Sonic Battle (GBA) Renderer Series - Culling

Posted on September 17, 2019

Table of Contents


Welcome to the twelvth article of the Sonic Battle (GBA) Renderer series.


Overview

The GBA can only render a finite amount of walls and sprites. To make the best use of this capacity the game eliminates any game element that isn’t visible on the screen from the render list.

Approach

I don’t know the exact method that was used in the game to determine screen visibility. But here’s my logic:

  • Character culling is blazing fast and hierarchical culling (cells, quadtrees) would only slow it down. Plus characters naturally gravitate towards one another and rarely leave the player’s screen, so the overhead wouldn’t be worth it.
  • Hierarchical culling doesn’t benefit us much for walls either because the levels are small and the camera often covers at least a fourth of the space. Also note that half of all walls can be eliminated right off the bat using only the camera heading (backwards culling).
  • The best culling representation for walls are camera-facing axis-aligned bounding rectangles. They match the shape closely and reduce the problem to two dimensions (so we don’t need to consider the frustum as a 3D box which would be more complicated and expensive).

Bounding rectangles

The camera-facing axis-aligned rectangles for these two walls:

Look like this:

To compute the width and height of a bounding rectangle we use our old pals the wall affine matrices (in camera space) from the wall rendering article:

Remember how walls can face only one of four directions and how visibility and affine matrices for each direction are cached for rendering?

This pays off now as well because we can immediately cull walls facing away from the camera just by checking which direction they belong to. Also we get to re-use the affine matrices:

  • WallAffineMatrix = WallAffineMatrices[Wall.Direction]
  • For width the red (horizontal) vector’s X component is used: CullWidth = Texture.Width * WallAffineMatrix[0].X
  • For height the green (vertical) vector’s Y component is used: CullHeight = Texture.Height * WallAffineMatrix[1].Y

But that’s not all. This hasn’t accounted for the height of the shear/slant (orange):

Shearing in the Y axis corresponds to the Y component of the red (horizontal vector):

So to find the total shear height we find the largest possible x coordinate and multiply it by s. The maximum x coordinate is at the edge of the wall - so it’s the width we have just computed earlier.

We discard the sign because the shear factor can be negative, resulting in:

  • ShearFactor = Abs(WallAffineMatrix[0].Y)
  • CullHeight += CullWidth * ShearFactor

Screen-space overlap

Once a bounding rectangle is determined it’s only a matter of checking if it’s oustide the screen’s bounding rectangle.

The rectangle is culled if any of these conditions is met:

  • (position.x - width / 2) > SCREEN_WIDTH / 2 (the left edge is to the right of the right bound)
  • (position.x + width / 2) < -SCREEN_WIDTH / 2 (the right edge is to the left of the left bound)
  • (position.y - height / 2) > SCREEN_HEIGHT / 2 (the lower edge is above the top bound)
  • (position.y + height / 2) < -SCREEN_HEIGHT / 2 (the top edge is under the lower bound)

There are micro-optimizations that can be added (such as computing bounding rectangle width + checking horizontal overlap before doing the same for height/vertical) but I don’t think there’s much to gain.

Characters

Characters don’t have any transforms (besides translation) relative to the screen so the screen-space overlap step can be directly applied using the sprites’ raw width and height.



The next article discusses a draw order bug I discovered in the original renderer which I named the “Escher Sandwich”.