Table of Contents for Geometric Tools for Computer Graphics

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
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 Reduction, 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   Definitions 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
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
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
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   Bezier Curves
          5.6.2   B-Splines Curves
          5.6.3   NURBS Curves
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
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
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  Line Tangent to a Given Circle and Normal to a Given Line
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   Bezier Curves
          9.6.2   B-Spline Curves
          9.6.3   NURBS Curves
    9.7   Polynomial Surfaces
          9.7.1   Bezier Surfaces
          9.7.2   B-Spline Surfaces
          9.7.3   NURBS Surfaces
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 Triagnle, 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 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
11  Intersection in 3D
    11.1  Linear Components and Planar Components
          11.11.1 Linear Components and Planes
          11.11.2 Linear Components and Triangles
          11.11.3 Linear Components and Polygons
          11.11.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 Surfaces
          11.7.1  Plane and General Quadric Surfaces
          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 Evaluations
          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
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
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 of a Line Segment by a BSP Tree
          13.2.5  Partitioning of 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 3D
          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 Sets
          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
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   Hyperplane 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 Quadratic Curve 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
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
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 Triangles
          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