On my macOS machine, the paths_bench example currently runs at about 40 fps in release mode. Profiling shows that at a 24 ms frame interval, roughly 6–9 ms are spent on the GPU (fragment work, which still needs optimization), while the remainder is CPU time. After more accurate profiling, the frame graph revealed that most of the CPU cost came from bounds tree insertion

The issue is that the existing tree structure performs poorly when many bounds are identical, which is exactly what happens in paths_bench.

The new implementation is a variant of an R-tree. I may experiment with an R*-tree variant later, but the current approach already addresses three major problems:

1. Fast path for max leaf (now O(1) for overlapping bounds)
   Before: Every insertion walked the entire tree to find the maximum intersecting ordering.
   After: The tree maintains a pointer to the leaf with the global maximum ordering, letting us test it immediately.

2. Higher branching factor
   The tree now uses four children per node instead of two, which reduces height and improves traversal efficiency.

3. Better overall balancing
   Node selection and splitting strategies produce a more stable and evenly distributed tree structure.

These changes reduce insertion complexity:

• Identical or fully overlapping bounds drop from O(n^2) to O(n)
• Mostly overlapping bounds drop from O(n^2) to O(n log n)
• Spatially distributed bounds keep similar asymptotic cost but benefit from reduced height
• Non-overlapping bounds also benefit from reduced height

And specific operations improve significantly:

• find_max_ordering: from O(n) to O(1) when the max leaf intersects, otherwise O(log n)
• insert_leaf: from O(n) for identical bounds to O(log4 n)
• Total cost for inserting n items: from O(n^2) worst-case to O(n) best-case and O(n log n) worst-case

In the paths_bench example, these changes produce a 100% performance improvement, increasing the frame rate from 40 fps to 80 fps. With a few more optimizations, I believe we can push the example to around 120 fps.

Before:

After:

Release Notes:

• Improved path and rendering performance