The Chunktree is the data structure holding the geometry of all LOD levels. It is build up on loading. At runtime, the correct mesh parts are choosen from it. In this article, the loading phase is described.
The whole geometry is hold in the Chunktree which is an octree. The root of the tree holds the whole volume in the lowest LOD level. The next level of the tree splits the volume into eight more detailed octants. And each of this children has again eight children dividing the parent again into eight octants. Figure one shows the Chunktree of a sphere with three LOD levels.
1: The Chunktree of a sphere with three LOD levels
One exception is the second last level. Each chunk of it only has one child instead of eight with the same size as the parent but more details. This is an optimization as later all children of the second last level chunks would have been drawn anyway if they get selected. So the geometry for the otherwise needed skirts can be saved here.
Having all chunks completly separated has the advantage, that each of them can be loaded independently and in parallel. Also paging gets possible with approach.
So each tree level encloses the whole volume and the deeper the tree is, the smaller and detailed the chunks are. The tree has as many levels as desired LOD levels. Every level of the tree is generated with a specified, own approximated geometric error.
All in all, this is the pseudocode to generate the tree:
generateChunkTree(chunkCube, level) {
invisible = true;
if (Abs(centralIsoValue) > chunkCube.diagonal()*1.5) {
return;
}
delta = chunkLevel * errorMultiplicator * baseError;
octree = createOctree(chunkCube, delta);
dualGrid = createDualGrid(octree);
triangles = createTriangles(dualGrid);
invisible = triangles.count == 0;
if (level > 2) {
children[0].generateChunkTree(chunkCube.children[0], level - 1);
children[1].generateChunkTree(chunkCube.children[1], level - 1);
children[2].generateChunkTree(chunkCube.children[2], level - 1);
children[3].generateChunkTree(chunkCube.children[3], level - 1);
children[4].generateChunkTree(chunkCube.children[4], level - 1);
children[5].generateChunkTree(chunkCube.children[5], level - 1);
children[6].generateChunkTree(chunkCube.children[6], level - 1);
children[7].generateChunkTree(chunkCube.children[7], level - 1);
} else if (level > 1) {
children[0].generateChunkTree(chunkCube, level - 1);
children[1] = 0;
}
}
First, an invisble flag is set to true and then a check is performed, whether the current chunk is near enough to the isosurface and has the chances to create triangles. Then the accepted geometric error is calculated and with it the octree of the chunk created. After creating the dualgrid out of it, the triangles including the Marching Squares Skirts can be generated.
The last step for this chunk is to revisit the invisble flag by checking whether triangles got created. It will be used while drawing as an optimization.
If the current chunktree level is greater than 2, the chunk is divided into eight children and the process starts recursivly again. If the level is greater than 1, the second last level has been reached and only one child is created.
