Reducing AABB-Brush sweep tests to Ray-Brush intersection

Post Reply
User avatar
Carsten
Posts: 14
Joined: Thu Sep 25, 2008 1:36 pm
Location: Germany
Contact:

Reducing AABB-Brush sweep tests to Ray-Brush intersection

Post by Carsten »

Dear folks,

I've been comparing several algorithms for continuous collision detection between convex objects, and I was wondering how the algorithm that is used in the "Quake (1/2/3)" engines fits in.

In a summary, the "Quake algorithm" traces AABBs along rays and determines collisions with brushes (convex polyhedra) by
  1. bloating the current brush, adding bevel planes where necessary, then
  2. tracing a ray against the bloated brush.
Step 1 is quasi the explicit computation of the Minkowski sum of the AABB and the brush, so that in step 2, the result of the ray test against the bloated brush is equivalent to tracing the AABB against the original (unbloated) brush.
The most difficult and least obvious part in this algorithm is how and where the compute the bevel planes, which however can be precomputed offline for AABBs.

I've been able to create my own implementation of this algorithm that works very fast and very stable, and I'm currently working on extending the concept so that instead of only AABBs, also arbitrary convex polyhedra can be traced against other convex polyhedra (the brushes). (Again, the only difficult problem is computing the proper bevel planes.)

Well, I was wondering under what name this algorithm is commonly known, and how it compares to GJK? :?:

I'm not (yet) very familiar with GJK, which seems to compute the Minkowski sum implicitly, whereas the above outlined algorithm computes it more explicitly.
I also have Christer Ericsons great book, and while it covers Minkowski sums and GJK, it doesn't seem to mention this "explicit" algorithm.

I'd be very grateful for any hints and tips about this algorithm, where I can find more information, and how it compares to GJK.
Thank you very much!! :-D
User avatar
Carsten
Posts: 14
Joined: Thu Sep 25, 2008 1:36 pm
Location: Germany
Contact:

Re: Reducing AABB-Brush sweep tests to Ray-Brush intersection

Post by Carsten »

Oh, I forgot to mention that the challenge is of course to compute the bevel planes dynamically, in real-time, for arbitrary and changing (that is, possibly different in each frame) trace objects.
Precomputing the explicit Minkowski sum ahead of time, e.g. by a convex hull algorithm for one fixed trace shape only, doesn't count. ;)
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Reducing AABB-Brush sweep tests to Ray-Brush intersection

Post by Erwin Coumans »

I've dealt with those issues before, and I recommend the implicit method, also known as conservative advancement (CA).

Explicit computation of the Minkowski sum is very expensive for complex convex shapes, so if you ignore rotation you can better precompute this. And then perform ray casts against the explicit Minkowski Sum (or bevel planes in quake lingo). Bullet implements the ray cast, convex sweep/cast and rotational continuous time of impact using implicit the Minkowski sum, and it requires very few iterations. For the non-rotational version, this has been excellently described by Gino van den Bergen in his Ray Casting against General Convex Objects with Application to Continuous Collision Detection. Other related papers are by Zhang/Lee/Kim, see http://graphics.ewha.ac.kr/CATCH and http://graphics.ewha.ac.kr/FAST/

Hope this helps,
Erwin
User avatar
Carsten
Posts: 14
Joined: Thu Sep 25, 2008 1:36 pm
Location: Germany
Contact:

Re: Reducing AABB-Brush sweep tests to Ray-Brush intersection

Post by Carsten »

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 :mrgreen:,
  • 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 :D )
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.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Reducing AABB-Brush sweep tests to Ray-Brush intersection

Post by Erwin Coumans »

(moved the topic, because it becomes too Bullet centric)
Carsten wrote: 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.
  • Can you help reproducing any of the problems, so we can fix them? Bullet should be able to deal with all those tasks (player control, volume triggers, ray tracing) reliably and fast.
  • Could you try exporting a sample scene that causes troubles using the Collada exporter?
  • Have you considered using a capsule or other smooth shape as character representation, instead of an AABB?
  • Do you consider contributing your explicit minkowski sum method, so we can compare results?
  • Have you checked out the latest btGhostShape? It should help with volume triggers etc.
  • What kind of acceleration structures and method do you use for ray-tracing?
Thanks,
Erwin
User avatar
Carsten
Posts: 14
Joined: Thu Sep 25, 2008 1:36 pm
Location: Germany
Contact:

Re: Reducing AABB-Brush sweep tests to Ray-Brush intersection

Post by Carsten »

Dear Erwin,
Erwin Coumans wrote:Can you help reproducing any of the problems, so we can fix them? Bullet should be able to deal with all those tasks (player control, volume triggers, ray tracing) reliably and fast.
I will do my best to help to get these problems fixed, but in general, I fear that we will not be able to isolate and fix all problems quickly due to the amount of code and data involved, so finding smallest-possible reproduction cases is sometimes not easy. Nonetheless, I'm positive that everything will eventually addressed while we get more familiarity and experience with Bullet.
  • Could you try exporting a sample scene that causes troubles using the Collada exporter?
Yes, but it would most likely be easier to produce a small code sample. Will make one asap, just give me a bit more time.
  • Have you considered using a capsule or other smooth shape as character representation, instead of an AABB?
Ah, sorry, not yet tried yet, will do so soon.
  • Do you consider contributing your explicit minkowski sum method, so we can compare results?
Yes, I'm happy to. I've almost finished it, and will post it here when done (will take another 2-3 weeks though, sorry).
  • Have you checked out the latest btGhostShape? It should help with volume triggers etc.
Oh, I never knew it existed - it doesn't seem to be mentioned at http://www.continuousphysics.com/Bullet ... index.html ?
  • What kind of acceleration structures and method do you use for ray-tracing?
Used to use a BSP tree with arbitrary subdivision planes (still use it for the graphics world / scene graph), but for the collision world (that also handles the ray-tracing queries), where no portal and PVS stuff is required, we now use a simpler BSP tree with axis-aligned planes only.

In summary, I'm sorry for not having anything more concrete at this time, but I will come back to each of the issues during our continued work with Bullet. :-)
Post Reply