Notes

Outline

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(m2) Pairwise:  O(n2)

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

System Architecture

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

Dimension Reduction

Dimension Reduction

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 amax: an upper bound on relative acceleration between any two points on any pair of objects. alin: relative absolute linear a: relative rotational accelerations w: relative rotational velocities r: vector difference btw CoM of two bodies d: initial separation for two given objects amax  = | alin + a x r + w x w x r | vi  = | vlin + w x  r |

Bounding Time to Collision Given the bound on maximum relative acceleration (including rotational and linear) amax and initial relative velocity (including rotational & linear) vi with separation d between two objects, tc = [ (vi2 + 2 amax d ) 1/2 - vi ] / amax

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 Literature Survey 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

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

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

Architectural Walkthrough

System Demonstration Video

Motivation

Motivation

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:

BVH-Based Collision Detection

Hierarchies Based on Higher Order Bounding Volumes OBBTree: Tree of Oriented Bounding       Boxes (OBBs) SSV:  Tree of Swept Sphere Volumes

OBBTREES:  Organization Building an OBBTree Tree Traversal OBB Overlap Test Performance

Building an OBB Tree

Building an OBB Tree

Building an OBB Tree

Building an OBB Tree

Building an OBB Tree

Building an OBB Tree

Building an OBB Tree:  Summary OBB Fitting algorithm: Covariance-based Use of convex hull Uniform sampling distributions O(n log n) fitting time for single BV O(n log2  n) fitting time for entire tree

OBBTREES:  Organization Building an OBBTree Tree Traversal OBB Overlap Test Performance

Tree Traversal

Tree Traversal

Tree Traversal

Tree Traversal

Tree Traversal

Tree Traversal

Tree Traversal

OBBTREES:  Organization Building an OBBTree Tree Traversal OBB Overlap Test Performance

Separating Axis Theorem L is a separating axis for OBBs A & B, since A & B become disjoint intervals under projection onto L

Separating Axis Theorem Two polytopes A and B are disjoint iff there exists a separating axis which is: perpendicular to a face from either or perpedicular to an edge from each

Implications of Theorem Given two generic polytopes, each with E edges and F faces, number of candidate axes to test is:                                    2F + E2 OBBs have only E = 3 distinct edge directions, and only F = 3 distinct face normals. OBBs need at most 15 axis tests. Because edge directions and normals each form orthogonal frames, the axis tests are rather simple.

OBB Overlap Test

OBB Overlap Test Project boxes onto axis.  If intervals don’t overlap, it is a separating axis. A separating axis exists if and only if boxes are disjoint. 2D OBBs: 4 axes to test 3D OBBs: 15 axes to test

OBB Overlap Test

OBB Overlap Test Strengths of this overlap test: 80 to 234 arithmetic operations per box overlap test No special cases for parallel/coincident faces, edges, or vertices No special cases for degenerate boxes No conditioning problems Good candidate for micro-coding

OBB Overlap Test:  SIMD Implementation [Jointly with Intel] Decompose into 5 sets of axis tests Each set implemented using Katmai SIMD instruction sets About 2.5 times speedup in practice

OBBTREES:  Organization Building an OBBTree Tree Traversal OBB Overlap Test Performance

AABB’s vs. OBB’s Approximation of a Torus

Dynamic Simulation Interactive Collision Detection on 2 complex Pipelines: 140K polygons each; 4.2ms on SGI RE/90M Hz

Engineering Animation Interference Detection of Engine Model: Fixed part: 84,454 triangles; Moving parts: 256,606 triangles

Simulation-Based Design Interactive Interference Detection:  A Torpedo (4780 polygons) on Pivot Structure (44921 polygons)

System Demonstration Video

Implementation: RAPID Available at: http://www.cs.unc.edu/~geom/OBB Part of V-COLLIDE: http://www.cs.unc.edu/~geom/V_COLLIDE More than 3000 users have ftp’ed the code Used for virtual prototyping, dynamic simulation, robotics and computer animation

Technology Transfer: RAPID Virtual Protptyping & VEs: Division, MSC, Prosolvia, AmandaSoft, Ford, Lockheed-Martin Computer Animation: Jack/Transom Tech. Dynamic Simulation: Mechanical Dynamics Inc. (MDI/ADAMS) Interactive Gaming:  Intel, OZ.com, Blaxxun etc.

Swept Sphere Volumes     PSS                LSS                   RSS

Swept Sphere Volumes (S-topes)

SSV Fitting Use OBB’s 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 BVH’s 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 BV’s in a BV family is unified Complications deciding which BV to use either dynamically or statically

PQP:  Implementation Library written in C++ Good for any proximity query 5-20x speed-up in distance computation over prior methods Available at http://www.cs.unc.edu/~geom/SSV/

PQP:  Technology Transfer Released in July’99 More than 250 active users Strong interest from Sony Optimized for PS2 applications: only 1-2 routines need optimization

Accelerated Computation of Generalized Voronoi Diagram Compute a discrete Voronoi diagram by rendering a three dimensional distance mesh for each Voronoi site. The polygonal mesh is a bounded-error approximation of a distance functions btw a site and a 2D planar grid of points. For each sample point, compute the closest site and the distance to that site using polygon scan-conversion and the Z-buffer depth comparison.

Brute-force Algorithm

Cone Drawing To visualize Voronoi diagram for points in 2D…

Graphics Hardware Acceleration

The Distance Function

Approximating the Distance Function Avoid per-pixel distance evaluation Point-sample the distance function Reconstruct by rendering polygonal mesh

Distance Functions for 3D Primitives

3D Voronoi Diagrams

Real-time Motion Planning : Static Scene

Real-time Motion Planning : Dynamic Scene

Voronoi Roadmap  for Dynamic Environments

Dynamic Mosaics

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

System Architecture

Localized Sub-graphs Reduce frequency of disk accessing Runtime ordering & traversal Localize region of contacts Allow modification on the fly Prefetch geometry

2D Objects A simple environment consisting of polygons

Object Bounding Boxes Each object is bounded by a AABB.

Slide 97

Slide 98

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

Algorithmic Choices Types of Bounding Volumes (e.g. spheres, AABBS, OBBs, etc.) On-the-fly Hierarchy Construction & Lazy Evaluation

IMMPACT:  Implementation Written in C++ & OpenGL Built on top of PQP (UNC-CH) Use of METIS (University of Minnesota) Real-time interaction with CAD models [Eurographics’99]

IMMPACT:  Demonstration

Technology Transfer & Feedback  7 Collision Detection & Proximity Systems More than 4500 downloads  More than 40 commercial licenses The Collide Inc. handles licensing Useful feedback from our users

Ongoing & Future Work Fast penetration depth computation Design of hybrid hierarchies Collision detection for deformable models Better Integration with path planning, haptic rendering and dynamic simulation Real-time performance for handlilng general models in video games

Acknowledgements Army Research Office Honda Intel National Science Foundation Office of Naval Research Sloan Foundation

Collaborators Dinesh Manocha John Canny (Berkeley) Jonathan Cohen (Johns Hopkins) Tim Culver Stephen Ehmann Stefan Gottschalk (NVidia) Kenneth Hoff III John Keyser Shankar Krishnan (AT & T Research Lab) Eric Larsen (Sony R&D America) Brian Mirtich (MERL) Amol Pattekar (Yahoo) Krish Ponamgi Andy Wilson

Industrial Collaborators Intel MGL Research Group Sony PS2 R&D Group

"The End" The End