Jump to content
  • Advertisement
Sign in to follow this  
Keramzit

Collision detection/response in world made of ellipsoids

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

Hello everyone. The objects in my game are made of oriented (not axis-alligned) ellipsoids. In other words, my geometry primitive is ellipsoid. Now I'm going to implement collision detection/response subsystem, so I need any links, code, suggestions and other help. Especially, I'm interested in how to reduce collision detection O(N^2) complexity. There are maximum 500 ellipsoids in my game's level, and this ellipsoids are moving (relatively slowly, so one ellipsoid cannot pass through another in one frame). PS: Sorry for my bad English. :)

Share this post


Link to post
Share on other sites
Advertisement
for the time-complexity issue, google sweep&prune. simple and effective, and it will reduce time complexity to O(objects*objectdensity), and i think its not getting any better than that anyway.

as for collision detection... that does seem like a solvable problem, however, i have to say i wouldnt really know how to. i have one idea though. transform both elipsoids in such a way that one becomes a sphere, and the other axis-aligned. not too hard, just a bit of matrix math, and from there on it shouldnt be too hard to see if the objects are intersecting.

to find a normal on the surface of an elipse, you can take the distance vector from the collision point to the centre of the elipse transformed to a sphere, and multiply that by the adjunct (inverse transpose) transformation matrix of this elipse, then normalize.

Share this post


Link to post
Share on other sites
Ellipsoids are a really bad idea - especially since yours can be alligned arbitrarily. If possible, I'd suggest using capsules (i.e. line-swept spheres).

Share this post


Link to post
Share on other sites
capsules would indeed be easier from a mathematical point of view, and hence probably faster. all it involves is line-line, line-point, and point-point distance.

Share this post


Link to post
Share on other sites
well, how about my elipsoid suggestions then?

if there is something you dont understand, feel free to ask.

Share this post


Link to post
Share on other sites
hmm i did a little googeling, and it turns out oriented elisoid vs oriented elisoid is a method that is avoided like the plague. maybe for good reasons: i dont know. but i do not see a solution to the problem as of yet (even though there is one for sure).

Share this post


Link to post
Share on other sites
but even if the problem is hard to solve analiticly, im pretty sure its quite possible to come up with an iterative method to find the closest point between two elipses.

again transform so that one elipse becomes a sphere, and then 'walk' the surface of the other elipse using some sort of gradient. since both are convex, this gradient is bound to lead you to the closest point (in other words, there is only one closest point).

im not sure what a good method for finding this gradient would be as of yet, but maybe ill come up with something. in any case such a method is bound to be pretty efficient.

Share this post


Link to post
Share on other sites
You could always approximate your ellipsoids by convex polyhedra and use an existing collision detection package...

So, why ellipsoids?!

Share this post


Link to post
Share on other sites
If indeed oriented ellipsoid vs oriented ellipsoid is extremely difficult, then transform one of the ellipsoids so that it is a sphere. Apply the same transformation to the other. You then have a simpler problem - sphere vs ellipsoid. Upon solving that, apply the reverse transform and "unsquash" your results. The beauty of a sphere vs ellipsoid is obviously that the sphere is orientation invariant. Just thinking out loud...

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!