Symbols: fix translation, variable-anchors and collision boxes

[kubapelc]

This is a port of the symbol bugfixes from: https://github.com/maplibre/maplibre-gl-js/pull/4067 The porting ended up being relatively straightforward :)

Fixes https://github.com/maplibre/maplibre-gl-js/issues/210 (as far as I can tell)

Fixes https://github.com/maplibre/maplibre-gl-js/issues/3456

Changes (same as the bugfixes in the globe PR)

• Fixed symbol collision debug view (showCollisionBoxes) not showing the actual bounding boxes used for collision and click areas. The displayed boxes now match actual collision boxes exactly. Displayed collision boxes will react to map motion with some latency. (Just as the actual collision boxes do.)
• Fixed symbol collisions using inaccurate and sometimes entirely wrong collision boxes when the map is pitched or rotated. (#210)
• Fixed symbol collision boxes not being accurate for variable-anchor symbols.
• Fixed icon collision boxes using text-translate property for translation instead of the correct icon-translate.
• Fixed text-translate and icon-translate behaving weirdly and inconsistently with other -translate properties. (#3456)
• Updated some old render tests to reflect new symbol & collision box behaviour, added several new render tests

Launch Checklist

• [x] Confirm your changes do not include backports from Mapbox projects (unless with compliant license) - if you are not sure about this, please ask!
• [x] Briefly describe the changes in this PR.
• [x] Link to related issues.
• [ ] Include before/after visuals or gifs if this PR includes visual changes.
• [x] Write tests for all new functionality.
• [ ] Document any changes to public APIs.
• [ ] Post benchmark scores.
• [x] Add an entry to CHANGELOG.md under the ## main section.

[codecov-commenter]

Codecov Report

Attention: Patch coverage is 94.62500% with 43 lines in your changes are missing coverage. Please review.

Project coverage is 63.32%. Comparing base (4abf018) to head (dc4b7a4). Report is 10 commits behind head on main.

Files	Patch %	Lines
src/symbol/placement.ts	93.83%	8 Missing and 6 partials :warning:
src/geo/projection/projection.ts	81.48%	4 Missing and 6 partials :warning:
src/symbol/projection.ts	94.25%	6 Missing and 4 partials :warning:
src/symbol/collision_index.ts	96.82%	0 Missing and 6 partials :warning:
src/symbol/symbol_layout.ts	0.00%	2 Missing :warning:
src/render/draw_symbol.ts	98.68%	0 Missing and 1 partial :warning:

Additional details and impacted files

@@             Coverage Diff             @@
##             main    #4071       +/-   ##
===========================================
- Coverage   86.43%   63.32%   -23.11%     
===========================================
  Files         241      239        -2     
  Lines       32535    32791      +256     
  Branches     2001     1241      -760     
===========================================
- Hits        28121    20766     -7355     
- Misses       3458    11238     +7780     
+ Partials      956      787      -169     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[kubapelc]

A render test tests\icon-text-fit\textFit-grid-long is failing on Windows, but it seems to a an issue in the unmodified main as well. A build test seems to fail, I'm not sure why.

I've also noticed that pitch-alignment: map texts also have their collision boxes slightly off, even in mercator projection. Since it is not a globe-only edge case after all, I would like to try to debug it and fix it, please wait with merging until that gets fixed.

[HarelM]

This looks amazing! Thanks! I still need to wrap my head around what you did, so any illustration of how the code used to work vs now would be helpful for me to understand. Consider using mermain for that as github supports is natively now.

[kubapelc]

At this point I'm not sure myself about how it all works now, this is an accumulation of small changes and tweaks since about January. Most of the bugged behaviour was about some part of symbols not respecting translation or pitch alignment or rotation alignment properly, I think.

[HarelM]

@ChrisLoer any chance you might be able to look at this PR? It would help a lot I believe. I know you introduced some changes which touch this very code in a previous PR:

• #2260

So your help would be greatly appreciated here.

[ChrisLoer]

@ChrisLoer any chance you might be able to look at this PR? It would help a lot I believe.

I just spent about 20 minutes going through it, which unfortunately is pretty superficial for a big PR like this, but my initial reaction is that this seems great!

I'm very happy to see the text/icon-translate collision inconsistencies addressed. I think they've stuck around for so long because it's such a big job to fix them, but the approach here looks like what I'd expect. Between the existing render tests and the new ones added, I feel pretty good about this not breaking too much existing behavior. It's especially heartening that the render tests using collision debug boxes are relatively stable.

My biggest concern would be performance. Again on a superficial read, it looks like almost everything here should be some (hopefully small) constant factor increase on the cost of render-time reprojection (and the projection that happens during collision detection). This is where it would be really nice to see benchmark results (ideally a benchmark that exercises text-translate, although I don't know that it'll make a huge difference).

I'm sorry I don't have time to get into poking it enough to find errors or suggest improvements. I'll try to come back to it if I get time, but I wanted to get something written down now in case I can't come back to it. One thing I'd definitely like to do is sync the branch and play around with it locally in a debug environment, just to see how it feels.

Btw, this was my first time playing with the globe demo, and it's looking pretty good!

[kubapelc]

I've managed to fix the bug mentioned in the first comment, where pitch-alignment: map texts had a slightly wrong collision box in the distance.

[HarelM]

Seems like some render tests are failing, can you please check why? I left a few last comments.

[HarelM]

Is there a way to benchmark this to make sure we didn't create any performance issues?

[HarelM]

Added a few comments after looking at the coverage report, which looks great BTW, good job on that!

[kubapelc]

I've added a benchmark that measures the performance of adding symbols to the collision grid and compared this branch to main.

When testing 20K symbols and adding all non-colliding symbols to the grid (as normal symbol placement would), I got ~170 ms on this branch compared to 90-100 ms on main.

When testing 20K symbols and only testing the collision box projection (replacing the grid test with a empty function), I got ~42 ms on this branch, compared to ~3 ms on main.

Only the second test is now present, the first is in my branch's commit history.

Analysis

I'm not sure how much merit the first test has, since the old collision box projection was pretty broken, so a lot of the performance difference might be caused by the collision grids being filled with different contents.

The second test shows that the accurate projection of collision boxes has a lot of overhead compared to the old approach. But the old approach basically only did 4 additions and 4 multiplications per box.

Both tests use 20K symbols, which is pretty extreme, I'd expect a typical map to have roughly 100x less symbols. Extra cost due to accurate projection would then be 0.4 ms. This is probably not worth optimizing further, especially with the assumption that symbol placement ~~runs asynchronously in a separate thread~~, so it would not slow down rendering.

Edit: symbol placement isn't asynchronous, as pointed out by a newer comment.

[ChrisLoer]

This is probably not worth optimizing further, especially with the assumption that symbol placement runs asynchronously in a separate thread, so it would not slow down rendering.

Is that asynchronous assumption based on work in progress somewhere else? I just did a quick check and it looks to me like placement still follows the logic I remember: synchronous in the main/rendering thread, but with logic in pauseable_placement to pause itself if it goes over 2ms and continue the work in the next frame. That is, there's still a safety valve to try to keep slow placement from causing dropped frames, but it's not asynchronous.

.4ms is definitely enough to matter, but as you said that's with a pretty large set of symbols -- and fundamentally this functionality is going to require some extra computation, so it doesn't seem terrible to me.

[kubapelc]

Is that asynchronous assumption based on work in progress somewhere else?

Hi, no, I'm dumb and only remembered that collisions somehow don't slow down main rendering or happen alongside it, and assumed that it is asynchronous. You are of course right.

The 0.4 ms figure is an estimate of how long would 200 symbols take. Actually running the benchmark with 200 symbols takes 0.6 ms.

(Also since we are now looking at the absolute time of the benchmark: I ran it in Firefox on a 2.8 GHz Intel Core 7th gen, with turboboost disabled. No idea how that compares to common phone CPUs performance-wise.)