• ### What is your GameDev Story?

#### Archived

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

# Ellipse vs. line collision detection

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

## 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 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 on other sites

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 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 on other sites
Thanks very much, I fully understand it now... went through one example on paper.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634088
• Total Posts
3015447
×