Re: [Algorithms] Colliding against polygon soup

[Tom H. <to...@3d...>]

At 09:47 PM 12/6/2000, you wrote:
>At 09:46 AM 12/7/00 +0800, Conor Stokes wrote:
>>OBB-Trees can apply to interiors rather well actually. Heightmaps are
>>special cases anyway, and suited to quadtrees much better (they are a very
>>2d collision problem.)
>
>I dislike the assumption that a terrain = heightmap.  I'd like to use a 
>generalized mesh to represent a terrain region, say something like you'd 
>say in the old Dagoth Moor demo that shipped with the GeForce.  Overhangs, 
>caves, etc.
>
>So if you're building an interior with OBB-Trees, how do you do it?  I 
>mean, not the technical stuff, I'm talking about the logical stuff -- do 
>you end up building it as discrete pieces (column 0, dais, stairs, rail, 
>etc.) or as a single monolithic mesh and there's some magic OBB-Tree 
>creation algorithm I'm unaware of that automatically takes a mesh and 
>decomposes it into sane OBBs?

Seems like this thread is bouncing around a bit, probably due to the very 
general nature of the question, "How do you collide with a polygon soup". 
By my definition (argue with it if you like) a polygon soup is a collection 
of triangles with no order, no definition of inside or outside, and no 
connectivity information. While this is an interesting exercise, it isn't 
really indicative of something we really have to deal with. You started 
with Max or Maya as a content source, so lets look at what we have coming 
out of those for data.

1. A clear definition of inside and outside. This is controlled by the 
winding of the triangles.
2. Connectivity information. Vertices are indexed and shared (if not, then 
vertices can be indexed and checked for redundancy within a tolerance). 
Edge connectivity can be extracted from this if desired (and I suspect it 
will be wanted for things like AI pathing).
3. Triangles collected into objects by the artists and placed into the 
scene by reference.
4. Fields for each object that can contain rendering or collision flags, or 
any other engine specific information.

So I think the question at this point should be, "Given these constraints, 
how do I design a collision detection system that allows objects to move 
around in a scene".

For a general system that works with large outdoor areas as well as 
internal buildings, I'd look at something like the following:

1. Flag objects in the scene as either "world" or "scenery" (I keep scenery 
separate so you can do thing like flag a 5k tri sculpture as scenery and 
only collide against its bounding box or something)
2. All the "world" object triangles would be pushed into a KD-tree*, and 
the triangles would be at the nodes of the tree. Splits of the tree would 
stop when a maximum triangle count is reached.
3. "scenery" would be inserted by reference into the leaves that it intersects

When rendering and colliding, multiple references to the same "scenery" and 
triangles contained in multiple leaves would need to be resolved so they 
wouldn't be rendered / checked multiple times. Either that, or the 
"scenery" and triangles can be split at node boundaries.

Since you now have leaves of small (and controlled) complexity, you can use 
these for whatever collision method you want. The idea here is that you can 
radically reduce the possible collision set down to a few hundred (or maybe 
a few thousand) triangles. Each leaf can have an OBB associated with it (or 
maybe a BSP if that's your wish). As I recall, the OBB stuff wraps an OBB 
around each triangle and then uses frame coherence to track which one 
you're closest to. When you penetrate an OBB, it check the triangle itself 
for collisions. The OBBs are collected into a hierarchy of OBBs to speed up 
processing. So ... you could have an OBB tree for each leaf, instead of an 
OBB for your entire world. Check for collisions against the OBB trees of 
the KD-tree node(s) your moving objects are in.

Might ask, why not put the entire world into one big OBB tree. My reason .. 
I suspect OBB nodes are much larger than KD-tree nodes. I also wouldn't 
want to walk through a HUGE world of 10s of millions of OBB nodes when I 
just want to collide in one small neighborhood. YMMV.

I guess my question for you is, how exactly do you want to use this stuff? 
Different methods of scene organization and collision are more useful 
depending on the type of data you expect to have. Whatever you do will have 
limits. What I describe above would work ok for areas of small animation 
(doors, draw bridges, etc) but would be awful if you wanted to have a large 
portion of the world moving over long distances in a non-deterministic 
manner, or deal with vastly changing geography (large scale deformations).

Design the world you want to play in, then figure out how to render and 
maneuver within it. Trying to figure out how to do anything and everything 
all at once isn't as productive as it might seem at first :)

>>with the same entity. Eg, a sphere can collide with 2 triangles, and needs
>>to be pushed back from both of them.
>
>I'm having a hard time visualizing this...what's an example of this?  Do 
>you mean the case where the sphere is going into a "V" and pushing off of 
>one triangle forces it into the other?

Yes, I'm pretty sure that's what he means.

* A KD-Tree is a binary tree. Each node of the tree is one of three planes 
(X, Y, or Z) and an origin, and as you traverse the tree you switch 
between, X, Y, Z. Its like an unrolled octree that you can move the 
boundaries around on. You can exactly represent an octree by always 
splitting the space in half, and cycling from Y, X, to Z at each depth 
increment, but by moving the origin around and allowing more freedom of 
plane selection you can get a better fit on most scenes. I seem to recall 
some decent descriptions on www.flipcode.com

Tom