Predicting circle line collisions
In my previous collision detection post (in what I expect will become a series), I talked about predicting whether two objects would collide in between frames. This is to avoid the situation where the objects are moving so fast that they pass through each other before you’ve had a chance to see if they’re overlapping. This is often known as a sweep test (amongst other things!)
And I showed how you could predict collisions between a 2D circle and a vertical line but what about lines that aren’t vertical? How do you work out collisions between circles and lines of any angle?
Here is where vector maths comes in, so if you haven’t looked at it since school, here’s a great article that will tell you the basics (based around Processing but you’ll get the jist). And for further study you can look at this very comprehensive guide from the CCSU.
So we have our circle flying around and we want to test whether it’s colliding with the line, in other words are they overlapping? Logic dictates that if the distance from the line to the centre of the circle is less than the circle’s radius then it must be penetrating (stop giggling at the back!). But how do we find this distance?
When I started solving these sort of problems I’d use trigonometry: right angled triangles and sine cosine and tan. But I later learned that you can use some magic vector maths to do the same thing much much faster. But first there are some things you need to know about :
Dot product
The dot product of 2 vectors is a number that varies depending on the angle between them. It’s called the dot product because it’s sometimes represented with a ‘˙’ symbol. It’s calculated by multiplying the various elements of the two vectors together. Use this interactive demo to see how the dot product changes as you move the vectors around.
To view flash content visit the original post
In particular, notice how the dot product is negative when the angle between the vectors is greater than 90º and positive when the angle is less than 90º. Also note that the dot product is 0 when the vectors are perpendicular to each other. This will be very useful to us later on.
Normals
Simply put, a normal is a vector that is at a right angle to a line, and it’s usually a unit vector, ie a vector that is 1 unit long.
Shortest distance between a line and a circle
Let’s say we have a line defined by two points P1 and P2, the line normal is N, and our circle’s centre point is C. We also have the vector between P1 and C, called (rather unimaginatively) P1C.
To find out the distance between C and the line you simply get the dot product between P1C and N. So if this distance is less than the radius of the circle then we know we’ve got an overlap and therefore the circle is colliding with the line!
You can see it here in this example, click to drag the points and the circle around.
To view flash content visit the original post
Predicting collisions between a circle and a line
So you know the distance between the line and where the circle is now (lets call it d1), and what the distance will be in the next frame (d2), but what we need to know is how far along were we between frames when (and if) there will be a collision. A collision occurs when the distance is equal to the radius, and we’re trying to find a value for t (time) where t = 0 now and t = 1 in the next frame.
We can use this formula :
current distance = d1 + (d2-d1) * t
so when d = the radius r :
r = d1 + (d2-d1) * t
and with some algebra even I can just about manage we can extract t :
r-d1 = (d2-d1)*t (r - d1) / (d2-d1) = t
So if t is between 0 and 1 we know we collided between frames!
Whew. This blog post is getting epic. But we’re not quite there yet, we still need to work out where the circle is at the point of collision: we take the vector between C1 and C2, multiply it by t and add it to C1.
Here’s an example that shows this all in action :
To view flash content visit the original post
I’ll continue this series further to explain :
- collision reactions
- collisions between moving circles
- and all the same for 3D – spheres and planes!
I really hope this is useful, it’s actually really hard to explain this in writing, so let me know if any of it is unclear. And of course I’ll be explaining this in more detail in my upcoming Flash Game Programming training course.
Related posts:
OMG, this is so useful! thanks!
I’ve always had an awful time working with vectors, specially cause I never really understood the operations involved, for instance, why a dot product is just a number (and not another vector) and what does it represents in “cartesian” terms? ^^… Those links about vectors seem great.
A dot product is just a single number (or a scalar) because it’s the product of the various elements of the vectors added together. As the vectors are described in values along each axis (x,y) they’re known as cartesian. This is as opposed to vectors in polar format (a length and a rotation).
Im still planning to implement this technique in AS3, but my Math isnt good enough (yet): http://www.metanetsoftware.com/technique/tutorialA.html
(i have no idea if it’s better/worse/different then what you’re doing, but
“Separating Axis Theorem” sounds impressive right?
I’ve used SAT before – it’s a great technique, I think it’s safe to say it’s more commonly used for intersection tests between polygons. I’m not sure if you can do a sweep test with that method?
Is this technique more efficient than doing a coordinate rotation?
Are there any other differences between the two techniques?
I haven’t done any benchmarking but I this method would definitely be faster than any rotational methods, at least if the line’s normal is precalculated (calculating a normal requires a processor-intensive square root). Dot products are very quick to calculate, if we have two vectors (x1,y1) and (x2,y2) the formula is :
so it’s very quick!
Sorry I didn’t get back to you on the last post. This is great. Those explorations are really clear.
Before I was talking about testing for point collision with a bounding box by taking the dot product of the motion vector and each axis then comparing them to the axis-oriented sides of the bounding box.
I like the direction you’re going with the circle bounding a lot, though.
I implement this kind of collisions predicting in my papervision 3d tour.. to create camera slide effect along the wall..
http://dreamflashstudio.com/my_lab/my3dTour/
Yes of course, this method is perfect for the “slide” effect (and it works in 3D but more about that later!). Are you doing collisions with every triangle? Great demo!
no, I didn’t do for every triangle, I just create a invisible plane object along the wall. that’s all. The challenge is papervision detect a hit for a plane abject as a cube. So I use this method to do “really” plane detection. And add extra calculation to make sure camera far little bit from wall to avoid clipping issues in 3D
Something wrong with the first example, the simple dot-product one.
If you use two vectors of length 1, the resulting dot product should be inside the range -1 to 1, but I can get it all the way to 20.
I think you’re working in pixels instead of grid units or something.
Great tutorial otherwise
that’s weird, I fixed that ages ago! I guess it’s version control issues. Fixed again now!
Gee, this is a lot simpler than my method I was using! But there’s still something wrong…
What happens when the ball hits the tip of a line segment? You assume that the line goes on forever, but this is rarely the case in games. If the ball hit the tip of a line segment, the distance between the ball center and the normal line would be less than the radius of the circle, and the distance between the ball center and the tip would have to equal the radius of the circle. I don’t know how to do that
Um, I was thinking about the problem for a bit; I might have come up with a solution:
First, do the circle-line collision normally. Then find, if the circle collides with the line, the point on the line closest to the center of the circle. If this point isn’t between the 2 corners of the line segment, ignore the collision.
Second, do a circle-circle collision with the two corners of the segment, and assume the corners are circles with radii of 0
yes, that’s exactly it, check the endpoints as circles. Good luck!