Tuesday, March 30, 2010

Thoughts on shape casting

I implemented a different type of shape casting yesterday. The most common way, to my knowledge at least, is to do it with conservative advancement:

1) Run the GJK algorithm to find closest point to the origin in configuration space
2) Use the distance and angle to compute a safe estimate to move (cast) the configuration space object towards the origin, in the cast direction.
3) Repeat until below a certain threshold, or the direction to the origin is pointing away from the cast direction (in which case it is a miss).

Even though this is an iterative method, relying of GJK, which in itself is iterative, this is actually pretty fast, because it converges quickly, like two or three iterations and you can benefit from warmstarting GJK with the simplex from the previous iteration.

However, there is a completely different method, which I thought I came up with, but after googling it for a while it seems Jay Stelly has mentioned similar methods before across the Bullet and MollyRocket forums. The method uses MPR on a swept CSO. The idea is to sweep the CSO in the direction of the cast far enough to enclose the origin, and then raycast from the origin to find the distance to the surface.

1) Construct the swept CSO. This may sound complicated, but since support functions are additive it's as easy as adding a vector to the existing support function. The resulting shape will be a swept version of the original CSO. The direction of the vector should be the sweep direction, and the length should be "long enough" to pass the origin. As showed later on, the distance here doesn't really matter much, so just keep it reasonable to avoid numerical issues. I use the distance from the geometric center of the CSO to the origin.

2) Use MPR, or XenoCollide, to find the distance from the origin to the surface of the swept CSO, in the sweep direction. If the origin is not inside the CSO, we know there is a miss.

3) Subtract the distance found in step 2) from the distance computed in step 1).

4) That's it! The difference in step 3 is the final sweep distance. Imagine a line going from the original CSO through the origin to the point computed using MPR in step 2). The line will have the same direction as the sweep and the origin will divide it into two parts, the first part, from the original CSO to the origin, and the second part from the origin to the surface of the swept CSO. You know the total length of the line (determined in step 1) and you know the length of the second part of the line (computed in step 3), so therefore the first part must be the difference. I know, I know, a picture would be ideal, but I'm lazy. Bug me about it and I might post one :)

Although I haven't done any side-by-side comparisons yet, it seems to me much more efficient to do this second approach, since it is much simpler, less prone to numerical precision issues and (yet to be proved) faster. So if this is a known method, how come everybody is still talking about conservative advancement?


I quickly profiled the new method against the old one (conservative advancement). Each session is 10 000 sweep queries with different angles, computing closest points, sweep distance and contact normal.

Box - Box (old)
Min 10 ms
Avg 16 ms
Max 30 ms

Box - Box (new)
Min 11 ms
Avg 14 ms
Max 16 ms

Cylinder - Cylinder (old)
Min 14 ms
Avg 40 ms
Max 99 ms

Cylinder - Cylinder (new)
Min 20 ms
Avg 35 ms
Max 53 ms

Polyhedron - Polyhedron 128 verts (old)
Min 99 ms
Avg 130 ms
Max 252 ms

Polyhedron - Polyhedron 128 verts (new)
Min 98 ms
Avg 130 ms
Max 185 ms

It turns out that conservative advancement is slightly faster in best case, slightly slower on average, but much slower in worst case, which makes sense, since it is doubly iterative. I have not noticed any differences in robustness so far, but I haven't stressed it either.


  1. You can merge the two loops (conservative advancement and gjk) into a single one. Did you try that? One of the Bullet casters implements this.

  2. I didn't try it, but I was under the impression that you couldn't get closest point information with that method since the CSO is deforming and the simplex may no longer represent points on the surface. I can very well have misunderstood the method though? Thanks for the tip anyway, I might have a look at the bullet implementation!