# Collision detection/response in world made of ellipsoids

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

## 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 on other sites
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 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 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 on other sites
Sorry, but capsule is not an option for me...

##### Share on other sites
well, how about my elipsoid suggestions then?

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

##### 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 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 on other sites
You could always approximate your ellipsoids by convex polyhedra and use an existing collision detection package...

So, why ellipsoids?!

##### 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...

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 22
• 17
• 46