If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource |
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 "http://images.gamedev.net/features/programming/ellipsoid-ccd/eq7.png">. 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 - "http://images.gamedev.net/features/programming/ellipsoid-ccd/eq7.png"> 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
x^{2} / Sx^{2} + y^{2} / Sy^{2} + z^{2} / Sz^{2} = Rad^{2}
The gradient is given by {2x/Sx^{2}, 2y/Sy^{2}, 2z/Sz^{2}}. 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
Let the ellipsoid be defined by, |
Let the plane be defined by, |
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 P_{1} & P_{2}. We need to determine the shortest distance ‘dist’ between an arbitrary point V and
this line segment.
Direction along P_{1} to P_{2} is given by
Dir = Edge / len
Where Edge = P_{2} - P_{1} and len = magnitude of Edge
A point along the line segment is given by
P = P_{1} + s * Edge (equation {1})
where 0 ≤ s ≤ 1, for all other values of s, P lies outside the line segment.
Let VP_{1} = V - P_{1} and V’P_{1} = V’ - P_{1}
Length of V’P_{1} is given by V’P_{1} = VP_{1} ⋅ Dir
Then V’ is given by
V’ = P_{1} + V’P_{1} * Dir where V’P_{1} is length of V’P_{1}
Or,
V’ = P_{1} + V’P_{1} * Edge / len (equation {2})
Comparing equations {1} & {2} we have,
s = V’P_{1} / len
If s < 0 then the closest point (ClsPt) is P_{1}. If s > 1 the, closest point is P_{2}.
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
x^{2} + y^{2} + z^{2} = r^{2}
That is, a point P on the sphere satisfies the equation:
P ⋅ P = r^{2} (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. r^{2} = (O + t * D) ⋅ (O + t * D)
or r^{2} = O ⋅ O + t^{2} * D ⋅ D + 2 t * O ⋅ D
or D ⋅ D * t^{2} + 2 O ⋅ D * t + O ⋅ O - r^{2} = 0
If we substitute
a = D ⋅ D
b = 2 O ⋅ D
c = O ⋅ O - r^{2}
we have a quadratic equation of the form at^{2} + bt + c = 0, whose solution is given by t = ( -b +/- Disc ) / 2a, where discriminant Disc = (b^{2} – 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.
t = ( -b - Disc ) / 2a
Note if t > 1, ray displacement D is not sufficient to intersect with the sphere.