Hi Erwin,
thank you very much for your reply and the links to the great papers!
I've finished my implementation using explicit Minkowski difference in the meanwhile. As you mentioned, the disadvantages are
- scary O(...) asymptotic complexity, and
- very difficult for "rotational sweeps" (the two objects can be arbitrarily rotated, but the sweep must be along a straight vector).
Fortunately we don't need rotational sweeps, so I didn't even consider them.
About the complexity/performance: There are indeed several loops that indicate an essentially squared behavior, for the worst case something like O(p_1*v_2 + e_1*e_2*(v_1+v_2)), where
p_i is the number of planes of object i, v_i is the number of vertices of object i, and e_i is the number of edges of object i.
Good news though is that all the inner loops are very cheap (usually hardly more than a dot product), and there are many(!) "early-outs".
I've not yet finished performance profiling and optimization (in fact my current implementation is still quite conservative), but first tests indicate surprisingly good performance, at least in my typical application scenario: The objects are not overly complex (at 95% just simple boxes, pyramids, wedges, triangles, etc.), the broadphase is effective, etc.
Moreover, I'm considering caching the computed bevel planes (Minkowski difference) for e.g. the last 1000 pairs of objects, based on their geometry, for reuse in subsequent frames. This wouldn't help with the worst case of course, but considerably speed up the average case, as it eliminates most of the terms in the O(...) complexity.
The advantages of the method are:
- it is geometrically very intuitive and thus easy to understand
,
- very stable: both termination and numerical accuracy are predictable,
- can easily be implemented so that interpenetration does never occur,
- requires little knowledge about the geometric topology of the objects,
- still very fast
To conclude, in general, I'm quite happy with the results, although the implicit method also continues to intrigue me so that I'll likely try it in parallel later.
So why do I bother, rather than just employ the means of Bullet?
Well, I'm currently integrating Bullet with our
Ca3D-Engine, and we're very happy with the results. (We've considered PhysX before, but Bullet is utterly the best
)
The only problem we have is with player movement / character controller, where the requirements are very high:
- The player must never get stuck in solid,
- never fall through the ground or walk through walls,
- never penetrate solids (the viewpoint should never jitter),
- sliding along walls that are made of multiple solids ("bricks") must feel like a wall made from one big solid, and
- the result must usually be bit-wise reproducible as we employ client-server network architecture that employs player prediction for lag compensation.
As a result, we're currently considering running two simulation worlds in parallel: The one in Bullet, where we do everything but the players, and our own, where we just do the player, inclusive trigger volume handling and entirely different tasks, e.g. ray-tracing for our Radiosity implementation etc.
