[SOLVED] CS scheme flex algorithm References

References
Additional lecture notes for 2/18/02.
I-COLLIDE: Interactive and Exact Collision Detection for Large-Scale Environments, by Cohen, Lin,
Manocha & Ponamgi, Proc. of ACM Symposium on Interactive 3D Graphics, 1995.
(More details in Chapter 3 of M. Lins Thesis)
A Fast Procedure for Computing the Distance between Objects in Three-Dimensional Space, by E. G. Gilbert, D. W. Johnson, and S. S. Keerthi, In IEEE Transaction of Robotics and Automation, Vol. RA-4:193203, 1988.
UNC Chapel Hill
M. C. Lin

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
UNC Chapel Hill
M. C. Lin

UNC Chapel Hill
M. C. Lin
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.
UNC Chapel Hill
M. C. Lin

UNC Chapel Hill
M. C. Lin
Some Possible Approaches
Geometric methods
Algebraic Techniques
Hierarchical Bounding Volumes Spatial Partitioning
Others (e.g. optimization)

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.
UNC Chapel Hill
M. C. Lin

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.
UNC Chapel Hill
M. C. Lin

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.
UNC Chapel Hill
M. C. Lin

Voronoi Marching
Basic Ideas:
Coherence: local geometry does not change much, when computations repetitively performed over successive small time intervals
Locality: to track the pair of closest features between 2 moving convex polygons(polyhedra) w/ Voronoi regions
Performance: expected constant running time, independent of the geometric complexity
UNC Chapel Hill
M. C. Lin

Simple 2D Example
P2 P1
B
A
UNC Chapel Hill
M. C. Lin
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.

Basic Idea for Voronoi Marching
UNC Chapel Hill
M. C. Lin

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 Ka, for all a in A .
where <*, *> is standard inner product in Rd.
UNC Chapel Hill
M. C. Lin

UNC Chapel Hill
M. C. Lin
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 > 0, for all a in A And < 0, for all b in Bwhere d = 2 (or 3). Minkowski Sums/Differences MinkowskiSum(A,B)={a+b |a A, b B } MinkowskiDiff(A,B)={a-b |aA, bB}A and B collide iff Minkowski Difference(A,B) contains the point 0. UNC Chapel HillM. C. LinSome Minkowski DifferencesABABUNC Chapel HillM. C. LinMinkowski Difference & TranslationMinkowski-Diff(Trans(A, t1), Trans(B, t2)) = Trans(Minkowski-Diff(A,B), t1 – t2) Trans(A, t1) and Trans(B, t2) intersect iff Minkowski-Diff(A,B) contains point (t2 – t1). UNC Chapel HillM. C. LinPropertiesDistance distance(A,B)=minaA, bB ||a-b||2distance(A,B) = min c Minkowski-Diff(A,B) || c ||2if A and B disjoint, c is a point on boundary ofMinkowski differencePenetration Depthpd(A,B) = min{ || t ||2 | A Translated(B,t) = }pd(A,B) = mint Minkowski-Diff(A,B) || t ||2if A and B intersect, t is a point on boundary ofMinkowski difference UNC Chapel HillM. C. LinPracticalityExpensive to compute boundary of Minkowski difference: For convex polyhedra, Minkowski difference may take O(n2) For general polyhedra, no known algorithm of complexity less than O(n6) is known UNC Chapel HillM. C. Lin GJK for Computing Distance between Convex PolyhedraGJK-DistanceToOrigin ( P ) // dimension is m1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.Initialize P0 with m+1 or fewer points. k =0while (TRUE) {if origin is within CH( Pk ), return 0 else {find x CH(Pk) closest to origin, and Sk Pk s.t. x CH(Sk) see if any point p-x in P more extremal in direction -xif no such point is found, return |x|else {Pk+1 = Sk {p-x}k=k+1 }} }UNC Chapel HillM. C. LinAn Example of GJKUNC Chapel HillM. C. LinRunning Time of GJKEach iteration of the while loop requires O(n) time.O(n) iterations possible. The authors claimed between 3 to 6 iterations on average for any problem size, making this expected linear.Trivial O(n) algorithms exist if we are given the boundary representation of a convex object, but GJK will work on point sets – computes CH lazily. UNC Chapel HillM. C. LinMore on GJKGivenA=CH(A) A={a1,a2,…,an }and B=CH(B) B={b1,b2,…,bm }Minkowski-Diff(A,B) = CH(P), P = {a – b | a A, b B} Can compute points of P on demand:p-x = a-x – bx where a-x is the point of A extremal in direction -x, and bx is the point of B extremal in direction x.The loop body would take O(n + m) time, producing the expected linear performance overall. UNC Chapel HillM. C. LinLarge, Dynamic EnvironmentsFor dynamic simulation where the velocity and acceleration of all objects are known at each step, use the scheduling scheme (implemented as heap) to prioritize critical events to be processed.Each object pair is tagged with the estimated time to next collision. Then, each pair of objects is processed accordingly. The heap is updated when a collision occurs. UNC Chapel HillM. C. LinScheduling Schemeamax: an upper bound on relative acceleration between any two points on any pair of objects.alin: relative absolute linear: relative rotational accelerations: relative rotational velocitiesr: vector difference btw CoM of two bodiesd: initial separation for two given objectsamax =|alin +xr+xxr|vi =|vlin+x r|Estimated Time to collision:tc = { (vi2 + 2 amax d)1/2 – vi } / amax UNC Chapel HillM. C. LinCollide System Architecture TransformOverlap Sweep & PruneSimulationExact Collision DetectionUNC Chapel HillM. C. LinParametersAnalysis & ResponseCollisionSweep and PruneCompute the axis-aligned bounding box (fixed vs. dynamic) for each objectDimension Reduction by projecting boxes onto each x, y, z- axisSort the endpoints and find overlapping intervalsPossible collision — only if projected intervals overlap in all 3 dimensions UNC Chapel HillM. C. LinSweep & PruneT=1e3e2 b3 e1b2 b1 b1 b2 e1e2 b3 e3T=2e2 e1b2 e3 b1 b2 e1e2 b3 e3b1 b3 UNC Chapel HillM. C. LinUpdating Bounding BoxesCoherence (greedy algorithm)Convexity properties (geometricproperties of convex polytopes)Nearly constant time, if the motion is relatively small UNC Chapel HillM. C. LinUse of Sorting MethodsInitial sort — quick sort runs in O(m log m) just as in any ordinary situationUpdating — 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. UNC Chapel HillM. C. LinImplementation Issues Collisionmatrix– basically adjacency matrixEnlarge bounding volumes with some tolerance thresholdQuick start polyhedral collision test — using bucket sort & look-up table UNC Chapel HillM. C. Lin