• 10/25/07 10:43 PM
    Sign in to follow this  
    Followers 0

    Continuous Collision Detection for translating Ellipsoid

    General and Gameplay Programming

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


    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

    (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

    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


    equation {1}

    Substituting this in the equation of the ellipsoid gives us,


    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

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

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

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

    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
    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.


    Sign in to follow this  
    Followers 0

    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.