WIP: voxel chunking

A very work-in-progress implementation of voxel chunking and generation.

Update 3: "Optimizations"

After thinking about what I need to optimzie for a bit, I realized I was still running everything as debug build! 🤦‍♂️

Update 2: slow, but headed in the right direction

Update with more progress

Pseudo-code

Cache
    entries : Map<Cell position, Entry>

Entry
    timestamp
    instance_id

update_cells:
    compute a NxNxM bounds around the camera
    transform the corners to cell coordinates
        cells are 32x32x8

    scan each cell in the bounds
        if cache[cell coords] is empty
            add a new entry
        entry.timestamp = now

    for each cache entry
        if entry.timestamp > AGE
            remove instance.id from scene
            drop entry
        else if entry has no model instance
            instance = call generator(cell bounds)
            entry.id = instance.id
            add instance to scene

Work-in-progress

The below gets the basic pseudo-code going, which was the goal. It has a number of issues, which were intentionally deferred to be addressed later:

• Hook in a real terrain generator function
• Improve the Potentially Visible Set (PVS) code - the fixed bounds around the camera seems a bit too brute force
• Cell cache
  • Address stuttering - rhe load/discard adds and removes many tiles at once. Seems like it would benefit from spreading out the load and/or somehow being smarter about the load/discard process.
• General performance - does a lot of work already and seems slow. Need to look into what kind of unnecessary work it is doing. Do that research before deciding what code changes are needed.
• The generator simply clones a fixed tile instance. It's not a "real" generator
• The load/discard of new tiles has a lot of stutter as many tiles get added / removed at once
• The potential visible set bounds are intentionally small for debugging
• General performance: this does a lot of work, which doesn't seem scalable without refinement

End-to-end functionality first

A bit about how I approach new work where I personally don't know exactly what needs to be done.

Note that step (2c) is (surprisingly?) often the easiest step to ignore yet the most beneficial to do well in terms of it's impact of understanding the problem space and implementating something both quickly but also future-friendly.

1. Define the result

2. Get it working
    a. Define the high-level approach
    b. Implement a rough end-to-end pipeline
    c. Proxy as many details as possible (i.e. use the simplest
       implementation I can that still is representative of what
       I eventually want)

3. Rinse-and-repeat step 2 until it works

4. Make it better
    a. Replace proxies with real implementations
    b. Fill in details

5. Scope to "good enough"
    a. Repeat 4 until it feels "complete" even if it's not what I
       fully wanted in 1
    b. Recognize

5. Code clean-up
    a. Remember I won't remember what I had been thinking even a
       week later, so code comments, naming, and general clean-up
       are worth it

6. Write-up
    a. Write a light summary of what I did. This highlights what I may
       have missed especially around (1), (2a), and (5)
    b. Write out the next todos to make it possible to pick up where
       I left off later

In this particular case, looking at step (2c) the keys to getting something going were:

1. Cloning a fixed instance rather than using a real, position dependent terrain generator
2. Making that fixed instance something very simple
3. Making the potentially visible set logic very simple (just a fixed bounds)
4. Ignoring performance until I got it functionally working

Performance fix

Figured out part of the performance issues:

1. I had incorrectly assumed dropping stale tiles would be fast; it wasn't
2. Dropped instances could be anywhere in the instance list
3. The re-sync code was written such that any mismatch implicitly invalidated everything after it in the list

The fix was to hash the existing instance IDs and check for against that unordered table rather than continuing the very simple prior logic which assumed indicies always aligned.