The Block Algorithm is a technique used in virtually every "Block Engine", but the Quad Algorithm is

Consider an array of 5x5x5 blocks:

We can do much better than 150 quads. We can do this by "merging" adjacent 1x1 squares that are on the same plane and have the same texture to form a single rectangular quad. Doing this in the above example, only 6 quads would need to be sent to the graphics card! That is much better than the naive algorithm that uses 750 quads! Let us call this algorithm (of merging 1x1 squares together that have the same texture, are on the same plane, and are facing the same direction) the

The following is an example of the quad algorithm in effect, where different quads are colored randomly for demonstration:

- AddSquare(x):

call AddQuad(x). - RemoveSquare(x):

find the quad y that contains x,

split y into subquad pieces where x is one such piece,

remove y from the data structure,

and call AddQuad(p) for each piece p of y other than x. - AddQuad(x):

Determine if x can be merged with any other quad y.

If so, then call RemoveQuad(y) and then call AddQuad(x merged with y).

If not, add x to the data structure. - RemoveQuad(x):

Remove the quad x from the data structure.

- A data structure, such as a 2D-interval tree, would need to be used to efficiently perform the step of determining which quad contains a particular square.
- To determine if one quad can be merged to another quad efficiently, quads need to be queried by their edges.
- When breaking up a quad into smaller pieces (at most 5 subquads), there are various cases which makes this tedious to program.

We have been treating blocks as if they have the same texture on every side, but of course this is not necessary. We could have a system where the texture of each side of a block (top, bottom, front, back, left, right) is determined by its type. See, for example, the above picture. Another thing we might what to do is manually change the texture of one side of a block (as if we were putting on wallpaper). We might want to do this to make the walls of the outside of an indoor map invisible so we do not waste time rendering them (this process is described here). It is clear how to change the interface of the Block Algorithm to accomodate this change.

Unfortunately, there is a slight clash between the idea of chunking and the Quad Algorithm. That is, if we want to use chunks in the ways described above, then every quad must be contained completely in a chunk. To accomplish this, the Quad Algorithm would be performed for each chunk. What is annoying is that more quads may be needed to render a scene than is theoretically necessary. This is problematic in the case that the block would to be rendered is extremely large but also quite homogeneous, so only a few quads are needed in theory. It is possible that I am the only person bothered by this issue.

If one is devoted to the idea of using the quad algorithm globally and not have any chunks, then the problem of view frustrum culling becomes quite a headache. Determining whether each individual quad is outside the view frustrum will take too long, so multiple quads need to be considered at once. Conceivably, one could impose some data structure on the collection of quads to speed up this procedure, but this will likely be more trouble than it is worth.

Since chunking is so essential, it seems like the best idea is to perform the quad algorithm within each chunk and not worry about how the chunking may theoretically limit the scenes that can be rendered.