I wrote a windows program that animates a ball bouncing in a window inside a polygon. Inside the first polygon is a second polygon that the ball will bounce off of (also, there''s a button to generate a new random polygon.) The program works great as it is; but it''s really treating the ball as a _point_ and not a circle. The collision and ''bouncing'' happens when the center-point of the ball hits a wall; not when the edge of the ball hits. If the ball center is traveling horizontally just below a "V" shaped polygon -- where the center of the ball passes under the bottom with no collision, but part of the ball actually collides, how can that be determined? And the angle of reflection doesn''t quiet seem obvious, because it''s colliding with a point and not a line. My first guess would be to simulate a line collision at that point with an imaginary line that is tangent to the ball at the collision point. If this is unclear, I can produce some graphic images to illustrate these conditions and post a follow up with the URL. My idea is to write a ''Break Out'' game; getting all the bouncing ball collision detection isn''t that trivial. But if I can solve this problem, then the "blocks" in the break out game could actually be any arbitrary polygon. I''d be happy to share the source code, both what I have already and what I come up with.. It''s a Visual C++ 6.0 MFC SDI project. Thanks, // CHRIS http://net-toys.8k.com

Look in any graphics or trig book for the formula to determine the distance of a point to a line, and use it to find the distance from the circle''s center to the wall. If the distance is equal or smaller than the radius of your circle, then you hit it.

I guess I wasn''t clear. I already know how to determine the distance from a point to a line. That isn''t the problem.

Consider, again, a ball at the lower left of two segments that form a "V" shape. The ball is to the left of the "V" and moves horizontally to the right. With the velocity vector going to the right, let''s say that the ending position of the ball is then to the lower right.

Let me try an ascii image..

. \ /
. ,--. \/ ,--.
. /__/ /__/

The ball on the left is the initial position (x,r) and the ball on the right is the ''next'' position after applying a velocity vector (Vx,Vy). The CENTER point of the ball DOES NOT go through either of the two segments that form the "V" shape, but part of the ball DOES.

If you were to simply check the distance from the ball center point to the segments, at both the initial and final state of the ball, then you will miss the fact that a collision occurred. The beginning and final state have a distance D > R (ball Radius).

I''m trying to figure out how to identify this collision without ''walking the trajectory line'' -- breaking it up into tiny (say 1 pixel increments) and testing each step.

Maybe I just figured it out. If you consider the tangents to the circle with the same slope as the velocity vector (Vx,Vy) [in the case above, it would be a horizontal line touching the top and bottom of the circle] then you can test if either of those lines intersect any other segments (like the "V" above.) If so, then a collision occurred. The only hole in that logic would be if there was a segment fully contained in the space the ball passes _through_.

// CHRIS

Get the distance of the ball from the line. If it is less than the radius of the ball, the ball has hit the line. The resulting trajectory of the ball would be the same as if it were a point.

If you want a demonstration of this take a look at my 3D breakout style game Wall3D at:

http://www.geocities.com/ben32768

No, No.. The "point to line" distance isn''t sufficient. Not unless you test with each point along the way from the initial to the final (initial + velocity).

I made a picture to show what I am talking about:
http://members.xoom.com/win32mfc/collide.html

The center of the ball, from the initial to the final position, never passes through a segment, but the ball does -- and not at the initial or final position, but IN BETWEEN. That is what I am trying to calculate: when does this happen? It''s easy to visualize but the function doesn''t seem easily solvable with non-itterative techniques.

Consider the distance D from the ball center "C" to a segments "S". This distance D = PointToSegmentDistance(C,S). If you were to graph the values of D from the balls initial position to the final position, (for the example above) you would get values greater than R (ball Radius), falling down to below R and then going back up above R. The answer to when the ball collides is the first value D such that D - R = 0.

Any ideas would be greatly appreciated.. I can''t sleep!

// CHRIS

Genovov,
Thanks for the link to that article. I''ll try and implement it next chance I get but it may be what I am looking for.

For my case, I have many lines/polygons to check against; I can eliminate the sweep test from all the segments that have a segment/segment distance > R (ball radius).

Thanks again,
// CHRIS

What I've done to implement my physics system is something like this:

Take a circle and draw a box around it. Obviously there is a lot of wasted space where the box says you HAVE collided when you really haven't but this is just for initial collision detection. This is a rather quick way to basically determine if another object is close enough to have "possibly" collided.

Then take that same circle and subdivide it into 4 squares that would basically fill up that one big square and check for a collision. If one of them has a collision then you know the collision occured somewhere in that part of the circle. Then create some more squares and test and test again. I think this is similiar to a branching tree algorithm? I'm not sure because I never read up on them, but it's a quick way to "zero in" on where the collision occured. Depending on how many times you subdivide the circle determines how accurate your collision detection is, much like your algorithm. But while for your algorithm you need to test every point, this one is able to narrow down where the collision occurs rather quickly.

To tell you the truth, I've never actually implemented this algorithm because I'm basically a beginning programmer (I've only done 2 java applets and only 1 of them had animation! LOL), but I spend a lot of my free time thinking about this kind of stuff analytically.

BTW, the trick is that when you initially create your object you need to create a 2D array of points which are calculated upon creation so you don't have to keep creating points every frame. So:

{
{place a "collision box object" in the array for the largest box, which contains the points for that box}
{put the next biggest boxes in here, each containing their points}
{next biggest boxes in here, etc}
}

Of course, you could implement a 3D array and get rid of the box objects and just put the points into that third part of the array, but that would get real messy.

And this only really works with normal geometric objects where you can calculate points to use based on their geometric properties. And each type of object would have to have its own constructor. Using weird shaped polys is another matter.

Oh yeah, and by using this system you can take the two points that you need to construct the box and use them as the parallel surface to the collision and create the normal from that (which is basically the negative inverse of that line) and then you can easily calculate what the resulting vector will be.

Edited by - BMason on 4/8/00 7:26:54 PM