Jump to content
  • Advertisement
Sign in to follow this  
smek2

ellipse intersection detection

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

Can anybody help me out with collision detection based on ellipses? I searched with google but found nothing so far. Well, nothing i could understand and use with c++ anyway. i have to admit, i do not know much about geometry. I would like to know how to check whether two ellipses intersect each other or not and maybe the size of the intersection area. Any hints? Thanks in advance.

Share this post


Link to post
Share on other sites
Advertisement
Better use capsules (capsule = cylinder capped with spheres; so for 2D it's 2 half-circles joined by lines). Ellipses are rather hard to check for intersection; for example to find intersection points you need to solve quartic equation.

Share this post


Link to post
Share on other sites
if you know how to do a collision test against a sphere then you know how to do one against an elipse. remember an elipse is just a sphere under a linear transform. suppose I have an elipse and the matrix that would make that eplipse from a unit sphere at the origin for example. for example suppose I got a mojor axis as the x axis and it's length is 2 and the minor axis is unchanged, then the matrix that would take the unit sphere to the elipse is
[2 0 0
0 1 0
0 0 1]

so we have a matrix that takes points from sphere local space to elipse global space(assuming there is no translation). so we know all objects we are testing against are in global space so instead of testing these objects against this elipse we can transform the object by the INVERSE of the matrix above and test against the resulting points against a sphere at the origin! this reduces it to a simple distance test.

tim

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"remember an elipse is just a sphere under fake linear transformation". You could be in for the the faked astology of the 21'st centuary if you are not careful.

Share this post


Link to post
Share on other sites
Quote:
Original post by timw
if you know how to do a collision test against a sphere then you know how to do one against an elipse. remember an elipse is just a sphere under a linear transform. suppose I have an elipse and the matrix that would make that eplipse from a unit sphere at the origin for example. for example suppose I got a mojor axis as the x axis and it's length is 2 and the minor axis is unchanged, then the matrix that would take the unit sphere to the elipse is
[2 0 0
0 1 0
0 0 1]

so we have a matrix that takes points from sphere local space to elipse global space(assuming there is no translation). so we know all objects we are testing against are in global space so instead of testing these objects against this elipse we can transform the object by the INVERSE of the matrix above and test against the resulting points against a sphere at the origin! this reduces it to a simple distance test.

tim

As I understand, smek2 are interested in collision between 2 ellipses.
The problem of course is collision of two ellipses that needs different transforms to become circles [or spheres if we talk about ellipsoids]. If one needs ellipse collision detection, one need to be able to detect collisions between two ellipses too.
Colsider two long ellipses (2d) intersecting in cross-like way, so there is four intersection points. There's aint no transformation that can reduce it to two circles (two circles can have at most 2 intersection points) Indeed it does reduce to ellipse versus circle, but you still get quartic equation.

Share this post


Link to post
Share on other sites
Yes i am interested into checking collision for two ellipses.
Can someone explain (or provide to a good link) for quartic equations and/or capsules (they seem to be a good alternative, but i have no idea about that either)
Anyways, thanks for the replies.

Share this post


Link to post
Share on other sites
well, quartic equations it's equation of form ax^4+bx^3+cx^2+dx+e=0 . It have up to four roots. You get it if you solve this ellipse-ellipse thing for intersection points. It is rather difficult to derive for general case; there's special-case solution(when both ellipses have same center) http://mathworld.wolfram.com/Circle-EllipseIntersection.html.
(for two ellipses you can transform it so one becomes a circle)

I know that distance between ellipsoids (3D) are commonly computed using iterative methods.

Capsules is quite simple thing. You can use google
Volume of capsule is defined as set of points whose distances to line segment is less or equal to r.
To check for intersection of 2 capsules you just find closest distance between 2 line segments and check if it is greater than r1+r2 .
(I'm currently assuming there's no real reason for you to prefer ellipsoids to capsules.)

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.

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!