October 28, 2016

If you read one article about Rectangle-Rectangle Intersections read this one


I've made an autonomous traffic intersection in which self-driving cars can find their way through the intersection faster than if the intersection had traffic lights. How much faster you might ask? The answer is about 10 seconds according to my simulations. The problem is that if you add pedestrians and bikes to the equation, everything will break down, but that's a later problem!

To be able to know if a self-driving car can drive through the intersection without colliding with another car, you approximate each car with a slightly larger rectangle (to be on the safe side) and then you predict where the rectangle will be in the future with your favorite integration method. Each integration step you test if the (pink) rectangle is intersecting with any of the other (pink) rectangles. It looks like this:


Using a fast rectangle-rectangle intersection method is important to make the algorithm as fast as possible. But how can you find out if two rectangles with orientation in 2d space are colliding? The first idea I had was to divide the rectangles into two triangles and then detect if any of the four triangles are intersecting. If you google 2d triangle-triangle intersection, you will find that one way of doing this is:
  1. Approximate the triangles with rectangles and check if they intersect with an AABB-AABB intersection algorithm. These approximated rectangles have no rotation (they are called OBB if they have rotation) so you can't use this algorithm to solve the main problem, but you can use it to speed up the algorithm.
  2. If the approximated AABB rectangles are intersecting, then test if any of the edges of each triangle is intersecting with any of the edges of the other triangle with a line segment-line segment intersection algorithm.
  3. If the above fails, but the approximated rectangles are intersecting according to the first test, it means that one of the triangles could be inside the other triangle. To find out if that is true, you test if one of the corners of the triangle is inside the other triangle (and vice versa) with a point-in-triangle intersection algorithm
If the above sounds complicated I've written a more detailed explanation (with C# code in Unity) here: Are two triangles in 2D space intersecting? And maybe this image explains it better:


The problem with testing if two rectangles are intersecting by using the triangle-triangle intersection algorithm is that you maybe have to do the above four times. What if there is a better way? One other way to test if two rectangles are intersecting is using the Separating Axis Theorem, or SAT

SAT is a little bit more difficult to understand, but when you have understood the basic ideas (and have repeated both the dot product and vector projections), you will be able to apply the intersection algorithm to all convex polygons. So it's possible to test if both triangles and rectangles are intersecting with SAT, because a rectangle is a polygon with four sides. If you want a more detailed explanation of the SAT algorithm, I've written a longer article here: Are two rectangles with orientation in 2D space intersecting?

But what I found is that even though SAT includes fewer steps, it's actually slower. The reason is that the triangle-triangle intersection algorithm doesn't always need to go through all steps to see if the triangles are intersecting. So an important lesson is to take out your timer and test how fast each algorithm is. But as today's Momentum quote said: "Live as if you were to die tomorrow. Learn as if you were to live forever" at least I've learned something new!

No comments:

Post a Comment