Benchmark Linear Quadtree vs Pointer Quadtree Construction

[sholloway]

The slowest thing in the simulation is the construction of the quadtree every frame. It may be faster to construct a linear quadtree using Z-Ordering rather than using the pointer quadtree approach.

Approaches

• The current pointer quadtree that does not leverage recursion.
• A linear quadtree that uses z-ordering to encode the points.
• The original linear quadtree algorithm.

Operations to Benchmark

• Tree Creation
• Range Search
• Memory consumption to store the tree.

Resources

• Bit Interweaving
• How fast can you bit-interleave 32-bit integers?
• SIMD Approach
• Z-ordering to Quadtrees Slides
• Bit Twiddling Hacks
• Example Implementation (Typescript)
• Stackoverflow: Implementing a quadtree using arrays

[sholloway]

Spent a lot of time on this. Construction of a Z-curve is faster than building a pointer quadtree. However, performing range searches on the Z-curve using the bigmin algorithm is quite slow and not practical for this use case. Performing binary search on a sorted z-curve is quite fast, but initially sorting the curve is expensive and not a good fit for dynamically growing/shrinking data sets.

While replacing the quadtree with an Z-Curve is not feasible, the Morton encoding is still useful. There are a few properties of the cellular automata simulations that can be exploited.

1. The total number of cells on a full grid can fit in a hash table in memory.
2. The Morton encoding of 2D Cartesian coordinates is very fast and can is a good option as a unique key for each live cell.
3. The range searches of the simulation are always the Moore neighborhood of a given cell.

Given these properties the quadtree can be replaced with a simpler solution of storing live cells in a Map object with the cell's Morton code as its key. The Moore neighborhood range searches are replaced by simply looking up each neighborhood in the map.