🗊Презентация Collision Detection

Категория: Математика
Нажмите для полного просмотра!
Collision Detection, слайд №1Collision Detection, слайд №2Collision Detection, слайд №3Collision Detection, слайд №4Collision Detection, слайд №5Collision Detection, слайд №6Collision Detection, слайд №7Collision Detection, слайд №8Collision Detection, слайд №9Collision Detection, слайд №10Collision Detection, слайд №11Collision Detection, слайд №12Collision Detection, слайд №13Collision Detection, слайд №14Collision Detection, слайд №15Collision Detection, слайд №16Collision Detection, слайд №17Collision Detection, слайд №18Collision Detection, слайд №19Collision Detection, слайд №20Collision Detection, слайд №21Collision Detection, слайд №22Collision Detection, слайд №23Collision Detection, слайд №24Collision Detection, слайд №25Collision Detection, слайд №26Collision Detection, слайд №27Collision Detection, слайд №28Collision Detection, слайд №29Collision Detection, слайд №30Collision Detection, слайд №31Collision Detection, слайд №32Collision Detection, слайд №33Collision Detection, слайд №34Collision Detection, слайд №35Collision Detection, слайд №36Collision Detection, слайд №37Collision Detection, слайд №38Collision Detection, слайд №39Collision Detection, слайд №40Collision Detection, слайд №41Collision Detection, слайд №42Collision Detection, слайд №43Collision Detection, слайд №44Collision Detection, слайд №45Collision Detection, слайд №46Collision Detection, слайд №47Collision Detection, слайд №48Collision Detection, слайд №49Collision Detection, слайд №50Collision Detection, слайд №51
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Collision Detection. Доклад-сообщение содержит 51 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Collision Detection
Описание слайда:
Collision Detection

Слайд 2


Collisions Up to this point, objects just pass through each other Two parts to handling collisions Collision detection – uses computational geometry techniques (useful in other ways, too) Collision response – modifying physical simulation
Описание слайда:
Collisions Up to this point, objects just pass through each other Two parts to handling collisions Collision detection – uses computational geometry techniques (useful in other ways, too) Collision response – modifying physical simulation

Слайд 3


Computational Geometry Algorithms for solving geometric problems Object intersections Object proximity Path planning
Описание слайда:
Computational Geometry Algorithms for solving geometric problems Object intersections Object proximity Path planning

Слайд 4


Distance Testing Useful for computing intersection between simple objects E.g. sphere intersection boils down to point-point distance test Just cover a few examples
Описание слайда:
Distance Testing Useful for computing intersection between simple objects E.g. sphere intersection boils down to point-point distance test Just cover a few examples

Слайд 5


Point-Point Distance Compute length of vector between two points P0 and P1, or
Описание слайда:
Point-Point Distance Compute length of vector between two points P0 and P1, or

Слайд 6


Line-Point Distance Line defined by point P and vector v Break vector w = Q – P into w and w|| w|| = (w  v) v ||w||2 = ||w||2 – ||w||||2
Описание слайда:
Line-Point Distance Line defined by point P and vector v Break vector w = Q – P into w and w|| w|| = (w  v) v ||w||2 = ||w||2 – ||w||||2

Слайд 7


Line-Point Distance Final formula: If v isn't normalized:
Описание слайда:
Line-Point Distance Final formula: If v isn't normalized:

Слайд 8


Line-Line Distance From http://www.geometryalgorithms.com Vector wc perpendicular to u and v or Two equations Two unknowns
Описание слайда:
Line-Line Distance From http://www.geometryalgorithms.com Vector wc perpendicular to u and v or Two equations Two unknowns

Слайд 9


Line-Line Distance Final equations:
Описание слайда:
Line-Line Distance Final equations:

Слайд 10


Segment-Segment Distance Determine closest point between lines If lies on both segments, done Otherwise clamp against nearest endpoint and recompute See references for details
Описание слайда:
Segment-Segment Distance Determine closest point between lines If lies on both segments, done Otherwise clamp against nearest endpoint and recompute See references for details

Слайд 11


Bounding Objects Detecting intersections with complex objects expensive Provide simple object that surrounds them to cheaply cull out obvious cases Use for collision, rendering, picking Cover in increasing order of complexity
Описание слайда:
Bounding Objects Detecting intersections with complex objects expensive Provide simple object that surrounds them to cheaply cull out obvious cases Use for collision, rendering, picking Cover in increasing order of complexity

Слайд 12


Bounding Sphere Tightest sphere that surrounds model For each point, compute distance from center, save max for radius
Описание слайда:
Bounding Sphere Tightest sphere that surrounds model For each point, compute distance from center, save max for radius

Слайд 13


Bounding Sphere (Cont’d) What to use for center? Local origin of model Centroid (average of all points) Center of bounding box Want a good fit to cull as much as possible Linear programming gives smallest fit
Описание слайда:
Bounding Sphere (Cont’d) What to use for center? Local origin of model Centroid (average of all points) Center of bounding box Want a good fit to cull as much as possible Linear programming gives smallest fit

Слайд 14


Sphere-Sphere Collision Compute distance d between centers If d < r1 + r2, colliding Note: d2 is not necessarily < r12 + r22 want d2 < (r1 + r2)2
Описание слайда:
Sphere-Sphere Collision Compute distance d between centers If d < r1 + r2, colliding Note: d2 is not necessarily < r12 + r22 want d2 < (r1 + r2)2

Слайд 15


Bounding Box Tightest box that surrounds model Compare points to min/max vertices If element less/greater, set element in min/max
Описание слайда:
Bounding Box Tightest box that surrounds model Compare points to min/max vertices If element less/greater, set element in min/max

Слайд 16


Axis-Aligned Bounding Box Box edges aligned to world axes Recalc when object changes orientation Collision checks are cheaper though
Описание слайда:
Axis-Aligned Bounding Box Box edges aligned to world axes Recalc when object changes orientation Collision checks are cheaper though

Слайд 17


Axis-Aligned Box-Box Collision Compare x values in min,max vertices If min2 > max1 or min1 > max2, no collision (separating plane) Otherwise check y and z directions
Описание слайда:
Axis-Aligned Box-Box Collision Compare x values in min,max vertices If min2 > max1 or min1 > max2, no collision (separating plane) Otherwise check y and z directions

Слайд 18


Object-Oriented Bounding Box Box edges aligned with local object coordinate system Much tighter, but collision calcs costly
Описание слайда:
Object-Oriented Bounding Box Box edges aligned with local object coordinate system Much tighter, but collision calcs costly

Слайд 19


OBB Collision Idea: determine if separating plane between boxes exists Project box extent onto plane vector, test against projection btwn centers
Описание слайда:
OBB Collision Idea: determine if separating plane between boxes exists Project box extent onto plane vector, test against projection btwn centers

Слайд 20


OBB Collision To ensure maximum extents, take dot product using only absolute values Check against axes for both boxes, plus cross products of all axes See Gottschalk for more details
Описание слайда:
OBB Collision To ensure maximum extents, take dot product using only absolute values Check against axes for both boxes, plus cross products of all axes See Gottschalk for more details

Слайд 21


Capsule Cylinder with hemispheres on ends One way to compute Calc bounding box Use long axis for length Next largest width for radius
Описание слайда:
Capsule Cylinder with hemispheres on ends One way to compute Calc bounding box Use long axis for length Next largest width for radius

Слайд 22


Capsule Compact Only store radius, endpoints of line segment Oriented shape w/faster test than OBB Test path collision
Описание слайда:
Capsule Compact Only store radius, endpoints of line segment Oriented shape w/faster test than OBB Test path collision

Слайд 23


Capsule-Capsule Collision Key: swept sphere axis is line segment with surrounding radius Compute distance between line segments If less than r1 + r2, collide
Описание слайда:
Capsule-Capsule Collision Key: swept sphere axis is line segment with surrounding radius Compute distance between line segments If less than r1 + r2, collide

Слайд 24


Caveat Math assumes infinite precision Floating point is not to be trusted Precision worse farther from 0 Use epsilons Careful of operation order Re-use computed results More on floating point on website
Описание слайда:
Caveat Math assumes infinite precision Floating point is not to be trusted Precision worse farther from 0 Use epsilons Careful of operation order Re-use computed results More on floating point on website

Слайд 25


Which To Use? As many as necessary Start with cheap tests, move up the list Sphere Swept Sphere Box May not need them all
Описание слайда:
Which To Use? As many as necessary Start with cheap tests, move up the list Sphere Swept Sphere Box May not need them all

Слайд 26


Recap Sphere -- cheap, not a good fit AABB -- still cheap, but must recalc and not a tight fit Swept Sphere -- oriented, cheaper than OBB but generally not as good a fit OBB -- somewhat costly, but a better fit
Описание слайда:
Recap Sphere -- cheap, not a good fit AABB -- still cheap, but must recalc and not a tight fit Swept Sphere -- oriented, cheaper than OBB but generally not as good a fit OBB -- somewhat costly, but a better fit

Слайд 27


Collision Detection Naïve: n2 checks! Two part process Broad phase Cull out non-colliding pairs Narrow phase Determine penetration and contact points between pairs
Описание слайда:
Collision Detection Naïve: n2 checks! Two part process Broad phase Cull out non-colliding pairs Narrow phase Determine penetration and contact points between pairs

Слайд 28


Broad Phase Obvious steps Only check each pair once Flag object if collisions already checked Only check moving objects Check against other moving and static Check rough bounding object first AABB or sphere
Описание слайда:
Broad Phase Obvious steps Only check each pair once Flag object if collisions already checked Only check moving objects Check against other moving and static Check rough bounding object first AABB or sphere

Слайд 29


Hierarchical Systems Can break model into hierarchy and build bounds for each level of hierarchy Finer level of detection Test top level, cull out lots of lower levels
Описание слайда:
Hierarchical Systems Can break model into hierarchy and build bounds for each level of hierarchy Finer level of detection Test top level, cull out lots of lower levels

Слайд 30


Hierarchical Systems Can use scene graph to maintain bounding information Propagate transforms down to children Propagate bound changes up to root
Описание слайда:
Hierarchical Systems Can use scene graph to maintain bounding information Propagate transforms down to children Propagate bound changes up to root

Слайд 31


Spatial Subdivision Break world into separate areas Only check your area and neighbors Simplest: uniform Slabs Grid Voxels
Описание слайда:
Spatial Subdivision Break world into separate areas Only check your area and neighbors Simplest: uniform Slabs Grid Voxels

Слайд 32


Sweep and Prune Store sorted x extents of objects Sweep from min x to max x As object min value comes up, make active, test against active objects Can extend to more dimensions
Описание слайда:
Sweep and Prune Store sorted x extents of objects Sweep from min x to max x As object min value comes up, make active, test against active objects Can extend to more dimensions

Слайд 33


Spatial Subdivision Other methods: Quadtrees, octrees BSP trees, kd-trees Room-portal Choice depends on your game type, rendering engine, memory available, etc.
Описание слайда:
Spatial Subdivision Other methods: Quadtrees, octrees BSP trees, kd-trees Room-portal Choice depends on your game type, rendering engine, memory available, etc.

Слайд 34


Temporal Coherence Objects nearby generally stay nearby Check those first Can take memory to store information
Описание слайда:
Temporal Coherence Objects nearby generally stay nearby Check those first Can take memory to store information

Слайд 35


Narrow Phase Have culled object pairs Need to find Contact point Normal Penetration (if any)
Описание слайда:
Narrow Phase Have culled object pairs Need to find Contact point Normal Penetration (if any)

Слайд 36


Contact Region Two objects interpenetrate, have one (or more) regions A bit messy to deal with Many try to avoid interpenetration
Описание слайда:
Contact Region Two objects interpenetrate, have one (or more) regions A bit messy to deal with Many try to avoid interpenetration

Слайд 37


Contact Features Faceted objects collide at pair of contact features Only consider E-E and F-V pairs Infinite possibilities for normals for others Can generally convert to E-E and F-V Ex: V-V, pick neighboring face for one
Описание слайда:
Contact Features Faceted objects collide at pair of contact features Only consider E-E and F-V pairs Infinite possibilities for normals for others Can generally convert to E-E and F-V Ex: V-V, pick neighboring face for one

Слайд 38


Contact Features For E-E: Point is intersection of edges Normal is cross product of edge vectors For F-V: Point is vertex location Normal is face normal
Описание слайда:
Contact Features For E-E: Point is intersection of edges Normal is cross product of edge vectors For F-V: Point is vertex location Normal is face normal

Слайд 39


Contact Points Can have multiple contact points Ex: two concave objects Store as part of collision detection Collate as part of collision resolution
Описание слайда:
Contact Points Can have multiple contact points Ex: two concave objects Store as part of collision detection Collate as part of collision resolution

Слайд 40


Example: Spheres Difference between centers gives normal n (after you normalize) Penetration distance p is p = (r1+r2) - ||c2-c1||
Описание слайда:
Example: Spheres Difference between centers gives normal n (after you normalize) Penetration distance p is p = (r1+r2) - ||c2-c1||

Слайд 41


Example: Spheres Collision point: average of penetration distance along extended normal If touching, where normal crosses sphere
Описание слайда:
Example: Spheres Collision point: average of penetration distance along extended normal If touching, where normal crosses sphere

Слайд 42


Lin-Canny For convex objects Easy to understand, hard to implement Closest features generally same from frame to frame Track between frames Modify by walking along object
Описание слайда:
Lin-Canny For convex objects Easy to understand, hard to implement Closest features generally same from frame to frame Track between frames Modify by walking along object

Слайд 43


Lin-Canny Frame 0 Frame 1
Описание слайда:
Lin-Canny Frame 0 Frame 1

Слайд 44


GJK For Convex Objects Hard to understand, easy to implement Finds point in Configuration Space Obstacle closest to origin. Corresponds to contact point Iteratively finds points by successive refinement of simplices
Описание слайда:
GJK For Convex Objects Hard to understand, easy to implement Finds point in Configuration Space Obstacle closest to origin. Corresponds to contact point Iteratively finds points by successive refinement of simplices

Слайд 45


GJK CSO Simplex Refinement
Описание слайда:
GJK CSO Simplex Refinement

Слайд 46


Missing Collision If time step is too large for object speed, two objects may pass right through each other without being detected (tunneling)
Описание слайда:
Missing Collision If time step is too large for object speed, two objects may pass right through each other without being detected (tunneling)

Слайд 47


Missing Collision One solution: slice time interval Simulate between slices Same problem, just reduced frequency
Описание слайда:
Missing Collision One solution: slice time interval Simulate between slices Same problem, just reduced frequency

Слайд 48


Missing Collision Another solution: use swept volumes If volumes collide, may collide in frame With more work can determine time-of-impact (TOI), if any
Описание слайда:
Missing Collision Another solution: use swept volumes If volumes collide, may collide in frame With more work can determine time-of-impact (TOI), if any

Слайд 49


Recap Collision detection complex Combo of math and computing Break into two phases: broad and narrow Be careful of tunneling
Описание слайда:
Recap Collision detection complex Combo of math and computing Break into two phases: broad and narrow Be careful of tunneling

Слайд 50


References Preparata, Franco P. and Michael Ian Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. O’Rourke, Joseph, Computational Geometry in C, Cambridge University Press, New York, 1994. Eberly, David H., 3D Game Engine Design, Morgan Kaufmann, San Francisco, 2001. Gottschalk, Stephan, Ming Lin and Dinesh Manocha, “OBB-Tree: A Hierarchical Structure for Rapid Interference Detection,” SIGGRAPH ‘96.
Описание слайда:
References Preparata, Franco P. and Michael Ian Shamos, Computational Geometry: An Introduction, Springer-Verlag, New York, 1985. O’Rourke, Joseph, Computational Geometry in C, Cambridge University Press, New York, 1994. Eberly, David H., 3D Game Engine Design, Morgan Kaufmann, San Francisco, 2001. Gottschalk, Stephan, Ming Lin and Dinesh Manocha, “OBB-Tree: A Hierarchical Structure for Rapid Interference Detection,” SIGGRAPH ‘96.

Слайд 51


References Van den Bergen, Gino, Collision Detection in Interactive 3D Environments, Morgan Kaufmann, San Francisco, 2003. Eberly, David H., Game Physics, Morgan Kaufmann, San Francisco, 2003. Ericson, Christer, Real-Time Collision Detection, Morgan Kaufmann, San Francisco, 2004.
Описание слайда:
References Van den Bergen, Gino, Collision Detection in Interactive 3D Environments, Morgan Kaufmann, San Francisco, 2003. Eberly, David H., Game Physics, Morgan Kaufmann, San Francisco, 2003. Ericson, Christer, Real-Time Collision Detection, Morgan Kaufmann, San Francisco, 2004.

Скачать

Теги Collision Detection
Похожие презентации
Mypresentation.ru
Загрузить презентацию