Advanced methods in computer graphics: with examples in OpenGL

✍ Scribed by Mukundan, Ramakrishnan

• Publisher: Springer
• Year: 2012
• Tongue: English
• Leaves: 316
• 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

Advanced Methods in Computer Graphics......Page 3
Preface......Page 6
Contents......Page 8
1.1 Advanced Computer Graphics......Page 13
1.3 Notations......Page 14
1.4 Contents Overview......Page 15
2.1 Points and Vectors......Page 17
2.2 Signed Angle and Area......Page 21
2.3 Lines and Planes......Page 23
2.4 Intersection of 3 Planes......Page 26
2.5 Curves......Page 28
2.6 Affine Transformations......Page 29
2.7 Affine Combinations......Page 31
2.8 Barycentric Coordinates......Page 34
2.9 Basic Lighting......Page 36
2.11 Supplementary Material for Chap. 2......Page 38
References......Page 41
3.1 The Basic Structure of a Scene Graph......Page 43
3.2 Transformation Hierarchy......Page 45
3.2.1 A Mechanical Part......Page 46
3.2.2 A Simple Character Model......Page 47
3.2.3 A Planetary System......Page 48
3.3 Relative Transformations......Page 50
3.4 Bounding Volume Hierarchy......Page 52
3.5.1 Group Node......Page 55
3.5.2 Object Node......Page 56
3.5.4 Light Node......Page 57
3.6 First-Person View......Page 59
3.8 Supplementary Material for Chap. 3......Page 61
3.9 Bibliographical Notes......Page 63
References......Page 64
4.1 Articulated Character Models......Page 65
4.2 Vertex Blending......Page 67
4.3 Skeleton and Skin......Page 69
4.4.1 The Bind Pose......Page 71
4.4.2 Mesh Vertex Transformation......Page 72
4.5 Vertex Skinning Using Scene Graphs......Page 74
4.6 Transformation Blending......Page 76
4.7 Keyframe Animation......Page 78
4.8.2 Skinned Mesh Node......Page 81
4.9 Summary......Page 84
4.10 Supplementary Material for Chap. 4......Page 86
References......Page 88
5.1 Review of Complex Numbers......Page 89
5.2 Quaternion Algebra......Page 91
5.3 Quaternion Transformation......Page 93
5.4 Generalized Rotations......Page 95
5.4.1 Euler Angles......Page 96
5.4.2 Angle-Axis Transformation......Page 98
5.5 Quaternion Rotations......Page 100
5.5.1 Quaternion Transformation Matrix......Page 102
5.5.2 Quaternions and Euler Angles......Page 103
5.5.3 Negative Quaternion......Page 104
5.6 Rotation Interpolation......Page 105
5.6.1 Euler Angle Interpolation......Page 107
5.6.2 Axis-Angle Interpolation......Page 108
5.6.3 Quaternion Linear Interpolation (LERP)......Page 110
5.6.4 Quaternion Spherical Linear Interpolation (SLERP)......Page 111
5.7 Quaternion Exponentiation......Page 113
5.8 Relative Quaternions......Page 114
5.9.1 Dual Numbers......Page 116
5.9.2 Algebra of Dual Quaternions......Page 117
5.9.3 Transformations Using Dual Quaternions......Page 120
5.10 Summary......Page 121
5.11 Supplementary Material for Chap. 5......Page 122
5.12 Bibliographical Notes......Page 123
References......Page 124
6.1 Robot Manipulators......Page 125
6.2.1 Joint Chain in Two Dimensions......Page 127
6.2.2 Joint Chain in 3D Space......Page 128
6.3 Linear and Angular Velocity......Page 130
6.3.1 Velocity in Two Dimensions......Page 131
6.3.2 Velocity Under Euler Angle Transformations......Page 132
6.3.3 Quaternion Velocity......Page 133
6.3.4 The Jacobian......Page 135
6.4 Inverse Kinematics......Page 136
6.4.1 2-Link Inverse Kinematics......Page 137
6.4.2 n-Link Inverse Kinematics......Page 138
6.5 Gradient Descent......Page 140
6.6 Cyclic Coordinate Descent......Page 142
6.7 Circular Alignment Algorithm......Page 144
6.9 Supplementary Material for Chap. 6......Page 147
References......Page 148
7.1 Polynomial Interpolation......Page 150
7.2 Cubic Parametric Curves......Page 152
7.3 Parametric Continuity......Page 156
7.4 Hermite Splines......Page 158
7.5 Cardinal Splines......Page 160
7.6.1 Cubic Bezier Splines......Page 162
7.6.2 de-Casteljau's Algorithm......Page 165
7.7 Polynomial Interpolants......Page 167
7.8 B-Splines......Page 170
7.8.1 Basis Functions......Page 171
7.8.2 Approximating Curves......Page 174
7.8.3 NURBS......Page 177
7.9 Surface Patches......Page 178
7.10 Coons Patches......Page 181
7.11 Bi-Cubic Bezier Patches......Page 183
7.13 Supplementary Material for Chap. 7......Page 185
References......Page 188
8.1 Mesh Representation......Page 189
8.2 Polygonal Manifolds......Page 193
8.3 Mesh Data Structures......Page 196
8.3.1 Face-Based Data Structure......Page 197
8.3.2 Winged-Edge Data Structure......Page 198
8.3.3 Half-Edge Data Structure......Page 200
8.4.1 Vertex Decimation......Page 204
8.4.2 Edge Collapse Operation......Page 206
8.5.1 Subdivision Curves......Page 211
8.5.2 The Loop Subdivision Algorithm......Page 213
8.5.3 Catmull-Clark Subdivision......Page 215
8.5.4 Root-3 Subdivision......Page 217
8.6 Mesh Parameterization......Page 219
8.6.1 Barycentric Embedding......Page 220
8.6.2 Spherical Embedding......Page 224
8.7 Polygon Triangulation......Page 225
8.7.1 Polygon Types......Page 226
8.7.2 Edge-Flip Algorithm......Page 228
8.7.3 Three Coins Algorithm......Page 229
8.7.4 Triangulation of Monotone Polygons......Page 232
8.8 Summary......Page 234
8.9 Supplementary Material for Chap. 8......Page 236
8.10 Bibliographical Notes......Page 238
References......Page 239
9.1 Bounding Volumes......Page 240
9.1.2 Minimal Bounding Sphere......Page 241
9.1.3 Oriented Bounding Box (OBB)......Page 246
9.1.4 Discrete Oriented Polytope (k-DOP)......Page 248
9.1.5 Convex Hulls......Page 250
9.2.1 AABB Intersection......Page 252
9.2.2 OBB Intersection......Page 255
9.2.3 Sphere Intersection......Page 260
9.2.4 k-DOP Intersection......Page 261
9.2.5 Triangle Intersection......Page 262
9.3 Bounding Volume Hierarchies......Page 266
9.3.1 Top-Down Design......Page 267
9.3.2 Bottom-Up Design......Page 268
9.3.3 Collision Testing Using Hierarchy Traversal......Page 269
9.3.4 Cost Function......Page 271
9.4.1 Octrees......Page 272
9.4.2 k-d Trees......Page 276
9.4.3 Boundary Interval Hierarchy......Page 280
9.6 Supplementary Material for Chap. 9......Page 282
9.7 Bibliographical Notes......Page 284
References......Page 285
Appendices......Page 286
A.1 Point3 Class......Page 287
A.2 Vec3 Class......Page 289
A.3 Triangle Class......Page 290
A.4 Matrix Class......Page 292
B.1 GroupNode Class......Page 294
B.2 ObjectNode Class......Page 296
B.3 CameraNode Class......Page 297
B.4 LightNode Class......Page 298
C.1 SkeletonNode Class......Page 299
C.2 Skeleton Class......Page 302
C.3 SkinnedMesh Class......Page 303
D.1 Quaternion Class......Page 306
D.2 Dual Quaternion Class......Page 309
Index......Page 311