2D Collision Detection

76677837e0b6fa71adf11321a072dd40
0
grom 101 Nov 13, 2007 at 22:36

I followed and understood http://www.gamasutra.com/features/20020118/vandenhuevel_02.htm and manged to make demo of bunch of balls flying around colliding with each other.

The collision detection code is passed a time parameter (t). It determines if a collision occurs in this amount of time and if it does it returns when the collision occurs.

for (int i = 0; i < balls.length; i++) {
a = balls;
for (int j = i+1; j < balls.length; j++) {
b = balls[j];
t = Math.min(t, a.testBallCollision(b, t, collisions));
}
}

The main parts of source code can be found at http://grom358.mygamesonline.org/bouncingballs_guide.html

So at end of this code the time variable (t) will have when the first collision occurs. All the balls are moved to this point in time and then handle calculating the physics for the collision.

Repeat this until we reach the time allocated for drawing of that frame.

Now I am trying to work on implementing box-box and box-sphere collisions. But I don’t know how to detect when box-box or box-sphere collision occurs.

I looked out couple articles like http://www.gamasutra.com/features/19991018/Gomez_1.htm but its confusing me. It says “A common approach to collision detection is to simply test for whether two objects are overlapping at the end of each frame. The problem with this method is that quickly moving objects can pass through each other without detection. To avoid this problem, their trajectories can be subdivided and the objects checked for overlap at each point; however, this gets expensive if either object experienced a large displacement. On the other hand, a sweep test can efficiently determine a lower and upper bound for the time of overlap, which can then be used as more optimal starting points for the subdivision algorithm.”

But I don’t see how this fits in. Can anyone explain this to me?

3 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Nov 14, 2007 at 00:08

For box-box collisions (assuming you’re not talking about axis aligned boxes, since those are easy), look up the separating axis test. It’s a general test that works for any pair of convex polyhedra.

Box-sphere is a little bit more involved. The general idea is to expand the box by moving each face of the box outward by the sphere’s radius, then test if the center of the sphere (a point) is inside the expanded box. However, for the test to be exact the expanded box should not be a sharp-edged box but a rounded box, with cylindrical edges and spherical corners. You can treat the expanded rounded box as being made of 3 regular boxes, 12 cylinders, and 8 spheres, and test if the original sphere’s center is inside any of these.

Regarding the quote from the last article: imagine a very thin wall and a small, very fast moving object. In one frame, the object might be entirely on one side of the wall, and in the next frame, the object’s moved far enough that it’s entirely on the other side of the wall. It *should* collide with the wall, but this isn’t detected because the collision occurs in between two frames. So to detect this, you need to test whether the wall collides with the entire volume of space that the moving object occupied in the time from one frame to the next. This is called a sweep test, and the article tells how to do sweep tests for a variety of shapes.

However, then in the case of a fast moving object, you want to determine the exact time that the collision occurred so you can apply physics properly. The sweep test lets you efficiently narrow down the range of time when the collision could have occurred, using a binary-search-like algorithm to find the moment of collision. (I don’t think it’s necessary to do as the article suggests and determine both lower and upper bounds for the time of overlap and then feed them to a different algorithm.)

76677837e0b6fa71adf11321a072dd40
0
grom 101 Nov 14, 2007 at 00:33

So once you do the sweep test and have upper and lower bounds. How do you find the moment they collide so can do the physics of the collision?

You mean binary-search like algorithm. Does this mean you divide up the timeslice into slices and test which slice collision first occured then on that slice divide it up. And then repeat until you are within acceptable margin of error?

This is the part I don’t get. All the materials I found so far talk about how to find they intersect but I don’t see how you determine when the collision occurs.

I don’t know if its because my approach is wrong or not. In the bouncing balls demo I find out when the first collision occurs then move all objects to that point in time. Determine new velocity of balls that collided. Then repeat this testing again until we reach the end of frame (there is roughly 12ms between frames with 80fps). I doing this cause the first collision will change what possible collisions can occur after that.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 168 Nov 14, 2007 at 02:03

@grom

You mean binary-search like algorithm. Does this mean you divide up the timeslice into slices and test which slice collision first occured then on that slice divide it up. And then repeat until you are within acceptable margin of error?

Yes, that’s exactly what I mean.

In the bouncing balls demo I find out when the first collision occurs then move all objects to that point in time. Determine new velocity of balls that collided. Then repeat this testing again until we reach the end of frame (there is roughly 12ms between frames with 80fps). I doing this cause the first collision will change what possible collisions can occur after that.

That sounds like the right approach.