Intersections & Collisions

Intersection testing:

• Determine whether two geometric primitives intersect
• Often one primitive is a line
• Used for picking, ray-tracing, collision detection, ...

Collision detection:

• Determine whether two objects are in contact
• Can be static or dynamic

Primitives

Line (or ray):     R(t) = O + Dt

Primitives

Sphere:     ||P - C|| = r

Primitives

Triangle     P0, P1, P2

Primitives

Axis-aligned bounding box (AABB):     Xmin <= x <= Xmax     Ymin <= y <= Ymax     Zmin <= z <= Zmax

Primitives

Oriented bounding box (OBB):     Bcenter     Bu, Bv, Bw

Primitives

Plane:     Ax + By + Cz + d = 0       or     N * P + d = 0

Rules of Thumb

• Perform trivial reject or accept tests early
  
  
• Exploit results from previous tests, if they fail
  
  
• Precalculate information that will be used for several tests
  
  
• Postpone expensive calculations (square root, trig, division)
  
  
• Reduce the dimension of the problem

Collision Detection

Techniques:

• Compute a bounding volume for each object
  
  
• Test bounding volumes against each other, before testing actual polygons
  
  
• Create a hierarchy of bounding volumes

Math

Dot product facts:

V dot V = ||V||²

Dot product of V with a unit vector u is the length of the projection of V onto u

Functions

• Distance between point and:
  • point
  • sphere
  • plane
  • line
  • AABB (axis aligned bounding box)
  • OBB (oriented bounding box)
• Point in:
  • sphere
  • AABB
  • OBB
• Sphere - sphere collision
• Sphere - sphere containment
• AABB - AABB collision
• Sphere - AABB collision
• Ray - plane intersection
• Point in triangle
  
  
• Reflection

Libraries

This document is by Dave Pape, and is released under a Creative Commons License.