Collision Detection - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

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

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

Слайд 3

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

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

Слайд 5

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

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

Слайд 7

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

Line-Point Distance Final formula: If v isn't normalized:

Слайд 8

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

Line-Line Distance From Vector wc perpendicular to u and v or Two equations Two unknowns

Слайд 9

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

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

Слайд 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

Слайд 12

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

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

Слайд 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

Слайд 15

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

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

Слайд 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

Слайд 18

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

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

Слайд 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

Слайд 21

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

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

Слайд 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

Слайд 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

Слайд 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

Слайд 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

Слайд 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

Слайд 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

Слайд 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

Слайд 30

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

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

Слайд 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

Слайд 33

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

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

Слайд 35

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

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

Слайд 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

Слайд 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

Слайд 39

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

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||

Слайд 41

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

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

Слайд 43

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

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

Слайд 45

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

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)

Слайд 47

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

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

Слайд 49

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

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.

Слайд 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.

Теги Collision Detection

Похожие презентации