Chapter 4.2 Collision Detection and ResolutionCollection DetectionCollision DetectionSlide 4Overlap TestingOverlap Testing: Useful ResultsOverlap Testing: Collision TimeOverlap Testing: LimitationsSlide 9Intersection TestingIntersection Testing: Swept GeometryIntersection Testing: Sphere-Sphere CollisionSlide 13Intersection Testing: LimitationsDealing with ComplexityDealing with Complexity: Simplified GeometryDealing with Complexity: Minkowski SumSlide 18Slide 19Dealing with Complexity: Bounding VolumesDealing with Complexity: Box Bounding VolumesDealing with Complexity: Achieving O(n) Time ComplexitySlide 23Terrain Collision Detection: Height Field LandscapeTerrain Collision Detection: Locate Triangle on Height FieldTerrain Collision Detection: Locate Point on TriangleSlide 27Slide 28Slide 29Collision Resolution: ExamplesCollision Resolution: PartsCollision Resolution: PrologueCollision Resolution: CollisionCollision Resolution: EpilogueCollision Resolution: Resolving Overlap TestingCollision Resolution: Extract Collision NormalSlide 37Collision Resolution: Resolving Intersection TestingChapter 4.2Collision Detection and Resolution2Collection DetectionNot as easy as it seemsSome objects move very fast (e.g. bullets)Some have complicated geometry(e.g. characters)Every object should be tested against every other object which is computationally expensive3Collision DetectionComplicated for two reasons1. Geometry is typically very complex, potentially requiring expensive testing2. Naïve solution is O(n2) time complexity, since every object can potentially collide with every other object For N objects, the amount of work is N*(N-1) or N2May cause difficulties during real time game play so we need to get good strategyCollision DetectionTwo basic techniques1. Overlap testingDetects whether a collision has already occurred2. Intersection testingPredicts whether a collision will occur in the future5Overlap TestingFactsMost common technique used in gamesExhibits more ERROR than intersection testingDiscrete Test of one point in time being testedOverlap testing is containment problemTest if any part of an object is inside any part of another objectConceptFor every simulation step, test every pair of objects to see if they overlapEasy for simple volumes like spheres, harder for polygonal models6Overlap Testing:Useful ResultsUseful results of detected collisionTime collision took placeCollision normal vectorNeeded later to compute response that prevents objects from further interpenetratingAccuracy of results not important as long as objects separated so that collision doesn’t occur next step7Overlap Testing:Collision TimeCollision time calculated by moving object back in time until right before collisionBisection is an effective techniqueSim moved forward or backward by half of the last sim step to converge on exact time of collision.Once collision detected simulation moved back to last simulation time. Moving Object A collides with Object B Five iterations of bisection to find time right before collisionB Bt1t0.375t0.25Bt0Iteration 1Forward 1/2Iteration 2Backward 1/4Iteration 3Forward 1/8Iteration 4Forward 1/16Iteration 5Backward 1/32Initial OverlapTestt0.5t0.4375t0.40625BB BAAAAA A8Overlap Testing:LimitationsFails horribly with objects that move too fastUnlikely to catch time slice during overlapBullet is small and traveling very fastFor it to always work, the speed of the fastest object, multiplied by time step must be less than the size of the smallest collidable object in the scenet0t-1t1t2bulletwindow9Overlap Testing:LimitationsPossible solutionsDesign constraint on speed of objects relative to the size of other objectsReduce simulation step size, but might result in having to step the simulation dozens or hundreds of times a framet0t-1t1t2bulletwindow10Intersection TestingPredict future collisions before they happenWhen predicted:Carefully Move simulation to time of collisionResolve collisionSimulate remaining time stepOften more accurate than overlap testingIf overlap testing is viewed as a containment problemIntersection testing is problem of visibility11Intersection Testing:Swept GeometryExtrude geometry in direction of movementSwept sphere turns into a “capsule” shapet0t112Intersection Testing:Sphere-Sphere CollisionQ1Q2P1P2PQt=0t=0t=1t=1t( ) ( )( )( ),22222BrrÁBtQP+−−⋅−⋅−=BAÂÁ( ) ( ).QQPPBQPA121211−−−=−=13Intersection Testing:Sphere-Sphere CollisionSimpler test of whether spheres collideSmallest distance ever separating two spheres: If there is a collision( )2222BAdBA ⋅−=( )22QPrrd +>14Intersection Testing:LimitationsIssue with networked gamesFuture predictions rely on exact state of world at present timeDue to packet latency, current state not always coherentErroneous collisions might occurAssumes constant velocity and zero acceleration over simulation stepHas implications for physics model and choice of integrator15Dealing with ComplexityTwo issues1. Complex geometry must be simplified2. Reduce number of object pair tests16Dealing with Complexity:Simplified GeometryApproximate complex objects with simpler geometry, like this ellipsoidSimpler Shape is cheaper to test17Dealing with Complexity:Minkowski SumBy taking the Minkowski Sum of two complex volumes and creating a new volume, overlap can be found by testing if a single point is within the new volume18Dealing with Complexity:Minkowski SumY}B and :{ ∈∈+=⊕ XABAYXX ⊕ Y⊕=YXX ⊕ Y=Created by sweeping the origin of X over all points within Y.19Dealing with Complexity:Minkowski Sumt0t1t0t1Performing an intersection test as a sphere moves during the simulation step. On the left, the swept sphere is tested against a stationary box. On the right, the line from the center of the sphere at t0 the center of the sphere at t1 is tested against the Minkowski sum of the sphere and box.20Dealing with Complexity:Bounding VolumesWith Minkowsky all volumes can be approximated by their bounding sphere.Bounding volume is a simple geometric shapeCompletely encapsulates objectIf no collision with bounding volume, no more testing is requiredCommon bounding volumesSphereBox21Dealing with Complexity:Box Bounding VolumesAxis-Aligned Bounding Box Oriented Bounding Box22Dealing
View Full Document