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

✍ Scribed by Philip Schneider, David H. Eberly

• Publisher: Morgan Kaufmann
• Year: 2002
• Tongue: English
• Leaves: 1043
• Edition: 1
• Category: Library

✦ Synopsis

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 Contents

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