ReferencesGeometric Proximity QueriesCollision DetectionClasses of Objects & ProblemsSome Possible ApproachesVoronoi DiagramsGeneralized Voronoi DiagramsVoronoi RegionsVoronoi MarchingSimple 2D ExampleBasic Idea for Voronoi MarchingLinear ProgrammingLP for Collision DetectionMinkowski Sums/DifferencesSome Minkowski DifferencesMinkowski Difference & TranslationPropertiesPracticalityGJK for Computing Distance between Convex PolyhedraAn Example of GJKRunning Time of GJKMore on GJKLarge, Dynamic EnvironmentsScheduling SchemeCollide System ArchitectureSweep and PruneSweep & PruneUpdating Bounding BoxesUse of Sorting MethodsImplementation IssuesUNC Chapel HillM. C. LinReferencesCollision Detection between Geometric Models: A Survey, by M. Lin and S. Gottschalk, Proc. of IMA Conference on Mathematics of Surfaces 1998. 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. Lin's 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:193--203, 1988.UNC Chapel HillM. C. LinGeometric 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 penetrationUNC Chapel HillM. C. LinCollision 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 intersectionsImagine larger input size: N = 1000+ ……UNC Chapel HillM. C. LinClasses 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. DynamicAnd so on… This may include other geometric representation schemata, etc.UNC Chapel HillM. C. LinSome Possible Approaches•Geometric methods•Algebraic Techniques•Hierarchical Bounding Volumes•Spatial Partitioning•Others (e.g. optimization)UNC Chapel HillM. C. LinVoronoi 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 HillM. C. LinGeneralized 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 HillM. C. LinVoronoi 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 HillM. C. LinVoronoi MarchingBasic 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 complexityUNC Chapel HillM. C. LinSimple 2D ExampleABP1P2Objects 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.UNC Chapel HillM. C. LinBasic Idea for Voronoi MarchingUNC Chapel HillM. C. LinLinear ProgrammingIn 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 <x, c>Subject to <a, x>  Ka, for all a in A . where <*, *> is standard inner product in Rd.UNC Chapel HillM. C. LinLP for Collision DetectionGiven two finite sets A, B in Rd For each a in A and b in B, Find x in Rd which minimize whateverSubject to <a, x> > 0, for all a in AAnd <b, x> < 0, for all b in Bwhere d = 2 (or 3).UNC Chapel HillM. C. LinMinkowski Sums/DifferencesMinkowski Sum (A, B) = { a + b | a  A, b  B } Minkowski Diff (A, B) = { a - b | a  A, b  B } A and B collide iff Minkowski Difference(A,B) contains the point 0.UNC Chapel HillM. C. LinSome Minkowski DifferencesA BABUNC Chapel HillM. C. LinMinkowski Difference & TranslationMinkowski-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. LinPropertiesDistance–distance(A,B) = min a  A, b B || a - b ||2–distance(A,B) = min c  Minkowski-Diff(A,B) || c ||2–if A and B disjoint, c is a point on boundary of Minkowski differencePenetration Depth –pd(A,B) = min{ || t ||2 | A  Translated(B,t) =  }–pd(A,B) = mint Minkowski-Diff(A,B) || t ||2 –if A and B intersect, t is a point on boundary of Minkowski differenceUNC Chapel HillM. C. LinPracticalityExpensive 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 knownUNC Chapel HillM. C. LinGJK for Computing Distance between Convex