Geometric Tools for Computer Graphics (The Morgan Kaufmann Series in Computer Graphics)

Description

Do you spend too much time creating the building blocks of your graphics applications or finding and correcting errors? Geometric Tools for Computer Graphics is an extensive, conveniently organized collection of proven solutions to fundamental problems that you'd rather not solve over and over again, including building primitives, distance calculation, approximation, containment, decomposition, intersection determination, separation, and more. If you have a mathematics degree, this book will save you time and trouble. If you don't, it will help you achieve things you may feel are out of your reach. Inside, each problem is clearly stated and diagrammed, and the fully detailed solutions are presented in easy-to-understand pseudocode. You also get the mathematics and geometry background needed to make optimal use of the solutions, as well as an abundance of reference material contained in a series of appendices. Features Filled with robust, thoroughly tested solutions that will save you time and help you avoid costly errors. Covers problems relevant for both 2D and 3D graphics programming. Presents each problem and solution in stand-alone form allowing you the option of reading only those entries that matter to you. Provides the math and geometry background you need to understand the solutions and put them to work. Clearly diagrams each problem and presents solutions in easy-to-understand pseudocode. Resources associated with the book are available at the companion Web site www.mkp.com/gtcg. Table of Content 1 Introduction How to Use This Book Issues of Numerical Computation Low-Level Issues High-Level Issues A Summary of the Chapters 2 Matrices and Linear Systems Introduction Motivation Organization Notational Conventions Tuples Definition Arithmetic Operations Matrices Notation and Terminology Transposition Arithmetic Operations Matrix Multiplication Linear Systems Linear Equations Linear Systems in Two Unknowns General Linear Systems Row Reductions, Echelon Form, and Rank Square Matrices Diagonal Matrices Triangular Matrices The Determinant Inverse Linear Spaces Fields Definition and Properties Subspaces Linear Combinations and Span Linear Independence, Dimension, and Basis Linear Mappings Mappings in General Linear Mappings Matrix Representation of Linear Mappings Cramer’s Rule Eigenvalues and Eigenvectors Euclidean Space Inner Product Spaces Orthogonality and Orthonormal Sets Least Squares Recommended Reading 3 Vector Algebra Vector Basics Vector Equivalence Vector Addition Vector Subtraction Vector Scaling Properties of Vector Addition and Scalar Multiplication Vector Space Span Linear Independence Basis, Subspaces, and Dimension Orientation Change of Basis Linear Transformations Affine Spaces Euclidean Geometry Volume, the Determinant, and the Scalar Triple Product Frames Affine Transformations Types of Affine Maps Composition of Affine Maps Barycentric Coordinates and Simplexes Barycentric Coordinates and Subspaces Affine Independence 4 Matrices, Vector Algebra, and Transformations Introduction Matrix Representation of Points and Vectors Addition, Subtraction, and Multiplication Vector Addition and Subtraction Point and Vector Addition and Subtraction Subtraction of Points Scalar Multiplication Products of Vectors Dot Product Cross Product Tensor Product The 'Perp' Operator and the 'Perp Dot Product' Matrix Representation of Affine Transformations Change-of-Basis/Frame/Coordinate System Vector Geometry of Affine Transformations Notation Translation Rotation Scaling Reflection Shearing Projections Orthographic Oblique Perspective Transforming Normal Vectors Recommended Reading 5 Geometric Primitives in 2D Linear Components Implicit Form Parametric Form Converting between Representations Triangles Rectangles Polylines and Polygons Quadratic Curves Circles Ellipses Polynomial Curves Bezier Curves B-Spline Curves NURBS Curves 6 Distance in 2D Point to Linear Component Point to Line Point to Ray Point to Segment Point to Polyline Point to Polygon Point to Triangle Point to Rectangle Point to Orthogonal Frustum Point to Convex Polygon Point to Quadratic Curve Point to Polynomial Curve Linear Components Line to Line Line to Ray Line to Segment Ray to Ray Ray to Segment Segment to Segment Linear Component to Polyline or Polygon Linear Component to Quadratic Curve Linear Component to Polynomial Curve GJK Algorithm Set Operations Overview of the Algorithm Alternatives to GJK 7 Intersection in 2D Linear Components Linear Components and Polylines Linear Components and Quadratic Curves Linear Components and General Quadratic Curves Linear Components and Circular Components Linear Components and Polynomial Curves Algebraic Method Polyline Approximation Hierarchical Bounding Monotone Decomposition Rasterization Quadratic Curves General Quadratic Curves Circular Components Ellipses Polynomial Curves Algebraic Method Polyline Approximation Hierarchical Bounding Rasterization The Method of Separating Axes Separation by Projection onto a Line Separation of Stationary Convex Polygons Separation of Moving Convex Polygons Intersection Set for Stationary Convex Polygons Contact Set for Moving Convex Polygons 8 Miscellaneous 2D Problems Circle through Three Points Circle Tangent to Three Lines Line Tangent to a Circle at a Given Point Line Tangent to a Circle through a Given Point Lines Tangent to Two Circles Circle through Two Points with a Given Radius Circle through a Point and Tangent to a Line with a Given Radius Circles Tangent to Two Lines with a Given Radius Circles through a Point and Tangent to a Circle with a Given Radius Circles Tangent to a Line and a Circle with a Given Radius Circles Tangent to Two Circles with a Given Radius Line Perpendicular to a Given Line through a Given Point Line between and Equidistant to Two Points Line Parallel to a Given Line at a Given Distance Line Parallel to a Given Line at a Given Vertical (Horizontal) Distance Lines Tangent to a Given Circle and Normal to a Given Line 9 Geometric Primitives in 3D Linear Components Planar Components Planes Coordinate System Relative to a Plane 2D Objects in a Plane Polymeshes, Polyhedra, and Polytopes Vertex-Edge-Face Tables Connected Meshes Manifold Meshes Closed Meshes Consistent Ordering Platonic Solids Quadric Surfaces Three Nonzero Eigenvalues Two Nonzero Eigenvalues One Nonzero Eigenvalue Torus Polynomial Curves Bezier Curves B-Spline Curves NURBS Curves Polynomial Surfaces Bezier Surfaces B-Spline Surfaces NURBS Surfaces 10 Distance in 3D Introduction Point to Linear Component Point to Ray or Line Segment Point to Polyline Point to Planar Component Point to Plane Point to Triangle Point to Rectangle Point to Polygon Point to Circle or Disk Point to Polyhedron General Problem Point to Oriented Bounding Box Point to Orthogonal Frustum Point to Quadric Surface Point to General Quadric Surface Point to Ellipsoid Point to Polynomial Curve Point to Polynomial Surface Linear Components Lines and Lines Segment/Segment, Line/Ray, Line/Segment, Ray/ Ray, Ray/Segment Segment to Segment, Alternative Approach Linear Component to Triangle, Rectangle, Tetrahedron, Oriented Box Linear Component to Triangle Linear Component to Rectangle Linear Component to Tetrahedron Linear Component to Oriented Bounding Box Line to Quadric Surface Line to Polynomial Surface GJK Algorithm Miscellaneous Distance between Line and Planar Curve Distance between Line and Planar Solid Object Distance between Planar Curves Geodesic Distance on Surfaces 11 Intersection in 3D Linear Components and Planar Components Linear Components and Planes Linear Components and Triangles Linear Components and Polygons Linear Component and Disk Linear Components and Polyhedra Linear Components and Quadric Surfaces General Quadric Surfaces Linear Components and a Sphere Linear Components and an Ellipsoid Linear Components and Cylinders Linear Components and a Cone Linear Components and Polynomial Surfaces Algebraic Surfaces Free-Form Surfaces Planar Components Two Planes Three Planes Triangle and Plane Triangle and Triangle Planar Components and Polyhedra Trimeshes General Polyhedra Planar Components and Quadric Surfaces Plane and General Quadric Surface Plane and Sphere Plane and Cylinder Plane and Cone Triangle and Cone Planar Components and Polynomial Surfaces Hermite Curves Geometry Definitions Computing the Curves The Algorithm Implementation Notes Quadric Surfaces General Intersection Ellipsoids Polynomial Surfaces Subdivision Methods Lattice Evaluation Analytic Methods Marching Methods The Method of Separating Axes Separation of Stationary Convex Polyhedra Separation of Moving Convex Polyhedra Intersection Set for Stationary Convex Polyhedra Contact Set for Moving Convex Polyhedra Miscellaneous Oriented Bounding Box and Orthogonal Frustum Linear Component and Axis-Aligned Bounding Box Linear Component and Oriented Bounding Box Plane and Axis-Aligned Bounding Box Plane and Oriented Bounding Box Axis-Aligned Bounding Boxes Oriented Bounding Boxes Sphere and Axis-Aligned Bounding Box Cylinders Linear Component and Torus 12 Miscellaneous 3D Problems Projection of a Point onto a Plane Projection of a Vector onto a Plane Angle between a Line and a Plane Angle between Two Planes Plane Normal to a Line and through a Given Point Plane through Three Points Angle between Two Lines 13 Computational Geometry Topics Binary Space-Partitioning Trees in 2D BSP Tree Representation of a Polygon Minimum Splits versus Balanced Trees Point in Polygon Using BSP Trees Partitioning a Line Segment by a BSP Tree Binary Space-Partitioning Trees in 3D BSP Tree Representation of a Polyhedron Minimum Splits versus Balanced Trees Point in Polyhedron Using BSP Trees Partitioning a Line Segment by a BSP Tree Partitioning a Convex Polygon by a BSP Tree Point in Polygon Point in Triangle Point in Convex Polygon Point in General Polygon Faster Point in General Polygon A Grid Method Point in Polyhedron Point in Tetrahedron Point in Convex Polyhedron Point in General Polyhedron Boolean Operations on Polygons The Abstract Operations The Two Primitive Operations Boolean Operations Using BSP Trees Other Algorithms Boolean Operations on Polyhedra Abstract Operations Boolean Operations Using BSP Trees Convex Hulls Convex Hulls in 2D Convex Hulls in 3D Convex Hulls in Higher Dimensions Delaunay Triangulation Incremental Construction in 2D Incremental Construction in General Dimensions Construction by Convex Hull Polygon Partitioning Visibility Graph of a Simple Polygon Triangulation Triangulation by Horizontal Decomposition Convex Partitioning Circumscribed and Inscribed Balls Circumscribed Ball Inscribed Ball Minimum Bounds for Point Sets Minimum-Area Rectangle Minimum-Volume Box Minimum-Area Circle Minimum-Volume Sphere Miscellaneous Area and Volume Measurements Area of a 2D Polygon Area of a 3D Polygon Volume of a Polyhedron Appendix A Numerical Methods Solving Linear Systems A.1.1 Special Case: Solving a Triangular System A.1.2 Gaussian Elimination 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 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 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 Root Finding A.5.1 Methods in One Dimension A.5.2 Methods in Many Dimensions A.5.3 Stable Solution to Quadratic Equations 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 Least Squares Fitting A.7.1 Linear Fitting of Points A.7.2 Linear Fitting of Points Using Orthogonal Regression A.7.3 Planar Fitting of Points 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 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 Topics from Calculus A.9.1 Level Sets A.9.2 Minima and Maxima of Functions A.9.3 Lagrange Multipliers Appendix B Trigonometry Introduction B.1.1 Terminology B.1.2 Angles B.1.3 Conversion Examples 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 Trigonometric Identities and Laws B.3.1 Periodicity B.3.2 Laws B.3.3 Formulas 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 Further Reading Appendix C Basic Formulas for Geometric Primitives Introduction Triangles C.2.1 Symbols C.2.2 Definitions C.2.3 Right Triangles C.2.4 Equilateral Triangle C.2.5 General Triangle 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 Circles C.4.1 Symbols C.4.2 Full Circle C.4.3 Sector of a Circle C.4.4 Segment of a Circle Polyhedra C.5.1 Symbols C.5.2 Box C.5.3 Prism C.5.4 Pyramid Cylinder Cone Spheres C.8.1 Segments C.8.2 Sector Torus