CSCE 441 Lecture 35

« previous | Wednesday, April 16, 2014 | next »

Collision Detection: Boundary Volume Hierarchies

A tree of bounding volumes:

Root: single BV around entire object

Each level: subdivide recusively into 2 or more parts, each with their own bounding volume

Repeat until only one atomic shape remains.

Intersecting Hierarchies

Keep queue of potentially intersecting pairs of BVs

• initialize with main BV for each object

Repeatedly dequeue next potential pair off queue and test for intersection:

• If they intersect, put pairs of children into the queue
• If no child for both BVs, test triangles inside

Stop when we either run out of pairs (no intersection) or ...

Broad Phase

Everything we have discussed so far are about "narrow phase" intersection (testing whether two individual objects collide)

Broad phase assumes we have a number of objects, and we want to find all pairs of objects that collide.

Testing pairs is inefficient

1. Form AABB for each object
2. Pick an axis
3. Sort objects along that axis
4. Find overlapping pairs along axis
5. For overlapping pairs, check along other axes

This limits the number of object/object tests Overlapping pairs then sent to narrow phase.

Physically-Based Simulation

Must account for object motion

Obey basic physical laws: integration of differential equations

Collision detection gives yes/no, but simulation asks more:

• determination: where do they intersect
• response: how do we adjust the motion of objects in response to collision

Both are nontrivial

Other Issues

Constructing an optimal BVH

Convergence of BVH (how fast do the BVs approach the actual object?)

• OBBs are asymptotically better at this.

Optimizing individual tests

Handling stacking and rest contacts

Programmable Shaders

GPUs are everywhere

Performance evolution:

Nvidia Geforce 6800 GTX || 6.4 Gpx/sec Nvidia Geforce 7900 GTX || 15.6 Gpx/sec Xbox 360 || 16 Gpx/sec (4× antialiased) Nvidia Geforce 8800 GTX || 36.8 Gpx/sec Nvidia Geforce GTX 295 || 92.2 Gpx/sec

Parallel processing:

Nvidia Geforce GTX 780 Ti 2880 programmable processors 875 MHz ea. 336 GB/s memory bandwidth 3 GB memory

AMD (formerly ATi) Radeon HD 7990 4096 processors 8.2 TFLOPS Requires maybe a couple KVolts of power

IBM's ASCI White, fastest computer in the world in 2000 4.9 TFLOPS Required a small reactor

GPU Processors are not like CPU processors:

• SIMD: single instruction, multiple data
• Groups of processors all perform the same operation on a vector of data.

The computing industry has wanted this for a while, but there was no demand for it... until computer gaming came about.

Problems formulated for GPUs can get a huge speedup!

• An industry evolved to turn any algorithm into a polygon drawing problem
• Programmable GPUs came about, voiding all of the prior work

China recently built the fastest supercomputer in the last couple years entirely out of GPUs...

GPUs are excellent at brute-force algorithms.