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.
Author(s): Ramakrishnan Mukundan
Publisher: Springer
Year: 2012
Language: English
Pages: 314
Cover
Advanced Methods in Computer Graphics
Preface
Contents
Chapter 1: Introduction
1.1 Advanced Computer Graphics
1.2 Supplementary Material
1.3 Notations
1.4 Contents Overview
Chapter 2: Mathematical Preliminaries
2.1 Points and Vectors
2.2 Signed Angle and Area
2.3 Lines and Planes
2.4 Intersection of 3 Planes
2.5 Curves
2.6 Affine Transformations
2.7 Affine Combinations
2.8 Barycentric Coordinates
2.9 Basic Lighting
2.10 Summary
2.11 Supplementary Material for Chap. 2
2.12 Bibliographical Notes
References
Chapter 3: Scene Graphs
3.1 The Basic Structure of a Scene Graph
3.2 Transformation Hierarchy
3.2.1 A Mechanical Part
3.2.2 A Simple Character Model
3.2.3 A Planetary System
3.3 Relative Transformations
3.4 Bounding Volume Hierarchy
3.5 Sample Implementation
3.5.1 Group Node
3.5.2 Object Node
3.5.3 Camera Node
3.5.4 Light Node
3.6 First-Person View
3.7 Summary
3.8 Supplementary Material for Chap. 3
3.9 Bibliographical Notes
References
Chapter 4: Skeletal Animation
4.1 Articulated Character Models
4.2 Vertex Blending
4.3 Skeleton and Skin
4.4 Vertex Skinning
4.4.1 The Bind Pose
4.4.2 Mesh Vertex Transformation
4.5 Vertex Skinning Using Scene Graphs
4.6 Transformation Blending
4.7 Keyframe Animation
4.8 Sample Implementation of Vertex Skinning
4.8.1 Skeleton Node
4.8.2 Skinned Mesh Node
4.9 Summary
4.10 Supplementary Material for Chap. 4
4.11 Bibliographical Notes
References
Chapter 5: Quaternions
5.1 Review of Complex Numbers
5.2 Quaternion Algebra
5.3 Quaternion Transformation
5.4 Generalized Rotations
5.4.1 Euler Angles
5.4.2 Angle-Axis Transformation
5.5 Quaternion Rotations
5.5.1 Quaternion Transformation Matrix
5.5.2 Quaternions and Euler Angles
5.5.3 Negative Quaternion
5.6 Rotation Interpolation
5.6.1 Euler Angle Interpolation
5.6.2 Axis-Angle Interpolation
5.6.3 Quaternion Linear Interpolation (LERP)
5.6.4 Quaternion Spherical Linear Interpolation (SLERP)
5.7 Quaternion Exponentiation
5.8 Relative Quaternions
5.9 Dual Quaternions
5.9.1 Dual Numbers
5.9.2 Algebra of Dual Quaternions
5.9.3 Transformations Using Dual Quaternions
5.10 Summary
5.11 Supplementary Material for Chap. 5
5.12 Bibliographical Notes
References
Chapter 6: Kinematics
6.1 Robot Manipulators
6.2 Forward Kinematics
6.2.1 Joint Chain in Two Dimensions
6.2.2 Joint Chain in 3D Space
6.3 Linear and Angular Velocity
6.3.1 Velocity in Two Dimensions
6.3.2 Velocity Under Euler Angle Transformations
6.3.3 Quaternion Velocity
6.3.4 The Jacobian
6.4 Inverse Kinematics
6.4.1 2-Link Inverse Kinematics
6.4.2 n-Link Inverse Kinematics
6.5 Gradient Descent
6.6 Cyclic Coordinate Descent
6.7 Circular Alignment Algorithm
6.8 Summary
6.9 Supplementary Material for Chap. 6
6.10 Bibliographical Notes
References
Chapter 7: Curves and Surfaces
7.1 Polynomial Interpolation
7.2 Cubic Parametric Curves
7.3 Parametric Continuity
7.4 Hermite Splines
7.5 Cardinal Splines
7.6 Bezier Curves
7.6.1 Cubic Bezier Splines
7.6.2 de-Casteljau's Algorithm
7.6.3 Rational Bezier Curves
7.7 Polynomial Interpolants
7.8 B-Splines
7.8.1 Basis Functions
7.8.2 Approximating Curves
7.8.3 NURBS
7.9 Surface Patches
7.10 Coons Patches
7.11 Bi-Cubic Bezier Patches
7.12 Summary
7.13 Supplementary Material for Chap. 7
7.14 Bibliographical Notes
References
Chapter 8: Mesh Processing
8.1 Mesh Representation
8.2 Polygonal Manifolds
8.3 Mesh Data Structures
8.3.1 Face-Based Data Structure
8.3.2 Winged-Edge Data Structure
8.3.3 Half-Edge Data Structure
8.4 Mesh Simplification
8.4.1 Vertex Decimation
8.4.2 Edge Collapse Operation
8.5 Mesh Subdivision
8.5.1 Subdivision Curves
8.5.2 The Loop Subdivision Algorithm
8.5.3 Catmull-Clark Subdivision
8.5.4 Root-3 Subdivision
8.6 Mesh Parameterization
8.6.1 Barycentric Embedding
8.6.2 Spherical Embedding
8.7 Polygon Triangulation
8.7.1 Polygon Types
8.7.2 Edge-Flip Algorithm
8.7.3 Three Coins Algorithm
8.7.4 Triangulation of Monotone Polygons
8.8 Summary
8.9 Supplementary Material for Chap. 8
8.10 Bibliographical Notes
References
Chapter 9: Collision Detection
9.1 Bounding Volumes
9.1.1 Axis Aligned Bounding Box (AABB)
9.1.2 Minimal Bounding Sphere
9.1.3 Oriented Bounding Box (OBB)
9.1.4 Discrete Oriented Polytope (k-DOP)
9.1.5 Convex Hulls
9.2 Intersection Testing
9.2.1 AABB Intersection
9.2.2 OBB Intersection
9.2.3 Sphere Intersection
9.2.4 k-DOP Intersection
9.2.5 Triangle Intersection
9.3 Bounding Volume Hierarchies
9.3.1 Top-Down Design
9.3.2 Bottom-Up Design
9.3.3 Collision Testing Using Hierarchy Traversal
9.3.4 Cost Function
9.4 Spatial Partitioning
9.4.1 Octrees
9.4.2 k-d Trees
9.4.3 Boundary Interval Hierarchy
9.5 Summary
9.6 Supplementary Material for Chap. 9
9.7 Bibliographical Notes
References
Appendices
Appendix A: Geometry Classes
A.1 Point3 Class
A.2 Vec3 Class
A.3 Triangle Class
A.4 Matrix Class
Appendix B: Scene Graph Classes
B.1 GroupNode Class
B.2 ObjectNode Class
B.3 CameraNode Class
B.4 LightNode Class
Appendix C: Vertex Skinning Classes
C.1 SkeletonNode Class
C.2 Skeleton Class
C.3 SkinnedMesh Class
Appendix D: Quaternion Classes
D.1 Quaternion Class
D.2 Dual Quaternion Class
Index
