Archived

This topic is now archived and is closed to further replies.

win32mfc

2D Ball Collision Detection w/ Arbitrary Segments

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The way I understand your problem it is one often called "tunnelling." Since your integration steps are discreet and not continuous, you miss the collision. Correct?

There is a lot of research on this problem. One of the more common approaches in 3D is to consider the two ball points the hemispherical caps to a cylinder along the line of motion. You then do the collision with the cylinder and collision boundaries.

A simplification of this for you would be this:
Consider the motion of the ball from starting to endpoint as a line segment. Do a distance test between the segment and any boundaries close (by some low order method). If the nearest point is smaller then the ball radius, you hit at that point.

The correct solution (that is numerically correct) is to back up the sim to the time of collision, resolve it, and restart from there.

Make sense?
-Jeff

Share this post


Link to post
Share on other sites
If you already have a ''line-to-line intersection'' algorithm, then

LineA = (ballstartX,ballstartY) to (balldestX, balldestY)
= current position to next position
LineB = any length of boundary.

Where A crosses B gives the collision point.

Do you really need more than this? (I couldn''t use that link above btw)

Regards

Matt

Share this post


Link to post
Share on other sites
You can use what is called a ''sweep test'' to solve this problem. This solves for normalized time when the distance between the center of the circle and the line segment is less than the radius. This requires solving a quadratic equation (meaning there can be two correct answers, the lower of which is when the circle first contacted the line segment).

This Gamasutra article has a number of useful sweep tests. The first is a sphere/plane sweeptest, that you should be able to use as a guide to derive the 2d formulas.

- genovov

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
There is one trick you can use if your balls are all the same size or a limited number of sizes.

For a ball of radius R, create a version of your bounding walls where they are moved towards the playing area by R times the normal of the wall.

For example. Lets say you have a bounding box of size 100 by 100. The coordinates of each corner of the box is (0,0), (0, 100), (100,100) and (100, 0). The size of your ball is 5. Then to compute your bounding walls, add the radius times the normals.

The wall going from (0, 0) to (0, 100) has a normal of (1, 0). The new coordinates are (5, 0) to (5, 100). The next wall from (0, 100) to (100, 100) has a normal of (0, -1). It's new points are (0, 95) to (100, 95). Etc. Parts of the walls are now outside of the bounded area. (i.e. (5, 0) to (5, 5)). These parts can be discarded. Your new bounding box has coordinates of (5, 5), (5, 95), (95, 95), and (95, 5).

So, what does this give you?

Well, now you can do a simple point sweep as you are doing now since all the walls have been adjusted to the radius of the ball.

I hope I explained it well... probably not.

(The circle sweep test works just fine too)

Note:

I remembered on problem with this method that might make it unusable in your case. With sharp corners, like the one in your drawing, the tip of the corner gets extended far beyond what it really needs to be. Oh well...

Tim


Edited by - timsmith on 4/8/00 8:06:46 PM

Share this post


Link to post
Share on other sites
There''s another way that I heard of, but I''m not sure if it''s true. If you draw lines from all of the points on your object to a point on another object and it adds up to 360 degrees then there is a collision because the point lies within the object. If it''s more than 360 degrees then it''s outside the object. But this doesn''t work for concave polygons.

Share this post


Link to post
Share on other sites