Editor's Note: Any ? symbols found in this document are meant to be dot product operators

Introduction

Discrete collision detection (overlap test) can be fast and simpler to implement but it suffers from the tunneling effect wherein very thin or fast moving objects can move through each other without being detected.

Things become worse at low frame rates as objects displace a lot more between frames.

Continuous collision detection (CCD) doesn't suffer from the tunneling effect and no collisions are missed even when the frame rate is low. Furthermore, accurate collision detection data, such as point of contact, time of contact and normal of contact are readily available.

Paul Nettle, in his excellent article titled "General Collision Detection for Games Using Ellipsoids" provides details on implementation of CCD for Sphere against Triangle. At the end of his article, information is provided on how the sphere test could be extended to support Ellipsoids.

However, the implied statement that the normal to the surface of the ellipsoid passes through its center is incorrect. Hence the approach outlined therein for ellipsoidal collision is misleading and will provide inaccurate results.

In this article we look at extending the Sphere CCD algorithm described in Paul's article to the Ellipsoidal case. We will use a more accurate formulation for the ellipsoid surface normal.

It is assumed that the reader has basic understanding of vectors.

CCD for Ellipsoids

Let us consider our ellipsoid (E) to be a sphere of radius 'Rad' that is scaled by Sx, Sy, Sz along its local x, y and z axis respectively. We also constrain the scales to be such that Max(Sx,Sy,Sz) = 1.

E.g. rad = 100, (Sx, Sy, Sz) = (1, 0.5, 0.25)

Position and orientation of E is determined by:
Ctr : Center in world space.
TMRot : Orientation matrix.

Let the triangle be represented by a plane that it lies on {N, d} (N being the planes normal, and d its distance from the origin) and three vertices V1, V2 and V3.

We need to see if the Ellipsoid collides with the Triangle for a displacement .

Let dispN be magnitude of displacement along the plane normal.

Then . So if dispN is >= 0, there is no collision as the Ellipsoid would be moving away from the plane. The distance of the ellipsoid center from the plane is,

It is clear from the adjacent figure that collision will not occur if

This is an inexpensive check that will allow us to exit the collision detection routing early.

Next we need to find point on ellipsoid that is closest to the plane, viz. ClsPt . It's easier to solve this problem if the ellipsoid is axis aligned. Hence we transform the plane to the ellipsoids object space. The transformed plane is simply

Where
(See Appendix A for a formulation of point on Ellipsoid that is closest to a given Plane. Remember to transform the point back to world space.)

Now that we have the closest point, we will find its distance from the plane. This will be the Ellipsoid-Plane separation;

Let 't' be time defined over the ellipsoid displacement such that at t = 0, ellipsoid is displaced by 0, and at t = 1, ellipsoid is displaced by . Then time at which ellipsoid will touch the plane is given by,

If t > 1, clearly there is no collision!

The point at which the ellipsoid touches the plane is ClsPtPl (closest point on plane) and is given by:

If we were colliding with an infinite plane, our detection would stop here. However, since we are more interested in colliding with triangles, we need to do a few more checks.

First we check to see if ClsPtPl is inside the triangle. (See Appendix B for a Point in Triangle test algorithm). If it is, we are done as we already have all the collision data, i.e.

Time of contact t Point of contact ClsPtPl E's center at contact Contact Normal

If ClsPtPl is outside triangle, ellipsoid is probably going to collide with one of the 3 edges.

It's clear from the adjacent figure that the ellipsoid will collide with the edge (and point on edge) that is closest to ClsPtPl. Let us call this the contact point CtPt. (Please see Appendix C for a formulation of Distance between Point & Line Segment (along with closest point on line segment)).

Now we know that the ellipsoid would collide at CtPt. To get the time of contact, we shoot a ray from CtpT in direction - to collide with the ellipsoid.

For a Ray - Ellipsoid collision algorithm please see Appendix D.

The normal of contact is determined using this intersected point. The normal would simply be along the ellipsoid gradient at this point. The equation of the ellipsoid in its object space is
x2 / Sx2 + y2 / Sy2 + z2 / Sz2 = Rad2
The gradient is given by {2x/Sx2, 2y/Sy2, 2z/Sz2}. The 2's can be removed as we would be normalizing the vector.

Note: the intersection point needs to be transformed to ellipsoid's object space, the gradient is then computed and normalized. This normal is then transformed back to world space.

The collision data is then given by,

Time of contact t Point of contact CtPt E's center at contact Contact Normal gradient

Appendix A

Point on Ellipsoid closest to given Plane

As can be seen from the adjacent figure, the closest & furthest point on the ellipsoid from plane will be such that the ellipsoid's surface normal at this point will be parallel to the plane's normal.

The ellipsoid's surface normal will point along its gradient

Hence for closest & furthest points we would have

for some scaler k

or,

equation {1}

Substituting this in the equation of the ellipsoid gives us,

Or,

Substituting the two values for k in equation {1} will give us the closest and furthest points on the ellipsoid.

Appendix B

Point in Triangle Test

Given a triangle with three vertices V0, V1 & V2 we need to determine if point P lies inside the triangle.

Let E0 = V1 - V0 and E1 = V2 - V0 represent two edges of the triangle.

Any point P lying in the plane of the triangle can be represented by,

P = V0 + s0 * E0 + s1 * E1 for some scaler's s0 & s1.

This formulation uses the Barycentric coordinates, put simply: the parallelogram law (notice the parallelogram in the fig above).

Substituting Q = P - V0 in the above equation gives,

Q = s0 * E0 + s1 * E1

In this equation, we have two unknowns s0 & s1 (Q is known as P is the point that we are testing). To solve for two unknowns we need to have two equations.

Multiplying the above equation first by E0 and then E1 yields two equations that can be solved for the two unknowns.

Q ? E0 = s0 * E0 ? E0 + s1 * E1 ? E0

Q ? E1 = s0 * E0 ? E1 + s1 * E1 ? E1

Substituting
q0 = Q ? E0 q1 = Q b E1
e00 = E0 ? E0 e11 = E1 ? E1
e01 = E0 ? E1

gives,
q0 = s0 * e00 + s1 * e01 & q1 = s0 * e01 + s1 * e11

Let,
z0 = e11*q0 - e01*q1 z1 = e00*q1 - e01*q0
det = e00*e11 - e01*e01

Then,
s0 = z0 / det and s1 = z1 / det

P will be inside triangle if,
0 <= s0 <= 1
0 <= s1 <= 1 and
s0+s1 <= 1

or if,
0 <= z0 <= det
0 <= z1 <= det and
z0+z1 <= det

Appendix C

Distance between Point & Line Segment

Let a line segment be defined by two points P1 & P2. We need to determine the shortest distance 'dist' between an arbitrary point V and this line segment.

Direction along P1 to P2 is given by
Dir = Edge / len
Where Edge = P2 - P1 and len = magnitude of Edge

A point along the line segment is given by

P = P1 + s * Edge (equation {1})

where 0 <= s <= 1, for all other values of s, P lies outside the line segment.

Let VP1 = V - P1 and V'P1 = V' - P1

Length of V'P1 is given by V'P1 = VP1 ? Dir
Then V' is given by
V' = P1 + V'P1 * Dir where V'P1 is length of V'P1
Or,
V' = P1 + V'P1 * Edge / len (equation {2})

Comparing equations {1} & {2} we have,

s = V'P1 / len

If s < 0 then the closest point (ClsPt) is P1. If s > 1 the, closest point is P2.
For all other cases the closest point will be V'.

The closest distance is then
dist = || V - ClsPt ||

Appendix D

Ray Ellipsoid Intersection

By transforming the ray to the ellipsoidal space (where the ellipsoid becomes a sphere), the problem reduces to a ray sphere intersection check.

The equation of a sphere of radius r and centered at the origin is given by
x2 + y2 + z2 = r2
That is, a point P on the sphere satisfies the equation:

P ? P = r2 (equation {1})

Let the ray originate from O and travel along a displacement vector given by D.

Then a point along the ray is given by

P = O + t * D, where t is some scalar. (equation {2})

At the point of intersection both the equations are satisfied.

i.e. r2 = (O + t * D) ? (O + t * D)
or r2 = O ? O + t2 * D ? D + 2 t * O ? D
or D ? D * t2 + 2 O ? D * t + O ? O - r2 = 0

If we substitute
a = D ? D
b = 2 O ? D
c = O ? O - r2
we have a quadratic equation of the form at2 + bt + c = 0, whose solution is given by t = ( -b +/- Disc ) / 2a, where discriminant Disc = (b2 - 4ac)1/2

There are two possible solutions as a ray can intersect a sphere at two different places.

• If discriminant is zero, there is only one solution and the ray will be tangent to the sphere.
• If discriminant is -ve, there is no solution and the ray will not intersect the sphere.

Since we are interested in the closest intersection (smallest t) only,
t = ( -b - Disc ) / 2a

Note if t > 1, ray displacement D is not sufficient to intersect with the sphere.