Basic Primitive Tests - Real-Time Collision Detection - page 229

The last consideration is when P lies in a vertexVoronoi region. In this case, L must
additionally be intersected against all three capsules of radius r determined by the
edges coincident to the vertex. If L does not intersect one of the capsules, S does
not intersect B . Otherwise, the intersection of S with B occurs at the smallest time
t at which L intersects one of the edge capsules. As a potential speedup, L can be
tested against a sphere K of radius r centered at the vertex. If L intersects K , and
the intersection point lies in the vertex Voronoi region, then this intersection point
provides the answer and the capsules do not have to be tested against. However,
if the intersection point between L and K lies outside the vertex Voronoi region (or
if L does not intersect K at all), the sphere test was in vain and the three cylinders
must be intersected anyway. The following code fragment illustrates how to efficiently
determine which Voronoi region P is contained in and which edges must be tested
for the edge and vertex region cases.
int IntersectMovingSphereAABB(Sphere s, Vector d, AABB b, float &t)
{
// Compute the AABB resulting from expanding b by sphere radius r
AABBe=b;
e.min.x -= s.r; e.min.y -= s.r; e.min.z -= s.r;
e.max.x += s.r; e.max.y += s.r; e.max.z += s.r;
// Intersect ray against expanded AABB e. Exit with no intersection if ray
// misses e, else get intersection point p and time t as result
Point p;
if (!IntersectRayAABB(s.c, d, e, t, p) || t > 1.0f)
return 0;
// Compute which min and max faces of b the intersection point p lies
// outside of. Note, u and v cannot have the same bits set and
// they must have at least one bit set among them
intu=0,v=0;
if (p.x < b.min.x) u |= 1;
if (p.x > b.max.x) v |= 1;
if (p.y < b.min.y) u |= 2;
if (p.y > b.max.y) v |= 2;
if (p.z < b.min.z) u |= 4;
if (p.z > b.max.z) v |= 4;
// 'Or' all set bits together into a bit mask (note: hereu+v==u|v)
intm=u+v;
// Define line segment [c, c+d] specified by the sphere movement
Segment seg(s.c, s.c + d);