# Geometric Tools for Computer Graphics

## 1st Edition

**Authors:**Philip Schneider Philip Schneider David Eberly

**Hardcover ISBN:**9781558605947

**eBook ISBN:**9780080478029

**Imprint:**Morgan Kaufmann

**Published Date:**26th September 2002

**Page Count:**1056

**View all volumes in this series:**The Morgan Kaufmann Series in Computer Graphics

## Table of Contents

Foreword

Figures

Tables

Preface

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

## Description

Foreword

Figures

Tables

Preface

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

## Key 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.

## Readership

Programmers, software engineers, and technical directors whose work involves 2D or 3D computer graphics for filmmaking including special effects and animation programming, gane development, visualization, medical image analysis, simulation, virtual worlds, and other software development.

## Details

- No. of pages:
- 1056

- Language:
- English

- Copyright:
- © Morgan Kaufmann 2003

- Published:
- 26th September 2002

- Imprint:
- Morgan Kaufmann

- eBook ISBN:
- 9780080478029

- Hardcover ISBN:
- 9781558605947

## Reviews

"An hour of a programmer's time often costs more than the price of a book. By this measure, you hold a volume potentially worth thousands of dollars. That it can be purchased for a fraction of this cost I consider a modern miracle. The amount of information crammed into this book is incredible." --Eric Haines

## About the Authors

### Philip Schneider Author

24 years of professional programming, primarily focused on modeling tools and geometric algorithms. Employers include Digital Equipment Corporation, Apple, Walt Disney Feature Animation, Digital Domain, and Industrial Light + Magic. Formed and lead groups specializing in these areas as well as in physics simulation.

Film Credits: Oil & Vinegar, 102 Dalmatians, Disney's Magic Lamp, Mickey's Philharmagic, Reign of Fire, Kangaroo Jack, Chicken Little, Indiana Jones and the Kingdom of the Crystal Skull, Pirates of the Caribbean: Dead Man's Chest, Harry Potter and the Goblet of Fire.

ACM Siggraph, IEEE.

M.S. in Computer Science, University of Washington.

### Affiliations and Expertise

24 years of professional programming, primarily focused on modeling tools and geometric algorithms. Employers include Digital Equipment Corporation, Apple, Walt Disney Feature Animation, Digital Domain, and Industrial Light + Magic. Formed and lead groups specializing in these areas as well as in physics simulation. Film Credits: Oil & Vinegar, 102 Dalmatians, Disney's Magic Lamp, Mickey's Philharmagic, Reign of Fire, Kangaroo Jack, Chicken Little, Indiana Jones and the Kingdom of the Crystal Skull, Pirates of the Caribbean: Dead Man's Chest, Harry Potter and the Goblet of Fire. ACM Siggraph, IEEE. M.S. in Computer Science, University of Washington.

### Philip Schneider Author

24 years of professional programming, primarily focused on modeling tools and geometric algorithms. Employers include Digital Equipment Corporation, Apple, Walt Disney Feature Animation, Digital Domain, and Industrial Light + Magic. Formed and lead groups specializing in these areas as well as in physics simulation.

Film Credits: Oil & Vinegar, 102 Dalmatians, Disney's Magic Lamp, Mickey's Philharmagic, Reign of Fire, Kangaroo Jack, Chicken Little, Indiana Jones and the Kingdom of the Crystal Skull, Pirates of the Caribbean: Dead Man's Chest, Harry Potter and the Goblet of Fire.

ACM Siggraph, IEEE.

M.S. in Computer Science, University of Washington.

### Affiliations and Expertise

24 years of professional programming, primarily focused on modeling tools and geometric algorithms. Employers include Digital Equipment Corporation, Apple, Walt Disney Feature Animation, Digital Domain, and Industrial Light + Magic. Formed and lead groups specializing in these areas as well as in physics simulation. Film Credits: Oil & Vinegar, 102 Dalmatians, Disney's Magic Lamp, Mickey's Philharmagic, Reign of Fire, Kangaroo Jack, Chicken Little, Indiana Jones and the Kingdom of the Crystal Skull, Pirates of the Caribbean: Dead Man's Chest, Harry Potter and the Goblet of Fire. ACM Siggraph, IEEE. M.S. in Computer Science, University of Washington.

### David Eberly Author

Dave Eberly is the president of Geometric Tools, Inc. (*www.geometrictools.com*), a company that specializes in software development for computer graphics, image analysis, and numerical methods. Previously, he was the director of engineering at Numerical Design Ltd. (NDL), the company responsible for the real-time 3D game engine, NetImmerse. He also worked for NDL on Gamebryo, which was the next-generation engine after NetImmerse. His background includes a BA degree in mathematics from Bloomsburg University, MS and PhD degrees in mathematics from the University of Colorado at Boulder, and MS and PhD degrees in computer science from the University of North Carolina at ChapelHill. He is the author of **3D Game Engine Design, 2nd Edition** (2006), **3D Game Engine Architecture** (2005), **Game Physics** (2004), and coauthor with Philip Schneider of **Geometric Tools for Computer Graphics** (2003), all published by Morgan Kaufmann. As a mathematician, Dave did research in the mathematics of combustion, signal and image processing, and length-biased distributions in statistics. He was an associate professor at the University of Texas at San Antonio with an adjunct appointment in radiology at the U.T. Health Science Center at San Antonio. In 1991, he gave up his tenured position to re-train in computer science at the University of North Carolina. After graduating in 1994, he remained for one year as a research associate professor in computer science with a joint appointment in the Department of Neurosurgery, working in medical image analysis. His next stop was the SAS Institute, working for a year on SAS/Insight, a statistical graphics package. Finally, deciding that computer graphics and geometry were his real calling, Dave went to work for NDL (which is now Emergent Game Technologies), then to Magic Software, Inc., which later became Geometric Tools, Inc. Dave’s participation in the newsgroup comp.graphics.algorit

### Affiliations and Expertise

President of Geometric Tools, Inc (www.geometrictools.com), a company that specializes in software development for computer graphics, image analysis, and numerical methods. Previously, he was the Director of Engineering at Numerical Design Ltd (NDL), the company responsible for the real-time 3D game engine, Netlmmerse. His background includes a BA in Mathematics from Bloomsburg U, MS and PhD degrees in Mathematics from the U of Colorado at Boulder, and MS and PhD degrees in computer science from the U of North Carolina at Chapel Hill.