Jump to content
  • Advertisement


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


Ellipse vs. line collision detection

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

Hiya, does anybody know how that works? I read the article here at GameDev.Net(http://www.gamedev.net/reference/articles/article1026.asp) but I don''t really understand some bits of the pseudo code: "Double pDist = intersect(source, -pNormal, pOrigin, pNormal);" There is an intersectSphere function somewhere in the article but it doesn''t use a radius vector... can I just change that or do I also have to make changes to the code? "Ray ray(sphereIntersectionPoint, Velocity);" How does that one work? If no one can help me it would be nice to see a working example. Thanks for any help.

Share this post

Link to post
Share on other sites
he simplifies the ellipse / segment test by converting it into a sphere / segment test, sphere being of radius=1 (that''s why there is no radius specified).

this is achieved by converting the segment into the ellipsoid space.

for example, if the ellipsoid is of size (2, 5), at position (1, 0) (like stretched along the Y axis), to convert a point (vertex, end points of segments, ect...) into the ellipsoid space, you do

P = Vector(7, -3);
P -= Ellipse.Position;
P.x /= Ellipse.Size.x;
P.y /= Ellipse.Size.y;

P will then become ((7 - 1) / 2, (-3 - 0) / 5) in the ellipse space.

then effectively, the point P is in the ellipse space, and the ellipsoid is like a sphere centred at (0, 0) and of radius 1, when convertex to it''s own space.

so all the tests from world space becomes easier in ellipsoid space, since you know you are colliding with a unit sphere.

if you extract some information from the test in object space, be sure to reconvert the result back to the world space, if you need to.

another thing about moving sphere/segment collision. the time of collision you''ll find by doing a sphere against a segment test is equivalent to doing a ray versus a capsule test (a fat segment). it''s like you extrude a sphere around the segment, and find the time when the centre of the sphere is at distance = radius to the segment.

Share this post

Link to post
Share on other sites
Thanks for the reply!

I worked through the algorithm and I almost fully understand it now, just one single thing is missing:

"t = intersect(ellipsoidIntersectionPoint, velocity, pOrigin, pNormal)"

I know that it''s a ray/plane collision detection. But: The prototype of insect is

double intersect(planeOrigin, planeNormal, rayOrigin, rayVector), where planeNormal and rayVector are unit-length.

So, doesn''t it have to be

t = intersect(pOrigin, pNormal, ellipsoidIntersectionPoint, velocity)

then(I think the ray is supposed to be fired from ellipsoidInterP.)? And isn''t velocity supposed to be normalized for the function?

Share this post

Link to post
Share on other sites
ewww... one of the bugs in the tutorial.

yeah, he got the prototype and the function call mixed up. His pseudo-code is riddled with errors like this, so it can look confusing. Although the algo itself looks sound.

you''re change is the right way round. The velocity does not have to be normalised, but you can. And probably should, if it makes feel you more confortable (the parameter returned will then be the real distance of intersection from the Intersect point, so useful for degugging). You can try with non-normalised later, when you want to optimise things a bit. Getting it working 100% and understanding the algo is the first priority.

the ray is fired from the intersectPoint, which isn''t really an intersection point, more like a support point along the plane normal, as they are usually called. It''s like the point on the sphere the lowest towards the direction of the plane normal, which will be the point of contact on the sphere when the sphere do collide with the plane.

Another awy of doing is to raise the plane by the radius of the sphere, and find the time of collision of the centre of the sphere and that plane. It''s essentially the same thing.

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!