Loading......

Chapter    1 Introduction    1
1.1    The Evolution of Graphics Hardware and Games    1
1.2    The Evolution of This Book and Its Software    2
1.3    A Summary of the Chapters    3
Chapter    2 The Graphics System    7
2.1    The Foundation    8
2.1.1    Coordinate Systems 9
2.1.2    Handedness and Cross Products    10
2.1.3    Points and Vectors    15
2.2    Transformations    18
2.2.1    Linear Transformations    18
2.2.2    Affine Transformations    29
2.2.3    Projective Transformations    31
2.2.4    Properties of Perspective Projection    35
2.2.5    Homogeneous Points and Matrices    40
2.3    Cameras    43
2.3.1    The Perspective Camera Model    43
2.3.2    Model or Object Space    48
2.3.3    World Space    48
2.3.4    View, Camera, or Eye Space    50
2.3.5    Clip, Projection, or Homogeneous Space    52
2.3.6    Window Space    56
2.3.7    Putting Them All Together    58
2.4    Culling and Clipping    66
2.4.1    Object Culling    66
2.4.2    Back-Face Culling    67
2.4.3    Clipping to the View Frustum    70
2.5    Rasterizing    77
2.5.1    Line Segments    77
2.5.2    Circles    82
2.5.3    Ellipses    84
2.5.4    Triangles    89
2.6    Vertex Attributes 92
2.6.1    Colors 92
2.6.2    Lighting and Materials 92
2.6.3    Textures 99
2.6.4    Transparency, Opacity, and Blending    117
2.6.5    Fog    122
2.6.6    And Many More    123
2.6.7    Rasterizing Attributes    124
2.7    Issues of Software, Hardware, and APIs    125
2.7.1    A General Discussion    125
2.7.2    Portability versus Performance    127
2.8    API Conventions    128
2.8.1    Matrix Representation and Storage    129
2.8.2    Matrix Composition    134
2.8.3    View Matrices    134
2.8.4    Projection Matrices    136
2.8.5    Window Handedness    139
2.8.6    Rotations    140
2.8.7    Fast Computations Using the Graphics API    143
Chapter    3 Renderers    147
3.1    Software Rendering    149
3.1.1    Vertex Shaders    149
3.1.2    Back-Face Culling    151
3.1.3    Clipping    154
3.1.4    Rasterizing    158
3.1.5    Edge Buffers    159
3.1.6    Scan Line Processing    161
3.1.7    Pixel Shaders    164
3.1.8    Stencil Buffering    167
3.1.9    Depth Buffering    169
3.1.10 Alpha Blending    170
3.1.11    Color Masking    171
3.1.12 Texture Sampling    171
3.1.13 Frame Buffers    172
3.2    Hardware Rendering    173
3.3    An Abstract Rendering API    175
3.3.1    Construction and Destruction    175
3.3.2    Camera Management    176
3.3.3    Global-State Management    177
3.3.4    Buffer Clearing    178
3.3.5    Object Drawing    179
3.3.6    Text and    2D Drawing    180
3.3.7    Miscellaneous    180
3.3.8    Resource Management    182
3.4    The Heart of the Renderer    194
3.4.1    Drawing a Scene    195
3.4.2    Drawing a Geometric Primitive    198
3.4.3    Applying an Effect    199
3.4.4    Loading and Parsing Shader Programs    201
3.4.5    Validation of Shader Programs    213
Chapter    4 Scene Graphs    217
4.1    Scene Graph Design Issues    217
4.1.1    The Core Classes    221
4.1.2    Spatial Hierarchy Design    226
4.1.3    Sharing of Objects    230
4.2    Geometric State    233
4.2.1    Vertex Buffers and Index Buffers    233
4.2.2    Transformations    234
4.2.3    Bounding Volumes    244
4.2.4    Geometric Types    251
4.3    Render State    259
4.3.1    Global State    259
4.3.2    Lights    261
4.3.3    Effects    266
4.4    The Update Pass    268
4.4.1    Geometric-State Updates    268
4.4.2    Render-State Updates    280
4.5    The Culling Pass    289
4.5.1    Hierarchical Culling    293
4.5.2    Sorted Culling    296
4.6    The Drawing Pass    297
4.6.1    Single-Pass Drawing    298
4.6.2    Single-Effect, Multipass Drawing    302
4.6.3    Multiple-Effect Drawing    304
4.7    Scene Graph Compilers    305
4.7.1    A Scene Graph as an Expression    307
4.7.2    Semantics of Compilation    311
Chapter    5 Controller-Based Animation    315
5.1    Keyframe Animation    317
5.1.1    Interpolation of Position    317
5.1.2    Interpolation of Orientation    318
5.1.3    Interpolation of Scale    318
5.2    Keyframe Compression    320
5.2.1    Fitting Points with a B-Spline Curve    321
5.2.2    Evaluation of a B-Spline Curve    325
5.2.3    Optimized Evaluation for Degree    3    333
5.3    Inverse Kinematics    339
5.3.1    Numerical Solution by Jacobian Methods    341
5.3.2    Numerical Solution by Nonlinear Optimization    342
5.3.3    Numerical Solution by Cyclic Coordinate Descent    342
5.4    Skinning    347
5.5    Vertex Morphing    349
5.6    Particle Systems    350
Chapter
6 Spatial Sorting    353
6.1    Binary Space Partitioning Trees    354
6.1.1    BSP Tree Construction    355
6.1.2    BSP Tree Usage    357
6.2    Node-Based Sorting    365
6.3    Portals    366
6.4    User-Defined Maps    375
6.5    Occlusion Culling    375
Chapter    7 Level of Detail    377
7.1    Sprites and Billboards    378
7.2    Discrete Level of Detail    379
7.3    Continuous Level of Detail    380
7.3.1    Simplification Using Quadric Error Metrics    380
7.3.2    Reordering of Vertices and Indices    385
7.3.3    Terrain    386
7.4    Infinite Level of Detail    387
Chapter    8 Collision Detection    389
8.1    The Method of Separating Axes    393
8.1.1    Extrema of Convex Polygons or Convex Polyhedra    394
8.1.2    Stationary Objects    404
8.1.3    Objects Moving with Constant Linear Velocity    412
8.1.4    Oriented Bounding Boxes    436
8.2    Finding Collisions between Moving Objects    444
8.2.1    Pseudodistance    444
8.2.2    Contact between Moving Intervals    446
8.2.3    Computing the First Time of Contact    448
8.2.4    Estimating the First Derivative    453
8.3    A Dynamic Collision Detection System    455
8.3.1    The Abstract Base Class    455
8.3.2    Pseudodistances for Specific Pairs of Object Types    461
8.3.3    Collision Culling with Axis-Aligned Bounding Boxes    465
8.4    Object Picking    472
8.4.1    Constructing a Pick Ray    472
8.4.2    Scene Graph Support    475
8.4.3    Staying on Top of Things    479
8.4.4    Staying Out of Things    481
8.5    Pathfinding to Avoid Collisions    481
8.5.1    Environments, Levels, and Rooms    482
8.5.2    Moving between Rooms    486
8.5.3    Moving between Levels    486
8.5.4    Moving through the Outdoor Environment    488
8.5.5    Blueprints    488
8.5.6    Visibility Graphs    489
8.5.7    Envelope Construction    494
8.5.8    Basic Data Structures    503
8.5.9    Efficient Calculation of the Visibility Graph    504
Chapter 9 Physics    507
9.1    Particle Systems    508
9.2    Mass-Spring Systems    510
9.2.1    Curve Masses    510
9.2.2    Surface Masses    513
9.2.3    Volume Masses    516
9.2.4    Arbitrary Configurations    519
9.3    Deformable Bodies    521
9.4    Rigid Bodies    522
9.4.1    The Rigid Body Class    525
9.4.2    Computing the Inertia Tensor    527
Chapter    10 Standard Objects    529
10.1    Linear Components    529
10.2    Planar Components    532
10.3    Boxes    534
10.4    Quadrics    535
10.4.1    Spheres    535
10.4.2    Ellipsoids    535
10.4.3    Cylinders    537
10.4.4    Cones    537
10.5    Sphere-Swept Volumes    538
10.5.1    Capsules    539
10.5.2    Lozenges    539
Chapter    11    Curves    541
11.1    Definitions    542
11.2    Reparameterization by Arc Length    543
11.3    B′ezier Curves    545
11.3.1    Definitions    545
11.3.2    Evaluation    545
11.3.3    Degree Elevation    546
11.3.4    Degree Reduction    546
11.4    Natural, Clamped, and Closed Cubic Splines    548
11.4.1    Natural Splines    550
11.4.2    Clamped Splines    550
11.4.3    Closed Splines    550
11.5    B-Spline Curves    551
11.5.1    Types of Knot Vectors    552
11.5.2    Evaluation    553
11.5.3    Local Control    558
11.5.4    Closed Curves    558
11.6    NURBS Curves    560
11.7    Tension-Continuity-Bias Splines    562
11.8    Parametric Subdivision    566
11.8.1    Subdivision by Uniform Sampling    566
11.8.2    Subdivision by Arc Length    566
11.8.3    Subdivision by Midpoint Distance    567
11.8.4    Fast Subdivision for Cubic Curves    568
11.9    Orientation of Objects on Curved Paths    570
11.9    .1    Orientation Using the Frenet Frame    571
11.9    .2    Orientation Using a Fixed Up-Vector    571
Chapter    12 Surfaces    573
12.1    Introduction    573
12.2    B′ezier Rectangle Patches    574
12.2.1    Definitions    574
12.2.2    Evaluation    575
12.2.3    Degree Elevation    575
12.2.4    Degree Reduction    576
12.3    B′ezier Triangle Patches    578
12.3.1    Definitions    578
12.3.2    Evaluation    578
12.3.3    Degree Elevation    580
12.3.4    Degree Reduction    580
12.4    B-Spline Rectangle Patches    582
12.5    NURBS Rectangle Patches    583
12.6    Surfaces Built from Curves    584
12.6.1    Cylinder Surfaces    584
12.6.2    Generalized Cylinder Surfaces    585
12.6.3    Revolution Surfaces    586
12.6.4    Tube Surfaces    586
12.7    Parametric Subdivision    587
12.7.1    Subdivision of Rectangle Patches    587
12.7.2    Subdivision of Triangle Patches    602
Chapter    13 Containment Methods    609
13.1    Spheres    609
13.1.1    Point in Sphere    609
13.1.2    Sphere Containing Points    610
13.1.3    Merging Spheres    616
13.2    Boxes    617
13.2.1    Point in Box    617
13.2.2    Box Containing Points    618
13.2.3    Merging Boxes    625
13.3    Capsules    627
13.3.1    Point in Capsule    627
13.3.2    Capsule Containing Points    628
13.3.3    Merging Capsules    629
13.4    Lozenges    630
13.4.1    Point in Lozenge    631
13.4.2    Lozenge Containing Points    631
13.4.3    Merging Lozenges    633
13.5    Cylinders    634
13.5.1    Point in Cylinder    634
13.5.2    Cylinder Containing Points    634
13.5.3    Least-Squares Line Moved to Minimum-Area Center    635
13.5.4    Merging Cylinders    635
13.6    Ellipsoids    636
13.6.1    Point in Ellipsoid    636
13.6.2    Ellipsoid Containing Points    637
13.6.3    Merging Ellipsoids    638
Chapter    14 Distance Methods    639
14.1    Point to Linear Component    639
14.1.1    Point to Line    640
14.1.2    Point to Ray    640
14.1.3    Point to Segment    641
14.2    Linear Component to Linear Component    642
14.2.1    Line to Line    642
14.2.2    Line to Ray    643
14.2.3    Line to Segment    644
14.2.4    Ray to Ray    645
14.2.5    Ray to Segment    645
14.2.6    Segment to Segment    645
14.3    Point to Triangle    646
14.4    Linear Component to Triangle    651
14.4.1    Line to Triangle    651
14.4.2    Ray to Triangle    654
14.4.3    Segment to Triangle    654
14.5    Point to Rectangle    655
14.6    Linear Component to Rectangle    657
14.6.1    Line to Rectangle    657
14.6.2    Ray to Rectangle    659
14.6.3    Segment to Rectangle    660
14.7    Triangle or Rectangle to Triangle or Rectangle    661
14.8    Point to Oriented Box    663
14.9    Linear Component to Oriented Box    663
14.9    .1    Line to Oriented Box    664
14.9    .2    Ray to Oriented Box    666
14.9    .3    Segment to Oriented Box    666
14.10 Triangle to Oriented Box    667
14.11    Rectangle to Oriented Box    669
14.12 Oriented Box to Oriented Box    670
14.13 Miscellaneous    672
14.13.1Point to Ellipse    672
14.13.2Point to Ellipsoid    673
14.13.3Point to Quadratic Curve or to Quadric Surface    674
14.13.4Point to Circle in    3D    675
14.13.5Circle to Circle in    3D    676
Chapter    15 Intersection Methods    681
15.1    Linear Components and Convex Objects    681
15.2    Linear Component and Planar Component    684
15.3    Linear Component and Oriented Box    686
15.3.1    Test-Intersection Query    686
15.3.2    Find-Intersection Query    693
15.4    Linear Component and Sphere    698
15.4.1    Line and Sphere    698
15.4.2    Ray and Sphere    700
15.4.3    Segment and Sphere    701
15.5    Line and Sphere-Swept Volume    703
15.5.1    Line and Capsule    703
15.5.2    Line and Lozenge    708
15.6    Line and Quadric Surface    709
15.6.1    Line and Ellipsoid    709
15.6.2    Line and Cylinder    710
15.6.3    Line and Cone    710
15.7    Culling Objects by Planes    710
15.7.1    Oriented Boxes    711
15.7.2    Spheres    712
15.7.3    Capsules    712
15.7.4    Lozenges    713
15.7.5    Ellipsoids    713
15.7.6    Cylinders    715
15.7.7    Cones    716
15.7.8    Convex Polygons or Convex Polyhedra    717
Chapter
16 Numerical Methods    719
16.1    Systems of Equations    719
16.1.1    Linear Systems    719
16.1.2    Polynomial Systems    720
16.2    Eigensystems    722
16.2.1    Extrema of Quadratic Forms    722
16.2.2    Extrema of Constrained Quadratic Forms    723
16.3    Least-Squares Fitting    724
16.3.1    Linear Fitting of Points (x, f (x))    724
16.3.2    Linear Fitting of Points Using Orthogonal Regression    725
16.3.3    Planar Fitting of Points (x,y,f (x,y))    726
16.3.4    Planar Fitting of Points Using Orthogonal Regression    726
16.3.5    Fitting a Circle to    2D Points    727
16.3.6    Fitting a Sphere to    3D Points    729
16.3.7    Fitting a Quadratic Curve to    2D Points    731
16.3.8    Fitting a Quadric Surface to    3D Points    731
16.4    Minimization    732
16.4.1    Methods in One Dimension    732
16.4.2    Methods in Many Dimensions    733
16.5    Root Finding    736
16.5.1    Methods in One Dimension    736
16.5.2    Methods in Many Dimensions    740
16.6    Integration    742
16.6.1    Romberg Integration    742
16.6.2    Gaussian Quadrature    746
16.7    Differential Equations    747
16.7.1    Ordinary Differential Equations    747
16.7.2    Partial Differential Equations    750
16.8    Fast Function Evaluation    754
16.8.1    Square Root and Inverse Square Root    754
16.8.2    Sine, Cosine, and Tangent    755
16.8.3    Inverse Tangent    756
Chapter    17 Rotations    759
17.1    Rotation Matrices    759
17.1.1    Axis/Angle to Matrix    760
17.1.2    Matrix to Axis/Angle    762
17.1.3    Interpolation    763
17.2    Quaternions    764
17.2.1    The Linear Algebraic View of Quaternions    766
17.2.2    Rotation of a Vector    769
17.2.3    Product of Rotations    769
17.2.4    The Classical View of Quaternions    770
17.2.5    Axis/Angle to Quaternion    772
17.2.6    Quaternion to Axis/Angle    773
17.2.7    Matrix to Quaternion    773
17.2.8    Quaternion to Matrix    773
17.2.9    Interpolation    774
17.3    Euler Angles    774
17.4    Performance Issues    777
17.5    The Curse of Nonuniform Scaling    778
17.5.1    Gram-Schmidt Orthonormalization    779
17.5.2    Eigendecomposition    781
17.5.3    Polar Decomposition    781
17.5.4    Singular Value Decomposition    781
Chapter    18 Object-Oriented Infrastructure    783
18.1    Object-Oriented Software Construction    783
18.1.1    Software Quality    784
18.1.2    Modularity    785
18.1.3    Reusability    787
18.1.4    Functions and Data    788
18.1.5    Object Orientation    789
18.2    Style, Naming Conventions, and Namespaces    790
18.3    Run-Time Type Information    793
18.3.1    Single-Inheritance Systems    793
18.3.2    Multiple-Inheritance Systems    797
18.3.3    Macro Support    799
18.4    Templates    800
18.5    Shared Objects and Reference Counting    802
18.6    Streaming    808
18.6.1    The Stream API    809
18.6.2    The Object API    812
18.7    Names and Unique Identifiers    819
18.7.1    Name String    820
18.7.2    Unique Identification    820
18.8    Initialization and Termination    822
18.8.1    Potential Problems    822
18.8.2    A Generic Solution for Classes    825
18.9    An Application Layer    831
18.9    .1    Processing Command-Line Parameters    832
18.9    .2    The Application Class    836
18.9    .3    The ConsoleApplication Class    839
18.9    .4    TheWindowApplication Class    842
18.9    .5    TheWindowApplication3 Class    849
18.9    .6    Managing the Engines    867
Chapter    19 Memory Management    873
19.1    Memory Budgets for Game Consoles    873
19.2    Leak Detection and Collecting Statistics    875
19.3    General Memory Management Concepts    882
19.3.1    Allocation Using Sequential-Fit Methods    882
19.3.2    Allocation Using Buddy-System Methods    891
19.3.3    Allocation Using Segregated-Storage Methods    895
19.3.4    Memory Compaction    895
Chapter    20 Special Effects Using Shaders    897
20.1    Vertex Colors    897
20.2    Lighting and Materials    899
20.2.1    Ambient Lights 901
20.2.2    Directional Lights 902
20.2.3    Point Lights 903
20.2.4    Spotlights 904
20.3    Textures 909
20.4    Multitextures 911
20.5    Bump Maps 914
20.5.1    Generating Normal Maps 914
20.5.2    Generating Tangent-Space Information 916
20.5.3    The Shader Programs 919
20.6    Gloss Maps 923
20.7    Sphere Maps 926
20.8    Cube Maps 929
20.9    Refraction 932
20.10 Planar Reflection 935
20.11    Planar Shadows 939
20.12 Projected Textures 943
20.13 Shadow Maps 945
20.14 Volumetric Fog 947
20.15 Skinning 950
20.16 Iridescence 951
20.17 Water Effects 955
Appendix Creating a Shader in Wild Magic 957
A.1    Shader Programs for an Illustrative Application 958
A.2    Creating the Geometric Data 963
A.3    A Classless Shader Effect 965
A.4    Creating a Class Derived from ShaderEffect 968
A.5    Dynamic Updates for the Shader Constants 970
References 973
Index 981
About the CD-ROM    1017