[font="Book Antiqua"]I'm trying to determine what narrow-phase collision detection techniques are fastest to execute for arbitrarily irregular "concave" objects. Most importantly, I'd like to know approximately how much slower they are than convex hull techniques like GJK (on the convex hull of the same objects). The emphasis I see on convex hull techniques implies that every technique that works reliably on arbitrarily irregular "concave" objects is slower than GJK. The question is, how much slower?

Mine is 2x to 20x slower than my GJK implementation. While 2x slower is not a big problem, the 20x slower cases "hurt". I'm pretty sure I see a way to reduce the upper end to 10x ~ 15x slower, but not further. Hence my desire to learn whether faster approaches exist. Thanks in advance for any ideas or tips.[/font]

Concave collision is usually much slower than convex. 20x slower would not surprise me. You might want to look into something like "inner sphere tree." Unfortunately, pre-computation methods are geared towards static geometry, not skinned/animated models.

[font="Book Antiqua"]Thanks for the tips. I read a couple articles about "inner sphere trees", plus an illustrative youtube video. What I wasn't completely clear about was precision. From what I read and saw, it seems like collision detection precision is limited by the spheres within the objects.

If objects intersect where spheres on those objects touch the object surfaces, the precision will be high. If objects intersect where moderately large gaps in the spheres exist, the precision will suffer. When the gaps get to a certain size, their algorithm seems to create and insert additional small balls in the gaps, but there is a very serious tension between precision and number of balls (where number of balls is costly in cache, memory and processing time).

Also, the articles I read conveniently didn't show any difficult cases - say, a sword that might slice other objects in the game. Since the sword is quite thin, the number of balls is inherently enormous (vastly more than the number of triangles), and a review of common objects indicates to me that the number of difficult cases is very non-trivial unless the game is purposely designed to avoid such objects. I suppose that's one strategy, but I'm writing a general purpose simulation/game engine optimized for procedurally generated content, and I cannot assume much of anything about the quantities, shapes or sizes of objects that are created and manipulated by the application/game.

Is that the only narrow phase collision detection scheme --- other than decomposing arbitrarily irregular "concave" objects into boatloads of convex ones and performing GJK (or similar) on every possible collision-pair?[/font]

What do you mean by "2x to 20x slower than my GJK implementation"? i.e did decompose your concave shape into convex chunks and run GJK on those? Otherwise I'm not sure how you could directly compare the two tests. (Also, is this in 2d or 3d?)

Unless your objects are deformable, I think the common solution is to opt for convex decomposition.

Having said that, what technique are you using for your concave collision tests? Just mesh-mesh? (i.e testing each triangle vs other triangles) Are you using an AABB-tree or some other form of broadphase structure to accelerate things?

What do you mean by "2x to 20x slower than my GJK implementation"? i.e did decompose your concave shape into convex chunks and run GJK on those? Otherwise I'm not sure how you could directly compare the two tests. (Also, is this in 2d or 3d?)

Unless your objects are deformable, I think the common solution is to opt for convex decomposition.

Having said that, what technique are you using for your concave collision tests? Just mesh-mesh? (i.e testing each triangle vs other triangles) Are you using an AABB-tree or some other form of broadphase structure to accelerate things?

[font="Book Antiqua"]My engine is a 3D simulation/game engine and everything is in 3D. I have a separate "general collision detection routine" that doesn't require convex objects, and doesn't care at all what the shapes of objects are. It does not require that anything be pre-computed, and works just as well on objects that deform every frame as fixed-shape objects.

Since I'm making a general purpose engine that is supposed to work on "everything" without exception (including deforming objects), and the engine is supposed to handle collision response automatically based upon the materials and collision dynamics, I can't afford to adopt "convex decomposition". Furthermore, the engine is intended and optimized for "procedurally generated content", and some "procedurally generated content" cannot be identified by the engine as concave or convex.

In those cases where the engine is certain an object is convex, it only calls the GJK function. At least I hope there is no need to call the general/concave/ANY collision detection function on known convex objects just to get the exact collision features at first-contact (or when penetrated if one or both are highly compressible objects like big fat air-filled tires). It is easy to get the closest features from GJK when objects are not in collision, but I'm not 100% sure I can make GJK generate "most deeply penetrating features" when objects are in collision. I think so, but I haven't done that yet.

I need the engine to support the most absurd possible cases, including objects with [moving] holes, tunnels winding through volumes, you name it. Which is why I had to create a totally general collision detection algorithm.

My comparisons are simple. I perform my timings with the native internal 64-bit CPU timer register that runs at the CPU clock rate, which is about 3.5 GHz in my case.

The "broad phase" collision detection routine has finished executing and has created a list of object-pairs that might be in collision. To compare my "GJK convex collision detection" function with my "general collision detection" function my code then executes the following for all object-pairs:


s64 timerGJK = 0; // GJK convex objects collision timer
s64 timerANY = 0; // ANY irregular/concave objects collision timer

for all object pairs that might be in collision according to broad-phase {
get_next_object_pair (&objid0, &objid1);

timer_get_now (&timer00);
GJK_collision_function (objid0, objid1);
timer_get_now (&timer01);
timerGJK = timerGJK + (timer01 - timer00);

timer_get_now (&timer00);
ANY_collision_function (objid0, objid1);
timer_get_now (&timer01);
timerANY = timerANY + (timer01 - timer00);
}


Once the above routine has gone through all possibly colliding object-pairs, it prints out the values timerGJK and timerANY. This tells me how many CPU cycles each routine consumes. The GJK function happily performs collision detection on the convex hull that contains all the object vertices, whether the objects themselves are convex or not. The ANY function performs collision detection on arbitrary objects and thus sometimes finds object-pairs not in collision that GJK considers in collision.
[/font]

The typical approach for concave objects is either:

* Build a BVH (I like sphere trees because they are rotationally invariant) of the triangles that compose the object and do triangle/triangle tests. The issue with this approach is that generating useful contact information can be difficult. It's also probably slower than the second option, though simpler to implement.

* Decompose the concave objects into a number of convex polyhedra using a convex decomposition algorithm (preprocessing step). Store these polyhedra in a sphere tree to determine which ones to test efficiently, then perform GJK + EPA on each potentially colliding pair. This should generate far better contact information than the above method, though it requires implementing several complex algorithms (decomposition is particularly hard to get right).

For deforming objects, you're going to need to handle them as a special case (using a tetrahedral mesh or lattice-based shape matching, for instance) in order to get the kind of performance you want. Most of the standard collision detection algorithms are designed to work for static geometry and won't be practical for deforming objects.

[font="Book Antiqua"]Thanks for the information.

Hmmm. I'll have to perform careful analysis on the consequences of those techniques in the context of my engine support for arbitrary "procedurally generated content". My initial reaction is, I might be better off investing my time and effort to make the existing concave collision detection routine faster (I should be able to improve the efficiency of 2 or 3 subprocesses). The nice thing about this approach is... relative simplicity (as if "general collision detection" is in any way compatible with "simplicity").

If I take this approach (rather than implement the techniques you mention), I should also try to make the engine better at figuring out which objects are concave and which aren't - when they are created. And I'll have to make sure objects can be only be deformed by calling my routines, so nothing can become concave without my engine knowing that might be happening.

Somewhere I read that decomposition is a slow algorithm that cannot execute in a fraction of a frame time. If that's true, then new objects cannot be created and introduced in a single frame (which I currently support, and want to support).

Which gets back to my original point... the complexity could get out of hand if I have too many parts in this collision detection system, each with nasty requirements (like not happening in a small fraction of 1 frame time) or other interactions.

I better sit down with this new information and some blank sheets of paper, and figure out which components can best fit and work together.

Thanks for the ideas.[/font]