0
101 Dec 09, 2007 at 21:33

I can’t seem to find any good tutorials on the implementation of per-polygon collision detection. By this, I don’t mean per-polygon hit detection (as in ray tracing), but detecting collisions between two animated meshes with potentially high polygon counts.

I’m looking for pointers on how to go about implementing something like this efficiently. Can you guys point me to a page with good references on the topic? Or sketch out algorithms?

What I’d like to be able to do is have say, semi-realistic collision detection and reaction between objects, with rotational velocities handled… I’d also like my implementation to be stable enough to handle reasonable boundary cases (so very fast objects can’t go through each other).

#### 7 Replies

0
101 Dec 10, 2007 at 19:31

Trimesh collision algorithms are there, but I must warn you, they are inefficient. There has been efforts to make them efficient, but convex hull and composite shapes are always going to be faster and take less memory …

You basically traverse the triangles and for every triangle, you traverse the other match, checking collisions. This process is usually sped up using octrees or so … ODE for example has trimesh vs trimesh collision algorithm.

0
101 Dec 10, 2007 at 22:59

It usually looks pretty good using approximations like cylinders mind …

0
101 Dec 11, 2007 at 02:41

I’d actually like to have animated models that are concave, if possible. For example, being able to step into a “mechwarrior” model, which is skeletally animated, and has a rather detailed inside.

I suppose a possible approach may be to compute multiple LODs for the mesh, as well as one or more bouding volumes around it, and proceed by progressive refinement…

How does one go about efficiently checking collision between moving triangles, though? I know how to do intersection testing, that’s easy, but moving triangles occupy a volume over time. Has anyone tried implementing this as the intersection of two four dimensional volumes? Is this a viable approach speed-wise (and code-sanity-wise)?

0
165 Dec 11, 2007 at 05:38

To a first approximation, I’d just calculate the convex hull of each triangle’s start and end positions in the current timestep, and look for an intersection between the two hulls. True, this doesn’t model high-speed rotation very accurately, and it’s possible with the right circumstances that the triangles missed each other even if their hulls collide. However, this method might well be good enough for your purposes.

Another possibility is to look into using OBB trees. You can probably create an OBB tree that models the interior of your mechwarrior with enough detail, but is much faster than colliding with every triangle, not to mention probably easier to make a stable physics simulation out of.

Also, even if you stick with real per-triangle collision, you needn’t use the same mesh for physics as for rendering. The physics mesh can be a very low-detail version and still get good-looking results.

0
101 Dec 11, 2007 at 17:30

True, this doesn’t model high-speed rotation very accurately.

This can easily be fixed by introducing an additonal time-frame subdivision step for fast-moving objects. Since only few objects in the scene need this treatment it actually is more efficent than one might guess. It also helps with physics robustness for low frame rates in physics/logics/rendering-coupled single threaded game scenarios, where the time frames may get too large for a more naive euler-based physics simulation.

Also, even if you stick with real per-triangle collision, you needn’t use the same mesh for physics as for rendering. The physics mesh can be a very low-detail version and still get good-looking results.

You even shouldn’t use the same meshes for both ! Consider physics involving a high-detail polymesh: Since it is high-detail there are many more discontinuities in the geometry than with a simpler mesh. This allows physics objects to get stuck or “wiggle” at certain points which gives the entire simulation a rough feeling, rather than a smooth drifting motion.

Cheers,
- Wernaeh

0
101 Dec 12, 2007 at 05:11

Had anyone ever done “per-poly” collision detection using raytracing? Say, stochastically tracing a certain number of rays in the direction the model is going, and seeing if the rays hit something… Then, if something is hit, taking the shortest ray to be the collision distance…

A quick bounding AABB test could be done to save useless ray-tracing… And say, by tracing up to 500 rays (which should not be so slow), the collision detection process could be refined.

You might think that things like grids may pose problems… But those potential colliderss may just be detected by the prior AABB test… And rays could also be traced from potential colliders to the object in question….

Just a thought?

0
101 Dec 16, 2007 at 00:26

@Nyx

Had anyone ever done “per-poly” collision detection using raytracing? Say, stochastically tracing a certain number of rays in the direction the model is going, and seeing if the rays hit something… Then, if something is hit, taking the shortest ray to be the collision distance…

Do you need to sample it stochastically? … the easiest way to work is if all “entities” apply a force in a given frame to move them around. Like that you don’t have to worry about such things, because for a given force and direction you can only move linearly to the next frame. Its amazing how good a system looks like this. If you REALLY wanna push it you could “splinearly” interpolate between positions … but that beats out multiple ray casts sent out stochastically .. surely?

Edit: 0xff posts! :D