You are previewing Game Programming Gems 8.
O'Reilly logo
Game Programming Gems 8

Book Description

Welcome to the eighth volume of the must-have reference series for game developers, "Game Programming Gems," the series that helped define the standards for game programming and continues to be an essential source for new, innovative techniques. "Game Programming Gems 8" provides the tools and inspiration that game developers need to excel. Featuring cutting-edge, ready-to-use techniques contributed by industry veterans and experts, this new collection is a key resource for inspiration, insight, and a plethora of time-saving, ready-to-use methods for the developer's tool box! Gems 8 answers the needs of passionate developers, eager newcomers, voracious production requirements, and the demand for innovating and entertaining gameplay. Covering all the key development areas including General Programming, Mathematics, Graphics, Artificial Intelligence, Physics, Networking/Multiplayer, and Audio, each section is edited by an expert in the field to ensure that the ideas are original, accurate, and useful. In this edition, there is even a special segment on General Purpose Programming on GPUs for Game Developers. Dig into this new volume of useful, practical ideas and techniques and get ready to make games that are more inventive, entertaining, and satisfying!

Table of Contents

  1. Copyright
  2. Preface
    1. Overview of Content
    2. About the Cover Image
    3. CD-ROM Downloads
  3. Acknowledgments
  4. Contributors
  5. 1. Graphics
    1. Introduction
    2. 1.1. Fast Font Rendering with Instancing
      1. Text-Rendering Basics
      2. Improving Performance
        1. Lock-Discard
        2. Vertex Compression
      3. Instancing Quad Geometry
      4. Constant Array Instancing
      5. Additional Considerations
        1. Sorting
        2. Clip-Space Positions
        3. Texture Atlasing
      6. Future Work
      7. Demo
      8. Conclusion
      9. References
    3. 1.2. Principles and Practice of Screen Space Ambient Occlusion
      1. Screen Space Ambient Occlusion
      2. Generating the Source Data
      3. Sampling Process
      4. Sampling Randomization
      5. Ambient Occlusion Post-Processing
      6. Handling Edge Cases
      7. Optimizing Performance
      8. Fake Global Illumination and Artistic Styling
      9. Transparency
      10. Final Results
      11. Conclusion
      12. References
    4. 1.3. Multi-Resolution Deferred Shading
      1. Deferred Shading
      2. Multi-Resolution Deferred Shading
      3. Conclusion and Future Work
      4. References
    5. 1.4. View Frustum Culling of Catmull-Clark Patches in DirectX 11
      1. Background
        1. Displaced Subdivision Surfaces and Catmull-Clark Surfaces
        2. Approximate Catmull-Clark Subdivision Surfaces
        3. Displacement
        4. DirectX 11 Pipeline
          1. Hull Shader
          2. Tessellator
          3. Domain Shader
      2. Culling
      3. Pre-Processing Step
      4. Run-Time Step
      5. Performance
      6. Conclusion
      7. References
    6. 1.5. Ambient Occlusion Using DirectX Compute Shader
      1. The Compute Shader
        1. Overview
        2. Compute Shader Threading Model
        3. Compute Shader Thread Interactions
        4. Compute Shader Resources
      2. Screen Space Ambient Occlusion
        1. SSAO Algorithm
        2. SSAO Algorithm Details
        3. SSAO Meets the Compute Shader
          1. Calculation Setup
          2. Randomize Sampling Kernel
          3. Acquire Depth Data
          4. Perform Partial Occlusion Calculation (per Sample)
          5. Perform Complete Occlusion Calculation
      3. Compute Shader Implementation Details
        1. Implementation Overview
        2. Depth/Normal Buffer Generation
        3. Raw Occlusion Buffer Generation
          1. Depth Value Cache with the GSM
        4. Separable Bilateral Filter
      4. Results
      5. Conclusion and Future Work
      6. References
    7. 1.6. Eye-View Pixel Anti-Aliasing for Irregular Shadow Mapping
      1. Background and Problem: Shadow Edge Aliasing
        1. Pixel-Perfect Shadows with the Irregular Z-Buffer
        2. Eye-View Aliasing
      2. Solution: Adaptive Multi-Sampling of Irregular Shadows
        1. Algorithm: Anti-Aliased Irregular Shadow Mapping
        2. Conservative Shadow Edge Stencil Buffer
        3. Shadow Sample Splatting
      3. Results and Discussion
        1. Implementation Details
        2. Compute Requirements
        3. Storage Requirements
        4. Future Work
      4. Conclusion
      5. Acknowledgements
      6. References
    8. 1.7. Overlapped Execution on Programmable Graphics Hardware
      1. Introduction to Irregular Z-Buffer Shadows
      2. Overview of Programmable Graphics Hardware
      3. Overview of Task-Based Parallelism
      4. Combining Render Graphs and Task Graphs
      5. Combined Dependency Graph
      6. Idle-Free Irregular Z-Buffer Shadows
      7. Conclusion
      8. References
    9. 1.8. Techniques for Effective Vertex and Fragment Shading on the SPUs
      1. The CBE as Part of a Real-World System
      2. The SPEs
        1. The SPU
          1. The Synergistic Execution Unit and SPU ISA
          2. Local Store and Memory Flow Controller
      3. Data Management
        1. Multi-Buffering
        2. Structure-of-Arrays versus Array-of-Structures
        3. Branch-Free DMAs
      4. Vertex/Geometry Shading
        1. Handling Strange Alignments When Multi-Buffering
        2. Case Study: Car Damage in Blur
        3. To GPU Types and Back Again
        4. Benefits versus Drawbacks
      5. Fragment Shading
        1. Batch! Batch! Batch!
        2. Pipeline Balance Is Key!
        3. Case Study: Light Pre-Pass Rendering in Blur
        4. Benefits versus Drawbacks
      6. Further Work
      7. Conclusion
      8. Acknowledgements
      9. References
  6. 2. Physics and Animation
    1. Introduction
    2. 2.1. A Versatile and Interactive Anatomical Human Face Model
      1. Overview
      2. Numerical Simulation
      3. Building the Anatomical Model
        1. The Skull
        2. Interactive Sketching of the Muscles
        3. Soft Model for a Facial Muscle
        4. The Muscle Map
        5. Morphing the Muscle Map into the Target Face Mesh
        6. Skin
      4. Conclusion
      5. References
    3. 2.2. Curved Paths for Seamless Character Animation
      1. Related Work
      2. Finding a Path
      3. Smoothing the Path
      4. Animation Selection
      5. Conclusion
      6. References
    4. 2.3. Non-Iterative, Closed-Form, Inverse Kinematic Chain Solver (NCF IK)
      1. Context
      2. Bone Definition
      3. IK Goal Position
        1. One-Bone IK
        2. Two-Bone IK
          1. Aligning the Chain to the IK Goal
          2. Calculating Bone 0 in a Two-Bone Chain
          3. Solving the Last Bone
        3. Three-Bone IK Solver
          1. Maximum Bone Angles
        4. Four-Bone IK Solver
        5. N-Bone IK Solver
      4. Handling Extreme Deformation
      5. Additional Details
        1. IK/FK Blending
        2. Animated Joint Offsets
        3. Extension Limit
      6. Future Work
        1. Sliding Joints
        2. Joint Limits
        3. DOF Constraints
        4. General-Purpose Programming on Graphics Processors
      7. Conclusion
      8. References
    5. 2.4. Particle Swarm Optimization for Game Programming
      1. A Few Words on Optimization
        1. Numerical Methods
        2. No Free Lunch (NFL) Theorem for Optimization
      2. The PSO Paradigm and Its Canonical Formulation
        1. Canonical Equations of Motion
        2. Velocity Update
        3. Evaluating the Particles: The Objective Function
      3. Add-Ons to the Classical Formulation
        1. Velocity Clamping
        2. Variable Inertia Weight ω(t)
        3. Constriction Coefficient
        4. Extended Full Model for Velocity Update
        5. Adding Constraints
        6. Integer Optimization
        7. Maintaining Diversity
      4. A Note on Randomness
      5. Case Study 1: Typical Benchmarking Functions
      6. Case Study 2: Optimization of Physical Parameters for In-Game Vehicle Simulation
      7. Case Study 3: Physics-Based Animation of Mechanical Systems
      8. Conclusion
      9. References
    6. 2.5. Improved Numerical Integration with Analytical Techniques
      1. Classifying Errors
      2. Kinematics of Constant Acceleration
      3. The Kinematic Integrator
      4. Integral Contributions Due to a Spring Force
      5. Multiple Forces
      6. Integral Contributions of a Pulse
      7. Integral Contributions of Collision Forces
      8. Integral Contributions of Viscous Forces
      9. Integral Contributions of Constraint Forces
      10. Summary
      11. Conclusion
    7. 2.6. What a Drag: Modeling Realistic Three-Dimensional Air and Fluid Resistance
      1. Physics
        1. Three-Dimensional Physics
        2. Conversion from Three-Dimensional Physics to One-Dimensional Physics
        3. One-Dimensional Solutions
      2. Solution of the Three-Dimensional Linear Case
      3. Solution of the Three-Dimensional Quadratic Case
      4. Pseudocode
      5. Comparison of Linear versus Quadratic Solutions
      6. Conclusion
      7. References
    8. 2.7. Application of Quasi-Fluid Dynamics for Arbitrary Closed Meshes
      1. Requirements for the Mesh Representing the Object
      2. Physical Rudiments
      3. Pre-Computation Based on a Triangle Mesh
        1. Calculating the Distance to Medium Boundary
        2. Calculating the Point Velocity
        3. Morphing Shape Objects
        4. Triangle Clipping
      4. Calculation of the Pressure on the Triangle Surface
      5. Simple Correction of Dynamic Pressure
      6. Conclusion
      7. References
    9. 2.8. Approximate Convex Decomposition for Real-Time Collision Detection
      1. Approximate Convex Decomposition
      2. Hierarchical Approximate Convex Decomposition
        1. Dual Graph
        2. Decimation Operator
        3. Simplification Strategy
        4. Choice of the Parameter α
      3. Experimental Results
      4. Conclusion
      5. References
  7. 3. AI
    1. Introduction
    2. 3.1. AI Level of Detail for Really Large Worlds
      1. Gradual LOD Example
      2. Graphical LOD versus LOD AI
      3. Simulation at the Full Detail
      4. Toward LOD AI: Hierarchical Behavior
        1. What Does It Mean to Execute a Task as Atomic?
        2. What to Do When the Detail Increases
        3. What to Do When the Detail Decreases
      5. Space Representation
        1. Limitations of Rules 1 through 3
        2. Pathfinding
      6. Positions of Objects and NPCs
        1. Storage of Positional Information
        2. General Information and Expirations
        3. Initialization and Traveling Objects
        4. NPCs
      7. Reshaping the Membrane
        1. What Is the Radius of LODs?
        2. When to Decrease the Detail
      8. Creating the Structure of the World
      9. Source Code Summary
      10. Conclusion
      11. Acknowledgements
      12. References
    3. 3.2. A Pattern-Based Approach to Modular AI for Games
      1. A Real-World Example: Apartment Shopping
      2. Boolean Decisions
        1. Constructing Decisions
        2. A Simple Example: First-Person Shooter AI
        3. AI Specification
        4. Extending the AI
        5. Data-Driven AI
        6. Meta-Considerations
      3. Float-Based Decisions
        1. An Example: Attack Goals
        2. Alternate Approaches
      4. Conclusion
      5. References
    4. 3.3. Automated Navigation Mesh Generation Using Advanced Growth-Based Techniques
      1. The Algorithms
        1. PASFV
        2. VASFV
      2. Post-Processing
      3. Conclusion
      4. References
    5. 3.4. A Practical Spatial Architecture for Animal and Agent Navigation
      1. Fundamental Components of the Spatial Representation System
      2. Navigation System Architecture
      3. Navrep Continuity and Stitching
      4. Handling Locomotion and Turning
      5. Conclusion
      6. Acknowledgements
      7. References
    6. 3.5. Applying Control Theory to Game AI and Physics
      1. Conclusion
      2. References
    7. 3.6. Adaptive Tactic Selection in First-Person Shooter (FPS) Games
      1. A Dynamic Approach to Adaptive Tactic Selection
      2. Overview of the Adaptive Tactic Selection Architecture
      3. Fitness and Weight-Update Functions
      4. Adapting Tactic Selection
      5. Conclusion
      6. References
    8. 3.7. Embracing Chaos Theory: Generating Apparent Unpredictability through Deterministic Systems
      1. The Need for Predictability
      2. Shaking Things Up
      3. A Brief History of Chaos
        1. Perceiving Error
        2. Brownian Motion
      4. Exploring Cellular Automata
      5. Leveraging Chaos Theory in Games
        1. Adding a Second Factor
        2. Selecting the Right Factors
        3. Beyond Booleans
      6. Conclusion
      7. References
    9. 3.8. Needs-Based AI
      1. Background
      2. Needs-Based AI Overview
        1. Needs
      3. Advertisements and Action Selection
        1. Advertisement Decoupling
        2. Advertisement Scoring
        3. Action Selection
        4. Action Selection Additions
      4. Action Performance
        1. Action Chaining
        2. Action Chain State Saving
      5. Design Consequences of Needs-Based AI
      6. Conclusion
      7. Acknowledgements
      8. References
    10. 3.9. A Framework for Emotional Digital Actors
      1. Models of Emotion, Mood, and Personality
        1. Emotion
        2. Mood
        3. Personality
      2. The Emotional Framework
        1. Appraisal/Arousal
        2. Knowledge Representation
        3. The Appraisal Process
          1. Sensing a New Object
          2. Sensing a New Agent
          3. Sensing an Event
      3. Conclusion
      4. References
    11. 3.10. Scalable Dialog Authoring
      1. Conversational Agents Today
        1. Typical Methods for Building Conversational Agents
        2. The Scalability Problem
        3. Unique Personalities and Other Things We Might Want
        4. What We Won’t Cover
      2. Overview
      3. Intention Modeling
        1. Topics, Response Types, and Trust
        2. Concept Hierarchies
      4. Cultural Wrappers
      5. Creating Unique Individuals
      6. Conclusion
    12. 3.11. Graph-Based Data Mining for Player Trace Analysis in MMORPGs
      1. Data Logging and Preprocessing
      2. Advertisement Placement in MMORPGs
        1. Frequency Maximizing Approach
        2. Markov Steady-State Probability-Based Approach
        3. Greedy, Marginal Gain Maximizing Approach
        4. Experimental Comparison
      3. Building Player Profiles with Clustering
        1. Distance Measure
        2. Applying Standard Clustering Algorithms
      4. Detecting Bots and Gold Farmers with Classification Models
        1. Using an LCS-Based Similarity Measure with K-NN
        2. Using an LCS-Based Similarity Measure with SVMs
      5. Conclusion
      6. References
  8. 4. General Programming
    1. Introduction
    2. 4.1. Fast-IsA
      1. Problem Definition
      2. Balanced Class Hierarchies
      3. Eliminating the Tree Traversal
      4. Building a Balanced Tree
      5. Conclusion
    3. 4.2. Registered Variables
      1. Getting Started
      2. Assumptions
        1. TArrays
        2. FNames
      3. The Base Class: RegisteredVar
      4. Single Variable Values versus Array Variable Values
      5. Type-Specific Registered Variable
      6. Setting a Registered Variable Directly
      7. IsA Functionality
      8. Setting a Registered Variable Indirectly
      9. Conclusion
    4. 4.3. Efficient and Scalable Multi-Core Programming
      1. Efficient Multi-Threaded Programming
        1. Shared Data
        2. Atomic Operations
        3. Synchronization Primitives
        4. Memory Ordering
        5. False Sharing
        6. Memory Allocator Contention
        7. Idle Thread State
        8. Thread Local Storage
        9. Lock-Free Algorithms
      2. Scalable Multi-Threaded Programming
        1. Task Scheduler Requirements
        2. Tasks
        3. Worker Threads
        4. Scheduler
        5. Scheduling Slice
        6. Registering Pending Tasks
        7. Scheduling Ready Tasks
        8. Deleting Executed Tasks
      3. Future Work
      4. Optimizations
      5. Conclusion
      6. References
    5. 4.4. Game Optimization through the Lens of Memory and Data Access
      1. Understand the Cache
      2. Pinpoint Problem Areas
      3. Avoid Waste
      4. Shrink the Data
        1. Packed Structures
        2. Compile for Size
      5. Organize the Data
        1. Prefer Compact Contiguous Containers
        2. Separate Hot and Cold Data
      6. Manipulate the Cache
        1. Prefetch Data
        2. Lock the Cache
      7. Conclusion
      8. References
    6. 4.5. Stack Allocation
      1. Overview
      2. Example Implementation
      3. Index-Based Implementation
      4. POD Types
      5. Known Issues
      6. Advantages and Disadvantages
      7. Conclusion
    7. 4.6. Design and Implementation of an In-Game Memory Profiler
      1. Introduction
      2. Memory Profiling Basics
      3. Function Hooking
      4. Call-Stack Generation
      5. Collecting Statistics
      6. Multi-Thread Issues
      7. The Source Code
      8. Conclusion
      9. References
    8. 4.7. A More Informative Error Log Generator
      1. Definition of RTSI
      2. Potential Uses
      3. Setting Up the Code
        1. Loading
        2. Usage
        3. Unloading
      4. Error Logs Redundancy Problem versus Using RTSI
      5. Conclusion
      6. References
    9. 4.8. Code Coverage for QA
      1. Common Approaches
      2. An Analogy: Breakpoint Testing
      3. Code Coverage
      4. Implementation
        1. The Markers
        2. Examples: Applying Markers
        3. The Tracker
        4. Per-Level Coverage Input File
        5. The Manager
      5. QA Interface and Workflow
        1. The GUI
        2. Labels as Hints
        3. Output of Results
        4. QA Workflow
      6. Collecting Results
      7. Possible Expansions
      8. A Post-Mortem
      9. Conclusion
      10. References
    10. 4.9. Domain-Specific Languages in Game Engines
      1. Domain-Specific Languages in Depth
        1. Domain-Specific Languages: Definitions and Examples
        2. The Different Types of Domain-Specific Languages
        3. Advantages of DSLs
        4. Disadvantages of DSLs
        5. Relations between DSL and Game Development
        6. When to Create a New Language
      2. Creating a DSL
        1. Choosing between Types of DSLs
        2. Common Programming Techniques for Building Internal DSLs
        3. Tools Easing Language Construction
      3. Multi-Language Game Engine Development
      4. Integrating DSLs into the Pipeline
        1. Engine Integration through Embedding
        2. Engine Integration through Code Generation
        3. Engine Integration through Interpretation
        4. Engine Integration through a Hybrid Approach
        5. Pipeline Integration through Data Generation
        6. Pipeline Integration through Centralization
      5. Conclusion
      6. References
    11. 4.10. A Flexible User Interface Layout System for Divergent Environments
      1. The Problem
      2. Some Cheap Solutions
      3. A More Flexible Solution
      4. Concatenate Conditional Modifiers and Conditions
      5. Implementation Details of the CM System
      6. Conditional Modifier Condition References
      7. Widget Templates
      8. Proxy Assets
      9. Performance
      10. Problems
      11. Conclusion
      12. References
    12. 4.11. Road Creation for Projectable Terrain Meshes
      1. Roads as Geodesic Curves
        1. Variation Problem for Roads
        2. Numerical Solution for Geodesics
      2. Road Grading Techniques for The Sims 3 Worlds
        1. Blending Roads with Terrain in The Sims 3
        2. Road Grade and Road Slope
        3. Flattening Road Slope
        4. Limiting Road Grade Angle
        5. Results and Possible Generalizations
      3. Conclusion
      4. References
    13. 4.12. Developing for Digital Drawing Tablets
      1. Background
        1. Building a Better Mouse
        2. Applications
      2. Tablet Theory
        1. Working in 3D
        2. Shortcuts and Gestural Interfaces
        3. Gestures and Pie Menus: Marking Menus
      3. Tablet Programming
        1. Getting Started with Wintab
        2. Being a Good Neighbor
        3. Cursor Proximity
        4. Additional Input Axes
        5. Buttons
      4. Conclusion
      5. References
    14. 4.13. Creating a Multi-Threaded Actor-Based Architecture Using Intel® Threading Building Blocks
      1. Introduction
        1. Finding Concurrency in Games
        2. Task Decomposition
        3. State Protection Strategies
      2. Actor-Based Programming
      3. Implementing an Actor Engine
        1. The Task Scheduler
        2. The Message Class
        3. The Actor Class
        4. The Message Queue
        5. Actor Hierarchies
        6. Message Processing
        7. Message Handling
      4. Message-Passing Patterns
        1. Querying for State and Promises
        2. Sequential Message Processing
        3. Message Epochs
      5. Conclusion
      6. References
  9. 5. Networking and Multiplayer
    1. Introduction
    2. 5.1. Secure Channel Communication
      1. Architecture
        1. Code Security
        2. Peer to Peer
        3. Client/Server
        4. Protocol
      2. Network Security
        1. Basic Security Principles
        2. Encryption
        3. Hashes
        4. Complete Secure Protocols
        5. Login
        6. Authentication
        7. Gaming
      3. Attacks
        1. Reverse Engineering
        2. Kernel Mode
        3. Lagging
        4. Other Attacks
      4. Responses
        1. Code Integrity
        2. Kernel Mode Help
        3. Cheat Detection
        4. Continued Vigilance
        5. Backups/Restore
      5. Disciplinary Measures
      6. Examples
        1. WoW
        2. Unreal Tournament
      7. Conclusion
      8. References
    3. 5.2. Social Networks in Games: Playing with Your Facebook Friends
      1. RESTful Web Services
        1. Requesting Data
        2. Authenticating a User
        3. Identifying Your Application
        4. Debugging RESTful Requests
      2. The Facebook API
        1. Setting Up a Facebook Application
        2. Facebook’s REST Server
        3. Authenticating Facebook Users
        4. Authentication with an External Browser
        5. Authentication with an Application-Integrated Browser
        6. Persisting a User Session
        7. Retrieving the Friends List
        8. Posting Messages
      3. Conclusion
      4. References
    4. 5.3. Asynchronous I/O for Scalable Game Servers
      1. Background
        1. Blocking and Non-Blocking Synchronous I/O
        2. Handling Multiple Clients
        3. Thread Carefully
      2. Asynchronous I/O APIs
        1. Implementation
      3. Results and Analysis
      4. Conclusion
      5. References
    5. 5.4. Introduction to 3D Streaming Technology in Massively Multiplayer Online Games
      1. The Problem
      2. The Solution
        1. Video Streaming
        2. Game Streaming
      3. The World
        1. What Constitutes a 3D World
        2. Slice the Land
          1. Patches of Land
          2. Tiles and Height Map
        3. Terrain Generation
      4. The Rendering
        1. Terrain Mesh
        2. Multi-Texture and Alpha Blending
          1. Single Texture
          2. Per-Tile Texturing
          3. Alpha Blending Multi-Layer Textures
        3. Static Shadow
        4. Terrain Objects
        5. Divide and Conquer
      5. The Transport
        1. Data Source and File Object
        2. Asynchronous Loading with Multi-Priority Queues
        3. Transport Protocol
          1. HTTP Compression
          2. HTTP Caching
        4. Leaky Bucket
      6. Predictive Loading
        1. Camera Control
        2. Distance Function
          1. Viewing Frustum-Based Preloading
          2. Distance Function–Based Preloading
          3. Straight Line Distance Function
          4. Probability-Based Distance Function
      7. 3DStreamer: Putting Everything Together
        1. Compile the Source
        2. Terrain Generation
        3. Staging the Data
        4. Run
      8. Conclusion
  10. 6. Audio
    1. Introduction
    2. 6.1. A Practical DSP Radio Effect
      1. The Effect
        1. Cranking Up the Distortion
      2. Automatic Gain Control
      3. Adding Static
        1. Making It Tinny
      4. Putting It All Together
      5. Parameter Animation
      6. Conclusion
    3. 6.2. Empowering Your Audio Team with a Great Engine
      1. Audio Code Building Blocks
      2. Sound Parameterization
        1. Impulse Sounds
        2. Looping Sounds
      3. Mixing
      4. Post-Production
      5. Conclusion
    4. 6.3. Real-Time Sound Synthesis for Rigid Bodies
      1. Modal Analysis and Impulse Responses
        1. Spring-Mass System Construction
        2. Modal Analysis
        3. Impulse Response Calculation
      2. From Physics Engine to Contact Sounds
        1. Event Classification: Transient or Lasting Contacts?
        2. From Transient Contacts to Impulses
        3. From Lasting Contacts to Impulses: Using Normal Maps
      3. Putting It Together
      4. Conclusion
      5. References
  11. 7. General Purpose Computing on GPUs
    1. Introduction
    2. 7.1. Using Heterogeneous Parallel Architectures with OpenCL
      1. OpenCL Primer
      2. Tips for Optimizing OpenCL C Kernels
        1. Convolution Kernel
        2. Loop Unrolling
        3. Invariants
        4. Vectorization
      3. Optimizing Memory-Bound OpenCL Kernels
        1. Number of Work-Groups
        2. Work-Group Size
        3. __global Read/Write Access Patterns
        4. Getting around the Scatter Bottleneck
        5. Optimizing __local Memory Access
      4. OpenCL Command Profiling
      5. Conclusion
      6. References
    3. 7.2. PhysX GPU Rigid Bodies in Batman: Arkham Asylum
      1. Requirements
      2. Shape Representation
      3. Dynamics Algorithm
      4. Pipeline
      5. Transform Spheres into World Space
      6. Sphere-Sphere Collision Detection
      7. Sphere-Mesh Collision Detection
      8. Evaluate Force Fields
      9. Calculate Unconstrained Velocities
      10. Generate Constraints
      11. Solver
        1. Calculate Impulse Required to Prevent Relative Motion Along Constraint Direction i
        2. Clamp the Accumulated Impulse to Satisfy the Signorini Constraint
        3. Apply Impulse to Update the Velocities of the Constrained Bodies
      12. Update Positions
      13. GPU Implementation
      14. CUDA Voxelizer
      15. Spatial Data Structures
      16. Solver
      17. Conclusion
      18. Acknowledgements
      19. References
    4. 7.3. Fast GPU Fluid Simulation in PhysX
      1. Particle Systems
      2. Fluids
      3. Robust Particle Collisions
      4. Fluid Simulation with Smoothed Particle Hydrodynamics
      5. Fluid Simulation Algorithm
        1. Particle Bounds Generation and the Broad Phase
        2. SPH Phase
          1. Hashed Grid Data Structure
          2. Computing Density and Force
          3. Parallel Implementation in CUDA
          4. Particle Collision Phase
          5. Surface Constraint Collision
          6. Collision Detection with Static and Dynamic Shapes
          7. Collision Response and Particle Update
      6. Fluid Rendering
        1. Screen-Space Fluid Rendering
      7. Performance
      8. Acknowledgements
      9. References
  12. Color Plate