Schneider P., Eberly D.H. Geometric Tools for Computer Graphics
Подождите немного. Документ загружается.
1004 Index
symmetric form
defined, 174, 326
of rectangles, 177, 178
systems of polynomials, 832–846
any-degree equations in any
formal variables, 837–846
any-degree equations in one
formal variable, 835–837
linear equations in one formal
variable, 833–834
three variables, one quadratic
equation, two linear
equations, 839–840
three variables, three quadratic
equations, 843–846
three variables, two quadratic
equations, one linear
equation, 840–842
two variables, one quadratic
equation, one linear equation,
837
two variables, two quadratic
equations, 838–839
T
tables, vertex-edge-face, 337–339
tags
current, 704
for edge-line intersections,
705
for horizontal line, 705
inside, 704, 705–706
interval, 706
minus, 703, 704
outside, 704, 705
plus, 703, 705
point, 705
See also points
tangency, 6
tangent function
for commonly used angles, 929
defined, 926
domain and range, 931
graph, 932
period, 936
See also trigonometric functions
tangents
defined, 731
law of, 939
lower, 740
lower, incremental search for,
741
search, 741, 743
search, extreme points
initializing, 745
upper, 740
See also convex hulls
tensor product, 120–121
defined, 121
math notation, 15
See also products
terminator
defined, 745
finding, 753, 754
traversing edges of, 749
tessellants, 522
TestIntersection function, 613
equivalent formulation,
280–281, 620–621
first loop, 277
modification, 277, 617
test-intersection query, 611
defined, 265
See also method of separating
axes (2D); method of
separating axes (3D)
tetrahedralization, 756
tetrahedron, 347
defined, 335, 543
illustrated, 346
line to, 447–448
linear component to, 447–465
point in, 708–709
point to, 391–393
projecting, onto perpendicular
plane, 448
ray and, 450
relationships, 347
segment and, 450
vertices, 347, 447
See also platonic solids
three-plane intersection, 532–534
configurations, 533
Cramer’s rule and, 534
defined, 532–533
Gaussian elimination and, 534
problem, 532
See also intersections (3D); plane
intersection
three-variable extrema problems,
917–922
single constraint, 917–920
two constraints, 920–922
three-variable extremum problem,
911–916
constraint curve and ellipse,
916
level curves, 916
plot of ellipse, 915
plot of function, 915
time-varying boundary condition,
478
torus, 355–356
defined, 355
defining, 659
formula, 960
horn, 356
intersection with linear
component, 659–662
major radius, 356
minor radius, 356
normal computation at point of
intersection, 660
parametric definition, 356
ring, 356
self-intersecting spindle, 356
u parameter at point on, 661
v parameter of point on, 662
transformation(s)
affine, 98–104
ambiguous, interpreting, 11
basis vectors, 49
concatenating, 11
homogeneous, 854, 855
linear, 76–79
matrices, computing, 12
normal vector, 165–168
from one plane to another, 11
plane onto itself, 11
point coordinates, 10
Index 1005
translation, 134–136
of frames, 136
orientation and, 135
transform, 134
vector length and, 135
See also affine transformations
transversality, 6
trapezoids
binary search tree for, 778
entire plane as, 777
forcing partitioning of, 778
formula, 955
horizontal decomposition into,
776
insertion pseudocode, 782
merged, 783, 784
“outside,” 780
triangulation support, 782–783
unbounded, 777, 778
triangle connectivity
dodecahedron, 349–350
hexahedron, 348
icosahedron, 350–351
tetrahedron, 347
See also platonic solids
triangle formulas, 949–953
definitions for, 950–952
equilateral triangle, 953
general triangle, 953
right triangle, 952
symbols for, 949–950
triangle intersections, 485–488
with cone, 583–587
with line, 485–488
with linear components,
485–488
with plane, 534–539
with polygon, 545–546
with ray, 488
with segment, 488
with triangle, 539–542, 721
See also intersections (3D)
triangle meshes
defined, 334
illustrated, 335
triangle/cone intersection, 583–587
cone axis and plane, 586
culling of triangles, 583
defined, 583
at edge point, 584
edge test, 585
find intersection, 586–587
at interior triangle point, 584
test intersection, 583–586
at vertex, 584
vertex test, 584
triangle/plane intersection,
534–539
configurations, 534–535
configurations illustration, 536
defined, 534
illustrated, 535
pseudocode, 535–539
See also intersections (3D)
triangle/triangle intersection,
539–542
algorithm outline, 542
configurations, 539
configurations illustration, 540
defined, 539
edge-face, 540
interval overlap configurations,
540–541
See also intersections (3D)
triangles
in 2D, 175–177
area, 816, 950
barycentric form, 175, 176
bounding box, 207
center of gravity, 950
circumcenter, 951
circumradius, 951
clockwise, 175
counterclockwise, 175
culling of, 583
defined, 175
domain, 175, 176
edges, 771, 790
incenter, 951
incircle of, 285
inradius, 951
intersection of altitudes, 952
intersection of angle bisectors,
951
intersection of medians, 950
intersection of perpendicular
bisectors, 951
line to, 434, 437–441
linear component to, 433–441
moving, edge-to-edge contact,
282
needlelike, 697
nonintersecting, 541
parametric form, 175, 176, 435
perimeter, 950
point in, 695–697
point to (2D), 196–211
point to (3D), 376–382
range, 175, 176
ray to, 441
segment to, 441
signed area of, 176
supertriangle, 757–758
vertices, 175, 376, 541, 583
See also triangle intersections
triangular matrices, 34
defined, 34
determinant of, 37
lower, 34
properties, 34
upper, 34
See also matrices
triangular system, 828
triangulation, 771–775
2D, 766
by ear clipping, 772–775
by horizontal decomposition,
775–789
canonical, 792–794
defined, 756, 771
Delaunay, 756–767
monotone mountain, 789
monotone polygon, 785–789
trigonometric functions, 926–934
for acute angles, 927–928
cosecant, 927, 929
cosine, 926, 929
cotangent, 927, 929
definitions in terms of
exponentials, 930
derivatives of, 931–933
1006 Index
trigonometric functions (contin-
ued)
domains and ranges, 931
generalized definition, 928
geometrical interpretation, 930
graphs, 932
integration, 934
inverse, 945–948
laws, 936–939
periodicity, 935–936
secant, 927, 929
sine, 926, 929
tangent, 926, 929
values for commonly used
angles, 929
trigonometry, 923–948
angles, 923–925
conversion examples, 925–926
formulas, 940–944
functions, 926–934
identities and laws, 934–944
introduction, 923–926
terminology, 923
trimeshes, 543–544
triple-angle formulas, 942
t-space, 598
tuple multiplication, 20–21, 110
defined, 20
properties of, 21
tuples, 14–16
addition of, 16
arithmetic operations, 16
collection of, 16
column, 23–24
composition of, 14–15
defined, 14, 15
division of, 16
list of, 17
math notation, 15
multiplication of, 16
of n elements, 16
row, 23–24
subtraction of, 16
tuples of, 17
two-plane intersection, 529–531
defined, 529–530
illustrated, 530
intersection line, 530
intersection point, 530–531
pseudocode, 531
See also intersections (3D); plane
intersections
two-variable extremum problem,
911
two-variable functions, 906
U
uniform B-spline curves, 187
uniform B-spline surfaces, 363
uniform sampling subdivision,
889–890
uniform scaling, 78, 79, 855
defined, 142
general, 145–146
illustrated, 145
See also scaling
union
Boolean operation on polygons
(abstract), 715, 717
Boolean operation on polygons
(primitive), 718
Boolean operation on polyhedra
(abstract), 726
simplices, 764
unit quaternions, 860
unit vectors, 15
Update function, 753, 754, 810
usual basis, 112
V
V algorithm, 725
defined, 725
edge comparisons, 725
implementation based on, 726
subedge identification/merging,
725
variation subdivision method,
892–894
defined, 892
metric quantities, 893
pseudocode, 893–894
See also subdivision of curves
vector addition, 42, 64
associativity, 68
chain, 66
commutativity, 68
distributivity of dot product
over, 90
distributivity over dot product,
91
illustrated, 66
in matrix presentation, 113–114
parallelogram rule for, 87
with points, 114–115
properties, 66–69
vector algebra, 63–107
vector geometry
of affine transformations,
132–158
coordinate approach to, 13
matrix operations, 13–14
vector length
illustrated, 86
math notation, 15
translation and, 135
vector multiplication, 42, 67
vector negation
defined, 66
illustrated, 69
vector product, 92–94
anticommutativity, 93
defined, 86
distributivity, 93
illustrated, 92
math notation, 15
parallelism, 93–94
properties, 93–94
vector projection, 87
vector space, 69–79
addition, 69
basis, 71
defined, 69–70
dimension, 71
linear independence, 71
linear transformations, 76–79
orientation, 73–75
properties, 69–70
spanned, 70
subspace, 71
Index 1007
vector subtraction, 65
defined, 65
illustrated, 67
in matrix representation,
113–114
with point, 114–115
vector-based approach, 12
vector(s)
angle between, 74, 86
basis, 49, 72
defined, 42, 63
as directed line segments, 64
direction, 193, 367
equation representation, 13
equivalence, 63–64
gradient, 607
identity matrix, 12
illustrated, 65
knot, 187, 362
linearly independent, 45, 73
math notation, 15
matrix representation of,
110–113
orthographic projection of, 159
parallel, 15
perpendicular, 15, 121
perspective map for, 165
perspective projection of, 164
preceding, 44
projection onto planes, 665–666
representation as affine
combination of basis vectors,
130
rotation, 10–11, 140
row, 110
row matrix representation, 50
scale illustration, 102
scaling, 65–66, 145
span in 3D space, 70
sum, 101
tangent, 168
transforming, 165–168
unit, 15
unit-length, 172
zero, 70
See also normal vectors
vector-valued properties, 63
vertex indices, 333
vertex ordering preservation, 35
vertex-edge contact, 267, 283
vertex-edge form, 177
vertex-edge-face tables, 337–339
defined, 337
edge representation, 337
face representation, 337
grammar, 337–338
meshes stored in, 344
vertex-vertex contact, 267, 283
vertices
collinear, 696–697, 767
cone, 213, 513
convex, 767, 770
defined, 333
dodecahedron, 349
hexahedron, 348
icosahedron, 350
isolation, 339
noncollinear, 695–696
octahedron, 348
parabola, 574
platonic solids, 346
polygons, 179
rectangle, 382
reflex, 767, 768, 770, 792
reflex chain, 786, 787, 789
tetrahedron, 347, 447
triangle, 175, 376, 541, 583
Voronoi regions for, 397
visibility cone, 745
visibility graphs, 767–771
between any two vertices,
769–771
defined, 767
volume
box, minimum, 806–807
formulation of Divergence
Theorem, 825
polyhedron, 824–825
signed, determinants as, 96
sphere, minimum, 811–813
Voronoi regions, 215–216
for edges, 397
for faces, 397
pseudocode for determining,
398–401
for vertices, 397
W
walking algorithm, 740
Weiler-Atherton (WA) algorithm,
724
defined, 724
implementation based on, 725
subedge identification/merging,
725
while loop, 714
X
x-axis, 138, 847
xy-plane, 331
level curves projected onto, 897
triangulation of, 333
Y
y-axis
reflection, 149
rotation, 138, 847
scaling, 143
Z
z-axis
rotation, 138, 847
scaling, 144
zero matrix, 19
zero vector, 70
About the Authors
Philip Schneider leads a modeling and dynamic simulation software group at Walt
Disney Feature Animation. Prior to that, his work at Apple and Digital Equipment
Corporation in 3D graphics ranged from low-level interfaces to graphics libraries and
interactive applications. He holds an M.S. in Computer Science from the University
of Washington.
David Eberly is President of Magic Software, Inc. and is the architect of the real-time
3D game engine Wild Magic. Previously, he was Director of Engineering at Numerical
Design, Ltd., the company responsible for the real-time 3D game engine NetImmerse.
He holds a Ph.D. in Computer Science from the University of North Carolina at
Chapel Hill and a Ph.D. in Mathematics from the University of Colorado at Boulder.
1009