Schneider P., Eberly D.H. Geometric Tools for Computer Graphics
Подождите немного. Документ загружается.
994 Index
parallelism (continued)
vector product, 93–94
parallelograms
area, 154
formula, 954
parameter plane
defined, 98
partitioning, 199
See also interior-to-edge search
parameterization surface, 597
parameterized standard cylinder
representation, 509–512
defined, 508
See also cylinders
parametric form, 173–174
of circles, 183, 184
converting, to implicit form, 174
converting, to normal-point
form, 328
converting implicit form to, 174
converting normal-point form
to, 328–329
defined, 173
deriving from normal form, 326
of ellipses, 183, 184
of line, 173
planes, 328
of rectangles, 177
of triangles, 175, 176
parametric surfaces
free-form, 521
intersection with plane, 587
point to, 407
See also surfaces
paths, geodesic, 469
periodicity, 935–936
perp dot product, 121, 123–126
defined, 123
geometric interpretation,
123–124
illustrated, 124
properties, 126
signed area of triangle and, 125
See also dot product
perp operator, 121–123
defined, 121
illustrated, 122
linearity, 122
properties, 122–123
perpendicular vectors, 15
perspective projection, 163–165
cross-ratio, 163–164
defined, 159
perspective point, 163
for points, 164–165
transformation matrix, 165
of vectors, 164
See also projections
planar component intersections,
529–542
with polyhedra, 543–546
with polynomial surfaces,
587–595
two planes, 529–531
See also intersections (3D)
planar component/polynomial
surface intersection, 587–595
3-space intersection curve, 592
algorithm, 592–595
curve computation, 591–592
defined, 587–588
as general surface-surface
intersection problem, 588
geometry definitions, 590–591
Hermite curves and, 589–590
illustrated, 587
implementation notes, 595
parametric space intersection
curve, 593
pseudocode, 592–594
transformation application, 588
planar components, 326–333
2D objects, 331–333
coordinate system, 330
defined, 326
intersection with linear
components, 481–493
planes, 326–330
point to, 374–391
See also geometric primitives
(3D)
planar curves distance, 472–477
algebraic representation,
473–477
defined, 472
example, 474–477
line and, 469–471
minimum squared, 477
parametric representation,
472–473
planar fitting, 884
planar merge, 737–738,
752
plane and OBB intersection,
635–637
defined, 635
illustrated, 637
OBB definition, 635
OBB diagonals projection, 636,
638
problem illustration, 636
See also intersections (3D)
plane equation
coefficients, geometric
interpretation of, 328
implicit form, 327
normalized, 328
normal-point form of, 327
polygon, 488
plane intersections
with axis-aligned bounding box,
634–635
with B
´
ezier patch, 525
with cone, 563–582
with cylinder, 551–563
with line, 483–484
with linear components,
482–485
with OBB, 635–637
with parametric surface, 587
with polygon, 545
with quadric surface, 547–548
with ray, 484
with segment, 484–485
with sphere, 548–551
three planes, 532–534
with triangle, 534–539
with trimesh, 543–544
two planes, 529–531
See also intersections (3D)
Index 995
plane normal to line and through
point, 667–669
computational notation, 668
defined, 667–668
distance coefficient computation,
669
illustrated, 668
plane through three points,
669–670
defined, 669
explicit form, 670
illustrated, 670
implicit equation, 669
parametric equation, 669
plane/AABB intersection, 634–635
AABB definition, 634
defined, 634
illustrated, 636
optimizations, 634
plane definition, 634
pseudocode, 635
plane/cone intersection, 563–582
circle, 565, 575–576
defined, 563
degenerate, 570, 581–582
detection, 564–569
edge-on view, 568
ellipse, 565, 576–577
finite cone, 563
hyperbola, 565, 577–581
illustrated, 564
infinite cone, 563
line, 565, 581
nondegenerate, 570–581
parabola, 565, 572–575
in parabolic curve, 570, 572
point, 565, 581
segment, 565
two lines, 565, 582
plane/cylinder intersection,
551–563
circle, 552, 561
cross section, 558
detection, 552–555
edge-on-view of, 554
ellipse, 552
elliptical arc/segment, 552
with finite cylinder, 551–552,
553–555
illustrated, 551
with infinite cylinder, 551, 553,
555–562
line, 552
point, 552
pseudocode, 562–563
quadrilateral, 552
plane/sphere intersection, 548–551
cross-sectional view, 550
defined, 548–549
illustrated, 548
pseudocode, 550–551
planes, 326–333
2D objects in, 331–333
angle between line and, 666–667
angle between two, 667
BSP tree partitioning of, 674
coordinate system relative to, 330
cylinder projection onto, 648
defined, 326
edge-on view, 375
illustrated, 327
intersecting, 354, 529–534
negative side of, 687
normal to line and through
point, 667–669
normal-constant form, 327
normal-point form, 327
parallel, 355
parametric form, 328
parametric representation
illustration, 329
partition by rectangle, 383
partitioning of, 687–688
point construction on, 327
point to, 374–376
positive side of, 687
projection of points onto,
663–664
projection of vectors onto,
665–666
ray representation as intersection
of, 524
st-plane, 378, 427
through three points, 669–670
union of two, 352
xy-plane, 331, 333
See also plane intersections
platonic solids, 346–351
defined, 346
dodecahedron, 346, 349–350
edges, 346
faces, 346
hexahedron, 346, 348
icosahedron, 346, 350–351
illustrated, 346
octahedron, 346, 348–349
relationships, 347
tetrahedron, 346, 347
vertices, 346
plus tag, 703, 705
point distance algorithms
point to circle, 388–389
point to convex polygon,
216–217
point to convex polyhedron, 393
point to disk, 389–391
point to ellipsoid, 403–405
point to general polyhedron,
393
point to line (2D), 190–191
point to line (3D), 366–367
point to linear components,
365–373
point to oriented bounding box,
394–397
point to orthogonal frustum
(2D), 213–216
point to orthogonal frustum
(3D), 397–401
point to planar component,
374–391
point to plane, 374–376
point to polygon (2D), 196–217
point to polygon (3D), 385–388
point to polyhedron, 391–401
point to polyline (2D), 194–196
point to polyline (3D), 369–373
point to polynomial curve,
219–221, 405–407
point to polynomial surface,
407–409
996 Index
point distance algorithms (contin-
ued)
point to quadratic curve,
217–219
point to quadric surface,
401–405
point to ray (2D), 191–192
point to ray (3D), 367–369
point to rectangle (2D), 211–213
point to rectangle (3D), 382–384
point to segment (2D), 192–193
point to segment (3D), 367–369
point to tetrahedron, 391–393
point to triangle (2D), 196–211
point to triangle (3D), 376–382
See also distance algorithms
(2D); distance algorithms
(3D)
point in convex polygon, 697–700
algorithm, 697–698
asymptotically faster method 1,
698–699
asymptotically faster method 2,
699–700
bisection implementation, 698
bottom half of polygon, 699
polygon edges, 697
polygon vertices, 699
sidedness tests, 697
test determining two edges
intersected by vertical line, 700
top half of polygon, 699
point in convex polyhedron,
709–711
algorithm, 709
asymptotically faster method,
709–711
defined, 709
planar meshes, 710
preprocessing, 710
point in general polygon, 700–706
defined, 700
faster, 706–707
test illustration, 701
point in general polyhedron,
711–714
configurations, 711–712
defined, 711
pseudocode, 713
point in polygon, 695–708
convex polygon, 697–700
defined, 695
general polygon, 700–706
general polygon (faster),
706–707
grid method, 707–708
sublinear tests, 706
test by counting intersections,
701
triangle, 695–697
point in polyhedron, 708–714
convex polyhedron, 709–711
general polyhedron, 711–714
tetrahedron, 708–709
point in tetrahedron, 708–709
barycentric coordinates, 708
defined, 708
point in triangle, 695–697
clockwise-ordered vertices,
696
collinear vertices, 696–697
counterclockwise-ordered
vertices, 695–696
needlelike triangle, 697
noncollinear vertices, 695
sidedness tests, 697
point subtraction
definition of, 81
matrix representation, 115
point tags, 705
point-to-triangle distance, 196–211
closest point illustration, 197
edge-to-interior search for
closest point, 205–211
edge-to-interior search time
analysis, 211
interior-to-edge search for
closest point, 198
interior-to-edge search time
analysis, 205
See also point distance
point-in-circle tests, 810
point-in-polygon problem, 490
point-in-polytope query, 344
points, 80
2D, fitting circle to, 886–887
2D, fitting quadratic curve to,
888–889
2D, transforming, 10
3D, fitting quadric surface to,
889
3D, fitting sphere to, 887–888
adding, 10
affine combination of, 83, 85
affinely independent, 106
circle through, 285, 286
classifying, 703
cocircular, 5
collinear, 5
construction on plane, 327
coordinates, transforming, 10
coplanar, 5
critical, 899, 900
cylinder surface, 646–647
defining plane, 670
end, 367, 379
equation representation, 13
hyperplanar fitting of, 884–885
inflection, 900
intersection, 5
line equidistant to, 317–318
linear fitting of, 882–884
math notation, 15
matrix representation of,
110–113
multiplicative operations on, 80
noncoincident, 385
noncollinear, 385
on acute cone, 515
perspective projection for,
164–165
planar fitting of, 884
in plane/cone intersection, 565
in plane/cylinder intersection,
552
in polygon using BSP trees,
683–684
in polyhedron using BSP trees,
691
projection, 163
projection onto plane, 663–664
Index 997
in quadric surfaces intersection,
595
rotation of, 140, 141–142
saddle, 908, 909
scaling, 142, 145, 146
stationary, 899
tangent to lines, 285–286
two, circle through, 297–298
uniform scaling about, 144
vector addition with, 114–115
vector subtraction with, 114–115
polar decomposition, 854–856
defined, 855
possibility of, 855–856
See also matrix decompositions
polygon intersections, 488–491
with line, 488–491
with plane, 545
plane of, 488
with ray, 489, 491
with segment, 491
with triangle, 545–546
polygon partitioning, 767–798
with additional interior point,
790
with BSP trees, 798
convex, 789–798
keyconcept,767
with only vertices, 790
triangulation, 771–775
triangulation by horizontal
decomposition, 775–789
visibility graph, 767–771
polygonal chains, 179–181
defined, 179
monotonic, 179–180
strictly monotonic, 179
polygons
in 2D, 179–181
Boolean operations on, 714–726
bottom half of, 699
bounded, 714
concave, 179
convex, 179, 266–284, 697–700
defined, 179
difference of, 717, 719
edges, 265, 697, 700
exclusive-or of, 717, 719
insertion, 765
intersection of, 715, 718,
720–723
inverted L-shaped, 677
keyhole, 723
linear component to, 229–230
monotone, 180–181, 783–789
negation of, 715, 718, 720
nonsimple, 180
overlapping, 281, 284
planar, 823
plane equation for, 488
plane of, 385
point to (2D), 196–217
point to (3D), 385–388
polysolids, 179, 180
regular, 346
simple, 179
spherical, 713
top half of, 699
triangulation of, 771–775
unbounded, 714
union of, 715, 718
vertices, 179
visibility graph, 767–771
See also polygon intersections;
polygon partitioning
polygons (BSP tree representation),
674–680
after processing edge (0, 1), 679
after processing edge (1, 2), 679
after processing edge (5, 6), 680
after processing edge (9, 0), 678
after processing edge (10, 5), 680
after processing edge (13, 9), 681
coincident edges, 675, 676
convex, 679
defined, 674
nodes, 674
point in, 683–684
pseudocode, 675–676
sample construction, 678
polyhedra
Boolean operations on, 726–729
convex, moving, 615–624
convex, point to, 393
convex, stationary, 611–615, 616
defined, 335, 494
formulas, 957–958
general, point to, 393
general projection pseudocode,
619–620
illustrated, 338
insertion, 764
partitioning problem, 798
point in, 708–726
polymesh constraints, 336–337
polymeshes not, 338, 339
polytope, 337
projection pseudocode, 618–619
ray interpenetration of, 712
regular, 346
polyhedron (BSP tree
representation), 688–690
balanced trees, 690
defined, 688
point in, 691
pseudocode, 688–689
See also binary space-partitioning
(BSP) trees (3D)
polyhedron intersections, 493–498
with line, 493–498
with planar components,
543–546
with ray, 494, 498
with segment, 494, 498
See also intersections (3D);
polygon intersections
polyhedron volume, 824–825
analytic construction, 824–825
faces, 824
polyline approximation
polynomial curve and line
intersection, 250–251
polynomial curves intersection,
262–263
polylines, 177–178
closed, 178, 229, 745
defined, 177
extensions, 178
illustrated, 178
intersection with linear
components, 246
998 Index
polylines (continued)
isolated, 339
linear component to, 229–230
open, 178, 229
point to (2D), 194–196
point to (3D), 369–373
segments, 195
polymeshes
defined, 334
definition of, 339
illustrated, 338, 339
implementation, 337
not polyhedra, 338, 339
polyhedra, 335
tetrahedron, 335
See also meshes
polynomial curve and line
intersection, 248–255
algebraic method, 248–250
hierarchical bounding, 251–252
monotone decomposition,
252–253
polyline approximation,
250–251
rasterization, 253–255
polynomial curves (2D), 185–188
B
´
ezier, 186
B-spline, 186–187
closest point on, 220
defined, 185
linear component to, 233
NURBS, 188
point to, 219–221
rational, 185
ray to, 233
segment to, 233
types of, 185
See also curves
polynomial curves (3D), 356–359
B
´
ezier, 357
B-spline, 357–358
defined, 356–357
Newton iteration and, 406
NURBS, 358–359
point to, 405–407
rational, 357
polynomial curves intersection,
262–264
algebraic method, 262
hierarchical bounding, 263
polyline approximation, 262–263
rasterization, 263–264
polynomial equations, 231, 606
general method of solution, 256
in unknown components, 466
polynomial roots, 870–873
bounding, by derivative
sequences, 871–872
bounding, by Sturm sequences,
872–875
polynomial surface intersections,
608–611
with algebraic surfaces, 520–521
analytic methods, 610
B-spline, 609
curves in parameter space, 610
defined, 608
failed, 522
with free-form surfaces, 521–529
lattice evaluation, 609
marching methods, 610–611
with planar components,
587–595
rational, 519
ray, 523–526
in ray tracing, 520
in selection process, 520
subdivision methods, 608–609
use of bounding volumes,
526–529
polynomial surfaces, 359–364
algebraic, 520–521
B
´
ezier, 360–362
B-spline, 362–363
defined, 359
free-form, 521–529
NURBS, 364
point to, 407–409
rational, 359
representation, 523
types of, 519
as vector-valued function, 519
See also polynomial surface
intersections
polynomials
Bernstein, 357
B
´
ezout matrix, 606
characteristic, 853
coefficients, 219
cubic, 844, 845, 846
intermediate, 844
numerator, 360
quadratic, 225, 260, 846
quartic, 260
ratios for, 359
roots, computing, 402
scalar-valued, 219
sixth-degree, 605
squared-distance, 220
Sturm, 873
systems of, 832–846
polysolids
defined, 179
illustrated, 180
polytope
defined, 337
illustrated, 339
Powell’s direction set method,
879–880
defined, 879
pseudocode, 879–880
See also minimization
preimage, 45
primitive operations (Boolean on
polygons), 717–719
difference, 719
exclusive-or, 718
intersection, 718
negation, 718
union, 718
See also Boolean operations (on
polygons)
principal subdeterminant, 598
principal submatrix, 598
prism formula, 958
product formula, 941
products
cross, 15, 92–93, 117–120
Index 999
dot, 15, 20, 54–55, 89, 90,
116–117
inner, 54
math notation, 15
perp dot, 121, 123–126
scalar, 20, 86–92
tensor, 15, 120–121
vector, 86, 92–94
ProjectGeneral function, 617
projection mapping, 333
projection point, 163
projections, 158–165, 266
area by, 821–822
center of, 159
cylinder onto line, 647
cylinder onto plane, 648
defined, 158–159
in graphics display systems, 159
inside disk, 390
interval, 277
matrix, 648
oblique, 160–162
orthogonal, 88, 159, 160
orthographic, 159–160
outside disk, 391
parallel, 159
perspective, 159, 163–165
of point onto plane, 663–664
subclasses, 159
uses, 159
of vector onto plane, 665–666
projective quadrics, 600
ProjectNormal function, 617
pyramid formula, 958
Pythagorean Theorem, 555, 934
Q
QR decomposition, 852–853
quadratic curve intersections,
255–262
circular components, 257–258
ellipses, 258–262
general quadratic curves, 255
quadratic curves, 181–185
circles, 183
classification, 377
closest point on, 218
defined, 181
ellipses, 183–185
fitting, to 2D points, 888–889
implicit equation of, 555
intersection with linear
components, 246–248
linear component to, 231–233
point to, 217–219
ray to, 232
segment to, 233
See also curves
quadratic equations, 181, 656
for ellipsoids, 605–606
general, 351, 401, 875
linear component/ellipsoid
intersection, 505
solutions to, 183
stable solution to, 875–876
quadratic form
for circles, 183
defined, 880
for ellipses, 184
minimizing, 880
restricted, minimizing, 880–881
quadratic polynomials, 225, 260,
846
quadric surface intersections,
595–608
algebraic approach, 596–601
curve, 595, 601
ellipsoids, 604–608
forms, 595
general, 596–604
geometric approach, 601–604
line, 595, 601
with linear components,
498–519
nonplanar, 602–604
nonplanar space curve, 595,
601
with planar components,
547–587
in planar conic sections, 602
with plane, 547–548
point, 595, 601
two curves, 595, 601
quadric surfaces, 351–355
ellipsoids, 403–405
fitting, to 3D points, 889
general, 499–501, 547
general, point to, 401–402
line to, 465–467
one nonzero eigenvalue, 352–355
point to, 401–405
three nonzero eigenvalues,
351–352
two nonzero eigenvalues, 352
See also quadratic curve
intersections
quadrics
canonical form, 598–599
Gauss’s reduction method, 600
Levin’s intersection method,
599–600
matrix form, 596
natural, 595, 602
parametric representation, 599,
600
projective, 600
ruled, 596, 599
signature, 598
trigonometric representations,
596–597
quadrilaterals
formulas, 954–955
in plane/cylinder intersection,
552
quadruple-angle formulas, 942
quartic polynomials, 260
quaternion representation, 860–861
axis-angle to quaternion, 860,
863
composition, 865–866
composition operation counts,
866
conversion time, 863–864
defined, 860
interpolation, 867
matrix to quaternion, 861,
863–864
memory usage, 862
quaternion to axis-angle,
860–861, 863
1000 Index
quaternion representation (contin-
ued)
quaternion to matrix, 861, 863
transformation time, 864–865
See also representations of 3D
rotations
quickhull, 730
R
radians, 924
definition of, 925
measure, 925
randomized algorithms, 732
randomized linear algorithms, 809
range
function, 45, 77
inverse trigonometric functions,
945–946
triangles, 175, 176
trigonometric functions, 931
rasterization
accuracy, 254–255, 264
effectiveness, 254
line and curve on grid, 254
polynomial curve and line
intersection, 253–255
polynomial curve intersections,
263–264
two curves on grid, 264
See also polynomial curve and
line intersection
rational polynomial curves
2D, 185
3D, 357
rational polynomial surfaces, 359,
519
ray intersections
with circular components, 248
with cone, 515–519
with cylinder, 507–512
with disk, 493
with ellipsoid, 504–507
with NURBS surface, 520
with OBB, 632
with parametric polynomial
surface, 523–526
with plane, 484
with polygon, 489, 491
with polyhedron, 494, 498
with sphere, 503–504
with triangle, 488
See also linear component
intersections
ray-to-ray distance (2D), 224–226
ray-to-ray distance (3D), 422–423
defined, 422
domains, 413
illustrated, 422
pseudocode, 422–423
See also distance algorithms (3D)
ray-to-segment distance (2D),
226–228
ray-to-segment distance (3D),
424–426
defined, 424
domains, 413
illustrated, 424
pseudocode, 424–426
See also distance algorithms (3D)
ray tracing, 660
grid method in, 708
in polynomial surface/linear
component intersection, 520
rays
boundary points of interest for,
226–227
closest point on, 192
defined, 173
illustrated, 172
line to (2D), 222–223
line to (3D), 418–420
to ORB, 464
origin, 325
parallel configurations for
distance, 227
parameterized, 241
point to (2D), 191–192
point to (3D), 367–369
pointing in opposite directions,
226
to polynomial curve, 233
to quadratic curve, 232
to rectangle, 446
representation as intersection of
two planes, 524
tetrahedron and, 450
to triangle, 441
See also linear components; ray
intersections
rectangles
in 2D, 177
alternative definition of, 382
area of, 177
axis-aligned, 373
axis-aligned bounding, 251
closest point on, 382–383
defined, 177
formula, 954
line to, 442–446
linear component to, 441–446
minimum-area, 803–806
parallel edges, 344
parametric form, 177
partitioning of plane by, 212, 383
point to (2D), 211–213
point to (3D), 382–384
ray to, 446
segment to, 446
symmetric form, 177, 178
vertex-edge form, 177
vertices, 382
recursive subdivision, 253
reflection, 148–153
2D, 150, 151
3D, 149–150, 151
defined, 148
general, 150–153
matrix, 149, 150
orientation reversal, 148
simple, 149–150
vector, 151–152
y-axis, 149
See also affine transformations
reflex chain
defined, 786
vertices, 786, 787, 789
reflex vertices, 768
as base vertex, 792
cone containment, 770
containment, testing for, 768
Index 1001
of convex polygon, 792
defined, 767
precomputing, 796
ReformatAndInsert function, 752,
753
regular polygons, 346
regular polyhedra, 346
rejection test, 194
intersection between segment
and axis-aligned box, 373
linear component to
polyline/polygon, 230
modification of, 195
point to polyline, 369–370
point-to-polyline example, 371
quantities, 195, 371
relative error
defined, 2
tolerances, 736
relative extrema, 903–905
defined, 903
of function of two variables, 906
illustrated, 903, 904
relative maximum, 903
relative minimum, 903
relaxation, 477
representations of 3D rotations,
857–869
axis-angle representation,
858–859
matrix representation, 857
performance issues, 861–869
quaternion representation,
860–861
rhombus formula, 955
right-hand rule, 74, 75, 93
ring torus, 356
Rodriguez’s formula, 141
root finders, 5, 6
root finding, 869–876
bisection, 870, 874
Laguerre’s method, 521
methods in many dimensions,
874–875
methods in one dimension,
869–873
Newton’s method, 870, 874–875
polynomial roots, 870–873
solution to quadratic equations,
875–876
roots
finding, 5–6
multiplicity, 5–6
Newton’s method for finding, 5
numerical problems, 6
rotating calipers method, 238–239
defined, 806
for finding minimum-area
rectangle, 806
rotation, 136–142
3D, representations of, 857–869
angle, 848
center of, 136
counterclockwise, 848
formula, 141
of frames, 137
general, 139–142
linear transformation
component, 142
matrix, 17–18, 138, 330, 652
matrix, factoring, 848–852
point, 140, 141–142
simple cases, 136–139
vector, 10–11, 140
x-axis, 138, 847
y-axis, 138, 847
z-axis, 138, 847
See also affine transformations;
linear transformations
rotation matrix representation, 857
composition, 865–866
composition operation counts,
866
conversion time, 862, 864
defined, 857
interpolation, 868, 869
memory usage, 862
transformation time, 864
See also representations of 3D
rotations
rotation transformation
defined, 78
illustrated, 79
See also linear transformations
round-off error, 2
row reductions, 31
rowvectors,110
ruled quadrics, 596, 599
S
saddle points
defined, 908
illustrated, 909, 911
locating, 908
scalar division, 19
scalar matrices, 33
scalar multiplication, 19
associativity of, 20, 23
defined, 65
determinant, 37
distributivity of, 20
identity, 20
matrix representation, 115
properties, 66–69
scalar product, 86–92
defined, 20, 86
symbols, 86–87
scalar triple product, 125–126
defined, 95
determinant relationship,
126
scalars, 42
defined, 15
math notation, 15
properties, 96
scalar-valued properties, 63
scaling, 142–148
direction, 146
factor, 145, 146
frames, 143
general, 144–148
illustrated, 143
nonuniform, 78, 79, 143, 855
origin, 145, 146
points, 142, 145, 146
sequence of operations, 144
simple, 142–144
uniform, 78, 79, 142, 855
vector, 65–66, 145
See also affine transformations
1002 Index
secant function
for commonly used angles, 929
defined, 927
domain and range, 931
graph, 932
period, 935
See also trigonometric functions
Second Derivative Test, 904
segment intersections
with cone, 515–519
with cylinder, 507–512
with disk, 493
with ellipsoid, 504–507
with plane, 484–485
with polygon, 491
pseudocode, 244–245
with sphere, 503–504
with triangle, 488
See also linear component
intersections
segment partitioning (BSP tree),
684–687, 692–694
defined, 684–685
partition illustration, 687
partitions, 685, 692
positive segments, 685, 692
pseudocode, 685–686
subsegments, 684
See also binary space-partitioning
(BSP) trees (2D)
segment-to-segment distance (2D),
228–229
segment-to-segment distance (3D),
415–418
alternative, 426–433
defined, 415
domains, 413
illustrated, 416
implementation, 429–433
nonparallel segments, 426–428
parallel segments, 429
pseudocode, 417–418
See also distance algorithms (3D)
SegmentIntersect function, 771
segments
closest point on, 192, 369
configuration for attaining
current minimum distance,
230
connecting closest points, 232
defined, 173, 325
diagonal, 767
illustrated, 172
iterating over, 369
line to (2D), 223–224
line to (3D), 420–422
nonparallel, 426–428
to ORB, 465
parallel, 429
parallel case for distance, 229
parameterized, 241
parametric, equivalent formula,
223
point to (2D), 192–193
point to (3D), 367–369
polyline, 195
to polynomial curve, 233
to quadratic curve, 233
ray to (2D), 226–228
ray to (3D), 424–426
to rectangle, 446
standard form, 173–174,
325–326
symmetric form, 174, 326
tetrahedron and, 450
to triangle, 441
See also linear components;
segment intersections
self-intersecting spindle torus,
356
separating axis test, 625–626
coefficients, 626
defined, 625
separating lines
defined, 265
with nonintersecting convex
objects, 266
test for two cylinders, 648–650
translation of, 265
separation
of moving convex polyhedra,
615–616
of stationary convex polyhedra,
611–615
sets
intersection, 273–276, 616, 723
level, 894–897
math notation, 15
operations, 234–235
spanning, 43, 70
SG algorithm, 725
shear transformation
defined, 78
illustrated, 79
See also linear transformations
shearing, 153–158
2D, 155
3D, 156
defined, 153
general, 157–158
scale, 154
simple, 154–156
transformation matrix, 154, 156
See also affine transformations
simplexes
1-simplex, 106
2-simplex, 106
3-simplex, 106
affine map operation on, 105
circumscribed ball for, 799
defined, 799
inscribed ball for, 801
line, 106, 107
tetrahedron, 106, 107
triangle, 106, 107
simplexification, 756
sine function
for commonly used angles,
929
defined, 926
domain and range, 931
graph, 932
illustrated, 77
period, 935
See also trigonometric functions
single cone, 213
single-variable functions, 898–905
singular value decomposition, 857
“skew symmetric matrix,” 119
slabs method, 627
slivers, 764
Index 1003
solids
defined, 171
platonic, 346–351
space(s)
affine, 80–98
Euclidean, 54–56
half-spaces, 687, 688
inner product, 54–55
linear, 41–45
math notation, 15
subspaces, 43
vector, 69–79
world, 112
spanning set, 43, 70
spatial merge, 753
spatial-partitioning scheme, 522
spectral radius, 871
sphere and AABB intersection,
644–646
AABB definition, 644
defined, 644–645
“hollow” primitives version, 646
illustrated, 644
pseudocode, 645
See also intersections (3D)
sphere intersections, 501–504
with axis-aligned bounding box,
644–646
with line, 502–503
with linear components,
501–504
with plane, 548–551
with ray, 503–504
with segment, 503–504
See also intersections (3D)
spheres
axis, 558
center, 501
center, distance to, 549
circumscribed, 799
defined, 548–549
fitting, to 3D points, 887–888
formulas, 959–960
inscribed, 799
minimum-volume, 811–813
radius, 501, 558
sector, 960
segments, 959–960
specification, 549
See also circles
SplitPolygon function, 690
square formula, 954
square matrices, 17, 32–40
determinant, 34–37
diagonal, 32–34
inverse, 38–40
triangular, 34
See also matrices
squared distance, 190, 191, 193, 194
calculation, 220
between circles, 477
function, 377
minimum, 219, 365, 477
between points, 224
polynomial, 220
standard form
algorithm to defer division, 193
defined, 173–174, 325–326
stationary convex polygons
alternative implementation
(separation test), 270–271
asymptotically better alternative
(separation test), 271–273
bisection method, 271–273
direct implementation
(separation test), 269–270
edge normals, 266, 268
edge-to-edge contact, 267
intersection set, 276–277
separation of, 266–273
vertex-edge contact, 267
vertex-vertex contact, 267
See also convex polygons
stationary convex polyhedra
edge-edge, 611
edge-vertex, 611
face-edge, 611
face-face, 611
face-vertex, 611
find-intersection query, 616
intersection set, 616
intersection testing, 611–612
separation of, 611–615
vertex-vertex, 611
See also convex polyhedra;
method of separating axes
(3D)
stationary points
defined, 899
illustrated, 900
steepest descent search, 878
Stokes’ Theorem, 822–823
st-plane, 378, 427
Sturm sequences, 872–873
subdivision of curves, 889–894
by arc length, 890–891
by midpoint distance, 891–892
by uniform sampling, 889–890
by variation, 892–894
See also curves
submatrix
defined, 36
forming, 36
minor, 36
principal, 598
subspaces, 43, 71
subtraction
formula, 940–941
of matrices, 19
point, 81
of tuples, 16
vector, 65
subtractive cancellation, 4
supersimplex, 763
supertriangle
defined, 757
infinitely many, 757–758
of input point set, 763
Supertriangle function, 760
surfaces
B
´
ezier, 360–362
B-spline, 362–363
geodesic distance on, 477–479
NURBS, 364, 520
parameterization, 597
parametric, 407, 521, 587
polynomial, 359–364
quadric, 351–355
types of, 360
surface-surface intersections (SSIs),
608