Hi, I've been researching convex/concave collision algorithms and am looking for some direction. When it comes to convex/convex, things are pretty easy to research (practically any Google search will return you GJK!), but I'm not entirely sure the optimal path for collisions between convex and arbitrary concave objects. Note for my purposes, I would be using a triangle mesh to describe the concave objects. From what I've seen online there are two options:

• a) Run Convex/Triangle intersection test against your convex object and every triangle in the mesh (making sure to respect the normal direction of the triangle). This can be optimized by precomputing the triangle mesh into a Bounding Volume Hierarchy, like a BSP Tree or Octree.
• b) Decompose the triangle mesh into a set of convex objects.

These kind of feel the same to me at a high level, since if you partition the space in A you're basically just decomposing your mesh into smaller objects anyways? The difference I see is that the object at the lowest level of the tree in B is much more efficient to test against, since it's just a single convex hull as opposed to a bunch of triangles in A. However, I'm guessing that building correct convex hulls that properly wrap the mesh could be more difficult to implement than A.

My use case is primarily for (ellipsoid or capsule) character collision (and other convex game objects) with world meshes. I'm leaning towards A for it's simplicity, but I wanted to get some input on possible options beforehand. As well, if A is a good option, is a BSP Tree the best way to go based on my use case?

Any input is appreciated, thanks very much.

Erik

I use a) with a BVH as acceleration structure. b) is really a good option that I haven't yet found time to implement. It solves a couple of problems though. You can handle a bunch of triangles in one GJK pass. Note there is no need to build the a hull for these subsets explicitly. GJK operates only on vertices and conceptually convexifies on the fly. This also eliminates potential problems with internal edge collisions.

Note that GJK is an algorithm to compute the distance between *disjoint* convex shapes. Once you are overlapping you need another algorithm (e.g. SAT, EPA, MPR, ...) as fallback. For ellipsoids GJK can become numerically quite challenging in 32bit floating point precision. I support only sphere, capsules, hulls and triangles. Spheres and capsules are handled as points or segments and the radius is added afterwards to avoid precision problems. Gino has could coverage on these issues in his book.

All together this is a decent analysis. The devil will be in the detail and the implementation. Debugging the issues can become quite challenging.

You could use a library for convex decomposition, like this: http://kmamou.blogspot.co.at/2011/10/hacd-hierarchical-approximate-convex.html

There's also a library from John Ratcliff mentioned at the page.

Newton Physics engine also has it.

Anyone knows another one...?

One advantage of convex decomposition (beside performance) is that you have a definition of empty or solid volume, probably leading to more robustness.

For triangle soup like a) that's not possible, so i would not dare to try a) for dynamic objects. (But i'm no expert here)

This can be optimized by precomputing the triangle mesh into a Bounding Volume Hierarchy, like a BSP Tree or Octree

I would choose BVH.

BSP is very slow to build, increases triangle count and may introduce additional numerical issues and contacts due to splits - just no.

Octree is fine but i don't see advantages over less restricted BVH.

Oriented bounding boxes could be a big win if your world is not totally axis aligned.

I use a) with a BVH as acceleration structure. b) is really a good option that I haven't yet found time to implement. It solves a couple of problems though. You can handle a bunch of triangles in one GJK pass. Note there is no need to build the a hull for these subsets explicitly. GJK operates only on vertices and conceptually convexifies on the fly. This also eliminates potential problems with internal edge collisions.

You're right of course! I always forget to remember that, which is especially important in this case.

This can be optimized by precomputing the triangle mesh into a Bounding Volume Hierarchy, like a BSP Tree or Octree

I would choose BVH.

BSP is very slow to build, increases triangle count and may introduce additional numerical issues and contacts due to splits - just no.

Octree is fine but i don't see advantages over less restricted BVH.

Oriented bounding boxes could be a big win if your world is not totally axis aligned.

I'm assuming then a for a triangle mesh BVH the volumes would overlap? Take the image below:

(Pretend those are AABB!) It wouldn't be possible to partition this with AABBs without the BBs overlapping, unless you add triangles to both boxes (like in a BSP). If this is correct, I'm guessing if your object intersects both bounding volumes you'd then have to test both sides of the tree (please correct me if I'm wrong).

Thanks to both of you for your replies!