For the last ~3 weeks I have struggled to get the progressive rasterization code to work, and today I am happy to tell you that I finally got it to work! This was the result of 2 major breakthroughs in the last 2 days:
1. Fixed the bug where future snapshot node references got screwed during node spawn.
2. Swapped to a fixed root system.
The first breakthrough was not resolved until I finally drew a 1D version (a binary tree) of the problem on paper and walked trough each step that needed to happen.
The second breakthrough allowed me to use Morton keys to identify nodes which have tonnes of benefits when we need to locate all nodes that share a particular place in space. Last spring, during my master thesis on Octrees, I did try the fixed-root/Morton-key implementation but decided against it. This time around it looks much more promising for the following reasons:
1. Each node stores a grid of pixels/voxels so the quadtree/octree never have to map down to individual pixels/voxels.
2. We don’t use any ray tracing now which was the biggest reason for keeping the height of the quadtree/octree small.
3. With a quadtree and 64^2 pixels per node we can fit a Morton key inside a single 32-bit word.
One small drawback of using a fixed root system is that the canvas is not technically ”infinite” anymore. My current implementation clamp the canvas size to 2 million by 2 million pixels which would be enough for most users (going higher then this would, among other things, require me to switch to doubles instead of floats inside the engine).
There is at least another week of engine work and then maybe 2~3 weeks of client work before I am finally done with my Leonardo prototype! Stay tuned!