


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 
















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




Use of coherence, locality, hierarchy 

and incremental computations 




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 

SimulationBased Design  interference
detection 





Efficiency 

realtime (interactive) for pairwise &
nbody 



Accuracy 

exact, not approximation 



Practical 

should work on “realworld” models 

relatively easy to implement 

general yet robust 





Model Representations 

polyhedra (convex vs. nonconvex vs. soups) 

CSG, Implicit Rep, Parametric Rep 



Type of Queries 

collision detection 

distance computation 

penetration depth 

estimated time to collision 



Simulation Environments 

pairwise vs. nbody 

static vs. dynamic 

rigid vs. deformable 






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



NBody: O(m^{2}) 



Pairwise:
O(n^{2}) 





MultiBody Environments 

Sweep & Prune 

Scheduling Scheme 

Pairwise Proximity Queries 

Convex Objects (GJK, Lin&Canny, SWIFT) 

General Models (OBBTree, SSV) 

Graphics Hardware Acceleration 

Data Management 





Compute the axisaligned 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 






Coherence (greedy walk) 



Convexity properties (geometric properties of
convex polytopes) 



Nearly constant time, if the motion is
relatively “small” 




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. 





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. 








a_{max}: an upper bound on relative
acceleration between any two points on any pair of objects. 

a_{lin}: 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 

a_{max}
=  a_{lin} + a x r + w x w x r  

v_{i}
=  v_{lin }+ w x r  




Given the bound on maximum relative acceleration
(including rotational and linear) a_{max} and initial relative
velocity (including rotational & linear) v_{i} with separation d
between two objects, 



t_{c} = [ (v_{i}^{2} + 2
a_{max }d ) ^{1/2}  v_{i} ]_{ }/_{ }a_{max} 




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 



Recompute timetocollision for the affected
feature pairs and reinsert them into the queue 





Literature Survey 

MultiBody Environments 

Sweep & Prune 

Scheduling Scheme 

Pairwise Proximity Queries 

Convex Objects (GJK, Lin&Canny, SWIFT) 

General Models (OBBTree, SSV) 

Graphics Hardware Acceleration 

Data Management 


















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


















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




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 







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. 





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 sublinear time performance even
without coherence 




Improved closest featuretracking based on
Voronoi regions 

Use of normal tables to jump start and avoid
local minima problem 

Take advantages of levelofdetails
(multiresolution) representations 




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 






Convex polytopes 



Penetration detection 



Nonconvex models 






Routines: 

Nbody 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 




Architectural Walkthrough 



Dynamic Simulator (Impulse) 



MultiBody Simulators 










Convex polytopes 



Penetration detection 



Nonconvex models 





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: 







OBBTree: Tree of Oriented Bounding Boxes (OBBs) 



SSV:
Tree of Swept Sphere Volumes 






Building an OBBTree 

Tree Traversal 

OBB Overlap Test 

Performance 










OBB Fitting algorithm: 



Covariancebased 

Use of convex hull 

Uniform sampling distributions 

O(n log n) fitting time for single BV 

O(n log^{2} n) fitting time for entire tree 






Building an OBBTree 

Tree Traversal 

OBB Overlap Test 

Performance 













Building an OBBTree 

Tree Traversal 

OBB Overlap Test 

Performance 






















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




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 






Given two generic polytopes, each with E edges
and F faces, number of candidate axes to test is: 

2F + E^{2} 

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. 





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 








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 microcoding 







[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 






Building an OBBTree 

Tree Traversal 

OBB Overlap Test 

Performance 



















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
















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






















Interactive Interference Detection: A Torpedo (4780 polygons) on Pivot
Structure (44921 polygons) 





Available at: http://www.cs.unc.edu/~geom/OBB 



Part of VCOLLIDE: 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 




Virtual Protptyping & VEs: Division, MSC,
Prosolvia, AmandaSoft, Ford, LockheedMartin 



Computer Animation: Jack/Transom Tech. 



Dynamic Simulation: Mechanical Dynamics Inc.
(MDI/ADAMS) 



Interactive Gaming: Intel, OZ.com, Blaxxun etc. 






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 




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. 







Use a simpler BV when it prunes search equally
well  benefit from lower cost of BV overlap tests 



Overlap test (based on LinCanny & 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 




Library written in C++ 



Good for any proximity query 



520x speedup in distance computation over
prior methods 



Available at http://www.cs.unc.edu/~geom/SSV/ 




Released in July’99 



More than 250 active users 



Strong interest from Sony 



Optimized for PS2 applications: only 12
routines need optimization 






Compute a discrete Voronoi diagram by rendering
a three dimensional distance mesh for each Voronoi site. 

The polygonal mesh is a boundederror
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 scanconversion and the
Zbuffer depth comparison. 





To visualize Voronoi diagram for points in 2D… 






Avoid perpixel distance evaluation
Pointsample the distance function
Reconstruct by rendering polygonal mesh 











MultiBody Environments 

Sweep & Prune 

Scheduling Scheme 

Pairwise Proximity Queries 

Convex Objects (GJK, Lin&Canny, SWIFT) 

General Models (OBBTree, SSV) 

Graphics Hardware Acceleration 

Data Management 





Reduce frequency of disk accessing 



Runtime ordering & traversal 



Localize region of contacts 



Allow modification on the fly 



Prefetch geometry 




A simple environment consisting of polygons 




Each object is bounded by a AABB. 






Identify cacheable components 

Object decomposition 

Find highvalence nodes 

Multilevel 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 




Types of Bounding Volumes (e.g. spheres, AABBS,
OBBs, etc.) 





Onthefly Hierarchy Construction & Lazy
Evaluation 






Written in C++ & OpenGL 

Built on top of PQP (UNCCH) 

Use of METIS (University of Minnesota) 

Realtime interaction with CAD models 



[Eurographics’99] 





7
Collision Detection & Proximity Systems 

More than 4500 downloads 

More
than 40 commercial licenses 

The Collide Inc. handles licensing 

Useful feedback from our users 






Fast penetration depth computation 

Design of hybrid hierarchies 

Collision detection for deformable models 



Better Integration with path planning, haptic
rendering and dynamic simulation 



Realtime performance for handlilng general
models in video games 






Army Research Office 

Honda 

Intel 

National Science Foundation 

Office of Naval Research 

Sloan Foundation 




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 




Intel MGL Research Group 



Sony PS2 R&D Group 



