Collision detection/response in world made of ellipsoids
Author
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. :)
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.
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.
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).
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.
well, how about my elipsoid suggestions then?
if there is something you dont understand, feel free to ask.
if there is something you dont understand, feel free to ask.
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).
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.
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.
You could always approximate your ellipsoids by convex polyhedra and use an existing collision detection package...
So, why ellipsoids?!
So, why ellipsoids?!
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...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
