3D Polyhedral Morphing
Collision and Proximity Queries
Dinesh Manocha
*
Geometric Proximity Queries
Given two object, how would you check:
If they intersect with each other while moving?
If they do not interpenetrate each other, how far are they apart?
If they overlap, how much is the amount of penetration
*
Proximity Queries
Geometric reasoning of spatial relationships among objects (in a dynamic environment)
d
Closest Points & Separation Distance
Penetration Depth
Collision Detection
Contact Points & Normals
d
NUS CS 5247 David Hsu
*
Problem
Input: two objects A and B
Output:
Distance computation: compute the distance (in the workspace) between A and B
Collision detection: determine whether A and B collide or not
OR
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
Collision detection vs. distance computation
The distance between two objects (in the workspace) is the distance between the two closest points on the respective objects.
Collision if and only if distance = 0
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
Collision detection vs. distance computation
The distance between two objects (in the workspace) is the distance between the two closest points on the respective objects.
Collision if and only if distance = 0
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
How will you compute the distance?
What is the distance between two convex polygons?
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
How will you compute the distance?
What is the distance between two sets of points?
NUS CS 5247 David Hsu
Collision Detection
Update configurations w/ TXF matrices
Check for edge-edge intersection in 2D
(Check for edge-face intersection in 3D)
Check every point of A inside of B &
every point of B inside of A
Check for pair-wise edge-edge intersections
Imagine larger input size: N = 1000+ ……
*
Classes of Objects & Problems
2D vs. 3D
Convex vs. Non-Convex
Polygonal vs. Non-Polygonal
Open surfaces vs. Closed volumes
Geometric vs. Volumetric
Rigid vs. Non-rigid (deformable/flexible)
Pairwise vs. Multiple (N-Body)
CSG vs. B-Rep
Static vs. Dynamic
And so on… This may include other geometric representation schemata, etc.
*
Some Possible Approaches
Geometric methods
Algebraic Techniques
Hierarchical Bounding Volumes
Spatial Partitioning
Others (e.g. optimization)
*
Essential Computational Geometry
Extreme Points & Convex Hulls
Providing a bounding volume
Convex Decomposition
For CD btw non-convex polyhedra
Voronoi Diagram
For tracking closest points
Linear Programming
Check if a pt lies w/in a convex polytope
Minkowski Sum
Computing separation & penetration measures
*
Extreme Point
Let S be a set of n points in R2. A point p = (px, py) in S is an extreme point for S iff there exists a, b in R such that for all q = (qx, qy) in S with q ≠ p we have
a px+ b py > a qx+ b qy
Geometric interpretation: There is a line with the normal vector (a,b) through p so that all other points of S lies strictly on one side of this line. Intuitively, p is the most extreme point of S in the direction of the vector v = (a,b).
*
Convex Hull
The convex hull of a set S is the intersection of all convex sets that contains S.
The convex hull of S is the smallest convex polygon that contains S and that the extreme points of S are just the corners of that polygon.
Solving the convex hull problem implicitly solves the extreme point problem.
*
Constructing Convex Hulls
Graham’s Scan
Marriage before Conquest
(similar to Divide-and-Conquer)
Gift-Wrapping
Incremental
And, many others ……
Lower bound: O(n log H), where n is the input size (No. of points in the given set) and H is the No. of the extreme points.
*
Convex Decomposition
The process to divide up a non-convex polyhedron into pieces of convex polyhedral
Optimal convex decomposition of general non-convex polyhedra can be NP-hard.
To partition a non-degenerate simple polyhedron takes O((n + r2) log r) time, where n is the number of vertices and r is the number of reflex edges of the original non-convex object.
In general, a non-convex polyhedron of n vertices can be partitioned into O(n2) convex pieces.
*
Voronoi Diagrams
Given a set S of n points in R2 , for each point pi in S, there is the set of points (x, y) in the plane that are closer to pi than any other point in S, called Voronoi polygons. The collection of n Voronoi polygons given the n points in the set S is the “Voronoi diagram”, Vor(S), of the point set S.
Intuition: To partition the plane into regions, each of these is the set of points that are closer to a point pi in S than any other. The partition is based on the set of closest points, e.g. bisectors that have 2 or 3 closest points.
*
Generalized Voronoi Diagrams
The extension of the Voronoi diagram to higher dimensional features (such as edges and facets, instead of points); i.e. the set of points closest to a feature, e.g. that of a polyhedron.
FACTS:
In general, the generalized Voronoi diagram has quadratic surface boundaries in it.
If the polyhedron is convex, then its generalized Voronoi diagram has planar boundaries.
*
Voronoi Regions
A Voronoi region associated with a feature is a set of points that are closer to that feature than any other.
FACTS:
The Voronoi regions form a partition of space outside of the polyhedron according to the closest feature.
The collection of Voronoi regions of each polyhedron is the generalized Voronoi diagram of the polyhedron.
The generalized Voronoi diagram of a convex polyhedron has linear size and consists of polyhedral regions. And, all Voronoi regions are convex.
*
Simple 2D Example
Objects A & B and their Voronoi regions: P1 and P2 are the pair of closest points between A and B. Note P1 and P2 lie within the Voronoi regions of each other.
*
NUS CS 5247 David Hsu
*
Voronoi regions of points and edges
Voronoi region of a point
Voronoi region of an edge
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
Voronoi Based Closest Features
Theorem: Let X and Y be a pair of features from disjoint convex polygons and let x X and y Y be the closest pair of points between X and Y. If x vor(Y) and y vor(X) , then x and y are a globally closest pair of points between the polygons.
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
Critical condition: vertex-vertex
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
vertex-edge
NUS CS 5247 David Hsu
NUS CS 5247 David Hsu
*
Sketch of the algorithm
1: Start with a candidate feature pair (X,Y).
2: if (X,Y) satisfies the closest pair condition
3: then
return (X,Y) as the closest pair.
4: else
Update either X or Y to its neighboring
feature. Go to (2).
NUS CS 5247 David Hsu
Voronoi Marching in 3D
*
Linear Programming
In general, a d-dimensional linear program-ming (or linear optimization) problem may be posed as follows:
Given a finite set A in Rd
For each a in A, a constant Ka in R, c in Rd
Find x in Rd which minimize
Subject to
where <*, *> is standard inner product in Rd.
*
LP for Collision Detection
Given two finite sets A, B in Rd
For each a in A and b in B,
Find x in Rd which minimize whatever
Subject to
And
L is a separating axis iff:
*
Box centers project to interval midpoints, so
midpoint separation is length of vector T’s image.
OBB Overlap Test: Axis Test Details
*
836.unknown
OBB Overlap Test: Axis Test Details
Half-length of interval is sum of box axis images.
*
838.unknown
OBB Overlap Test
Typical axis test for 3-space.
Up to 15 tests required.
s = fabs(T2 * R11 – T1 * R21);
ha = a1 * Rf21 + a2 * Rf11;
hb = b0 * Rf02 + b2 * Rf00;
if (s > (ha + hb)) return 0;
*
OBB Overlap Test
Strengths of this overlap test:
89 to 252 arithmetic operations per box overlap test
Simple guard against arithmetic error
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 Tests: Comparison
Benchmarks performed on SGI Max Impact,
250 MHz MIPS R4400 CPU, MIPS R4000 FPU (1996)
=
*
Parallel Close Proximity
Q: How does the number of BV tests increase as the gap size decreases?
Two models are in parallel close proximity when every point on each model is a given fixed distance (e) from the other model.
*
In order to quantify the performance of the various BV types, we consider an easily parameterized configuration: parallel close proximity. When the models are concentric, every point on one model is a fixed distance (epsilon) from the other model, and vice-versa. This is our definition of transverse contact.
This means the two models are offset surfaces of one another, and the offset is the gap size (epsilon).
As epsilon decreases, we will have to descend the hierarchies more and more deeply in order to bound the models apart. How far will we have to go? That depends on the specific shape of the bounding volumes.
841.unknown
Parallel Close Proximity: Convergence
1
*
Consider two bounding volumes covering opposing parallel segments. We will call the distance between the segments one unit.
Parallel Close Proximity: Convergence
1
2
/
2
1
4
/
*
When the separation is cut in half, we have to BVs half as big, which means we have to use twice as many. On each successive halving of the gap, we double the number of BV required. At each successive level, each sphere covers half the length of segment as the level above, and each sphere sticks out half as far away from the segment. Because the length covered and the amount extended from the segment diminish proportionally, we say spheres have linear convergence.
1
Parallel Close Proximity: Convergence
*
For AABBs, the reasoning is the same. Consider the two line segments, and the AABBs which bound them. If the segments were themselves axis-aligned, then the AABBs would fit perfectly. Let us assume the segments are tilted some arbitrary amount. Then, let us define the closest distance they can get without the AABBs touching to be one unit.
Parallel Close Proximity: Convergence
1
2
/
2
1
4
/
*
Now, keeping the tilt angle the same, but cutting the gap size in half results in a doubling of the number of required AABBs. This is true regardless of the angle of the line. As with spheres, with each successive level of the hierarchy, the amount the AABB extends outward from the segment diminishes at the same rate as does the amount of segment covered, so AABBs have linear convergence.
1
Parallel Close Proximity: Convergence
*
OBBs are different. First of all, any straight segment of any tilt angle would be bounded perfectly by a well-fitted OBB, so we will assume we are working with parallel arcs of low curvature. Given the arcs of specific curvature, position them as closely as possible without letting the OBBs touch.
Note, the longer the radius of curvature relative to the size of the OBBs, the tighter the fit will be.
Parallel Close Proximity: Convergence
1
4
/
1
16
/
*
If the curvature is low, then will be able to reduce the gap by approximately a factor of four, and still bound the arcs apart by only doubling the number of OBBs. Each additional factor of four reduction in gap size doubles the number of OBBs.
One way of thinking about this is that the radius of curvature stays fixed, but since the OBBs are getting smaller, the radius curvature is increasing relative to the OBBs, and hence, the fit is getting progressively tighter.
The amount the OBB extends away from the arc is proportional to the SQUARE of the arc length covered.
Parallel Close Proximity: Convergence
1
4
/
1
4
/
1
4
/
*
Now, notice what quartering the gap does with each BV type. It quadruples the number of BVs required by spheres and AABBs, but it only doubles the number required by OBBs. This means that for every quartering of the gap, we descend additional two levels of the sphere and AABB trees, but only one additional level of the OBB tree.
Performance: Overlap Tests
k
O(n)
2k
O(n2)
OBBs
Spheres & AABBs
*
OBBs asymptotically outperform AABBs and spheres
Log-log plot
Gap Size (e)
Number of BV tests
Parallel Close Proximity: Experiment
*
We verify this in the plot of BV tests versus gap size. This log-log plot shows gap size for concentric spheres on the x-axis, and number of BV tests for that configuration — the experiment was repeated for each BV type. For extremely large gap sizes, on the right, we have a unit size sphere model inside a very large sphere model — and there is some minimum number of BV tests required to determine non contact. Then, as we reduce the gap size, we start seeing an increase in the number of BV tests needed — but the rate of increase of the AABB and sphere tests is greater than the rate of increase of the OBB tests. In fact, the slopes are different — the AABB and sphere slopes are approximately twice that of the OBB slope. On a log-log plot, only monomial functions are straight lines, and the slope is the degree of the monomial. This means the slope -2 of the AABBs and sphere indicates v = O(1/e^2) and the -2 slope for OBBs means v = O(1/e). So indeed, the former is the square of the latter.
Example: AABB’s vs. OBB’s
Approximation
of a Torus
*
Implementation: RAPID
Available at: http://www.cs.unc.edu/~geom/OBB
Part of V-COLLIDE: http://www.cs.unc.edu/~geom/V_COLLIDE
Thousands of users have ftp’ed the code
Used for virtual prototyping, dynamic simulation, robotics & computer animation
*
Hybrid Hierarchy of
Swept Sphere Volumes
PSS LSS RSS
[Larsen et al. 1999]
*
Swept Sphere Volumes (S-topes)
PSS LSS RSS
*
842.bin
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 SSVs
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/
*
References
Interactive Collision Detection, by P. M. Hubbard, Proc. of IEEE Symposium on Research Frontiers in Virtual Reality, 1993.
Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs, by Held, Klosowski and Mitchell, Proc. of Canadian Conf. on Computational Geometry 1995.
Efficient collision detection using bounding volume hierarchies of k-dops, by J. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, IEEE Trans. on Visualization and Computer Graphics, 4(1):21–37, 1998.
*
References
OBB-Tree: A Hierarchical Structure for Rapid Interference Detection, by S. Gottschalk, M. Lin and D. Manocha, Proc. of ACM Siggraph, 1996.
Rapid and Accurate Contact Determination between Spline Models using ShellTrees, by S. Krishnan, M. Gopi, M. Lin, D. Manocha and A. Pattekar, Proc. of Eurographics 1998.
Fast Proximity Queries with Swept Sphere Volumes, by Eric Larsen, Stefan Gottschalk, Ming C. Lin, Dinesh Manocha, Technical report TR99-018, UNC-CH, CS Dept, 1999. (Part of the paper in Proc. of IEEE ICRA’2000)
*
A
B
P1
P2
Test Method
Speed(us)
Separating Axis
6.26
GJK
66.30
LP
217.00
A
B
P1
P2
A
B
n
T
A
T
B
T
s
nTT
BA
s
n
B
r
B
nRnRnR
BBB
B
bbbr
332211
Test Method Speed(us)
Separating Axis 6.26
GJK 66.30
LP 217.00
10
-4
10
-3
10
-2
10
-1
10
0
10
1
234567234567234567234567234567
10
1
10
2
10
3
10
4
10
5
10
6
2
3
4
6
2
3
5
2
3
4
6
2
3
5
2
3
5
2
3