Mapbox-gl-js: Implement cross-source symbol placement

[mollymerp]

Prior 🎨 can be found at #2516 + #2624 + #1042

Per chat in Slack today, we will be moving forward with a big 💪 refactor that will allow our cross-source symbol placement dreams to become a reality. 🌈

Here is a brain dump based on what I understand from @yhahn @jfirebaugh @ansis @lucaswoj:
Goal:

• change the TilePyramid - Source relationship so that instead of having many sources with their own TilePyramids storing data on each Tile for that source, we have one TilePyramid and each Tile id would represent an array of Tile information for every source in the style.

Options:

• TilePyramid can dispatch a worker to placeFeatures after all tiles have been sent back to the main thread with their symbol placement info (from #2624)
  
  
  
  • this would allow current Worker behavior to remain the same (?) and we'd just have to add an additional Worker dispatch at the end for the final symbol placement (?)
  
  
• new TilePyramid would dispatch _all_ tiles under a given id in the TilePyramid to the same worker to compute placement information
  In chat, it seemed like the latter is preferred ( @jfirebaugh ?) If so, the work from #2624 was purely educational for me 😭

☝️ – please correct or edit as you see fit if I got something wrong

Questions that need answering (by me or anyone else):

• should the main thread handle symbol vs. non-symbol layers differently? Does it already?
• @jfirebaugh suggested a quadtree structure for the TilePyramid. What would that look like and what benefits does it offer?
• how will non-placement related Worker tasks be affected? @jfirebaugh says 👇

tile parsing + bucket creation could still be per-source-tile

• how much of this does the work @anandthakker is doing solve? How far away is that from shipping?

Future expansion of the TilePyramid refactor for rendering perf improvements (from slack mostly)

• combining tiles for rendering efficiency, for example 4x512 tiles into one mega tile (cc @jfirebaugh ) ?
• this refactor would mean that only one clipping mask is necessary. No need to redraw the clipping mask when drawing layers in different sources (-js) or use the more complicated and not completely sound approach -native does. (cc @ansis )

I plan on 💭 on the questions above to solidify my understanding of the task. Once we've settled on the approach we want to take going forward, I will put together a more detailed roadmap of the process and start a PR. Comments / thoughts welcome!!

[anandthakker]

@mollymerp I've updated the top of #2667 with the current status and outstanding tasks. Assuming broad 👍 to the overall design there, I think it's actually not too far from being 🚢-able.

[lucaswoj]

This looks great @mollymerp!

TilePyramid has a few too many responsibilities at the moment. @anandthakker is refactoring TilePyramid into SourceCache. I think what you're looking for is sufficiently new / different that you can think about a clean-slate design. Hopefully this is a little easier for you than trying to refactor TilePyramid!

[lucaswoj]

Some architectural doodlings...

• TileStoreCache wraps TileStore to provide tile caching
• TileStore (name up for debate) exposes a loadTile(coord, callback) method. There is one tile per coordinate.
• SourceCache wraps Source to provide source tile caching
• Source exposes a loadTile(coord, callback) method. There is one "source tile" per coordinate per source. All of this class's expensive operations are set to the worker.
• WorkerSource does all the heavy lifting for Source
• _tile combinator and symbol placer_ is a module within the worker that combines tiles and places symbols

[lucaswoj]

• should the main thread handle symbol vs. non-symbol layers differently? Does it already?

I think the main thread TileStore can be completely ignorant about the contents of tiles. the _tile combinator and symbol placer_ will need to handle symbol layers as a special case.

• @jfirebaugh suggested a quadtree structure for the TilePyramid. What would that look like and what benefits does it offer?

I'm not sure about this. TileStore can store a simple map of coord ids to tiles. There might be a need for a quad tree within _tile combinator and symbol placer_.

• how will non-placement related Worker tasks be affected? @jfirebaugh says 👇
  > tile parsing + bucket creation could still be per-source-tile

Conceptually, not at all. What you're doing is a new & separate task for the workers.

• how much of this does the work @anandthakker is doing solve? How far away is that from shipping?

@anandthakker is working on everything from SourceCache down. This is hopefully isolated from your work on TileStoreCache, TileStore, and _tile combinator and symbol placer_.

[lucaswoj]

💭 Looking over my diagram above with a couple months retrospect, I wonder if we need to keep a SourceCache if we're caching the final merged tiles in TileStoreCache

[anandthakker]

@lucaswoj good point! Although, along the lines of #2951, I do think there are good use cases for caching things at a finer level of granularity than the fully-baked, ready-to-render tiles: e.g., maybe caching something like the TileLayers that you proposed in #2875. This makes me wonder whether Source should be serving up TileLayers rather than tiles: isn't that more directly what the TileStore here is going to want to work with in baking the cross-source symbol-placed tiles?

[vicapow]

Hey all! Wanted to see what the latest was here. Is there still interest in getting this in? If so, would a PR be welcome?

[mollymerp]

@vicapow this is not being actively worked on – we'd love to see a PR 😸

[ChrisLoer]

I believe this is fixed in #5150 -- global/viewport collision detection gave us cross-source symbol placement as a bonus feature! Some of the refactoring discussed above has long since merged, but otherwise the implementation we actually landed doesn't follow the TileCombinator approach discussed above.

Since I'm not super-familiar with this ticket, please re-open if I'm missing an important part.