CSCE 441 Lecture 34

« previous | Monday, April 14, 2014 | next »

Extra Credit Assignment

Subdivision Surfaces; 60 points possible

Compute normals of quads by taking the cross product of the diagonals

Collision Detection

Used in:

• simulations
• ray tracing speedup
• culling objects or classifying objects in regions

Usually needs to be fast: lots of objects, often in real-time applications

Bounding Volumes

Key idea: surround object with a simpler bounding object (bounding volume)

If something does not collide with the bounding volume, it does not intersect the object inside.

Often, to intersect two objects, first intersect their bounding volumes.

Lots of cohices, each with tradeoffs:

• Tighter fitting is better (more likely to eliminate "false intersections")
• Simpler is better (easier and faster to comptue)
• Convex objects give simpler shape
• Rotation-invariant is better (easier to update as the object moves)

Sphere

• Rotationally invariant (usually; only if rotating about the center)
• Usually fast to compute with
• Often not a tight fit.
• Center point is often the center of mass.

Axis-Aligned Bounding Box (AABB)

• very fast to compute with
• store max and min x,y,z coordinates
• moderately tight fit
• must update after rotation/transformation

K Discrete Oriented Polytopes (K-DOPS)

Same idea as AABB, but uses more axes

Tighter fit, but requires more work.

Common axes: consider axes coming out of the center of a cube:

• faces give 6-DOP (same as AABB)
• Faces and vertices give 14-DOP
• Faces and edge centers give 18-DOP
• Faces, vertices, and edge centers give 26-DOP
• More is not really helpful
• 14–18 usually performs best

Oriented Bounding Box (OBB)

• Similar to AABB, but allow the bounding box to rotate with object
• Store rectangular parallelepiped oriented to best fit the object:
  • center
  • orthonormal set of axes
  • extent along each axis
• Generally slower than AABB

Convex Hull

• Very tight fit (tightest convex bounding volume
• Slow computation
• Store set of polygons forming convex hull
• Rotate hull along with object
• Can be efficient for some applications

Testing for Collision

Will depend on type of objects and bounding volumes

Specialized algorithms for each:

• Sphere/Sphere
• AABB/AABB
• OBB/OBB
• Ray/Sphere
• Triangle/Triangle

Sphere-Sphere =

Find distances between centers of spheres Compare to sum of radii If distance is less than sum, they collide.

AABB-AABB

Project AABBs onto axes (i.e. look at extents)

If overlapping on all axes, then the boxes overlap.

Same idea for K-DOPS

OBB-OBB

Separating Axis Theorem: Two convex objects do not overlap if and only if there exists an axis such that the projectiso of the two shapes do not overlap.

Enumerating Separating Axes:

• 2D: check axis aligned with normal of each face.
• 3D: check axis aligned with normals of each face and cross product of each pair of edges.

Triangle-Triangle

Two common approaches, both involve finding plane the triangle lies in.

• Cross product of edges to get triangle normal.
• This is the plane normal $\left\langle a,b,c\right\rangle$, where the plane is defined as $a\,x+b\,y+c\,z+d=0$.
• Solve for $d$ by plugging in a triangle vertex.

Algorithm 1

1. Find line of intersection between triangle planes
2. Find extents of triangles along this line.
3. If extends intersect, the triangles overlap

Algorithm 2

1. Intersect edges of one triangle with plane of other triangle
2. 2 edges will intersect: form line segment in plane
3. Test if segment intersects with other triangle

Bounding Volume Hierarchies

What happens when bounding volumes do intersect?

• test whether actual objects underneath intersect
• objects beneath top-level bounding volume could be sub-bounding-volumes, and so on.