Spatially variable maxzoom

[AbelVM]

Motivation

Most of the datasets the user might want to display on a map have sparse data. Even basemaps are quite crowded in city centers but mostly empty in the countryside or water areas. But, as the user zoom in, regardless of the amount of new information found in higher Z tiles, new tiles are requested, downloaded, parsed, and rendered. This causes an overhead on both the client and the server.

As an example, this map depicts the highest local LoD tile that contains at least 15 events (Ref. 1)

The same applies to flyTo actions, where lower LoD would be more than welcome for the precaching and smoothing of the animation.

So, to optimize network traffic and processing time, not every location should have the same LoD. In other words, the maxzoom should be dynamically set for each location depending on the data to be rendered there, as for some locations zooming in won't add new information or it's irrelevant for the user.

This discussion is opened on Martin repo, but it might be cross to the clients repos.

The Starting discussion on Slack

Proposal

The amount of criteria to locally choose the right LoD is as large as the use cases you can think of, but maybe, we can narrow the possibilities to 3 generic possibilities:

1. Dasymetric approach (Ref. 2): using a 3rd dataset and a ruleset to set the max LoD. V.g.: City centers vs country-side
2. Local density approach (Ref. 3): using a ruleset that links KDE of each feature with the max LoD the container tile might reach, higher KDE -> higher LOD
3. Tile density approach: If the number of features in a tile is above a threshold, then we can use the higher LoD tile. This approach is like a relaxed KDE approach, faster and fuzzier. Quite similar to the functionality most tilers have for lower zooms

Some thoughts on how to attack the required tasks

Client side

Now that the mixed LoD is (somehow) available in the client (at least in MapLibre GL JS) (Ref. 4), the needed changes might include:

1. Decouple the mixed LoD management from the pitch-distance LoD selection logic, so it can be reused. Maybe tweak the overzooming' logic for this specific feature.
2. Add the logic to perform any of the 3 proposed approaches...
   a. YES
   - Implement the rules logic
   - Map the new requests
   - No need for server changes
   b. NO
   - Add the logic to be able to request a zxy tile and flawlessly process a response with a z'x'y' tile instead, being z' <= z
   - Memoizing! As every time a lower z is received (z') for a specific tile, it will affect 4^(z-z') requests for the sibling tiles
   - The server should be aware of this feature and proxy the requests

IMHO, working on point 2.a is shooting us in the foot. The complexity, external dependencies, and performance hit might be huge. As an educated guess, only the 3rd approach could be performed client-side with a limited drop in performance.

Server Side

Starting point: the client request the usual zxy, and knows nothing about dynamic LoD

The 3 proposed approaches might be implemented server-side, more or less easily (using PostGIS, they are easy peasy tasks 😅 ).

Regardless of that, a new LoD proxy feature is needed to map the request for the expected zxy to a response containing a rule-compliant z'x'y' tile, and that new z'x'y' should be informed in the response' header so it can be processed accordingly clientside.

Data source preprocessing

Almost every tiler tool lets the user choose to limit the number of features or vertex per tile, that is a way to reduce the LoD based on zoom... not maxzoom, but minzoom. They looks for reducing the tile size for lower zooms by limiting the amount of information per tile. And this discussion is pointing the other side of the zoom scale 😄

Most of the work on the data itself could be achieved offline, with preprocessed datasets. But, anyway, the tiles mapping should be done somewhere. So we can rely on the server as a proxy... or push a change in the data format (MBTiles, PMTiles,...) ... that won't happen.

So, regardless of the data preprocessing, we still rely on the tile server as a proxy.

Conclussions

None, let's discuss! 😅

References

1. QuadGrid: fast spatial data generalization for the best LoD, 2017
2. Dasymetric maps
3. How Kernel Density works
4. Fix level of detail at high pitch #4779

[HarelM]

I believe there are other links to maplibre spec related ideas of a similar issue/feature:

• Design Proposal: Allow overzoom for sparse pyramids tiles maplibre-style-spec#938
• Design Proposal: Expanding tileSources bounds maplibre-style-spec#60
  Not that I have a good idea how to solve this...

[AbelVM]

• Regarding overzooming: IMHO, it's a basic feature that should be added to the stack. The logic described in #938 totally fits the one in my mind, so "plus one" to that issue. This will mostly fulfill the need this discussion is about, but only when the data is preprocessed to avoid empty tiles and the server knows what to do then. But, if we rely on the client without any clue, it would take z-z' requests to find the tile with data to be overzoomed. So an extra cog would be needed to tell the client the tile that should be requested
• Regarding bounds: interesting reading, but I can't see the direct connection, but some quadtree logic that could be used to detail the boundaries

Both of these issues look client-targeted, but we might need to think across the whole stack

[nyurik]

There was also an idea to use a b&w image as an indicator of which tiles should have what zoom level. The idea being that a 1 bit image could have a pixel for each z14 tile, and have 0=z14, and 1=z15 -- i.e. an image would be 14^2 x 14^2 pixels in size. Or the image itself could be smaller than that, so each pixel would represent more than one tile (since most areas with high feature density is in one area. Or the image could be grayscale - and each pixel could be 2 bit or more, indicating the load level - e.g. 0=12, 1=14, 2=15, 3=16, or any other system.

P.S. this would obviously just the client-side improvement, where the server (Martin) simply serves whatever it is being asked, but the client decides which zoom to request for which area

[AbelVM]

Hmmm 🤔 . So like metadata served as a raster image that indexes the available zoom levels... But the 1bit-image should be 2^14 x 2^14, you have the numbers swapped 😅 , that's like 34MB just for zoom 14 (raw BMP). And we might need one per zoom level... Being the z21 file like 0,5GB (raw BMP again).

[nyurik]

hehe, oops, typed too fast :) Yes, 2^14, and with PNG it would drop significantly lower than 34MB because most low and high density areas are not random individual dots, but instead more like clusters - exactly what PNG would be good to compress. Moreover, it might even be possible to use JPG, as long as it "over-tags points", i.e. some low areas could be marked as high -- not a big deal. The reverse would be a problem though.

We only need a single mask image per source because "variable zoom" should only tell the client if the area is high density vs low density - e.g. telling the client to ask for z10 for low vs z15 for high (in which case the image would be 2^10 x 2^10). The specifics of which zoom to ask for low vs high could vary by specific map data provider.

[AbelVM]

But it looks like you're addressing a very specific usecase: low vs high density, 2 zoom levels, and statically harcoded per source via the metadata image file, that I suppose is downloaded once per source as in its onLoad event

Let me describe a quite common use-case: location-related marketplaces. We can imagine a real estate portal, a local tourism office,... Let's go with the not-exactly-made-up proptech usecase 😅 , that might be one of most complex indeed. It looks very specific, but I want to make a point against harcoding and the usual trend to solve only one simple use case that we, biased, think is the most common

• The company has a dataset of geolocated assets to be sold or rent
• Their portal offers a map of the available assets to ease the search and contextualization of assets
• The dataset and the linked map are dynamically updated, as new ads are published
• They offer 3 pricing tiers to announcers:
  • Free: the full address and location of the asset are disclosed and can be seen on the marketplace map as a pin in the exact location
  • Paid-cheap: the number of the street is anonymized, and the pin is randomly located along the street
  • Paid-expensive: the whole address is anonymized, and the pin is randomly located in the neighborhood area
• They want to focus the portal user on the assets area (to optimize tiles storage and network traffic), but because of the pricing model, they don't want to mess with the anonymization, so:
  • Free assets can be zoomed up to the highest level
  • Paid-cheap assets can be zoomed up to a medium-high level
  • Paid-expensive assets can be zoomed up to a medium-low level
  • Areas with assets within can be zoomed up to a low level (this goes back to any of the 3 approaches in my proposal above)
  • Areas without assets within can be zoomed up to a very low level (let's say map minZoom)

So, IMHO, relying on the client to request the right tile every time adds an extra layer of complexity, as it needs to be continuously up to date with the available-zoom-levels-per-pixel metadata. I would let that logic at the server side, as the server itself already knows what's available and what's not. And then, the client just checks whether it should overzoom the received tile or not

[AbelVM]

I'd go with a hybrid server/client solution. In broad terms, quite raw ideas:

• The data source is preprocessed to be sparse or the tiler knows the rules and how to apply them and proxy the requests
• The client, clueless, requests a tile zxy
• The client request header includes a tag to let the server know whether it supports overzooming (to allow back compatibility and allow the users to change the behavior via the source's options)
• If the client sends the overzooming tag, the server replies with the requested zxy tile if available or rules compliant, or the z'x'y' tile (z'<z) if not. If there's no tag, the server behaves as of today
• The server response header always includes the zxy values of the served tile
• The (overzooming aware) client receives the tile and checks the header
  • if the response' z is the same as the requested z, then it just follows the current pipeline. No overhead
  • if the response' z is lower than the requested z, then it goes through the overzooming logic

[AbelVM]

Extra round:

I think I have mixed two ways to fill the gaps while rendering in my opening post

1. Overzooming: a tile zxy is displayed using a zoomed-in clipped region of a z'x'y' tile to zoom level z, being z'x'y' an ancestor of zxy. So, we have a z level tile, but rendered using the data of a z' level tile
2. Multizoom: like the approach of Rerf.4 in the opening post. This implies replace the "missing" tile and its siblings with the selected ancestor
   

I'm personally quite partial to the first option, but I think both options should be profiled in terms of performance and visual quality