Advanced Methods in Computer Graphics : With Examples in OpenGL

"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"--Provided by publisher 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 Advanced Methods in Computer Graphics provides an in-depth analysis ℗¡of a selection of topics that are important in the areas of character animation and game development. ℗¡The discussion of a wide range of algorithms and their implementation aspects presented in the book will serve as a useful reference for researchers and practitioners in computer graphics. ℗¡Students will find the book to be a valuable resource in their study of advanced graphics concepts.℗¡ The key topics covered in the book are ℗¡hierarchical modelling and transformations using scene graphs, skeletal animation, forward and inverse kinematics solutions, ℗¡quaternion based rotation interpolation, mesh processing and collision detection algorithms. The book also gives a thorough overview of splines, interpolation curves, and surface design methods. Features: Comprehensive coverage of a large collection of methods used in animation and game programming. Detailed description of the theoretical aspects of algorithms, complemented by examples, figures and pseudo-codes. Each chapter accompanied by a set of demonstration programs that clearly show the implementation and working of key algorithms. The C++ source code of all the examples, demos and classes for each chapter can be downloaded from the publisher's website, http://extras.springer.com/978-1-4471-2339-2. Ramakrishnan Mukundan is an associate professor in the Department of Computer Science and Software Engineering at the University of Canterbury, Christchurch, New Zealand. He has been teaching computer graphics courses at both undergraduate and graduate levels for the past twelve years.℗¡℗¡