I suppose it is unrealistic to suggest that performance is never an issue when creating a video game. Since the better a game performs, the more graphical tricks you can cram up your games proverbial sleeves. But with the speed of modern computers, 2D games tend to not require much optimization. And as they primarily use tile-based graphics, it is relatively trivial to determine which tiles in the level are on screen (and therefore should be drawn), and which are not.

However, there are some newer 2D games, such as Braid, or Aquaria which use a entirely different method for their graphics which is not tile-based, but instead uses images which can be repeated positioned, rotated, and scaled arbitrarily to build a level. These images are rendered to the screen using modern 3D graphics hardware, which—being designed for 3D games—is rather fast for this application. Even still, there can be quite a large number of these images building up a level, so it is useful to devise an accurate and speedy method for determining which objects are on screen, and which are not.

Ideally, our solution should draw only the objects that are completely or partially on the screen and cull (or do not draw) the ones that are completely off the screen.

One of the simplest and fastest types of collision detection is between two axis-aligned rectangles. Therefore if we simplify the collision detection between the possibly rotated assets and the rectangle of our camera’s viewing portal into a axis-aligned rectangle-rectangle collision, then that would be ideal. So how does one simplify an arbitrarily rotated rectangle into a axis-aligned one. One solution is to bind the asset with a square having sides at least as long as the longest side of the asset.

However, this solution does not bind the object accurately enough. The resulting square is too small, and when the asset is rotated, it’s corners will still poke outside the bounding box. If this square were the basis for visibility, objects might not be drawn when they should still be visible. So we need a square that is larger, but how much larger?

Taking a cue from an totally unrelated article on simulating motion blur, There is a fairly simple technique for determining the maximum area which a rotating quadrilateral may take up. A circle can be efficiently be bound inside a square with sides the length of its diameter. Since the area occupied by a rotating quadrilateral forms a circle, by determining the length of the diameter of that circle, we will have the size of our bounding box. Luckily, the diagonal from corner to corner of our quadrilateral is the diameter of that circle, therefore we simply need to find the length of that diagonal. This can easily be determined using the Pythagorean Theorem.

C²=A²+B²

 

In order to solve for the hypotenuse C, we need to know the lengths of sides A and B, these are fairly simple to find, as they directly correspond to the width and height of our image asset. The length of side C is the square root of the sum of the squared width and height of our asset. We then bind the object inside a square having sides of length C. This bounding square will completely cover the area of the circle occupied by our rotated asset, and therefore will be exactly the right size for our simplified, axis-aligned rectangle based culling technique.

Now, although rectangle-rectangle collision detection is one of the simplest types of collision detection, there are a few pitfalls that a beginner can easily fall into when attempting to devise his implementation.

Perhaps the most obvious, but incorrect solution is to test if each of the vertices, or corners, of the rectangle is inside of the other rectangle. Since point-rectangle collision detection is fairly simple, this seems like a good idea. All we must do then is check if each point (x,y) is inside the bounds of the other rectangle. For example, if we label the sides of the rectangle as x1, x2, y1, and y2. Our solution would work somewhat like this:

for each point in each rectangle:
if ( other_rectangle.x1 < this_rectangle.point.x < other_rectangle.x2 and other_rectangle.y1 < this_rectangle.point.y <
other_rectangle.y2)
then a collision has occurred.

However, in practice, there are certain situations in which two rectangles may be intersecting, but neither rectangle has
any vertices inside of the other. In these particular situations, our solution will fail to detect the collision. Because of this inaccuracy, we must devise a better solution.

Ideally we want to instead test if each of the sides of the rectangles are inside of the other. This concept, although
relatively simple to the human mind, can be somewhat non-trivial to implement correctly inside of a computer. So in order to simplify the problem somewhat, and build up an understanding in the mind of the reader. We will bring this collision detection down into the realm of a 1-dimensional universe. A one-dimensional universe exists entirely on one line. Therefore, we will be only determining collisions between line segments on that line. For the sake of clarity, our illustration shows this one dimensional universe exploded into two dimensions.

In one dimension, testing for collisions between lines based on the end points of each line does actually work in all situations. Therefore, we can accurately determine if two lines are intersecting simply by seeing if either point on one line is between the two points of the other line.

For each line:
if (other_line.x1 < this_line.x1 < other_line.x2 or other_line.x1 < this_line.x2 < other_line.x2)
then a collision has occurred.

This principle does not apply to lines in 2D, however. But by extension, it does apply to rectangles. Instead of testing the points at the corners of the rectangles, we must test each axis of the rectangle independently. In other words, we split the problem up into two one-dimensional line segment collision detection problems. Consider the left and right sides of each rectangle to be the end points of a onedimensional line segment. Do the same for the top and bottom sides. Then check to see if each of those segments intersect. If there is at least one intersection on each axis for at least one of the rectangles, there is an intersection. This is how we will solve our problem:

For each rectangle:
if (other_rect.x1 < this_rect.x1 < other_rect.x2 or other_rect.x1 < this_rect.x2 < other_rect.x2) and (other_rect.y1 <
this_rect.y1 < other_rect.y2 or other_rect.y1 < this_rect.y2 < other_rect.y1)
then a collision has occurred.

Although I have attempted to make these concepts as easily understandable for a beginner as possible. It is likely that I am still talking over many peoples heads. For this, I apologize. However if you can gain any insights by my technical ramblings, then I would be delighted to have helped. As shown in the graphs below, by implementing the techniques described here, I gained a significant performance boost when drawing a level containing around 400 objects.

The two different “Culling” bars shown are simply different methods of solving the pythagorean theorem, either by using a function which returns a number to a power of x, or simply by multiplying the number by itself. Although one would think that the square root function would be the biggest performance hog in this culling technique, my experimentation showed that eliminating it by leaving my asset’s bounding rectangle size as a squared value and squaring all the other values I compared it to was actually much slower, at 326 frames per second even being slower than just drawing all of the assets in the level un-culled.