RENDERING - User Interface Programming for Games - page 123

3.13B INARY S PACE P ACKING
Binary space packing is the action of taking some area of space and subdividing it with the
goal of finding the best organization of data within the available space. This is an optimiz-
ation intended to reduce the number of context switching in the graphics device, changing
renderingstates,rendertargets,andissuingmultipledrawcallsalladduptotheoveralltime
cost of the game's frame. For world space text rendering, we can take advantage of this bin-
ary space packing algorithm that will allow us to batch as much as text as we can into a
single render target in order to render some or all of it in a single draw call.
We will proceed by analyzing the use of this binary space packing algorithm as applied to
texture packing. In this case, we have a finite amount of 2D space in the form of a texture,
and we wish to store rectangles of arbitrary widths and heights into it.
Thefirststepincreatingthebinaryspacepartitioniswhenweinsertsomeamountofdatain
the shape of a rectangle. We will divide, or partition the free texture space by two as many
times as needed until we can fit the rectangle, or until we find that it is impossible to fit it.
If we are unable to fit the rectangle into the available space, we would have to incur the cost
of creating additional render targets, or perform individual draw calls for any items that did
not fit. Given a large enough render target, this situation should not occur frequently.
Figure 49 - Inserting a 512x512 texture into a larger texture by using binary space partition.
First, we will determine that there is no exact fit within the texture, so we will split the tex-
ture vertically using the items' height and trying to fit it again into the first child in the new
partition, if it fits vertically, the next step is to try and fit it horizontally, the process is the