Geometric Tools for Computer Graphics (eBook)
1056 Seiten
Elsevier Science (Verlag)
978-0-08-047802-9 (ISBN)
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.
* 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.
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.
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.
1 Introduction 45
How to Use This Book 45
Issues of Numerical Computation 46
Low-Level Issues 46
High-Level Issues 48
A Summary of the Chapters 50
2 Matrices and Linear Systems 53
Introduction 53
Motivation 53
Organization 57
Notational Conventions 58
Tuples 58
Definition 59
Arithmetic Operations 60
Matrices 60
Notation and Terminology 61
Transposition 61
Arithmetic Operations 62
Matrix Multiplication 64
Linear Systems 68
Linear Equations 68
Linear Systems in Two Unknowns 70
General Linear Systems 73
Row Reductions, Echelon Form, and Rank 74
Square Matrices 76
Diagonal Matrices 76
Triangular Matrices 78
The Determinant 78
Inverse 82
Linear Spaces 85
Fields 85
Definition and Properties 86
Subspaces 87
Linear Combinations and Span 87
Linear Independence, Dimension, and Basis 88
Linear Mappings 89
Mappings in General 89
Linear Mappings 91
Matrix Representation of Linear Mappings 93
Cramer's Rule 94
Eigenvalues and Eigenvectors 96
Euclidean Space 98
Inner Product Spaces 98
Orthogonality and Orthonormal Sets 99
Least Squares 100
Recommended Reading 104
3 Vector Algebra 107
Vector Basics 107
Vector Equivalence 107
Vector Addition 108
Vector Subtraction 109
Vector Scaling 109
Properties of Vector Addition and Scalar Multiplication 110
Vector Space 113
Span 114
Linear Independence 115
Basis, Subspaces, and Dimension 115
Orientation 117
Change of Basis 119
Linear Transformations 120
Affine Spaces 124
Euclidean Geometry 128
Volume, the Determinant, and the Scalar Triple Product 138
Frames 140
Affine Transformations 142
Types of Affine Maps 147
Composition of Affine Maps 147
Barycentric Coordinates and Simplexes 148
Barycentric Coordinates and Subspaces 150
Affine Independence 150
4 Matrices, Vector Algebra, and Transformations 153
Introduction 153
Matrix Representation of Points and Vectors 154
Addition, Subtraction, and Multiplication 157
Vector Addition and Subtraction 157
Point and Vector Addition and Subtraction 158
Subtraction of Points 159
Scalar Multiplication 159
Products of Vectors 159
Dot Product 160
Cross Product 161
Tensor Product 164
The 'Perp' Operator and the ÏPerpÓ Dot Product 165
Matrix Representation of Affine Transformations 170
Change-of-Basis/Frame/Coordinate System 172
Vector Geometry of Affine Transformations 176
Notation 177
Translation 178
Rotation 180
Scaling 186
Reflection 192
Shearing 197
Projections 202
Orthographic 203
Oblique 204
Perspective 207
Transforming Normal Vectors 209
Recommended Reading 212
5 Geometric Primitives in 2D 215
Linear Components 215
Implicit Form 216
Parametric Form 217
Converting between Representations 218
Triangles 219
Rectangles 221
Polylines and Polygons 221
Quadratic Curves 225
Circles 227
Ellipses 227
Polynomial Curves 229
Bezier Curves 230
B-Spline Curves 230
NURBS Curves 232
6 Distance in 2D 233
Point to Linear Component 234
Point to Line 234
Point to Ray 235
Point to Segment 236
Point to Polyline 238
Point to Polygon 240
Point to Triangle 240
Point to Rectangle 255
Point to Orthogonal Frustum 257
Point to Convex Polygon 260
Point to Quadratic Curve 261
Point to Polynomial Curve 263
Linear Components 265
Line to Line 265
Line to Ray 266
Line to Segment 267
Ray to Ray 268
Ray to Segment 270
Segment to Segment 272
Linear Component to Polyline or Polygon 273
Linear Component to Quadratic Curve 275
Linear Component to Polynomial Curve 277
GJK Algorithm 277
Set Operations 278
Overview of the Algorithm 279
Alternatives to GJK 282
7 Intersection in 2D 285
Linear Components 285
Linear Components and Polylines 290
Linear Components and Quadratic Curves 290
Linear Components and General Quadratic Curves 291
Linear Components and Circular Components 291
Linear Components and Polynomial Curves 292
Algebraic Method 292
Polyline Approximation 294
Hierarchical Bounding 295
Monotone Decomposition 296
Rasterization 297
Quadratic Curves 299
General Quadratic Curves 299
Circular Components 301
Ellipses 302
Polynomial Curves 306
Algebraic Method 306
Polyline Approximation 306
Hierarchical Bounding 307
Rasterization 307
The Method of Separating Axes 309
Separation by Projection onto a Line 309
Separation of Stationary Convex Polygons 310
Separation of Moving Convex Polygons 317
Intersection Set for Stationary Convex Polygons 320
Contact Set for Moving Convex Polygons 321
8 Miscellaneous 2D Problems 329
Circle through Three Points 329
Circle Tangent to Three Lines 329
Line Tangent to a Circle at a Given Point 331
Line Tangent to a Circle through a Given Point 332
Lines Tangent to Two Circles 335
Circle through Two Points with a Given Radius 341
Circle through a Point and Tangent to a Line with a Given Radius 342
Circles Tangent to Two Lines with a Given Radius 346
Circles through a Point and Tangent to a Circle with a Given Radius 349
Circles Tangent to a Line and a Circle with a Given Radius 353
Circles Tangent to Two Circles with a Given Radius 358
Line Perpendicular to a Given Line through a Given Point 360
Line between and Equidistant to Two Points 361
Line Parallel to a Given Line at a Given Distance 362
Line Parallel to a Given Line at a Given Vertical ( Horizontal) Distance 364
Lines Tangent to a Given Circle and Normal to a Given Line 366
9 Geometric Primitives in 3D 369
Linear Components 369
Planar Components 370
Planes 370
Coordinate System Relative to a Plane 374
2D Objects in a Plane 375
Polymeshes, Polyhedra, and Polytopes 377
Vertex-Edge-Face Tables 381
Connected Meshes 384
Manifold Meshes 386
Closed Meshes 386
Consistent Ordering 387
Platonic Solids 390
Quadric Surfaces 395
Three Nonzero Eigenvalues 395
Two Nonzero Eigenvalues 396
One Nonzero Eigenvalue 396
Torus 399
Polynomial Curves 400
Bezier Curves 401
B-Spline Curves 401
NURBS Curves 402
Polynomial Surfaces 403
Bezier Surfaces 404
B-Spline Surfaces 406
NURBS Surfaces 408
10 Distance in 3D 409
Introduction 409
Point to Linear Component 409
Point to Ray or Line Segment 411
Point to Polyline 413
Point to Planar Component 418
Point to Plane 418
Point to Triangle 420
Point to Rectangle 426
Point to Polygon 429
Point to Circle or Disk 432
Point to Polyhedron 435
General Problem 435
Point to Oriented Bounding Box 438
Point to Orthogonal Frustum 441
Point to Quadric Surface 445
Point to General Quadric Surface 445
Point to Ellipsoid 447
Point to Polynomial Curve 449
Point to Polynomial Surface 451
Linear Components 453
Lines and Lines 453
Segment/Segment, Line/Ray, Line/Segment, Ray/ Ray, Ray/ Segment 456
Segment to Segment, Alternative Approach 470
Linear Component to Triangle, Rectangle, Tetrahedron, Oriented Box 477
Linear Component to Triangle 477
Linear Component to Rectangle 485
Linear Component to Tetrahedron 491
Linear Component to Oriented Bounding Box 494
Line to Quadric Surface 509
Line to Polynomial Surface 511
GJK Algorithm 512
Miscellaneous 513
Distance between Line and Planar Curve 513
Distance between Line and Planar Solid Object 515
Distance between Planar Curves 516
Geodesic Distance on Surfaces 521
11 Intersection in 3D 525
Linear Components and Planar Components 525
Linear Components and Planes 526
Linear Components and Triangles 529
Linear Components and Polygons 532
Linear Component and Disk 535
Linear Components and Polyhedra 537
Linear Components and Quadric Surfaces 542
General Quadric Surfaces 543
Linear Components and a Sphere 545
Linear Components and an Ellipsoid 548
Linear Components and Cylinders 551
Linear Components and a Cone 556
Linear Components and Polynomial Surfaces 563
Algebraic Surfaces 564
Free-Form Surfaces 565
Planar Components 573
Two Planes 573
Three Planes 576
Triangle and Plane 578
Triangle and Triangle 583
Planar Components and Polyhedra 587
Trimeshes 587
General Polyhedra 588
Planar Components and Quadric Surfaces 591
Plane and General Quadric Surface 591
Plane and Sphere 592
Plane and Cylinder 595
Plane and Cone 607
Triangle and Cone 627
Planar Components and Polynomial Surfaces 631
Hermite Curves 633
Geometry Definitions 634
Computing the Curves 635
The Algorithm 636
Implementation Notes 639
Quadric Surfaces 639
General Intersection 640
Ellipsoids 648
Polynomial Surfaces 652
Subdivision Methods 652
Lattice Evaluation 653
Analytic Methods 654
Marching Methods 654
The Method of Separating Axes 655
Separation of Stationary Convex Polyhedra 655
Separation of Moving Convex Polyhedra 659
Intersection Set for Stationary Convex Polyhedra 660
Contact Set for Moving Convex Polyhedra 660
Miscellaneous 668
Oriented Bounding Box and Orthogonal Frustum 668
Linear Component and Axis-Aligned Bounding Box 670
Linear Component and Oriented Bounding Box 674
Plane and Axis-Aligned Bounding Box 678
Plane and Oriented Bounding Box 679
Axis-Aligned Bounding Boxes 681
Oriented Bounding Boxes 683
Sphere and Axis-Aligned Bounding Box 688
Cylinders 690
Linear Component and Torus 703
12 Miscellaneous 3D Problems 707
Projection of a Point onto a Plane 707
Projection of a Vector onto a Plane 709
Angle between a Line and a Plane 710
Angle between Two Planes 711
Plane Normal to a Line and through a Given Point 711
Plane through Three Points 713
Angle between Two Lines 714
13 Computational Geometry Topics 717
Binary Space-Partitioning Trees in 2D 717
BSP Tree Representation of a Polygon 718
Minimum Splits versus Balanced Trees 724
Point in Polygon Using BSP Trees 727
Partitioning a Line Segment by a BSP Tree 728
Binary Space-Partitioning Trees in 3D 731
BSP Tree Representation of a Polyhedron 732
Minimum Splits versus Balanced Trees 734
Point in Polyhedron Using BSP Trees 735
Partitioning a Line Segment by a BSP Tree 736
Partitioning a Convex Polygon by a BSP Tree 738
Point in Polygon 739
Point in Triangle 739
Point in Convex Polygon 741
Point in General Polygon 744
Faster Point in General Polygon 750
A Grid Method 751
Point in Polyhedron 752
Point in Tetrahedron 752
Point in Convex Polyhedron 753
Point in General Polyhedron 755
Boolean Operations on Polygons 758
The Abstract Operations 759
The Two Primitive Operations 761
Boolean Operations Using BSP Trees 763
Other Algorithms 768
Boolean Operations on Polyhedra 770
Abstract Operations 770
Boolean Operations Using BSP Trees 771
Convex Hulls 773
Convex Hulls in 2D 773
Convex Hulls in 3D 788
Convex Hulls in Higher Dimensions 794
Delaunay Triangulation 800
Incremental Construction in 2D 801
Incremental Construction in General Dimensions 805
Construction by Convex Hull 810
Polygon Partitioning 811
Visibility Graph of a Simple Polygon 811
Triangulation 815
Triangulation by Horizontal Decomposition 819
Convex Partitioning 833
Circumscribed and Inscribed Balls 842
Circumscribed Ball 843
Inscribed Ball 845
Minimum Bounds for Point Sets 847
Minimum-Area Rectangle 847
Minimum-Volume Box 850
Minimum-Area Circle 851
Minimum-Volume Sphere 855
Miscellaneous 857
Area and Volume Measurements 860
Area of a 2D Polygon 860
Area of a 3D Polygon 864
Volume of a Polyhedron 868
Appendix A Numerical Methods 871
Solving Linear Systems 871
A.1.1 Special Case: Solving a Triangular System 872
A.1.2 Gaussian Elimination 873
Systems of Polynomials 876
A.2.1 Linear Equations in One Formal Variable 877
A.2.2 Any-Degree Equations in One Formal Variable 879
A.2.3 Any-Degree Equations in Any Formal Variables 881
Matrix Decompositions 891
A.3.1 Euler Angle Factorization 891
A.3.2 QR Decomposition 896
A.3.3 Eigendecomposition 897
A.3.4 Polar Decomposition 898
A.3.5 Singular Value Decomposition 901
Representations of 3D Rotations 901
A.4.1 Matrix Representation 901
A.4.2 Axis-Angle Representation 902
A.4.3 Quaternion Representation 904
A.4.4 Performance Issues 905
Root Finding 913
A.5.1 Methods in One Dimension 913
A.5.2 Methods in Many Dimensions 918
A.5.3 Stable Solution to Quadratic Equations 919
Minimization 920
A.6.1 Methods in One Dimension 920
A.6.2 Methods in Many Dimensions 921
A.6.3 Minimizing a Quadratic Form 924
A.6.4 Minimizing a Restricted Quadratic Form 924
Least Squares Fitting 926
A.7.1 Linear Fitting of Points 926
A.7.2 Linear Fitting of Points Using Orthogonal Regression 926
A.7.3 Planar Fitting of Points 928
A.7.4 Hyperplanar Fitting of Points Using Orthogonal Regression 928
A.7.5 Fitting a Circle to 2D Points 930
A.7.6 Fitting a Sphere to 3D Points 931
A.7.7 Fitting a Quadratic Curve to 2D Points 932
A.7.8 Fitting a Quadric Surface to 3D Points 933
Subdivision of Curves 933
A.8.1 Subdivision by Uniform Sampling 933
A.8.2 Subdivision by Arc Length 934
A.8.3 Subdivision by Midpoint Distance 935
A.8.4 Subdivision by Variation 936
Topics from Calculus 938
A.9.1 Level Sets 938
A.9.2 Minima and Maxima of Functions 942
A.9.3 Lagrange Multipliers 954
Appendix B Trigonometry 967
Introduction 967
B.1.1 Terminology 967
B.1.2 Angles 967
B.1.3 Conversion Examples 969
Trigonometric Functions 970
B.2.1 Definitions in Terms of Exponentials 974
B.2.2 Domains and Ranges 975
B.2.3 Graphs of Trigonometric Functions 975
B.2.4 Derivatives of Trigonometric Functions 975
B.2.5 Integration 978
Trigonometric Identities and Laws 978
B.3.1 Periodicity 979
B.3.2 Laws 980
B.3.3 Formulas 984
Inverse Trigonometric Functions 989
B.4.1 Defining arcsin and arccos in Terms of arctan 989
B.4.2 Domains and Ranges 989
B.4.3 Graphs 990
B.4.4 Derivatives 990
B.4.5 Integration 992
Further Reading 992
Appendix C Basic Formulas for Geometric Primitives 993
Introduction 993
Triangles 993
C.2.1 Symbols 993
C.2.2 Definitions 994
C.2.3 Right Triangles 996
C.2.4 Equilateral Triangle 997
C.2.5 General Triangle 997
Quadrilaterals 998
C.3.1 Square 998
C.3.2 Rectangle 998
C.3.3 Parallelogram 998
C.3.4 Rhombus 999
C.3.5 Trapezoid 999
C.3.6 General Quadrilateral 999
Circles 1000
C.4.1 Symbols 1000
C.4.2 Full Circle 1000
C.4.3 Sector of a Circle 1000
C.4.4 Segment of a Circle 1001
Polyhedra 1001
C.5.1 Symbols 1001
C.5.2 Box 1001
C.5.3 Prism 1002
C.5.4 Pyramid 1002
Cylinder 1002
Cone 1003
Spheres 1003
C.8.1 Segments 1003
C.8.2 Sector 1004
Torus 1004
Index 1004
A 1017
B 1018
C 1020
D 1023
E 1025
F 1026
G 1027
H 1028
I 1028
J–K 1030
L 1031
M 1033
N 1035
O 1036
P 1037
Q 1043
R 1044
S 1045
T 1048
U 1050
V 1050
W 1051
X 1051
Y 1051
Z 1051
| Erscheint lt. Verlag | 10.10.2002 |
|---|---|
| Sprache | englisch |
| Themenwelt | Kunst / Musik / Theater ► Design / Innenarchitektur / Mode |
| Mathematik / Informatik ► Informatik ► Grafik / Design | |
| Mathematik / Informatik ► Informatik ► Software Entwicklung | |
| Informatik ► Weitere Themen ► CAD-Programme | |
| Mathematik / Informatik ► Mathematik ► Geometrie / Topologie | |
| Technik ► Bauwesen | |
| ISBN-10 | 0-08-047802-6 / 0080478026 |
| ISBN-13 | 978-0-08-047802-9 / 9780080478029 |
| Haben Sie eine Frage zum Produkt? |
PDF (Adobe DRM)Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
