Jump to content
  • Advertisement

Archived

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

TolTol

Urgent help needed with ellipsoids

This topic is 5191 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello there, I need to know how to find out whether a 3D point is inside an ellipsoid located at the origin. Although the ellipsoid is centred at the origin, it is not aligned with any axis. For the ellipsoid I have the following: 1) a vector representing the major axis; 2) the size of the ellipsoid, A, B, C (which are half the lengths in each dimension). Any help or suggestions would be appreciated. Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
quote:
Original post by TolTol
For the ellipsoid I have the
following:

1) a vector representing the major axis;
2) the size of the ellipsoid, A, B, C (which are half the lengths in each dimension).



well there is an inifinite set of ellipsoids with this data...

Share this post


Link to post
Share on other sites
Sorry,

The above is data which I store. When needed I get a vector coming out the side of the ellipsoid by getting the cross product between the major axis and a vertical axis. And then another vector coming out the top of the ellipsoid by getting the cross product between the major axis and the vector coming out the side.

In other words I have three vectors representing each axis.

Any ideas?

Share this post


Link to post
Share on other sites
You just need to work out the scaling that you would need to apply to the ellipsoid in order to turn it into a unit sphere (i.e. 1/A in the first ellipsoid axis direction etc). Apply that 3D scaling to your point. Then see if the point lies within the unit sphere.

Share this post


Link to post
Share on other sites
Okay, let me get this straight:

If the ellipsoid was aligned with the X, Y, Z axis, I would just have to do the following:

Point.x = Point.x * (1/ellipsoid.A)
Point.y = Point.y * (1/ellipsoid.B)
Point.z = Point.z * (1/ellipsoid.C)

and then check if the point was within a distance of 1 from the origin. Is that correct?

If that is correct then how do take the ellipsoid not being aligned with the axis into account when scaling the point?

Again any help would be muchly appreciated.

Share this post


Link to post
Share on other sites
you can think of your ellipsoid as the following series of transformations:

Ellipsoid = Rotation_XYZ * Scaling_XYZ * UnitSphere

so UnitSphere = Scaling_XYZ.inverse * Rotation_XYZ.inverse * Ellipsoid.

So when you talk about generating those three axes, by taking cross products and what-not that''s really just defining a local coordinate system for your ellisoid scaled along its own XYZ axes. Since it''s a rotation, it''s orthonormal, the inverse is just the transpose. You can create this rotation inverse by taking a 3x3 matrix with the X axis as the top row, Y as the middle, and Z as the bottom. The scaling inverse is represented by a 3x3 matrix with 1/scale_x in the 0,0 entry, 1/scale_y at 1,1 and 1/scale_z at 2,2, and zeroes everywhere else. So, you build those two matrices and your final equation is:

Point_To_Test = Scale_Inverse * Rotation_Inverse * 3d_Point;

and if Point_To_Test is inside the unit sphere, then your 3d point is inside the ellipsoid.

Share this post


Link to post
Share on other sites
Thanks for your reply. It works except for the rotation inverse does nothing.

I have:

rotation_inverse(0,0) = ellipsoid->major.x;
rotation_inverse(0,1) = ellipsoid->major.y;
rotation_inverse(0,2) = ellipsoid->major.z;
rotation_inverse(1,0) = up.x;
rotation_inverse(1,1) = up.y;
rotation_inverse(1,2) = up.z;
rotation_inverse(2,0) = out.x;
rotation_inverse(2,1) = out.y;
rotation_inverse(2,2) = out.z;

Is this correct?

Share this post


Link to post
Share on other sites
if major/up/out are all perpendicular to each other and of unit length, you need the transpose of the matrix (equivalent to an inverse in that case), not the matrix itself.


// point to test

Vector P;

// the ellipsoid parameter

Matrix orientation(ellipsoid->major, up, out); // that''s your matrix

Vector scale(ellipsoid.A, ellipsoid.B, ellipsoid.C);
Vector pos(ellipsoid.position.x, ellipsoid.position.y, ellipsoid.position.z);

// to scale from ellipsoid to unit sphere

Matrix orientation_inverse(orientation.Transpose());
Vector scale_inverse(1.0f / scale.x, 1.0f / scale.y, 1.0f / scale.z);
Vector trans(-ellipsoid.position.x, -ellipsoid.position.y, -ellipsoid.position.z);


// point in unit sphere coord. system

Vector Q;
Q = P - trans;
Q = Q * orientation_inverse;
Q.x *= scale_inverse.x;
Q.y *= scale_inverse.y;
Q.z *= scale_inverse.z;

// true if transformed point in unit sphere

return (Q * Q < 1.0f);

Share this post


Link to post
Share on other sites
Sorry I was wrong, it does work. Just needed to perform the rotation first. Sorry about that.

I still have one more problem with ellipsoids:

If I have:

- a cluster of 3D points;
- a point representing the centre of a ellipsoid;
- three vectors representing the three axes of the ellipsoid.

How do I determine the A,B & C dimensions of the ellipsoid so that the ellipsoid encapsulates the points?

I have spent the last week searching the net for a solution but to no success.

Thanks again for all the previous replies and any future ones.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!