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