Sign in to follow this  
Keramzit

Collision detection/response in world made of ellipsoids

Recommended Posts

Keramzit    122
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
Eelco    301
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
Eelco    301
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
Eelco    301
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
Eelco    301
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
Rompa    307
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
Keramzit    122
Eelco, thanks for "sweep-&-prune" suggestion. I think i'll use this method in my game. It's really very simple and effective enough for me. But now I have a question... How to efficiently find projections of ellipsoid on coordinate axis?
Let our ellipsoid's center be at the coordinate system center. Let define our ellipsoid by three orthogonal vectors ("halfaxis").


Share this post


Link to post
Share on other sites
Eelco    301
im not sure what youre asking.

but say you have an elipsiod represented as an orthogonal matrix, composed of a rotation * scaling, or as you put it, three orthogonal vectors, you can manipulate it as you would do to any linear space.

Share this post


Link to post
Share on other sites
johnb    351
I had a look at this a while ago when looking to add ellipsoids to a collision system. In the end I decided not to implement them (or at least only do ellipsoid-plane collisions) as the mathematics required to resolve general ellipsoid collisions simplifies down to a tricky and expensive quartic.

This makes sense as if you consider the 2D problem of e.g. finding the intersections between an ellipse and a circle it's easy to see there are in general four distinct solutions (consider e.g. x^2 + y^2 = 1 and x^2 + 4y^2 = 2).

It makes no difference whether the ellipsoids are axis aligned as if not you can use a scaling matrix to transform the problem so one of the ellipsoids is a sphere, then work in the space of the axes of the non-spherical ellipsoid.

Share this post


Link to post
Share on other sites
Eelco    301
well, thats if you want to know the intersections of the pair.

however, youre only interested in the closest point, of which there is only one.

Share this post


Link to post
Share on other sites
Charles B    863
Just like everyone else said non axis aligned col. det. of ellipsoids should be avoided.

Nonetheless, somebody already asked a similar question. Direct algebraic solutions are not possible. I have thought about it around 3 hours in a train and I found some interesting quick iterative solutions, based on a separating plane ... again,

To give you some fisrt indications, (local coords) ellipse/plane is quasi immediate. For E : a*x*x + b*y*y + c*z*z = d, find x,y,z / gradient G(x,y,z) is parallel to the plane normal N. Just one reciprocical square root in the end you get something like :

s = sqrt(d) * rsqrt(Nx^2/a + Ny^2/b + Nz^2/c)

And P : x=+-a*s, y=+-b*s, z=+-c*s. This is the point of E that is the nearest to the plane N. You find the signs as the obvious opposite to the coords of N. You also have the min distance easilly : N*P.

I need to think about it again to remember exactly how you make an algo of it. But the general idea is :

You select a set of 3 tangent planes at start on the second ellipse E2. Then you recurse to get an approximation the tangent plane of E2 whose mindisrance is maximum to the first ellipse E1. This gives you is the 'contact' plane (thus normal) and nearest point on E2. In practice, for quick rejection, you stop as soon as this min-distance is positive, greater than your collision metric tolerance. You can also cache the plane(s) between frames as in the algo for convex polyhedrons.

[Edited by - Charles B on October 4, 2004 9:59:55 AM]

Share this post


Link to post
Share on other sites
Dmytry    1151
You may store your ellipsoids as linear transforms of spheres.
That is, ellipsoid is represented by 3X3 matrix that transforms unit sphere into that ellipsoid, and vector that gives position. (And that transform, 3x3 linear + offset must have some name i don't know. Let's name it 3x4 transfrom. Note that you can define multiplication and inverse on 3x4 transforms)

If ellipsoid is defined by M and V, it's mean, for every unit-length vector Q ,point P = M*Q+V is placed on ellipsoid.

So,then, if you want to collide 2 ellipsoids with matrices M1 and M2, positions V1 and V2,
you can transform both by inverse(M1) so first ellipsoid becomes a unit sphere with xenter at 0. So now you only have to test second ellipsoid(with matrix M = inverse(M1)*M2 and offset V=inverse(M1)*(V2-V1)) against unit sphere. And it must be simpler, you can make your ellipsoid be axis-aligned if you turn it.

Also, note that there's infinitely many matrices that can represent same ellipsoid. If O is an orthonormal matrix, and M is a ellipsoid matrix, M*O gives same ellipsoid. In general, there's finitely many(6) orthogonal (not orthonormal) matrices that represent same ellipsoid. So,how to find equivalent orthogonal matrix from arbitrary ellipsoid matrix M:
you need to find orthonormal matrix O that M*O is orthogonal.....
Must be somehow related to eigenvectors or something, but i don't sure how exactly.

edit: and about using closest distance to check if 'em is collided. We need to do it for ellipsoid and sphere, because we always can make one of ellipsoids to be sphere (edit2: as Charles B pointed out, we no longer find closest distance, but it can be used for collision detection anyway).

It's the same as closest distance between ellipsoid and point. It must be simple to find. It might be even possible analitically. Let's sphere center is at 0,0,0 . First test if 0,0,0 is inside ellipsoid (simple) If inside, they're surely collided. Otherwise:
Pick some point in or on ellipsoid, P2. Center will work the best.
In loop:
P1=P2;
find other point P2 on ellipsoid that (P1 dot P2) is
minimal. this dot product it's closest distance to plane with normal P1)
To find P2 we need to just find unit vector Q that P2=M*Q+V. So (P1)dot(M*Q+V) is minimal. So P1 dot(M*Q) + P1 dot V is minimal, so unroll P1 dot (M*Q) = (P1*M) dot Q (using identity A dot B = matrix_with_A_as_row * matrix_with_B_as_column)
. From there, Q = -normalized(P1*M) , that gives minimal dot product.
and P2=M*(-normalized(P1*M))+V , but note that P1*M = -transpose(M)*P1;
that is,
P2= -M*normalized(transpose(M)*P1) + V;
Repeat till necessary accuracy is achieved(till P1-P2 small enough).
Must give accurate answer quite fast.

Probably my explanations is totally unreadable,so....

Loop rewritten without explanations:
P2=V;

do{
P1=P2;
P2=V-M*normalized(tranpose(M)*P1);
}while(NotVerySmall(P1-P2)&&(|P2|>1.0)).
and if |P2|<=1.0 we're collided.

Note that ideally we should get P1 that
P1=V-M*normalized(tranpose(M)*P1);

and it's might even be trivially solvable
edit3: there was horrible typos with normalized(tranpose(M)*P1) I accidently typed tranpose(M)*normalized(P1) /

Hope i'm was right and made no idiotic mistakes....

edit3: some bad typos.

[Edited by - Dmytry on October 4, 2004 10:44:17 AM]

Share this post


Link to post
Share on other sites
Charles B    863
@Dmytry : When I studied the problem one month or so ago, I have turned around this idea quickly enough to conclude it brings nothing.

Introducing a scaling to have one unit sphere :

- Does not change the algorithmic difficulty since the second is still a general ellipsoid. For instance in my algo, you will only save a few multiplications in the implementation, really nothing valuable.

- More important. You change the metrics !. Your transformed space (S2) of resolution is no more Euclidian if the first (S1) was (which is the case). This means that the nearest points you'll find in (S2), transformed back into (S1), will not be the nearest points in (S1) ! Thus, you'll only be able to respond to the intersection test (boolean : yes/no). But you won't be able to give the minimum distances, contact points and normals, necessary to a physics engine ! (Try a 2D scheme and you will see the problem)

EDIT : I have found a paper that details the general algebraic solution (seek "Intersection of Ellipsoids", a pdf). Hard maths and it requires solving a 16th degree polynomial in the end ! ;)

Now I am close to the optimal iterative algo. It requires a small numbers of iterations (probably one only in practice). It may be of the same order in efficiency than Capsule/Capsule. I'll post it later, a bit boring to write in ascii text.

Share this post


Link to post
Share on other sites
Shannon Barber    1681
You make a geometry tree, oct-tree, quad-tree, sphere-tree, or in your case I think you should use an ellipsoid tree if you stick to ellipsoids.

If memory serves me, ellisoids are very difficult to use with moving objects - a sphere becomes a capsule, a capsule becomes two capsules and a box, an ellipsoid becomes a non-elementary shape (a sort of 2dof ellipsoid instead of 1). Slow-moving saves you, but this isn't a robust design.

Share this post


Link to post
Share on other sites
Shannon Barber    1681
Quote:
Original post by Rompa
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...


Why wouldn't you just use sphere's in the first place then?

Share this post


Link to post
Share on other sites
Dmytry    1151
Quote:
Original post by Charles B
@Dmytry : When I studied the problem one month or so ago, I have turned around this idea quickly enough to conclude it brings nothing.

Introducing a scaling to have one unit sphere :

- Does not change the algorithmic difficulty since the second is still a general ellipsoid. For instance in my algo, you will only save a few multiplications in the implementation, really nothing valuable.

- More important. You change the metrics !. Your transformed space (S2) of resolution is no more Euclidian if the first (S1) was (which is the case). This means that the nearest points you'll find in (S2), transformed back into (S1), will not be the nearest points in (S1) ! Thus, you'll only be able to respond to the intersection test (boolean : yes/no). But you won't be able to give the minimum distances, contact points and normals, necessary to a physics engine ! (Try a 2D scheme and you will see the problem)

EDIT : I have found a paper that details the general algebraic solution (seek "Intersection of Ellipsoids", a pdf). Hard maths and it requires solving a 16th degree polynomial in the end ! ;)

Now I am close to the optimal iterative algo. It requires a small numbers of iterations (probably one only in practice). It may be of the same order in efficiency than Capsule/Capsule. I'll post it later, a bit boring to write in ascii text.


Right. It's not a distance. But anyway, we probably can analitically find if them is collided, and it's useful. See my edit.

Share this post


Link to post
Share on other sites
Dmytry    1151
and got not very efficient idea about algo how to find minimal distance between two ellipsoids(may not work if one inside other).
V=V2-V1;
O1=vec3(0,0,0);
O2=V;
do{
P1=O1;
P2=O2;
R=P2-P1;
O1=M1*normalized(tranpose(M1)*R);
O2=V-M2*normalized(tranpose(M2)*R);
}while(NotVerySmall(P1-O1)&&NotVerySmall(P2-O2)).

Hope it works. At least, it looks nice[grin].
edit:small typo.

Share this post


Link to post
Share on other sites
Charles B    863
@Dmytry:

and it's might even be trivially solvable
Yes ;)

OK I take your demo here : You have applied several transfos to get a your unit sphere centered and the other ellipsoid axis aligned (since the unit sphere symetry enables you to rotate as you want). It's really easy to picture this.

So the problem is now find the point of an axis aligned ellipsoid closest to the origin, thus also closest to the unit sphere in terms of signed distances. It's trivial with the gradient ;)

You named M the ellipsoid matrix. I'd prefer naming it S. It's a diagonal scaling matrix that transforms the unit sphere into an axis aligned ellipsoid. Do not care about eigen vectors. Obviously the structure representing a general ellipsoid should be totally identical to an oriented bounding box :

- 3 extents : Sx, Sy, Sz (<=> pseudo radii <=> scaling matrix )
- 1 rotation (quaternion or matrix)
- 1 center (3 coords)

In 3D algebra this gives : P = T*R*S*U. Scale, Rotate, Translate unit vector U to a point P in world coords.

In its local coords (remove T and R) an ellipsoid equation is just given by the transform back of a point into the "unit sphere" system : (~S*P)^2 = 1 <=> P belongs to E. ~S being a notation for the inverse of S.

<=> E : (x/Sx)^2 + (y/Sy)^2 + (z/Sz)^2 = 1


Back to our issue. There R is removed. We translate by -T so that the unit sphere center C is at -T and the center of the axis aligned ellipse is (0,0,0) : we're in the local referential of the ellipsoid. P(x,y,z) of E is nearest to C iff (1) Grad(P)=k*CP, k negative.

(2) Grad(P) = (2x/Sx^2, 2y/Sy^2, 2z/Sz^2) = 2* (~S)^2 * P
P belongs to E thus :
(3) (~S*P)^2 = 1 (1 equation)
By definition :
(4) CP = P+T

Thus (1)&&(2)&&(4) =>
CP = k*Grad(P) <=> (P+T) = 2 * k * (~S)^2 * P
(3 coords equations)

Can you finish it ? 4 equations, 4 unkowns ;) Easy, find k, by exploiting (3), a square root, and next it's done for x,y,z, all linear.


Well in fact, to correct my initial judgement on the unit sphere idea. It can be used :
- For quick rejection. One can return a majoration (analyse the scaling part) of the contact distance. And exclude any contact within an error threshold for sure.
- To get a good first guess of the nearest point, back to world coords, in euclidian space. Start the search contact point algo more quickly.

Share this post


Link to post
Share on other sites
Eelco    301
Quote:
Original post by Magmai Kai Holmlor
Quote:
Original post by Rompa
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...


Why wouldn't you just use sphere's in the first place then?

because you transform both elipses, so the effect is still that of the intended elipse vs elipse.

however, its probably true it doesnt make a difference for iterative methods. however, im still not convinced there isnt a trivial exact solution for sphere-AAelipse closest point detection.

Share this post


Link to post
Share on other sites
Charles B    863
There is a trivial solution for sphere/ellipsoid. Cf my response to Dmytry.

But I also explained it does not give you the answer for ellipsoid/ellispoid when you transform back (unscale). It only answers for rejection, metrics are lost in the non euclidian transfo, since angles are not preserved.

I have now an intuitive solution for the ellipsoid/ellipsoid case. I am quasi certain it converges and quickly, but it would be surely hard to demonstrate exactly why, mathematically.

It's easy to find the furthest point in one direction N. Demo similar to my ellipse/sphere demo.

In local coords (discard T and R, just keep the scaling matrix S), the point furthest in direction N is :

P = S^2 * N / ||S*N||

(Note that for a sphere P=R*N. This is coherent since S would be a uniform scaling by R : R*Identity).

So take the direction between the two centers and you get 1 point on each ellipse. They aren't the closest ones. But the take direction of the segment between them. Average it with the previous direction. This is probably the trick. Two new points again. For some obscure reason, I am convinced it converges and in the end to a limit where the two points are the closest ones. At each step the distance between the two points will be strictly lower than at the previous step. That's what I'd like to prove. Next showing the limit is optimal should not be too difficult to prove.

Anyway it would be worth testing the code empirically.

[Edited by - Charles B on October 4, 2004 12:18:25 PM]

Share this post


Link to post
Share on other sites
Dmytry    1151
@Charles B :
argh, haven't thought to use that in closest point we just simply have gradient(aka normal) parallel to distance!(edit: in fact i tried to use that in closest point we must have minimal dot product)
Yes, that's solution. Will dig into that tomorrow.
as about your last post:
in my prev. post with pseudocode i'm truing to do exactly that , furthest point in one direction , and this direction is named R.

I probably picked _bad_ representation of ellipsoids (general 3x3 matrix and translate, very hard to find gradient, so i'm deriving furthest point as point that have minimal/maximal dot product). Will try with your representation.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this