# Ellipsoid Circumference Testing

## Recommended Posts

FlyHigh    122
Hi people on gamedev, I really need help sorting out the 3d math part of my project and google seems unhelpful recently. I need to test if a triangle intersects a non axis-aligned ellipsiod, I don't need to know if the triangle is completely emcompassed or completely separate, only if it intersects and at what point on the triangle it intersects. The ellipsoid class I am using is below, but if it helps to represent it differently I am open to suggestion.
class Ellipsiod
{
public:
vector3 Centre;
vector3 Rotation;
};

I am basically looking for an: int Intersects(const Ellipsoid &Ell, const TriangleList &Tri, PointList &out) At this moment the speed of the program is the least of my concerns only that I can prove it works, I'll sub-divide the triangleList into a oct-tree once everything is working nicely If anybody has any code they would like to share I would be really thankful, although tips / advice /links are what I'm looking for at the moment. Thanks in advance.

##### Share on other sites
jyk    2094
The short answer is that the test is most easily performed in 'ellipsoid space', where the ellipsoid is a unit sphere. For a good description of 'ellipsoid space' see Kasper Fauerby's article (although the link seems to be down at the moment), or ask here if you need more info.

That leaves you with a triangle-sphere test, which (I think) is best accomplished by finding the point on the triangle closest to the sphere center and performing a squared distance test. Useful contact info can be derived from this as well if you need it.

You may have to clarify what you mean by the 'point of intersection' between a triangle and an ellipsoid. Do you mean where the edges intersect the ellipsoid? In any case, the actual intersection is liable to be an irregular shape that would not be particularly useful nor easy to compute.

##### Share on other sites
FlyHigh    122
'Ellisoid space' I never even knew such a helpful technique existed, that makes everything much more clearer. I can do sphere/triangle tests and its easier to google as well.

Thanks a lot I been pulling my hair out for so long because of this I never thought to resize everything else to make it a sphere test.

I see what you mean about the point of intersection now, I wasn't visualising it properly. What I wanted instead are a list points which the triangle intersect the ellipsoid, I don't want the shape just enough points that intersect to carry on a simulation.

##### Share on other sites
FlyHigh    122
Oks just have a few questions that I would like to get out the way before starting this;

1/ To translate a triangle into 'eSpace' do I just multiply all of points x,y,z vector by the scaling factor needed to reduce the ellipsoid into a sphere?

2/ Because the ellipsoid isn't axis-aligned I have to rotate all the triangles points as well don't I? (is this before or after scaling?)

3/ How would you recommend I collect information on the points that intersect? Is there a way of finding out the ellipse (or circle or arc) that was created by the intersection and just storing a few of those points.

Any help appreciated, if you need more background info I'll post it.

Thanks.

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by FlyHigh1/ To translate a triangle into 'eSpace' do I just multiply all of points x,y,z vector by the scaling factor needed to reduce the ellipsoid into a sphere?

Not sure what you mean here. you have 3 radii for the ellipsoid, one for x, one for y and one for z, what you do is given each point p of a triangle, divide each of its components by the equivalent radius r, IE:

p'.x = p.x/r.x
p'.y = p.x/r.y
p'.z = p.x/r.z

Quote:
 Original post by FlyHigh2/ Because the ellipsoid isn't axis-aligned I have to rotate all the triangles points as well don't I? (is this before or after scaling?)

Yes, you do, not only that, but must also move the ellipsoid to the origin because the world MUST be rotated around the ellipsoid origin, so the steps are:

1 - Translate the ellipsoid to the origin (substract the position of the ellipsoid from the current triangle you're testing against)

2 - Rotate triangle points

3 - Transform triangle to Ellipsoid Space

4 - Test the transformned triangle against a unit radius sphere located at the origin.

5 - you're done if all you want is test, if you need points of collision you will have to calculate them on the sphere and then roll back the operations to get them back into normal Space.

Quote:
 Original post by FlyHigh3/ How would you recommend I collect information on the points that intersect? Is there a way of finding out the ellipse (or circle or arc) that was created by the intersection and just storing a few of those points.

Not sure here, in theory once you find the points on the unit sphere, you would have to multiply the point againts the radii, then rotate in the oposite direction that you did earlier, and finally add the position of the ellipse, rolling back all the operations you performed to get to ellipsoid space.

##### Share on other sites
FlyHigh    122
Thanks for your help, I get the order of things now. Just the last step i'm stuck on now. (ie. the final most important step)

You say 'once you found the points' I think I missed a step, is there an algorithm which given a triangle and a sphere returns enough data to represent the infinite number of points? I can probably get a suitable subset of points given the infinite set but don't understand how I can get that much data from an intersection test.

Do you mean that if I find the point on the triangle which is nearest the origin (and is less than radius) then taking the three corners' distance from the origin I can work out if its an arc (1 point inside) an circle / ellipse (0 points inside). And then work from there yeah?

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by FlyHighYou say 'once you found the points' I think I missed a step, is there an algorithm which given a triangle and a sphere returns enough data to represent the infinite number of points? I can probably get a suitable subset of points given the infinite set but don't understand how I can get that much data from an intersection test.

Hmmm, well, in theory, you could use a set of functions (the sphere function, the plane function, and line function) in order to determine wether or not a point resides on the union of the 2 shapes, I think perhaps researching on 3d boolean operations would help, but I really dont know.

What you usually look for though, is a collision normal and a penetration depth, the normal (a unit vector) being the direction on which to move the sphere or triangle in order to separate them and the penetration depth (a single scalar), which is the magnitude you must move either object in the direction of the normal to make them disjoint (but barelly touching).

Although there could be many normal-pd pairs that do the job, you usually look for the one having the smallest absolute penetration depth.

Quote:
 Original post by FlyHighDo you mean that if I find the point on the triangle which is nearest the origin (and is less than radius) then taking the three corners' distance from the origin I can work out if its an arc (1 point inside) an circle / ellipse (0 points inside). And then work from there yeah?

I think what you want is to look for baricentric coordinates and Voronoi regions, find the closest feature to the origin (point,edge,face), which is given by which Voronoi region of the triangle the origin is in, and take it from there, if its a point, the point is the closest point, if its an edge, the closest point will be a point in the edge, if its facing the triangle, the closest point would be the closest point to the origin from the triangle plane.

Cheers!