Internal and External Squares

Home --> Programming Projects --> Block Engine --> Internal and External Squares

In this page, when we say a square, what is meant is the side of a solid block that is adjacent to an empty block.

Consider the image above (it was taken from a version of Fractal Block World where chunks were 8x8x8). The picture shows an individual chunk with the "internal squares" shown in green and the "external squares" shown in blue.

When a chunk is being created, we can create all the internal squares because we know all the relevant block information. However, we cannot create the external squares yet until we have the appropriate chunk adjacent to the given chunk.

In the modern version of Fractal Block World, a chunk is 16x16x16. You might think that only 1/16 (or 6.25%) of squares are external squares. However in most worlds the fraction of squares that are external is between 10% and 20%.

Do We Need To Store The Squares In Memory?

We need to know the squares to create the quads (see the Quad Algorithm). However if we know the quads then we can recover the individual squares. So one might ask if we really need to store the individual squares in memory. My conclusion is that we do not need to, but we might as well store them to simplify the situation. Indeed, as long as we are storing individual blocks in memory (that are not of the default type for the chunk), then we might as well store all indivual squares as well.

Creating Internal Squares

Once we know what are all the blocks in a chunk, we can then create the internal squares.

Every chunk has a "default block type". When a chunk is created, we only specify the blocks whose type is different from the default block type. We use one of two algorithms to create the internal squares, depending on the number of blocks that are not of the default block type for the chunk.

The "sparse" algorithm: Iterate over all of the SOLID blocks of non-default type. For each of the six directions, create a square on the block iff the adjacent block position is of an empty type.

The "non-sparse" algorithm: Iterate over ALL block positions in the chunk and create the squares appropriately. We actually consider the three axes separately: X, Y, and Z. Suppose we are considering the Z axis. Then we have x go from 0 to 15 and y go from 0 to 15. For each such (x,y) pair, we have z go from 0 to 15 and in the process we create all SIDE_Z_POS and SIDE_Z_NEG squares for that column (this involves querying the type of all blocks in this (x,y) column). Note that with this non-sparse algorithm, we query the block type of each position exactly 3 times (one time for each axis).

Note that if we have a separate thread generating the blocks in a chunk, we can easily have that same thread create the internal squares for the chunk.

Creating External Squares

Creating external squares is more complex than creating internal squares, but luckily there are much fewer external squares.

Something very simple but quite inefficient is to pretend all chunks adjacent to a given one are empty. This will likely create external squares that are actually blocked by solid blocks in adjacent chunks. So we would be rendering squares that are actually blocked. I would not recommend this technique.

Suppose we are about to create the external squares for a chunk in a particular direction. So, we need to get the adjacent chunk and query its blocks. However what should we do if the adjacent chunk has not yet been created? MOST OF THE TIME that this happens, the adjacent chunk is farther away from the player than the current chunk in such a way that the player would not be able to see the external squares even if they are created. So it would make a lot of sense to simply not create the external sqaures in this situation. However, in Fractal Block World the world is more complex so we choose to create the external squares as if the adjacent chunk (that is not yet loaded) is entirely filled with empty blocks.

As mentioned, the system that generates a chunk (in a separate thread) cannot create the external squares because it does not have enough information. However the system can create external squares pretending that the adjacent chunks are entirely empty. Call these the "stump squares". The main thread can then render these stump squares until the main thread is ready and able to create the external squares (for one side of the chunk).

Vertex Buffer Objects

What vertex buffer objects should we use to render squares (if we decide to do rendering this way)? Let I represent "internal" and "E" represent "external". We can have one vertex buffer object (VBO) for each pair (t,g) where t is a texture and g is either I or E. The reason for subdividing squares into the categories I and E is beccause the I vertex buffer objects will be larger than the E ones and they will be changed less often.

Here is a more complex system. Let I represent "internal" and let E1, E2, E3, E4, E5, E6 represent the external squares, grouped by side. Let E1s, E2s, E3s, E4s, E5s, E6s represent the "stump" version of external squares, group by side. We can have one vertex buffer object for each pair (t,g) where t is a texture and g is one of I, E1, E2, E3, E4, E5, E6, E1s, E2s, E3s, E4s, E5s, E6s. With this method, the thread that originally generates the chunk can create the I and E1s through E6s vertex buffer objects and the main thread can create E1 through E6 vertex buffer objects when ready and able. During each render cycle, the main thread will not render both E1 and E1s. Similarly, it will not render both E2 and E2s, etc.