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.