Archived

This topic is now archived and is closed to further replies.

code_evo

problems with oriented ellipsoid vs poly collision

Recommended Posts

code_evo    146
Anyone have a good article I can visit? I have sphere vs poly working I have an ellipsoid bounding volume around my object. I know the 3 vectors (world coords) which define the shape of the ellipsoid (ex. in 2D x,y | | Object-------x,y these rotate around with the Object I'm not sure where to go from here. Basically, I know my polygon (plane) normal, I need to get the radius vector of my elipsoid in the direction of the plane normal. This cant be that hard, but I cant crack the case. Thanks, /jeff [edited by - code_evo on January 24, 2004 8:09:28 PM]

Share this post


Link to post
Share on other sites
ga    126
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.

Share this post


Link to post
Share on other sites
code_evo    146

ga, thanks for those equations, but they confuse a bit too much, I cannot visualize what you are trying to do (I''m not the best mathematician in the world )

olii, that link you gave me, let me get it straight. they are taking the ellipsoid, transforming it into a unit sphere using the radius vector, then applying that same transformation to the colliding polygon, calculating, then transforming the intersection point back to ellipsoid space?

how much would rotations effect this? I suppose if I had a proper transformation/rotation matrix for the ellipsoid I could use this for both, but I''m not sure how I would generate this matrice. Guess I''ll read up on matrices, its been a couple years since I''ve had to use them.

Share this post


Link to post
Share on other sites
oliii    2196
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.

Share this post


Link to post
Share on other sites
code_evo    146
Okay thanks a lot.

As I might have said before, I'm not great at math so one more question. The ellipsoid is rotated, and translated (currently a matrix stores this information)
If I fill a new matrix with the orientation vectors of the ellipsoid, and apply that to the triangle (or the transpose i suppose), Do I need to worry about rotations? or will doing the above transform the vertices into ellipsoid space?

After they are in the same space, I suppose I transform both to unit sphere space correct?

I'll give this collision technique a go in the next week or two. So I might be back.

Thanks for all the help.

[edited by - code_evo on January 26, 2004 1:59:50 AM]

[edited by - code_evo on January 26, 2004 2:03:58 AM]

Share this post


Link to post
Share on other sites
oliii    2196
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

Share this post


Link to post
Share on other sites