Geometric Tools for Computer Graphics

✍ Scribed by Schneider, Philip J;Eberly, David H

• Publisher: Morgan Kaufmann Publishers
• Year: 2002
• Tongue: English
• Leaves: 1056
• 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 Graphicsis 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 sitewww.mkp.com/gtcg.

✦ Table of Contents

How to Use This Book......Page 48
Low-Level Issues......Page 49
High-Level Issues......Page 51
A Summary of the Chapters......Page 53
Motivation......Page 56
Organization......Page 60
Tuples......Page 61
Definition......Page 62
Matrices......Page 63
Transposition......Page 64
Arithmetic Operations......Page 65
Matrix Multiplication......Page 67
Linear Equations......Page 71
Linear Systems in Two Unknowns......Page 73
General Linear Systems......Page 76
Row Reductions, Echelon Form, and Rank......Page 77
Diagonal Matrices......Page 79
The Determinant......Page 81
Inverse......Page 85
Fields......Page 88
Definition and Properties......Page 89
Linear Combinations and Span......Page 90
Linear Independence, Dimension, and Basis......Page 91
Mappings in General......Page 92
Linear Mappings......Page 94
Matrix Representation of Linear Mappings......Page 96
Cramer's Rule......Page 97
Eigenvalues and Eigenvectors......Page 99
Inner Product Spaces......Page 101
Orthogonality and Orthonormal Sets......Page 102
Least Squares......Page 103
Recommended Reading......Page 107
Vector Equivalence......Page 110
Vector Addition......Page 111
Vector Scaling......Page 112
Properties of Vector Addition and Scalar Multiplication......Page 113
Vector Space......Page 116
Span......Page 117
Basis, Subspaces, and Dimension......Page 118
Orientation......Page 120
Change of Basis......Page 122
Linear Transformations......Page 123
Affine Spaces......Page 127
Euclidean Geometry......Page 131
Volume, the Determinant, and the Scalar Triple Product......Page 141
Frames......Page 143
Affine Transformations......Page 145
Composition of Affine Maps......Page 150
Barycentric Coordinates and Simplexes......Page 151
Affine Independence......Page 153
Introduction......Page 156
Matrix Representation of Points and Vectors......Page 157
Vector Addition and Subtraction......Page 160
Point and Vector Addition and Subtraction......Page 161
Products of Vectors......Page 162
Dot Product......Page 163
Cross Product......Page 164
Tensor Product......Page 167
The 'Perp' Operator and the ÏPerpÓ Dot Product......Page 168
Matrix Representation of Affine Transformations......Page 173
Change-of-Basis/Frame/Coordinate System......Page 175
Vector Geometry of Affine Transformations......Page 179
Notation......Page 180
Translation......Page 181
Rotation......Page 183
Scaling......Page 189
Reflection......Page 195
Shearing......Page 200
Projections......Page 205
Orthographic......Page 206
Oblique......Page 207
Perspective......Page 210
Transforming Normal Vectors......Page 212
Recommended Reading......Page 215
Linear Components......Page 218
Implicit Form......Page 219
Parametric Form......Page 220
Converting between Representations......Page 221
Triangles......Page 222
Polylines and Polygons......Page 224
Quadratic Curves......Page 228
Ellipses......Page 230
Polynomial Curves......Page 232
B-Spline Curves......Page 233
NURBS Curves......Page 235
6 Distance in 2D......Page 236
Point to Line......Page 237
Point to Ray......Page 238
Point to Segment......Page 239
Point to Polyline......Page 241
Point to Triangle......Page 243
Point to Rectangle......Page 258
Point to Orthogonal Frustum......Page 260
Point to Convex Polygon......Page 263
Point to Quadratic Curve......Page 264
Point to Polynomial Curve......Page 266
Line to Line......Page 268
Line to Ray......Page 269
Line to Segment......Page 270
Ray to Ray......Page 271
Ray to Segment......Page 273
Segment to Segment......Page 275
Linear Component to Polyline or Polygon......Page 276
Linear Component to Quadratic Curve......Page 278
GJK Algorithm......Page 280
Set Operations......Page 281
Overview of the Algorithm......Page 282
Alternatives to GJK......Page 285
Linear Components......Page 288
Linear Components and Quadratic Curves......Page 293
Linear Components and Circular Components......Page 294
Algebraic Method......Page 295
Polyline Approximation......Page 297
Hierarchical Bounding......Page 298
Monotone Decomposition......Page 299
Rasterization......Page 300
General Quadratic Curves......Page 302
Circular Components......Page 304
Ellipses......Page 305
Polyline Approximation......Page 309
Rasterization......Page 310
Separation by Projection onto a Line......Page 312
Separation of Stationary Convex Polygons......Page 313
Separation of Moving Convex Polygons......Page 320
Intersection Set for Stationary Convex Polygons......Page 323
Contact Set for Moving Convex Polygons......Page 324
Circle Tangent to Three Lines......Page 332
Line Tangent to a Circle at a Given Point......Page 334
Line Tangent to a Circle through a Given Point......Page 335
Lines Tangent to Two Circles......Page 338
Circle through Two Points with a Given Radius......Page 344
Circle through a Point and Tangent to a Line with a Given Radius......Page 345
Circles Tangent to Two Lines with a Given Radius......Page 349
Circles through a Point and Tangent to a Circle with a Given Radius......Page 352
Circles Tangent to a Line and a Circle with a Given Radius......Page 356
Circles Tangent to Two Circles with a Given Radius......Page 361
Line Perpendicular to a Given Line through a Given Point......Page 363
Line between and Equidistant to Two Points......Page 364
Line Parallel to a Given Line at a Given Distance......Page 365
Line Parallel to a Given Line at a Given Vertical ( Horizontal) Distance......Page 367
Lines Tangent to a Given Circle and Normal to a Given Line......Page 369
Linear Components......Page 372
Planes......Page 373
Coordinate System Relative to a Plane......Page 377
2D Objects in a Plane......Page 378
Polymeshes, Polyhedra, and Polytopes......Page 380
Vertex-Edge-Face Tables......Page 384
Connected Meshes......Page 387
Closed Meshes......Page 389
Consistent Ordering......Page 390
Platonic Solids......Page 393
Three Nonzero Eigenvalues......Page 398
One Nonzero Eigenvalue......Page 399
Torus......Page 402
Polynomial Curves......Page 403
B-Spline Curves......Page 404
NURBS Curves......Page 405
Polynomial Surfaces......Page 406
Bezier Surfaces......Page 407
B-Spline Surfaces......Page 409
NURBS Surfaces......Page 411
Point to Linear Component......Page 412
Point to Ray or Line Segment......Page 414
Point to Polyline......Page 416
Point to Plane......Page 421
Point to Triangle......Page 423
Point to Rectangle......Page 429
Point to Polygon......Page 432
Point to Circle or Disk......Page 435
General Problem......Page 438
Point to Oriented Bounding Box......Page 441
Point to Orthogonal Frustum......Page 444
Point to General Quadric Surface......Page 448
Point to Ellipsoid......Page 450
Point to Polynomial Curve......Page 452
Point to Polynomial Surface......Page 454
Lines and Lines......Page 456
Segment/Segment, Line/Ray, Line/Segment, Ray/ Ray, Ray/ Segment......Page 459
Segment to Segment, Alternative Approach......Page 473
Linear Component to Triangle......Page 480
Linear Component to Rectangle......Page 488
Linear Component to Tetrahedron......Page 494
Linear Component to Oriented Bounding Box......Page 497
Line to Quadric Surface......Page 512
Line to Polynomial Surface......Page 514
GJK Algorithm......Page 515
Distance between Line and Planar Curve......Page 516
Distance between Line and Planar Solid Object......Page 518
Distance between Planar Curves......Page 519
Geodesic Distance on Surfaces......Page 524
Linear Components and Planar Components......Page 528
Linear Components and Planes......Page 529
Linear Components and Triangles......Page 532
Linear Components and Polygons......Page 535
Linear Component and Disk......Page 538
Linear Components and Polyhedra......Page 540
Linear Components and Quadric Surfaces......Page 545
General Quadric Surfaces......Page 546
Linear Components and a Sphere......Page 548
Linear Components and an Ellipsoid......Page 551
Linear Components and Cylinders......Page 554
Linear Components and a Cone......Page 559
Linear Components and Polynomial Surfaces......Page 566
Algebraic Surfaces......Page 567
Free-Form Surfaces......Page 568
Two Planes......Page 576
Three Planes......Page 579
Triangle and Plane......Page 581
Triangle and Triangle......Page 586
Trimeshes......Page 590
General Polyhedra......Page 591
Plane and General Quadric Surface......Page 594
Plane and Sphere......Page 595
Plane and Cylinder......Page 598
Plane and Cone......Page 610
Triangle and Cone......Page 630
Planar Components and Polynomial Surfaces......Page 634
Hermite Curves......Page 636
Geometry Definitions......Page 637
Computing the Curves......Page 638
The Algorithm......Page 639
Quadric Surfaces......Page 642
General Intersection......Page 643
Ellipsoids......Page 651
Subdivision Methods......Page 655
Lattice Evaluation......Page 656
Marching Methods......Page 657
Separation of Stationary Convex Polyhedra......Page 658
Separation of Moving Convex Polyhedra......Page 662
Contact Set for Moving Convex Polyhedra......Page 663
Oriented Bounding Box and Orthogonal Frustum......Page 671
Linear Component and Axis-Aligned Bounding Box......Page 673
Linear Component and Oriented Bounding Box......Page 677
Plane and Axis-Aligned Bounding Box......Page 681
Plane and Oriented Bounding Box......Page 682
Axis-Aligned Bounding Boxes......Page 684
Oriented Bounding Boxes......Page 686
Sphere and Axis-Aligned Bounding Box......Page 691
Cylinders......Page 693
Linear Component and Torus......Page 706
Projection of a Point onto a Plane......Page 710
Projection of a Vector onto a Plane......Page 712
Angle between a Line and a Plane......Page 713
Plane Normal to a Line and through a Given Point......Page 714
Plane through Three Points......Page 716
Angle between Two Lines......Page 717
Binary Space-Partitioning Trees in 2D......Page 720
BSP Tree Representation of a Polygon......Page 721
Minimum Splits versus Balanced Trees......Page 727
Point in Polygon Using BSP Trees......Page 730
Partitioning a Line Segment by a BSP Tree......Page 731
Binary Space-Partitioning Trees in 3D......Page 734
BSP Tree Representation of a Polyhedron......Page 735
Minimum Splits versus Balanced Trees......Page 737
Point in Polyhedron Using BSP Trees......Page 738
Partitioning a Line Segment by a BSP Tree......Page 739
Partitioning a Convex Polygon by a BSP Tree......Page 741
Point in Triangle......Page 742
Point in Convex Polygon......Page 744
Point in General Polygon......Page 747
Faster Point in General Polygon......Page 753
A Grid Method......Page 754
Point in Tetrahedron......Page 755
Point in Convex Polyhedron......Page 756
Point in General Polyhedron......Page 758
Boolean Operations on Polygons......Page 761
The Abstract Operations......Page 762
The Two Primitive Operations......Page 764
Boolean Operations Using BSP Trees......Page 766
Other Algorithms......Page 771
Abstract Operations......Page 773
Boolean Operations Using BSP Trees......Page 774
Convex Hulls in 2D......Page 776
Convex Hulls in 3D......Page 791
Convex Hulls in Higher Dimensions......Page 797
Delaunay Triangulation......Page 803
Incremental Construction in 2D......Page 804
Incremental Construction in General Dimensions......Page 808
Construction by Convex Hull......Page 813
Visibility Graph of a Simple Polygon......Page 814
Triangulation......Page 818
Triangulation by Horizontal Decomposition......Page 822
Convex Partitioning......Page 836
Circumscribed and Inscribed Balls......Page 845
Circumscribed Ball......Page 846
Inscribed Ball......Page 848
Minimum-Area Rectangle......Page 850
Minimum-Volume Box......Page 853
Minimum-Area Circle......Page 854
Minimum-Volume Sphere......Page 858
Miscellaneous......Page 860
Area of a 2D Polygon......Page 863
Area of a 3D Polygon......Page 867
Volume of a Polyhedron......Page 871
Solving Linear Systems......Page 874
A.1.1 Special Case: Solving a Triangular System......Page 875
A.1.2 Gaussian Elimination......Page 876
Systems of Polynomials......Page 879
A.2.1 Linear Equations in One Formal Variable......Page 880
A.2.2 Any-Degree Equations in One Formal Variable......Page 882
A.2.3 Any-Degree Equations in Any Formal Variables......Page 884
A.3.1 Euler Angle Factorization......Page 894
A.3.2 QR Decomposition......Page 899
A.3.3 Eigendecomposition......Page 900
A.3.4 Polar Decomposition......Page 901
A.4.1 Matrix Representation......Page 904
A.4.2 Axis-Angle Representation......Page 905
A.4.3 Quaternion Representation......Page 907
A.4.4 Performance Issues......Page 908
A.5.1 Methods in One Dimension......Page 916
A.5.2 Methods in Many Dimensions......Page 921
A.5.3 Stable Solution to Quadratic Equations......Page 922
A.6.1 Methods in One Dimension......Page 923
A.6.2 Methods in Many Dimensions......Page 924
A.6.4 Minimizing a Restricted Quadratic Form......Page 927
A.7.2 Linear Fitting of Points Using Orthogonal Regression......Page 929
A.7.4 Hyperplanar Fitting of Points Using Orthogonal Regression......Page 931
A.7.5 Fitting a Circle to 2D Points......Page 933
A.7.6 Fitting a Sphere to 3D Points......Page 934
A.7.7 Fitting a Quadratic Curve to 2D Points......Page 935
A.8.1 Subdivision by Uniform Sampling......Page 936
A.8.2 Subdivision by Arc Length......Page 937
A.8.3 Subdivision by Midpoint Distance......Page 938
A.8.4 Subdivision by Variation......Page 939
A.9.1 Level Sets......Page 941
A.9.2 Minima and Maxima of Functions......Page 945
A.9.3 Lagrange Multipliers......Page 957
B.1.2 Angles......Page 970
B.1.3 Conversion Examples......Page 972
Trigonometric Functions......Page 973
B.2.1 Definitions in Terms of Exponentials......Page 977
B.2.4 Derivatives of Trigonometric Functions......Page 978
Trigonometric Identities and Laws......Page 981
B.3.1 Periodicity......Page 982
B.3.2 Laws......Page 983
B.3.3 Formulas......Page 987
B.4.2 Domains and Ranges......Page 992
B.4.4 Derivatives......Page 993
Further Reading......Page 995
C.2.1 Symbols......Page 996
C.2.2 Definitions......Page 997
C.2.3 Right Triangles......Page 999
C.2.5 General Triangle......Page 1000
C.3.3 Parallelogram......Page 1001
C.3.6 General Quadrilateral......Page 1002
C.4.3 Sector of a Circle......Page 1003
C.5.2 Box......Page 1004
Cylinder......Page 1005
C.8.1 Segments......Page 1006
Torus......Page 1007
References......Page 1008
A......Page 1020
B......Page 1021
C......Page 1023
D......Page 1026
E......Page 1028
F......Page 1029
G......Page 1030
I......Page 1031
J–K......Page 1033
L......Page 1034
M......Page 1036
N......Page 1038
O......Page 1039
P......Page 1040
Q......Page 1046
R......Page 1047
S......Page 1048
T......Page 1051
V......Page 1053
Z......Page 1054

✦ Subjects

Computer Science;Technical;Reference