ABSTRACT

A abstract interface, 181-184 abstract layer, 45 Acceleration function, 577,

582, 586, 589, 591 active intervals, 555 AddInitializer function, 143 addition

hard, 211, 437, 438 soft, 211, 437, 438

AddTerminator function, 144 adjacent indices, 589 Adjoint function, 82 adjoint matrix, 82 AdjustVerticalDistance

function, 535 AdjustWindowRect function, 6 affine algebra, 174 AglRenderer class, 277 algebraic operations, 70 Align function, 100 Allocate function, 371, 376,

585, 589 alpha blending, 203-204, 354

classical method, 208 classic equation, 208-209 coefficients, 209 default behavior, 212 defined, 208 destination coefficients, 210,

212 destination color, 208 source coefficients, 210, 211 source color, 208 use of, 214 See also global states

alpha channels, 439 AlphaState class, 209-210, 212,

alpha testing AlphaState interface and,

213 default, 213 defined, 212 examples, 214-215 pseudocode, 212

ambient lights defined, 223 specular modulator, 227 See also lights

angles Euler, 414, 418 joint, 414 of rotation, 418, 622 sines/cosines, 424 specification, 414-415

angular momentum, 594 angular velocity, 594 animation

defined, 121 keyframe, 402-404 skin-and-bones, 410-414 support, 158 via controllers, 592

Append operation, 49 Application class, 607-609

constructor, 608 defined, 607 interface, 607-608

application layers, 27 applications, 601-675

abstraction, 602-637 command line parameter

processing, 603-607 console, 609-612 entry point to, 608 header file, 637 library, 602

object motion, 621 sample, 637-672 skeleton code, 637-641 subsystem, 602-603 TestBillboardNode, 642, 643 TestBspNode, 642-645 TestCachedArray, 645-646 TestCastle, 646-648 TestClodMesh, 648 TestCollision, 648-654 TestInverseKinematics,

654-656 TestPortals, 656-662 TestScreenPolygon, 662-668 TestSkinnedBiped, 668-669 TestSortFaces, 669-670 TestTerrain, 670-672 types, 603 windowed, event handlers,

608 ApplyForward function, 173,

339 ApplyInverse function, 173,

176 arithmetic operations, 81 arrays, 33-35

allocation, 52 constructor, 33 contiguous, 81 deallocation, 35, 53 dynamic, 165 edge, 323, 324, 326 elements, removing, 34 global, 141 heap, 313-319 initializer, 144 largest-indexed element, 32 manipulation, 23 n×m, 14

pointers, 66-67 reallocation, 35 shared, 294 size, 32 three-dimensional, 51-53 two-dimensional, 49-51 typecast, 66-67 vertex, 23, 294

assignment operators, 80 AttachChild function, 163 AttachOutside function, 347 automatic portaling systems,

274 axis-aligned bounding boxes

(AABBs), 555 generating, 561 intersecting intervals,

555-560 intersection determination,

561 updating, 555

B back buffers, 279 back-facing triangles, 220 background colors

in back buffer clearing, 23 replacement, 25

backward finite difference, 573

barycentric coordinates, 503 Base class, 64, 65 BeginScene function, 281, 282 Be´zier curves, 370 Be´zier mesh, 361 Be´zier patches, 361 bilinear interpolation, 24, 233,

240, 388 coordinates on image

boundaries and, 238 illustrated, 235 infinite, 300

defined, 300 interface, 300-301 use of, 302

billboards, 300-302 alignment, 301, 302 constrained, 301 continuous, 300 corners, 305 defined, 299 discrete, 300 model space, 301 rectangular, 300 squares, 303, 304 world transforms

computation, 301 See also level of detail (LOD)

binary number comparisons, 69

binary space partitioning (BSP) trees, 336-343

as coarse-level sorting, 336 leaf nodes, 343 sorting in two dimensions,

337 for spatial partitioning, 343

BindInfoArray class, 479 BindInfo class, 293, 479 binding

public access, 293 texture, 295

binormal vectors, 363, 443 bisection

algorithm, 490 derivative evaluations and,

496 root finding with, 496-497

blocks in distance, 382 even, 382 management, 384 odd, 382 resetting, 396 simplification, 382-388

state, BloodCellController class, 410 BmpToWmif converter, 673 bones

defined, 410 model space, 411 offset, 411 vertices relationship, 412 See also skinning

Booleans, 605 border colors, 238-239 bounding sphere, 180 BoundingVolume class, 181,

182-183, 531, 542 bounding volumes, 177-184

abstract interface, 181-184 better-fitting, 180 calling, 183 child, 187 in collision determination,

180-181 complexity, 179 convex, 177, 178 creating, 183-184 for culling, 178-180 default type, 180 defined, 177 input, 183 inside view frustum planes,

271 intersection, testing for,

180-181 intersection with linear

components, 508-527 iterative growing algorithms,

194 location, 181 model, 188 model computation, 544 in Spatial class, 184 sphere, 178 test, 540 types of, 508 union of, 177

193, 544

See also oriented bounding boxes (OBBs); spheres

BoundingVolumeTree class constructor, 544, 545, 546 defined, 542 interface, 542-544

bounding volume trees, 540-542

defined, 540 interior nodes, 546 leaf nodes, 540 types, 542 using, 540

bounds model, 154 transformations relationship,

157 world, 155

BoxBV class bounding volume, 546 defined, 542 use of, 542

BoxBVTree class, 542 braces, 685-686 BspNode class, 337-338

constructors, 338 defined, 337 interface, 337-338

BSP nodes, 337 children, 342 classical, 337 plane specification, 338 positive child, 342 See also binary space

partitioning (BSP) trees buffers

back, 279 clearing, 23 depth, 279 input, 48, 49 stencil, 279 swap, 12, 13

attaching, to objects, 444 defined, 443 interface, 443-444 virtual function pointer

assignment, 444 bump mapping, 432, 440-446

defined, 440 dot3, 441, 443, 445, 446 illustrated, 446 sample application, 445

C C++ exceptions, 691-692 caching

support, 292, 295 vertex buffer objects for, 295

Camera class, 263-265, 342 bit flag, 271 culling interface, 272 culling portal support, 351 defined, 263 interface, 263-264 local translation, 264 object culling support,

270-275 picking interface, 276 pick ray implementation,

528-529 public interface, 273-274 support interface, 352 viewport parameters

interface, 268 camera models, 28, 259-276

coordinate system, 259-260 defined, 259 view frustum and, 261

CameraNode class, 263 cameras

attaching to global state, 263 coordinate frame, 622 coordinate system, 9, 264

direction vector, 260 local coordinate axes, 623 location specification, 4 movement about terrain, 398 origin, 260 position, 264 renderers and, 259-298 right vector, 260 rotation, 15 translation, 5 up vector, 260 world coordinates, 398

center-and-fit operation, 631 central processing unit (CPU),

158 CgConverter program, 486 Cg pixel shader, 470-472 Cg Toolkit, 466, 486 Cg vertex shader program,

465-466 CharcoalEffect class, 486

defined, 478 interface, 478-479 object, 479

CharcoalPShader class, 486 constructor, 476-477 defined, 476 interface, 476

CharcoalVShader class, 486 constructor, 475 defined, 474 interface, 474 object, 479

children, sorting, 354-356 Clamp method, 104 clamp-to-edge mechanism,

399 class names, 690 Clear method, 44 clipping

algorithm, 517 defined, 259 planes, 274

382-384

defined, 382 interface, 382-384

ClodTerrain class, 391-393 constructor, 393, 398 defined, 391-392 interface, 392-393

ClodTerrainPage class, 384-387 creation, 394 defined, 384 interface, 385-387 page, 384

ClodTerrainVertex class, 379-380

array, 380 defined, 379 interface, 380

Clone function, 432, 438, 444, 447, 451, 478

clones controls, 136, 137 default, 135 illustrated, 137

cloning, 133-137 defined, 135 operations, 137

close terrain assumption, 382 clouds

EMBMI, 151, 152 exporting, 152 geometry, 151

coding conventions, 677-698 braces, 685-686 C++ exceptions, 691-692 classes and functions, 690 comment preamble and

separators, 680-681 constructor initializers, 683 enumerations, 690-691 file naming/organization,

677-679 identifier names, 688-691 pointer types, 686-688

white space, 681-685

collision avoidance, 535-536 basis, 536 defined, 535 support, 536

collision detection, 487-563 algorithms, 487 defined, 487 distance-based methods,

488, 492-500 hierarchical, 540-553 intersection-based methods,

488, 500-503 library, 501 moving objects, 488 queries, 487 stationary objects, 487-488 subsystems, 592 system, 487

collision determination, 180-181

bounding volumes in, 180-181

for triangle meshes, 180 CollisionGroup class

defined, 537 FindIntersection function,

552 interface, 551 TestIntersection function,

552 collision groups, 536-540

collision records, 547 defined, 536 intersection query, 539-540 management, 652 objects in, 536 organization, 537 updating, 536-537

collision proxies, 542 collision queries, 542 CollisionRecord class

defined, 539

interface, TestIntersection query,

548-549 collision records, 652

for cylinders, 654 defined, 547 find-intersection query, 550 passing callback functions to,

652 test-intersection query,

548-549 collision response system, 487 ColorRGBA class, 103, 104-105 ColorRGB class, 103, 104 colors, 103-105

background, 23, 25 border, 238-239 classes, 103 combination of, 209 constant, 249 destination, 208, 211 hard addition, 211 material, 216, 249 modulated, 104 particle, 306 previous, 245 primary, 243-244, 245 saturation, 211 shadow, 456 soft addition, 211 source, 208, 211 texture, 245 vertex, 288

Command class, 603-605 constructor, 605 defined, 603 interface, 604-605

command line parsing, 605-607 comment separators, 680-681 ComparesFavorably function,

207, 212 comparison operators, 69

color, 104 sorting support, 69

complicated scenes, 27 ComputeFromData method, 183 Compute function, 500 ComputeLightVectors function,

function, 365-366 conditionals, 684-685 ConsoleApplication class,

609-612 defined, 609 derived class, 610 example, 610-612 interface, 609 Main function, 610 Run function, 610

console applications, 609-612 constants

mathematical, 55-57 register component use, 469 shader, 467, 470 state, 467, 469, 470 storage, 469 user-defined, 467, 469

constructors copy, 80, 120 default, 80, 90, 171, 211 initializers, 683 See also specific constructors

continuous LOD, 309-311 decrease, 324, 331 defined, 300 dynamic change, 322-325,

331 fast algorithm, 310-311 heap initialization, 312-317 increase, 331 remove and update

operations, 317-322 reordering vertices, 326 simple algorithm, 310 source supporting, 331-334 terrain algorithm, 378

326-330

See also level of detail (LOD) Controller class

defined, 399 interface, 399-400

controllers, 121 animation support through,

158, 592 base class, 399 defined, 399 index, 159 inverse kinematic, 158, 415,

427-429 keyframe, 158, 402, 414 management, 399 morphing, 192, 404-406 object management, 121 particles, 408-410 pointers, 128, 131 points, 406-408 repeat type, 401 semantics, 159 skin, 192 updates, 192, 401 uses, 121 vertex, 158-159

controller time application time conversion,

402 clamp type, 401 modifications, 401 repeat type, 401 scale, 401 wrap type, 401

convex function, 494 convex objects, 491 convex polyhedra, 309, 343

infinite, 524 semi-infinite, 522

ConvexRegion class, 348349

constructor, 349 interface, 348

346-347

interface, 346 role, 347

convex regions, 347, 349, 656

drawing routine for, 350 manager, 350, 656

coordinate axes, 4, 9 coordinate frame, 622 coordinate systems

camera, 9 defined, 259-260 independent, 154 lights, 229 matrix mode and, 12 normalized, 630 storage, 264 trackball, 629

CopyFrom function, 183, 184 Copy function, 134 core classes, 28 core systems, 28, 31-147

low-level, 31-53 mathematics, 53-105 object, 105-147

cosine function, 59-60 counterclockwise rotation, 76,

77 CreateBspTree function, 659 CreateClodMesh class, 368

collapsing records with, 333 defined, 331 interface, 331 source code, 332

Create function, 182 CreateModelBound function, 545 CreateModel function, 21-22 CreateScene function, 652, 654 cubic environment mapping,

447 cubic polynomial curves, 97,

98, 99 Culled function, 271, 272, 273

in adjacent regions, 345 back-face, 354 bounding volumes for,

178-180 defined, 219, 259 direction, reversing, 461 disabling, 220 objects, 261, 270-275 occlusion, 343, 345 plane-at-a-time, 178-179,

261 planes, 353 state, 644 triangle, 219 See also global states

CullState class, 219-220 CurveInfo class, 370 curve masses, 580-583

illustrated, 581 representation, 580 sample application, 583 See also masses

CurveMesh class, 367-369 Boolean flag, 369 constructor, 367 interface, 367 sample application, 377 vertex attribute construction

information, 368 curve meshes, 361 curves

Be´zier, 370 curvature, 363 defined, 361 dynamic updates, 370 parametric, 361, 362-364 patch boundary, 361 as path for cameras, 363 tessellation by subdivision,

366-373 torsion, 363

CurveSegment class, 362-364 defined, 362

interface, 362-363 cyclic coordinate descent

(CCD) algorithm, 418, 428

iterations, 428 loop, 428-429 Update function and, 428

D DarkMapEffect class, 436 dark maps, 436

defined, 436 illustrated, 438

data management, 27 data structures, 33-45

arrays, 33-35 hash sets, 38-39 hash tables, 35-37 lists, 39-41 sets, 41-43 stacks, 43-44 strings, 44-45

Deallocate function, 585, 589 debugging, 106 decompositions

Euler angle, 101 for picking, 533 polar, 168-169 singular value, 168, 169

DecrementReferences function, 115, 117, 118

deferred drawing, 356-360 data members manipulation,

356-358 disabling, 356, 358 enabling, 356 functions, 358 functions, implementing,

359 with no drawing, 360 with no sorting, 360

deformable bodies, 591-592 degrees of freedom, 417-418 degrees to radians, 56 depth buffering, 203, 206-208,

354 aspects, 206 defined, 206 disabling, 214, 343 enabling, 214 using, 208 See also global states

Derived class, 64 derived classes, 278 DetachChildAt function, 163 DetachChild function, 163 DetachOutside function, 347 determinant

computation, 82 evaluation, 72 formal, 72

Determinant function, 82 diagonal matrices, 168, 169 differential equations

Euler’s method, 565, 566, 567-569

implicit equations and, 573-575

midpoint method, 569570

numerical methods for solving, 565-575

for particles, 580-581 Runge-Kutta fourth-order

method, 571-572 second-order system, 576

diffuse light, 223 Direct3D, 16, 149

pre-/postdraw semantics, 281

renderers for, 149, 150 working in, 277

directed acyclic graph (DAG), 164, 165

defined, 223 diffuse modulator, 227 direction, 224 orientation change, 224 unit-length direction, 227 See also lights

DisableColorRGBAs function, 289

DisableColorRGBs function, 289 DisableLight function, 287 DisableTexture function, 290,

291 DisableVertices function, 288 discrete LOD, 306-309

defined, 300, 306 See also level of detail (LOD)

DisplayBackBuffer function, 280

distance calculations, abstract

interface for, 497-500 calculators, 492 function, 492 measure computation, 492 between moving objects, 495 pseudosigned, 494 signed, 492, 494 squared function, 493, 494 time-varying function, 492

distance-based methods, 492-500

complexity, 490 defined, 489 plan of attack, 495-496 root finding (bisection),

496-497 root finding (hybrid), 497 root finding (Newton’s

method), 496 skepticism, 490 See also collision detection

Distance class, 497-500 defined, 497 interface, 497-500

distant terrain assumption,

381-382 dithering, 221-222

defined, 221 example, 222 pattern, 222 See also global states

DitherState class, 222 divergence theorem, 600 DlodNode class, 308-309 DoIntersectionQuery function,

537 DoPick function, 531, 532-533 DoProcessQuery function, 538,

539 dot3 bump mapping, 441, 445

defined, 441 illustrated, 446 support, 443

DotPerp function, 72 dot perp operation, 72 dot product implementation,

96 double-buffered drawing, 279 DrawDeferredNoDraw function,

358 DrawDeferredNoSort function,

358 DrawElements function, 292 DrawEnvironmentMap function,

250, 448-449 Draw function, 278, 281, 283

BspNode class, 339 ConvexRegionManager class,

347 Node class, 296-297 Portal class, 351 pure virtual, 283 Renderer class, 358

DrawGlobalFeature function, 298

drawing to back-buffer, 282 complicated scenes, 27

double-buffered, 7, 279 single-pass, 281-284 traversal, 283-284 triangle meshes, 17-26 triangles, 2-17

DrawIt function, 11, 22, 24, 602 DrawPlanarReflection

function, 459-460 DrawPlanarShadow function,

455, 456 DrawPrimitive function,

285-292, 359-360, 478, 482

defined, 285 drawing, 292 global state, setting, 286 lighting, enabling/disabling,

286 operations order, 285 texture units, 289-290 transformation matrix,

restoring, 291 transformation matrix,

setting, 285 vertex colors, 288 vertex normals, 288 vertices, 187-188

DrawProjectedTexture function, 452

DrawScene function, 281, 282 DrawShader function, 482 DxRenderer class, 277 dynamic-link libraries (DLLs),

46, 68 dynamic typecast, 110-111

caller, 111 defined, 105

E edge arrays, 323, 324, 326 Edge class, 371 edge collapses

defined, 326

edge keep vertices, 326, 327 mesh folding on itself result,

329 operation support, 328 pseudocode, 329-330 records, 330, 331 sequence of, 328 throw vertices, 326, 327 triangles deleted by, 331

edges bubble, 330 deletion, 330 infinite weights, 327 insertion, 330

Effect class, 296 defined, 231, 431 encapsulation, 249 function pointer data

member, 250 interface, 250, 431-432 objects, 432 vertex colors storage, 250

effects, 248-251 advanced, 284 global, 249, 250, 284 local, 296 multitexturing and, 250 system, 248 See also renderer state

eigendecomposition, 83, 86 EigenDecomposition method,

83 eigenvalues, 83 eigenvectors, 83 EnableColorRGBAs function, 289 EnableColorRGBs function, 289 EnableLight function, 287 EnableTexture function,

289-290, 291, 449, 452 EnableVertices function, 288 EndianCopy functions, 47 endian order, 46 EndScene function, 281, 282

447-448 constructor, 448 defined, 447 interface, 447 objects, attaching, 448, 449

environment-mapped, bumpmapped, iridescent (EMBMI) clouds, 151, 152

environment mapped model, 360

environment mapping, 240, 242, 432

cubic, 447 sphere, 447

environment maps, 446-450 defined, 446 reflection vector, 447 sample application, 449 sample screen shots, 450 view direction, 446

Euler angles, 86, 414, 418, 427 decompositions, 101 order of, 427

Euler’s method approximation, 565 defined, 565 forward finite difference, 573 implementation, 567-568 as prototype, 566

even blocks, 382 event callbacks, 615-616

key, 617 mouse, 618, 634-635 OnIdle, 619, 628, 635 OnInitialize, 616-617, 618,

640-641, 691 OnMotion, 629, 635 OnMouseClick, 629, 634-635 OnMove, 617 OnPrecreate, 616, 618 OnTerminate, 617 Response, 652

ExcessArguments method, 605 executables (EXEs), 68 ExternalAcceleration

function, 586, 589, 591

performance issues, 170 prototype, 87

Factory function, 126 far plane, 259 filenames, 605 files

cpp, 680 extensions, 677 handling, 48-49 header, 677, 679, 692-698 inline, 678 naming, 677-678 organization, 679 source, 677

file-static data, 140, 141 file-static pointers, 140 filtering

bilinear, 234 with multiple images,

234-237 with single images, 232-234

FindIntersection function, 551, 552, 553

find-intersection queries, 488 with clipping methods,

517-518 collision records, 550 dynamic, 550-551 line-sphere intersection, 509 line-triangle intersection,

506-507 picking, 531 ray-sphere intersection,

511-513

516-517

static, 550 Find method, 502 finite difference, 573 fixed-function pipeline, 431

defined, 30 special effects with, 431-562

fixed-function pipelines, 149 flat shading, 222 flickering, 356 floating-point numbers, 66, 75 fog, 217-218

calculation, 217 class, 217 density, 217 exponential, 218 factor, 218 squared exponential, 218 See also global states

FogState class, 217 forward finite difference, 573 frame rate, 635, 636 Frenet frame, 363, 364 Frenet-Serret equations, 363 FromEulerAnglesUVW method,

86 front-facing triangles, 219, 220 frustum

settings, 9 view, 3, 179, 259, 265-268

frustum planes, 260, 261 bottom, 262 bounding volume inside,

271 equations, 262 far, 259, 262 left, 262 near, 259, 261, 262 normals, 178 right, 262 storage, 353 top, 262

Function function, 597

declarators, 682-683 names, 690 pointers, 250 See also specific functions

304 GenerateColorRGBs function,

304, 305-306 GenerateOrthonormalBasis

function, 73, 74, 75 GenerateParticles function,

303 GenerateUVs function, 304 geometric operations, 70-75 geometric state, 166-196

bounding volumes, 177-184 current, 307 transformations, 167-177 updates, 307, 338

geometric types, 196-203 implementation, 196 line segments, 198-200 particles, 202-203 points, 197-198 triangle meshes, 200-202

geometric updates, 184-196 defined, 184 with geometric quantities

change, 195 Geometry interface, 187-188 illustrated, 189 Node member functions, 188 of scene graph, 189 scene hierarchy, 195 as side effects, 194 Spatial interface data

members, 184-185 Geometry class, 152, 153, 159

enumerations for geometric types, 196

184-196

global states storage, 205 interrelationships, 153 lights support, 230 motivation, 154 objects, 160 render state updates and,

251-259 geometry objects, 156-157

as leaf nodes, 160 special effects application,

158 GetAllObjectsByID function,

114 GetAttributes function, 369 GetAxis function, 422 GetBinormal function, 364 GetChild function, 163 GetClosest function, 500 GetColumnMajor function, 81 GetContactTime function, 500 GetContainingRegion function,

347 GetContrastImage function, 479 GetControlTime function, 402 GetCoordinates function, 585 GetDiskUsed function, 123, 129,

133 GetEffectorPosition function,

416 GetElements function, 42 GetFrame function, 364 Get function, 500 GetGlobalStateType function,

206 GetHeight function, 388 GetID function, 293 GetIndex function, 585 GetIntermediate function, 99 GetKeyInfo function, 404, 406 GetLastError function, 605 GetLight function, 230 GetLightQuantity function, 230

GetMemoryUsed function, 123,

126 GetName function, 112 GetNormal function, 364 GetObjectByID function, 114 GetObjectByName function, 114 GetObjectCount function, 123 getopt routines, 603 GetParent function, 162 GetQuantity function, 198 GetRandomImage function, 479 GetReferences function, 114 GetShaderType function, 473 GetSigned function, 500 GetSquared function, 500 GetTangent function, 364 GetTargetPosition function,

416 GetTime function, 635, 636 GetTop method, 44 GetTriangleQuantity function,

201 GetType function, 107, 108, 464,

475 GetUVs function, 388 GetWorldTriangle function, 457 gimbal locks, 87 glActiveTextureARB function,

function, 19 glDrawElements function, 23 GLEW, 17 glFrustum function, 266 glLookAt function, 12 global arrays, 141 global effects, 249, 250, 284, 296

multipass support and, 295-298

Renderer function, 298 GlobalState class, 204, 205 global states, 203-223, 641

alpha blending, 203-204, 208-215

attaching cameras to, 263 Boolean data members, 286 culling, 219-221 defined, 203 depth buffering, 203,

206-208 derived classes, 206 dithering, 221-222 fast access, 204 fog, 217-218 list of, 258 materials, 216 pointers, 205 shading, 222-223 storage, 205, 259 types of, 203 wireframes, 221

GlossMapEffect class, 437-439 constructor, 439 defined, 437 interface, 438 objects, attaching, 439 virtual function pointer

assignment, 439 gloss maps, 437-440

defined, 437 implementation, 439 sample application, 440

glPopMatrix function, 13 glTexEnvi function, 25 gluLookAt function, 9 gluPerspective function, 266 GlutRenderer class, 277 glVertexPointer function, 23 goals, 415-416

array, 417 defined, 415 end effector, 424 influence, 416 minimization of distances,

420 primary, 415 secondary, 415

types of, weights, 420

Gouraud shading, 222 Gram-Schmidt orthonormal-

ization applying, to columns, 83 defined, 72 implementation, 72-73 Orthonormalize use, 74

graphics APIs, 27, 28 graphics processing units

(GPUs), 158, 299 graphs

abstract, 122 nodes, 122 scene, 122, 126-133, 150,

299-429 greedy algorithms, 194 grouping nodes, 160, 161 GrowToContain function, 183,

H hard addition, 211

defined, 437 light maps with, 438

hash function default, 36 evaluation, 36, 38

hash sets, 38-39 element insertion, 38 iteration, 38-39

hash tables, 35-37 class, 35 item visitation, 37 iterations, 37 key-value pair removal, 36 time requirement, 35

HasMultipleClosestPoints function, 500

header files compilation time,

minimizing, 695-698 extension, 677

nested, 692-694 organization, 692-698 organization guidelines,

695-698 strong organization, 696

heap after changing weight,

swapping, changing weight, 323

after changing weights, 320 after changing weights and

swapping, 321 after moving and swapping,

321, 322 array, after removing

contents, 319 array, after swapping, 313,

314, 315, 316, 317, 318 array, initial values, 313 contents, 319 implementation, 329 index, 311 initialization, 312-317 invalid, 319, 320, 321 last node, 320 mini, 311, 312 records, 312 removing minimum element

from, 317 state, 321 update, 330

height fields automatic generation, 378 defined, 377, 379 level-of-detail algorithms,

378 on sampled grid, 378 over rectangular grid, 378 page in, 384 semiautomatic generation,

378 hierarchical collision detection,

540-553 collision query support, 542

sample application, 553 tree construction support,

542 triangle-triangle intersection

queries, 550-551 See also collision detection

hints defined, 171 flags, 176 setting, 172

Hooke’s law, 583, 589 hybrid root finding, 497

I identifier names, 688-691

classes and functions, 690 enumerations, 690-691 variables, 688-689

identity matrix, 5, 76 idle loops, 626

callback, 281-282 defined, 10

IKController class, 592 defined, 415 interface, 427-428

IKGoal class, 415-416 constructor, 416 defined, 415 interface, 415-416

IKJoint class, 415-417 defined, 415 interface, 416-417 objects, 428 UpdateLocalR function, 422,

425-427 UpdateLocalT function,

420-422 implicit equations, 573-575 in-betweeners, 402 include guards, 692, 693, 694 IncrementalReferences

function, 114-115 index controllers, 159

indices, 154

adjacent, 589 edge, 322, 323 heap, 311 mapping, 325 triangle, 330 vertex, 312 vertex, deleted, 330

inertia tensor complexity, 600 computing, 600 rigid bodies, 593 in world coordinates, 593

infinite LOD, 300, 334-335 obtaining, 334 subdivisions of rectangle

domain, 335 subdivisions of triangle

domain, 335 See also level of detail (LOD)

initialization, 139-147 C-style, 140 dynamic, 142 function additions, 143 function call, 143 function registration, 142 order, 147 pre-main, 139, 142, 146 services, 146 static function, 141

InitializeFactory function, 126

Initialize function, 144, 562

InitializeObjectMotion function, 627

initializers adding, 143 array, 144 calling, 147 execution, 144

instances, 163 management, 165 multiple, 165

defined, 163 of models, 166

integers, 605, 687 interpolation

bilinear, 24, 233, 235, 240, 388

linear, 404 nearest-neighbor, 25, 234 quaternions, 95-101 sequence of unit-length

quaternions, 98 spherical linear, 95 spherical quadrangle, 96-97 triangle meshes, 24, 25 trilinear, 236, 237, 452

intersecting boxes, 561-563 outline, 561 sample application, 563 system implementation,

561-562 IntersectingBoxes class

defined, 561 interface, 561-562

intersection-based methods, 500-503

abstract interface, 501-503 algorithm design/

implementation, 490 defined, 488-489 See also collision detection

intersections convex objects and, 491 intervals, 555-560 linear components and

bounding volumes, 508-527

linear components and OBBs, 517-527

linear components and spheres, 508-517

linear components and triangles, 503-507

line-OBB, 520-522

line-plane, 490 line-sphere, 508-509 nonconvex objects and, 491 object-object, 536-563 ray-OBB, 522-524 ray-sphere, 510-513 rectangles, 560 segment-OBB, 524-527 segments of, 494 segment-sphere, 513-517 two cylinders, 554 two triangles, 501

Intersector class, 501-502 IntervalRandom function, 57 intervals

active, 555 intersecting, 555-560 nonoverlapping, 558 overlapping, 558, 560 reported, 556 sorted, end points, 555, 556

IntrLine3Box3 class, 521-522 IntrLine3Sphere3 class,

508-509 defined, 508 find-intersection query, 509 test-intersection query,

508-509 IntrLine3Triangle3 class, 507 IntrRay3Box3 class, 523-524 IntrRay3Sphere3 class, 511-513

defined, 511 find-intersection query,

511-513 test-intersection query, 511

IntrRay3Triangle3 class, 507 IntrSegment3Box3 class,

526-527 IntrSegment3Sphere3 class,

515-517 defined, 515 find-intersection query,

516-517

507 IntrTriangle3Triangle3 class,

550 inverse kinematic controllers,

158, 415, 427-429 inverse kinematics (IK),

414-429 algorithms, 414 goals, 415-416 joints, 415, 416-427 sample application, 429 system, 415 system illustration, 415, 416

inverse mass, 597 inverse permutation, 326 inverse transformations, 13,

169, 175 computation, 175 implementation, 176-177 rotation, 175 scale, 175 translation, 175 See also transformations

InvSqrt function, 54 IsDerived function, 107 IsEmpty method, 44 IsExactly function, 106 IsFull method, 44

angles, 414 constraining, 418 defined, 415 local transformations,

update, 422 management, 418 motion, 428 position, 419 rotation, 417, 418 transformation, 417

key events, 617 keyframe animation, 402-404

defined, 402 sample application, 404 support class, 402-403

KeyframeController class, 402-403

defined, 402 interface, 402-403

keyframe controllers, 158, 414 keyframes

defined, 402 times, 406 weights as, 404

key-value pair, 36, 37

L Laplace expansion theorem, 82 leaf nodes, 160, 161, 189

bounding volume tree, 540 BSP tree, 343 recomputing, 189 render state at, 252 in scene hierarchy, 213

level of detail (LOD), 299-335 billboards, 299-302 categories, 299-300 continuous, 300, 309-334 discrete, 300, 306-309 dynamic change, 322-325,

331 infinite, 300, 334-335 terrain, 378-388 terrain pages, 389

Light class, 224, 225-229 interface, 225, 228-229 light support, 225

lighting, 223 color computation due to,

440 diffuse, 216 enabling/disabling, 286-287 models, 223

LightMapEffect class, 437 light maps, 437

defined, 437 with hard addition, 438 with soft addition, 437

lights, 223-230 adding/removing from list,

230 ambient, 223, 227 ambient contribution, 226 array of, 230 attenuation factor, 225-226 coordinate system, 229 creating, 225 diffuse, 223 diffuse contribution, 226 directional, 223, 224, 227,

457 incorrect use of, 224 intensity factor, 226 list of, 258 physical attributes, 223 point, 224, 227 smart pointers to, 230 specular, 223 specular contribution,

226 spot, 22, 224, 227 support for, 229-230 turning on/off, 225 types, 223

light vectors, 440-441 computing, 445 generating, 441-442 point lights, 445 spot lights, 445

LightWave left-handed coordinates, 263

LightWave objects, 224 linear complementarity

problems (LCPs), 600 linear components, 491

intersection with bounding volumes, 508-527

517-527

intersection with spheres, 508-517

intersection with triangles, 503-507

See also specific types of components

linear interpolation, 404 linear momentum, 592,

593-594 linear velocity, 594 line loops, 197 line-OBB intersection, 520-522

illustrated, 520 Minkowski difference, 520 picking, 527-534 separation tests, 521

line-object intersection, 503-536

linear components and bounding volumes, 508-527

linear components and triangles, 503-507

See also intersections lines, 102

distance to point, 102 intersection with spheres,

508-509 line segments, 196, 198-200

collection of, 196, 198 disjoint, 200 end points, 199, 200 See also geometric types

line strips, 197 linkers, 142 Link function, 126, 132 link IDs

accessing, 133 defined, 130

lists, 39-41 construction support, 39 deleting, 40 need, 39

lists node allocation, 40 node counting, 40 node insertion, 41 node removal, 40-41 node search, 41

Load function, 48, 126, 130, 131 local coordinate axes, 623 local effects, 296 local transformations, 155, 156

as homogeneous matrices, 168

joint, 422 See also transformations

logarithmic function, 98 LookDown function, 625 LookUp function, 625 loops

CCD algorithm, 428-429 idle, 10, 281-282, 626 line, 197 starting, 9-10

low-level system, 31-53 data structures, 33-45 endianness, 46-47 file handling, 48-49 memory allocation/

deallocation, 49-53 platform-specific

encapsulation, 45-46 system time, 47 See also core systems

M magnification, 234 Main function, 608-609, 612,

method, 88 MakePerspectiveProjection

method, 89 MakeReflection method, 89-90 manifold mesh, 361

maps

bump, 440-446 dark, 436 environment, 446-450 gloss, 437-440 light, 437 normal, 440, 444

masses accessing, 585, 589 boundary, 588-589 center of, 600 computing, 600 corner, 589 curve, 580-583 edge, 589 face, 589 inverse, 597 surface, 583-586 times linear velocity, 593-594 volume, 586-589

mass matrix, 593-594 MassSpringArbitrary class,

590-591 constructor, 591 defined, 590 interface, 590 use illustration, 591

MassSpringCurve class, 581-582 Acceleration function

implementation, 582 defined, 581 interface, 581 use illustration, 586

MassSpringSurface class, 584-586

defined, 584 interface, 584-585 use illustration, 586

mass-spring systems, 580-591 arbitrary configurations,

589-591 curve masses, 580-583 number of particles in, 582

spring 589

surface masses, 583-586 volume masses, 586-589

MassSpringVolume class, 587-589

defined, 587 interface, 587-588 use illustration, 589

materials, 216 colors, 216, 249 specular highlights, 216

MaterialState class, 216 mathematics functions, 53-61

alternate versions, 55 basic, 53-57 constants, 55-57 cosine, 59 fast, 57-61 FastCos0, 58 FastInvCos0, 59 FastInvCos1, 60 FastInvSin0, 59 FastInvSin1, 59 FastInvSqrt, 60 FastInvTan0, 60 FastInvTan1, 60 FastSin1, 58 FastTan0, 59 FastTan1, 59 forms, 54 IntervalRandom, 57 InvSqrt, 54 Sign, 57 sine, 55, 58 Sqr, 54 SymmetricRandom, 57 tangent, 60 trigonometric, 57-61 UnitRandom, 57

mathematics system, 53-105 colors, 103-105 fast functions, 57-61 functions, 53-57

matrices, 75-90 planes, 102-103 quaternions, 90-102 vectors, 61-75 See also core systems

matrices, 75-90 adjoint, 82 arithmetic operations, 81 assignment operators, 80 classes, 78 common operations, 78-80 comparison, 81 constructors, 80 conventions, 14, 75-78 creation, 80 data, transferring, 81 diagonal, 168, 169 eigendecomposition, 83 eigenvalues, 83 eigenvectors, 83 handling, 23 homogeneous, 174 identity, 5, 76 inversion, 169 invertible, 82 mass, 593 member access, 80-81 memory layout, 75 operation application, 76 operations specific to 2D,

82-84 operations specific to 3D,

85-88 operations specific to 4D,

88-90 orientation, 594 orthogonal, 169 products, 81 projection, 457 reflection, 460 rotation, 4, 5, 14, 76 skew-symmetric, 76 square, 75, 82

trace, 86 typecast, 75

Matrix3 class, 595 matrix-matrix operation, 75 matrix-vector operation, 75 Maya exporter, 673 MeasureTime function, 635-

636 defined, 635 implementation, 636

member access by array brackets, 68 matrices, 80-81 named, 69 vectors, 68-69

memory allocation, 49-53 deallocation, 49-53, 140 footprint, 123 increasing usage, 13 leaks, 140 management, 388-399 streaming, 124-125 terrain page use, 388

memory layout matrices, 75 vectors, 61-67

mesh classes, 32 message pump, 9-10 midpoint method

class interface, 569-570 defined, 569 mathematical formulation,

569 minification, 235 Minkowski difference

defined, 518 illustrated, 519 line-OBB, 520 ray-OBB, 522 segment-OBB, 524 in three dimensions, 520

Minkowski sum, 518, 519

algorithms, 236 application of, 235 defined, 235

model bounding sphere computing world bounding

sphere from, 172 transformation, 172-173

models bound, 154 bounding volume, 188 camera, 259-276 environment mapped, 360 instancing of, 166 multitexture mapped, 360 normals, 154 scale, 154 vertices, 154

model-to-world transformation, 13, 338

modifiers, 159 modular continuity, 185 MorphController class, 591

defined, 404 interface, 404-405

morphing, 404-406, 534 defined, 404 sample application, 406 weight arrays for, 404

motion camera, 622-627 control, 399 object, 621-622, 627-635 trackball, 631

mouse events, 618 MoveBackward function, 623,

624 MoveCamera function, 626 MoveDown function, 624 MoveForward function, 535, 623 MoveObject function, 628-629 MoveUp function, 624 moving objects, 488

distance computation, 495

test-/find-intersection

queries for, 503 MsCreateRenderer function,

619-620 multiple-inheritance systems,

111 multiplication, 91-92 multitexture mapped model,

360 multitexturing, 242-248

blending equations, 246 defined, 242 effects and, 250 multipass, 250 single-pass, 250 See also renderer state

MyConsoleApplication class, 610-612

defined, 610 order of events, 611-

612 source file, 611

MyFunction function, 120 MyWindowApplication class,

613-614 defined, 613 interface, 613-614

N n×m arrays, 14 namespaces, 106 name strings, 112 nearest-neighbor interpolation,

25, 234 near plane, 259 Newton’s method, 573,

574 Node class, 152, 153, 531

Draw function, 296-297 encapsulation, 184 geometric updates and,

184-196 interrelationships, 153

render state updates and,

251-259 nodes

BSP, 337 child, 163 end effectors, 415 grouping, 160, 161 leaf, 160, 161, 189, 213, 343 linear list of, 257 local transformation

modification, 157 rectangular boxes, 189 states, 257 subgraph of, 166 switch, 300, 306 Utensil Group, 161

nonuniform scaling, 167 diagonal matrix, 168 nonsupport, 169

normalized viewport coordinates, 528

Normalize function, 71, 100 normal map, 440, 444 null pointers, 256 numerical minimizer, 495 numerical root finders, 494 NURBS surfaces, 362

O OBB trees, 542 Object class, 108, 110

hierarchy, 135 name strings, 112 reference counter, 114 streaming support, 125-126 unique identifiers, 113-114

object culling, 178-180, 270-275

additional planes, 274 bounding volume straddling

plane, 273 force-culled, 271 planes, 274

See also object-object intersection,

536-563 collision groups, 536-540 hierarchical collision

detection, 540-553 spatial/temporal coherence,

553-563 See also intersections

objects, 150 calling, 73 in collision groups, 536 convex, 491 copied, 137 copying, 133-137 degrees of freedom, 417-418 dynamically allocated, 115 extra spins, 96 geometry, 156-157, 158 grouping, 156 hierarchy, 155-156 instances, 163-166 linear component, 491 link, 131 link order, 133 links between, 130 loading, 130 loading, from disk, 45 management, 121 memory address, 130 motion, 621, 627-635 moving, 488 nonvisible, 84 OBB containing, 84 pointers as, 686 registration, 126, 127 rotation, 621-622 semitransparent, 213, 214 sharing, 114 sorting, 335-360 stationary, 487-488 texture, 435 top-level, 122, 123, 129 velocities, 500 in view volume, 259

cloning, 133-137 controllers, 121 initialization and

termination, 139-147 name strings, 112 run-time type information,

105-111 sharing and smart pointers,

114-120 streaming, 122-133 string trees, 138-139 unique identification,

113-114 See also core systems

odd blocks, 382 OdeEuler class, 567-569

defined, 567 implementation, 567-568 sample illustration, 568-569

OdeImplicitEuler class, 574-575

defined, 574 interface, 574-575 update function, 575

OdeMidpoint class, 569-570 defined, 569 interface, 569-570 update method, 570

OdeRungeKutta4 class, 571-572 defined, 571 interface, 571-572 update function, 572

OdeSolver class, 566 OnDisplay method, 617 OnDraw function, 283, 284, 296 OnDynamicChange method, 370 OnFrameChange function, 264,

265 OnFrustumChange function, 266 OnViewPortChange function,

268 open-closed principle, 159 OpenGL, 3, 149

calls, replacing, 16

with, 7

Extension Wrangler Library, 17

matrix convention, 14 pre-/postdraw semantics

and, 281 renderers for, 149, 150 support, 277 versions, 17

OpenGLRenderer class, 276-277 operator[] accessor, 34, 91, 104 organization, this book, 28-30 orientation matrix, 594 oriented bounding boxes

(OBBs), 83 axes, 84 bounding volume hierarchy

of, 84 clipping method, 517-518 component coordinates, 517 component direction,

517-518 intersection with linear

components, 517-527 intersection with lines,

520-522 intersection with rays,

522-524 intersection with segments,

524-527 polygon enclosed by, 84 separating axes method, 518 values, 181 See also bounding volumes

orthogonal matrices, 169 Orthonormalize function, 74,

83, 86 orthonormal set, 489

P parametric curves, 361,

362-364 curvature, 363

as path for cameras, 363 torsion, 363 See also curves

parametric surfaces, 361, 364-366

defined, 364 See also surfaces

parent-child relationship, 155 partial derivatives, computing,

442, 443 ParticleController class,

408-409, 591 defined, 408 interface, 408-409 structure, 409

particle physics, 576-580 particles, 196

attributes, 306 billboard squares for, 304 colors, 306 controller, 408-410 defined, 202 differential equation,

580-581 display of, 302-306 finite mass, 577 forces acting on, 581 location, 202, 203, 303 in mass-spring system, 582 model space of, 303 one-dimensional array, 585 rendering, 304 as rigid bodies, 592 sizes, 203 texture image, 410 world rotation matrix, 303 See also geometric types

Particles class, 202-203, 302-304

defined, 302 interface, 302-303 vertex attributes, 304

ParticleSystem class, 576-577 classes, deriving, 580

ued)

defined, 576 interface, 576-577 template parameters, 576

particle systems class, 576-577 defined, 202, 302 simulation of, 576

patches array, 374 Be´zier, 361 boundary curves, 361 defined, 361 evaluation, 374 querying, 361 rectangle, 361 with rectangular domains,

378 triangle, 361

PeekMessage function, 10 perp operation

defined, 71 dot, 72 perpendicular, 72

physics, 565-600 deformable bodies, 591-592 differential equations,

565-575 mass-spring systems,

580-591 particle, 576-580 rigid bodies, 592-600

picking, 275-276, 527-534 decomposition for, 533 defined, 275, 527 find-intersection query,

531 hierarchical, 530 initiating, 276 pick ray construction and,

528-530 ray, 276 sample applications, 533-534

530-534

system, 534 test-intersection query, 531,

533 pick rays, 527-530

Camera implementation, 528-529

constructing, 528-530 defined, 527 direction, 528, 534 origin, 527, 534

PickRecord class, 531-532 defined, 531 interface, 532 objects, 531

pitch, 87 PixelShader class, 464, 473-474

GetShaderType function implementation, 473

instantiation, 474 interface, 473

pixel shaders, 149 Cg, 470-472 defined, 150, 462 enabling in OpenGL, 483 inputs, 486 prototypical, 462 support implementation,

463 writing, 462 See also shader programs

PlanarReflectionEffect class, 457-459

constructor, 459 defined, 457 interface, 457-458

planar reflections, 249, 295, 457-462

defined, 457 as global effect, 459 illustrated, 462 reflectance setting, 457, 461 sample application, 461

454-455

constructor, 455 defined, 454 interface, 454-455

planar shadows, 454-457 caster, 456 colors, 456 as global effect, 455 illustrated, 458 projected, 454 sample application, 457

plane-at-a-time culling, 178-179

Plane class, 342 planes, 102-103

clipping, 274 constant, 102 culling, 353 frustum, 260, 261, 262, 353 input, 176 light source, 455 maximum number of, 353 negative side, 103 output, 176 perpendicular, 274 popping, 274 positive side, 103 pushing, 274 reflecting, 460 removing, 353 signed distance to, 103 transformation of, 175

PointAngularAxis function, 408 PointAngularSpeed function,

408 PointController class, 406-

407, 591 defined, 406 interface, 407

pointers controller, 128, 131, 406-408 disk, 130 file-static, 140

global state, 205 null, 256 as objects, 686 parent, 162 parent, lookups, 165 smart, 114-120, 230 types, 686-688

point lights defined, 224 direction change, 224 light vector, 445 unit-length vector, 227

PointLinearAxis function, 408 PointLinearSpeed function, 408 points, 196, 197-198

collection of, 196, 197 curve, 368 end, 199, 200 index array, 198 shared, 200 umbilic, 366 See also geometric types

point systems defined, 407 illustrated, 410 motion update, 410 nonrigid, 408 origin, 407-408

polar decomposition, 168-169 polygons

adjective, 361 convex, 349 portal, 345, 354 screen space, 291, 662-667 vertex collapses for, 325 vertices, 345

polyhedra convex, 309, 343, 491 touching, 501

polylines closed, 197, 200, 309,

322-323, 324 generation, 360 open, 196, 200, 309, 322, 324

reduced, vertices, 310 variation of, 309 vertex colors, 368 of vertices, 580

polymorphism, 118 polynomial curves, 310 PopState function, 252 Portal class, 348-349

constructor, 349, 351 defined, 344 interface, 348-349

portals, 343-354 bidirectional, 343 bIgnoreNearPlane variable

and, 354 culling, 352 culling call, 353 defined, 343 drawing code, 351 for generating culling planes,

350 incoming, 344 outgoing, 344, 349, 352 planes, 350, 352 planes, pushing/popping,

352 polygon, 345, 354 in sorting, 344 unidirectional, 343, 345 updating, 349 visibility, 351

previous color, 245-246 primary colors, 243-244, 245 principal curvatures, 365-366 principal directions, 365

computing, 365-366 frames using, 366

PrintInUse function, 115 projected shadows, 249 ProjectedTexture class, 248 ProjectedTextureEffect class,

451-452 constructor, 451-452 defined, 451

projected textures, 240, 242,

432, 451-454 application, 249 defined, 451 illustrated, 455 problem, 248 sample application, 454 See also special effects;

textures projection matrix, 457 projection planes, 89 PropagateStateFromRoot

function, 253, 254, 256 PropagateToRoot function, 187 pseudosigned distance, 494 public interface, 171

convention, 186 exposing data members to,

185 PushState function, 252

Q Qform function, 82 quadratic form, 82 quadratic polynomial graph

configurations ray-sphere intersection, 510 segment-sphere intersection,

513 Quaternion class, 90, 99, 595 quaternions, 90-102

addition, 91, 102 algebraic properties, 91-93 angular velocity, 101 comparison functions, 91 components access, 91 computational costs, 87 default constructor, 90 defined, 90 interpolation, 95-101 member access methods,

90-91 memory, 90

multiplication, 92 multiplicative inverse, 94 physics, 101-102 products, 92 rotations, 93-95 scalar multiplication, 91-92,

102 standard constructors, 90 symbolic representation, 91 typecasting, 90 unit-length, 93, 94 utility, 93

queries collision detection, 487, 540,

542 collision group intersection,

539-540 containment, 347 find-intersection, 488,

506-507, 511-513, 516-517

group intersection, 538 intersection, 184, 501-503 object state change during,

539 patch, 361 renderer, 280 RTTI, 107, 108 test-intersection, 487-488,

501, 505-506, 511, 515 triangle-triangle intersection,

550-551 which-side-of-plane, 178,

function, 47 QueryPerformanceFrequency

function, 47 quick rejection test, 540

R radians to degrees, 56

ray-OBB intersection, 522-524

illustrated, 522 projections, 523 separation tests, 522 test-intersection query,

523-524 rays

intersection with triangles, 504

pick, 527-530 ray-sphere intersection,

510-513 find-intersection query,

511-513 graph configurations, 510 quadratic equation, 511 test-intersection query, 511

reals, 605 rectangle patches, 361 rectangles

axis-aligned, 560 in denoting grouping nodes,

161 intersecting, 560 overlapping, 560 vertices, 6

reentrancy, 295 reference counters, 114

increment/decrement, 114 manipulating, 115

reflections 4 × 4 homogeneous

transformation for, 90 matrix, 460 planar, 249, 295, 457-462 planes, 89

reflection vector, 447 RegisterFactory function,

126 Register function, 126 registers, 469 reindexing, 326 ReleaseShader function, 481

RemoveAllLights function, 230 RemoveAll method, 34 Remove method, 34, 43 Renderer class, 152, 153

deferred drawing interface, 356

defined, 276 enable/disable functions, 481 interface, 277-278, 464, 481 interrelationships, 153 motivation for, 157-158

renderers building, 149 cameras and, 259-298 defined, 149 derived-class, 278 notifying, 294 querying, 280 requirements, 158 vertices and, 157 virtual functions, 278

renderer state, 203-259, 248-251

effects, 248-251 global state, 203-223 at leaf node, 252 lights, 223-230 multitexturing, 242-248 restoration, 457 textures, 230-242 updates, 251-259, 307

rendering advanced topics, 431-486 architecture, 276-280 cameras for, 263 particles, 304 portable layer, 277 reflected object, 461 scene graph management vs.,

150-151 tiled, 267, 268

Reorder function, 332

617 ResetColors function, 654 Response function, 654 RestoreScreenTransformation

function, 291 rigid bodies, 592-600

angular momentum, 593 angular velocity, 593 class, 595-600 defined, 592 immovable, 597 inertia tensor, 593 initializing, 600 linear momentum, 592,

593-594 motion calculations, 592 motion equation, 593 standard representation, 592 unconstrained motion, 592,

594 RigidBody class, 595-600

applications using, 599-600 constructor, 597 defined, 595 Function function, 597 interface, 595-596 Update function, 597-599

ROAM algorithm, 378-379 description, 379 variants, 378-379

roll, 87 root finding

with bisection, 496-497 hybrid, 497 with Newton’s method, 496 numerical, 494

RotateTrackBall function, 630, 631-634

rotation matrices, 4, 5, 171 counterclockwise, 76 interpolation, 87 local, 264

quaternion, 93 representation, 76 rotational slerp, 87-88 rotation definition, 88 unit length quaternions and,

94 update, 14 x-axis, 77 y-axis, 78 z-axis, 78

rotation(s) about right axis, 15-16 about right vector, 623 about up vector, 622 about view direction, 16 angle of, 100, 418, 622 axis, 100 camera, 15 composition of, 90 counterclockwise, 77, 622 incremental, 625-626 inverse transformation, 175 joint, 417, 418 object, 621-622 quaternion, 94 trackball, 630, 634 triangle, 3, 4 twist, 101

round-off errors, 56, 356 Run function, 609, 610 Runge-Kutta methods, 102

defined, 569 fourth-order method,

571-572 midpoint method, 569-570 numerical solver, 582 solver, 577, 580

run-time type information (RTTI), 105-111, 531

caller object, 106, 107 defined, 105 input object, 106, 107 name, 108, 128

single-inheritance class trees,

105-109 static and dynamic

typecasting, 110-111 strings, 130

S sample applications, 637-672

654-656 TestPortals, 656-662 TestScreenPolygon, 662-

668 TestSkinnedBiped, 668-669 TestSoftFaces, 669-670 TestTerrain, 670-672

sample tools, 673-675 Save class, 128 scalar multiplication, 91-92,

102 scale

inverse transformation, 175 nonuniform, 177 uniform, 177

ScaleByMax method, 104, 105 scene graph management, 28

changes and, 151 core, 29 core classes, 28, 152-166 defined, 150 rendering system vs.,

150-151 shader program support,

463-479 sharing, 294 visibility determination, 150

advanced topics, 299-429 defined, 150 deleting, 293 geometric update of, 189 illustrated, 164, 166 loading, 129-133 memory footprint, 123 reconstruction, 129 roots of, 122 saving, 126-129 string trees applied to, 138 written to disk, 129

scene hierarchies leaf nodes, 213 updating need, 195

ScenePrinter tool, 138, 674 scenes

defined, 150 organization, 213 root node, 129 writing memory blocks to,

133 SceneTree tool, 138, 674, 675 SceneViewer tool, 674 ScreenPolygon class, 292 screen space

height, 388 polygons, 291, 292

segment-OBB intersection, 524-527

illustrated, 525 Minkowski difference, 524 projections, 525 separation tests, 525 test-intersection query,

526-527 segments

array, 367 curve, 361 defined, 361 of intersections, 494 intersection with triangles,

quantity, 367 storage during subdivision,

370 tessellated by single line, 366

segment-sphere intersection, 513-517

configuration descriptions, 514

find-intersection query, 516-517

graph configurations, 513 test-intersection query, 515

SelectLevelOfDetail function, 309, 333

self-intersections, preventing, 591

separating axes defined, 518 line-OBB, 521 potential, 518 ray-OBB, 522 segment-OBB, 525

SetActiveQuality function, 198 SetAlphaState function, 286 SetChild function, 163 SetConstantCameraPosition

function, 485 SetConstantFogParams

function, 485 SetConstantLightDiffuse

function, 485-486 SetConstantTransform

function, 486 SetDirection function, 229 SetElement method, 34 SetFrustum method, 266, 267 SetGeometryType function, 199 SetGlobalState function, 286 SetLevel function, 374, 376 SetLight function, 230 SetLocal function, 185 SetMaxQuantity method, 35 SetName function, 112

sets, 41-43

assert-and-repair paradigm, 42

elements insertion, 43 elements modification, 42 elements quantity, 42 elements removal, 43 initial maximum quantity, 42 memory overhead, 41 searching, 43 STL, 41

function, 291 SetTranslate function, 171 SetViewPort function, 528 Shader class, 472-474

architecture, 465 binding mechanism, 479 defined, 464 interface, 472-473, 474 shader program

encapsulation, 472 ShaderConstant class, 467-470

constructor inputs, 476 interface, 468-469 objects, 467, 470, 472 variables, 484

shader constants defined, 467 vertex shader, 470

ShaderEffect class, 477-478 defined, 477 interface, 477-478 objects, 478, 481

shader programs benefits, 462 defined, 462 drawing function support,

481-482 DrawShader function and,

482 encapsulation, 472

as functions, 463 global effects, 478 inputs, 469, 474 low-level, 486 paper texture, 479 pixel shader, 462 renderer support, 479-486 scene graph support,

463-479 support, implementing, 463 text string representation,

474 vertex shader, 462

shaders defined, 30, 149 pixel, 149, 150 vertex, 149-150 writing, 150

ShadeState class, 222-223 shading, 222-223

flat, 222 Gouraud, 222 models, 222 modes, 223 See also global states

shadows caster, 456 colors, 456 planar, 454-457

sharing, 114-120 signed distance

defined, 492 flat spot, 494, 495 function, 494, 495 measure, 494

Sign functions, 57 simplification

algorithms, 396 block, 382-388 terrain, 671 terrain pages, 395-398 vertex, 379-382

Simplify function, 398

fast approximations to, 58 inverse, 59

single-inheritance systems class trees, 105-109 defined, 105 hierarchy illustration, 106

single-pass drawing, 281-284 behavior, 284 with DrawPrimitive function,

285 traversal, 283-284

single textures, 434-435 singular value decomposition,

168, 169 skeleton application code,

637-641 header file, 637-638 OnInitialize callback,

640-641 source file, 638-640 See also applications

skew-symmetric matrix, 76 skin-and-bones. See skinning SkinController class, 411-413,

592 defined, 411 interface, 411-412 Update function, 413

skinning, 404, 410-414 bones, 410-414 data, 414 defined, 410 hardware-based, 414 sample application, 414 skin, 410, 413 software-based, 411 support, 411 update routine, 414

skins defined, 410 world transformation,

413 Slerp function, 88, 96

smart alias, 116 array, 259 assignment to self, 117 comparison, 118 defined, 114 eliminating, 255 as function parameters, 119 implementation warning,

117 to lights, 230 NULL assignment, 119 to texture images, 232 typecast, 118 use guidelines, 119

soft addition, 211 defined, 437 light map using, 438

SortByTexture function, 359 SortedCube class, 669 sorting, 29, 335-360

with BSP trees, 336-343 by texture state, 359 children of nodes, 354-356 coarse-level, 336 deferred drawing and,

356-360 for faces, 355 geometric, 335 portals, 343-354 spatial regions, 336 vertices, 331

source support continuous LOD, 331-334

Spatial class, 152, 153, 158, 160 bounding volumes in, 184 design goal, 160 encapsulation, 184 geometric updates and,

184-196 hierarchical picking, 530 interrelationships, 153 lights support, 229-230 motivation for, 154-155

render state updates and,

251-259 spatial hierarchy design,

160-163 special effects

bump maps, 440-446 dark maps, 436 environment maps, 446-450 with fixed-function pipeline,

431-462 gloss maps, 437-440 light maps, 437 planar reflection, 457-462 planar shadows, 454-457 projected textures, 451-454 renderer support, 479-486 scene graph support,

463-479 single textures, 434-436 with vertex and pixel shaders,

462-486 vertex coloring, 433-434

specular highlights, 223 specular light, 223 SphereBV class, 182, 542

bounding volume, 546 defined, 542 objects, 545 use of, 542

SphereBVTree class defined, 542 pre-main initialization

macros, 545 spheres, 178

bounding, 180 intersection with line,

508-509 intersection with linear

components, 508-517 intersection with ray,

510-513 intersection with segment,

513-517

See also bounding volumes

sphere trees, 542 spherical environment

mapping, 447 spherical linear interpolation,

95 acronym, 96 equation, 96

spherical quadrangle interpolation, 96-97

defined, 96-97 of four quaternions, 97

SplitTriangles function, 546

spot lights angle, 227 defined, 224 direction change, 224 direction vector, 227 light vector, 445 modulator, 227 position, 227 unit-length vector, 227 See also lights

Sqr function, 54 square-distance function, 489,

493, 494 stacks, 43-44

full, 44 iterating over, 44 operations, 44

Standard Template Library (STL), 31, 698

applications using, 68 functionality, 33 maps, 32

state, 28 state constants, 467, 469, 470 static typecast, 110-111

in C-style, 110, 111 safety, 110 using, 110

stencil buffers, 279

code, 390-391 visual anomaly, 399 See also terrain; terrain pages

Stream class, 49, 122, 129, 133 streaming, 122-133

deep copy side effect, 133 defined, 122 disk, 124 memory, 124-125 to memory block, 133 object registration, 126-127 support, 125 to/from disks, 123 typical usage, 124

stream loader, 128 strings, 44-45, 605

names, 134 reading, 44, 45 RTTI, 130 type, 45

Strings class, 44, 45 StringTree class, 138-139 string trees, 138-139

applied to scene graphs, 138 control code, 138 creation, 139 nodes, 139 saving, 139 tools using, 138

Subdivide function, 371, 376 subdivision

adaptive schemes, 372 Boolean results and, 491 curve segment storage, 370 curve tessellation by,

366-373 default level, 368 level, varying, 371 polyline produced by, 368 surfaces, 334 surface tessellation by,

373-377 uniform scheme, 372

subdivision functions, 371, 376 surface masses, 583-586

deformable, 584, 586 illustrated, 583 implementation class,

584-585 representation, 583 sample application, 586

surface mesh code, 376 defined, 361

SurfaceMesh class, 591 defined, 373 interface, 374 sample application, 377

SurfacePatch class, 364-365 surfaces

dynamic changes, 375, 376 locking mechanism, 376 NURBS, 362 parametric, 361, 364-366 subdivision, 334 tessellation by subdivision,

373-377 vertices, 373

SwapBuffers function, 12, 13 swaps, 314, 321

heap arrays after, 314, 315, 316, 317

repeating, 317 sweep algorithm

defined, 555 phase, 556 pseudocode, 556-557 update phase, 559

switching, 308, 309 SwitchNode class, 531 switch nodes

active child support, 308 defined, 300, 306

SymmetricRandom function, 57 System functions, 46-47 system headers, 31, 45-46

function, 60 unit-length, 364 vectors, 97, 99, 363, 364

target records, 333 targets, 406

defined, 404 display in viewport, 534 goals, 415 weighted combination of,

404 TArray class, 42 templates, 53-54

member functions, 52 vector, 67-68

TerminateFactory function, 126 termination, 139-147

function additions, 143 function call, 143 function registration, 142 post-main, 142

terrain, 377-399 algorithm design, 377 camera movement about,

398 clamp-to-edge mechanism,

399 close assumption, 382 data representations,

377-378 distant assumption, 381-382 fold over, 377 as height field, 377 level of detail, 378-388 objects, 29 simplification, 671 tiled, handling, 388 uses, 377 vertex simplification,

379-382

as child nodes, 395 collection, as active set, 395 dependencies, 389 design, 399 invisible, 398 level of detail, 389 management, 391-395 memory management and,

388-399 memory use, 388 numbering, 389 ordering, 389 replacing, 395, 398-399 simplification, 395-398 stitching, 389-391 stitching code, 390-391 subset, 398 texturing issues, 399 toroidal topology, 394 vertex dependences (sharing

column edge), 391 vertex dependences (sharing

row edge), 390 world origin, 388

TestBillboardNode sample, 642-643

defined, 642 scene graph, 642 screen shots, 643

TestBspNode sample, 642-645 defined, 642 illustrated, 645 scene graph, 642-643

TestCachedArray sample, 645-646

TestCastle sample, 646-648 defined, 646 picking system, 646 screen shots (inside), 649 screen shots (outside), 647

TestCharcoalEffect sample, 480, 486

TestClodMesh sample, 648

callback, 653 defined, 648 OnKeyDown function, 650-651 Response function, 650 scene graph structure, 648 Transform function, 651

TestIntersection function, 183, 551, 552, 552-553

test-intersection queries, 487-488

collision records, 548-549 dynamic, 550 line-sphere intersection,

508-509 line-triangle intersection,

505-506 picking, 531, 533 ray-OBB intersection,

523-524 ray-sphere intersection, 511 segment-OBB intersection,

52-67 segment-sphere intersection,

515 separating axes method, 518 static, 550 triangle-triangle pairs, 550 for two ellipsoids, 501

TestInverseKinematics sample, 654-656

defined, 654 IK system encapsulation,

655 implementation, 655 scene graph, 654-655 screen shot, 656

Test method, 502 TestPortals sample, 656-662

environment cross section, 657

indoor environment bounding planes, 658-659

screen shots, 663, 665

assignments, 661-662

wireline views, 664, 666 TestScreenPolygon sample,

662-668 defined, 662 OnIdle loop, 667-668 screen shot, 667

TestSkinnedBiped sample, 668-669

TestSortFaces sample, 669-670 defined, 669 scene graph, 669 screen shot, 670

TestTerrain sample, 670-672 defined, 670 OnIdle callback, 671 screen shots, 672 terrain simplification, 671

texels defined, 234 interpolation at, 238 size, 235

Texture class, 210 blending equation

information, 249 defined, 230-231 interface, 231, 235-236, 240-

241, 242-243, 249-250, 292-293

texture coordinates, 22, 231, 479

arrays, 24, 231 automatic generation of,

240-242 computation, 447 cylinders, 654 at image boundaries, 238 interpolated, 232 out-of-range, 238-240 with sphere mapping, 447

TextureEffect class, 434-435 defined, 434 interface, 434-435

sample texture images, 231, 393, 440

affine drawing, 232 draw control, 232 filtering with, 232-237 magnification, 234 numbering scheme, 394 particle, 410 perspective-correct drawing,

232 projection type, 232 samples, 234 smart pointer to, 232

textures, 17, 230-242 alpha channel, 439 apply mode, 242 artifacts, 234 binding, 295 blending, 242 bound to graphics card, 292 bump maps, 440-446 cached, 292-295 checkerboard, 233 color, 245 dark maps, 436 decal, 215 deleting, 293 environment maps, 446-450 global effect, 448, 449 gloss maps, 437-440 information, 24 light maps, 437 loading, 21 objects, 435 primary, 26, 242 projected, 240, 242, 248, 249,

451-454 secondary, 25, 242, 248 single, 434-435 soft addition, 211 state, sorting by, 359 sunfire, 454 toggle, 20 unbinding, 294

TextureState class, 248, 249 texture units, 24

configuring, 248 different numbers of,

290-291 disabling, 26, 289-290 enabling, 289-290

THashSet class, 38 THashTable class, 35 three-dimensional arrays,

51-53 allocation/deallocation,

51-53 storage, 51

3D Game Engine Design (3DGED), 1

3D picking, 180 3DsToWmof importer, 673 tiled rendering, 267, 268 tiled terrain, 388 TimesTranspose function, 81 time-varying distance function,

492 TList class, 39, 40 ToAngle method, 83 ToAxisAngle method, 86 ToEulerAnglesUVW method, 86 tools, sample, 673-675

BmpToWmif converter, 673 Maya exporter, 673 ScenePrinter, 674 SceneTree, 674, 675 SceneViewer, 674 3DsToWmof importer, 673 WmifToBmp converter, 674

trackballs coordinate system, 629 motion, 631 projection, 630 rotation, 630, 634 virtual, 629, 630

Transformation class, 339

4 × 4 homogeneous, 89 affine, 167 algebraic operations for, 173 bounds relationship, 157 homogeneous, 174-175 identity, 173 inverse, 13, 169, 175,

176-177, 339 joint, 417 local, 155, 156, 157, 168, 422 model bounding sphere,

172-173 model-to-world, 13, 183, 338 of planes, 175 propagation, 156 restoring, 291 setting, 291 similarity, 631 support, 167 world, 155, 156, 164,

169-170, 186 translation

inverse transformation, 175 in right direction, 622 in up direction, 622 in view direction, 622

Transpose function, 81 TransposeTimes function, 81 trees

bounding volume, 540, 542, 546

BSP, 336-343 directed, 105, 107 OBB, 542 single-inheritance, 105-109 sphere, 542 string, 138-139

tree structure, 163 triangle meshes, 196, 200-202

application screen shots, 18 bilinear interpolation, 24 class, 201

in collision queries, 540 decimation, 309, 326, 328 defined, 201 destroying, 22 drawing, 17-26 generation, 360 nearest-neighbor

interpolation, 25 shrinking, avoiding, 327 in terrain design, 378 textures, 17, 20 with vertex normals,

201-202 without normals, 202 See also geometric types

triangle patches, 361 triangles

back-facing, 220 center point, 3, 4 centroids, 544 configurations, 380 double-sided, 220 drawing, 2-17 drawing application screen

shots, 17 front-facing, 219, 220 insertion, 330 intersection, 501 intersection with linear

components, 503-507 intersection with rays, 504 intersection with segments,

504 partitioning, 544 point representation, 503 removal, 330 rotating, 3 unit-length normals, 202 vertex normal and, 202 vertices, 2, 4, 11, 12, 200

triangle soup, 200, 201 defined, 200

sent to renderer, 201

triangle-triangle intersection queries, 550-551

dynamic, 550-551 implementation, 550 static, 550

trigonometric functions, 57-61 cosine, 59-60 fast, 58 inverse, 58 sine, 55, 57, 58, 59 tangent, 60 See also mathematics

functions trilinear interpolation, 236,

237, 452 defined, 236 illustrated, 237

TriMesh class, 201, 203, 332, 374, 531

TSet class, 41, 42 TStack class, 43 TurnLeft function, 624 TurnRight function, 624, 625 two-dimensional arrays, 49-51 typecast

dynamic, 110-111 smart pointers, 118 static, 110-111

U umbilic point, 366 uniform scaling, 167, 170 unique identifiers, 113-114 UnitCross function, 74 UnitRandom function, 57 UpdateBS function, 187, 194 Update function, 400, 403, 406,

412, 413, 562 UpdateGS function, 187, 190,

192, 194, 195-196, 229 UpdateLocal function, 419

425-427

UpdateLocalT function, 420-422, 429

UpdateModelNormals function, 188, 201

UpdateMS function, 188, 192 UpdatePointMotion function,

408, 409 UpdateRS method, 252, 255,

256, 258 updates

geometric, 184-196 geometric state, 307 heap, 330 local transformations, 422 render state, 251-259, 307

UpdateState function, 252, 254, 258

UpdateSystemMotion function, 408, 409

UpdateWorldBound function, 188, 192, 229, 264

UpdateWorldData function, 187, 188, 191-192, 258, 301

UpdateWorldSRT function, 418 updating the render state,

251-259 common situation for, 253 defined, 251 initiation, 253 interfaces, 251-252 semantics, 254

user-defined constants, 467, 469

UVBias function, 388

V variables, 688-689 vectors, 61-75

algebraic operations, 70 basic operations, 67-68 basis, 68

camera direction, 260 camera right, 260 camera up, 260 classes, 61, 67-68 comparison operators, 69 constant, 68 with float components, 67 geometric operations, 70-75 homogeneous, 174 input, 73, 176 light, 440-442, 445 member access, 68-69 memory layout, 61-67 normal, 363, 364 normalized, 71 output, 176 perpendicular, 71 reflection, 447 returned, 73 tangent, 97, 99, 363, 364 templates, 67-68 unit-length, 71, 100 zero, 68 See also mathematics system

velocities angular, 594 changes, 538 constant linear, 537-538 linear, 593-594 object, 500

vertex arrays, 23 vertex collapses

for 16-sided polygon, 325 computing, 322 illustrated, 324 table, 326, 327

VertexColorEffect class, 433-434

defined, 433 interface, 433 sample use, 433-434

vertex coloring, 433-434 vertex controllers, 158-159

473-474

GetShaderType function implementation, 473

instantiation, 474 interface, 473 object, 483

vertex shaders Cg, 465-466 defined, 149-150 enabling in OpenGL,

482-483 inputs, 466-467, 486 prototypical, 462 shader constants, 470 support implementation,

463 writing, 462 See also shader programs

vertex simplification, 379-382 vertex weights

adjacent, 320 calculation of, 310 defined, 309 definitions for, 310

vertices batch-transforming, 326 colors, 288 disabled, 382 far plane, 260 index, 312 keep, 326, 327 model, 154 near plane, 260 normals, 288 offset, 411 order of application, 156 polygon, 345 polyline of, 580 reduced polyline, 310 renderer and, 157 reordering, 326, 331 sorting, 331 surface, 373

vertices (triangle), 2, 4, 200

colors, 12 connecting, 22 locations, 12 normals, 201, 202 transformed to world

coordinates, 11 view frustum, 179

camera model and, 261 defined, 259 parameters, 265-268 specifying, 3 symmetric, 267

viewport parameters, 268-270 defined, 268 offset window, 269 orientation, 269-270 position, 269-270

viewports current, 276 normalized coordinates, 528 on near plane, 529 settings, 275, 534 target display in, 534

view volume, 259 virtual function tables

base class, 64 derivation support, 62 derived class, 64 results, 65 virtual function pointers, 62

virtual trackballs, 629, 630 volume masses, 586-589

deformable, 587 illustrated, 586 implementation class,

587-588 representation, 586 sample application, 589 See also masses

VRAM, 335-336 discard operations, 336 limited, 335

W weighted squared distances,

420, 424 WglRenderer class, 277 WhichSide function, 103, 183,

342 which-side-of-plane query, 178,

180 white space, 681-685

blank lines, 682 conditionals, 684-685 function calls, 684 function declarators,

682-683 indentation, 681-682 See also coding conventions

Wild Magic, 17 abstract system layer, 45 architecture, 28 classes, 67 class hierarchy, 30 collision detection support,

30 defined, 1, 28 renderers, 149

Win32, 3, 5 WindowApplication3 class,

620-636 defined, 620 interface, 620-621 LookDown function, 625 LookUp function, 625 MoveBackward function, 624 MoveDown function, 624 MoveForward function, 623 MoveObject function,

628-629 MoveUp function, 624 OnKeyDown function, 629 OnMotion callback, 635 OnMouseClick callback,

624-625 TurnLeft function, 624 TurnRight function, 624, 625

612-620

constructor, 614-615 defined, 612 event callbacks, 615-616 font handling support, 619 interface, 612 Main function, 614

windowing systems event handling, 615-620 main function structure, 616

windows creation step, 6 dimensions, 6 title, 7 width/height, 3

WinMain function, 601, 602 WinProc function, 10, 13 wireframes, 221

as application members, 221

enabling/disabling, 221 See also global states

WireframeState class, 221 Wm3System file, 31 WmifToBmp converter, 674 WndProc function, 601, 602 world bound, 155

children, 157 defined, 155 parent, 157

world bounding volumes, 186 calculation, 187 propagation, 190, 191, 194 recomputation, 189 updating, 193

world coordinates camera, 398 inertia tensor in, 593

triangle transformation to, 11

world transformations, 155, 156, 164

as compositions, 186 computation, 169-170, 186 directly setting, 186 in public scope, 186 See also transformations

X-Z yaw, 87 z-buffers

defined, 206 state, 253 state members, 215 state pointer, 254