Jump to content
  • Advertisement
Sign in to follow this  
fig

Sphere and Cylinder vs Ellipsoid problem

This topic is 4419 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

I managed to come up with an Ellipsoid vs Ellipsoid intersection test that seems to work perfectly. But when one of the ellipsoids has the same radius on all axis (ie. a sphere) it doesn't work correctly. Is a sphere not just an ellipsoid like I described? The effect I get is like testing a sphere against 2 other spheres one on top of the other, kinda like a figure 8. I have the same problem with Cylinders. My Cylinder/Sphere test works fine, but I'm not sure how to transform the cylinder into ellipsoid space. Any pointers would be appreciated..
function ellipsoidVellipsoid(pos1, pos2: TAffinevector; r1, r2: TAffinevector): single;
var
    dir: TAffinevector;
    ar1, ar2: single;
begin
    pos1 := vectordivide(pos1, r1);
    pos2 := vectordivide(pos2, r1);
    r2 := vectordivide(r2, r1);
    r1 := affinevectormake(1, 1, 1);

    dir := vectornormalize(vectorsubtract(pos2, pos1));
    ar1 := Sqrt(sqr(r1[0] * dir[0]) +
        sqr(r1[1] * dir[1]) +
        sqr(r1[2] * dir[2]));
    ar2 := Sqrt(sqr(r2[0] * dir[0]) +
        sqr(r2[1] * dir[1]) +
        sqr(r2[2] * dir[2]));

    result := SphereVSphere(pos1, pos2, ar1, ar2);
end;
ps. Sorry about the cross post, I didn't realise the post I was reading at the time was on a different forum :)

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by fig
function ellipsoidVellipsoid(pos1, pos2: TAffinevector; r1, r2: TAffinevector): single;
var
dir: TAffinevector;
ar1, ar2: single;
begin
pos1 := vectordivide(pos1, r1);
pos2 := vectordivide(pos2, r1);
r2 := vectordivide(r2, r1);
r1 := affinevectormake(1, 1, 1);

dir := vectornormalize(vectorsubtract(pos2, pos1));
ar1 := Sqrt(sqr(r1[0] * dir[0]) +
sqr(r1[1] * dir[1]) +
sqr(r1[2] * dir[2]));
ar2 := Sqrt(sqr(r2[0] * dir[0]) +
sqr(r2[1] * dir[1]) +
sqr(r2[2] * dir[2]));

result := SphereVSphere(pos1, pos2, ar1, ar2);
end;
Just curious, are you absolutely sure that the above test works, even in most cases? Have you tested it rigorously? I can't say this with absolute certainty, but I suspect the test is not correct; distance and intersection tests involving pairs of ellipses or ellipsoids are not trivial.

Share this post


Link to post
Share on other sites
Yeah I doubt that would work on anything other than the cases where a) both ellipsoids are axis aligned (no rotations) and b) both ellipsoids have the exact same radii.

Share this post


Link to post
Share on other sites
In my tests, if the ellipsoids are taller than they are wide, there's no visible gaps or overlap all the way round. If I make one of them wider, the problem starts to show. The problem areas are, if there was a bounding box, where the corners would be. I took 3 screen shots at a problem area..

Image Hosted by ImageShack.us

Share this post


Link to post
Share on other sites
Here's a little exe demo showing that it does kinda work..

http://www.upload2.net/download2/bxeTUb4CXjxWI51/Base.rar.html

I couldn't really find any info on the subject so most of it is based on trial and error. And of course, my math skills aren't all that great :) I'm trying to build up an easy to use library of collision routines that I can incorporate into my verlet engine. Oriented ellipsoids, cylinders etc. may be added later.

Share this post


Link to post
Share on other sites
Quote:
Original post by fig
Here's a little exe demo showing that it does kinda work..

http://www.upload2.net/download2/bxeTUb4CXjxWI51/Base.rar.html

I couldn't really find any info on the subject so most of it is based on trial and error. And of course, my math skills aren't all that great :) I'm trying to build up an easy to use library of collision routines that I can incorporate into my verlet engine. Oriented ellipsoids, cylinders etc. may be added later.
I would only say this with certainty if I'd implemented ellipsoid vs. ellipsoid intersection myself (which I haven't), but I don't think you're going to get very far with your current algorithm; that is, no amount of tweaking is going to make it accurate. The mathematical representation for ellipses and ellipsoids involves squares, and most problems concerning them produce higher-order equations that are non-trivial to solve. See here for more info on this particular topic, and here for a number of papers dealing with these shapes.

There are various special cases which aren't so bad - raytracing of ellipsoids, ellipsoid vs. polygon soups, and perhaps even pairs of axis-aligned ellipsoids (I'm not sure) - but in general they're not the easiest shape to work with.

Share this post


Link to post
Share on other sites
The problem I see on your code is that you are trying to move both ellipsoids into the ellipsoid space of ellipsoid 1, which is ok if they share the same radii or the radii of one is proportional to the other as they would then both become spheres when converted.

for example one's radii is (1,2,3) the other (2,4,6), no problem there, we move into the first one space and we get

(1/1,2/2,3/3)==(1,1,1) and (2/1,4/2,3/6)==(2,2,2),

you do SphereVSphere with radii 1 and 2 and it will work, however, what happens if we have:

(1,2,3) and (6,4,2)

turns

(1/1,2/2,3/3)==(1,1,1) and (6/1,4/2,2/3)==(6,2,0.66)

now, (6,2,0.66) is hardly a sphere.

Hope that helps.

Share this post


Link to post
Share on other sites
Thanks to both of you for your replies.

Quote:
one's radii is (1,2,3) the other (2,4,6)


While testing, I was probably picking similar values to these. So both ended up as spheres like you said. duh! :)

The main reason I wanted ellipsoids was for a player bounding volume. I think I'll just go with cylinders for now. One problem I can image with them though. If one player lands on another's head, because the top and bottom of the cylinder is flat, the player will be able to stand there? :) Maybe I could have a cylinder with a sphere on top, a kind of capsule shape..

The primitives I'm planning to use so far are spheres, cylinders, planes and AABBs. Most of which is implemented already. Are the any other fairly simple ones that I should consider while I'm up for it?

Share this post


Link to post
Share on other sites
Quote:
Original post by fig
The main reason I wanted ellipsoids was for a player bounding volume. I think I'll just go with cylinders for now. One problem I can image with them though. If one player lands on another's head, because the top and bottom of the cylinder is flat, the player will be able to stand there? :) Maybe I could have a cylinder with a sphere on top, a kind of capsule shape..
You answered your own question there! Rather than using a cylinder, which has the problem you describe and also a rather expensive test, you are better off using capsules. A capsule is a cylinder with spherical endcaps, and it is defined by a line segment and a radius. Capsule-capsule tests are pretty cheap, whereas cylinder-cylinder intersection tests are most certainly not.

Also, with regards to the original topic of ellipsoid-ellipsoid tests, jyk and Kwizatz already explained what the problem is: the transformation you apply will only work when the each of the radii of ellipsoid A is a multiple of the corresponding radius of ellipsoid B. As jyk said, generic ellipsoid-ellipsoid testing is very intricate (and expensive) so it's not something you really want to do, if you can avoid it.

Share this post


Link to post
Share on other sites
Ellipsoid versus ellipsoid is very different from circle versus circle and, basically, the method you give won't ever work correctly.
Simple explanation: if you look at ellipsoid versus ellipsoid intersection, there is four intersection points (roots of quartic equation). With circles it is at most quadratic equations. It is possible to do ellipsoid-ellipsoid intersection but it would be much slower.

So yes, for bounding, use capsules. Each capsule is defined by line segment and radius.
Point is inside capsule if distance from point to the line segment of capsule is less than capsule radius. Two capsules intersect when distance between their line segments is less than sum of radiuses. Additional bonus, line segment is just capsule with radius 0 , and circle is capsule with zero length of line segment and given radius.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!