Continuous Collision DetectionInterference vs. CollisionWhy Perform Continuous CD?Slide 4Slide 5Slide 6Types of motionSwept-volumesSwept VolumesSlide 10Swept volumes in 3D spaceSlide 12Slide 13Approximate CCDConvex Hulls of Swept VolumesSlide 16Slide 17Slide 18Four-Dimensional ExtrusionSlide 20Exact CCDExact CCD: How may two polygons collide?Slide 23Vertex/FaceEdge/EdgeEdge/Edge and Vertex/FaceCo-Planarity TestSolving the EquationsInterval ArithmeticInterval Arithmetic OperationsInterval Arithmetic - exampleInterval arithmeticInterval Arithmetic – solvingBounding SpheresAxis-Aligned Bounding BoxesOriented Bounding BoxesSlide 37Slide 38OBB TestOBB Test – Example in 2DContinuous OBB TestApplication - ClothClothSlide 44Cloth CCDOur approachOur ApproachOther Issues in CCDSlide 49The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Continuous Collision DetectionDavid KnottCOMP 259 class presentationThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Interference vs. Collision•Most algorithms that we think of as collision detection are actually Interference Detection♦Interference Detection: Static setting♦Collision Detection: Dynamic setting•Most collision detection algorithms consist of repeated application of interference detectionThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Why Perform Continuous CD?•The exact time and location of first contact may need to be found.The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Why Perform Continuous CD?•Sampling at discrete intervals may miss a collision entirely.The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Why Perform Continuous CD?•Sampling at discrete intervals may give the wrong collision!The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Why Perform Continuous CD?•Most animation systems use backtracking methods♦Try to find point of first contact by binary search.♦Subject to all problems from previous slides♦Especially poor for non-solid objects (eg. cloth)The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Types of motion•Almost all CCD algorithms assume linear motion over a single time step•Non-linear motion makes CCD computation much more expensive♦True for both approximate and exact methodsThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Swept-volumes•The motion of a primitive through space “sweeps out” a volume over a time interval♦Similar to extrusion with an added rotational component.The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Swept Volumes•Swept-Volumes of moving objects may be compared against each other•This is a binary test for collision♦Does not reveal when or where collision occursThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Swept Volumes•Swept volumes are a sufficient but not necessary condition for determining if objects are collision-free♦Swept volumes may overlap, even when the objects have not collided♦Subdivision is needed♦Or consider relative motionThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Swept volumes in 3D space•1D - line•2D – prism•3D♦becomes very complicated very quicklyaba'b'aa'The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Swept Volumes•A object in n dimensions sweeps out a volume in n+1 dimensions•These volumes are very expensive to compute.♦Even harder with arbitrary rotations.The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Swept VolumesSource: “Fast Swept Volume Approximation…” Y. Kim – ACM Solid Modelling 2003The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Approximate CCD•Rough (conservative) CCD tests can be performed via bounding volumes of the swept volumes•Hierarchies of bounding volumes may be constructedThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Convex Hulls of Swept Volumes“A Safe Swept-Volume Approach to Collision Detection”A. Foisy & V. HaywardInt. Symp. on Robotics Research 1994The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Convex Hulls of Swept Volumes•The AABB of a moving vertex•Can find the convex hull of the AABBs of all verticesThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Convex Hulls of Swept Volumes•The convex hull of vertex AABBs is also a convex approximation to the swept volume of the moving object•Can consider hierarchies of theseBut NOT the convex hull of the AABBs.The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Convex Hulls of Swept Volumes•Can compute bounding boxes of the motion of individual vertices♦From this, a convex approximation of the object’s swept volume is straightforward•If bounding volumes test positive, then individual polygon primitives must be tested♦Similar to discrete bounding volumesThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Four-Dimensional Extrusion•Extrude an object from N-dimensional space into N+1 dimensional space♦eg. 2D object extruded through time to form 3D object•“Collision Detection by 4D Intersection Testing…”♦J. Cameron – IEEE Trans. Robotics & Automation - 1990The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Four-Dimensional Extrusion•Not the same as swept volumes♦Swept volumes compute sweep of the boundary of the surface♦4D extrusion computes sweep of volume♦Overlap of extruded volumes is a necessary and sufficient condition for collision.•Conceptually nice•Implementation is exceedingly difficultThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Exact CCD•Swept volumes and bounding volumes will only report potential collisions.•Still need to determine the exact time and point of collision.•The types of objects that are being tested are usually polygonal♦How can the exact tests be done for polyhedra?The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Exact CCD: How may two polygons collide?•Vertex/Face Collision•Edge/Edge CollisionThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Exact CCD•“Collision Detection for Moving Polyhedra”♦J.Canny – IEEE Patt. Anal. and Mach. Int. 1986•CCD for both the edge/edge and vertex/face tests reduces to a system of constraints and solving a polynomial of degree 5The UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Vertex/Face•Collision when vertex/face distance is zero•Check for point/plane coplanarity•Then check for vertex/face intersection validity)()()()()( ttttt dccbN 0)()()(  ttt Nba)(ta)(tb)(tc)(td)()( tt baThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Edge/Edge•Collision when edge/edge distance is zero•Check for line/line coplanarity•Then check for edge/edge intersection validity0)()()(  ttt Nca)()()()()( ttttt dcbaN