Previously, the collision system has been brute force for all labels (points and text labels with collision enabled) in the current set of visible tiles. As labels are placed, every new label candidate is tested against every previously placed label.
This brute force approach has been fine (and often faster than adding indexing schemes which bring their own overhead) with typical / small sets of labels, e.g. ~1000. As label density grows, it get quadratically slower, and with large (e.g. 100,000 points) sets it is essentially unusable (multi-second collision passes). These cases have not arisen in typical Tangram basemap scenes, but easily can with dataviz (in many cases you have collision off for these large sets anyway... but you still want a practical way to turn them on for some use cases).
This PR adds a simple collision grid system to drastically reduce the number of collisions performed for dense data sets. In a collision grid, the labels are divided (in this case in screen-space) into a grid of a given size; each label is added to the one or more grid cells that it intersects. When we need to know which labels a given label intersects, we only need to test the "local" labels that are in the same grid cells.
The grid size is adaptive based on the label density of the scene. We find the visible tile with the most labels, and determine a grid size based on that. When the label density is low (currently less than 256 labels in the densest tile), the collision grid is skipped entirely.
Currently, the collision grid is only implemented on the main thread collision pass for all labels. The first collision pass of each tile (on the worker thread) is generally assumed to already be "local" enough to not benefit substantially from a grid, though we could benchmark to see if it is helpful for even denser data sets.
Previously, the collision system has been brute force for all labels (points and text labels with collision enabled) in the current set of visible tiles. As labels are placed, every new label candidate is tested against every previously placed label.
This brute force approach has been fine (and often faster than adding indexing schemes which bring their own overhead) with typical / small sets of labels, e.g. ~1000. As label density grows, it get quadratically slower, and with large (e.g. 100,000 points) sets it is essentially unusable (multi-second collision passes). These cases have not arisen in typical Tangram basemap scenes, but easily can with dataviz (in many cases you have collision off for these large sets anyway... but you still want a practical way to turn them on for some use cases).
This PR adds a simple collision grid system to drastically reduce the number of collisions performed for dense data sets. In a collision grid, the labels are divided (in this case in screen-space) into a grid of a given size; each label is added to the one or more grid cells that it intersects. When we need to know which labels a given label intersects, we only need to test the "local" labels that are in the same grid cells.
The grid size is adaptive based on the label density of the scene. We find the visible tile with the most labels, and determine a grid size based on that. When the label density is low (currently less than 256 labels in the densest tile), the collision grid is skipped entirely.
Currently, the collision grid is only implemented on the main thread collision pass for all labels. The first collision pass of each tile (on the worker thread) is generally assumed to already be "local" enough to not benefit substantially from a grid, though we could benchmark to see if it is helpful for even denser data sets.