Schneider P., Eberly D.H. Geometric Tools for Computer Graphics

Подождите немного. Документ загружается.

984 Index

GetLineFromEdge function, 676

GetPartition function, 722

GetPlaneFromFace function,

689

gift wrapping, 730

GJK algorithm, 1, 217, 233–239

3D, 468

alternatives, 238–239

deﬁned, 234

as descent method, 236

ﬁrst iteration, 237

fourth iteration, 238

implementation, 236

as iterative method, 234–235

overview, 235–238

second iteration, 237

set operations, 234–235

third iteration, 238

Graham’s algorithm, 730

Gram-Schmidt orthogonalization

process, 55–56

Gram-Schmidt orthonormalization

algorithm, 852

Green’s Theorem, 819, 820

grid

cells, 707

data structure, 707

method, 707–708

Haines algorithm, 495

half-angle formulas, 944

half-spaces, 370, 687

negative side, 687

positive side, 687

subdivision, 688

Head-to-Tail axiom, 80–82

deﬁned, 80

illustrated, 81

rewriting, 82

Hermite basis functions, 589

Hermite curves, 589–590

deﬁned, 589

illustrated, 590

hexadedron, 348

face connectivity, 348

illustrated, 346

relationships, 347

triangle connectivity, 348, 349

vertices, 348

See also distance algorithms (3D)

line-to-planar curve distance,

469–471

algebraic representation,

470–471

deﬁned, 469

examples, 470, 471

parametric representation,

469–470

See also distance algorithms (3D)

line-to-polynomial distance,

467–468

line-to-quadric surface distance,

465–467

alternative approach, 467

deﬁned, 465

equations, 465, 466

polynomial equations, 466

See also distance algorithms (3D)

line-to-ray distance (2D), 222–223

line-to-ray distance (3D), 418–420

deﬁned, 418

domains, 413

illustrated, 419

pseudocode, 419–420

See also distance algorithms (3D)

line-to-rectangle distance, 442–446

illustrated, 442

partitioning, 444

region pseudocode, 444–446

See also distance algorithms (3D)

line-to-segment distance (2D),

223–224

988 Index

line-to-segment distance (3D),

420–422

deﬁned, 420

domains, 413

illustrated, 420

pseudocode, 421–422

See also distance algorithms (3D)

line-to-tetrahedron distance,

447–448

line-to-triangle distance, 437–441

illustrated, 434

region 0 pseudocode, 439

region 3 boundary strip/planes,

440

region breakdown, 437–439

See also distance algorithms (3D)

linear combinations, 43

of basis vectors, 72, 75

deﬁned, 174

preserving, 77

of two sets of basis vectors, 76

of vectors, 100

linear component and AABB

intersection, 626–630

clipping line against slab, 629

as clipping problem, 627

deﬁned, 626–627

illustrated, 627

pseudocode, 628–630

slab clipping illustration, 631

slabs method, 627

in spatial subdivision problems,

626–627

as three “slabs,” 628

See also intersections (3D)

linear component and OBB

intersection, 630–634

clipping against oriented slab,

632

clipping distance calculation, 630

deﬁned, 630

pseudocode, 632–634

ray, 632

See also intersections (3D)

linear component and torus

intersection, 659–662

deﬁned, 659

illustrated, 659

normal computation of torus at,

660

quadratic equation, 660

for ray tracing, 660

texture coordinate computation,

661

torus deﬁnition, 659

u parameter of point on torus,

661

v parameter of point on torus,

662

See also intersections (3D)

linear component intersections

2D, 241–245

with axis-aligned bounding box,

626–630

with circular components,

247–248

with cone, 512–519

with cylinders, 507–512

with disks, 491–493

with ellipsoid, 504–507

with general quadratic curves,

247

with oriented bounding boxes,

630–634

with planar components,

481–493

with planes, 482–485

with polygons, 488–491

with polyhedra, 493–498

with polylines, 246

with polynomial curves, 248–255

with polynomial surfaces,

519–529

with quadratic curves, 246–248

with quadric surfaces, 498–519

with spheres, 501–504

with torus, 659–662

with triangles, 485–488

linear component to rectangle

distance, 441–446

deﬁned, 442

determinant, ﬁnding, 444

line, 442–446

ORB, 450–453

to oriented bounding box,

450–453

partitioning, 443

ray, 446

segment, 446

solution domain partitioning,

444

squared-distance function, 442

See also distance algorithms (3D)

linear component to tetrahedron

distance, 447–465

cases, 449

closest points, 448–449

line, 447–448

no zero-components, 458–464

one zero-component, 455–458

ray, 450

ray to ORB, 464

segment, 450

segment to ORB, 465

three zero-components, 453

two zero-components, 453–455

linear component to triangle

distance, 433–441

domains, 436

line, 434, 437–441

partitionings, 436

ray, 441

segment, 441

solution values, 436

See also distance algorithms (3D)

linear components

in 2D, 171–174

converting between

representations, 174

deﬁned, 241, 326

distance algorithms (2D),

221–229

distance algorithms (3D),

409–433

geometric primitives (2D),

171–174

geometric primitives (3D),

325–326

implicit form, 172–173

parametric form, 173–174

points to, 365–373

Index 989

to polygon, 229–230

to polyline, 229–230

to polynomial curve, 233

to quadratic curve, 231–233

See also distance algorithms (3D)

manifold edges, 339

manifold meshes

connected, 344

consistent orderings, 343

deﬁned, 342

orientability, 342, 343

See also intersections (3D)

oriented bounding boxes (OBBs)

as AABB with different

orientation, 630

as axis-aligned box, 394

basis vectors, 395

centerpoint, 394, 450

clipping distance calculation, 630

deﬁned, 394, 630

deﬁning, 630

diagonal projection, 636, 638

distance computation, 395

inside frame computations, 451

line to, 451–453

linear component to, 450–453

local frame, 452

point to, 394–397

“positive” faces, 459, 460

specifying, 631

symmetric form, 624