I read that thread and then also the collision.pdf that was linked to it. However, I am still unsure what I should do for a moving sphere and rectangle collision. Those collisions seem to be just for sphere/sphere and ellipsoid collisions. Surely there is a more optimal one for a sphere/triangle. Does anyone know of one?

Quote:Original post by simotix
I read that thread and then also the collision.pdf that was linked to it. However, I am still unsure what I should do for a moving sphere and rectangle collision. Those collisions seem to be just for sphere/sphere and ellipsoid collisions. Surely there is a more optimal one for a sphere/triangle. Does anyone know of one?

The .pdf covers sphere-vs.-triangle collision. Also, check the thread again (some additional information regarding sphere-triangle intersection has been added).

I have read that, however, is there no more optimized technique rather then just doing two triangle checks?

Quote:I have read that, however, is there no more optimized technique rather then just doing two triangle checks?

You mean specifically for a swept sphere vs. rectangle test? If so, sure, it can be optimized. It's basically the same principle: you raytrace the CSO of the rectangle and the sphere, which can be thought of as being comprised of two rectangles, four (finite) cylinders, and four spheres, more or less. An optimized version of the algorithm will most likely test against the rectangles first, then, based on the results of this test, determine what other features need to be tested against, etc., etc. Implementing all of this correctly and robustly can be kind of a pain, but it's doable.

Quote:Original post by simotix
I have read that, however, is there no more optimized technique rather then just doing two triangle checks?

Make a minor modification to the algorithm and identify closest features based on the Voronoi region of the rectangle within its plane. In fact, the implementation is slightly easier for the rectangle, because you can take advantage of the fact that you have two pairs of parallel edges. The clipping of the projected line of centers is simpler for the rectangle than for the triangle.

I am still looking into this issue, I was reading real time collision detection to learn other in motion collision detect techniques. I was able understand the moving sphere to plane collision just fine. As a result, i took my knowledge of sphere to rectangle collision and moving sphere to plane collision, than tried to apply it together in what I thought would make logical sense.

What I basically did was just calculate the distance different than I would for moving sphere to plane collision. I calculated the distance as I would for a sphere/rectangle collision. The problem is it is still wrong. Does anyone have any suggestions on what I should do?

Quote:Original post by simotix
I am still looking into this issue, I was reading real time collision detection to learn other in motion collision detect techniques. I was able understand the moving sphere to plane collision just fine. As a result, i took my knowledge of sphere to rectangle collision and moving sphere to plane collision, than tried to apply it together in what I thought would make logical sense.

What I basically did was just calculate the distance different than I would for moving sphere to plane collision. I calculated the distance as I would for a sphere/rectangle collision. The problem is it is still wrong. Does anyone have any suggestions on what I should do?

*** Source Snippet Removed ***

Unfortunately, it's not as easy as what you've posted there.

To intersect a moving sphere with a rectangle in 3-d, there's a certain amount of work that has to be done - you really can't just tweak the discrete test and hope to get reasonable results.

I'd recommend reading the thread linked to previously again. That thread is on the topic of sphere-vs.-triangle intersection, but a swept sphere-vs.-rectangle test can be implemented in a similar way.

Note that these sorts of tests can be tricky to implement. May I ask what you need it for? Perhaps there are other, more practical solutions to whatever problem you're trying to solve.

Quote:Original post by jyk
To intersect a moving sphere with a rectangle in 3-d, there's a certain amount of work that has to be done - you really can't just tweak the discrete test and hope to get reasonable results.

I'd recommend reading the thread linked to previously again. That thread is on the topic of sphere-vs.-triangle intersection, but a swept sphere-vs.-rectangle test can be implemented in a similar way.

Note that these sorts of tests can be tricky to implement. May I ask what you need it for? Perhaps there are other, more practical solutions to whatever problem you're trying to solve.

I will read the sphere vs triangle intersection again and see if I could get a good grasp of it.

The reason I want to test a moving sphere against a wall is because I want to set up a room and have balls be thrown against the wall. It is not going to be a simple box room, but there will be ledges in the room also, so I can not just use planes.

Also the rectangle is not moving. Only the sphere is moving.

[Edited by - simotix on April 2, 2010 1:38:24 AM]

Could someone be more specific? I have researched the static collisions of sphere with a rectangle and sphere with a triangle. I then looked at how a moving sphere to rectangle is calculated. I just do not see how a moving sphere to triangle calculation can be translated to moving sphere to rectangle. Could someone explain the collision steps for a moving sphere to rectangle?

Quote:Could someone explain the collision steps for a moving sphere to rectangle?

Well, let's see. (Long post coming up, I think...)

Suggestion number one: use an existing physics library. If this is for learning purposes and the main point is to implement the collision detection yourself, then this probably isn't an option. If the goal is just to get a simulation up and running though, using an existing physics solution will probably be much faster than trying to implement it yourself.

Suggestion number two: stick with the discrete test, and make sure that the per-update displacement for the sphere is small enough to prevent tunneling and other unwanted effects. The discrete test is much easier to implement than the continuous test, so this approach would probably be much easier. (Plus, it sounds like you've already got the discrete test implemented, or nearly so.)

Ok, if you're still here...

The first thing to realize is that there's a limit to how simple the continuous test can be made. In other words, it's complex enough that it doesn't necessarily break down easily into simple 'step by step' directions.

The other thread that we've been discussing includes pretty much all the info you need in one form or another. There were some points made in that thread that I didn't fully understand (as evidenced by my responses there), but I'll go ahead and provide the best answer I can here.


There are several different ways to conceptualize the test, and several different ways to implement it. I find at useful, at least for illustrative purposes, to look at the test as what I refer to (perhaps incorrectly?) as a 'CSO raytrace'. This approach may not be to everyone's taste, but personally, I've found it useful.

Consider the Minkowski sum of a rectangle and a sphere. This is the shape swept out by sweeping the sphere center over the surface of the rectangle; you can also think of it as the set of all points for which the distance from the point to the rectangle is <= the sphere radius. Dave Eberly refers to this shape as a 'lozenge' in his materials, which should give you a sense of the type of shape we're talking about.

If we take the line segment representing the motion of the sphere center over the time step and intersect it with this lozenge, we can use the information returned to infer some things about the intersection (if any) between the sphere and the rectangle. If the segment and lozenge don't intersect, neither do the sphere and the rectangle. If the segment intersects the lozenge at some valid value of t, then the sphere and rectangle intersect, and t gives us the first time of intersection. And so on.

The segment-lozenge test can be implemented fairly easily if you already have segment intersection tests available for boxes, spheres, cylinders, and/or capsules. In short, you simply intersect the segment against all of the (overlapping) features of the lozenge, and look for (e.g.) the minimum value of t. This isn't very efficient, but might suffice if the number of narrow-phase tests you anticipate performing per update is small.

If greater efficiency is needed, the segment-lozenge test can be optimized considerably by first determining (via analysis of the relative configuration of the two shapes) which features must be tested against. This process is described in some of Dave's materials, although I'm not sure if there's an implementation for this particular test available on the website (I looked, but didn't see one).

There are other ways of conceptualizing and implementing the test as well. You could sweep the sphere against the various features of the rectangle (edges, etc.) and look for the first intersection, if any (note that the individual sweep tests are similar to the individual raycasts in the CSO test). Or you could follow the method described in Dave's references, where the segment is clipped to the Voronoi regions of the rectangle and quadratics are solved on a per-region basis in order to determine the points of intersection. Or, you could implement a generic continuous GJK test (I haven't done this myself, but I get the impression that it's non-trivial).

If you need more information, you might need to ask questions that are more specific. That is, rather than simply requesting more detail, explain what you've tried, what aspect of the test you're uncertain about, and/or what sort of problems you've run into with your implementation.