GPGPU programming for games and science/ David H.Eberly

Includes bibliographical references and index.

1 Introduction
2.4.1 Conversion from Rational to Binary Scientific Numbers 24
2.4.2 Arithmetic Properties of Binary Scientific Numbers 27
2.4.2.1 Addition of Binary Scientific Numbers . . .
2.4.2.2 Subtraction of Binary Scientific Numbers .
2.4.2.3 Multiplication of Binary Scientific Numbers
2.4.2.4 Division of Binary Scientific Numbers . . .
2.4.3 Algebraic Properties of Binary Scientific Numbers .
2.5 Floating-Point Arithmetic
2.5.1 Binary Encodings
5 CPU Computing
2.1 Numerical Computing ^
2.1.1 The Curse: An Example from Games
2.1.2 The Curse: An Example from Science
2.1.3 The Need to Understand Floating-Point Systems
2.2 Balancing Robustness, Accuracy, and Speed
2.2.1 Robustness
2.2.1.1 Formal Definitions
2.2.1.2 Algorithms and Implementations
2.2.1.3 Practical Definitions
2.2.2 Accuracy
2.2.3 Speed
2.2.4 Computer Science Is a Study of Trade-offs . . .
2.3 IEEE Floating Point Standard
2.4 Binary Scientific Notation
2.5.1.1 8-bit Floating-Point Numbers 33
2.5.1.2 16-Bit Floating-Point Numbers 36
2.5.1.3 32-Bit Floating-Point Numbers 39
2.5.1.4 64-Bit Floating-Point Numbers 41
2.5.1.5 n-Bit Floating-Point Numbers 42
2.5.1.6 Classifications of Floating-Point Numbers . . 45
2.5.2 Rounding and Conversions 50
2.5.2.1 Rounding with Ties-to-Even 51
2.5.2.2 Rounding with Ties-to-Away 52
2.5.2.3 Rounding toward Zero 52
2.5.2.4 Rounding toward Positive 52
2.5.2.5 Rounding toward Negative 53
2.5.2.6 Rounding from Floating-Point to Integral
Floating-Point 54
2.5.2.7 Conversion from Integer to Floating-Point . 60
2.5.2.8 Conversion from Floating-Point to Rational . 64
2.5.2.9 Conversion from Rational to Floating-Point. 67
2.5.2.10 Conversion to Wider Format 70
2.5.2.11 Conversion to Narrower Format 73
2.5.3 Arithmetic Operations 81
2.5.4 Mathematical Functions 82
2.5.5 Floating-Point Oddities 83
2.5.5.1 Where Have My Digits Gone? 83
2.5.5.2 Have a Nice Stay! 88
2.5.5.3 The Best I Can Do Is That Bad? 89
2.5.5.4 You Have Been More Than Helpful 91
2.5.5.5 Hardware and Optimizing Compiler Issues . 92
SIMD Computing
3.1 Intel Streaming SIMD Extensions 93
3.1.1 Shuflling Components 94
3.1.2 Single-Component versus All-Component Access . .. 95
3.1.3 Load and Store Instructions 95
3.1.4 Logical Instructions 98
3.1.5 Comparison Instructions 99
3.1.6 Arithmetic Instructions 100
3.1.7 Matrix Multiplication and TVanspose 100
3.1.8 IEEE Floating-Point Support 103
3.1.9 Keep the Pipeline Running 103
3.1.10 Flattening of Branches 104
3.2 SIMD Wrappers 100
3.3 Function Approximations 107
3.3.1 Minimax Approximations
3.3.2 Inverse Square Root Function Using Root Finding . . 110
3.3.3 Square Root Function HI
3.3.4 Inverse Square Root Using a Minimax Algorithm ... 114
3.3.5 Sine Function 116
3.3.6 Cosine Function ." 116
3.3.7 Tangent Function 117
3.3.8 Inverse Sine Function 117
3.3.9 Inverse Cosine Function 119
3.3.10 Inverse Tangent Function 119
3.3.11 Exponential Functions 120
3.3.12 Logarithmic Functions 120
GPU Computing 123
4.1 Drawing a 3D Object 123
4.1.1 Model Space 123
4.1.2 World Space 123
4.1.3 View Space 124
4.1.4 Projection Space 125
4.1.5 Window Space 129
4.1.6 Summary of the Transformations 130
4.1.7 Rasterization 131
4.2 High Level Shading Language (HLSL) 134
4.2.1 Vertex and Pixel Shaders 134
4.2.2 Geometry Shaders 138
4.2.3 Compute Shaders 141
4.2.4 Compiling HLSL Shaders 144
4.2.4.1 Compiling the Vertex Coloring Shaders . . . 147
4.2.4.2 Compiling the Texturing Shaders 151
4.2.4.3 Compiling the Billboard Shaders 152
4.2.4.4 Compiling the Gaussian Blurring Shaders . . 156
4.2.5 Reflecting HLSL Shaders 160
4.3 Devices, Contexts, and Swap Chains 168
4.3.1 Creating a Device and an Immediate Context 168
4.3.2 Creating Swap Chains 170
4.3.3 Creating the Back Buffer 171
4.4 Resources 173
4.4.1 Resource Usage and CPU Access 174
4.4.2 Resource Views 175
4.4.3 Subresources 178
4.4.4 Buffers 179
4.4.4.1 Constant Buffers 181
4.4.4.2 Texture Buffers 181
4.4.4.3 Vertex Buffers 182
4.4.4.4 Index Buffers 184
4.4.4.5 Structured Buffers 184
4.4.4.6 Raw Buffers 187
4.4.4.7 Indirect-Argument Buffers 189
4.4.5 Textures 189
4.4.5.1 ID Textures 192
4.4.5.2 2D Textures 193
4.4.5.3 3D Textures 194
4.4.6 Texture Arrays 195
4.4.6.1 ID Texture Arrays 195
4.4.6.2 2D Texture Arrays 196
4.4.6.3 Cubemap Textures 197
4.4.6.4 Cubemap Texture Arrays 198
4.4.7 Draw Targets 198
4.5 States 201
4.6 Shaders 202
4.6.1 Creating Shaders 202
4.6.2 Vertex, Geometry, and Pixel Shader Execution . . .. 202
4.6.3 Compute Shader Execution 205
4.7 Copying Data between CPU and CPU 207
4.7.1 Mapped Writes for Dynamic Update 207
4.7.2 Staging Resources 210
4.7.3 Copy from CPU to CPU 211
4.7.4 Copy from CPU to CPU 212
4.7.5 Copy from CPU to CPU 213
4.8 Multiple CPUs 214
4.8.1 Enumerating the Adapters 214
4.8.2 Copying Data between Multiple CPUs 215
4.9 IEEE Floating-Point on the CPU 217
Practical Matters 223
5.1 Engine Design and Architecture 223
5.1.1 A Simple Low-Level D3D11 Application
5.1.2 HLSL Compilation in Microsoft Visual Studio . . .
5.1.3 Design Goals for the Geometric Tools Engine . . .
5.1.3.1 An HLSL Factory
5.1.3.2 Resource Bridges
5.1.3.3 Visual Effects
5.1.3.4 Visual Objects and Scene Graphs . . . .
5.1.3.5 Cameras
5.2 Debugging
5.2.1 Debugging on the CPU
5.2.2 Debugging on the CPU
5.2.3 Be Mindful of Your Surroundings n • •
5.2.3.1 An Example of an HLSL Compiler Bug .
5.2.3.2 An Example of a Programmer Bug . . . .
5.3 Performance
5.3.1 Performance on the CPU
5.3.2 Performance on the CPU
5.3.3 Performance Guidelines
5.4 Code Testing 249
5.4.1 Topics in Code Testing 250
5.4.2 Code Coverage and Unit Testing on the CPU 254
Linear and AfRne Algebra 257
6.1 Vectors 257
6.1.1 Robust Length and Normalization Computations . . . 258
6.1.2 Orthogonality 260
6.1.2.1 Orthogonality in 2D 260
6.1.2.2 Orthogonality in 3D 261
6.1.2.3 Orthogonality in 4D 262
6.1.2.4 Gram-Schmidt Orthonormalization 263
6.1.3 Orthonormal Sets 264
6.1.3.1 Orthonormal Sets in 2D 265
6.1.3.2 Orthonormal Sets in 3D 265
6.1.3.3 Orthonormal Sets in 4D 267
6.1.4 Barycentric Coordinates 269
6.1.5 Intrinsic Dimensionality 270
6.2 Matrices 273
6.2.1 Matrix Storage and Transfom Conventions 274
6.2.2 Base Class Matrix Operations 275
6.2.3 Square Matrix Operations in 2D 278
6.2.4 Square Matrix Operations in 3D 279
6.2.5 Square Matrix Operations in 4D 281
6.2.6 The Laplace Expansion Theorem 282
6.3 Rotations 288
6.3.1 Rotation in 2D 288
6.3.2 Rotation in 3D 289
6.3.3 Rotation in 4D 292
6.3.4 Quaternions 294
6.3.4.1 Algebraic Operations 295
6.3.4.2 Relationship of Quaternions to Rotations . . 297
6.3.4.3 Spherical Linear Interpolation of Quaternions 299
6.3.5 Euler Angles 305
6.3.5.1 World Coordinates versus Body Coordinates 306
6.3.6 Conversion between Representations 308
6.3.6.1 Quaternion to Matrix 309
6.3.6.2 Matrix to Quaternion 309
6.3.6.3 Axis-Angle to Matrix 311
6.3.6.4 Matrix to Axis-Angle 311
6.3.6.5 Axis-Angle to Quaternion 312
6.3.6.6 Quaternion to Axis-Angle 312
6.3.6.7 Euler Angles to Matrix 313
6.3.6.8 Matrix to Euler Angles 313
6.3.6.9 Eiiler Angles to and from Quaternion or Axis-
Angle .. ." 317
6.4 Coordinate Systems 318
6.4.1 Geometry and Affine Algebra 319
6.4.2 Transformations 322
6.4.2.1 Composition of Affine Transformations . . . 322
6.4.2.2 Decomposition of Affine Transformations . . 327
6.4.2.3 A Simple Transformation Factory 330
6.4.3 Coordinate System Conventions 332
6.4.4 Converting between Coordinate Systems 336
Sample Applications 341
7.1 Video Streams 341
7.1.1 The VideoStream Class 341
7.1.2 The VideoStreamManager Class 342
7.2 Root Finding 346
7.2.1 Root Bounding 346
7.2.2 Bisection 347
7.2.3 Newton's Method 348
7.2.4 Exhaustive Evaluation 350
7.2.4.1 CPU Root Finding Using a Single Thread . . 350
7.2.4.2 CPU Root Finding Using Multiple Threads . 351
7.2.4.3 CPU Root Finding 352
7.3 Least Squares Fitting 355
7.3.1 Fit a Line to 2D Points 355
7.3.2 Fit a Plane to 3D Points 358
7.3.3 Orthogonal Regression 359
7.3.3.1 Fitting with Lines 359
7.3.3.2 Fitting with Planes 361
7.3.4 Estimation of Tangent Planes 362
7.4 Partial Sums 364
7.5 All-Pairs Triangle Intersection 368
7.6 Shortest Path in a Weighted Graph 371
7.7 Convolution 377
7.8 Median Filtering 384
7.8.1 Median by Sorting 385
7.8.2 Median of 3 x 3 Using Min-Max Operations 387
7.8.3 Median of 5 x 5 Using Min-Max Operations 389
7.9 Level Surface Extraction 392
7.10 Mass-Spring Systems 398
7.11 Fluid Dynamics 400
7.11.1 Numerical Methods 401
7.11.2 Solving Fluid Flow in 2D 403
7.11.2.1 Initialization of State 405
7.11.2.2 Initialization of External Forces 406
7.11.2.3 Updating the State with Advection 409
7.11.2.4 Applying the State Boundary Conditions . . 410
7.11.2.5 Computing the Divergence of Velocity .... 413
7.11.2.6 Solving the Poisson Equation 413
7.11.2.7 Updating the Velocity to Be Divergence FVee 414
7.11.2.8 Screen Captures from the Simulation .... 415
7.11.3 Solving Fluid Flow in 3D 416
7.11.3.1 Initialization of State 418
7.11.3.2 Initialization of External Forces 419
7.11.3.3 Updating the State with Advection 422
7.11.3.4 Applying the State Boundary Conditions . . 424
7.11.3.5 Computing the Divergence of Velocity .... 425
7.11.3.6 Solving the Poisson Equation 425
7.11.3.7 Updating the Velocity to Be Divergence Free 427
7.11.3.8 Screen Captures from the Simulation .... 427