In the previous article regarding blocks, we outlined Octrees, how they were used, and what the reasoning was behind their employ. Now, in this article, we’ll discuss how the block system is being refactored and optimized.
Octrees as mentioned, are essentially a large invisible cube, which can be subdivided into a set of smaller chunks that are spatially organized, in order for the program to be able to organize sparse points of data, in relation to other points of data. Octrees are really excellent at efficiently handling sparse data. An example of sparse data, is having only a handful of colliders in one part of the map, and several hundred concentrated far away on the other side of the map, with large swathes of the area with no colliders present.
So an Octree would have to generate a low amount of subdivisions to sort the three colliders, and concentrate on creating as many subdivisions as necessary for the large concentration of colliders to minimize the number of colliders within each Octree leaf. The resulting data structure would end up with a high level of subdivision on the side with many colliders, and a low level of subdivision on the side with few, and therefore it would have a great overall memory efficiency, as the program would not eat up memory to remind itself that there is nothing present in redundant subdivisions. However, when there is a dense amount of data present, an Octree isn’t an optimal structure to be able to efficiently store this data.
Due to the n-dimensional nature of Octrees, and having as many tiers of subsections as necessary as to organize the dataset, it can often take a large amount of overhead to organize the position of a single point of data. This eats up a lot of performance and causes the placement of dozens of blocks to bog down the system, as the program has to keep track of many multiple layers of organizational information.
How an Octree creates more subsections and layers within layers for a "geometrically-rigid" form
The model of Buddha demonstrates how the layers of the Octree become complex and practically inseperable when dealing with "Geometrically-fluid" forms, such as this, becoming much more memory-intense
An alternative to this situation would be using a grid array, where to keep track of the placement of blocks is relatively simple, as they all either activate or deactivate pre-determined subsections of a grid. There eliminates the complexity of having to create and collapse multiple layers in order to track blocks on the map. However, a grid array still does not solve the problem of memory usage. It consumes a large amount of information, regardless if there is something or nothing in the grid, resulting in a large amount of useless information being consumed in order to explain that there is nothing there.
So in an effort to alleviate this memory issue, a hybrid solution was sought out. The hybrid being that there would be an Oct-tree like structure that consisted of three tiers: The chunk, which spanned the entire area of a page, the subchunks (AKA Octree leaves), which would be the result of an evenly subdivided the page, and the actual blocks and cubes themselves. So this imposed structural limit to the Oct-tree would allow the system to be able to efficiently navigate the structure in no more than 3 steps. It would say only need to take one step, if the block being placed was in the same subchunk as the last block that was being placed. As well, if the block being placed was outside the relevant data subchunk (IE, in a valley further down the map), it would only take three steps (or layers) to find and place that block, by travelling outside the subchunk and into the superchunk tier. This allows the program to still collapse and remove all irrelevant bits of data, and not have to continually use up memory taking note of where all the non-active chunks are, like an array would; all while being able to simply and quickly move to different locations in a memory efficient way, when things get dense, data-wise. So this hybrid gives us the flexibility of an Octree, with the simplicity of a Grid, without taking up too much memory.
Thanks for reading, hope you enjoyed it!
-- Stephen "Hatchling" Smolley