|
Outdoor Collisions & Culling Question submitted by (27 July 1999)  |
Return to The Archives |
 |
 |
|
|
I am currently writing a simple 3d platform game, which is in
the large outside. Consider Mario64 for a reference point. If I was rendering inside, I could use portals/BSPs to help with collision and culling, but when dealing with many seemingly random shapes floating in space, it gets tricky. Does anyone know of any good algorithms or ideas? |
||
 |
 |
 |
|
|
|
Often times, I tend to fall back on octrees. The time has come to do it
again. You can build an octree of your scene (or portions of your scene) to be used to limit the number of collision tests you perform. You can build your octree in a standard fasion (i.e. subdivide each node until fewer than 'n' polygons are contained within a node.) To perform collisions, traverse the octree with the input location to find the leaf node for that point. Try colliding with each polygon in that node. If no collisions are found, step to the next leaf node along the velocity vector and try those polygons. If you reach the destination node (i.e. the 'end' of your velocity vector) with no collisions, then no collisions occured. If you can limit your leaf nodes to, say, 10 or fewer polygons, then your collision tests should go quite quickly. Notice how this gives you perfect collision with every polygon in the scene and fairly good performance to boot! Response provided by Paul Nettle |
||
|
|
|
This article was originally an entry in flipCode's Fountain of Knowledge, an open Question and Answer column that no longer exists. |