There is a flaw in the skinned vertex shader (xsi_defaultvs.hlsl) provided by AutoDesk SoftImage tool. In the VSSkinned vertex shader, the weighted position has not been transformed in the world space. This made the 3D model to ignore every transformation (translation and rotation) made on it. The line of code mistaken is:
// Skin the vertex position
float4 weightedposition = mul(IN.position, skinTransform);
should be changed into:
float4 weightedposition = mul(mul(IN.position, skinTransform), Model);
After this change you should be able to transform (translation, rotation and scale) your 3D model in the DrawModel() method in this way:
Model model = character.GetModel(); // my model
float rotation = character.GetRotation(); // desire rotation
Vector3 position = character.GetPosition(); // desire position
// transformation Matrix
Matrix worldMatrix = Matrix.CreateRotationY( rotation ) * Matrix.CreateTranslation( position );
UpdateSASData( game, camera );
Matrix[] bones = GetBones( model );
bool isSkinned = (bones.Length > 0);
Matrix[] transforms = new Matrix[model.Bones.Count];
model.CopyAbsoluteBoneTransformsTo( transforms ); // apply default transforms
foreach( ModelMesh mesh in model.Meshes )
{
//apply our transform to each mesh
this.SASData.Model = transforms[mesh.ParentBone.Index] * worldMatrix;
//...
}
Thanks to: http://www.matthughson.com/
Wednesday, April 21, 2010
Game Programming Gems - List of contents
This is the list of contents of the Game Programming Gems series. For more important game programming books go to My Bibliography.
Game Programming Gems 1
Section 1 Programming
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 Polygonal 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
Game Programming Gems 2
Section 1 - General Programming
1.1 Optimizations for C++ games
1.2 Inline Functions Versus Macros
1.3 Programming with Abstract Interfaces
1.4 Exporting C++ Classes from DLLs
1.5 Protect yourself from DLL Hell and Missing OS Functions
1.6 Dynamic Type Information
1.7 A Property Class for Generic C++ Member Access
1.8 A Game Entity Factory
1.9 Adding Deprecation Facilities to C++
1.10 A Drop-in Debug Memory Manager
1.11 A Built-in Game Profiling Module
1.12 Linear Programming Model for Windows-based Games
1.13 Stack Winding
1.14 Self-Modifying Code
1.15 File Management using Resource Files
1.16 Game Input Recording and Playback
1.17 A Flexible Text Parsing System
1.18 A Generic Tweaker
1.19 Genuine Random Number Generation
1.20 Using Bloom Filters to Improve Computational Performance
1.21 3ds Max Skin exporter and animation toolkit
1.22 Using Web Cameras in Video Games
Section 2 - Mathematics
2.1 Floating-Point Tricks: Improving Performance with IEEE Floating Point
2.2 Vector and Plane Tricks
2.3 Fast, Robust Intersection of 3D Line Segments
2.4 Inverse Trajectory Determination
2.5 The Parallel Transport Frame
2.6 Smooth C2 Quaternion-based Flythrough Paths
2.7 Recursive Dimensional Clustering: A Fast Algorithm for Collision Detection
2.8 Programming Fractals
Section 3 - Artificial Intelligence
3.1 Strategies for Optimizing AI
3.2 Micro-Threads for Game Object AI
3.3 Managing AI with Micro-Threads
3.4 An Architecture for RTS Command Queuing
3.5 A High-Performance Tile-based Line-of-Sight and Search System
3.6 Influence Mapping
3.7 Strategic Assessment Techniques
3.8 Terrain Reasoning for 3D Action Games
3.9 Expanded Geometry for Points-of-Visibility Pathfinding
3.10 Optimizing Points-of-Visibility Pathfinding
3.11 Flocking with Teeth: Predators and Prey
3.12 A Generic Fuzzy State Machine in C++
3.13 Imploding Combinatorial Explosion in a Fuzzy System
3.14 Using a neural network in a game: A concrete example
Section 4 - Geometry Management
4.1 Comparison of VIPM Methods
4.2 Simplified Terrain Using Interlocking Tiles
4.3 Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching
4.4 Compressed Axis-Aligned Bounding Box Trees
4.5 Direct Access Quadtree Lookup
4.6 Approximating Fish Tank Refractions
4.7 Rendering Print Resolution Screenshots
4.8 Applying Decals to Arbitrary Surfaces
4.9 Rendering Distant Scenery with Skyboxes
4.10 Self-Shadowing Characters
4.11 Classic Super Mario 64 Third-Person Control and Animation
Section 5 - Graphics Display
5.1 Cartoon Rendering: Real-time Silhouette Edge Detection and Rendering
5.2 Cartoon Rendering Using Texture Mapping and Programmable Vertex Shaders
5.3 Dynamic Per-Pixel Lighting Techniques
5.4 Generating Procedural Clouds Using 3D Hardware
5.5 Texture Masking for Faster Lens Flare
5.6 Practical Priority Buffer Shadows
5.7 Impostors: Adding Clutter
5.8 Operations for Hardware-Accelerated Procedural Texture Animation
Section 6 - Audio Programming
6.1 Game Audio Design Patterns
6.2 A Technique to Instantaneously Reuse Voices in a Sampler-based Synthesizer
6.3 Software-based DSP Effects
6.4 Interactive Processing Pipeline for Digital Audio
6.5 A Basic Music Sequencer for Games
6.6 An Interactive Music Sequencer for Games
6.7 A Low-Level Sound API
Game Programming Gems 3
Section 1 General programming
1.1 Scheduling Game Events
1.2 An Object-Composition Game Framework
1.3 Finding Redeeming Value in C-Style Macros
1.4 Platform-Independent, Function-Binding Code Generator
1.5 Handle-Based Smart Pointers
1.6 Custom STL Allocators
1.7 Save Me Now!
1.8 Autolists Design Pattern
1.9 Floating-Point Exception Handling
1.10 Programming a Game Design-Compliant Engine Using UML
1.11 Using Lex and Yacc To Parse Custom Data Files
1.12 Developing Games for a World Market
1.13 Real-Time Input and UI in 3D Games
1.14 Natural Selection: The Evolution of Pie Menus
1.15 Lightweight, Policy-Based Logging
1.16 Journaling Services
1.17 Real-Time Hierarchical Profiling
Section 2 Maths
2.1 Fast Base-2 Functions for Logarithms and Random Number Generation
2.2 Using Vector Fractions for Exact Geometry
2.3 More Approximations to Trigonometric Functions
2.4 Quaternion Compression
2.5 Constrained Inverse Kinematics
2.6 Cellular Automata for Physical Modeling
2.7 Coping with Friction in Dynamic Simulations
Section 3 Artificial Intelligence
3.1 Optimized Machine Learning with GoCap
3.2 Area Navigation: Expanding the Path-Finding Paradigm
3.3 Function Pointer-Based, Embedded Finite-State Machines
3.4 Terrain Analysis in an RTS-The Hidden Giant
3.5 An Extensible Trigger System for AI Agents, Objects, and Quests
3.6 Tactical Path-Finding with A*
3.7 A Fast Approach to Navigation Meshes
3.8 Choosing a Relationship Between Path-Finding and Collision
Section 4 Graphics
4.1 T-Junction Elimination and Retriangulation
4.2 Fast Heightfield Normal Calculation
4.3 Fast Patch Normals
4.4 Fast and Simple Occlusion Culling
4.5 Triangle Strip Creation, Optimizations, and Rendering
4.6 Computing Optimized Shadow Volumes for Complex Data Sets
4.7 Subdivision Surfaces for Character Animation
4.8 Improved Deformation of Bones
4.9 A Framework for Realistic Character Locomotion
4.10 A Programmable Vertex Shader Compiler
4.11 Billboard Beams
4.12 3D Tricks for Isometric Engines
4.13 Curvature Simulation Using Normal Maps
4.14 Methods for Dynamic, Photorealistic Terrain Lighting
4.15 Cube Map Lighting Techniques
4.16 Procedural Texturing
4.17 Unique Textures
4.18 Textures as Lookup Tables for Per-Pixel Lighting Computations
4.19 Rendering with Handcrafted Shading Models
Section 5 Network and multiplayer
5.1 Minimizing Latency in Real-Time Strategy Games
5.2 Real-Time Strategy Network Protocol
5.3 A Flexible Simulation Architecture for Massively Multiplayer Games
5.4 Scaling Multiplayer Servers
5.5 Template-Based Object Serialization
5.6 Secure Sockets
5.7 A Network Monitoring and Simulation Tool
5.8 Creating Multiplayer Games with DirectPlay 8.1
5.9 Wireless Gaming Using the Java Micro Edition
Section 6 Audio
6.1 Audio Compression with Ogg Vorbis
6.2 Creating a Compelling 3D Audio Environment
6.3 Obstruction Using Axis-Aligned Bounding Boxes
6.4 Using the Biquad Resonant Filter
6.5 Linear Predictive Coding for Voice Compression and Effects
6.6 The Stochastic Synthesis of Complex Sounds
6.7 Real-Time Modular Audio Processing for Games
Game Programming Gems 4
Section 1 General programming
1.1 The Science of Debugging Games
1.2 An HTML-Based Logging and Debugging System
1.3 The Clock: Keeping Your Finger on the Pulse of the Game
1.4 Designing and Maintaining Large Cross-Platform Libraries
1.5 Fight Memory Fragmentation with Templated Freelists
1.6 A Generic Tree Container in C++
1.7 The Beauty of Weak References and Null Objects
1.8 A System for Managing Game Entities
1.9 Address-Space Managed Dynamic Arrays for Windows and the Xbox
1.10 Critically Damped Ease-In/Ease-Out Smoothing
1.11 A Flexible, On-the-Fly Object Manager
1.12 Using Custom RTTI Properties to Stream and Edit Objects
1.13 Using XML without Sacrificing Speed
Section 2 Mathematics
2.1 Zobrist Hash Using the Mersenne Twister
2.2 Extracting Frustum and Camera Information
2.3 Solving Accuracy Problems in Large World Coordinates
2.4 Nonuniform Splines
2.5 Using the Covariance Matrix for Better-Fitting Bounding Objects
2.6 The Jacobian Transpose Method for Inverse Kinematics
Section 3 Physics
3.1 Ten Fingers of Death: Algorithms for Combat Killing
3.2 Vehicle Physics Simulation for CPU-Limited Systems
3.3 Writing a Verlet-Based Physics Engine
3.4 Constraints in Rigid Body Dynamics
3.5 Fast Contact Reduction for Dynamics Simulation
3.6 Interactive Water Surfaces
3.7 Fast Deformations with Multilayered Physics
3.8 Modal Analysis for Fast, Stable Deformation
Section 4 Artificial Intelligence
4.1 Third-Person Camera Navigation
4.2 Narrative Combat: Using AI to Enhance Tension in an Action Game
4.3 NPC Decision Making: Dealing with Randomness
4.4 An Object-Oriented Utility-Based Decision Architecture
4.5 A Distributed-Reasoning Voting Architecture
4.6 Attractors and Repulsors
4.7 Advanced Wall Building for RTS Games
4.8 Artificial Neural Networks on Programmable Graphics Hardware
Section 5 Graphics
5.1 Poster Quality Screenshots
5.2 GPU Shadow Volume Construction for Nonclosed Meshes
5.3 Perspective Shadow Maps
5.4 Combined Depth and ID-Based Shadow Buffers
5.5 Carving Static Shadows into Geometry
5.8 Techniques to Apply Team Colors to 3D Models
5.9 Fast Sepia Tone Conversion
5.10 Dynamic Gamma Using Sampled Scene Luminance
5.11 Heat and Haze Post-Processing Effects
5.13 Motion Capture Data Compression
5.14 Fast Collision Detection for 3D Bones-Based Articulated Characters
5.15 Terrain Occlusion Culling with Horizons
Section 6 Network and multiplayer
6.1 General Lobby Design and Development
6.2 Thousands of Clients per Server
6.3 Efficient MMP Game State Storage
6.4 Practical Application of Parallel-State Machines in a Client-Server Environment
6.5 Bit Packing: A Network Compression Technique
6.6 Time and Consistency Management for Multiserver-Based MMORPGs
Section 7 Audio
7.1 A Brief Introduction to OpenAL
7.2 A Simple Real-Time Lip-Synching System
7.3 Dynamic Variables and Audio Programming
7.4 Creating an Audio Scripting System
7.5 Implementing an Environmental Audio Solution Using EAX and ZoomFX
7.6 Controlling Real-Time Sound Synthesis from Game Physics
Game Programming Gems 5
Section 1 General programming
1.1 Context-Sensitive HUDs for Editors
1.2 Parsing Text Data in Games
1.3 Component Based Object Management
1.4 Using Templates for Reflection in C++
1.5 Sphere Trees for Speedy BSPs
1.6 Improved Frustum Culling
1.7 Generic Pager
1.8 Large-Scale Stack-Based State Machines
1.9 CSG Construction Using BSP Trees
1.10 Building Lua into Games
1.11 Improving Freelists with Policy Based Design
1.12 A Real-Time Remote Debug Message Logger
1.13 A Transparent Class Saving and Loading Trick
1.14 An Effective Cache-Oblivious Implementation of the ABT Tree
1.15 Visual Design of State Machines
1.16 A Generic Component Library
1.17 Choose Your Path-A Menu System
Section 2 Mathematics
2.1 Using Geometric Algebra for Computer Graphics
2.2 Minimal Acceleration Hermite Curves
2.3 Spline-Based Time Control for Animation
2.4 Faster Quaternion Interpolation Using Approximations
2.5 Minimax Numerical Approximation
2.6 Oblique View Frustums for Mirrors and Portals
Section 3 Artificial Intelligence
3.1 Automatic Cover Finding with Navigation Meshes
3.2 Fast Target Ranking Using an Artificial Potential Field
3.3 Using Lanchester Attrition Models to Predict the Results of Combat
3.4 Implementing Practical Planning for Game AI
3.5 Optimizing a Decision Tree Query Algorithm for Multithreaded Architectures
3.6 Parallel AI Development with PVM
3.7 Beyond A*
3.8 Advanced Pathfinding with Minimal Replanning Cost: Dynamic A Star (D*)
Section 4 Physics
4.1 Back of the Envelope Aerodynamics for Game Physics
4.2 Dynamic Grass Simulation and Other Natural Effects
4.3 Realistic Cloth Animation Using the Mass-Spring Model
4.4 Practical Animation of Soft Bodies for Game Development: The Pressurized Soft-Body Model
4.5 Adding Life to Ragdoll Simulation Using Feedback Control Systems
4.6 Designing a Prescripted Physics System
4.7 Prescripted Physics: Techniques and Applications
4.8 Realistic Camera Movement in a 3D Car Simulator
Section 5 Graphics
5.1 Realistic Cloud Rendering on Modern GPUs
5.2 Let It Snow, Let It Snow, Let It Snow (and Rain)
5.3 Widgets: Rendering Fast and Persistent Foliage
5.4 2.5 Dimensional Impostors for Realistic Trees and Forests
5.5 Gridless Controllable Fire
5.6 Powerful Explosion Effects Using Billboard Particles
5.7 A Simple Method for Rendering Gemstones
5.8 Volumetric Post-Processing
5.9 Procedural Level Generation
5.10 Recombinant Shaders
Section 6 Network and multiplayer
6.1 Keeping a Massively Multiplayer Online Game Massive, Online, and Persistent
6.2 Implementing a Seamless World Server
6.3 Designing a Vulgarity Filtering System
6.4 Fast and Efficient Implementation of a Remote Procedure Call System
6.5 Overcoming Network Address Translation in Peer-to-Peer Communications
6.6 A Reliable Messaging Protocol
6.7 Safe Random Number Systems
6.8 Secure by Design
Section 7 Audio
7.1 Multithreaded Audio Programming Techniques
7.2 Sound Management by Group
7.3 Using 3D Surfaces as Audio Emitters
7.4 Fast Environmental Reverb Based on Feedback Delay Networks
7.5 Introduction to Single-Speaker Speech Recognition
Game Programming Gems 6
Section 1 General programming
1.1 Lock-Free Algorithms
1.2 Utilizing Multicore Processors with OpenMP
1.3 Computer Vision in Games Using the OpenCV Library
1.4 Geographic Grid Registration of Game Objects
1.5 BSP Techniques
1.6 Closest-String Matching Algorithm
1.7 Using CppUnit To Implement Unit Testing
1.8 Fingerprinting Pre-Release Builds To Deter and Detect Piracy
1.9 Faster File Loading with Access-Based File Reordering
1.10 Stay in the Game: Asset Hotloading for Fast Iteration
Section 2 Mathematics and Physics
2.1 Floating-Point Tricks
2.2 GPU Computation in Projective Space Using Homogeneous Coordinates
2.3 Solving Systems of Linear Equations Using the Cross Product
2.4 Sequence Indexing for Game Development
2.5 Exact Buoyancy for Polyhedra
2.6 Real-Time Particle-Based Fluid Simulation with Rigid Body Interaction
Section 3 Artificial Intelligence
3.1 Applying Model-Based Decision-Making Methods to Games: Applying the Locust AI Engine to Quake III
3.2 Achieving Coordination with Autonomous NPCs
3.3 Behavior-Based Robotic Architectures for Games
3.4 Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Extended Behaviour Networks
3.5 A Goal-Oriented Unreal Bot: Building a Game Agent with Goal-Oriented Behaviour and Simple Personality Using Extended Behaviour Networks
3.6 Short-Term Memory Modelling Using a Support Vector Machine
3.7 Using the Quantified Judgment Model for Engagement Analysis
3.8 Designing a Multilayer, Pluggable AI Engine
3.9 A Fuzzy-Control Approach to Managing Scene Complexity
Section 4 Scripting and data-driven systems
4.1 Scripting Language Survey
4.2 Binding C/C++ Objects to Lua
4.3 Programming Advanced Control Mechanisms with Lua Coroutines
4.4 Managing High-Level Script Execution Within Multithreaded Environments
4.5 Exposing Actor Properties Using Nonintrusive Proxies
4.6 Game Object Component System
Section 5 Graphics
5.1 Synthesis of Realistic Idle Motion for Interactive Characters
5.2 Spatial Partitioning Using an Adaptive Binary Tree
5.3 Enhanced Object Culling with (Almost) Oriented Bounding Boxes
5.4 Skin Splitting for Optimal Rendering
5.5 GPU Terrain Rendering
5.6 Interactive Fluid Dynamics and Rendering on the GPU
5.7 Fast Per-Pixel Lighting with Many Lights
5.8 Rendering Road Signs Sharply
5.9 Practical Sky Rendering for Games
5.10 High Dynamic Range Rendering Using OpenGL Frame Buffer Objects
Section 6 Audio
6.1 Real-Time Sound Generation from Deformable Meshes
6.2 A Lightweight Generator for Real-Time Sound Effects
6.3 Real-Time Mixing Busses
6.4 Potentially Audible Sets
6.5 A Cheap Doppler Effect
6.6 Faking Real-Time DSP Effects
Section 7 Network and multiplayer
7.1 Dynamically Adaptive Streaming of 3D Data for Animated Characters
7.2 Complex Systems-Based High-Level Architecture for Massively Multiplayer Games
7.3 Generating Globally Unique Identifiers for Game Objects
7.4 Massively Multiplayer Online Prototype Utilizing Second Life for Game Concept Prototyping
7.5 Reliable Peer-to-Peer Gaming Connections Penetrating NAT
Game Programming Gems 7
Game Programming Gems 8
Section 1 Graphics
1.1 Fast Font Rendering with Instancing
1.2 Principles and Practice of Screen Space Ambient Occlusion
1.3 Multi-Resolution Deferred Shading
1.4 View Frustum Culling of Catmull-Clark Patches in DirectX 11
1.5 Ambient Occlusion Using DirectX Compute Shader
1.6 Eye-View Pixel Anti-Aliasing for Irregular Shadow Mapping
1.7 Overlapped Execution on Programmable Graphics Hardware
1.8 Techniques for Effective Vertex and Fragment Shading on the SPUs
Section 2 Physics and animation
2.1 A Versatile and Interactive Anatomical Human Face Model
2.2 Curved Paths for Seamless Character Animation
2.3 Non-Iterative, Closed-Form, Inverse Kinematic Chain Solver (NCF IK)
2.4 Particle Swarm Optimization for Game Programming
2.5 Improved Numerical Integration with Analytical Techniques
2.6 What a Drag: Modeling Realistic Three-Dimensional Air and Fluid Resistance
2.7 Application of Quasi-Fluid Dynamics for Arbitrary Closed Meshes
2.8 Approximate Convex Decomposition for Real-Time Collision Detection
Section 3 Artificial intelligence
3.1 AI Level of Detail for Really Large Worlds
3.2 A Pattern-Based Approach to Modular AI for Games
3.3 Automated Navigation Mesh Generation Using Advanced Growth-Based Techniques
3.4 A Practical Spatial Architecture for Animal and Agent Navigation
3.5 Applying Control Theory to Game AI and Physics
3.6 Adaptive Tactic Selection in First-Person Shooter (FPS) Games
3.7 Embracing Chaos Theory: Generating Apparent Unpredictability through Deterministic Systems
3.8 Needs-Based AI
3.9 A Framework for Emotional Digital Actors
3.10 Scalable Dialog Authoring
3.11 Graph-Based Data Mining for Player Trace Analysis in MMORPGs
Section 4 General programming
4.1 Fast-IsA
4.2 Registered Variables
4.3 Efficient and Scalable Multi-Core Programming
4.4 Game Optimization through the Lens of Memory and Data Access
4.5 Stack Allocation
4.6 Design and Implementation of an In-Game Memory Profiler
4.7 A More Informative Error Log Generator
4.8 Code Coverage for QA
4.9 Domain-Specific Languages in Game Engines
4.10 A Flexible User Interface Layout System for Divergent Environments
4.11 Road Creation for Projectable Terrain Meshes
4.12 Developing for Digital Drawing Tablets
4.13 Creating a Multi-Threaded Actor-Based Architecture Using Intel® Threading Building Blocks
Section 5 Networking and Multiplayer
5.1 Secure Channel Communication
5.2 Social Networks in Games: Playing with Your Facebook Friends
5.3 Asynchronous I/O for Scalable Game Servers
5.4 Introduction to 3D Streaming Technology in Massively Multiplayer Online Games
Section 6 Audio
6.1 A Practical DSP Radio Effect
6.2 Empowering Your Audio Team with a Great Engine
6.3 Real-Time Sound Synthesis for Rigid Bodies
Section 7 General Purpose Computing on GPUs
7.1 Using Heterogeneous Parallel Architectures with OpenCL
7.2 PhysX GPU Rigid Bodies in Batman: Arkham Asylum
7.3 Fast GPU Fluid Simulation in PhysX
Game Programming Gems 1
Section 1 Programming
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 Polygonal 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
Game Programming Gems 2
Section 1 - General Programming
1.1 Optimizations for C++ games
1.2 Inline Functions Versus Macros
1.3 Programming with Abstract Interfaces
1.4 Exporting C++ Classes from DLLs
1.5 Protect yourself from DLL Hell and Missing OS Functions
1.6 Dynamic Type Information
1.7 A Property Class for Generic C++ Member Access
1.8 A Game Entity Factory
1.9 Adding Deprecation Facilities to C++
1.10 A Drop-in Debug Memory Manager
1.11 A Built-in Game Profiling Module
1.12 Linear Programming Model for Windows-based Games
1.13 Stack Winding
1.14 Self-Modifying Code
1.15 File Management using Resource Files
1.16 Game Input Recording and Playback
1.17 A Flexible Text Parsing System
1.18 A Generic Tweaker
1.19 Genuine Random Number Generation
1.20 Using Bloom Filters to Improve Computational Performance
1.21 3ds Max Skin exporter and animation toolkit
1.22 Using Web Cameras in Video Games
Section 2 - Mathematics
2.1 Floating-Point Tricks: Improving Performance with IEEE Floating Point
2.2 Vector and Plane Tricks
2.3 Fast, Robust Intersection of 3D Line Segments
2.4 Inverse Trajectory Determination
2.5 The Parallel Transport Frame
2.6 Smooth C2 Quaternion-based Flythrough Paths
2.7 Recursive Dimensional Clustering: A Fast Algorithm for Collision Detection
2.8 Programming Fractals
Section 3 - Artificial Intelligence
3.1 Strategies for Optimizing AI
3.2 Micro-Threads for Game Object AI
3.3 Managing AI with Micro-Threads
3.4 An Architecture for RTS Command Queuing
3.5 A High-Performance Tile-based Line-of-Sight and Search System
3.6 Influence Mapping
3.7 Strategic Assessment Techniques
3.8 Terrain Reasoning for 3D Action Games
3.9 Expanded Geometry for Points-of-Visibility Pathfinding
3.10 Optimizing Points-of-Visibility Pathfinding
3.11 Flocking with Teeth: Predators and Prey
3.12 A Generic Fuzzy State Machine in C++
3.13 Imploding Combinatorial Explosion in a Fuzzy System
3.14 Using a neural network in a game: A concrete example
Section 4 - Geometry Management
4.1 Comparison of VIPM Methods
4.2 Simplified Terrain Using Interlocking Tiles
4.3 Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching
4.4 Compressed Axis-Aligned Bounding Box Trees
4.5 Direct Access Quadtree Lookup
4.6 Approximating Fish Tank Refractions
4.7 Rendering Print Resolution Screenshots
4.8 Applying Decals to Arbitrary Surfaces
4.9 Rendering Distant Scenery with Skyboxes
4.10 Self-Shadowing Characters
4.11 Classic Super Mario 64 Third-Person Control and Animation
Section 5 - Graphics Display
5.1 Cartoon Rendering: Real-time Silhouette Edge Detection and Rendering
5.2 Cartoon Rendering Using Texture Mapping and Programmable Vertex Shaders
5.3 Dynamic Per-Pixel Lighting Techniques
5.4 Generating Procedural Clouds Using 3D Hardware
5.5 Texture Masking for Faster Lens Flare
5.6 Practical Priority Buffer Shadows
5.7 Impostors: Adding Clutter
5.8 Operations for Hardware-Accelerated Procedural Texture Animation
Section 6 - Audio Programming
6.1 Game Audio Design Patterns
6.2 A Technique to Instantaneously Reuse Voices in a Sampler-based Synthesizer
6.3 Software-based DSP Effects
6.4 Interactive Processing Pipeline for Digital Audio
6.5 A Basic Music Sequencer for Games
6.6 An Interactive Music Sequencer for Games
6.7 A Low-Level Sound API
Game Programming Gems 3
Section 1 General programming
1.1 Scheduling Game Events
1.2 An Object-Composition Game Framework
1.3 Finding Redeeming Value in C-Style Macros
1.4 Platform-Independent, Function-Binding Code Generator
1.5 Handle-Based Smart Pointers
1.6 Custom STL Allocators
1.7 Save Me Now!
1.8 Autolists Design Pattern
1.9 Floating-Point Exception Handling
1.10 Programming a Game Design-Compliant Engine Using UML
1.11 Using Lex and Yacc To Parse Custom Data Files
1.12 Developing Games for a World Market
1.13 Real-Time Input and UI in 3D Games
1.14 Natural Selection: The Evolution of Pie Menus
1.15 Lightweight, Policy-Based Logging
1.16 Journaling Services
1.17 Real-Time Hierarchical Profiling
Section 2 Maths
2.1 Fast Base-2 Functions for Logarithms and Random Number Generation
2.2 Using Vector Fractions for Exact Geometry
2.3 More Approximations to Trigonometric Functions
2.4 Quaternion Compression
2.5 Constrained Inverse Kinematics
2.6 Cellular Automata for Physical Modeling
2.7 Coping with Friction in Dynamic Simulations
Section 3 Artificial Intelligence
3.1 Optimized Machine Learning with GoCap
3.2 Area Navigation: Expanding the Path-Finding Paradigm
3.3 Function Pointer-Based, Embedded Finite-State Machines
3.4 Terrain Analysis in an RTS-The Hidden Giant
3.5 An Extensible Trigger System for AI Agents, Objects, and Quests
3.6 Tactical Path-Finding with A*
3.7 A Fast Approach to Navigation Meshes
3.8 Choosing a Relationship Between Path-Finding and Collision
Section 4 Graphics
4.1 T-Junction Elimination and Retriangulation
4.2 Fast Heightfield Normal Calculation
4.3 Fast Patch Normals
4.4 Fast and Simple Occlusion Culling
4.5 Triangle Strip Creation, Optimizations, and Rendering
4.6 Computing Optimized Shadow Volumes for Complex Data Sets
4.7 Subdivision Surfaces for Character Animation
4.8 Improved Deformation of Bones
4.9 A Framework for Realistic Character Locomotion
4.10 A Programmable Vertex Shader Compiler
4.11 Billboard Beams
4.12 3D Tricks for Isometric Engines
4.13 Curvature Simulation Using Normal Maps
4.14 Methods for Dynamic, Photorealistic Terrain Lighting
4.15 Cube Map Lighting Techniques
4.16 Procedural Texturing
4.17 Unique Textures
4.18 Textures as Lookup Tables for Per-Pixel Lighting Computations
4.19 Rendering with Handcrafted Shading Models
Section 5 Network and multiplayer
5.1 Minimizing Latency in Real-Time Strategy Games
5.2 Real-Time Strategy Network Protocol
5.3 A Flexible Simulation Architecture for Massively Multiplayer Games
5.4 Scaling Multiplayer Servers
5.5 Template-Based Object Serialization
5.6 Secure Sockets
5.7 A Network Monitoring and Simulation Tool
5.8 Creating Multiplayer Games with DirectPlay 8.1
5.9 Wireless Gaming Using the Java Micro Edition
Section 6 Audio
6.1 Audio Compression with Ogg Vorbis
6.2 Creating a Compelling 3D Audio Environment
6.3 Obstruction Using Axis-Aligned Bounding Boxes
6.4 Using the Biquad Resonant Filter
6.5 Linear Predictive Coding for Voice Compression and Effects
6.6 The Stochastic Synthesis of Complex Sounds
6.7 Real-Time Modular Audio Processing for Games
Game Programming Gems 4
Section 1 General programming
1.1 The Science of Debugging Games
1.2 An HTML-Based Logging and Debugging System
1.3 The Clock: Keeping Your Finger on the Pulse of the Game
1.4 Designing and Maintaining Large Cross-Platform Libraries
1.5 Fight Memory Fragmentation with Templated Freelists
1.6 A Generic Tree Container in C++
1.7 The Beauty of Weak References and Null Objects
1.8 A System for Managing Game Entities
1.9 Address-Space Managed Dynamic Arrays for Windows and the Xbox
1.10 Critically Damped Ease-In/Ease-Out Smoothing
1.11 A Flexible, On-the-Fly Object Manager
1.12 Using Custom RTTI Properties to Stream and Edit Objects
1.13 Using XML without Sacrificing Speed
Section 2 Mathematics
2.1 Zobrist Hash Using the Mersenne Twister
2.2 Extracting Frustum and Camera Information
2.3 Solving Accuracy Problems in Large World Coordinates
2.4 Nonuniform Splines
2.5 Using the Covariance Matrix for Better-Fitting Bounding Objects
2.6 The Jacobian Transpose Method for Inverse Kinematics
Section 3 Physics
3.1 Ten Fingers of Death: Algorithms for Combat Killing
3.2 Vehicle Physics Simulation for CPU-Limited Systems
3.3 Writing a Verlet-Based Physics Engine
3.4 Constraints in Rigid Body Dynamics
3.5 Fast Contact Reduction for Dynamics Simulation
3.6 Interactive Water Surfaces
3.7 Fast Deformations with Multilayered Physics
3.8 Modal Analysis for Fast, Stable Deformation
Section 4 Artificial Intelligence
4.1 Third-Person Camera Navigation
4.2 Narrative Combat: Using AI to Enhance Tension in an Action Game
4.3 NPC Decision Making: Dealing with Randomness
4.4 An Object-Oriented Utility-Based Decision Architecture
4.5 A Distributed-Reasoning Voting Architecture
4.6 Attractors and Repulsors
4.7 Advanced Wall Building for RTS Games
4.8 Artificial Neural Networks on Programmable Graphics Hardware
Section 5 Graphics
5.1 Poster Quality Screenshots
5.2 GPU Shadow Volume Construction for Nonclosed Meshes
5.3 Perspective Shadow Maps
5.4 Combined Depth and ID-Based Shadow Buffers
5.5 Carving Static Shadows into Geometry
5.8 Techniques to Apply Team Colors to 3D Models
5.9 Fast Sepia Tone Conversion
5.10 Dynamic Gamma Using Sampled Scene Luminance
5.11 Heat and Haze Post-Processing Effects
5.13 Motion Capture Data Compression
5.14 Fast Collision Detection for 3D Bones-Based Articulated Characters
5.15 Terrain Occlusion Culling with Horizons
Section 6 Network and multiplayer
6.1 General Lobby Design and Development
6.2 Thousands of Clients per Server
6.3 Efficient MMP Game State Storage
6.4 Practical Application of Parallel-State Machines in a Client-Server Environment
6.5 Bit Packing: A Network Compression Technique
6.6 Time and Consistency Management for Multiserver-Based MMORPGs
Section 7 Audio
7.1 A Brief Introduction to OpenAL
7.2 A Simple Real-Time Lip-Synching System
7.3 Dynamic Variables and Audio Programming
7.4 Creating an Audio Scripting System
7.5 Implementing an Environmental Audio Solution Using EAX and ZoomFX
7.6 Controlling Real-Time Sound Synthesis from Game Physics
Game Programming Gems 5Section 1 General programming
1.1 Context-Sensitive HUDs for Editors
1.2 Parsing Text Data in Games
1.3 Component Based Object Management
1.4 Using Templates for Reflection in C++
1.5 Sphere Trees for Speedy BSPs
1.6 Improved Frustum Culling
1.7 Generic Pager
1.8 Large-Scale Stack-Based State Machines
1.9 CSG Construction Using BSP Trees
1.10 Building Lua into Games
1.11 Improving Freelists with Policy Based Design
1.12 A Real-Time Remote Debug Message Logger
1.13 A Transparent Class Saving and Loading Trick
1.14 An Effective Cache-Oblivious Implementation of the ABT Tree
1.15 Visual Design of State Machines
1.16 A Generic Component Library
1.17 Choose Your Path-A Menu System
Section 2 Mathematics
2.1 Using Geometric Algebra for Computer Graphics
2.2 Minimal Acceleration Hermite Curves
2.3 Spline-Based Time Control for Animation
2.4 Faster Quaternion Interpolation Using Approximations
2.5 Minimax Numerical Approximation
2.6 Oblique View Frustums for Mirrors and Portals
Section 3 Artificial Intelligence
3.1 Automatic Cover Finding with Navigation Meshes
3.2 Fast Target Ranking Using an Artificial Potential Field
3.3 Using Lanchester Attrition Models to Predict the Results of Combat
3.4 Implementing Practical Planning for Game AI
3.5 Optimizing a Decision Tree Query Algorithm for Multithreaded Architectures
3.6 Parallel AI Development with PVM
3.7 Beyond A*
3.8 Advanced Pathfinding with Minimal Replanning Cost: Dynamic A Star (D*)
Section 4 Physics
4.1 Back of the Envelope Aerodynamics for Game Physics
4.2 Dynamic Grass Simulation and Other Natural Effects
4.3 Realistic Cloth Animation Using the Mass-Spring Model
4.4 Practical Animation of Soft Bodies for Game Development: The Pressurized Soft-Body Model
4.5 Adding Life to Ragdoll Simulation Using Feedback Control Systems
4.6 Designing a Prescripted Physics System
4.7 Prescripted Physics: Techniques and Applications
4.8 Realistic Camera Movement in a 3D Car Simulator
Section 5 Graphics
5.1 Realistic Cloud Rendering on Modern GPUs
5.2 Let It Snow, Let It Snow, Let It Snow (and Rain)
5.3 Widgets: Rendering Fast and Persistent Foliage
5.4 2.5 Dimensional Impostors for Realistic Trees and Forests
5.5 Gridless Controllable Fire
5.6 Powerful Explosion Effects Using Billboard Particles
5.7 A Simple Method for Rendering Gemstones
5.8 Volumetric Post-Processing
5.9 Procedural Level Generation
5.10 Recombinant Shaders
Section 6 Network and multiplayer
6.1 Keeping a Massively Multiplayer Online Game Massive, Online, and Persistent
6.2 Implementing a Seamless World Server
6.3 Designing a Vulgarity Filtering System
6.4 Fast and Efficient Implementation of a Remote Procedure Call System
6.5 Overcoming Network Address Translation in Peer-to-Peer Communications
6.6 A Reliable Messaging Protocol
6.7 Safe Random Number Systems
6.8 Secure by Design
Section 7 Audio
7.1 Multithreaded Audio Programming Techniques
7.2 Sound Management by Group
7.3 Using 3D Surfaces as Audio Emitters
7.4 Fast Environmental Reverb Based on Feedback Delay Networks
7.5 Introduction to Single-Speaker Speech Recognition
Game Programming Gems 6Section 1 General programming
1.1 Lock-Free Algorithms
1.2 Utilizing Multicore Processors with OpenMP
1.3 Computer Vision in Games Using the OpenCV Library
1.4 Geographic Grid Registration of Game Objects
1.5 BSP Techniques
1.6 Closest-String Matching Algorithm
1.7 Using CppUnit To Implement Unit Testing
1.8 Fingerprinting Pre-Release Builds To Deter and Detect Piracy
1.9 Faster File Loading with Access-Based File Reordering
1.10 Stay in the Game: Asset Hotloading for Fast Iteration
Section 2 Mathematics and Physics
2.1 Floating-Point Tricks
2.2 GPU Computation in Projective Space Using Homogeneous Coordinates
2.3 Solving Systems of Linear Equations Using the Cross Product
2.4 Sequence Indexing for Game Development
2.5 Exact Buoyancy for Polyhedra
2.6 Real-Time Particle-Based Fluid Simulation with Rigid Body Interaction
Section 3 Artificial Intelligence
3.1 Applying Model-Based Decision-Making Methods to Games: Applying the Locust AI Engine to Quake III
3.2 Achieving Coordination with Autonomous NPCs
3.3 Behavior-Based Robotic Architectures for Games
3.4 Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Extended Behaviour Networks
3.5 A Goal-Oriented Unreal Bot: Building a Game Agent with Goal-Oriented Behaviour and Simple Personality Using Extended Behaviour Networks
3.6 Short-Term Memory Modelling Using a Support Vector Machine
3.7 Using the Quantified Judgment Model for Engagement Analysis
3.8 Designing a Multilayer, Pluggable AI Engine
3.9 A Fuzzy-Control Approach to Managing Scene Complexity
Section 4 Scripting and data-driven systems
4.1 Scripting Language Survey
4.2 Binding C/C++ Objects to Lua
4.3 Programming Advanced Control Mechanisms with Lua Coroutines
4.4 Managing High-Level Script Execution Within Multithreaded Environments
4.5 Exposing Actor Properties Using Nonintrusive Proxies
4.6 Game Object Component System
Section 5 Graphics
5.1 Synthesis of Realistic Idle Motion for Interactive Characters
5.2 Spatial Partitioning Using an Adaptive Binary Tree
5.3 Enhanced Object Culling with (Almost) Oriented Bounding Boxes
5.4 Skin Splitting for Optimal Rendering
5.5 GPU Terrain Rendering
5.6 Interactive Fluid Dynamics and Rendering on the GPU
5.7 Fast Per-Pixel Lighting with Many Lights
5.8 Rendering Road Signs Sharply
5.9 Practical Sky Rendering for Games
5.10 High Dynamic Range Rendering Using OpenGL Frame Buffer Objects
Section 6 Audio
6.1 Real-Time Sound Generation from Deformable Meshes
6.2 A Lightweight Generator for Real-Time Sound Effects
6.3 Real-Time Mixing Busses
6.4 Potentially Audible Sets
6.5 A Cheap Doppler Effect
6.6 Faking Real-Time DSP Effects
Section 7 Network and multiplayer
7.1 Dynamically Adaptive Streaming of 3D Data for Animated Characters
7.2 Complex Systems-Based High-Level Architecture for Massively Multiplayer Games
7.3 Generating Globally Unique Identifiers for Game Objects
7.4 Massively Multiplayer Online Prototype Utilizing Second Life for Game Concept Prototyping
7.5 Reliable Peer-to-Peer Gaming Connections Penetrating NAT
Game Programming Gems 7
Game Programming Gems 8Section 1 Graphics
1.1 Fast Font Rendering with Instancing
1.2 Principles and Practice of Screen Space Ambient Occlusion
1.3 Multi-Resolution Deferred Shading
1.4 View Frustum Culling of Catmull-Clark Patches in DirectX 11
1.5 Ambient Occlusion Using DirectX Compute Shader
1.6 Eye-View Pixel Anti-Aliasing for Irregular Shadow Mapping
1.7 Overlapped Execution on Programmable Graphics Hardware
1.8 Techniques for Effective Vertex and Fragment Shading on the SPUs
Section 2 Physics and animation
2.1 A Versatile and Interactive Anatomical Human Face Model
2.2 Curved Paths for Seamless Character Animation
2.3 Non-Iterative, Closed-Form, Inverse Kinematic Chain Solver (NCF IK)
2.4 Particle Swarm Optimization for Game Programming
2.5 Improved Numerical Integration with Analytical Techniques
2.6 What a Drag: Modeling Realistic Three-Dimensional Air and Fluid Resistance
2.7 Application of Quasi-Fluid Dynamics for Arbitrary Closed Meshes
2.8 Approximate Convex Decomposition for Real-Time Collision Detection
Section 3 Artificial intelligence
3.1 AI Level of Detail for Really Large Worlds
3.2 A Pattern-Based Approach to Modular AI for Games
3.3 Automated Navigation Mesh Generation Using Advanced Growth-Based Techniques
3.4 A Practical Spatial Architecture for Animal and Agent Navigation
3.5 Applying Control Theory to Game AI and Physics
3.6 Adaptive Tactic Selection in First-Person Shooter (FPS) Games
3.7 Embracing Chaos Theory: Generating Apparent Unpredictability through Deterministic Systems
3.8 Needs-Based AI
3.9 A Framework for Emotional Digital Actors
3.10 Scalable Dialog Authoring
3.11 Graph-Based Data Mining for Player Trace Analysis in MMORPGs
Section 4 General programming
4.1 Fast-IsA
4.2 Registered Variables
4.3 Efficient and Scalable Multi-Core Programming
4.4 Game Optimization through the Lens of Memory and Data Access
4.5 Stack Allocation
4.6 Design and Implementation of an In-Game Memory Profiler
4.7 A More Informative Error Log Generator
4.8 Code Coverage for QA
4.9 Domain-Specific Languages in Game Engines
4.10 A Flexible User Interface Layout System for Divergent Environments
4.11 Road Creation for Projectable Terrain Meshes
4.12 Developing for Digital Drawing Tablets
4.13 Creating a Multi-Threaded Actor-Based Architecture Using Intel® Threading Building Blocks
Section 5 Networking and Multiplayer
5.1 Secure Channel Communication
5.2 Social Networks in Games: Playing with Your Facebook Friends
5.3 Asynchronous I/O for Scalable Game Servers
5.4 Introduction to 3D Streaming Technology in Massively Multiplayer Online Games
Section 6 Audio
6.1 A Practical DSP Radio Effect
6.2 Empowering Your Audio Team with a Great Engine
6.3 Real-Time Sound Synthesis for Rigid Bodies
Section 7 General Purpose Computing on GPUs
7.1 Using Heterogeneous Parallel Architectures with OpenCL
7.2 PhysX GPU Rigid Bodies in Batman: Arkham Asylum
7.3 Fast GPU Fluid Simulation in PhysX
Monday, April 19, 2010
C++ Code Performance
There are lots of things that a C++ programmer can do to increase the performance of the written code.
Amdahl's law:
1. Constness
Use the keyword constant as much as possible: in variables, function arguments, return values, and member functions.
void SetHeight( const int & height);
Also use const in return values to prevent that value to be changed:
2. Function parameters
Pass arguments by reference instead of pass-by-value to eliminate its overhead by avoiding the copy unnecessary objects. To make sure the object reference passed it is not modified use the const keyword.
3. Constructor and destructor
Try to not call the constructor unless it is absolutely necessary. The fastest code is that which never runs.
When arg is zero, we pay the cost of calling Object's constructor and destructor. If arg is often zero, and especially if Object itself allocates memory, this waste can add up in a hurry. The solution, of course, is to move the declaration of obj until after the if statement.
Two techniques very useful to reduce the call overhead are: inline them and use initialisation list.
Inefficient:
4. Function types
5. Inlining
The compiler takes care of removing the function call and embeds its content directly into the calling code in order to avoid the overhead of the function call. Inline should be used only with small, frequently used functions. However, the compiler decides whether to inline the function or not.
6. Return values
7. Avoid copies and temporaries
a) Prefer preincrement to postincrement
The problem with writing x = y++ is that the increment function has to make a
copy of the original value of y, increment y, and then return the original value.
Thus, postincrement involves the construction of a temporary object, while
preincrement doesn't. For integers, there's no additional overhead, but for userdefined types, this is wasteful. You should use preincrement whenever you have
the option. You almost always have the option in for loop iterators.
8. Operator overloading
Try to avoid binary operators, the return type is not a reference or a pointer, but an object itself. That means that the compiler first will create a temporary object, load it with the result and then will copy it into the caller variable.
Bibliography
Amdahl's law:
the performance improvement to be gained from using some faster mode of execution is limited by the fraction of the time the faster mode can be used.
Overall SpeedUp = 1/( (1-f) + (f/s) )
f: fraction of a program that is enhanced
s: speedup of the enhanced portion
1. Constness
Use the keyword constant as much as possible: in variables, function arguments, return values, and member functions.
- const int MAX = 4 vs #define MAX = 4
- Functions
void SetHeight( const int & height);
Also use const in return values to prevent that value to be changed:
const char * GetName();- Classes
const char * GetName() const;2. Function parameters
Pass arguments by reference instead of pass-by-value to eliminate its overhead by avoiding the copy unnecessary objects. To make sure the object reference passed it is not modified use the const keyword.
void MyGame::Update( Matrix mat) {...} // By value - expensivevoid MyGame::Update( const Matrix & mat) {...} // By reference - faster3. Constructor and destructor
Try to not call the constructor unless it is absolutely necessary. The fastest code is that which never runs.
void Function(int arg)
{
Object obj;
if (arg *= 0)
return;
//...
}
When arg is zero, we pay the cost of calling Object's constructor and destructor. If arg is often zero, and especially if Object itself allocates memory, this waste can add up in a hurry. The solution, of course, is to move the declaration of obj until after the if statement.
Two techniques very useful to reduce the call overhead are: inline them and use initialisation list.
Inefficient:
Enemy::Enemy()Efficient:
{
m_strName = "game_enemy";
m_position = Vector3( 0.0f , 0.0f ,0.0f );
m_life = 100;
}
Enemy::Enemy():In this case, the initialisation happens only once as the objects are constructed and initialised.
m_strName = "game_enemy",
m_position = Vector3( 0.0f , 0.0f ,0.0f ),
m_life = 100
{}
4. Function types
5. Inlining
The compiler takes care of removing the function call and embeds its content directly into the calling code in order to avoid the overhead of the function call. Inline should be used only with small, frequently used functions. However, the compiler decides whether to inline the function or not.
inline bool isDead() const { return (m_live==0); }It has some drawbacks:- The size of the executable could increase out of control, due to every part of the code that calls the function would duplicate that function's call.
- For a function to be inlined, its definition has to be present in the header file. That means that "include" statements that could otherwise be in the .cpp have to be moved to the .h file, which results in longer compile times.
6. Return values
7. Avoid copies and temporaries
a) Prefer preincrement to postincrement
The problem with writing x = y++ is that the increment function has to make a
copy of the original value of y, increment y, and then return the original value.
Thus, postincrement involves the construction of a temporary object, while
preincrement doesn't. For integers, there's no additional overhead, but for userdefined types, this is wasteful. You should use preincrement whenever you have
the option. You almost always have the option in for loop iterators.
8. Operator overloading
Try to avoid binary operators, the return type is not a reference or a pointer, but an object itself. That means that the compiler first will create a temporary object, load it with the result and then will copy it into the caller variable.
const Vector3d operator+( const Vector3d & v1, const Vector3d & v2 )The solution is to replace binary operators with unary operators.In this case, we are not copying any object, we are just returning a reference to the object the function acted upon.
{
return Vector3d( v1.x + v2.x, v1.y + v2.y, v1.z + v2.z );
}
Vector3d & Vector3d::operator+=( const Vector3d & v )9. Cache friendly
{
x+= v.x; y+= v.y; z+=v.z;
return *this;
}
- Object size
- Member variables order
- Memory allignment
- Load-Hit-Store
- Object Pools
Bibliography
Sunday, April 18, 2010
Load-Hit-Store
90% of the time is spent in 10% of the code, so make that 10% the fastest code it can be.
Load-Hit-Store: is one of those quirky CPU implementation details that can cause significant performance problems in high-level code. It happens when the compiler writes data to an address 'x' and the tries to load the data from 'x' again too song.
This sequence of a memory read operation (LOAD), the assignment of the value to a register (HIT) and the actual writing of the value into a register (LOAD) is usually hidden away in stages of the pipelines, so these operations cause no stalls. However, if the memory location being read was one recently written to by a previous write operation, it can take as many at 40 cycles before the Store operation can complete.
stfs fr3, 0(r3) // Store the float - takes up to 40 cycles
lwz r9, 0(r3) // Load r3 into r9
add r9, r1, r9 // Stall: use r9 before the store operation has finished
There are different ways to generate LHS:
Using member values or references pointers as iterators in tight loops
Example A:for( int i = 0; i < 100; i++ )
{
m_iData++; // As member function it is stored in memory
}
//-----------------------------------------------------------
Example B:
void foo( int & count ) // the variable count is memory bound
{
for( int i = 0; i < 100; i++ )
{
count++; // As member function it is stored in memory
}
}
Solution: use registers that invoke no penalty
Example A:
int iData = m_iData;
for( int i = 0; i < 100; i++ )
{
iData++; // The local variable is stores in a register
}
m_iData = iData;
//-----------------------------------------------------------
Example B:
void foo( int & output )
{
int count = output;
for( int i = 0; i < 100; i++ )
{
count++; // As member function it is stored in memory
}
output = count;
}
Conversion between int and float
Try to avoid int to float conversions like:
float fAngle = (float)i * fAngleDelta;
Solution: It will be better to have int and float duplicated members.
typedef struct ScreenSize
{
int m_iWidth;
int m_iHeight;
float m_fWidth;
float m_fHeight;
// Update both, int and float
inline void SetHeight( int iWidth)
{
m_iWidth = iWidth;
m_fWidht = static_cast(iWidth);
}
}
C++ constructors that have just one parameter automatically
perform implicit type conversion. If you pass anint when the
constructor expects a float, the compiler will add the
necessary code to convert int to float. This will cause a
Load-Hit-Store issue. It is possible to add the explicit
keyword to the constructor declaration to prevent implicit
conversions. This, forces the code to either use a parameter of
the correct type, or cast the parameter to the correct type.
Read and write in memory too close
int CauseLHS( int *ptrA )
{
int a,b;
int * ptrB = ptrA; // B and A point to the same direction
*ptrA = 5; // Write data to address prtA
b = *ptrB; // Read that data back again
//(won't be available for 40/80 cycles)
a = b + 10;// Stall! The data b isn't available yet
}
Solution: this seems like the sort of thing the compiler should notice and fix by simply keeping content of *ptrA in a register. But it doesn't, so it is obliged to read memory back from a pointer every time yo dereference it, because any other pointer in the function might have aliased and modified the data. The keyword __restrict on a pointer promises the compiler that it has no aliases: nothing else in the function points to that same data. Thus, this keyword helps to avoid LHS.
The compiler knows that if it writes data to a pointer, it doesn't need to read it back into a register later on because nothing else could have written to that address. Without __restrict, the compiler is forced to read data from every pointer every time it is used, because another pointer may have aliased x.
This keyword is a promise you make to the compiler. If you break your promise, you can get incorrect results. If pointer pA and pB are __restrict and pA==pB that will cause mysterious bugs.
int slow( int * a, int * b)
{
*a = 5;
*b = 7;
return *a + *b; // Stall! The compiler doesn't know whether
// a==b, so it has to reload both
// before the add
}
int fast( int *__restrict a, int *__restrict b)
{
*a = 5;
*b = 7; // Restrict promises that a!=b
return *a + *b; // No stall, a & b are in registers
}
There is no way to mark references as __restrict. In this case, copy the parameters to local variables inside your function, then write the final values back out again at the end, as we saw in the previous solutions.
Bibliography
Monday, April 12, 2010
Finite State Machine Tool
The main objective of this tool is to minimized the bottleneck that supposes animation development within the creation of a video game. Therefore, this tool is a bridge between the model software and the final game.
* Import animations from XSI to XNA using a modified XSI runtime pipeline
* Control the character locomotion via Finite State Machines
* Maintain the character locomotion and general animations within game easily before using them in the final version.
* Create a Performance Test. Animate an entire crowd of random characters at the same time.
More specific information and demonstrations can be found on the Finite State Machine page.
* Import animations from XSI to XNA using a modified XSI runtime pipeline
* Control the character locomotion via Finite State Machines
* Maintain the character locomotion and general animations within game easily before using them in the final version.
* Create a Performance Test. Animate an entire crowd of random characters at the same time.
More specific information and demonstrations can be found on the Finite State Machine page.
Terrain Editor Tool
This is a high-quality terrain generation tool based on height and normal mapping. It also uses other advanced techniques like Phong lighting model and altitude based texture sampling in order to achieve a realistic product.
More specific information about this tool and a demonstration of it can be found in: Terrain Editor page
More specific information about this tool and a demonstration of it can be found in: Terrain Editor page
Subscribe to:
Posts (Atom)