Re: [Algorithms] Colliding against polygon soup

[Brian H. <bw...@wk...>]

At 08:44 AM 12/6/00 +0800, Conor Stokes:
>But, anyway, the first thing to do is test if the destination and starting
>point (+ the length of the radius in each direction) of the sphere are on
>seperate sides of the plane.

Right, trivial rejection.

>If this point is within the set of planes perpindicular to both the triangle
>and on the line of an edge on the triangle, then your collision has occured
>and that point is kept.

I understand the theory of this, but how do people do the 
implementation?  Do folks keep a set of planes for each triangle that 
define its interior or do they compute these on the fly or do they do 
something completely different in practice?

On a related note, the articles I've been reading on OBB-Trees make it seem 
like a fast way of culling against a hierarchical set of geometry very 
rapidly.  This doesn't seem to apply to things like terrains or large 
convoluted meshes like interiors...or am I missing something fundamental?

 From what I'm gathering, collision basically works in three basic steps:

- high level culling..find the set of objects that you might be able to 
hit.  This can usually be done using general sphere tests against 
everything in the world, and probably with some other fast way of 
refinement, e.g. oct-tree, convex cells, grid, etc.

- mid level culling...given an object, find the set of pieces that you 
might collide against via hierarchical examination.  This is typically done 
with a hierarchical tree, e.g. OBB-Tree or AABB-Tree, that lets you quickly 
refine your search to pieces of the object that are truly likely to collide.

- given a "potentially collidable set" of triangles, i.e. the final soup, 
iterate over every triangle, test for collision against your core collision 
entity (ray, swept sphere, wthaever), and use the nearest triangle as the 
output of your "what is the nearest thing I collide against traveling from 
point A to point B"?  This seems rather, well, yucky.

Brian