Generic Collision Detection for Games Using Ellipsoids

with the three vectors a, b, c you can take the parametrization

x(phi,theta) = a*sin(theta)*cos(phi) + b*sin(theta)*sin(phi) + c*cos(theta)

then calculate the tangent vectors in theta and phi direction

dx/dphi = -a*sin(theta)*sin(phi) + b*sin(theta)*cos(phi)

dx/dtheta = a*cos(theta)*cos(phi) + b*cos(theta)*sin(phi) - c*sin(theta)

get the normal by cross - product

n(phi,theta) = dx/dphi x dx/dtheta

and create an equation which states that n and the plane normal are parallel

n(phi,theta) = c*nplane

now you''ve got 3 equations and 3 unknowns - solve them (you''ll get two solutions, should be easy to find out which of them is the one you need by e.g. comparing distances or doing a dot product radius vector - normal) and plug phi and theta back into the original equation to get the point where the plane would touch the ellipsoid.

yep, that''s what they do.

as far as orientation goes, it does not matter for triangles, you can use oriented ellipsoids. But for boxes, and other oriented ellipsoids, you''ll be in trouble.

Also, you''ll have to re-normalise the triangle normal, or if you can find ways to avoid the normalisation. That also means that it would be as fast not to store the triangle normal, you just recompute the normal once you transform the triangle. So you save a transform, but you do a normal calculation.

to build an orientation matrix from your 3 vectors, simply load the matrix with the vectors, like

Matrix Orientation;
Orientation.SetColumn(0, Dir[0]);
Orientation.SetColumn(1, Dir[1]);
Orientation.SetColumn(2, Dir[2]);

or

Matrix Orientation;
Orientation.SetRow(0, Dir[0]);
Orientation.SetRow(1, Dir[1]);
Orientation.SetRow(2, Dir[2]);


one or the other, depending on how your matrices are organised (I would think you''d have to load columns).

to build the inverse matrix, which you need to apply the first transform on the triangle vertices, you ''transpose'' the matrix.

or, to put it simply, if you loaded columns in your orientation matrix, you load rows in your transposed matrix, and vice versa.


or, if you are using DirectX''s D3DX utilities, you can use 4x4 D3D matrices to build a single transform matrix for your ellipsoid, and its inverse.

That should work,

here''s what I think it would look like

struct CEllipsoid{    Vector Dir[3];    Vector Pos;    Vector Size;    Matrix Orient;    Matrix Trans;    Vector InvSize;};struct CTriangle{    Vector V[3];};bool CEllipsoid::Update(const Matrix& Rotation){    Dir[0] *= Rotation;    Dir[1] *= Rotation;    Dir[2] *= Rotation;    Orient.SetColumn(0, Dir[0]);    Orient.SetColumn(1, Dir[1]);    Orient.SetColumn(2, Dir[2]);    Trans.SetRow(0, Dir[0]);    Trans.SetRow(1, Dir[1]);    Trans.SetRow(2, Dir[2]);}bool CEllipsoid::Collide(const CTriangle& Tri, Vector& P0, Vector& P1) const{    CTriangle T = Tri;    //-----------------------------------------------    // Transform vertices in ellipsoid space (use 4x4 transpose matrix instead)    //-----------------------------------------------    for(int i = 0; i < 3; i ++)    {        T.V[i]   += (-Pos);        T.V[i]   *= Trans;        T.V[i].Scale(InvSize);    }        //-----------------------------------------------    // Do a unit sphere against triangle collision    //-----------------------------------------------    CSphere Sphere(Vector(0, 0, 0), 1);    if (!Sphere.Collide(T, P0, P1))        return false;       //-----------------------------------------------    // convert collision info into world space (use 4x4 orientation matrix instead)    //-----------------------------------------------    P0.Scale(Size);    P0 *= Orient;    P0 += Pos;      P1.Scale(Size);    P1 *= Orient;    P1 += Pos;        return true;}

although for the update, I''d prefer doing it the other way round

bool CEllipsoid::Update(const Matrix& Rotation){    Orient *= Rotation;    Trans   = Orient.Transpose();        Dir[0] = Orient.GetColumn(0);    Dir[1] = Orient.GetColumn(1);    Dir[2] = Orient.GetColumn(2);}

I think it look better like that