Skip to content

vector: Recalculate the R-tree every frame

James Westman requested to merge jwestman/libshumate:rtree-improvements into main

This changes the way symbol collision detection works to make it more flexible and more performant.

Previously, the R-tree was maintained for all symbols in the current tiles. The tree was updated when tiles were added or removed, and each frame, it would recalculate which of its members should be visible.

Now, the R-tree is rebuilt every frame. This seems like it would be less efficient, but it is actually much more efficient, due to several reasons:

  • Insertions are O(1), but queries are roughly O(label_density). Thus, performing more insertions to save query time is a good tradeoff.
  • The R-tree now only contains visible markers, which greatly reduces the number of bounding boxes that must be searched. This is not possible when maintaining the tree between frames because the marker might be visible again on the next frame.
  • Likewise, the bounding boxes don't need extra margin to account for future rotations or zoom. Smaller bounding boxes mean shorter query times.

Another benefit is that ShumateVectorCollision no longer needs to handle the complexities of line labels or future features such as icons. This is all handled by ShumateVectorSymbol.

One more notable change is that the R-tree now uses coordinates in screen space rather than map space.

Merge request reports