Schneider P., Eberly D.H. Geometric Tools for Computer Graphics
Подождите немного. Документ загружается.
974 Index
affine transformations (continued)
matrix representation of,
126–128
notation, 133
reflection, 148–153
rotation, 136–142
scaling, 142–148
shearing, 153–158
translation, 134–136
vector geometry of, 132–158
algebraic surfaces, 520–521
component form equation, 521
defined, 520
angle between two lines, 670–672
in 3D, 671
in 3D with one line reversed, 671
defined, 670–671
lines normalized, 672
lines not normalized, 671–672
pseudocode, 671–672
angles, 923–925
acute, 927–928
cone, 213
dihedral, 346
direction of, 125
formulas, 942–943
interior, 767
between line and plane, 666–667
math notation, 15
negative, 923
orientation of, 125
positive, 923
standard position, 923
standard terminology, 924
threshold, 242
between two planes, 667
anticommutativity, 93
antisymmetry, 120
any-degree equations
in any formal variables, 837–846
in one formal variable, 835–837
arc length, 924
defined, 890, 925
reparameterization by, 890
arc length subdivision method,
890–891
defined, 890
pseudocode, 890–891
See also subdivision of curves
arcs
of circle spanned
counterclockwise, 249
intersecting, 258
intersection with linear
components, 248
area
2D polygon, 816–820
3D polygon, 820–823
as algebraic quantity, 817–819
as analytic quantity, 819–820
bounding box, minimum,
806–807
circle, 183
circle, minimum, 807–811
ellipse, 184
ellipse, minimum, 813–815
ellipsoid, minimum, 815–816
formula, 940
as geometric quantity, 819
of planar polygons, 823
by projection, 821–822
rectangle, 177
rectangle, minimum, 803–806
by Stokes’ Theorem, 822–823
triangle, 816, 950
arithmetic operations
matrices, 18–20
tuples, 16
associativity
addition, 20
associativity, 42
matrix multiplication, 23
scalar multiplication, 20, 23
vector addition, 68
augmented matrix
defined, 29, 828
form, 30
submatrices of, 834
See also matrices
axis-aligned bounding box
intersections, 637–639
defined, 637–638
illustrated, 639
with linear component, 626–630
with plane, 634–635
pseudocode, 638
with sphere, 644–646
axis-aligned bounding boxes
(AABB), 263, 527
defined, 626
memory usage, 862
in spatial subdivision problems,
626–627
See also bounding boxes
axis-aligned infinite strips, 194
axis-aligned rectangle, 373
axis-angle representation, 858–859
axis-angle to matrix, 858–859,
863
composition, 865–866
composition operation counts,
866
conversion time, 863, 864
defined, 858
interpolation, 868
matrix to axis-angle, 859, 863
transformation time, 864–865
See also representations of 3D
rotations
B
back substitution, 828, 829, 830
defined, 828
division step, 830
Gaussian elimination and, 829
balanced BSP trees, 680–683
for convex polygon, 681–683
for convex polyhedron, 690
partition, 682, 683
See also binary space-partitioning
(BSP) trees (2D)
balls
circumscribed, 799–801
inscribed, 799, 801–803
barycentric coordinates, 104–106
defined, 104
illustrated, 105
for ray/triangle intersection,
489
of triangles, 175, 176
Index 975
basis
change of, 75–76
defined, 71
Euclidean, 112
orthogonal, 98
orthonormal, 98
perpendicular, 98
usual, 112
basis vectors
Euclidean, 55
linear combination of, 72, 75
linear combination of different
sets of, 76
linear transformations and, 78
matrix representation, 128
OBB, 395
orthogonal set of, 55
rotating, 78
transformation, 49
transformed coordinates of, 138
Bernstein polynomials, 357
B
´
ezier curves
2D, 186
3D, 357
illustrated, 358
B
´
ezier rectangular patches, 360–362
defined, 360
illustrated, 361
B
´
ezier surfaces, 360–362
illustrated, 361
rational, 525
rectangular patches, 360–361
triangular patches, 361–362
types of, 360
See also surfaces
B
´
ezier triangular patches, 361–362
defined, 361
illustrated, 362
B
´
ezout determinant, 607, 844
B
´
ezout matrix, 606, 844
binary space-partitioning (BSP)
trees (2D), 246, 673–687
balanced, 680–683
Classify function and, 676–677,
686
minimum splits vs. balanced
trees, 680–683
partitioning line segment by,
684–687
partitioning of plane, 674
point in polygon using, 683–684
polygon partitioning with, 798
representation of polygons,
674–680
unbalanced, 680
binary space-partitioning (BSP)
trees (3D), 687–695
Classify function and, 689–690,
693
minimum splits vs. balanced
trees, 690
partitioning convex polygon by,
694–695
partitioning segment by,
692–694
point in polyhedron using, 691
polyhedron representation,
688–690
bisection method, 271–273, 870,
874
algorithm for extreme value, 272
defined, 271–272, 870
intersection testing pseudocode,
273
middle index, 272
root finding in many dimensions,
874
root finding in one dimension,
870
block matrix, 133
Boolean operations (on polygons),
714–726
abstract, 715–717
bounded polygons, 714
inside region, 714
other, 726
outside region, 714
polygon assumptions, 714
primitive, 717–719
unbounded polygons, 714
using BSP trees, 719–723
Boolean operations (on polyhedra),
726–729
abstract operations, 726
with BSP trees, 727–729
defined, 726
other, 729
boundary conditions, time-
varying, 478
boundary edges, 339
bounding boxes
adjacent, coalesced into single
box, 529
axis-aligned, 263, 527
hierarchy of, 527
leaf-node, 527, 528
minimum-area, 806–807
motivations for using, 526
in polynomial surface
intersections, 526–529
box formula, 957
Brent’s method, 876–877
bracketing points, 877
defined, 876
modification, 877
See also minimization
BSP tree Boolean operations (on
polygons), 719–723
intersection, 720–723
negation, 720
See also Boolean operations (on
polygons)
BSP tree Boolean operations (on
polyhedra), 727–729
intersection, 728–729
negation, 727–728
See also Boolean operations (on
polyhedra)
B-spline curves, 186–187
control points, 186
degree, 357
illustrated, 187, 359
knots, 186
nonuniform, 187, 358
uniform, 187, 358
See also curves
B-spline surfaces, 362–363
defined, 362
illustrated, 363
intersection, 609
nonuniform, 363
976 Index
B-spline surfaces (continued)
polynomial components, 363
uniform, 363
See also surfaces
C
canonical triangulation, 792–794
of convex polygons, 794
defined, 792
See also optimal partitioning;
triangulation
capsules, 646
Carmichael and Mason bound, 872
Cartesian frames, 97–98
Cayley-Menger determinant
equation, 800, 801
chapters summary, this book, 6–7
characteristic polynomials, 53, 853
Chebyshev boxing, 526
circle through point and tangent to
line, 298–302
circles mirrored across line, 300
configurations, 298
defined, 298
equations, 299–300
illustrated, 299
insight, 298
pseudocode, 301–302
two distinct circles, 299
circle through two points (given
radius), 297–298
defined, 297
illustrated, 297
insight for computing, 297–298
possible, 297
pseudocode, 298
circles, 171
in 3D, 556
area for, 183
“auxiliary,” 308
bounding, 807
circumscribed, 798–799
closest point to, 389, 390
defined, 183
fitting, to 2D points, 886–887
formulas, 956–957
growing, 808
inscribed, 285, 798–799
intersecting, 257–258
intersection with linear
components, 247–248
line tangent at given point,
287–288
line tangent through given point,
288–291
minimum-area, 807–811
in parametric form, 183, 184
parametric representation in 3D,
332
in plane/cone intersection, 565,
575–576
in plane/cylinder intersection,
552, 561
point to, 388–389
quadratic equation, 183
quadratic form, 183
sector of, 956
segment of, 957
squared distance between, 477
tangent to three lines, 285–286
through three points, 285, 286
two, lines tangent to, 291–296
See also spheres
circles tangent to line and circle,
309–313
circle position, 310
defined, 309
equations, 312
insight, 309–310
insight for circle of given radius,
311
line position, 310
pseudocode, 312–313
radius, 310
radius too small, 311
solution schematic, 312
solutions, 310
circles tangent to two circles,
314–316
circle radius and, 314
construction for, 316
defined, 314
equations, 314
illustrated, 314
no solutions, 315
one solution, 315
pseudocode, 315–316
two solutions, 315
circles tangent to two lines, 302–305
circles, 303
constructive approach, 304
defined, 302
illustrated, 303
line definition, 303
pseudocode, 304–305
radius, 302
circles through point and tangent
to circle, 305–309
analytical approach, 305
constructive approach, 308
defined, 305
equations, 306–307
illustrated, 305
insight for solving problem, 307
pseudocode, 307–308
solutions, 306
special case for constructive
approach, 309
circular components
intersecting, 257–258
intersection with linear
components, 247–248
intersection with lines, 248
intersection with rays, 248
circular curve intersection, 576
circumhyperspheres
defined, 762
point determination, 763
union of, 764
See also Delaunay triangulation
circumscribed balls, 799–801
construction, 799
defined, 799
dimension 2, 800
dimension 3, 800–801
for simplex, 799
See also inscribed balls
circumscribed circles, 798–799
defined, 799
illustrated, 799
Index 977
circumscribed spheres, 799
Classify function, 676–677, 686,
689–690, 693
closed meshes
defined, 342
normals, 344
See also meshes
closed polylines, 178, 229
cocircular points, 5
co-domain, 45
coefficient matrix, 29, 828
cofactors, 36
coincident edges
defined, 675
opposite direction normals,
676
polygon, 700
storage, 675
See also edges
collinear points, 5
collinear vertices, 767
collinearity test, 733–735
defined, 733
possibilities, 734
possibilities illustration, 734
pseudocode, 735, 736
CollinearTest function, 735, 736,
738, 744
commutative ring, 41
commutativity
addition, 20, 42
dotproduct,90
matrix multiplication, 22
vector addition, 68
companion matrix, 871–872
component jumping, 611
components
connected, 340
defined, 63, 72
normal, 88
parallel, 147
perpendicular, 147
composition
of functions, 47
of mappings, 46
matrix representation of, 50
concave polygons, 179
cone intersections, 512–519
with linear components,
512–519
with plane, 563–582
with triangle, 583–587
See also intersections (3D)
cones
acute, 514, 515
angle of, 213
axis of, 213
double, 514, 515, 516, 583
elliptic, 352
finite, 563, 566–569
formula, 959
frustum, 213, 214
infinite, 563, 564–566
inside of, 583
intersection with line, 515–519
orthogonal frustum, 213–216
outside, 584
parameterized standard
representation, 513–519
single, 213
vertex of, 213, 513
visibility, 745
conjugate gradient search, 878–879
connected components, 340
connected meshes, 340–342
defined, 340
manifold, 344
pseudocode, 340–341
variation pseudocode, 341–342
See also meshes
consistent orderings, 343–345
choosing, 344
defined, 342
face normals, 343
illustrated, 343
manifold meshes, 343
pseudocode, 345
Constrained-Extremum Principle
Three-Variable Form with Two
Constraints, 920
Two-Variable Form, 913–914
contact
edge-to-edge, 267, 282, 283
set, 277–284
vertex-edge, 267, 283
vertex-vertex, 267, 283
contact set
moving convex polygons,
277–284
moving convex polyhedra,
616–624
See also method of separating
axes (2D); method of
separating axes (3D)
contours
adjacent, relative distance
between, 894
defined, 894
maps, 894–895
control points, 186
B
´
ezier, 525
defined, 357
NURBS curves, 358
three-dimensional, 362
convex combination, 84
convex faces
generating minimum number of,
789–790
illustrated, 334
See also faces
convex hulls (2D), 729–744
algorithms, 730
defined, 729
with divide-and conquer, 730,
739–744
with incremental construction,
730, 731–738
input indices, 741, 743
point set and, 730
tangents, 731
convex hulls (3D), 744–750
becoming convex polyhedron,
745
defined, 729
Delaunay triangulation
construction by, 766–767
divide-and-conquer method,
748–750
face mesh, 746
incremental construction,
745–748
978 Index
convex hulls (3D) (continued)
linear, 747
planar, 747
convex hulls (higher dimensions),
750–755
asymptotic behavior, 750
complexity, 750
divide-and-conquer method,
755
incremental construction,
751–755
convex partitioning, 789–798
with BSP trees, 798
minimum number of diagonals
in, 791
miscellaneous, 798
optimal, 791–798
suboptimal but fast, 790–791
uses, 789
convex polygons, 179, 266–284
balanced BSP trees, 681–683
bisection splitting for, 681
BSP tree construction, 679
containing, locating, 710
decomposition into triangular
fan, 334
edge-to-edge contact, 267, 282,
283
intersecting, 267
matrix, 768
moving, contact set for, 277–284
moving, separation of, 273–276
nonintersecting, 267
partitioning by 3D BSP tree,
694–695
point in, 697–700
point to, 216–217
reflex vertex of, 792
stationary, intersection set for,
276–277
stationary, separation of,
266–273
vertex-edge contact, 267, 283
vertex-vertex contact, 267,
283
vertices, 265
See also faces; polygons
convex polyhedra
finding extreme points on, 613
intersection testing, 611–612
moving, 615–624
point in, 709–711
point to, 393
stationary, 611–615, 616
See also polyhedra
convex vertices
cone containment, 770
defined, 767
Coordinate Axiom, 80
defined, 110
invoking, 111
coordinate system, 330
coordinate-based methods, 9–10
coordinate-free API, 109
coordinate-free geometry, 12
coordinates
affine, 105
of affine point relative to frame,
98
barycentric, 104–106
change of, 11
defined, 72, 97
frame, 104
transforming, 10
coplanar points, 5
cosecant function
for commonly used angles, 929
defined, 927
domain and range, 931
graph, 932
period, 935
See also trigonometric functions
cosine function
for commonly used angles, 929
defined, 926
domain and range, 931
graph, 932
period, 935
See also trigonometric functions
cotangent function
for commonly used angles, 929
defined, 927
domain and range, 931
graph, 932
period, 936
See also trigonometric functions
Cox-de Boor recursion formulas,
187
Cramer’s rule, 50–52, 534
general form, 52
instability, 52
larger systems and, 52
solution, 57
critical points, 899, 900
defined, 899, 908
finding, 905
illustrated, 900
second partials at, 910
cross product, 117–120
3D, 242
antisymmetry, 120
defined, 15, 92, 117, 119
direct computation, 117–119
of edge pairs, 613
formula proof, 119
of gradient vectors, 607
length, 93, 118
as matrix multiplication,
119–120
nonzero vector, 377
normals as, 167
orientation, 118
orthogonality, 118
of polygon normals, 614
properties, 117–118
separation tests, 617
oftwovectors,93
See also products; vector product
cross-ratio, 163–164
defined, 163
illustrated, 164
preservation of, 163–164
See also perspective projection
curve tracing, 610
curves
B
´
ezier, 186
B-spline, 186–187
critical points, 598
geodesic, 477–479
Hermite, 589–590
level, 199, 200, 226, 379
Index 979
nonplanar space, 595, 601
NURBS, 188, 358–359
planar, 469–471, 472–477
polynomial, 185–188, 356–359
quadratic, 181–185
in quadric surfaces intersection,
595
subdivision of, 889–894
cylinder intersections, 646–659
cylinder projection onto line,
647
cylinder projection onto plane,
648
cylinder representation, 646–647
defined, 646
with linear components,
507–512
with plane, 551–563
separating line tests, 648–650
tests at perpendicular vectors,
651–652
tests for directions, 652–654
See also intersections (3D)
cylinders
analysis of F (x, y), 654–655
axis, 559
axis directions, 648, 649
centerpoint, 646
elliptic, 352, 354
end disks, 646, 647
end points, 655
fast method to test F(x, y)0,
658–659
finite, 551, 553–555
formula, 958
general representation, 508
heights, 648
hyperbolic, 352, 354
infinite, 551, 553, 555–562
parabolic, 353, 355
parameterized standard
representation, 508, 509–512
pure standard representation,
508
radius, 560, 648
representation of, 646–647
solving for (x, y), 657–658
surface points, 646–647
trigonometric representation,
597
See also cylinder intersections
D
Dandelin’s construction, 556–557,
570
de Casteljau algorithm, 523
decomposition(s)
eigendecomposition, 853–854
equivalent classes of, 792
horizontal, 775–789
matrix, 847–857
minimum convex (MCD),
793–794, 796
polar, 854–856
QR, 852–853
singular value, 857
degenerate plane/cone
intersections, 570, 581–582
configuration illustrations, 581
configurations resulting in, 571
line, 565, 581
point, 565, 581
two lines, 565, 582
See also plane/cone intersection
Delaunay triangulation, 5, 756–767
3D, 764
constructing, 756
construction by convex hull,
766–767
defined, 756
incremental construction (2D),
757–761
incremental construction
(general dimensions),
761–766
triangle property, 756
See also triangulation
delete algorithm, 750
determinant expansion by minors,
36
determinants, 34–37
B
´
ezout, 607, 844
general solution, 36–37
of identity matrix, 37
of inverse of matrix, 37
math notation, 15
of matrix of coefficients, 53
minor, 36
of product of two matrices, 37
properties, 37
of scalar multiple of matrix, 37
as signed volume, 96
special solutions, 35–36
of square matrices, 34–37
terminology, 35
of triangular matrix, 37
diagonal matrices, 32–34
defined, 32
identity, 33–34
illustrated, 32
inverse, 218, 402
properties, 33
scalar, 33
See also matrices; square matrices
diagonals
defined, 767
as edges of triangles, 790
essential, 791
inessential, removing, 790
minimum number in convex
partitioning, 791
testing for, 769–770
See also segments
difference
Boolean operation on polygons
(abstract), 717, 718
Boolean operation on polygons
(primitive), 719
Boolean operation on polyhedra
(abstract), 726
dihedral angle, 346
dimension
affine space, 80
linear space, 45
vector space, 71
DisjointUnion operation, 724
disk intersection, 491–493
with line, 492–493
with linear component, 491–493
with ray, 493
980 Index
disk intersection (continued)
with segment, 493
disks
closest point (projection inside
disk), 390
closest point (projection outside
disk), 391
defined, 171, 389, 492
point to, 389–391
distance
between convex polyhedra, 1
geodesic, 469, 477–479
minimum, 194, 220, 226, 230,
234
positive, 221, 222, 223, 224
squared, 190, 191, 193, 194, 219
squared, between objects, 1
zero, 221, 222, 223, 224
distance algorithms (2D), 189–239
line to line, 221–222
line to planar curve, 469–471
line to ray, 222–223
line to segment, 223–224
linear component to polygon,
229–230
linear component to polyline,
229–230
linear component to polynomial
curve, 233
linear component to quadratic
curve, 231–233
point to convex polygon,
216–217
point to line, 190–191
point to orthogonal frustum,
213–216
point to polygon, 196–217
point to polyline, 194–196
point to polynomial curve,
219–221
point to quadratic curve,
217–219
point to ray, 191–192
point to rectangle, 211–213
point to segment, 192–193
point to triangle, 196–211
ray to line, 226
ray to ray, 224–226
segment to segment, 228–229
distance algorithms (3D), 365–479
geodesic distance on surfaces,
477–479
introduction to, 365
line to planar curve, 469–471
line to planar solid object,
471–472
line to polynomial surface,
467–468
line to quadric surface, 465–467
line to ray, 418–420
line to rectangle, 442–446
line to segment, 420–422
line to triangle, 434, 437–441
linear component to ORB,
450–453
linear component to rectangle,
441–446
linear component to tetrahedron,
447–465
linear component to triangle,
433–441
lines to lines, 409–412
planar curves, 472–477
point to circle, 388–389
point to convex polyhedron, 393
point to disk, 389–391
point to ellipsoid, 403–405
point to general polyhedron, 393
point to linear components,
365–3674
point to oriented bounding box,
394–397
point to orthogonal frustum,
397–401
point to planar components,
374–391
point to plane, 374–376
point to polygon, 385–388
point to polyhedron, 391–401
point to polyline, 369–374
point to polynomial curve,
405–407
point to polynomial surface,
407–409
point to quadric surface,
401–405
point to ray, 367–369
point to rectangle, 382–384
point to segment, 367–369
point to tetrahedron, 391–393
point to triangle, 376–382
ray to ORB, 464
ray to ray, 422–424
ray to rectangle, 446
ray to segment, 424–426
ray to triangle, 441
segment to ORB, 465
segment to rectangle, 446
segment to segment, 415–418
segment to triangle, 441
distributivity
addition, 42
dot product over vector addition,
90
matrix multiplication, 23
multiplication, 42
vector addition over dot product,
91
vector addition over
multiplication, 69
vector multiplication over
addition, 69
vector product, 93
Divergence Theorem, 825
divide-and-conquer method (2D),
730, 739–744
defined, 739
GetHull function, 739–740
linear-time merge, 739
Merge function, 741–743
pseudocode, 739
recursive construction, 739
walking algorithm, 740
See also convex hulls (2D)
divide-and-conquer method (3D),
748–750
defined, 748
delete algorithm, 750
discarded faces, 749
hidden/visible face detachment,
749
Index 981
merged hull, 749
plane wrapping and, 748
supporting sets and, 748
See also convex hulls (3D)
divide-and-conquer method
(higher dimensions), 755
division
by scalars, 19
of tuples, 16
dodecahedron, 349–350
face connectivity, 349
illustrated, 346
relationships, 347
triangle connectivity, 350
vertices, 349
See also platonic solids
domain(s)
of functions, 45, 77
for linear component distance
calculations, 413
for linear component to triangle
distance calculation, 436
triangles, 175, 176
visible boundaries, definition of,
414
dot product, 20, 54–55, 89,
116–117, 288
bilinearity, 90
commutativity, 90
computing, 117
as coordinate-free operation,
116–117
defined, 116
distributivity of vector addition
over, 91
distributivity over vector
addition, 90
math notation, 15
negative value, 393
perp, 121, 123–126
positive definiteness, 90
projection, 137, 138
See also products
double cones, 514, 515, 516,
583
double-angle formulas, 942
E
ear clipping, 772–775
algorithm modification, 773–775
defined, 772–773
pseudocode, 773
triangle failure, 786
See also triangulation
echelon form, 32
edges
boundary, 339
“closest,” 459
coincident, 675, 676, 700
counting, 701
defined, 333
direction vectors, 624
interior, 339
junction, 339
keyhole, 722–723
list, 338, 339
manifold, 339
OBB intersection directions, 639
parallel, 344
platonic solids, 346
polygon, 265, 697, 700
rectangle, 344
representation, 337
sharing vertices, 338
splitting, 693
triangle, 771
Voronoi regions for, 397
edge-to-edge contact, 267, 282, 283
edge-to-interior search, 205–211
conditional test, 208
defined, 205
operation counts, 211
pseudocode, 209–210
test-point distance calculation,
207–208
time analysis, 211
See also point to triangle
eigendecomposition, 402, 853–854
eigensystems, 853–854
defined, 853
solving, 853–854
eigenvalues, 52–54
defined, 52
negative, 352
one nonzero, 352–355
positive, 352
three nonzero, 351–352
two nonzero, 352
eigenvectors, 54, 854, 881
elementary row operations, 31
elimination
defined, 28
Gaussian, 30
ellipse equation, 255
ellipses, 183–185
in 3D, 556
area for, 184
axis-aligned, 261
defined, 183, 185
factored form, 183
intersecting, 258–262
intersection illustration, 262
intersection with parabola, 256
minimum-area, 813–815
minor radius, 579
parametric form, 183
in plane/cone intersection, 565,
576–577
in plane/cylinder intersection,
552
quadratic form, 184
sphere and cone distance, 579
ellipsoids, 352, 604–608
centerpoint, 504
closest point on, 403
equation, 507
finding intersections, 605–608
illustrated, 353
inside definition, 604
intersection with linear
components, 504–507
intersections of, 604–608
minimum-area, 815–816
point to, 403–405
points on, 605
possible closest points, 404
quadratic equations, 605–606
scaling factors, 506
testing for intersections, 605
elliptic cones
defined, 352
982 Index
elliptic cones (continued)
illustrated, 353
See also cones
elliptic cylinders
defined, 352
illustrated, 354
See also cylinders
elliptic paraboloids
defined, 352
illustrated, 354
Euclidean basis, 112
Euclidean geometry, 84–94
Euclidean space, 54–56
defined, 86
inner product, 54–55
sets of basis vectors, 55
Euler angle factorization, 847–852
exclusive-or
Boolean operation on polygons
(abstract), 717, 719
Boolean operation on polygons
(primitive), 719
Boolean operation on polyhedra
(abstract), 726
exponential formulas, 943–944
Extreme Value Theorem, 899, 903
defined, 899
functions violating assumptions
of, 899
Relative, 903
Two-Variable Form, 912
F
face connectivity
dodecahedron, 349
hexahedron, 348
See also platonic solids
faces
“back,” 495
consistent orderings, 342, 345
convex, 334, 789–790
defined, 333
discarded, 749
edges shared by, 337
fanned into triangles, 334
hidden, 749
hyperfaces, 754, 755
list, 338, 339
manifold meshes, 342
nonconvex, 334, 335
OBB intersection orientations,
639
on splitting plane, 689
orthogonal frustum, 624
platonic solids, 346
“positive,” 459, 460
reordered, 344
representation, 337
splitting, 693
visible, 749
Voronoi regions for, 397
factorization
Euler angle, 847–852
pseudocode, 849
of rotation matrices, 848–852
fields, 41–42
defined, 41
examples, 41
properties, 41
FindIntersection function,
281
implementation, 621
pseudocode, 621–622
find-intersections query, 611
defined, 265
for stationary convex polyhedra,
616
See also method of separating
axes
FindPolygonIntersection function,
284
finite cones, 563
intersection detection, 566–569
intersections, 565
See also cones; plane/cone
intersection
finite cylinders, 551
intersection detection, 553
intersection illustrations, 552
See also cylinders; plane/cylinder
intersection
First Derivative Test, 903
fitting. See least squares fitting
floating-point
addition, order for, 3
imprecision, 385
issues, 3
representation, 2
round-off errors, 677, 736
for loop, 714
formulas, 940–944
addition and subtraction,
940–941
area, 940
double-angle, 942
exponential, 943
general exponential, 944
general multiple-angle, 943
geometric primitives, 949–960
half-angle, 944
Mollweide’s, 940
Newton’s, 940
product, 941
quadruple-angle, 942
rotation, 141
triple-angle, 942
frames, 96–98
Cartesian, 97–98
coordinates, 104
coordinates of affine point
relative to, 98
defined, 96, 105
notation, 96–97
rotation, 137
scaling, 143
translation of, 136
free-form surfaces, 521–529
defined, 521
subdividing, 522
frustum
constraints, 213
coordinate system, 214–215
defined, 213
in first quadrant, 215
illustrated, 214
orthogonal, 213–216
See also cones
functions
absolute maximum value of, 898
absolute minimum value of, 899
Index 983
Classify, 676–677, 686,
689–690, 693
CollinearTest, 735, 736, 738,
744
composition of, 47
defined, 45
domain of, 45, 77
FindIntersection, 281,
621–622
FindPolygonIntersection, 284
GetHull, 739–740
GetLineFromEdge, 676
GetPartition, 722
GetPlaneFromFace, 689
graph of, 77
IntersectCurve, 594
Merge, 741–743, 755
MergeLinear, 733, 743, 747
MergePlanar, 737–738
MergeSpatial, 747–748
minima and maxima of, 898–922
MinimizeOn, 878
for more than one variable,
905–910
NoIntersect, 279, 616, 620
for one variable, 898–905
one-to-one, 48
onto, 48
ProjectGeneral, 617
ProjectNormal, 617
range of, 45, 77
ReformatAndInsert, 752, 753
schematic diagram, 46
SegmentIntersect, 771
sine, 77
SplitPolygon, 690
Supertriangle, 760
TestIntersection, 277,
280–281, 613, 617, 620–621
Update, 753, 754, 810
G
Gaussian elimination, 30, 534,
829–832
back-substitution division step,
830
back-substitution basis, 829
pseudocode, 832
Gauss’s reduction method, 600
general cylinder representation
defined, 508
illustrated, 509
See also cylinders
general linear systems, 29–30
general multiple-angle formulas,
943
general polyhedron, point in,
711–714
general quadratic curves
intersecting, 255–257
intersection with linear
components, 247
See also quadratic curves
general quadric surfaces
defined, 547
implicit form of equation, 499
intersections, 499–501
matrix notation, 499
plane intersection with, 547
point to, 401–402
pseudocode, 500–501
See also quadric surfaces
general reflection, 150–153
3D, 152
defined, 150–151
matrix, 152
See also reflection
general rotation, 139–142
coordinate-free vector algebra,
139
defined, 139
illustrated, 140
matrix, 139
in perpendicular plane, 141
symbols, 139–140
See also rotation
general scaling, 144–148
defined, 144
nonuniform, 146–148
uniform, 145–146
See also scaling
general shearing, 157–158
2D y-shear matrix, 158
3D shear matrix, 157–158
defined, 157
illustrated, 157
transform matrix, 157
See also shearing
geodesic curve, 477–479
construction of, 477–479
defined, 477
geodesic distance
approximation, 479
defined, 469, 477
on surfaces, 477–479
geodesic paths, 469
geometric algebra, 12
geometric algorithms, 2
geometric primitive formulas,
949–960
box, 957
circles, 956–957
cone, 959
cylinder, 958
equilateral triangle, 953
general quadrilateral, 955
general triangle, 953
parallelogram, 954
polyhedra, 957–958
prism, 958
pyramid, 958
quadrilaterals, 954–955
rectangle, 954
rhombus, 955
right triangle, 952
spheres, 959–960
square, 954
torus, 960
trapezoid, 955
triangles, 949–953
geometric primitives (2D), 171–188
linear components, 171–174
polygons, 179–181
polylines, 177–178
rectangles, 177
triangles, 175–177
geometric primitives (3D), 325–364
linear components, 325–326
planar components, 326–333
GetHull function, 739–740