Game Programming Gems 1

SECTION 1 PROGRAMMING TECHNIQUES

//z 2014-07-18 17:12:26 L.166'24454 BG57IV3@XCL T2649809119.K.F1752546504[T8,L150,R7,V167]

1.0	The Magic of Data-Driven Design
1.1	Object-Oriented Programming and Design Techniques
1.2	Fast Math Using Template Metaprogramming
1.3	An Automatic Singleton Utility
1.4	Using the STL in Game Programming
1.5	A Generic Function-Binding Interface
1.6	A Generic Handle-Based Resource Manager
1.7	Resource and Memory Management
1.8	Fast Data Load Trick
1.9	Frame-Based Memory Allocation
1.10	Simple, Fast Bit Arrays
1.11	A Network Protocol for Online Games
1.12	Squeezing More Out of Assert
1.13	Stats: Real-Time Statistics and In-Game Debugging
1.14	Real-Time In-Game Profiling

SECTION 2 MATHEMATICS

2.0	Predictable Random Numbers
2.1	Interpolation Methods
2.2	Integrating the Equations of Rigid Body Motion
2.3	Polynomial Approximations to Trigonometric Functions
2.4	Using Implicit Euler Integration for Numerical Stability
2.5	Wavelets: Theory and Compression
2.6	Interactive Simulation of Water Surfaces
2.7	Quaternions for Game Programming
2.8	Matrix-Quaternion Conversions
2.9	Interpolating Quaternions
2.10	The Shortest Arc Quaternion

SECTION 3 ARTIFICIAL INTELLIGENCE

3.0	Designing a General Robust AI Engine
3.1	A Finite-State Machine Class
3.2	Game Trees
3.3	The Basics of A* for Path Planning
3.4	A* Aesthetic Optimizations
3.5	A* Speed Optimizations
3.6	Simplified 3D Movement and Pathfinding Using Navigation Meshes
3.7	Flocking: A Simple Technique for Simulating Group Behavior
3.8	Fuzzy Logic for Video Games
3.9	A Neural-Net Primer

SECTION 4 POLYGONOL TECHNIQUES

4.0	Optimizing Vertex Submissions for OpenGL
4.1	Tweaking A Vertex’s Projected Depth Value
4.2	The Vector Camera
4.3	Camera Control Techniques
4.4	A Fast Cylinder-Frustum Intersection Test
4.5	3D Collision Detection
4.6	Multi-Resolution Maps for Interaction Detection
4.7	Computing the Distance into a Sector
4.8	Object Occlusion Culling
4.9	Never Let ‘Em See You Pop - Issues in Geometric Level of Detail Selection
4.10	Octree Construction
4.11	Loose Octrees
4.12	View-Independent Progressive Meshing
4.13	Interpolated 3D Keyframe Animation
4.14	A Fast and Simple Skinning Techniques
4.15	Filling the Gaps - Advanced Animation Using Stitching and Skinning
4.16	Real-Time Realistic Terrain Generation
4.17	Fractal Terrain Generation - Fault Formation
4.18	Fractal Terrain Generation - Midpoint Displacement
4.19	Fractal Terrain Generation - Particle Deposition

SECTION 5 PIXEL EFFECTS

5.0	2D Lens Flare
5.1	Using 3D Hardware for 2D Sprite Effects
5.2	Motif-Based Static Lighting
5.3	Simulated Real-Time Lighting Using Vertex Color Interpolation
5.4	Attenuation Maps
5.5	Advanced Texturing Using Texture Coordinate Generation
5.6	Hardware Bump Mapping
5.7	Ground-Plane Shadows
5.8	Real-Time Shadows on Complex Objects
5.9	Improving Environment-Mapped Reflection Using Glossy Prefiltering and the Fresnel Term
5.10	Convincing-Looking Glass for Games
5.11	Refraction Mapping for Liquids in Containers

SECTION 6 APPENDIX

6.0	The Matrix Utility Library
6.1	The Text Utility Library
6.2	About the CD-ROM

Index

Game Programming Gems 2

Preface		(xxi)
About the Cover Image		(xxv)
Author Bios		(xxvii)

SECTION 1 GENERAL PROGRAMMING (1)

Introduction: General Programming		(3)
1.1	Optimization for C++ Games	(5)
1.2	Inline Functions Versus Macros	(16)
1.3	Programming with Abstract Interfaces	(5)
1.4	Exporting C++ Classes from DLLs	(28)
1.5	Protect Yourself from DLL Hell and Missing OS Functions	(33)
1.6	Dynamic Type Information	(38)
1.7	A Property Class for Generic C++ Member Access	(46)
1.8	A Game Entity Factory	(51)
1.9	Adding Deprecation Facilities to C++	(62)
1.10	A Drop-in Debug Memory Manager	(66)
1.11	A Built-in Game Profiling Module	(74)
1.12	Linear Programming Model for Windows-based Games	(80)
1.13	Stack Winding	(85)
1.14	Self-Modifying Code	(91)
1.15	File Management Using Resource Files	(100)
1.16	Game input Recording and Playback	(105)
1.17	A Flexible Text Parsing System	(112)
1.18	A Generic Tweaker	(118)
1.19	Genuine Random Number Generation	(127)
1.20	Using Bloom Filters to improve Computational Performance	(133)
1.21	3ds max Skin Exporter and Animation Toolkit	(141)
1.22	Using Web Cameras in Video Games	(153)

SECTION 2 MATHEMATICS (163)

Introduction: Mathematics		(165)
2.1	Floating-Point Tricks: Improving Performance with IEEE Floating Point	(167)
2.2	Vector and Plane Tricks	(182)
2.3	Fast, Robust Intersection of 3D Line Segments	(191)
2.4	Inverse Trajectory Determination	(205)
2.5	The Parallel Transport Frame	(215)
2.6	Smooth C2 Quaternion-based Flythrough Paths	(220)
2.7	Recursive Dimensional CLustering: A Fast Algorithm for Collision Detection	(228)
2.8	Programming Fractals	(239)

SECTION 3 ARTIFICIAL INTELLIGENCE (247)

Introduction: Artificial Intelligence		(249)
3.1	Strategies for Optimizing AI	(251)
3.2	Micro-Threads for Game Object AI	(258)
3.3	Managing AI with Micro-Threads	(265)
3.4	An Architecture for RTS Command Queuing	(273)
3.5	A High-Performance Tile-Based Line-of-Sight and Search System	(279)
3.6	Influence Mapping	(287)
3.7	Strategic Assessment Techniques	(298)
3.8	Terrain Reasoning for 3D Action Games	(307)
3.9	Expanded Geometry for Points-of-Visibility Pathfinding	(317)
3.10	Optimizing Points-of-Visibility Pathfinding	(324)
3.11	Flocking with Teeth: Predators and Prey	(330)
3.12	A Generic Fuzzy State Machine in C++	(337)
3.13	Imploding Combinatorial Explosion in a Fuzzy System	(342)
3.14	Using a Neutral Network in a Game: A Concrete Example	(351)

SECTION 4 GEOMETRY MANAGEMENT (359)

Introduction: Geometry Management		(361)
4.1	Comparison of VIPM Methods	(363)
4.2	Simplified Terrain Using Interlocking Tiles	(377)
4.3	Sphere Trees for Fast Visibility Culling, Ray Tracing and Range Searching	(384)
4.4	Compressed Axis-Aligned Bounding Box Trees	(388)
4.5	Direct Access Quadtree Lookup	(394)
4.6	Approximating Fish Tank Refractions	(402)
4.7	Rendering Print Resolution Screenshots	(406)
4.8	Applying Decals to Arbitrary Surfaces	(411)
4.9	Rendering Distans Scenery with Skyboxes	(416)
4.10	Self-Shadowing Characters	(421)
4.11	Classic Super Mario 64 Third-Person Control and Animation	(425)

SECTION 5 GRAPHICS DISPLAY (433)

Introduction: Graphics Display		(435)
5.1	Cartoon Rendering: Real-Time Silhouette Edge Detection and Rendering	(436)
5.2	Cartoon Rendering Using Texture Mapping and Programmable Vertex Shaders	(444)
5.3	Dynamix Per-Pixel Lighting Technique	(452)
5.4	Generating Procedural Clouds using 3D Hardware	(463)
5.5	Texture Masking for Faster Lens Flare	(474)
5.6	Practical Priority Buffer Shadows	(481)
5.7	Impostors: Adding Clutter	(488)
5.8	Operations for Hardware-Accelerated Procedural Texture Animation	(497)

Game Programming Gems 3

Foreword		(xi)
Preface		(xv)
Acknowledgments		(xix)
About the Cover Image		(xxi)
Contributor Bios		(xxiii)

SECTION 1 GENERAL PROGRAMMING (1)

Introduction		(3)
1.1	Scheduling Game Events	(5)
1.2	An Object-Composition Game Framework	(15)
1.3	Finding Redeeming Value in C-Style Macros	(26)
1.4	Platform-Independent, Function-Binding Code Generator	(38)
1.5	Handle-Based Smart Pointers	(44)
1.6	Custom STL Allocators	(49)
1.7	Save Me Now	(59)
1.8	Autolists Design Pattern	(64)
1.9	Floating-Point Exception Handling	(69)
1.10	Programming a Game Design-Compliant Engine Using UML	(73)
1.11	Using Lex and Yacc To Parse Custom Data Files	(83)
1.12	Developing Games for a World Market	(92)
1.13	Real-Time Input and UI in 3D Games	(109)
1.14	Natural Selection: The Evolution of Pie Menus	(117)
1.15	Lightweight, Policy-Based Logging	(129)
1.16	Journaling Services	(136)
1.17	Real-Time Hierarchical Profiling	(146)

SECTION 2 MATHEMATICS (153)

Introduction		(155)
2.1	Fast Base-2 Functions for Logarithms and Random Number Generation	(157)
2.2	Using Vector Fractions for Exact Geometry	(160)
2.3	More Approximations to Trigonometric Functions	(170)
2.4	Quaternion Compression	(187)
2.5	Constrained Inverse Kinematics	(192)
2.6	Cellular Automata for Physical Modeling	(200)
2.7	Coping with Friction in Dynamic Simulations	(215)

SECTION 3 ARTIFICIAL INTELLIGENCE (227)

Introduction		(229)
3.1	Optimized Machine Learning with GoCap	(231)
3.2	Area Navigation: Expanding the Path-Finding Paradigm	(240)
3.3	Function Pointer-Based, Embedded Finite-State Machines	(256)
3.4	Terrain Analysis in an RTS-The Hidden Giant	(268)
3.5	An Extensible Trigger System for AI Agents, Objects, and Quests	(285)
3.6	Tactical Path-Finding with A	(294)
3.7	A Fast Approach to Navigation Meshes	(307)
3.8	Choosing a Relationship Between Path-Finding and Collision	(321)

SECTION 4 GRAPHICS (333)

Introduction		(335)
4.1	T-Junction Elimination and Retriangulation	(338)
4.2	Fast Heightfield Normal Calculation	(344)
4.3	Fast Patch Normals	(349)
4.4	Fast and Simple Occlusion Culling	(353)
4.5	Triangle Strip Creation, Optimizations, and Rendering	(359)
4.6	Computing Optimized Shadow Volumes for Complex Data Sets	(367)
4.7	Subdivision Surfaces for Character Animation	(372)
4.8	Improved Deformation of Bones	(384)
4.9	A Framework for Realistic Character Locomotion	(394)
4.10	A Programmable Vertex Shader Compiler	(404)
4.11	Billboard Beams	(413)
4.12	3D Tricks for Isometric Engines	(417)
4.13	Curvature Simulation Using Normal Maps	(424)
4.14	Methods for Dynamic, Photorealistic Terrain Lighting	(433)
4.15	Cube Map Lighting Techniques	(444)
4.16	Procedural Texturing	(452)
4.17	Unique Textures	(459)
4.18	Textures as Lookup Tables for Per-Pixel Lighting Computations	(467)
4.19	Rendering with Handcrafted Shading Models	(477)

SECTION 5 NETWORK AND MULTIPLAYER (485)

Introduction		(487)
5.1	Minimizing Latency in Real-Time Strategy Games	(488)
5.2	Real-Time Strategy Network Protocol	(496)
5.3	A Flexible Simulation Architecture for Massively Multiplayer Games	(506)
5.4	Scaling Multiplayer Servers	(520)
5.5	Template-Based Object Serialization	(534)
5.6	Secure Sockets	(546)
5.7	A Network Monitoring and Simulation Tool	(557)
5.8	Creating Multiplayer Games with DirectPlay 8.1	(561)
5.9	Wireless Gaming Using the Java Micro Edition	(573)

SECTION 6 AUDIO (583)

Introduction		(585)
6.1	Audio Compression with Ogg Vorbis	(587)
6.2	Creating a Compelling 3D Audio Environment	(595)
6.3	Obstruction Using Axis-Aligned Bounding Boxes	(600)
6.4	Using the Biquad Resonant Filter	(606)
6.5	Linear Predictive Coding for Voice Compression and Effects	(613)
6.6	The Stochastic Synthesis of Complex Sounds	(622)
6.7	Real-Time Modular Audio Processing for Games	(630)

Appendix: About the CD-ROM		(639)
Contents

Game Programming Gems 4

Foreword		(xi)
Preface		(xv)
Acknowledgments		(xvii)
About the Cover Image		(xix)
Contributor Bios		(xxi)

SECTION 1 GENERAL PROGRAMMING (1)

Introduction		(3)
1.1	The Science of Debugging Games	(5)
1.2	An HTML-Based Logging and Debugging System	(19)
1.3	The Clock: Keeping Your Finger on the Pulse of the Game	(27)
1.4	Designing and Maintaining Large Cross-Platform Libraries	(35)
1.5	Fight Memory Fragmentation with Templated Freelists	(43)
1.6	A Generic Tree Container in C++	(51)
1.7	The Beauty of Weak References and Null Objects	(61)
1.8	A System for Managing Game Entities	(69)
1.9	Address-Space Managed Dynamic Arrays for Windows and the Xbox	(85)
1.10	Critically Damped Ease-In/Ease-Out Smoothing	(95)
1.11	A Flexible, On-the-Fly Object Manager	(103)
1.12	Using Custom RTTI Properties to Stream and Edit Objects	(111)
1.13	Using XML without Sacrificing Speed	(125)

SECTION 2 MATHEMATICS (137)

Introduction		(139)
2.1	Zobrist Hash Using the Mersenne Twister	(141)
2.2	Extracting Frustum and Camera Information	(147)
2.3	Solving Accuracy Problems in Large World Coordinates	(157)
2.4	Nonuniform Splines	(171)
2.5	Using the Covariance Matrix for Better-Fitting Bounding Objects	(183)
2.6	The Jacobian Transpose Method for Inverse Kinematics	(193)

SECTION 3 PHYSICS (205)

Introduction		(207)
3.1	Ten Fingers of Death: Algorithms for Combat Killing	(209)
3.2	Vehicle Physics Simulation for CPU-Limited Systems	(221)
3.3	Writing a Verlet-Based Physics Engine	(231)
3.4	Constraints in Rigid Body Dynamics	(241)
3.5	Fast Contact Reduction for Dynamics Simulation	(253)
3.6	Interactive Water Surfaces	(265)
3.7	Fast Deformations with Multilayered Physics	(275)
3.8	Modal Analysis for Fast, Stable Deformation	(287)

SECTION 4 ARTIFICIAL INTELLIGENCE (299)

Introduction		(301)
4.1	Third-Person Camera Navigation	(303)
4.2	Narrative Combat: Using AI to Enhance Tension in an Action Game	315
4.3	NPC Decision Making: Dealing with Randomness	(325)
4.4	An Object-Oriented Utility-Based Decision Architecture	(337)
4.5	A Distributed-Reasoning Voting Architecture	(345)
4.6	Attractors and Repulsors	(355)
4.7	Advanced Wall Building for RTS Games	(365)
4.8	Artificial Neural Networks on Programmable Graphics Hardware	(373)

SECTION 5 GRAPHICS (379)

Introduction		(381)
5.1	Poster Quality Screenshots	(383)
5.2	GPU Shadow Volume Construction for Nonclosed Meshes	(393)
5.3	Perspective Shadow Maps	(399)
5.4	Combined Depth and ID-Based Shadow Buffers	(411)
5.5	Carving Static Shadows into Geometry	(427)
5.8	Techniques to Apply Team Colors to 3D Models	(451)
5.9	Fast Sepia Tone Conversion	(461)
5.10	Dynamic Gamma Using Sampled Scene Luminance	(465)
5.11	Heat and Haze Post-Processing Effects	(477)
5.13	Motion Capture Data Compression	(497)
5.14	Fast Collision Detection for 3D Bones-Based Articulated Characters	(503)
5.15	Terrain Occlusion Culling with Horizons	(515)

SECTION 6 NETWORK AND MULTIPLAYER (529)

Introduction		(531)
6.1	General Lobby Design and Development	(533)
6.2	Thousands of Clients per Server	(541)
6.3	Efficient MMP Game State Storage	(555)
6.4	Practical Application of Parallel-State Machines in a Client-Server Environment	(563)
6.5	Bit Packing: A Network Compression Technique	(571)
6.6	Time and Consistency Management for Multiserver-Based MMORPGs	(579)

SECTION 7 AUDIO (591)

Introduction		(593)
7.1	A Brief Introduction to OpenAL	(595)
7.2	A Simple Real-Time Lip-Synching System	(607)
7.3	Dynamic Variables and Audio Programming	(613)
7.4	Creating an Audio Scripting System	(621)
7.5	Implementing an Environmental Audio Solution Using EAX and ZoomFX	(633)
7.6	Controlling Real-Time Sound Synthesis from Game Physics	(649)

APPENDIX: ABOUT THE CD-ROM		(657)
INDEX		(659)

Game Programming Gems 5

Foreword		(xi)
Preface		(xv)
About the Cover Image		(xix)
Contributor Bios		(xxi)

SECTION 1 GENERAL PROGRAMMING (1)

Introduction		(3)
1.1	Context-Sensitive HUDs for Editors	(5)
1.2	Parsing Text Data in Games	(17)
1.3	Component Based Object Management	(25)
1.4	Using Templates for Reflection in C++	(39)
1.5	Sphere Trees for Speedy BSPs	(55)
1.6	Improved Frustum Culling	(65)
1.7	Generic Pager	(79)
1.8	Large-Scale Stack-Based State Machines	(93)
1.9	CSG Construction Using BSP Trees	(103)
1.10	Building Lua into Games	(115)
1.11	Improving Freelists with Policy Based Design	(129)
1.12	A Real-Time Remote Debug Message Logger	(143)
1.13	A Transparent Class Saving and Loading Trick	(149)
1.14	An Effective Cache-Oblivious Implementation of the ABT Tree	(159)
1.15	Visual Design of State Machines	(169)
1.16	A Generic Component Library	(177)
1.17	Choose Your Path-A Menu System	(189)

SECTION 2 MATHEMATICS (197)

Introduction		(199)
2.1	Using Geometric Algebra for Computer Graphics	(201)
2.2	Minimal Acceleration Hermite Curves	(225)
2.3	Spline-Based Time Control for Animation	(233)
2.4	Faster Quaternion Interpolation Using Approximations	(247)
2.5	Minimax Numerical Approximation	(269)
2.6	Oblique View Frustums for Mirrors and Portals	(281)

SECTION 3 ARTIFICIAL INTELLIGENCE (295)

Introduction		(297)
3.1	Automatic Cover Finding with Navigation Meshes	(299)
3.2	Fast Target Ranking Using an Artificial Potential Field	(307)
3.3	Using Lanchester Attrition Models to Predict the Results of Combat	(317)
3.4	Implementing Practical Planning for Game AI	(329)
3.5	Optimizing a Decision Tree Query Algorithm for Multithreaded Architectures	(345)
3.6	Parallel AI Development with PVM	(353)
3.7	Beyond A	(367)
3.8	Advanced Pathfinding with Minimal Replanning Cost: Dynamic A Star (D*)	(383)

SECTION 4 PHYSICS (391)

Introduction		(393)
4.1	Back of the Envelope Aerodynamics for Game Physics	(395)
4.2	Dynamic Grass Simulation and Other Natural Effects	(411)
4.3	Realistic Cloth Animation Using the Mass-Spring Model	(421)
4.4	Practical Animation of Soft Bodies for Game Development: The Pressurized Soft-Body Model	(435)
4.5	Adding Life to Ragdoll Simulation Using Feedback Control Systems	(449)
4.6	Designing a Prescripted Physics System	(457)
4.7	Prescripted Physics: Techniques and Applications	(473)
4.8	Realistic Camera Movement in a 3D Car Simulator	(483)

SECTION 5 GRAPHICS (495)

Introduction		(497)
5.1	Realistic Cloud Rendering on Modern GPUs	(499)
5.2	Let It Snow, Let It Snow, Let It Snow (and Rain	(507)
5.3	Widgets: Rendering Fast and Persistent Foliage	(515)
5.4	2.5 Dimensional Impostors for Realistic Trees and Forests	(527)
5.5	Gridless Controllable Fire	(539)
5.6	Powerful Explosion Effects Using Billboard Particles	(551)
5.7	A Simple Method for Rendering Gemstones	(561)
5.8	Volumetric Post-Processing	(571)
5.9	Procedural Level Generation	(579)
5.10	Recombinant Shaders	(589)

SECTION 6 NETWORK AND MULTIPLAYER (599)

Introduction		(601)
6.1	Keeping a Massively Multiplayer Online Game Massive, Online, and Persistent	(603)
6.2	Implementing a Seamless World Server	(611)
6.3	Designing a Vulgarity Filtering System	(621)
6.4	Fast and Efficient Implementation of a Remote Procedure Call System	(627)
6.5	Overcoming Network Address Translation in Peer-to-Peer Communications	(643)
6.6	A Reliable Messaging Protocol	(665)
6.7	Safe Random Number Systems	(673)
6.8	Secure by Design	(681)

SECTION 7 AUDIO (693)

Introduction		(695)
7.1	Multithreaded Audio Programming Techniques	(697)
7.2	Sound Management by Group	(713)
7.3	Using 3D Surfaces as Audio Emitters	(721)
7.4	Fast Environmental Reverb Based on Feedback Delay Networks	(729)
7.5	Introduction to Single-Speaker Speech Recognition	(741)

About the CD-ROM		(751)
Index		(753)

Game Programming Gems 6

Foreword		(xi)
Preface		(xv)
About the Cover Image		(xxi)
Contributor Bios		(xxiii)

SECTION 1 GENERAL PROGRAMMING (1)

Introduction		(3)
1.1	Lock-Free Algorithms	(5)
1.2	Utilizing Multicore Processors with OpenMP	(17)
1.3	Computer Vision in Games Using the OpenCV Library	(25)
1.4	Geographic Grid Registration of Game Objects	(39)
1.5	BSP Techniques	(49)
1.6	Closest-String Matching Algorithm	(69)
1.7	Using CppUnit To Implement Unit Testing	(79)
1.8	Fingerprinting Pre-Release Builds To Deter and Detect Piracy	(97)
1.9	Faster File Loading with Access-Based File Reordering	(103)
1.10	Stay in the Game: Asset Hotloading for Fast Iteration	(109)

SECTION 2 MATHEMATICS AND PHYSICS (117)

Introduction		(119)
2.1	Floating-Point Tricks	(121)
2.2	GPU Computation in Projective Space Using Homogeneous Coordinates	(137)
2.3	Solving Systems of Linear Equations Using the Cross Product	(149)
2.4	Sequence Indexing for Game Development	(161)
2.5	Exact Buoyancy for Polyhedra	(175)
2.6	Real-Time Particle-Based Fluid Simulation with Rigid Body Interaction	(189)

SECTION 3 ARTIFICIAL INTELLIGENCE (207)

Introduction		(209)
3.1	Applying Model-Based Decision-Making Methods to Games: Applying the Locust AI Engine to QuakeŽ III	(211)
3.2	Achieving Coordination with Autonomous NPCs	(223)
3.3	Behavior-Based Robotic Architectures for Games	(235)
3.4	Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Extended Behavior Networks	(245)
3.5	A Goal-Oriented Unreal Bot: Building a Game Agent with Goal-Oriented Behavior and Simple Personality Using Extended Behavior Networks	(259)
3.6	Short-Term Memory Modeling Using a Support Vector Machine	(273)
3.7	Using the Quantified Judgment Model for Engagement Analysis	(283)
3.8	Designing a Multilayer, Pluggable AI Engine	(291)
3.9	A Fuzzy-Control Approach to Managing Scene Complexity	(307)

SECTION 4 SCRIPTING AND DATA-DRIVEN SYSTEMS (317)

Introduction		(319)
4.1	Scripting Language Survey	(323)
4.2	Binding C/C++ Objects to Lua	(341)
4.3	Programming Advanced Control Mechanisms with Lua Coroutines	(357)
4.4	Managing High-Level Script Execution Within Multithreaded Environments	(371)
4.5	Exposing Actor Properties Using Nonintrusive Proxies	(383)
4.6	Game Object Component System	(393)

SECTION 5 GRAPHICS (405)

Introduction		(407)
5.1	Synthesis of Realistic Idle Motion for Interactive Characters	(409)
5.2	Spatial Partitioning Using an Adaptive Binary Tree	(423)
5.3	Enhanced Object Culling with (Almost) Oriented Bounding Boxes	(437)
5.4	Skin Splitting for Optimal Rendering	(449)
5.5	GPU Terrain Rendering	(461)
5.6	Interactive Fluid Dynamics and Rendering on the GPU	(473)
5.7	Fast Per-Pixel Lighting with Many Lights	(489)
5.8	Rendering Road Signs Sharply	(501)
5.9	Practical Sky Rendering for Games	(517)
5.10	High Dynamic Range Rendering Using OpenGL Frame Buffer Objects	(529)

SECTION 6 AUDIO (537)

Introduction		(539)
6.1	Real-Time Sound Generation from Deformable Meshes	(541)
6.2	A Lightweight Generator for Real-Time Sound Effects	(549)
6.3	Real-Time Mixing Busses	(555)
6.4	Potentially Audible Sets	(561)
6.5	A Cheap Doppler Effect	(573)
6.6	Faking Real-Time DSP Effects	(583)

SECTION 7 NETWORK AND MULTIPLAYER (589)

Introduction		(591)
7.1	Dynamically Adaptive Streaming of 3D Data for Animated Characters	(593)
7.2	Complex Systems-Based High-Level Architecture for Massively Multiplayer Games	(607)
7.3	Generating Globally Unique Identifiers for Game Objects	(623)
7.4	Massively Multiplayer Online Prototype Utilizing Second Life for Game Concept Prototyping	(629)
7.5	Reliable Peer-to-Peer Gaming Connections Penetrating NAT	(641)

About the CD-ROM		(651)
Index		(653)

Game Programming Gems 7

Preface		(ix)
About the Cover Image		(xiii)
Acknowledgements		(xv)
Contributor Bios		(xvii)

SECTION 1 GENERAL PROGRAMMING (1)

Introduction		(3)
1.1	Efficient Cache Replacement Using the Age and Cost Metrics	(5)
1.2	High Performance Heap Allocator	(15)
1.3	Optical Flow for Video Games Played with Webcams	(25)
1.4	Design and Implementation of a Multi-Platform Threading Engine	(35)
1.5	For Bees and Gamers: How to Handle Hexagonal Tiles	(47)
1.6	A Sketch-Based Interface to Real-Time Strategy Games Based on a Cellular Automaton	(59)
1.7	Foot Navigation Technique for First-Person Shooting Games	(69)
1.8	Deferred Function Call Invocation System	(81)
1.9	Multithread Job and Dependancy System	(87)
1.10	Advanced Debugging Techniques	(97)

SECTION 2 MATH AND PHYSICS (107)

Introduction		(10
2.1	Random Number Generation	(113)
2.2	Fast Generic Ray Queries for Games	(127)
2.3	Fast Rigid-Body Collision Detection using Farthest Feature Maps	(143)
2.4	Using Projective Space to Improve Precision of Geometric Computations	(153)
2.5	XenoCollide: Complex Collision Made Simple	(165)
2.6	Efficient COllision Detection Using Transformation Semantics	(179)
2.7	Trigonemtric Splines	(191)
2.8	Using Gaussian Randomness to Realistically Vary Projectile Paths	(199)

SECTION 3 AI (205)

Introduction		(20
3.1	Creating Interesting Agents with Behavior Cloning	(209)
3.2	Designing a Realistic and Unified Agent-Sesning Model	(217)
3.3	Managing AI Algorithmic Complexity: Generic Programming Apprach	(229)
3.4	All About Attitude: Building Blocks for Opinion, Reputation, and NPC Personalities	(249)
3.5	Understanding Intelligence in Games using Player Traces and Interactive Player Graphs	(265)
3.6	Goal-Oriented Plan Merging	(281)
3.7	Beyond A*: IDA* and Fringe Search	(289)

SECTION 4 AUDIO (295)

Introduction		(297)
4.1	Audio Signal Processing Using Programmable Graphics Hardware	(299)
4.2	MultiStream - The Art of Writing a Next-Gen Audio Engine	(305)
4.3	Listen Carefully, You Probably Won’t Hear This Again	(321)
4.4	Real-Time Audio Effects Applied	(331)
4.5	Context-Driven, Layered Mixing	(341)

SECTION 5 GRAPHICS (349)

Introduction		(351)
5.1	Advanced Particle Deposition	(353)
5.2	Reducing Cumulative Errors in Skeletal Animations	(365)
5.3	An Alternative Model for Shading of Diffuse Light for Rough Materials	(373)
5.4	High-Performance Subdivision Surfaces	(381)
5.5	Animating Relief Impostors Using Radial Basis Functions Textures	(401)
5.6	Clipmapping on SM1.1 and Higher	(413)
5.7	An Advanced Decal System	(423)
5.8	Mapping Large Textures for Outdoor Terrain Rendering	(435)
5.9	Art-Based Rendering with Graftal Impostors	(447)
5.10	Cheap Talk: Dynamic Real-Time Lipsync	(455)

SECTION 6 NETWORKING AND MULTIPLAYER (463)

Introduction		(465)
6.1	High-Level Abstraction of Game World Synchronization	(467)
6.2	Authentication for Online Games	(481)
6.3	Game Network Debugging with Smart Packet Sniffers	(491)

SECTION 7 SCRIPTING AND DATA-DRIVEN SYSTEMS (499)

Introduction		(50)
7.1	Automatic Lua Binding System	(503)
7.2	Serializing C++ Objects into a Database Using Introspection	(517)
7.3	Dataports	(535)
7.4	Support Your Local Artist: Adding Shaders to Your Engine	(541)
7.5	Dance with Python’s AST	(555)

About the CD-ROM		(561)
Index		(563)

Game Programming Gems 8

Section 1 Graphics (1)

Introduction		(1)
1.1	Fast Font Rendering with Instancing	(3)
1.2	Principles and Practice of Screen Space Ambient Occlusion	(12)
1.3	Multi-Resolution Deferred Shading	(32)
1.4	View Frustum Culling of Catmull-Clark Patches in DirectX 11	(39)
1.5	Ambient Occlusion Using DirectX Compute Shader	(50)
1.6	Eye-View Pixel Anti-Aliasing for Irregular Shadow Mapping	(74)
1.7	Overlapped Execution on Programmable Graphics Hardware	(90)
1.8	Techniques for Effective Vertex and Fragment Shading on the SPUs	(101)

Section 2 Physics and Animation (119)

Introduction		(119)
2.1	A Versatile and Interactive Anatomical Human Face Model	(121)
2.2	Curved Paths for Seamless Character Animation	(132)
2.3	Non-Iterative, Closed-Form, Inverse Kinematic Chain Solver (NCF IK)	(141)
2.4	Particle Swam Optimization for Game Programming	(152)
2.5	Improved Numerical Integration with Analytical Techniques	(168)
2.6	What a Drag: Modelling Realistic Three-Dimensional Air and Fluid Resistance	(183)
2.7	Application of Quasi-Fluid Dynamics for Arbitrary Closed Meshes	(194)
2.8	Approximate Convex Decomposition for Real-Time Collision Detection	(202)

Section 3 AI (211)

Introduction		(211)
3.1	AI Level of Detail for Really Large Worlds	(213)
3.2	A Pattern-Based Approach to Modular AI for Games	(232)
3.3	Automated Navigation Mesh Generation Using Advanced Growth-Based Techniques	(244)
3.4	A Practical Spatial Architecture for Animal and Agent Navigation	(256)
3.5	Applying Control Theory to Game AI and Physics	(264)
3.6	Adaptive Tactic Selection in First-Person Shooter (FPS) Games	(279)
3.7	Embracing Chaos Theory: Generating Apparent Unpredictability through Deterministic Systems	(288)
3.8	Needs-Based AI	(302)
3.9	A Framework for Emotional Digital Actors	(312)
3.10	Scalable Dialog Authoring	(323)
3.11	Graph-Based Data Mining for Player Trace Analysis in MMORPGs	(335)

Section 4 General Programming (353)

Introduction		(353)
4.1	Fast-IsA	(355)
4.2	Registered Variables	(363)
4.3	Efficient and Scalable Multi-Core Programming	(373)
4.4	Game Optimization through the Lens of Memory and Data Access	(385)
4.5	Stack Allocation	(393)
4.6	Design and Implementation of an In-Game Memory Profiler	(402)
4.7	A More Informative Error Log Generator	(409)
4.8	Code Coverage for QA	(416)
4.9	Domain-Specific Languages in Game Engines	(428)
4.10	A Flexible User Interface Layout system for Divergent Environments	(442)
4.11	Road Creation for Projectable Terrain Meshes	(453)
4.12	Developing for Digital Drawing Tables	(462)
4.13	Creating a Multi-Threaded Actor-Based Architecture using Intel® Threading Building Blocks	(473)

Section 5 Networking and Multiplayer (485)

Introduction		(485)
5.1	Secure Channel Communication	(487)
5.2	Social Networks in Games: Playing with Your Facebook Friends	(498)
5.3	Asynchronous I/O for Scalable Game Servers	(506)
5.4	Introduction to 3D Streaming Technology in Massively Multiplayer Online Games	(514)

Section 6 Audio (539)

Introduction		(539)
6.1	A Practical DSP Radio Effect	(542)
6.2	Empowering Your Audio Teams with a Great Engine	(553)
6.3	Real-Time Sound Synthesis for Rigid Bodies	(563)

Section 7 General Purpose Computing on GPUs (573)

Introduction		(573)
7.1	Using Heterogenous Parallel Architecture with OpenCL	(575)
7.2	PhysX CPU Rigid Bodies in Batman: Arkham Asylum	(590)
7.3	Fast GPU Fluid Simulation in PhysX	(602)

Index

(616)

Best of Game Programming Gems

Acknowledgments		(ix)
About the Authors		(xi)
Introduction		(xxv)

SECTION 1 GENERAL INFORMATION (1)

1.1	The Science of Debugging Games	(3)
1.2	Finding Redeeming Value in C-Style Macros	(17)
1.3	Inline Functions vs Macros	(29)
1.4	Squeezing More Out of Assaert	(35)
1.5	Programming with Abstract Interfaces	(41)
1.6	The Beauty of Weak References and Null Objects	(49)
1.7	Using the STL in Game Programming	(57)
1.8	Custom STL Allocators	(73)
1.9	Optimizations for C++ Games	(83)
1.10	Real-Time Hierarchical Profiling	(95)
1.11	A Generic Tree Container in C++	(103)
1.12	Lock-Free Algorithms	(113)
1.13	Utilizing Multicore Processors with OpenMP	(125)

SECTION 2 MATH AND PHYSICS (133)

2.1	More Approximations to Trigonometric Functions	(135)
2.2	Faster Quaternion Interpolation Using Approximations	(153)
2.3	Quaternion Compression	(175)
2.4	Zobrist Hash Using the Mersenne Twister	(181)
2.5	Solving Accuracy Problems in Large World Coordinates	(187)
2.6	Writing a Verlet-Based Physics Engine	(201)
2.7	Constraints in Rigid Body Dynamics	(211)
2.8	The Jacobian Transpose Method for Inverse Kinematics	(223)

SECTION 3 ARTIFICIAL INTELLIGENCE (235)

3.1	The Basics of A* for Path Planning	(237)
3.2	A* Aesthetic Optimizations	(247)
3.3	A* Speed Optimizations	(255)
3.4	Tactical Path-Finding with A	(271)
3.5	A Fast Approach to Navigation Meshes	(285)
3.6	Flocking: A Simple Technique for Simulating Group Behavior	(297)
3.7	A Finite-State Machine Class	(311)
3.8	Implementing Practical Planning for Game AI	(323)

SECTION 4 GRAPHICS (339)

4.1	T-Junction Elimination and Retriangulation	(341)
4.2	Filling the Gaps: Advanced Animation Using Stitching and Skinning	(347)
4.3	Improved Skin Deformation Using Kinematic Skeletons	(355)
4.4	Motion Capture Data Compression	(363)
4.5	Compressed Axis-Aligned Bounding Box Trees	(371)
4.6	Textures as Lookup Tables for Per-Pixel Lighting Computations	(377)
4.7	Methods for Dynamic, Photorealistic Terrain Lightning	(387)
4.8	Practical Sky Rendering for Games	(399)
4.9	Powerful Explosion Effects using Billboard Particles	(411)
4.10	Rendering Handcrafted Shading Models	(421)

SECTION 5 NETWORKING (427)

5.1	Overcoming Network Address Translation in Peer-to-Peer Communications	(429)
5.2	Minimizing Latency in Real-Time Strategy Games	(451)
5.3	Real-Time Strategy Network Protocol	(459)
5.4	Secure Sockets	(469)
5.5	Bit Packing: A Network Compression Technique	(481)

SECTION 6 AUDIO (489)

6.1	A Basic Music Sequencer for Games	(491)
6.2	Audio Compression with Ogg Vorbis	(503)
6.3	Using 3D Surfaces as Audio Emitters	(511)
6.4	Introduction to Single-Speaker Speech Recognition	(521)
6.5	A Technique to instantaneously Reuse Voices in a Sample-Based Synthesizer	(531)

Index

(535)

---

Game Programming Gems TOC

Game Programming Gems 1

Section 1 Programming Techniques

• 1.0 The Magic of Data-Driven Design
• 1.1 Object-Oriented Programming and Design Techniques
• 1.2 Fast Math Using Template Metaprogramming
• 1.3 An Automatic Singleton Utility
• 1.4 Using the STL in Game Programming
• 1.5 A Generic Function-Binding Interface
• 1.6 A Generic Handle-Based Resource Manager
• 1.7 Resource and Memory Management
• 1.8 Fast Data Load Trick
• 1.9 Frame-Based Memory Allocation
• 1.10 Simple, Fast Bit Arrays
• 1.11 A Network Protocol for Online Games
• 1.12 Squeezing More Out of Assert
• 1.13 Stats: Real-Time Statistics and In-Game Debugging
• 1.14 Real-Time In-Game Profiling

Section 2 Mathematics

• 2.0 Predictable Random Numbers
• 2.1 Interpolation Methods
• 2.2 Integrating the Equations of Rigid Body Motion
• 2.3 Polynomial Approximations to Trigonometric Functions
• 2.4 Using Implicit Euler Integration for Numerical Stability
• 2.5 Wavelets: Theory and Compression
• 2.6 Interactive Simulation of Water Surfaces
• 2.7 Quaternions for Game Programming
• 2.8 Matrix-Quaternion Conversions
• 2.9 Interpolating Quaternions
• 2.10 The Shortest Arc Quaternion

Section 3 Artificial Intelligence

• 3.0 Designing a General Robust AI Engine
• 3.1 A Finite-State Machine Class
• 3.2 Game Trees
• 3.3 The Basics of A* for Path Planning
• 3.4 A* Aesthetic Optimizations
• 3.5 A* Speed Optimizations
• 3.6 Simplified 3D Movement and Pathfinding Using Navigation Meshes
• 3.7 Flocking: A Simple Technique for Simulating Group Behavior
• 3.8 Fuzzy Logic for Video Games
• 3.9 A Neural-Net Primer

Section 4 Polygonol Techniques

• 4.0 Optimizing Vertex Submissions for OpenGL
• 4.1 Tweaking A Vertex's Projected Depth Value
• 4.2 The Vector Camera
• 4.3 Camera Control Techniques
• 4.4 A Fast Cylinder-Frustum Intersection Test
• 4.5 3D Collision Detection
• 4.6 Multi-Resolution Maps for Interaction Detection
• 4.7 Computing the Distance into a Sector
• 4.8 Object Occlusion Culling
• 4.9 Never Let 'Em See You Pop - Issues in Geometric Level of Detail Selection
• 4.10 Octree Construction
• 4.11 Loose Octrees
• 4.12 View-Independent Progressive Meshing
• 4.13 Interpolated 3D Keyframe Animation
• 4.14 A Fast and Simple Skinning Techniques
• 4.15 Filling the Gaps - Advanced Animation Using Stitching and Skinning
• 4.16 Real-Time Realistic Terrain Generation
• 4.17 Fractal Terrain Generation - Fault Formation
• 4.18 Fractal Terrain Generation - Midpoint Displacement
• 4.19 Fractal Terrain Generation - Particle Deposition

Section 5 Pixel Effects

• 5.0 2D Lens Flare
• 5.1 Using 3D Hardware for 2D Sprite Effects
• 5.2 Motif-Based Static Lighting
• 5.3 Simulated Real-Time Lighting Using Vertex Color Interpolation
• 5.4 Attenuation Maps
• 5.5 Advanced Texturing Using Texture Coordinate Generation
• 5.6 Hardware Bump Mapping
• 5.7 Ground-Plane Shadows
• 5.8 Real-Time Shadows on Complex Objects
• 5.9 Improving Environment-Mapped Reflection Using Glossy Prefiltering and the Fresnel Term
• 5.10 Convincing-Looking Glass for Games
• 5.11 Refraction Mapping for Liquids in Containers

Section 6 Appendix

• 6.0 The Matrix Utility Library
• 6.1 The Text Utility Library
• 6.2 About the CD-ROM
• Index

Game Programming Gems 2

Mathematics

• Algebraic Techniques
• Trigonometry and Geometry
• Linear Algebra
• Matrix and Vector Operations
• Advanced Mathematics
• Ray/ Polygon/Polyhedra Instersection Algorithms
• Handling Large Amounts of Polygonal Data
• Triangle Stripification and Fanning Algorithms
• Using 2D and 3D Billboards
• LIGHTING: Multi-texturing to Achieve Lighting Effects
• Shadow Algorithms
• Using Simple Radiosity
• Projected Texture Lights

Texturing

• Using Texture Matrices
• Bump Mapping
• Cubic Environment Mapping
• Procedural Textural Mapping
• DYNAMIC POLYGON CONTROL: Parametric Curves and Surfaces
• Subdivision Surfaces
• Multi-resolution Meshes
• Spatial Partitioning Schemes
• Camera Techniques/ Movement Techniques

Graphic Effects

• How to do Lens Flares
• Weather Techniques
• Sky Domes
• Effective Clouds and Fog
• Aliasing Effects (Anti-Aliasing
• Motion Blur
• Depth-of-Field)
• Teleport Portals
• Particle Systems

Animation

• Inverse Kinematics
• Blending Keyframed Animations
• Solid Skinning vs.Hierarchical Skeletons
• Using Motion Capture Data

Artificial Intelligence

• Finite State Machines
• Heuristic Tree Searches
• Flocking and Crowding Behavior
• Path Planning and the A*Algorithm

Music and Sound Effects

• Blending Phrases in Interactive Music
• Dynamic Audio Generation
• Simulating a 3D Sound-Effect Environment
• Using Music Cues to Initiate Game Events

Networked Play

• Minimizing Latency in the Network Pipeline
• Dead Reckoning Algorithms
• Client/Server Design
• Encryption Techniques.

Game Programming Gems 3

• Foreword (xi)
• Preface (xv)
• Acknowledgments (xix)
• About the Cover Image (xxi)
• Contributor Bios (xxiii)

SECTION 1 GENERAL PROGRAMMING (1)

• Introduction (3)
• 1.1 Scheduling Game Events (5)
• 1.2 An Object-Composition Game Framework (15)
• 1.3 Finding Redeeming Value in C-Style Macros (26)
• 1.4 Platform-Independent, Function-Binding Code Generator (38)
• 1.5 Handle-Based Smart Pointers (44)
• 1.6 Custom STL Allocators (49)
• 1.7 Save Me Now! (59)
• 1.8 Autolists Design Pattern (64)
• 1.9 Floating-Point Exception Handling (69)
• 1.10 Programming a Game Design-Compliant Engine Using UML (73)
• 1.11 Using Lex and Yacc To Parse Custom Data Files (83)
• 1.12 Developing Games for a World Market (92)
• 1.13 Real-Time Input and UI in 3D Games (109)
• 1.14 Natural Selection: The Evolution of Pie Menus (117)
• 1.15 Lightweight, Policy-Based Logging (129)
• 1.16 Journaling Services (136)
• 1.17 Real-Time Hierarchical Profiling (146)

SECTION 2 MATHEMATICS (153)

• Introduction (155)
• 2.1 Fast Base-2 Functions for Logarithms and Random Number Generation (157)
• 2.2 Using Vector Fractions for Exact Geometry (160)
• 2.3 More Approximations to Trigonometric Functions (170)
• 2.4 Quaternion Compression (187)
• 2.5 Constrained Inverse Kinematics (192)
• 2.6 Cellular Automata for Physical Modeling (200)
• 2.7 Coping with Friction in Dynamic Simulations (215)

SECTION 3 ARTIFICIAL INTELLIGENCE (227)

• Introduction (229)
• 3.1 Optimized Machine Learning with GoCap (231)
• 3.2 Area Navigation: Expanding the Path-Finding Paradigm (240)
• 3.3 Function Pointer-Based, Embedded Finite-State Machines (256)
• 3.4 Terrain Analysis in an RTS-The Hidden Giant (268)
• 3.5 An Extensible Trigger System for AI Agents, Objects, and Quests (285)
• 3.6 Tactical Path-Finding with A* (294)
• 3.7 A Fast Approach to Navigation Meshes (307)
• 3.8 Choosing a Relationship Between Path-Finding and Collision (321)

SECTION 4 GRAPHICS (333)

• Introduction (335)
• 4.1 T-Junction Elimination and Retriangulation (338)
• 4.2 Fast Heightfield Normal Calculation (344)
• 4.3 Fast Patch Normals (349)
• 4.4 Fast and Simple Occlusion Culling (353)
• 4.5 Triangle Strip Creation, Optimizations, and Rendering (359)
• 4.6 Computing Optimized Shadow Volumes for Complex Data Sets (367)
• 4.7 Subdivision Surfaces for Character Animation (372)
• 4.8 Improved Deformation of Bones (384)
• 4.9 A Framework for Realistic Character Locomotion (394)
• 4.10 A Programmable Vertex Shader Compiler (404)
• 4.11 Billboard Beams (413)
• 4.12 3D Tricks for Isometric Engines (417)
• 4.13 Curvature Simulation Using Normal Maps (424)
• 4.14 Methods for Dynamic, Photorealistic Terrain Lighting (433)
• 4.15 Cube Map Lighting Techniques (444)
• 4.16 Procedural Texturing (452)
• 4.17 Unique Textures (459)
• 4.18 Textures as Lookup Tables for Per-Pixel Lighting Computations (467)
• 4.19 Rendering with Handcrafted Shading Models (477)

SECTION 5 NETWORK AND MULTIPLAYER (485)

• Introduction (487)
• 5.1 Minimizing Latency in Real-Time Strategy Games (488)
• 5.2 Real-Time Strategy Network Protocol (496)
• 5.3 A Flexible Simulation Architecture for Massively Multiplayer Games (506)
• 5.4 Scaling Multiplayer Servers (520)
• 5.5 Template-Based Object Serialization (534)
• 5.6 Secure Sockets (546)
• 5.7 A Network Monitoring and Simulation Tool (557)
• 5.8 Creating Multiplayer Games with DirectPlay 8.1 (561)
• 5.9 Wireless Gaming Using the Java Micro Edition (573)

SECTION 6 AUDIO (583)

• Introduction (585)
• 6.1 Audio Compression with Ogg Vorbis (587)
• 6.2 Creating a Compelling 3D Audio Environment (595)
• 6.3 Obstruction Using Axis-Aligned Bounding Boxes (600)
• 6.4 Using the Biquad Resonant Filter (606)
• 6.5 Linear Predictive Coding for Voice Compression and Effects (613)
• 6.6 The Stochastic Synthesis of Complex Sounds (622)
• 6.7 Real-Time Modular Audio Processing for Games (630)

• Appendix: About the CD-ROM (639)
• Contents

Game Programming Gems 4

• Foreword (xi)
• Preface (xv)
• Acknowledgments (xvii)
• About the Cover Image (xix)
• Contributor Bios (xxi)

SECTION 1 GENERAL PROGRAMMING (1)

• Introduction (3)
• 1.1 The Science of Debugging Games (5)
• 1.2 An HTML-Based Logging and Debugging System (19)
• 1.3 The Clock: Keeping Your Finger on the Pulse of the Game (27)
• 1.4 Designing and Maintaining Large Cross-Platform Libraries (35)
• 1.5 Fight Memory Fragmentation with Templated Freelists (43)
• 1.6 A Generic Tree Container in C++ (51)
• 1.7 The Beauty of Weak References and Null Objects (61)
• 1.8 A System for Managing Game Entities (69)
• 1.9 Address-Space Managed Dynamic Arrays for Windows and the Xbox (85)
• 1.10 Critically Damped Ease-In/Ease-Out Smoothing (95)
• 1.11 A Flexible, On-the-Fly Object Manager (103)
• 1.12 Using Custom RTTI Properties to Stream and Edit Objects (111)
• 1.13 Using XML without Sacrificing Speed (125)

SECTION 2 MATHEMATICS (137)

• Introduction (139)
• 2.1 Zobrist Hash Using the Mersenne Twister (141)
• 2.2 Extracting Frustum and Camera Information (147)
• 2.3 Solving Accuracy Problems in Large World Coordinates (157)
• 2.4 Nonuniform Splines (171)
• 2.5 Using the Covariance Matrix for Better-Fitting Bounding Objects (183)
• 2.6 The Jacobian Transpose Method for Inverse Kinematics (193)

SECTION 3 PHYSICS (205)

• Introduction (207)
• 3.1 Ten Fingers of Death: Algorithms for Combat Killing (209)
• 3.2 Vehicle Physics Simulation for CPU-Limited Systems (221)
• 3.3 Writing a Verlet-Based Physics Engine (231)
• 3.4 Constraints in Rigid Body Dynamics (241)
• 3.5 Fast Contact Reduction for Dynamics Simulation (253)
• 3.6 Interactive Water Surfaces (265)
• 3.7 Fast Deformations with Multilayered Physics (275)
• 3.8 Modal Analysis for Fast, Stable Deformation (287)

SECTION 4 ARTIFICIAL INTELLIGENCE (299)

• Introduction (301)
• 4.1 Third-Person Camera Navigation (303)
• 4.2 Narrative Combat: Using AI to Enhance Tension in an Action Game 315
• 4.3 NPC Decision Making: Dealing with Randomness (325)
• 4.4 An Object-Oriented Utility-Based Decision Architecture (337)
• 4.5 A Distributed-Reasoning Voting Architecture (345)
• 4.6 Attractors and Repulsors (355)
• 4.7 Advanced Wall Building for RTS Games (365)
• 4.8 Artificial Neural Networks on Programmable Graphics Hardware (373)

SECTION 5 GRAPHICS (379)

• Introduction (381)
• 5.1 Poster Quality Screenshots (383)
• 5.2 GPU Shadow Volume Construction for Nonclosed Meshes (393)
• 5.3 Perspective Shadow Maps (399)
• 5.4 Combined Depth and ID-Based Shadow Buffers (411)
• 5.5 Carving Static Shadows into Geometry (427)
• 5.8 Techniques to Apply Team Colors to 3D Models (451)
• 5.9 Fast Sepia Tone Conversion (461)
• 5.10 Dynamic Gamma Using Sampled Scene Luminance (465)
• 5.11 Heat and Haze Post-Processing Effects (477)
• 5.13 Motion Capture Data Compression (497)
• 5.14 Fast Collision Detection for 3D Bones-Based Articulated Characters (503)
• 5.15 Terrain Occlusion Culling with Horizons (515)

SECTION 6 NETWORK AND MULTIPLAYER (529)

• Introduction (531)
• 6.1 General Lobby Design and Development (533)
• 6.2 Thousands of Clients per Server (541)
• 6.3 Efficient MMP Game State Storage (555)
• 6.4 Practical Application of Parallel-State Machines in a Client-Server Environment (563)
• 6.5 Bit Packing: A Network Compression Technique (571)
• 6.6 Time and Consistency Management for Multiserver-Based MMORPGs (579)

SECTION 7 AUDIO (591)

• Introduction (593)
• 7.1 A Brief Introduction to OpenAL (595)
• 7.2 A Simple Real-Time Lip-Synching System (607)
• 7.3 Dynamic Variables and Audio Programming (613)
• 7.4 Creating an Audio Scripting System (621)
• 7.5 Implementing an Environmental Audio Solution Using EAX and ZoomFX (633)
• 7.6 Controlling Real-Time Sound Synthesis from Game Physics (649)

• APPENDIX: ABOUT THE CD-ROM (657)
• INDEX (659)

Game Programming Gems 5

• Foreword (xi)
• Preface (xv)
• About the Cover Image (xix)
• Contributor Bios (xxi)

SECTION 1 GENERAL PROGRAMMING (1)

• Introduction (3)
• 1.1 Context-Sensitive HUDs for Editors (5)
• 1.2 Parsing Text Data in Games (17)
• 1.3 Component Based Object Management (25)
• 1.4 Using Templates for Reflection in C++ (39)
• 1.5 Sphere Trees for Speedy BSPs (55)
• 1.6 Improved Frustum Culling (65)
• 1.7 Generic Pager (79)
• 1.8 Large-Scale Stack-Based State Machines (93)
• 1.9 CSG Construction Using BSP Trees (103)
• 1.10 Building Lua into Games (115)
• 1.11 Improving Freelists with Policy Based Design (129)
• 1.12 A Real-Time Remote Debug Message Logger (143)
• 1.13 A Transparent Class Saving and Loading Trick (149)
• 1.14 An Effective Cache-Oblivious Implementation of the ABT Tree (159)
• 1.15 Visual Design of State Machines (169)
• 1.16 A Generic Component Library (177)
• 1.17 Choose Your Path-A Menu System (189)

SECTION 2 MATHEMATICS (197)

• Introduction (199)
• 2.1 Using Geometric Algebra for Computer Graphics (201)
• 2.2 Minimal Acceleration Hermite Curves (225)
• 2.3 Spline-Based Time Control for Animation (233)
• 2.4 Faster Quaternion Interpolation Using Approximations (247)
• 2.5 Minimax Numerical Approximation (269)
• 2.6 Oblique View Frustums for Mirrors and Portals (281)

SECTION 3 ARTIFICIAL INTELLIGENCE (295)

• Introduction (297)
• 3.1 Automatic Cover Finding with Navigation Meshes (299)
• 3.2 Fast Target Ranking Using an Artificial Potential Field (307)
• 3.3 Using Lanchester Attrition Models to Predict the Results of Combat (317)
• 3.4 Implementing Practical Planning for Game AI (329)
• 3.5 Optimizing a Decision Tree Query Algorithm for Multithreaded Architectures (345)
• 3.6 Parallel AI Development with PVM (353)
• 3.7 Beyond A* (367)
• 3.8 Advanced Pathfinding with Minimal Replanning Cost: Dynamic A Star (D*) (383)

SECTION 4 PHYSICS (391)

• Introduction (393)
• 4.1 Back of the Envelope Aerodynamics for Game Physics (395)
• 4.2 Dynamic Grass Simulation and Other Natural Effects (411)
• 4.3 Realistic Cloth Animation Using the Mass-Spring Model (421)
• 4.4 Practical Animation of Soft Bodies for Game Development: The Pressurized Soft-Body Model (435)
• 4.5 Adding Life to Ragdoll Simulation Using Feedback Control Systems (449)
• 4.6 Designing a Prescripted Physics System (457)
• 4.7 Prescripted Physics: Techniques and Applications (473)
• 4.8 Realistic Camera Movement in a 3D Car Simulator (483)

SECTION 5 GRAPHICS (495)

• Introduction (497)
• 5.1 Realistic Cloud Rendering on Modern GPUs (499)
• 5.2 Let It Snow, Let It Snow, Let It Snow (and Rain) (507)
• 5.3 Widgets: Rendering Fast and Persistent Foliage (515)
• 5.4 2.5 Dimensional Impostors for Realistic Trees and Forests (527)
• 5.5 Gridless Controllable Fire (539)
• 5.6 Powerful Explosion Effects Using Billboard Particles (551)
• 5.7 A Simple Method for Rendering Gemstones (561)
• 5.8 Volumetric Post-Processing (571)
• 5.9 Procedural Level Generation (579)
• 5.10 Recombinant Shaders (589)

SECTION 6 NETWORK AND MULTIPLAYER (599)

• Introduction (601)
• 6.1 Keeping a Massively Multiplayer Online Game Massive, Online, and Persistent (603)
• 6.2 Implementing a Seamless World Server (611)
• 6.3 Designing a Vulgarity Filtering System (621)
• 6.4 Fast and Efficient Implementation of a Remote Procedure Call System (627)
• 6.5 Overcoming Network Address Translation in Peer-to-Peer Communications (643)
• 6.6 A Reliable Messaging Protocol (665)
• 6.7 Safe Random Number Systems (673)
• 6.8 Secure by Design (681)

SECTION 7 AUDIO (693)

• Introduction (695)
• 7.1 Multithreaded Audio Programming Techniques (697)
• 7.2 Sound Management by Group (713)
• 7.3 Using 3D Surfaces as Audio Emitters (721)
• 7.4 Fast Environmental Reverb Based on Feedback Delay Networks (729)
• 7.5 Introduction to Single-Speaker Speech Recognition (741)

• About the CD-ROM (751)
• Index (753)

Game Programming Gems 6

• Foreword (xi)
• Preface (xv)
• About the Cover Image (xxi)
• Contributor Bios (xxiii)

SECTION 1 GENERAL PROGRAMMING (1)

• Introduction (3)
• 1.1 Lock-Free Algorithms (5)
• 1.2 Utilizing Multicore Processors with OpenMP (17)
• 1.3 Computer Vision in Games Using the OpenCV Library (25)
• 1.4 Geographic Grid Registration of Game Objects (39)
• 1.5 BSP Techniques (49)
• 1.6 Closest-String Matching Algorithm (69)
• 1.7 Using CppUnit To Implement Unit Testing (79)
• 1.8 Fingerprinting Pre-Release Builds To Deter and Detect Piracy (97)
• 1.9 Faster File Loading with Access-Based File Reordering (103)
• 1.10 Stay in the Game: Asset Hotloading for Fast Iteration (109)

SECTION 2 MATHEMATICS AND PHYSICS (117)

• Introduction (119)
• 2.1 Floating-Point Tricks (121)
• 2.2 GPU Computation in Projective Space Using Homogeneous Coordinates (137)
• 2.3 Solving Systems of Linear Equations Using the Cross Product (149)
• 2.4 Sequence Indexing for Game Development (161)
• 2.5 Exact Buoyancy for Polyhedra (175)
• 2.6 Real-Time Particle-Based Fluid Simulation with Rigid Body Interaction (189)

SECTION 3 ARTIFICIAL INTELLIGENCE (207)

• Introduction (209)
• 3.1 Applying Model-Based Decision-Making Methods to Games: Applying the Locust AI Engine to QuakeŽ III (211)
• 3.2 Achieving Coordination with Autonomous NPCs (223)
• 3.3 Behavior-Based Robotic Architectures for Games (235)
• 3.4 Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Extended Behavior Networks (245)
• 3.5 A Goal-Oriented Unreal Bot: Building a Game Agent with Goal-Oriented Behavior and Simple Personality Using Extended Behavior Networks (259)
• 3.6 Short-Term Memory Modeling Using a Support Vector Machine (273)
• 3.7 Using the Quantified Judgment Model for Engagement Analysis (283)
• 3.8 Designing a Multilayer, Pluggable AI Engine (291)
• 3.9 A Fuzzy-Control Approach to Managing Scene Complexity (307)

SECTION 4 SCRIPTING AND DATA-DRIVEN SYSTEMS (317)

• Introduction (319)
• 4.1 Scripting Language Survey (323)
• 4.2 Binding C/C++ Objects to Lua (341)
• 4.3 Programming Advanced Control Mechanisms with Lua Coroutines (357)
• 4.4 Managing High-Level Script Execution Within Multithreaded Environments (371)
• 4.5 Exposing Actor Properties Using Nonintrusive Proxies (383)
• 4.6 Game Object Component System (393)

SECTION 5 GRAPHICS (405)

• Introduction (407)
• 5.1 Synthesis of Realistic Idle Motion for Interactive Characters (409)
• 5.2 Spatial Partitioning Using an Adaptive Binary Tree (423)
• 5.3 Enhanced Object Culling with (Almost) Oriented Bounding Boxes (437)
• 5.4 Skin Splitting for Optimal Rendering (449)
• 5.5 GPU Terrain Rendering (461)
• 5.6 Interactive Fluid Dynamics and Rendering on the GPU (473)
• 5.7 Fast Per-Pixel Lighting with Many Lights (489)
• 5.8 Rendering Road Signs Sharply (501)
• 5.9 Practical Sky Rendering for Games (517)
• 5.10 High Dynamic Range Rendering Using OpenGL Frame Buffer Objects (529)

SECTION 6 AUDIO (537)

• Introduction (539)
• 6.1 Real-Time Sound Generation from Deformable Meshes (541)
• 6.2 A Lightweight Generator for Real-Time Sound Effects (549)
• 6.3 Real-Time Mixing Busses (555)
• 6.4 Potentially Audible Sets (561)
• 6.5 A Cheap Doppler Effect (573)
• 6.6 Faking Real-Time DSP Effects (583)

SECTION 7 NETWORK AND MULTIPLAYER (589)

• Introduction (591)
• 7.1 Dynamically Adaptive Streaming of 3D Data for Animated Characters (593)
• 7.2 Complex Systems-Based High-Level Architecture for Massively Multiplayer Games (607)
• 7.3 Generating Globally Unique Identifiers for Game Objects (623)
• 7.4 Massively Multiplayer Online Prototype Utilizing Second Life for Game Concept Prototyping (629)
• 7.5 Reliable Peer-to-Peer Gaming Connections Penetrating NAT (641)

• About the CD-ROM (651)
• Index (653)

//z 2014-07-18 17:12:26 L.166'24454 BG57IV3@XCL T2649809119.K.F1752546504[T8,L150,R7,V167] IS2120