Game Engine Gems

Preface
Part I Graphics and Rendering
	Chapter 1 Fast Computation of Tight-Fitting Oriented Bounding Boxes
		1.1   Introduction
		1.2   Algorithm
			Selecting the Extremal Points
			Finding the Axes of the OBB
			Handling Detrimental Cases
		1.3   Evaluation
			Bounding Volume Hierarchy Quality
		1.4   Optimization Using SIMD Instructions
		1.5   Discussion and Future Work
			References
	Chapter 2 Modeling, Lighting, and Rendering Techniques for Volumetric Clouds
		2.1   Modeling Cloud Formation
			Growing Clouds with Cellular Automata
			Simulating the Distribution of Clouds
		2.2   Cloud Lighting Techniques
		2.3   Cloud Rendering Techniques
			Volumetric Splatting
			Volumetric Slicing
			GPU Ray Casting
			Hybrid Approaches
			References
	Chapter 3 Simulation of Night-Vision and Infrared Sensors
		3.1   The Physics of the Infrared
		3.2   Simulating Infrared Sensor Effects
		3.3   Night-Vision Goggle Simulation
			References
	Chapter 4 Screen-Space Classification for Efficient Deferred Shading
		4.1   Introduction
		4.2   Overview of Method
		4.3   Depth-Related Classification
		4.4   Pixel Classification
		4.5   Combining Classification Results
		4.6   Index Buffer Generation
		4.7   Tile Rendering
		4.8   Shader Management
		4.9   Platform Specifics
			Xbox 360
			PlayStation 3
		4.10   Optimizations
			Reducing Shader Count
			Tile Coalescing
		4.11   Performance Comparison
			References
	Chapter 5 Delaying OpenGL Calls
		5.1   Introduction
		5.2   Motivation
		5.3   Possible Implementations
		5.4   Delayed Calls Implementation
		5.5   Implementation Notes
		5.6   Improved Flexibility
		5.7   Concluding Remarks
			Acknowledgements
			References
	Chapter 6 A Framework for GLSL Engine Uniforms
		6.1   Introduction
		6.2   Motivation
		6.3   Implementation
		6.4   Beyond GLSL Built-in Uniforms
		6.5   Implementation Tips
		6.6   Concluding Remarks
			Acknowledgements
	Chapter 7 A Spatial and Temporal Coherence Framework for Real-Time Graphics
		7.1   Introduction
		7.2   The Spatiotemporal Framework
			Bilateral Upsampling
			Reprojection Caching
			Bilateral Filtering
			Spatiotemporal Coherency
		7.3   Applications
			Screen-Space Ambient Occlusion
			Soft Shadows
			Shadows and Ambient Occlusion Combined
			Postprocessing
		7.4   Future Work
			Antialiasing
			High-Quality Spatiotemporal Reconstruction
			References
	Chapter 8 Implementing a Fast DDOF Solver
		8.1   Introduction
		8.2   Modifying the Basic CR Solver
		8.3   Results
			References
	Chapter 9 Automatic Dynamic Stereoscopic 3D
		9.1   General Problems in S3D
			Window Violations
			Convergence Fatigue
			Accommodation/Convergence Deviation
		9.2   Problems in S3D Unique to Games
			Keystone Distortions
			2D Image-Based Effects
			HUD and Subtitles
		9.3   Dynamic Controls
		9.4   A Simple Dynamic S3D Camera
			Camera Target Tracking
			Dynamic Parallax Separation
		9.5   Content-Adaptive Feedback
			References
	Chapter 10 Practical Stereo Rendering
		10.1   Introduction to Stereo 3D
		10.2   Overview of Stereo Displays
		10.3   Introduction to Rendering Stereo
		10.4   The Mathematics of Stereo Views and Projection
		10.5   Using Geometry Shader to Render Stereo Pairs
			References
	Chapter 11 Making 3D Stereoscopic Games
		11.1   Introduction
		11.2   How Stereoscopic 3D Works
		11.3   How to Set Up the Virtual 3D Cameras
		11.4   Safe Area
		11.5   Technical Considerations
		11.6   Same Scene, Both Eyes, and How to Optimize
		11.7   Scene Traversal
		11.8   Supporting Both Monoscopic and Stereoscopic Versions
		11.9   Visual Quality
			Stereo Coherence
			Fast Action
			3D Slider
			Color Enhancement
			Crosstalk Reduction
		11.10   Going One Step Further
		11.11   Conclusion
			References
	Chapter 12 A Generic Multiview Rendering Engine Architecture
		12.1   Introduction
		12.2   Analyzing Multiview Displays
		12.3   The Architecture
		12.4   The Multiview Camera
		12.5   The Multiview Buffer
		12.6   The Multiview Compositor
		12.7   Rendering Management
			Shared Data between Different Views
		12.8   Rendering Optimizations
			Multiview Level-of-Detail for Objects
			Multiview Level-of-Detail for Multiview Buffers
			Other Optimization Approaches
		12.9   Discussion
			Multiview Scene Setup
			Enabling/Disabling Multiview Rendering at Run Time
			Postprocessing Pipelines
			Integration with Other Stereo-Rendering APIs
			3D Video Playback
			Using Multiview Pipeline for Other Rendering Techniques
			Acknowledgements
			References
	Chapter 13 3D in a Web Browser
		13.1   A Brief History
		13.2   Fast Forward
		13.3   3D with Flash
		13.4   3D with Java
		13.5   3D with a Game Engine Plug-In
		13.6   Google Native Client
		13.7   3D with HTMLS
		13.8   Conclusion
			References
	Chapter 14 2D Magic
		14.1   Tools of the Trade
		14.2   Position
			Scale Effects
			Motion Effects
			Perspective Effects
		14.3   Color and Opacity
			Colored UI Model
			Opacity Separate from Color
			Interpolation
			Day and Night
		14.4   Texture (UV) Coordinates
			UI Frames
			Texture Scrolling
			Texture Sheets
		14.5   What a Mesh!
		14.6   Mesh Architecture
			Mesh
			Space
			State
			Modifiers
		14.7   Mesh Examples
			Point Light
			Sunrise and Double Rainbows
			Flashlight
			Pinch
			Optimization
		14.8   Conclusion
			Acknowledgements
			References
Part II Game Engine Design
	Chapter 15 High-Performance Programming with Data-Oriented Design
		15.1   Modern Hardware
		15.2   Principles of Data-Oriented Design
		15.3   Data-Oriented Design Benefits
		15.4   How to Apply Data-Oriented Design
		15.5   Real-World Situations
			Homogeneous, Sequential Data
			Heterogeneous Data
			Break and Batch
			Conditional Execution
			Polymorphism
		15.6   Parallelization
		15.7   Conclusion
	Chapter 16 Game Tuning Infrastructure
		16.1   Introduction
		16.2   The Need for Tweak
		16.3   Design Considerations
		16.4   The Tuning Tool
			Using the Debugger
			Using a Console Window
			Integrating with an Existing DCC1 Tool
			Dedicated Editor Application
		16.5   Data Exchange
			Direct Value Access
			Interprocess Communication
			Cross-Platform Communication
		16.6   Schema and Exposure
			Marking Tunable Variables
			Reflection
			Explicit Definition
		16.7   Data Storage
			Text or Binary
			Divide and Conquer
			Supporting Structure Changes
			File Format
			Writing Data
		16.8   Case Studies
			Quraish
			Unreal 3/Unreal Development Kit
		16.9   Final Words
			Acknowledgements
			References
	Chapter 17 Placeholders beyond Static Art Replacement
		17.1   Placeholder Assets in a Game
			Placeholders as Development Productivity Tools
			Desired Features of a Placeholder System
		17.2   Preaching by Example: The Articulated Placeholder Model
			Skeleton Construction
			Placeholder Mesh Generation with implicit Surfaces
			Automatic Vertex Weight Assignment
			Skinning
			Limitations
		17.3   Integration in a Production Environment
			Who Makes It, and Where Do You Make It?
			Game Pipeline Integration
		17.4   In the End, Is It Really Needed?
		17.5   Implementation
			References
	Chapter 18 Believable Dead Reckoning for Networked Games
		18.1   Introduction
		18.2   Fundamentals
			Myth Busting-Ground Truth
			Basic Math
			Myth Busting-Discontinuities Are Not Minor
		18.3   Pick an Algorithm, Any Algorithm
			Projective Velocity Blending
			Prove It!
		18.4   Time for T
			What Time Is It?
			Time to Put It Together
			Just in Time Notes
		18.5   Publish or Perish
			When to Publish?
			What to Publish
			Myth Busting-Acceleration Is Not Always Your Friend
			Publishing Tips
			The Whole Story
		18.6   Ground Clamping
			Can We Fix It?
			Other Considerations
		18.7   Orientation
			Myth Busting-Quaternions
			Two Wrong Turns Don't Make a Right
		18.8   Advanced Topics
			Integrating Physics with Dead Reckoning
			Server Validation
			Who Hit Who?
			Articulations
			Path-Based Dead Reckoning
			Delayed Dead Reckoning
			Subscription Zones
		18.9   Conclusion
			Acknowledgements
			References
	Chapter 19 An Egocentric Motion Management System
		19.1   Fundamental Components of the ECMMS
		19.2   Collision Sensors
		19.3   Query Space
			Query Space Allows for an Understanding of Space
		19.4   Modeling the Environment
		19.5   The ECMMS Architecture
		19.6   Modeling an ECMMS-Enabled Agent
		19.7   Generating a Behavior Model with the ECMMS
		19.8   Animation Validation
		19.9   A Single Agent Behavioral Response Algorithm and Example
			References
	Chapter 20 Pointer Patching Assets
		20.1   Introduction
			Bad Solutions
			Analysis
			An Alternative, High-Performance, Solution
			Considerations
		20.2   Overview of the Technique
			Desirable Properties
		20.3   A Brief Example
			Tools Side
			The Run-Time Pointer Patching Process
	Chapter 21 Data-Driven Sound Pack Loading and Organization
		21.1   Introduction
		21.2   Constructing a Sound Map
		21.3   Constructing Sound Packs by Analyzing the Event Table
			Determining Which Sound Events to Stream
			Constructing Sound Packs
		21.4   Constructing and Using Sound Loading Triggers
			Optimizing Sound Loaders
			Out of Memory Detection
			Loading Sound Packs While Running the Game
		21.5   Conclusion
	Chapter 22 GPGPU Cloth Simulation Using GLSL, OpenCL, and CUDA
		22.1   Introduction
		22.2   Numerical Algorithm
		22.3   Collision Handling
		22.4   CPU Implementation
		22.5   GPU Implementations
		22.6   GLSL Implementation
		22.7   CUDA Implementation
		22.8   OpenCL Implementation
		22.9   Results
		22.10   Future Work
		22.11   Demo
			Acknowledgements
			References
	Chapter 23 A Jitter-Tolerant Rigid Body Sleep Condition
		23.1   Introduction
		23.2   The Sleep Condition
Part III Systems Programming
	Chapter 24 Bit Hacks for Games
		24.1   Integer Sign Manipulation
			Absolute Value
			Sign Function
			Sign Extension
		24.2   Predicates
			Conditional Increment and Decrement
			Conditional Addition and Subtraction
			Increment or Decrement Modulo N
			Clamping to Zero
			Minimum and Maximum
		24.3   Miscellaneous Tricks
			Clear the Least Significant 1 Bit
			Test for Power of Two
			Test for Power of Two Minus One
			Determine Whether a Voxel Contains Triangles
			Determine the Index of the Greatest Value in a Set of Three
		24.4   Logic Formulas
			References
	Chapter 25 Introspection for C++ Game Engines
		25.1   Introduction
		25.2   The Demo
		25.3   The Gem
		25.4   Lifting the Veil
		25.5   To and From a Network
		25.6   In Closing
	Chapter 26 A Highly Optimized Portable Memory Manager
		26.1   Introduction
			Alternatives to Rolling Your Own
			Desirable Properties
		26.2   Overview
			Fighting Fragmentation Is Job #1
			Paged Allocation
			Easing Portability with the OSAPI Class
		26.3   Small Block Allocator
			How Alloc() Works
			How Free() Works
			Performance Analysis
			Memory Overhead
		26.4   Medium Block Allocator
			How Alloc() Works
			How Free() Works
			Performance Analysis
			Memory Overhead
		26.5   Large Block Allocator
		26.6   Page Management in the Memory Manager
			SBA Pages
			MBA Pages
		26.7   OSAPI Ideas
	Chapter 27 Simple Remote Heaps
		27.1   Introduction
			Considerations
		27.2   Bitwise Remote Heap
			Overview
			Algorithm
		27.3   Blockwise Remote Heap
			Overview
			Algorithm
		27.4   Testing Results
			Memory Efficiency
			Performance
	Chapter 28 A Cache-Aware Hybrid Sorter
		28.1   Stream Splitting
		28.2   Substream Sorting
		28.3   Stream Merging and Loser Tree
		28.4   Multicore Implementation
			Parallel Loser Tree
		28.5   Conclusion
			Appendix
			Acknowledgements
			References
	Chapter 29 Thread Communication Techniques
		29.1   Latency and Threading
		29.2   Single Writer, Single Reader
		29.3   The Aggregator
		29.4   The Dispatcher
		29.5   The Gateway
		29.6   Debugging
			References
	Chapter 30 A Cross-Platform Multithreading Framework
		30.1   Threading
			ThreadManager
			ThreadInfo
		30.2   Synchronization Objects
			Critical Section (class BasicSection)
			Mutex (class BasicMutex)
			Semaphore (class BasicSemaphore)
			Event (class BasicEvent)
			Wait Objects
			Lock Helper Classes
			Waiting for Multiple Objects
		30.3   Limitations
		30.4   Future Extensions
			References
	Chapter 31 Producer-Consumer Queues
		31.1   Introduction
		31.2   Multithreading Overview
		31.3   A First Approach: Using Win32 Semaphores and Critical Sections
		31.4   A Second Approach: Lock-Free Algorithms
		31.5   Processor Architecture Overview and Memory Models
		31.6   Lock-Free Algorithm Design
		31.7   Lock-Free Implementation of a Free List
		31.8   Lock-Free Implementation of a Queue
		31.9   Interprocess Communication
			References