Result after 2 weeks:
The coding challenge is over and the result is a prototype of a decent voxel engine. It now has a visual hull construction so only those sides which are clearly visible are drawn. The reduced the vertex count of each mesh so one single mesh can cover a depth of 5 which improved the rendering performance a lot. Now It still has 700+ frames per second after heavy destruction instead of droping to 30 due to the insane vertex count. The visual hull construction now also uses an different approach where every thread covers one mesh which means tasks are spread evenly across all cores (my computer has Intel I7 2600 which has 4 cores) anbd less overhead caused by multithreading.
Most difficult parts so far:
The most difficult part was the visual hull construction and the merging of nodes which could still be buggy. For the visual hull construction, the neighbours of the current voxel are required and must be evaluated inside the octree. These steps are very difficult to debug as the final result often does not look like as expected. The left image show a view inside the whole voxel structure and there are clearly sides visible allthough they are fully obstructed. The reason for this is because the neighbor of such side was subdivided in the past and may not be fully obstructed (case 4 below).
Getting the neighbours inside an octree:
Hashing the neighbors of a voxel in an octree can assume several cases which are:
- The neighbour has the same parent as the current voxel: Easy to evaluate
- The neighbour does not share the same parent.
- Neighbour does not exist because it is occupied by an large node
- Neighbour exists but is not a leaf.
The first case is straight forward and can be obtained from the parent. The second case is more complicated as now the search has to hash the neighbour in a recursive way while storing the indices. Then move downward until the neigbour is found. For my master thesis I may have to draw an image to ilustrate this -, because it uses the divine power of recursion 🙂
Case 3 is similar to case 2 but it cannot traverse down fully because the voxel of the given depth does not exist. Now there is the option to force the creation or just return the ID of the last voxel. Forcing the creation is not required for visual hull construction.
Case 4 is also similar but it could traverse deeper because the target depth is not the final one. For visual hull construction, this means that the side must be drawn as it may not be fully covered. It is an edge case which took me a whole day to find out as the result are occasional holes inside the geometry.if it is not handeled.
The visual hull construction currently does check the 6 adjacent neighbors and only draw a side if it is not fully obstructed. More complex algorithms would also require more neighbours but before I implement this, basic things must work without special features 🙂
Merging obsolet nodes:
This step was extremely bugged as the glitches occur as small voxels being invulnerable.to destruction. Currently I dont saw any of them but it could still remain bugged. In theory this step is very simple as the children of a voxel can be merged if they share the same ID. So if a voxel changes, the parent must be checked if it is possible to merge its children together and if it is capable of doing so, merge them.
The merge itself is simple as all chidren are destroyed and the ID becomes the ID of the original voxel which should change. If a merge happened, it could be possible that now its parent can also do a merge so it has to be checked upwards using recursion.
Now all meshes which represent those destroyed voxels must be updated and if the voxel was the root of a mesh piece, The unity object carrying the mesh must be destroyed and this was the most difficult part. I solved this by assignign a special ID to voxels which are destroyed. If it is the root of a mesh, it is added to the visual hull generation queue and is resolved there.
Special voxel IDs
Special voxel ids are used to mark voxels which have a certain state. For example if a voxel has children, its ID becomes 0. If it disconnected from the octree due to merging or destroying, its ID becomes 1. ID 2 is an empty leaf node which should not be rendered at all. ID 3 – 255 are free to use for fancy stuff. With these states, null checks are greatly reduced which also increase performance.
Future Improvements: Data Oriented Design
With data oriented design, real efficient code is possible which is cache friendly. Unity 2018.1 now has the Burst Compile which is able to double the performance. Therefore the Octree must be represented as Struct instead of Class. Structs cannot have refrences to other structs of the same type because it would result in a infinite declaration. However with NativeArray it may be possible to build an Octree with structs only but now its time to test it in VR.