In my previous collision detection post, 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 :
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.
[kml_flashembed publishmethod=”dynamic” fversion=”9.0.0″ movie=”/wp-content/uploads/manual/2010/physicstutorials/DotProduct.swf” width=”560″ height=”400″ targetclass=”flashmovie”]
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.
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.
[kml_flashembed publish method=”dynamic” fversion=”9.0.0″ movie=”/wp-content/uploads/manual/2010/physicstutorials/PointLineDistance.swf” width=”560″ height=”400″ targetclass=”flashmovie”][kml_flashembed]
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 :
[kml_flashembed publishmethod=”dynamic” fversion=”9.0.0″ movie=”/wp-content/uploads/manual/2010/physicstutorials/CircleLinePredictive.swf” width=”560″ height=”400″ targetclass=”flashmovie”][/kml_flashembed]
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 game programming training courses.