The standard approach to handling collisions between spheres and triangles is to perform two tests.
The first test is a Ray/Plane test, and the second is a Point/Triangle test.

Most implementations attempt to treat the Sphere as a Point and Radius.
They calculate the Ray for the Intersection Test from the Sphere Origin at two moments in Time, find the projected intersection, then "correct it" to compensate for the radius.

If the Sphere has Initial Time (Ti) and End Time (TQ), and the ray between the origins at those times intersects the plane (at collision time TX), then we can further assume that theres two moments (T0 and T1) where the distance from the intersection point (on the plane) to the sphere origin in the unsigned direction of the plane normal equals the sphere radius.
In english, T0 is when the sphere is positioned so as to just touch the front face of the plane as the collision event is just occurring (the sphere just touches the front of plane), TX is when the plane is passing through the sphere origin, and T1 is when the sphere is out the other side of the plane but is just still touching it.

(we can actually calculate T0 and T1 with a formula that requires DistancePointPlane, but that sucks.. read on , my method doesn't require this at all)


If we calculate T0 so we can shift the projected sphere back from TX to T0, we can then project from the origin at T0 along the direction negative to plane normal by distance=Radius to find the ACTUAL intersection point TANGENT TO SPHERE AT T0.

That, my friends, is a lot of work which can be avoided.
Here's my solution:
Our Plane is defined by a Point (on the Plane) and a Normal, right?
We can easily SHIFT THE PLANE TOWARDS THE SPHERE ALONG THE PLANES NORMAL AND BY THE DISTANCE=RADIUS by simply multiplying the normal and the radius (save the result - see below) and addiing the result to the theoretical Plane Point
We now go ahead and test for intersection of ray between sphere origins and shifted plane.
The resulting intersection point TX is the exact location for the Sphere Origin at T0.
To find the intersection point at T0 on the Plane, we negate the result vector we saved earlier and we add it to the sphere origin at T0(we just calculated as TX)
We have the Sphere in position without backpaddling, and we have the correct planar intersection point without "correcting".
We now continue to the second stage testing (triangle geometry) as usual.

What do you think?? :D
Posted on 2005-04-25 23:54:45 by Homer
Here's a demo actually using the optimisation outlined in the previous post.
A further optimisation involves precalculating "PlaneD" value(s).

This demo shows (from above, and at a slight angle) a sphere bouncing on a triangle.
We're using the optimised triangleplane test and fast PointInTriangle test.

The surfacenormal is calculated from the triangle vertices.
If I was to move a vertex to put the triangle on an angle, the ball correctly responds to hitting the sloped face, but soon it will bounce right off the triangle, and then we'll get an error message, so I'm not showing it. In a game environment, we hedge the world to either prevent objects leaving the world proper, or to be culled out of existance by planes surrounding the world proper. Regardless, this is a small demo which does what I wanted.

Posted on 2005-04-26 07:47:39 by Homer
Some of you might notice the physics are acting up.
The sphere doesn't comply to Newton's law of conservation of energy !!

Who wants to help fix this code and earn the codebase in the process?
Posted on 2005-04-27 05:36:22 by Homer
I want to try! Give me your source code let's see if I can beat it. :-)

Just to clarify, this is a dynamic sphere intersecting a static triangle?
Posted on 2005-05-06 08:37:30 by wildgnu
Yes, that's right.
We have a static triangle and a moving sphere.
I'll post the code for you as soon as I've retrieved the hard drive from my dead epox.
It's pretty straightforward stuff..
Posted on 2005-05-06 08:42:52 by Homer
I probably should have been more explicit.
We have a theoretical sphere at a given position in space, an initial velocity vector (null in demo) and then Time begins passing.
We apply only Gravity , recalculating the velocity on the fly.
During collisions, frametime is broken into components around the intersection point on the plane, so that we can find the corrected post-collision position in space at the end of the timeframe.
That's probably where the problem lies.
What I do is figure out when in the current timeframe the collision occurs, which tells me how much of the travel during the current timeframe is "illegal" - then I resolve the collision to the moment of impact, apply the reflected velocity, then using this new velocity I apply whatever time is remaining in the current timeframe, the amount of illegal time from earlier, so the sphere moves along its new direction vector for the remaining time, and there we are done, we can render the sphere for the current frame , exactly where it should have been after the collision at that moment, and with the supposedly correct velocity and direction..
Posted on 2005-05-06 09:14:00 by Homer
Uh huh. You probably want to consider the sphere's velocity to be constant between time frames. I take it you want to not only test for collision but also find the first point (or time) of intersection. If you could find a way to only test between sphere's and planes you would be in luck because it is particularly easy to find the first point of intersection under those circumstances. The math goes like this: Let r be the radius of a sphere with moving center C(t)=C_0+tW. The distance between the center and the plane is |N dot C(t)-d| and the first time of contact is T=/(N dot W). Here d is the distance of the plane from the origin along the normal N. All capitols are vectors. If the numerator of this figure is negative there is no need to perform the division as this means the sphere is moving away from the plane.

I am kind of assuming that the triangle is actually a part of a wall in which case you should probably test against the bounding planes of whatever region you are in. If not, you are probably better off with a Sphere,Sphere test or something else depending on the circumstances.
Posted on 2005-05-06 10:40:15 by wildgnu
Oh I see. Reading back I see you were trying to avoid that very test. Anyway I'd still like to see what you got.  :)
Posted on 2005-05-06 10:44:41 by wildgnu
I assume that the sphere's velocity is constant between each two timeframes.
That is to say, its velocity won't alter until the end of each timeframe, unless a collision occurs.
What I do is measure the actual elapsed time and calculate a new velocity at the end of each timeframe based on it. This will be the input velocity for the next frame.
If a collision occurs, I assume the velocity at the moment of collision is the same as it was at the start of the timeframe - I don't apply any gravity force - what I do is split that input velocity in two, based on how far into the timeframe the collision occurs.
I reflect the collision angle and then I set the output velocity as the second part of the split input velocity, ie, the "remaining" velocity.. I apply this velocity immediately, for "remaining" time (ie time from collision until end of timeframe) which is the same way as saying I move the sphere along its reflected ray from the collision point and collision time, until the end of the timeframe. Now I am at the end of the timeframe. I apply gravity and update the velocity as usual for the end of a timeframe.

This should be accurate, even if the elapsed times are jumpy.

Posted on 2005-05-14 01:39:56 by Homer
I think i don't get something :| what's the difference between this funcion and the D3DXIntersectTri funcion?

(and sorry if the question is VERY stupid :P )
Posted on 2005-05-15 15:31:19 by ti_mo_n
As far as I am aware, the D3DX helper function uses the classical method of calculating the intersection time and then converging on it.
This method is faster, with two caveats that the testpoint must be coplanar and the sphere must always start on the happy side of the plane.
Also, this method is naiive ie it was written for use with opengl, and does not depend on any microsoft library.
If you get to the point where you want to know where the bottlenecks are in your applications, you will find that they are usually found within highly iterated math functions.
Personally I found the d3dx math helpers wanting in terms of speed.
This is particularly true for example with a Mesh/Ray intersection.

One of the things I use sphere tests for is Bounding Spheres around more complex object geometries, in an attempt to speed things up through culling. If I introduce a boundingsphere test for all my objects, that test better be fast...
I have just added extra complexity to the code and potentially it can run slower now !!

Therefore I introduce this algorithmic shortcut.
What I have done is reduce the math required to achieve the same output.
It's really nothing more than a clever transposition of the order of math operations :)

Like I say, it has two major caveats and will not work in all situations.
But if we assume that a sphere may never leave the world, and/or that the world is enclosed, then it is ok to use this.
Posted on 2005-05-15 19:20:24 by Homer