Faster convex-convex SAT: internal objects
I noticed that I had a fairly low amount of posts in the “physics” category, for somebody working in physics & collision detection all day long. So let me try to increase the ratio a bit. Last time we talked about partial hulls, today I’ll present another optimization for the same problem.
The penetration depth between two convex polytopes can easily be computed using separating-axis tests. But the large number of edge-edge tests often makes this process very slow, and other algorithms such as EPA or Xenocollide are thus often chosen over SAT to compute the MTD between two convexes. There are however a large number of tricks to optimize the SAT version. One of the most efficient ones is to use simple “internal objects”, i.e. simple objects such as a sphere or a box embedded in the convex.
Recall that for each candidate axis we do something like:
bool testSepAxis(const btVector3& axis, const MyConvex& hull0, const MyConvex& hull1, float& dmin, Vector3& mtd)
{
// Project hull 0 on candidate axis
float Min0,Max0;
hull0.Project(axis, Min0, Max0);// Project hull 1 on candidate axis
float Min1,Max1;
hull1.Project(axis, Min1, Max1);// If the projected intervals don’t overlap, the candidate axis is a separating axis.
// In that case the hulls don’t overlap, we can early exit and return non penetration.
if(Max0<Min1 || Max1<Min0)
return false;// Else compute penetration depth (PD) = how much the intervals overlap
const float d0 = Max0 - Min1;
const float d1 = Max1 - Min0;
const float depth = d0<d1 ? d0:d1;// Then keep track of minimal PD. The axis for which the PD is minimal is the MTD.
if(d<dmin)
{
dmin = d;
mtd = axis;
}
return true;
}
So we’re looking for the minimal overlap, and the MTD is the axis for which the overlap is minimal. The idea, then, is to first project the simpler, internal objects on the candidate axis, and use the overlap results to skip the real hull projections if we can.
Say our internal objects are spheres (it could also be boxes, but for the sake of the argument let’s use spheres). Let hullOverlap(V) be the overlap value for the hulls on a given axis V, and sphereOverlap(V) be the one for the spheres on the same axis. Since spheres are embedded in the hulls, it should be clear that we always have:
hullOverlap(V) >= sphereOverlap(V) (1) (see Figure 1)
Now let minHullOverlap be our current best result, i.e. our current minimal penetration depth computed from real hull projections (not sphere projections). It should be obvious that thanks to (1) we have:
sphereOverlap(V) > minHullOverlap => hullOverlap(V) > minHullOverlap (2)
In other words, if sphereOverlap(V) is already bigger than our current best result, hullOverlap(V) will be bigger as well, and thus there is no need to compute it.
Figure 1
This is interesting since, of course, projecting a sphere is a lot faster than projecting a convex hull. Projecting a sphere is one dot product, projecting a hull is one dot product per vertex (plus, we don’t need to even access the vertex memory).
As Figure 1 shows, the embedded spheres don’t need to actually touch for this test to be useful - only the spheres’ projections on the candidate axis. In practice, this happens very often, and that single optimization sometimes culls away 90% of the actual hull projections. You can try out this demo for a proof-of-concept.
It is also a good idea to test the MTD from the previous frame first, to initialize minHullOverlap to a small value right from the start - discarding candidate axes as early as possible.
Finally a note about the internal shapes one should choose. A sphere might not be a great fit for long thin rods, in which case an embedded box might be better. But it might be easier to just use both, and at runtime choose whatever internal shape gives the best results. This is what I do in the above demo.
January 25th, 2011 at 9:15 am
I tend to find that 95% of convexes I see in my engine are boxes, cylinders from segments and wedges. The only examples I have of more complex polyhedra are those generated by out of control auto generation(which is something I have been meaning to remove from my levels)…
I would be very tempted to just decompose everything into tetra(and wedges + boxes as an optimization) and let the broad/mid phase deal with the culling. (this seems like the logical extension of your last post…)
I think this approach would also be the best way to approach doing RBs on GPUs as it avoids most of the divergant flow control, has a fixed size for each primitive type and increases the amount of parallel work.
January 27th, 2011 at 1:14 am
Well people use more complex convexes in a lot of different places, for example to approximate the shape of a car in a racing game, or around ragdoll bones, etc. John’s old decomposer also approximates arbitrary meshes with several convexes, and these can have a fair amount of vertices. So we need to optimize the worst case anyway.
January 27th, 2011 at 7:10 am
I hope you guys release a GPU rigid body system soon, and also some details about how well it works and how you adapt such things to work within the constraints of the GPU(maybe just using software for some things, like big convexes).
Just using collections of connected spheres seems a bit lame… (as in Batman:-) and I only found one brief mention and no analysis in a slide.
I am tempted to to experiment my self with something in OpenCL, but I have more practical useful things to do(from my perspective anyway).