Geometric Tools for Computer Graphics
Regular price
43.750 KD
inc. VAT
Couldn't load pickup availability
Table of contents
- Cover
- Contentsix
- 1 Introduction1
- How to Use This Book1
- Issues of Numerical Computation2
- Low-Level Issues2
- High-Level Issues4
- A Summary of the Chapters6
- 2 Matrices and Linear Systems9
- Introduction9
- Motivation9
- Organization13
- Notational Conventions14
- Tuples14
- Definition15
- Arithmetic Operations16
- Matrices16
- Notation and Terminology17
- Transposition17
- Arithmetic Operations18
- Matrix Multiplication20
- Linear Systems24
- Linear Equations24
- Linear Systems in Two Unknowns26
- General Linear Systems29
- Row Reductions, Echelon Form, and Rank30
- Square Matrices32
- Diagonal Matrices32
- Triangular Matrices34
- The Determinant34
- Inverse38
- Linear Spaces41
- Fields41
- Definition and Properties42
- Subspaces43
- Linear Combinations and Span43
- Linear Independence, Dimension, and Basis44
- Linear Mappings45
- Mappings in General45
- Linear Mappings47
- Matrix Representation of Linear Mappings49
- Cramer's Rule50
- Eigenvalues and Eigenvectors52
- Euclidean Space54
- Inner Product Spaces54
- Orthogonality and Orthonormal Sets55
- Least Squares56
- Recommended Reading60
- 3 Vector Algebra63
- Vector Basics63
- Vector Equivalence63
- Vector Addition64
- Vector Subtraction65
- Vector Scaling65
- Properties of Vector Addition and Scalar Multiplication66
- Vector Space69
- Span70
- Linear Independence71
- Basis, Subspaces, and Dimension71
- Orientation73
- Change of Basis75
- Linear Transformations76
- Affine Spaces80
- Euclidean Geometry84
- Volume, the Determinant, and the Scalar Triple Product94
- Frames96
- Affine Transformations98
- Types of Affine Maps103
- Composition of Affine Maps103
- Barycentric Coordinates and Simplexes104
- Barycentric Coordinates and Subspaces106
- Affine Independence106
- 4 Matrices, Vector Algebra, and Transformations109
- Introduction109
- Matrix Representation of Points and Vectors110
- Addition, Subtraction, and Multiplication113
- Vector Addition and Subtraction113
- Point and Vector Addition and Subtraction114
- Subtraction of Points115
- Scalar Multiplication115
- Products of Vectors115
- Dot Product116
- Cross Product117
- Tensor Product120
- The 'Perp' Operator and the ÏPerpÓ Dot Product121
- Matrix Representation of Affine Transformations126
- Change-of-Basis/Frame/Coordinate System128
- Vector Geometry of Affine Transformations132
- Notation133
- Translation134
- Rotation136
- Scaling142
- Reflection148
- Shearing153
- Projections158
- Orthographic159
- Oblique160
- Perspective163
- Transforming Normal Vectors165
- Recommended Reading168
- 5 Geometric Primitives in 2D171
- Linear Components171
- Implicit Form172
- Parametric Form173
- Converting between Representations174
- Triangles175
- Rectangles177
- Polylines and Polygons177
- Quadratic Curves181
- Circles183
- Ellipses183
- Polynomial Curves185
- Bezier Curves186
- B-Spline Curves186
- NURBS Curves188
- 6 Distance in 2D189
- Point to Linear Component190
- Point to Line190
- Point to Ray191
- Point to Segment192
- Point to Polyline194
- Point to Polygon196
- Point to Triangle196
- Point to Rectangle211
- Point to Orthogonal Frustum213
- Point to Convex Polygon216
- Point to Quadratic Curve217
- Point to Polynomial Curve219
- Linear Components221
- Line to Line221
- Line to Ray222
- Line to Segment223
- Ray to Ray224
- Ray to Segment226
- Segment to Segment228
- Linear Component to Polyline or Polygon229
- Linear Component to Quadratic Curve231
- Linear Component to Polynomial Curve233
- GJK Algorithm233
- Set Operations234
- Overview of the Algorithm235
- Alternatives to GJK238
- 7 Intersection in 2D241
- Linear Components241
- Linear Components and Polylines246
- Linear Components and Quadratic Curves246
- Linear Components and General Quadratic Curves247
- Linear Components and Circular Components247
- Linear Components and Polynomial Curves248
- Algebraic Method248
- Polyline Approximation250
- Hierarchical Bounding251
- Monotone Decomposition252
- Rasterization253
- Quadratic Curves255
- General Quadratic Curves255
- Circular Components257
- Ellipses258
- Polynomial Curves262
- Algebraic Method262
- Polyline Approximation262
- Hierarchical Bounding263
- Rasterization263
- The Method of Separating Axes265
- Separation by Projection onto a Line265
- Separation of Stationary Convex Polygons266
- Separation of Moving Convex Polygons273
- Intersection Set for Stationary Convex Polygons276
- Contact Set for Moving Convex Polygons277
- 8 Miscellaneous 2D Problems285
- Circle through Three Points285
- Circle Tangent to Three Lines285
- Line Tangent to a Circle at a Given Point287
- Line Tangent to a Circle through a Given Point288
- Lines Tangent to Two Circles291
- Circle through Two Points with a Given Radius297
- Circle through a Point and Tangent to a Line with a Given Radius298
- Circles Tangent to Two Lines with a Given Radius302
- Circles through a Point and Tangent to a Circle with a Given Radius305
- Circles Tangent to a Line and a Circle with a Given Radius309
- Circles Tangent to Two Circles with a Given Radius314
- Line Perpendicular to a Given Line through a Given Point316
- Line between and Equidistant to Two Points317
- Line Parallel to a Given Line at a Given Distance318
- Line Parallel to a Given Line at a Given Vertical ( Horizontal) Distance320
- Lines Tangent to a Given Circle and Normal to a Given Line322
- 9 Geometric Primitives in 3D325
- Linear Components325
- Planar Components326
- Planes326
- Coordinate System Relative to a Plane330
- 2D Objects in a Plane331
- Polymeshes, Polyhedra, and Polytopes333
- Vertex-Edge-Face Tables337
- Connected Meshes340
- Manifold Meshes342
- Closed Meshes342
- Consistent Ordering343
- Platonic Solids346
- Quadric Surfaces351
- Three Nonzero Eigenvalues351
- Two Nonzero Eigenvalues352
- One Nonzero Eigenvalue352
- Torus355
- Polynomial Curves356
- Bezier Curves357
- B-Spline Curves357
- NURBS Curves358
- Polynomial Surfaces359
- Bezier Surfaces360
- B-Spline Surfaces362
- NURBS Surfaces364
- 10 Distance in 3D365
- Introduction365
- Point to Linear Component365
- Point to Ray or Line Segment367
- Point to Polyline369
- Point to Planar Component374
- Point to Plane374
- Point to Triangle376
- Point to Rectangle382
- Point to Polygon385
- Point to Circle or Disk388
- Point to Polyhedron391
- General Problem391
- Point to Oriented Bounding Box394
- Point to Orthogonal Frustum397
- Point to Quadric Surface401
- Point to General Quadric Surface401
- Point to Ellipsoid403
- Point to Polynomial Curve405
- Point to Polynomial Surface407
- Linear Components409
- Lines and Lines409
- Segment/Segment, Line/Ray, Line/Segment, Ray/ Ray, Ray/ Segment412
- Segment to Segment, Alternative Approach426
- Linear Component to Triangle, Rectangle, Tetrahedron, Oriented Box433
- Linear Component to Triangle433
- Linear Component to Rectangle441
- Linear Component to Tetrahedron447
- Linear Component to Oriented Bounding Box450
- Line to Quadric Surface465
- Line to Polynomial Surface467
- GJK Algorithm468
- Miscellaneous469
- Distance between Line and Planar Curve469
- Distance between Line and Planar Solid Object471
- Distance between Planar Curves472
- Geodesic Distance on Surfaces477
- 11 Intersection in 3D481
- Linear Components and Planar Components481
- Linear Components and Planes482
- Linear Components and Triangles485
- Linear Components and Polygons488
- Linear Component and Disk491
- Linear Components and Polyhedra493
- Linear Components and Quadric Surfaces498
- General Quadric Surfaces499
- Linear Components and a Sphere501
- Linear Components and an Ellipsoid504
- Linear Components and Cylinders507
- Linear Components and a Cone512
- Linear Components and Polynomial Surfaces519
- Algebraic Surfaces520
- Free-Form Surfaces521
- Planar Components529
- Two Planes529
- Three Planes532
- Triangle and Plane534
- Triangle and Triangle539
- Planar Components and Polyhedra543
- Trimeshes543
- General Polyhedra544
- Planar Components and Quadric Surfaces547
- Plane and General Quadric Surface547
- Plane and Sphere548
- Plane and Cylinder551
- Plane and Cone563
- Triangle and Cone583
- Planar Components and Polynomial Surfaces587
- Hermite Curves589
- Geometry Definitions590
- Computing the Curves591
- The Algorithm592
- Implementation Notes595
- Quadric Surfaces595
- General Intersection596
- Ellipsoids604
- Polynomial Surfaces608
- Subdivision Methods608
- Lattice Evaluation609
- Analytic Methods610
- Marching Methods610
- The Method of Separating Axes611
- Separation of Stationary Convex Polyhedra611
- Separation of Moving Convex Polyhedra615
- Intersection Set for Stationary Convex Polyhedra616
- Contact Set for Moving Convex Polyhedra616
- Miscellaneous624
- Oriented Bounding Box and Orthogonal Frustum624
- Linear Component and Axis-Aligned Bounding Box626
- Linear Component and Oriented Bounding Box630
- Plane and Axis-Aligned Bounding Box634
- Plane and Oriented Bounding Box635
- Axis-Aligned Bounding Boxes637
- Oriented Bounding Boxes639
- Sphere and Axis-Aligned Bounding Box644
- Cylinders646
- Linear Component and Torus659
- 12 Miscellaneous 3D Problems663
- Projection of a Point onto a Plane663
- Projection of a Vector onto a Plane665
- Angle between a Line and a Plane666
- Angle between Two Planes667
- Plane Normal to a Line and through a Given Point667
- Plane through Three Points669
- Angle between Two Lines670
- 13 Computational Geometry Topics673
- Binary Space-Partitioning Trees in 2D673
- BSP Tree Representation of a Polygon674
- Minimum Splits versus Balanced Trees680
- Point in Polygon Using BSP Trees683
- Partitioning a Line Segment by a BSP Tree684
- Binary Space-Partitioning Trees in 3D687
- BSP Tree Representation of a Polyhedron688
- Minimum Splits versus Balanced Trees690
- Point in Polyhedron Using BSP Trees691
- Partitioning a Line Segment by a BSP Tree692
- Partitioning a Convex Polygon by a BSP Tree694
- Point in Polygon695
- Point in Triangle695
- Point in Convex Polygon697
- Point in General Polygon700
- Faster Point in General Polygon706
- A Grid Method707
- Point in Polyhedron708
- Point in Tetrahedron708
- Point in Convex Polyhedron709
- Point in General Polyhedron711
- Boolean Operations on Polygons714
- The Abstract Operations715
- The Two Primitive Operations717
- Boolean Operations Using BSP Trees719
- Other Algorithms724
- Boolean Operations on Polyhedra726
- Abstract Operations726
- Boolean Operations Using BSP Trees727
- Convex Hulls729
- Convex Hulls in 2D729
- Convex Hulls in 3D744
- Convex Hulls in Higher Dimensions750
- Delaunay Triangulation756
- Incremental Construction in 2D757
- Incremental Construction in General Dimensions761
- Construction by Convex Hull766
- Polygon Partitioning767
- Visibility Graph of a Simple Polygon767
- Triangulation771
- Triangulation by Horizontal Decomposition775
- Convex Partitioning789
- Circumscribed and Inscribed Balls798
- Circumscribed Ball799
- Inscribed Ball801
- Minimum Bounds for Point Sets803
- Minimum-Area Rectangle803
- Minimum-Volume Box806
- Minimum-Area Circle807
- Minimum-Volume Sphere811
- Miscellaneous813
- Area and Volume Measurements816
- Area of a 2D Polygon816
- Area of a 3D Polygon820
- Volume of a Polyhedron824
- Appendix A Numerical Methods827
- Solving Linear Systems827
- A.1.1 Special Case: Solving a Triangular System828
- A.1.2 Gaussian Elimination829
- Systems of Polynomials832
- A.2.1 Linear Equations in One Formal Variable833
- A.2.2 Any-Degree Equations in One Formal Variable835
- A.2.3 Any-Degree Equations in Any Formal Variables837
- Matrix Decompositions847
- A.3.1 Euler Angle Factorization847
- A.3.2 QR Decomposition852
- A.3.3 Eigendecomposition853
- A.3.4 Polar Decomposition854
- A.3.5 Singular Value Decomposition857
- Representations of 3D Rotations857
- A.4.1 Matrix Representation857
- A.4.2 Axis-Angle Representation858
- A.4.3 Quaternion Representation860
- A.4.4 Performance Issues861
- Root Finding869
- A.5.1 Methods in One Dimension869
- A.5.2 Methods in Many Dimensions874
- A.5.3 Stable Solution to Quadratic Equations875
- Minimization876
- A.6.1 Methods in One Dimension876
- A.6.2 Methods in Many Dimensions877
- A.6.3 Minimizing a Quadratic Form880
- A.6.4 Minimizing a Restricted Quadratic Form880
- Least Squares Fitting882
- A.7.1 Linear Fitting of Points882
- A.7.2 Linear Fitting of Points Using Orthogonal Regression882
- A.7.3 Planar Fitting of Points884
- A.7.4 Hyperplanar Fitting of Points Using Orthogonal Regression884
- A.7.5 Fitting a Circle to 2D Points886
- A.7.6 Fitting a Sphere to 3D Points887
- A.7.7 Fitting a Quadratic Curve to 2D Points888
- A.7.8 Fitting a Quadric Surface to 3D Points889
- Subdivision of Curves889
- A.8.1 Subdivision by Uniform Sampling889
- A.8.2 Subdivision by Arc Length890
- A.8.3 Subdivision by Midpoint Distance891
- A.8.4 Subdivision by Variation892
- Topics from Calculus894
- A.9.1 Level Sets894
- A.9.2 Minima and Maxima of Functions898
- A.9.3 Lagrange Multipliers910
- Appendix B Trigonometry923
- Introduction923
- B.1.1 Terminology923
- B.1.2 Angles923
- B.1.3 Conversion Examples925
- Trigonometric Functions926
- B.2.1 Definitions in Terms of Exponentials930
- B.2.2 Domains and Ranges931
- B.2.3 Graphs of Trigonometric Functions931
- B.2.4 Derivatives of Trigonometric Functions931
- B.2.5 Integration934
- Trigonometric Identities and Laws934
- B.3.1 Periodicity935
- B.3.2 Laws936
- B.3.3 Formulas940
- Inverse Trigonometric Functions945
- B.4.1 Defining arcsin and arccos in Terms of arctan945
- B.4.2 Domains and Ranges945
- B.4.3 Graphs946
- B.4.4 Derivatives946
- B.4.5 Integration948
- Further Reading948
- Appendix C Basic Formulas for Geometric Primitives949
- Introduction949
- Triangles949
- C.2.1 Symbols949
- C.2.2 Definitions950
- C.2.3 Right Triangles952
- C.2.4 Equilateral Triangle953
- C.2.5 General Triangle953
- Quadrilaterals954
- C.3.1 Square954
- C.3.2 Rectangle954
- C.3.3 Parallelogram954
- C.3.4 Rhombus955
- C.3.5 Trapezoid955
- C.3.6 General Quadrilateral955
- Circles956
- C.4.1 Symbols956
- C.4.2 Full Circle956
- C.4.3 Sector of a Circle956
- C.4.4 Segment of a Circle957
- Polyhedra957
- C.5.1 Symbols957
- C.5.2 Box957
- C.5.3 Prism958
- C.5.4 Pyramid958
- Cylinder958
- Cone959
- Spheres959
- C.8.1 Segments959
- C.8.2 Sector960
- Torus960
- Index960
- A973
- B974
- C976
- D979
- E981
- F982
- G983
- H984
- I984
- J–K986
- L987
- M989
- N991
- O992
- P993
- Q999
- R1000
- S1001
- T1004
- U1006
- V1006
- W1007
- X1007
- Y1007
- Z1007
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.
* 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.