Jump to content

  • Log In with Google      Sign In   
  • Create Account

Figuring out ellipsoid-ellipsoid collision detection


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
20 replies to this topic

#1 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 30 August 2012 - 10:50 PM

I've been working on collision detection code for a project, and I'm trying to figure out the method to use to detect collisions between objects. Since I use ellipsoids to test against level geometry, I'd like to use them for collisions between objects as well. The problem is figuring out exactly how. One method I've seen converts the ellipsoids to a sphere and an axis-aligned ellipsoid, which looks like a great solution, but the method involves finding eigenvectors and other advanced stuff that I don't really understand (yet) and would rather not have to implement.

It should be easy to convert the ellipsoids to a sphere and a skewed ellipsoid by applying a series of affine transformations.
I've read that a skewed ellipse is still elliptical, so the skewing is equivalent to a rotation and a scaling, and I assume that the same principle applies to ellipsoids. However, I'm not sure how to determine the rotation and axis lengths of the new ellipse. If I knew that, it would be easy to make the ellipsoid axis-aligned. After that, I'm hoping to be able to perform a sweep test, but I'm not sure how efficiently it can be done, and I haven't figured out the equations to use yet, although I could possibly figure those out with a little work.

I'm also considering working with other collision shapes if ellipsoids don't work out, but it would be really nice to be able to use the same shapes for object-world and object-object collisions.

Sponsor:

#2 mv348   Members   -  Reputation: 253

Like
0Likes
Like

Posted 31 August 2012 - 01:12 AM

I just typed up a way of computing ellipsoid collisions but there was a flaw in my logic so I'll have to think about it some more.

But anyway, I would recommend using capsules ('capped cyllinders') for object collisions if your 'objects' are people, for example. Or just plain boxes, if only for coarse collision detection. Ellipsoids are not exactly standard so I don't know why you'd want them so bad.

Edited by mv348, 31 August 2012 - 01:24 AM.


#3 Álvaro   Crossbones+   -  Reputation: 13913

Like
0Likes
Like

Posted 31 August 2012 - 01:14 AM

Computing eigenvectors is precisely how you figure out the axes of the ellipsoid, and I am afraid you are going to have to learn how to use them.

Edited by alvaro, 31 August 2012 - 01:14 AM.


#4 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 31 August 2012 - 02:44 AM

It looks like I might have to learn more about eigenvectors. Capsules are a nice solution for collisions with meshes, but there doesn't seem to be a good sweep test for them that allows arbitrary rotation. Is there a simpler, faster method of finding eigenvectors when the matrices represent affine transformations?

EDIT:
It looks like finding the eigenvectors for basic affine transformations (such as scaling) isn't tough at all, but the eigenvectors for a combined transformation are tougher. I think the set would just be the union of the eigenvector sets of the component transformations if there were no pairs of inverse transformations involved, but I might not always be able to guarantee that. Of course, if I know where the pairs are, I might be able to eliminate them from the calculation.

#5 Álvaro   Crossbones+   -  Reputation: 13913

Like
0Likes
Like

Posted 31 August 2012 - 07:55 AM

You need to find the eigenvectors of the 3x3 submatrix that maps vectors to vectors (i.e., without the row and column that are zero and a translation). Here's what I would try:
  • Compute coordinates where one of the ellipsoids becomes axis aligned. Pick the length of the vectors so the ellipsoid becomes a sphere.
  • After the transformation, compute coordinates where the other ellipsoid becomes axis aligned. Now you should pick unit-length vectors so you keep the sphere a sphere.
  • Compose the two changes of coordinates.
There is some theorem about simultaneously turning a quadratic form into the identity and diagonalizing another one, which I think is effectively what we are doing here. Unfortunately I couldn't find a good reference with a quick web search.

#6 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 31 August 2012 - 09:29 AM

The first step should be easy; I can use an inverse rotation and a scaling instead of finding eigenvectors.

If the axes of the transformed ellipse coincide with (the transformation) * (the original axes), finding the rotation/scale that correspond to the introduced skew shouldn't be too hard. I'm just not sure if the skewing makes the ellipse bulge, changing its axes beyond what the skew might suggest.

Edit:
I know it changes at least one axis; otherwise this would be way too easy...
I think all I need to do is to figure out how to find the new axes given the eigenvectors. From there, calculating the required transformation should be easy.

#7 Álvaro   Crossbones+   -  Reputation: 13913

Like
0Likes
Like

Posted 31 August 2012 - 09:40 AM

The first step should be easy; I can use an inverse rotation and a scaling instead of finding eigenvectors.


It depends on how the ellipsoid is expressed, but if you do have the axes already, yes.

If the axes of the transformed ellipse coincide with (the transformation) * (the original axes), finding the rotation/scale that correspond to the introduced skew shouldn't be too hard.


Unfortunately, it's not that easy. The first transformation can easily change the axes of the other ellipsoid.

I seem to remember Dave Eberly's book "3D Game Engine Design" had details on how to perform many intersection tests, probably including this one. I'll take a look at it when I get home. Or maybe Dave could lend a hand here, since he does hang out in these forums.

#8 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 05 September 2012 - 01:18 PM

I've tried playing around with the equations for an ellipse, but that's getting me nowhere. I found a method here, but it's beyond my comprehension, especially with defining the ellipse equation in terms of matrices. Is there some other way to represent the relationship between the eigenvectors of the transformation matrix and the axes of the skewed ellipsoid?

#9 Álvaro   Crossbones+   -  Reputation: 13913

Like
0Likes
Like

Posted 05 September 2012 - 11:16 PM

It is extremely natural to represent the equation of an ellipsoid using a symmetric matrix. Finding the axes of an ellipsoid is equivalent to finding coordinates in which the ellipsoid is simply a*x^2 + b*y^2 + c*z^2 = 1. In terms of the matrix, you are diagonalizing it (the off-diagonal elements correspond to terms that contain products of different variables). This is a very well understood problem, and the solution is to use the eigenvectors as the basis for your coordinates. So if you figure out a procedure to find the axes, you will have reinvented an algorithm to find the eigenvectors.

I don't think you can get away without an understanding of linear algebra if you want to do this kind of thing.

#10 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 06 September 2012 - 02:05 AM

I think I'm starting to get it...maybe...

I haven't taken a linear algebra course, so I'm learning as I go. I'll see if I can make more sense of the paper I mentioned. If not, I'll probably just switch to capsules for the object-object pass. I've got an idea for a capsule-capsule sweep test that might work.

#11 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 06 September 2012 - 12:00 PM

I'm starting to understand more of the theory behind this, but if I'm going to have to implement a Newton's Method solver on top of the linear algebra, I think I'll just go with capsules instead. If I pad one of the capsules by the other's radius, I should be able to put the problem in terms of a sweep test between a capsule and a line segment, which shouldn't be too tough, especially if I make the capsule axis-aligned. Do you think it would work?

#12 raigan   Members   -  Reputation: 744

Like
0Likes
Like

Posted 06 September 2012 - 05:43 PM

If you get capsule-vs-capsule sweeps working, please post -- that would be super interesting :)

#13 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 06 September 2012 - 06:39 PM

If you get capsule-vs-capsule sweeps working, please post -- that would be super interesting :)


I'll see what I can do. Hopefully it actually works...

#14 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 06 September 2012 - 08:50 PM

I just realized that capsules are useless for objects that are shorter than they are wide. I might go back to ellipsoids...
If I can get the eigendecomposition, I should be able to get the second ellipsoid to be axis-aligned. I can then pad the second ellipsoid by the radius of the now-spherical first ellipsoid and make the first ellipsoid a point, making the test a simple case of a ray-ellipsoid intersection.
Is there an algorithm for getting the eigenvectors of an affine 3x3 matrix that is more efficient than the general case, or should I just implement a general eigenvector solver?

..and the solution is to use the eigenvectors as the basis for your coordinates.

I guess that means I can just use dot products to bring the sphere's position into the space defined by the eigenvectors. That should be equivalent to making the ellipsoid axis-aligned, right?

#15 Álvaro   Crossbones+   -  Reputation: 13913

Like
0Likes
Like

Posted 06 September 2012 - 09:44 PM

I just realized that capsules are useless for objects that are shorter than they are wide. I might go back to ellipsoids...
If I can get the eigendecomposition, I should be able to get the second ellipsoid to be axis-aligned. I can then pad the second ellipsoid by the radius of the now-spherical first ellipsoid and make the first ellipsoid a point, making the test a simple case of a ray-ellipsoid intersection.


Unfortunately for this plan, a padded ellipsoid is not an ellipsoid. :(


Is there an algorithm for getting the eigenvectors of an affine 3x3 matrix that is more efficient than the general case, or should I just implement a general eigenvector solver?


I would go with the general method. Worry about getting something that works first, and worry about performance later.


..and the solution is to use the eigenvectors as the basis for your coordinates.

I guess that means I can just use dot products to bring the sphere's position into the space defined by the eigenvectors. That should be equivalent to making the ellipsoid axis-aligned, right?


At the very least you should learn enough linear algebra to know how to change coordinates from one basis to another (i.e., multiply by a matrix). But yes, it can be expressed as a bunch of dot products.

#16 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 06 September 2012 - 11:04 PM

Unfortunately for this plan, a padded ellipsoid is not an ellipsoid. Posted Image

Are you sure? I took an ellipse and expanded each axis by a fixed amount, and the resulting ellipse seemed to be a perfectly padded ellipse so that a point colliding with it is equivalent to a circle colliding with the original. I didn't verify it mathematically, but it looked just fine with a ruler, which is probably good enough for an approximate collision detection.

I would go with the general method. Worry about getting something that works first, and worry about performance later.

Sounds like a good plan. Looks like it's Google time.

Edit:
I've found some code that might work. Does 6,000 cycles per decomposition sound reasonably efficient?

At the very least you should learn enough linear algebra to know how to change coordinates from one basis to another (i.e., multiply by a matrix). But yes, it can be expressed as a bunch of dot products.

Oh... now I see it. For some reason, linear algebra takes longer to "click" in my mind than most other topics do. I might need a little more practice...
I think I've just about got this figured out, though.

Edited by BLM768, 06 September 2012 - 11:24 PM.


#17 Dave Eberly   Members   -  Reputation: 1161

Like
1Likes
Like

Posted 06 September 2012 - 11:50 PM

My advice is to skip ellipsoids. Use a bounding box or a k-DOP (or some convex polyhedron with a small number of faces), then use separating axis tests. The coding is just a lot easier, and the numerical robustness issues in determining ellipsoid-ellipsoid intersection can be avoided.

That said, there is an implementation of the ellipsoid-ellipsoid intersection at my web site.

Regarding capsules, better choice than ellipsoids because the intersection/separation tests are simpler to implement. For capsule-capsule sweep, a simple implementation uses bisection over the desired time interval. At each time you apply a (static) capsule-capsule overlap test, which reduces to a computation of distance between line segments and a comparson involving this distance and capsule radii. You can avoid the iteration--I have pseudocode for this in my Game Physics 2nd edition (section 6.3.2).

Regarding bounded cylinders, the game physics book and a document at my web site show the complexity of intersection testing via separating axes. Turns out that it is simpler to do cylinder-cylinder intersection with infinite cylinders, then clip the intersection set based on the finite cylinder heights. Not an exact test (result is not a closed form solution), but effective. I have a document about this at my web site and a sample application (for the infinite cylinder-cylinder test).

#18 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 07 September 2012 - 01:06 AM

My advice is to skip ellipsoids. Use a bounding box or a k-DOP (or some convex polyhedron with a small number of faces), then use separating axis tests. The coding is just a lot easier, and the numerical robustness issues in determining ellipsoid-ellipsoid intersection can be avoided.

If I can manage to simplify it to a ray-ellipsoid intersection by padding one ellipse, the code shouldn't be hard (except for the eigendecomposition, for which I can just use existing code). The simplification would also make it possible to solve all but the eigendecomposition analytically. I think that would take care of a lot of the numerical robustness issues, although I don't know for sure.

That said, there is an implementation of the ellipsoid-ellipsoid intersection at my web site.

I've actually been working off that implementation, although the final implementation will probably be quite different.

Regarding capsules, better choice than ellipsoids because the intersection/separation tests are simpler to implement.

They are easier, and I was going to use them, but I realized that they don't handle disk-shaped objects well at all; they can't get any flatter than a sphere. I'm not sure how often that would be an issue, but it would be nice to not have to worry about it.

If I knew of a better algorithm to find the eigendecomposition, I think I could get ellipsoids to work extremely well. The fact that I need one of those complex, time-consuming algorithms makes me a little uneasy about my solution, but not enough to abandon it before I see how well it works.
I just realized, though, that getting the inverse matrix to get the modified velocity back into world space might be hairy...

Hmm... I guess I might have to drop ellipsoids (except for collision with meshes; the code for that is just too nice to replace) and go with capsules. I suppose that I'll just have to go without disk-shaped objects or special-case the collision code somehow.

Darn it; I was getting a really nice solution before the technical details had to spoil it for me. There's just too much math in this math stuff :).

As far as capsule-capsule collision goes, I'm pretty sure I can simplify it to sweeping a line segment against a larger capsule, which could give me a really nice analytical solution as long as sweeping it against the spherical ends isn't a problem. I think I can figure it out...

#19 Álvaro   Crossbones+   -  Reputation: 13913

Like
0Likes
Like

Posted 07 September 2012 - 07:04 AM

Unfortunately for this plan, a padded ellipsoid is not an ellipsoid. Posted Image

Are you sure? I took an ellipse and expanded each axis by a fixed amount, and the resulting ellipse seemed to be a perfectly padded ellipse so that a point colliding with it is equivalent to a circle colliding with the original. I didn't verify it mathematically, but it looked just fine with a ruler, which is probably good enough for an approximate collision detection.


Think of an ellipsoid that is very very skinny: Say 2 units long, 0.0001 wide and 0.0001 deep. Now add one unit of padding. The resulting figure is much closer to a capsule than it is to an ellipsoid.

#20 BLM768   Members   -  Reputation: 295

Like
0Likes
Like

Posted 07 September 2012 - 09:10 AM

Think of an ellipsoid that is very very skinny: Say 2 units long, 0.0001 wide and 0.0001 deep. Now add one unit of padding. The resulting figure is much closer to a capsule than it is to an ellipsoid.


OK; I see. Degenerate or near-degenerate cases seem to be great for disproving incorrect ideas; I might have to make use of that fact.

A padded capsule should still be a capsule, though, right? Even the degenerate case seems to work there.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS