Why Perform Continuous CD?Slide 2Slide 3Slide 4Types of motionSwept-volumesSwept VolumesSlide 8Swept volumes in 3D spaceSlide 10Slide 11Approximate CCDConvex Hulls of Swept VolumesSlide 14Slide 15Slide 16Four-Dimensional ExtrusionSlide 18Exact CCDExact CCD: How may two polygons collide?Slide 21Vertex/FaceEdge/EdgeEdge/Edge and Vertex/FaceCo-Planarity TestSolving the EquationsInterval ArithmeticInterval Arithmetic OperationsInterval Arithmetic - exampleInterval arithmeticInterval Arithmetic – solvingBounding SpheresAxis-Aligned Bounding BoxesOriented Bounding BoxesSlide 35Slide 36OBB TestOBB Test – Example in 2DContinuous OBB TestApplication - ClothClothSlide 42Cloth CCDOur approachOur ApproachOther Issues in CCDSlide 47The 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 Volumes“Fast Swept Volume Approximation”Y. Kim et al., Proc. of ACM Solid Modeling 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 )(ta)(tb)(tc)(td)()( tt caThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Edge/Edge and Vertex/Face•Note that both types of tests are of the form:♦Find when four points are co-planar (continuous)♦Check for validity at time of co-planarity (in-plane distance computation)•When two primitives have more than one contact during a single time step – choose the first oneThe UNIVERSITY of NORTH CAROLINA at CHAPEL HILL Co-Planarity Test•For both edge/edge and vertex/face, the test has the form:    