Re: [Algorithms] Colliding against polygon soup

[Conor S. <cs...@tp...>]

> 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?

Well, that is up to you. Generating them on the fly is okay, but the main
problem is the fact that you have to normalise the plane normals.

This can be got around with some simple math, and a tiny bit of
precalculation. Instead of storing the normals you store the inverse lengths
of the edges of your triangles (3 floats vs 12 floats to store the planes of
edges). To get the normal of the new planes, you take the cross product of
an edge and the normal of the triangle. Because the magnitude of the cross
product is |A||B|sin(of the angle between A and B) and the angle between
them the triangle normal and the edge is always 90 degrees, the cross
product always comes out with a magnitude of |A||B|. And assuming your
triangle's normal is normalised, it comes out as 1|edge|.

So your normalisation becomes a multiply rather than division and roots.

>
> 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?

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.)

> - 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.

You can actually combine the two steps if you want. Store your entire world
in an tree, where you have objects at one level in the nodes, then go lower
for better collision detection.

>
> - 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.
>

Well, once you get the final soup, which is usually very few triangles, the
collision can still be more complicated than "what is the nearest thing I
collide against". Except in the case or rays, you can have multiple collides
with the same entity. Eg, a sphere can collide with 2 triangles, and needs
to be pushed back from both of them.

It may seem a lot of things to do, but reducing your set prior to the
collision tests can be very important.

Conor Stokes