Geometric Tools for Computer Graphics

ForewordFiguresTablesPreface Chapter 1 Introduction 1.1 How to Use This Book 1.2 Issues of Numerical Computation 1.2.1 Low-Level Issues 1.2.2 High-Level Issues 1.3 A Summary of the Chapters Chapter 2 Matrices and Linear Systems 2.1 Introduction 2.1.1 Motivation 2.1.2 Organization 2.1.3 Notational Conventions 2.2 Tuples 2.2.1 Definition 2.2.2 Arithmetic Operations 2.3 Matrices 2.3.1 Notation and Terminology 2.3.2 Transposition 2.3.3 Arithmetic Operations 2.3.4 Matrix Multiplication 2.4 Linear Systems 2.4.1 Linear Equations 2.4.2 Linear Systems in Two Unknowns 2.4.3 General Linear Systems 2.4.4 Row Reductions, Echelon Form, and Rank 2.5 Square Matrices 2.5.1 Diagonal Matrices 2.5.2 Triangular Matrices 2.5.3 The Determinant 2.5.4 Inverse 2.6 Linear Spaces 2.6.1 Fields 2.6.2 Definition and Properties 2.6.3 Subspaces 2.6.4 Linear Combinations and Span 2.6.5 Linear Independence, Dimension, and Basis 2.7 Linear Mappings 2.7.1 Mappings in General 2.7.2 Linear Mappings 2.7.3 Matrix Representation of Linear Mappings 2.7.4 Cramer’s Rule 2.8 Eigenvalues and Eigenvectors 2.9 Euclidean Space 2.9.1 Inner Product Spaces 2.9.2 Orthogonality and Orthonormal Sets 2.10 Least Squares Recommended Reading Chapter 3 Vector Algebra 3.1 Vector Basics 3.1.1 Vector Equivalence 3.1.2 Vector Addition 3.1.3 Vector Subtraction 3.1.4 Vector Scaling 3.1.5 Properties of Vector Addition and Scalar Multiplication 3.2 Vector Space 3.2.1 Span 3.2.2 Linear Independence 3.2.3 Basis, Subspaces, and Dimension 3.2.4 Orientation 3.2.5 Change of Basis 3.2.6 Linear Transformations 3.3 Affine Spaces 3.3.1 Euclidean Geometry 3.3.2 Volume, the Determinant, and the Scalar Triple Product 3.3.3 Frames 3.4 Affine Transformations 3.4.1 Types of Affine Maps 3.4.2 Composition of Affine Maps 3.5 Barycentric Coordinates and Simplexes 3.5.1 Barycentric Coordinates and Subspaces 3.5.2 Affine Independence Chapter 4 Matrices, Vector Algebra, and Transformations 4.1 Introduction 4.2 Matrix Representation of Points and Vectors 4.3 Addition, Subtraction, and Multiplication 4.3.1 Vector Addition and Subtraction 4.3.2 Point and Vector Addition and Subtraction 4.3.3 Subtraction of Points 4.3.4 Scalar Multiplication 4.4 Products of Vectors 4.4.1 Dot Product 4.4.2 Cross Product 4.4.3 Tensor Product 4.4.4 The “Perp” Operator and the “Perp” Dot Product 4.5 Matrix Representation of Affine Transformations 4.6 Change-of-Basis/Frame/Coordinate System 4.7 Vector Geometry of Affine Transformations 4.7.1 Notation 4.7.2 Translation 4.7.3 Rotation 4.7.4 Scaling 4.7.5 Reflection 4.7.6 Shearing 4.8 Projections 4.8.1 Orthographic 4.8.2 Oblique 4.8.3 Perspective 4.9 Transforming Normal Vectors Recommended Reading Chapter 5 Geometric Primitives in 2D 5.1 Linear Components 5.1.1 Implicit Form 5.1.2 Parametric Form 5.1.3 Converting between Representations 5.2 Triangles 5.3 Rectangles 5.4 Polylines and Polygons 5.5 Quadratic Curves 5.5.1 Circles 5.5.2 Ellipses 5.6 Polynomial Curves 5.6.1 B´ezier Curves 5.6.2 B-Spline Curves 5.6.3 NURBS Curves Chapter 6 Distance in 2D 6.1 Point to Linear Component 6.1.1 Point to Line 6.1.2 Point to Ray 6.1.3 Point to Segment 6.2 Point to Polyline 6.3 Point to Polygon 6.3.1 Point to Triangle 6.3.2 Point to Rectangle 6.3.3 Point to Orthogonal Frustum 6.3.4 Point to Convex Polygon 6.4 Point to Quadratic Curve 6.5 Point to Polynomial Curve 6.6 Linear Components 6.6.1 Line to Line 6.6.2 Line to Ray 6.6.3 Line to Segment 6.6.4 Ray to Ray 6.6.5 Ray to Segment 6.6.6 Segment to Segment 6.7 Linear Component to Polyline or Polygon 6.8 Linear Component to Quadratic Curve 6.9 Linear Component to Polynomial Curve 6.10 GJK Algorithm 6.10.1 Set Operations 6.10.2 Overview of the Algorithm 6.10.3 Alternatives to GJK Chapter 7 Intersection in 2D 7.1 Linear Components 7.2 Linear Components and Polylines 7.3 Linear Components and Quadratic Curves 7.3.1 Linear Components and General Quadratic Curves 7.3.2 Linear Components and Circular Components 7.4 Linear Components and Polynomial Curves 7.4.1 Algebraic Method 7.4.2 Polyline Approximation 7.4.3 Hierarchical Bounding 7.4.4 Monotone Decomposition 7.4.5 Rasterization 7.5 Quadratic Curves 7.5.1 General Quadratic Curves 7.5.2 Circular Components 7.5.3 Ellipses 7.6 Polynomial Curves 7.6.1 Algebraic Method 7.6.2 Polyline Approximation 7.6.3 Hierarchical Bounding 7.6.4 Rasterization 7.7 The Method of Separating Axes 7.7.1 Separation by Projection onto a Line 7.7.2 Separation of Stationary Convex Polygons 7.7.3 Separation of Moving Convex Polygons 7.7.4 Intersection Set for Stationary Convex Polygons 7.7.5 Contact Set for Moving Convex Polygons Chapter 8 Miscellaneous 2D Problems 8.1 Circle through Three Points 8.2 Circle Tangent to Three Lines 8.3 Line Tangent to a Circle at a Given Point 8.4 Line Tangent to a Circle through a Given Point 8.5 Lines Tangent to Two Circles 8.6 Circle through Two Points with a Given Radius 8.7 Circle through a Point and Tangent to a Line with a Given Radius 8.8 Circles Tangent to Two Lines with a Given Radius 8.9 Circles through a Point and Tangent to a Circle with a Given Radius 8.10 Circles Tangent to a Line and a Circle with a Given Radius 8.11 Circles Tangent to Two Circles with a Given Radius 8.12 Line Perpendicular to a Given Line through a Given Point 8.13 Line between and Equidistant to Two Points 8.14 Line Parallel to a Given Line at a Given Distance 8.15 Line Parallel to a Given Line at a Given Vertical (Horizontal) Distance 8.16 Lines Tangent to a Given Circle and Normal to a Given Line Chapter 9 Geometric Primitives in 3D 9.1 Linear Components 9.2 Planar Components 9.2.1 Planes 9.2.2 Coordinate System Relative to a Plane 9.2.3 2D Objects in a Plane 9.3 Polymeshes, Polyhedra, and Polytopes 9.3.1 Vertex-Edge-Face Tables 9.3.2 Connected Meshes 9.3.3 Manifold Meshes 9.3.4 Closed Meshes 9.3.5 Consistent Ordering 9.3.6 Platonic Solids 9.4 Quadric Surfaces 9.4.1 Three Nonzero Eigenvalues 9.4.2 Two Nonzero Eigenvalues 9.4.3 One Nonzero Eigenvalue 9.5 Torus 9.6 Polynomial Curves 9.6.1 Bézier Curves 9.6.2 B-Spline Curves 9.6.3 NURBS Curves 9.7 Polynomial Surfaces 9.7.1 Bézier Surfaces 9.7.2 B-Spline Surfaces 9.7.3 NURBS Surfaces Chapter 10 Distance in 3D 10.1 Introduction 10.2 Point to Linear Component 10.2.1 Point to Ray or Line Segment 10.2.2 Point to Polyline 10.3 Point to Planar Component 10.3.1 Point to Plane 10.3.2 Point to Triangle 10.3.3 Point to Rectangle 10.3.4 Point to Polygon 10.3.5 Point to Circle or Disk 10.4 Point to Polyhedron 10.4.1 General Problem 10.4.2 Point to Oriented Bounding Box 10.4.3 Point to Orthogonal Frustum 10.5 Point to Quadric Surface 10.5.1 Point to General Quadric Surface 10.5.2 Point to Ellipsoid 10.6 Point to Polynomial Curve 10.7 Point to Polynomial Surface 10.8 Linear Components 10.8.1 Lines and Lines 10.8.2 Segment/Segment, Line/Ray, Line/Segment, Ray/Ray, Ray/Segment 10.8.3 Segment to Segment, Alternative Approach 10.9 Linear Component to Triangle, Rectangle, Tetrahedron, Oriented Box 10.9.1 Linear Component to Triangle 10.9.2 Linear Component to Rectangle 10.9.3 Linear Component to Tetrahedron 10.9.4 Linear Component to Oriented Bounding Box 10.10 Line to Quadric Surface 10.11 Line to Polynomial Surface 10.12 GJK Algorithm 10.13 Miscellaneous 10.13.1 Distance between Line and Planar Curve 10.13.2 Distance between Line and Planar Solid Object 10.13.3 Distance between Planar Curves 10.13.4 Geodesic Distance on Surfaces Chapter 11 Intersection in 3D 11.1 Linear Components and Planar Components 11.1.1 Linear Components and Planes 11.1.2 Linear Components and Triangles 11.1.3 Linear Components and Polygons 11.1.4 Linear Component and Disk 11.2 Linear Components and Polyhedra 11.3 Linear Components and Quadric Surfaces 11.3.1 General Quadric Surfaces 11.3.2 Linear Components and a Sphere 11.3.3 Linear Components and an Ellipsoid 11.3.4 Linear Components and Cylinders 11.3.5 Linear Components and a Cone 11.4 Linear Components and Polynomial Surfaces 11.4.1 Algebraic Surfaces 11.4.2 Free-Form Surfaces 11.5 Planar Components 11.5.1 Two Planes 11.5.2 Three Planes 11.5.3 Triangle and Plane 11.5.4 Triangle and Triangle 11.6 Planar Components and Polyhedra 11.6.1 Trimeshes 11.6.2 General Polyhedra 11.7 Planar Components and Quadric Surface 11.7.1 Plane and General Quadric Surface 11.7.2 Plane and Sphere 11.7.3 Plane and Cylinder 11.7.4 Plane and Cone 11.7.5 Triangle and Cone 11.8 Planar Components and Polynomial Surfaces 11.8.1 Hermite Curves 11.8.2 Geometry Definitions 11.8.3 Computing the Curves 11.8.4 The Algorithm 11.8.5 Implementation Notes 11.9 Quadric Surfaces 11.9.1 General Intersection 11.9.2 Ellipsoids 11.10 Polynomial Surfaces 11.10.1 Subdivision Methods 11.10.2 Lattice Evaluation 11.10.3 Analytic Methods 11.10.4 Marching Methods 11.11 The Method of Separating Axes 11.11.1 Separation of Stationary Convex Polyhedra 11.11.2 Separation of Moving Convex Polyhedra 11.11.3 Intersection Set for Stationary Convex Polyhedra 11.11.4 Contact Set for Moving Convex Polyhedra 11.12 Miscellaneous 11.12.1 Oriented Bounding Box and Orthogonal Frustum 11.12.2 Linear Component and Axis-Aligned Bounding Box 11.12.3 Linear Component and Oriented Bounding Box 11.12.4 Plane and Axis-Aligned Bounding Box 11.12.5 Plane and Oriented Bounding Box 11.12.6 Axis-Aligned Bounding Boxes 11.12.7 Oriented Bounding Boxes 11.12.8 Sphere and Axis-Aligned Bounding Box 11.12.9 Cylinders 11.12.10 Linear Component and Torus Chapter 12 Miscellaneous 3D Problems 12.1 Projection of a Point onto a Plane 12.2 Projection of a Vector onto a Plane 12.3 Angle between a Line and a Plane 12.4 Angle between Two Planes 12.5 Plane Normal to a Line and through a Given Point 12.6 Plane through Three Points 12.7 Angle between Two Lines Chapter 13 Computational Geometry Topics 13.1 Binary Space-Partitioning Trees in 2D 13.1.1 BSP Tree Representation of a Polygon 13.1.2 Minimum Splits versus Balanced Trees 13.1.3 Point in Polygon Using BSP Trees 13.1.4 Partitioning a Line Segment by a BSP Tree 13.2 Binary Space-Partitioning Trees in 3D 13.2.1 BSP Tree Representation of a Polyhedron 13.2.2 Minimum Splits versus Balanced Trees 13.2.3 Point in Polyhedron Using BSP Trees 13.2.4 Partitioning a Line Segment by a BSP Tree 13.2.5 Partitioning a Convex Polygon by a BSP Tree 13.3 Point in Polygon 13.3.1 Point in Triangle 13.3.2 Point in Convex Polygon 13.3.3 Point in General Polygon 13.3.4 Faster Point in General Polygon 13.3.5 A Grid Method 13.4 Point in Polyhedron 13.4.1 Point in Tetrahedron 13.4.2 Point in Convex Polyhedron 13.4.3 Point in General Polyhedron 13.5 Boolean Operations on Polygons 13.5.1 The Abstract Operations 13.5.2 The Two Primitive Operations 13.5.3 Boolean Operations Using BSP Trees 13.5.4 Other Algorithms 13.6 Boolean Operations on Polyhedra 13.6.1 Abstract Operations 13.6.2 Boolean Operations Using BSP Trees 13.7 Convex Hulls 13.7.1 Convex Hulls in 2D 13.7.2 Convex Hulls in 3D 13.7.3 Convex Hulls in Higher Dimensions 13.8 Delaunay Triangulation 13.8.1 Incremental Construction in 2D 13.8.2 Incremental Construction in General Dimensions 13.8.3 Construction by Convex Hull 13.9 Polygon Partitioning 13.9.1 Visibility Graph of a Simple Polygon 13.9.2 Triangulation 13.9.3 Triangulation by Horizontal Decomposition 13.9.4 Convex Partitioning 13.10 Circumscribed and Inscribed Balls 13.10.1 Circumscribed Ball 13.10.2 Inscribed Ball 13.11 Minimum Bounds for Point Set 13.11.1 Minimum-Area Rectangle 13.11.2 Minimum-Volume Box 13.11.3 Minimum-Area Circle 13.11.4 Minimum-Volume Sphere 13.11.5 Miscellaneous 13.12 Area and Volume Measurements 13.12.1 Area of a 2D Polygon 13.12.2 Area of a 3D Polygon 13.12.3 Volume of a Polyhedron Appendix A Numerical Methods A.1 Solving Linear Systems A.1.1 Special Case: Solving a Triangular System A.1.2 Gaussian Elimination A.2 Systems of Polynomials A.2.1 Linear Equations in One Formal Variable A.2.2 Any-Degree Equations in One Formal Variable A.2.3 Any-Degree Equations in Any Formal Variables A.3 Matrix Decompositions A.3.1 Euler Angle Factorization A.3.2 QR Decomposition A.3.3 Eigendecomposition A.3.4 Polar Decomposition A.3.5 Singular Value Decomposition A.4 Representations of 3D Rotations A.4.1 Matrix Representation A.4.2 Axis-Angle Representation A.4.3 Quaternion Representation A.4.4 Performance Issues A.5 Root Finding A.5.1 Methods in One Dimension A.5.2 Methods in Many Dimensions A.5.3 Stable Solution to Quadratic Equations A.6 Minimization A.6.1 Methods in One Dimension A.6.2 Methods in Many Dimensions A.6.3 Minimizing a Quadratic Form A.6.4 Minimizing a Restricted Quadratic Form A.7 Least Squares Fitting A.7.1 Linear Fitting of Points (x, f (x)) A.7.2 Linear Fitting of Points Using Orthogonal Regression A.7.3 Planar Fitting of Points (x, y, f (x, y)) A.7.4 Hyperplanar Fitting of Points Using Orthogonal Regression A.7.5 Fitting a Circle to 2D Points A.7.6 Fitting a Sphere to 3D Points A.7.7 Fitting a Quadratic Curve to 2D Points A.7.8 Fitting a Quadric Surface to 3D Points A.8 Subdivision of Curves A.8.1 Subdivision by Uniform Sampling A.8.2 Subdivision by Arc Length A.8.3 Subdivision by Midpoint Distance A.8.4 Subdivision by Variation A.9 Topics from Calculus A.9.1 Level Sets A.9.2 Minima and Maxima of Functions A.9.3 Lagrange Multipliers Appendix B Trigonometry B.1 Introduction B.1.1 Terminology B.1.2 Angles B.1.3 Conversion Examples B.2 Trigonometric Functions B.2.1 Definitions in Terms of Exponentials B.2.2 Domains and Ranges B.2.3 Graphs of Trigonometric Functions B.2.4 Derivatives of Trigonometric Functions B.2.5 Integration B.3 Trigonometric Identities and Laws B.3.1 Periodicity B.3.2 Laws B.3.3 Formulas B.4 Inverse Trigonometric Functions B.4.1 Defining arcsin and arccos in Terms of arctan B.4.2 Domains and Ranges B.4.3 Graphs B.4.4 Derivatives B.4.5 Integration B.5 Further Reading Appendix C Basic Formulas for Geometric Primitives C.1 Introduction C.2 Triangles C.2.1 Symbols C.2.2 Definitions C.2.3 Right Triangles C.2.4 Equilateral Triangle C.2.5 General Triangle C.3 Quadrilaterals C.3.1 Square C.3.2 Rectangle C.3.3 Parallelogram C.3.4 Rhombus C.3.5 Trapezoid C.3.6 General Quadrilateral C.4 Circles C.4.1 Symbols C.4.2 Full Circle C.4.3 Sector of a Circle C.4.4 Segment of a Circle C.5 Polyhedra C.5.1 Symbols C.5.2 Box C.5.3 Prism C.5.4 Pyramid C.6 Cylinder C.7 Cone C.8 Spheres C.8.1 Segments C.8.2 Sector C.9 Torus References Index About the Authors