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;Sphere and Cylinder vs Ellipsoid problem
Author
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..
Quote:Original post by figJust 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.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;
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.
Author
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..
Author
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.
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.
Quote:Original post by figI 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.
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.
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.
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.
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.
Author
Thanks to both of you for your replies.
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?
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?
Quote:Original post by figYou 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.
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..
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
