Sign in to follow this  
NiGoea

moving ellipsoid VS moving triangles

Recommended Posts

NiGoea    104
Hi All ! We're again talking about collision detection. The question is this: once you have a working ellipsoid based collision system, in which the ellipsoid velocity is taken into account, how do you handle moving triangles ? I mean, if you consider an ellipsoid and its velocity vector, you pass into ellipsoid space but then how do you handle a triangle if it is moving ? In "3D Mathematics for 3D Game Programming" I read how to handle two moving spheres, but not a moving sphere and a moving triangle. Ideas ? THANKS !

Share this post


Link to post
Share on other sites
Alrecenk    400
I would break the triangle into it's component parts: a plane, 3 lines, and 3 points. Then your problem becomes how do I do a swept collision between a sphere and those things?

The plane is pretty easy. Move the plane along it's normal toward the sphere a distance equal to the sphere's radius(you can do this because when the sphere collides it's center is guaranteed to be this vector away from the plane). Then perform a ray plane intersection with the sphere's center as the origin and the difference in velocities as the direction. The points should be pretty easy if you've got sphere-sphere code already. A point is just a sphere with no radius. I can't seem to think of the swept line-sphere collision off the top of my head right now, but I'll see what I can come up with if noone else posts soon.

Anyways, once you've got the time of intersection of all of those things you'll want to check the point of intersection for the lines and planes. Ya know, make sure the collision point on the plane is inside the triangle and make sure the line collision points are between the end points. Once you've discarded the false positive that aren't actually on the triangle, just pick the time of collision that is the smallest.

Keep in mind that this still only considers swept translations and won't take into account the rotation of the triangle. If that's what you're trying to do, well, you're on your own.

P.S. When someone starts a post with "Hi All". I choose to believe the second l is a typo.

Share this post


Link to post
Share on other sites
Eric_Brown    127
First, subtract the velocity of the triangle from the velocity of the ellipsoid, to pose the problem such that the triangle is at rest.

Second, sweep the ellipsoid against the infinite plane that contains the triangle, to find the point on this plane where the ellipsoid first makes contact.

Third, find the point on the triangle that is nearest to the point on the plane. This is the point where the ellipsoid will first touch the triangle if they make contact.

Finally, sweep the triangle point back along the relative velocity direction toward the ellipsoid. If the point sweeps through the ellipsoid then there is a collision, otherwise you have no collision.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Third, find the point on the triangle that is nearest to the point on the plane. This is the point where the ellipsoid will first touch the triangle if they make contact.
I don't think this is true. (In fact, this might be the oft-mentioned error in the original paper on this subject - I haven't read the paper in a while though, so I might be wrong about that.)

As a counterexample, consider a sphere (for simplicity) moving towards a triangle at a velocity that is angled with respect to the triangle plane. The sphere comes into contact with the supporting plane, but the contact point is not on the triangle. Since there is a component of the relative velocity that is parallel to the plane, the point on the triangle closest to this contact point will likely not be the same as the first point of contact between the sphere and the triangle edge.

Share this post


Link to post
Share on other sites
rewolfer    120
I'm not sure that Eric_Brown's idea will work. Surely it assumes that all points on the triangle are moving with the same velocity, ie. there is no rotation? If you were to look at the relative trajectory between one of the vertices and the sphere, it would surely be nonlinear?

I don't have pretty solution to this, but am also very interested to know the "correct" way to do this.

I recently had to perform this test. And as Al said, I split it up into primitives, but then I performed a bisection method to locate the time of collision and from there each calculation was easy.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Surely it assumes that all points on the triangle are moving with the same velocity, ie. there is no rotation? If you were to look at the relative trajectory between one of the vertices and the sphere, it would surely be nonlinear?
That's right; the solutions proposed above all assume constant linear velocity and fixed orientation over the time step. As Alrecenk alluded to, considering angular motion makes the problem quite a bit more complicated.
Quote:
I recently had to perform this test. And as Al said, I split it up into primitives, but then I performed a bisection method to locate the time of collision and from there each calculation was easy.
Does your test consider angular motion? If not, I don't think there's any need for bisection; for a sphere and a triangle moving with constant linear velocities, an exact, single-step solution (i.e. no bisection) can be constructed easily enough.

Share this post


Link to post
Share on other sites
oliii    2196
It's potentially a difficult subject.

If the movement of the triangle cannot be simplified to just a translation, you can either do some form of conservative advancement, decompose the trajectory and shape of your triangle into smaller steps, or do some complex equation solving using constant angular velocity.

High angular velocity is a problem, and the current methods are either very complicated, or very slow (well, much slower than just dealing with translations).

There is a paper on continuous collision detection involving triangles and their angular velocities, but it's not for the faint-hearted. And even then, the paper makes assumptions, such as the angular and linear velocities of the triangles are constant during the collision step.

Share this post


Link to post
Share on other sites
NiGoea    104
Uh, some answers, great :D

[for now on I'll talk about just spheres]

Well, for me, first of all we have to consider the type of collision we want:

1- rigid body with mass => two spheres that are moving towards each other collide somewhere in the middle of the trajectory. That is, the first sphere affects the final position of the second, and viceversa. This is the case of two actors.

2- "fake" body without mass => The final position of this object is never affected by collisions with other objects. This is the case of doors or elevators.
For example, an elevator goes up of 5 meters per seconds regardless of how many actors are on it.
Let's note that this is an approximation of a real Newton-law based collision system (which I'm using for the first case)

--

The first case works well with ellipsoid/ellipsoid collisions, and this is enough for me.

The second case is the problem I was asking help for. But as I said, in this case (for me) you don't have to compute the collision point for the no-mass object, because it has anyway to reach its destination.

Therefore Alrecenk's solution can't easily work for me. However, it should work for a more efficient collision system: in fact I've already considered it by myself.

Eric_Brown's method is very similar to the one I came out with yesterday. My method is like this:
- substract triangle velocity from sphere velocity
- translate the sphere using the triangle velocity (if the triangle is going up of 2, you move up the sphere of 2)
- perform the standard collision procedure

In this way the sphere will try to reach its original position, but it will be obstructed by the triangle. If not, it will reach its original position.

What do you think ?

Share this post


Link to post
Share on other sites
NiGoea    104
As for rotations, I think yes, they DO increase a lot the difficulty of the problem :)
Anyway, rotations are way way less used.

Share this post


Link to post
Share on other sites
Eric_Brown    127
Quote:
Original post by jyk
Quote:
Third, find the point on the triangle that is nearest to the point on the plane. This is the point where the ellipsoid will first touch the triangle if they make contact.
I don't think this is true. (In fact, this might be the oft-mentioned error in the original paper on this subject - I haven't read the paper in a while though, so I might be wrong about that.)

As a counterexample, consider a sphere (for simplicity) moving towards a triangle at a velocity that is angled with respect to the triangle plane. The sphere comes into contact with the supporting plane, but the contact point is not on the triangle. Since there is a component of the relative velocity that is parallel to the plane, the point on the triangle closest to this contact point will likely not be the same as the first point of contact between the sphere and the triangle edge.


I will have to think about that... I'm not sure if I'm convinced.

I have recently posted the method I use on my blog.

Share this post


Link to post
Share on other sites
Dave Eberly    1173
Quote:
Original post by Eric_Brown
I will have to think about that... I'm not sure if I'm convinced.


JYK is correct. Consider a stationary triangle with vertices (0,0,0), (1,0,0), and (0,1,0). The plane of the triangle is z = 0. Consider a sphere with center initially at (0,-1,1) and with constant linear velocity (1,1,-1). At time zero, the sphere is just touching the plane at (0,-1,1), in which case the closest point on the triangle is (0,0,0). The sphere intersects the triangle at time t = 1 - sqrt(1/2), with intersection (t,0,0). At this time, the circle of intersection of the sphere and plane has center (t,t-1,0) and radius sqrt(1/2). The closest point (0,0,0) is not the intersection point (t,0,0).

Share this post


Link to post
Share on other sites
Eric_Brown    127
Hmm... I see what you mean. It's a wonder my collision works!

What if you swept the center of the sphere along the relative velocity, and then found the closest point on the triangle to the line? Then use this point and sweep back toward the sphere?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
It's a wonder my collision works!
It may be that you just haven't encountered a failure case yet, or that there is some error but it's going unnoticed.
Quote:
What if you swept the center of the sphere along the relative velocity, and then found the closest point on the triangle to the line? Then use this point and sweep back toward the sphere?
I think you would encounter similar problems with this method.

In any case, the swept-sphere-vs.-triangle test is more or less a solved problem, and basically reduces to performing a raytrace against the CSO of the triangle and the sphere. The test itself can get kind of involved, depending on how it's implemented, but conceptually it's pretty straightforward. (As for references, there was a paper floating around the internet at one point by Kasper Fauerby that covered it, and I believe Dave has code for it on his site as well.)

Share this post


Link to post
Share on other sites
NiGoea    104
SOLVED

Before moving the mesh (not the ellipsoid), consider its velocity (displacement) vector.
So:
- move the sphere by the inverse of the mesh velocity (so the mesh will be still)
- check for collisions. If a collision happens, retrieve the intersection point
- newVelocity = intersection - initialPosition
- D = velocity - newVelocity; this is the allowed displacement for the ellipsoid to touch the mesh
- ellipsoidPos += D

then, after updating all the ellipsoids, you update the mesh position by adding its velocity.

that works

Share this post


Link to post
Share on other sites
Eric_Brown    127
Quote:

Original post by jyk
In any case, the swept-sphere-vs.-triangle test is more or less a solved problem, and basically reduces to performing a raytrace against the CSO of the triangle and the sphere.


Wouldn't a ray-trace against the CSO of the triangle and sphere be an iterative method that is slow to converge? (due to the spherical nature of ... a .. sphere)

Is there a non-iterative approach?

Looking at it last night, I'm convinced that the "sweep the sphere against the plane and find the closest point on the polygon" approach DOES work in 2D. In this case, the sphere is a circle, the plane is a line, and a polygon is a line segment. It is only when there is a component of velocity out of the 2D plane that there is a problem.

What I said before was

Quote:

What if you swept the center of the sphere along the relative velocity, and then found the closest point on the triangle to the line? Then use this point and sweep back toward the sphere?


I actually meant to say "point on the sphere closest to the plane" rather than "center of the sphere". It works for the 2D cases, as well as for the 3D example given by Dave Eberly. Does it work all the time? I don't know.

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Wouldn't a ray-trace against the CSO of the triangle and sphere be an iterative method that is slow to converge? (due to the spherical nature of ... a .. sphere)

Is there a non-iterative approach?
Yes, it can be solved non-iteratively.

You wouldn't want to actually implement it this way, but one way to perform the test would be as follows (here we're assuming that the sphere is not already in contact with the triangle):

1. Raytrace against the two triangles formed by moving the triangle along its normal in the positive and negative directions by a distance equal to the sphere radius.

2. Raytrace against the three (finite) cylinders corresponding to the triangle edges.

3. Raytrace against the three spheres corresponding to the triangle vertices.

4. If there are any intersections, take the intersection with the minimum 't' value; that's your intersection.

In practice you wouldn't do it this way for efficiency reasons, but the optimized version is similar. All of the ray-primitive intersections can be solved analytically (quadratic is the highest order function encountered), so no iterative methods are required.
Quote:
I actually meant to say "point on the sphere closest to the plane" rather than "center of the sphere". It works for the 2D cases, as well as for the 3D example given by Dave Eberly. Does it work all the time? I don't know.
It still doesn't seem to me like that would work in all cases.

Unless I'm mistaken, any test that handles all cases correctly must *necessarily* be equivalent to a CSO raytrace. The test can be implemented in different ways; continuous GJK (which would be iterative in this case, I believe) and per-feature raytracing as described above (which is exact and non-iterative) are the two methods that I'm familiar with.

Furthermore, the per-feature approach can be thought of as raytracing of planes, cylinders, and spheres, or as sweeping of spheres against planes, line segments, and points, but these are just different ways of expressing the same tests (however you look at it, it's still a CSO raytrace).

Share this post


Link to post
Share on other sites
Eric_Brown    127
Quote:
Original post by jyk
Quote:
I actually meant to say "point on the sphere closest to the plane" rather than "center of the sphere". It works for the 2D cases, as well as for the 3D example given by Dave Eberly. Does it work all the time? I don't know.
It still doesn't seem to me like that would work in all cases.


I found a case where it does not work - if the sphere is already intersecting the polygon plane. In this case you can't choose a single point on the boundary of the sphere that is closest to the plane - there are lots of them.

Share this post


Link to post
Share on other sites
Dave Eberly    1173
Quote:
Original post by Eric_Brown
Quote:

originally posted by Eric_Brown
I have recently posted the method I use on my blog.

I've modified the article on my blog to account for the fact that I was... wrong.


Have you considered the case when the projection of the sphere is moving toward the polygon, but the sphere passes under (or over) the polygon (the projection passes through the polygon) and then just touches a polygon edge, after which the sphere travels away from the polygon?

I think the reason folks struggle with moving-sphere/moving-polygon contact is that there are a lot of details to handle. I mentioned the Voronoi approach, but I had first started to write that PDF using the sphere-projection idea. In the end, the closest-feature problem seemed not to go away, so I rewrote the PDF to describe the Voronoi stuff.

jyk mentions the ray tracing approach. This might be a simpler algorithm to implement but probably not as efficient regarding performance. Shrink the sphere to a point and grow the triangle by the radius (the usual Minkowski concept). The expanded triangle is a (not-disjoint) union of three spheres, three finite cylinders, and a convex polyhedron. In fact, you can embed this in a tight-fitting convex polyhedron that contains the spheres and cylinders.

The sphere center moves along a ray. Clip the ray against the tight-fitting convex polyhedron. Clip the ray against each sphere and each cylinder, discarding those portions outside the expanded triangle. If a segment remains after clipping, compare its time values to your desired time interval for the query.

[Edited by - Dave Eberly on March 25, 2010 8:29:58 PM]

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
jyk mentions the ray tracing approach. This might be a simpler algorithm to implement but probably not as efficient regarding performance.
Based on my own experiences implementing these types of tests, my sense is that the sphere-vs.-feature and CSO-raytrace methods are (or at least can be) just two different ways at looking at the same thing, and therefore are (or at least can be) more or less equivalent in terms of efficiency.

However, I haven't done any sort of formal comparison in terms of operation counts or run-time performance, so I can't really back that up with hard data.

Share this post


Link to post
Share on other sites
Eric_Brown    127
Quote:
Original post by Dave Eberly
Have you considered the case when the projection of the sphere is moving toward the polygon, but the sphere passes under (or over) the polygon (the projection passes through the polygon) and then just touches a polygon edge, after which the sphere travels away from the polygon?


Do you mean, the sphere is moving tangent to the polygon plane? If so, the sphere projection would once again break down, or at least require a special case.

I think my concern here is that I have previously deployed this algorithm on a game which, after doing so, completely eliminated all collision bugs for the entire duration of the development cycle. To be fair, the game didn't have too much dynamics going on, but it was unconstrained enough that the problems with the sphere projection method should have been showing up everywhere. It just doesn't make sense to me that I could get such solid performance out of a broken algorithm.

To be sure - next time the need arises I think I will go with the voronoi approach, rather than try to patch all the holes in the sphere projection approach.

Share this post


Link to post
Share on other sites
Dave Eberly    1173
Quote:
Original post by jyk
Based on my own experiences implementing these types of tests, my sense is that the sphere-vs.-feature and CSO-raytrace methods are (or at least can be) just two different ways at looking at the same thing, and therefore are (or at least can be) more or less equivalent in terms of efficiency.


Mathematical equivalency is not the same as computational equivalency. The distance between sphere center (when moving with constant linear velocity) and triangle is a convex function of time. The first time of contact is the smallest root of this function. You can set up Newton's method to find that root (and if it does not exist, detect this during execution). Assuming the root exists, you find it as the limit of the sequence of iterates. This is mathematically equivalent to the "CSO-raytrace method" but is not computationally equivalent.

Quote:

However, I haven't done any sort of formal comparison in terms of operation counts or run-time performance, so I can't really back that up with hard data.


The proof is in the pudding.

Regardless, here is an implementation for the "CSO-raytrace" algorithm (with a Wild Magic 4 application I used for testing it): MovingSphereTriangle.zip. This has a small amount of Voronoi-ness (distance from point to triangle is based on identifying closest featur).

I plan on implementing the Voronoi-based method just for comparison.

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