Advanced Methods in Computer Graphics: With examples in OpenGL

✍ Scribed by Ramakrishnan Mukundan

• Publisher: Springer
• Year: 2012
• Tongue: English
• Leaves: 319
• Edition: 2012
• Category: Library

✦ Synopsis

This book brings together several advanced topics in computer graphics that are important in the areas of game development, three-dimensional animation and real-time rendering. The book is designed for final-year undergraduate or first-year graduate students, who are already familiar with the basic concepts in computer graphics and programming. It aims to provide a good foundation of advanced methods such as skeletal animation, quaternions, mesh processing and collision detection. These and other methods covered in the book are fundamental to the development of algorithms used in commercial applications as well as research.

✦ Table of Contents

Cover......Page 1
Advanced Methods in Computer Graphics......Page 4
Preface......Page 8
Contents......Page 10
1.1 Advanced Computer Graphics......Page 16
1.3 Notations......Page 17
1.4 Contents Overview......Page 18
2.1 Points and Vectors......Page 20
2.2 Signed Angle and Area......Page 24
2.3 Lines and Planes......Page 26
2.4 Intersection of 3 Planes......Page 29
2.5 Curves......Page 31
2.6 Affine Transformations......Page 32
2.7 Affine Combinations......Page 34
2.8 Barycentric Coordinates......Page 37
2.9 Basic Lighting......Page 39
2.11 Supplementary Material for Chap. 2......Page 41
References......Page 44
3.1 The Basic Structure of a Scene Graph......Page 46
3.2 Transformation Hierarchy......Page 48
3.2.1 A Mechanical Part......Page 49
3.2.2 A Simple Character Model......Page 50
3.2.3 A Planetary System......Page 51
3.3 Relative Transformations......Page 53
3.4 Bounding Volume Hierarchy......Page 55
3.5.1 Group Node......Page 58
3.5.2 Object Node......Page 59
3.5.4 Light Node......Page 60
3.6 First-Person View......Page 62
3.8 Supplementary Material for Chap. 3......Page 64
3.9 Bibliographical Notes......Page 66
References......Page 67
4.1 Articulated Character Models......Page 68
4.2 Vertex Blending......Page 70
4.3 Skeleton and Skin......Page 72
4.4.1 The Bind Pose......Page 74
4.4.2 Mesh Vertex Transformation......Page 75
4.5 Vertex Skinning Using Scene Graphs......Page 77
4.6 Transformation Blending......Page 79
4.7 Keyframe Animation......Page 81
4.8.2 Skinned Mesh Node......Page 84
4.9 Summary......Page 87
4.10 Supplementary Material for Chap. 4......Page 89
References......Page 91
5.1 Review of Complex Numbers......Page 92
5.2 Quaternion Algebra......Page 94
5.3 Quaternion Transformation......Page 96
5.4 Generalized Rotations......Page 98
5.4.1 Euler Angles......Page 99
5.4.2 Angle-Axis Transformation......Page 101
5.5 Quaternion Rotations......Page 103
5.5.1 Quaternion Transformation Matrix......Page 105
5.5.2 Quaternions and Euler Angles......Page 106
5.5.3 Negative Quaternion......Page 107
5.6 Rotation Interpolation......Page 108
5.6.1 Euler Angle Interpolation......Page 110
5.6.2 Axis-Angle Interpolation......Page 111
5.6.3 Quaternion Linear Interpolation (LERP)......Page 113
5.6.4 Quaternion Spherical Linear Interpolation (SLERP)......Page 114
5.7 Quaternion Exponentiation......Page 116
5.8 Relative Quaternions......Page 117
5.9.1 Dual Numbers......Page 119
5.9.2 Algebra of Dual Quaternions......Page 120
5.9.3 Transformations Using Dual Quaternions......Page 123
5.10 Summary......Page 124
5.11 Supplementary Material for Chap. 5......Page 125
5.12 Bibliographical Notes......Page 126
References......Page 127
6.1 Robot Manipulators......Page 128
6.2.1 Joint Chain in Two Dimensions......Page 130
6.2.2 Joint Chain in 3D Space......Page 131
6.3 Linear and Angular Velocity......Page 133
6.3.1 Velocity in Two Dimensions......Page 134
6.3.2 Velocity Under Euler Angle Transformations......Page 135
6.3.3 Quaternion Velocity......Page 136
6.3.4 The Jacobian......Page 138
6.4 Inverse Kinematics......Page 139
6.4.1 2-Link Inverse Kinematics......Page 140
6.4.2 n-Link Inverse Kinematics......Page 141
6.5 Gradient Descent......Page 143
6.6 Cyclic Coordinate Descent......Page 145
6.7 Circular Alignment Algorithm......Page 147
6.9 Supplementary Material for Chap. 6......Page 150
References......Page 151
7.1 Polynomial Interpolation......Page 153
7.2 Cubic Parametric Curves......Page 155
7.3 Parametric Continuity......Page 159
7.4 Hermite Splines......Page 161
7.5 Cardinal Splines......Page 163
7.6.1 Cubic Bezier Splines......Page 165
7.6.2 de-Casteljau's Algorithm......Page 168
7.7 Polynomial Interpolants......Page 170
7.8 B-Splines......Page 173
7.8.1 Basis Functions......Page 174
7.8.2 Approximating Curves......Page 177
7.8.3 NURBS......Page 180
7.9 Surface Patches......Page 181
7.10 Coons Patches......Page 184
7.11 Bi-Cubic Bezier Patches......Page 186
7.13 Supplementary Material for Chap. 7......Page 188
References......Page 191
8.1 Mesh Representation......Page 192
8.2 Polygonal Manifolds......Page 196
8.3 Mesh Data Structures......Page 199
8.3.1 Face-Based Data Structure......Page 200
8.3.2 Winged-Edge Data Structure......Page 201
8.3.3 Half-Edge Data Structure......Page 203
8.4.1 Vertex Decimation......Page 207
8.4.2 Edge Collapse Operation......Page 209
8.5.1 Subdivision Curves......Page 214
8.5.2 The Loop Subdivision Algorithm......Page 216
8.5.3 Catmull-Clark Subdivision......Page 218
8.5.4 Root-3 Subdivision......Page 220
8.6 Mesh Parameterization......Page 222
8.6.1 Barycentric Embedding......Page 223
8.6.2 Spherical Embedding......Page 227
8.7 Polygon Triangulation......Page 228
8.7.1 Polygon Types......Page 229
8.7.2 Edge-Flip Algorithm......Page 231
8.7.3 Three Coins Algorithm......Page 232
8.7.4 Triangulation of Monotone Polygons......Page 235
8.8 Summary......Page 237
8.9 Supplementary Material for Chap. 8......Page 239
8.10 Bibliographical Notes......Page 241
References......Page 242
9.1 Bounding Volumes......Page 243
9.1.2 Minimal Bounding Sphere......Page 244
9.1.3 Oriented Bounding Box (OBB)......Page 249
9.1.4 Discrete Oriented Polytope (k-DOP)......Page 251
9.1.5 Convex Hulls......Page 253
9.2.1 AABB Intersection......Page 255
9.2.2 OBB Intersection......Page 258
9.2.3 Sphere Intersection......Page 263
9.2.4 k-DOP Intersection......Page 264
9.2.5 Triangle Intersection......Page 265
9.3 Bounding Volume Hierarchies......Page 269
9.3.1 Top-Down Design......Page 270
9.3.2 Bottom-Up Design......Page 271
9.3.3 Collision Testing Using Hierarchy Traversal......Page 272
9.3.4 Cost Function......Page 274
9.4.1 Octrees......Page 275
9.4.2 k-d Trees......Page 279
9.4.3 Boundary Interval Hierarchy......Page 283
9.6 Supplementary Material for Chap. 9......Page 285
9.7 Bibliographical Notes......Page 287
References......Page 288
Appendices......Page 289
A.1 Point3 Class......Page 290
A.2 Vec3 Class......Page 292
A.3 Triangle Class......Page 293
A.4 Matrix Class......Page 295
B.1 GroupNode Class......Page 297
B.2 ObjectNode Class......Page 299
B.3 CameraNode Class......Page 300
B.4 LightNode Class......Page 301
C.1 SkeletonNode Class......Page 302
C.2 Skeleton Class......Page 305
C.3 SkinnedMesh Class......Page 306
D.1 Quaternion Class......Page 309
D.2 Dual Quaternion Class......Page 312
Index......Page 314