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").
Collision detection/response in world made of ellipsoids
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.
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.
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.
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.
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.
however, youre only interested in the closest point, of which there is only one.
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]
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]
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]
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]
@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.
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.
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.
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.
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
