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 !

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.

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.

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'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.

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.

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 ?

As for rotations, I think yes, they DO increase a lot the difficulty of the problem :)
Anyway, rotations are way way less used.

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.