fast-proximity-queries-for-large-game-environments.md

Fast Proximity Queries for Large Game Environments

Ming C. Lin

Department of Computer Science University of North Carolina

http://www.cs.unc.edu/~lin http://www.cs.unc.edu/~geom/collide.html

Proximity Queries

• A procedure to compute the geometric contact (and distance) between objects.

Theme

• Use of coherence, locality, hierarchy and incremental computations

Applications other than Games

• Rapid Prototyping -- tolerance verification
• Dynamic simulation -- contact force calculation
• Computer Animation -- motion control
• Motion Planning -- distance computation
• Virtual Environments -- interactive manipulation
• Haptic Rendering -- restoring force computation
• Simulation-Based Design -- interference detection

Goals

• Efficiency

  • real-time (interactive) for pairwise & n-body

• Accuracy

  • exact, not approximation

• Practical

  • should work on "real-world" models
  • relatively easy to implement
  • general yet robust

Problem Domain Specifications

• Model Representations

  • polyhedra (convex vs. non-convex vs. soups)
  • CSG, Implicit Rep, Parametric Rep

• Type of Queries

  • collision detection
  • distance computation
  • penetration depth
  • estimated time to collision

• Simulation Environments

  • pairwise vs. n-body
  • static vs. dynamic
  • rigid vs. deformable

Problem Complexity

Given an environment consisted of m objects and each has no more than n polygons, the problem has the following complexity using brute-force methods:

• N-Body: O(m^2)
• Pairwise: O(n^2)

Organization

• Multi-Body Environments
  • Sweep & Prune
  • Scheduling Scheme
• Pairwise Proximity Queries
  • Convex Objects (GJK, Lin&Canny, SWIFT)
  • General Models (OBBTree, SSV)
  • Graphics Hardware Acceleration
• Data Management

Sweep and Prune

• Compute the axis-aligned bounding box (fixed vs. dynamic) for each object
• Dimension Reduction by projecting boxes onto each x, y, and z axis
• Sort the endpoints and find overlapping intervals
• Possible collision -- only if projected intervals overlap in all 3 dimensions

Dimension Reduction

https://i.imgur.com/ui0jEjM.png https://i.imgur.com/BJNwy0l.png

Updating Bounding Boxes

• Coherence (greedy walk)
• Convexity properties (geometric properties of convex polytopes)
• Nearly constant time, if the motion is relatively "small"

Use of Sorting Methods

• Initial sort -- quick sort runs in O(m log m) just as in any ordinary situation
• Updating -- insertion sort runs in O(m) due to coherence. We sort an almost sorted list from last stimulation step. In fact, we look for "swap" of positions in all 3 dimension.

Scheduling Scheme

• When the velocity and acceleration of all objects are known, use the scheduling scheme to prioritize "critical events" to be processed (using heap)
  • Each object pair is tagged with the estimated time to next collision.
  • All object pairs are sorted accordingly.
  • The heap is updated when a collision occurs.

Deriving Bounds

https://i.imgur.com/CxdK20r.png

Bounding Time to Collision

https://i.imgur.com/UzT7iMU.png

Basic Steps

• Maintain a queue of all object pairs sorted by approximated time to collision
• At each step, only update the closest feature pair at the head of priority queue (as a heap)
• If collision occurs, handle collision
• Re-compute time-to-collision for the affected feature pairs and reinsert them into the queue

Organization

• Multi-Body Environments
  • Sweep & Prune
  • Scheduling Scheme
• Pairwise Proximity Queries
  • Convex Objects (GJK, Lin&Canny, SWIFT)
  • General Models (OBBTree, SSV)
  • Graphics Hardware Acceleration
• Data Management

GJK Method for Convex Polytopes

• Linear time performance, based on Minkowski differences and convex optimization methods

Tracking Closest Features

Lin & Canny [1991]: expected O(1) time performance, independent of complexity

Voronoi Regions

• Given a collection of geometric primitives, it is a subdivision of space into cells such that all points in a cell are closer to one primitive than to any other

Closest Feature Tracking Using Voronoi Regions

https://i.imgur.com/GL2nzVB.png

Basic Algorithm

• Given one feature from each polyhedron, find the nearest points of the two features.
• If each nearest point is in the Voronoi region of the other feature, closest features have been found.
• Else, walk to one or both of their neighbors or some other feature.

Running Time Analysis

• Distance strictly decreases with each change of feature pair, and no pair of features can be selected twice.
• Convergence to closest pair typically much better for dynamic environments:
  • O(1) achievable in simulations with coherence
  • Closer to sub-linear time performance even without coherence

Accelerated Proximity Queries based on Multi-Level Marching

• Improved closest feature-tracking based on Voronoi regions
• Use of normal tables to jump start and avoid local minima problem
• Take advantages of level-of-details (multi-resolution) representations

Implementation: SWIFT

• Progressive Refinement Framework
  • Faster (2x to 10x) than any public domain packages for convex objects
  • Insensitive to level of motion coherence
  • Will be available at: http://www.cs.unc.edu/~geom/SWIFT

Exact Collision Detection

• Convex polytopes
• Penetration detection
• Non-convex models

Penetration Detection

https://i.imgur.com/Iv17XZe.png

I-Collide Collision Detection System

• Routines:
  • N-body overlap tests (sweep and prune)
  • Distance calculation btwn convex polytopes
• Public domain system
• 2500+ researchers have FTP'ed the code
• A mailing list of many hundreds of users

I-Collide System Demonstrations

• Architectural Walkthrough
• Dynamic Simulator (Impulse)
• Multi-Body Simulators

Exact Collision Detection

• Convex polytopes
• Penetration detection
• Non-convex models

BVH-Based Collision Detection

• Model Hierarchy
  • each node has a simple volume that bounds a set of triangles
  • children contain volumes that each bound a different portion of the parent's triangles
  • the leaves of the hierarchy usually contain individual triangles
• A binary bounding volume hierarchy: https://i.imgur.com/RTUs2eE.png

Hierarchies Based on Higher Order Bounding Volumes

• OBBTree: Tree of Oriented Bounding-Boxes (OBBs)
• SSV: Tree of Swept Sphere Volumes

SSV Fitting

• Use OBBs code based upon Principle Component Analysis
• For PSS, use the largest dimension as the radius
• For LSS, use the two largest dimensions as the length and radius
• For RSS, use all three dimensions

Overlap Test

• One routine that can perform overlap tests between all possible combination of CORE primitives of SSV(s).
• The routine is a specialized test based on Voronoi regions and OBB overlap test.
• It is faster than GJK.

Hybrid BVHs based on SSV

• Use a simpler BV when it prunes search equally well - benefit from lower cost of BV overlap tests
• Overlap test (based on Lin-Canny & OBB overlap test) between all pairs of BVs in a BV family is unified
• Complications
  • deciding which BV to use either dynamically or statically

Localized Sub-graphs

• Reduce frequency of disk accessing
• Runtime ordering & traversal
• Localize region of contacts
• Allow modification on the fly
• Prefetch geometry

Object Bounding Boxes

https://i.imgur.com/X7NoPaR.png

Object Nodes

https://i.imgur.com/qhP0nvM.png

Overlap Graph

https://i.imgur.com/ketq18c.png

Computing Connected Components

• Identify cacheable components
• Object decomposition
• Find high-valence nodes
• Multi-level graph partitioning
• Repeat on the resulting cut graph till decomposing the overlap graph into localized subgraphs, such that the weight of each subgraph < memory cache size