Establish Goals

[nyurik]

This is a place to discuss the next generation of vector map tile specification, and the goals we are trying to achieve with it.

• Use Write a reply to comment on a goal
• Use Write a comment to submit a new goal -- One goal per post please. Start with the "why" -- what's the goal of your proposal?
• Click the ⬆️ to vote up the goal

[nyurik]

GOAL: new functionality

Add elevation (z-coordinate) to geometries

[lseelenbinder]

Do we want to support only 3D or maybe also N-D?

[maxammann]

I'm not sure if we want to go into the direction of 3D-tiles. There are already specifications for 3D tiles e.g. https://github.com/CesiumGS/3d-tiles

And it is quite complicated to design such a format.

Also 3D tiles and 2D tiles could definitely co-exist.

[IvanSanchez]

Does this also mean having Polyhedron geometry types?

[IvanSanchez]

GOAL: ???

Revamp geometry encoding.

The current geometry encoding in the MVT spec is using opcodes related to 2D canvas operations to encode geometries: points are 1, linestrings are 1-2-2-2-2 (with a 2 per vertex after the first), polygons are 1-2-2-2-2-7.

I'd like to propose an encoding based on Volodymyr Agafonkin's earcut:

• The dimension of the geometry, i.e. number of coordinates per point (either 2 or 3)
• A flat array of coordinates
• An array containing the coordinate index where a (inner) ring starts
• An array containing the coordinate index where a hull starts

My main intent with this is improve the sanity of the geometry encoding. A more immediate benefit is to enable geometry data to be dumped into GPU memory with minimal or no manipulation.

Given current WebGL support, it's safe(ish) to assume that optimizations geared towards 2D canvas are not a priority at all.

Also: consider providing a triangulation of polygons. earcut is fast, but it'd be interesting to see triangulating once in the server side offers a benefit against the increased size of the tiles.

[nyurik]

Thanks @IvanSanchez, could you give some examples of the actual storage? Also, just to clarify - could you update the post above with the goal you think we would satisfy with this? I.e. the "why?"

[maxammann]

Yes the goal is missing here. I guess it should be effienecy in terms of time or space.

In order to see if the proposed solution is really better wo would have to benchmark.

[StylianosVitalis-TomTom]

I, also, think we are missing a goal here. Not only in terms of what we want to achieve (storage efficiency or parsing/computational efficiency on the client), but regarding the use case. I can, personally, see two reasons why we would need 3D coordinates:

• 2.5D data (e.g. a terrain with elevation), and
• true 3D data, like complex 3D models with vertical elements (e.g. buildings with vertical walls etc).

I think these two can be covered by different solutions. For instance, any true 3D data always introduces a redundancy in terms of vertices, so introducing some form of topology (like indexed vertices) makes a huge impact in terms of storage efficiency.

[mactrem]

GOAL: smaller tiles

Significantly reduce the tile size and thereby the latency for loading the tiles.
This can be achieved by using a column oriented layout like the state of the art big data formats Parquet and ORC instead of the row oriented approach on which Mapbox Vector Tiles (MVT) is (implicit) based on.
In addition it should be possible to specify lightweight compression schemes per column like RLE, Bit-Vector, PFOR-Delta and custom geometry compression algorithms in addition to a tile wide heavyweight data agnostic compression algorithm.
Also bit aligned null suppression algorithms for the integer compression instead of the byte aligned Base 128 Varint encoding used in Protobuf can/will improve the compression ratio because a lot of data in a MVT tile are stored in the form of arrays of integers.
This can significantly improve the compression ratio -> 5x on some zoom levels could be possible compared to the current MVT size.

[AbelVM]

This rang a bell, and it was related to the way Foursquare/Unfolded serves their H3 tiles

https://medium.com/foursquare-direct/hex-tiles-building-a-new-data-tiling-system-with-h3-61eb33fed4cb

https://location.foursquare.com/resources/blog/news/introducing-hex-tiles-our-next-gen-tiling-system/

[mactrem]

@wipfli @nyurik I have now a state which could potentially form the basis for the next generation of vector tiles. So far I have only evaluated a limited tileset but the first results are promising. I updated my repo with the new stats and layout. Would be nice if we could set up a meeting again sometime in the future to further discuss on that topic

[wipfli]

@mactrem let's talk about this tomorrow evening in the MapLibre Web Technical Steering Committee Meeting. You find the zoom link in the MapLibre Slack channel

[wipfli]

@HarelM do you think we have time for this tomorrow? Also, do you remember who recently asked about non-MVT sources in MapLibre GL JS? There was an issue recently, right?

[HarelM]

I think we have the time, yes.
I don't remember who asked about non-MVT sources unfortunately...

[lseelenbinder]

GOAL: faster tile processing

Data encoding that supports easier zero-copy operations in many languages.

Eventually comes down to the tradeoffs between:

• tile size (more packed = less likely to be directly usable, but smaller)
• runtime performance (more packed = likely to be slower to consume, but could load faster)

[maxammann]

Just 👍🏼

I guess zero-copy is a property of the file format, which probably does not interfere directly with what is stores. So zero-copy is more the how, instead of the what.

Just wanted to clarify that. Probably zero-copy is a goal which can be reached orthogonal to all the other goals mentioned here :)

[wipfli]

GOAL: new functionality

Put styling information into tiles. For example, I would like to add styling for glaciers in Switzerland and for palm trees in Mallorca. At the moment, the map vector style has to handle everything so if I want to have more specialization, my style.json file just gets longer...

[wipfli]

Yeah you are right @StylianosVitalis-TomTom... Maybe what I need is a tiled style file

[wipfli]

Just to be clear: I think putting style information into tiles is a bad idea because it is too far away from the current paradigm.

[wipfli]

I just sharing my wishes for a future better map renderer tech stack...

[wipfli]

But maybe I also just need to learn better how to use MapLibre GL styling...

[StylianosVitalis-TomTom]

@wipfli As far as I understand, then, your problem is that you can't have localized styling without bloating the one-and-only main style.json with complicated rules. That's a very good point, actually! I think it's a very interesting use case. And I like the idea of exploring "tiled style files" as you mentioned.

[mactrem]

GOAL: faster tile processing

Improve the decoding performance of a tile to enable a better user experience.
Use SIMD instructions and vectorization for decoding the tiles see for example https://arxiv.org/pdf/1209.2137v5.pdf or https://openproceedings.org/2017/conf/edbt/paper-146.pdf.
SIMD instructions are supported in the browser via WebAssembly.
There could by one cross-platform decoding library written in Rust which can be compiled to WebAssembly for the usage in a browser.

[lseelenbinder]

I really like this! I forget--is SIMD widely supported on ARM? We'd have to be careful to not broadly impact mobile performance by optimizing for x86 instruction sets? (It's been a bit since I was that deep in ARM...) It looks like there is pretty good support for SIMD on ARM.

[maxammann]

SIMD also works in WASM :)

[IvanSanchez]

GOAL: Meta (Bikeshedding)

Get rid of the word "layer".

Seriously. It makes me go crazy because so many things are called "layer" these days. The concept of "layer" in current vector tiles means "theme".

[lseelenbinder]

And if we replace it, we want something that is better than the current terminology. (We shouldn't replace it just because it's confusing—it is—but we because we have something we know is better.)

[maxammann]

Maybe I misunderstood the proposal, but was @IvanSanchez confused because of the confusion between layers in tiles and style layers in the style.json or because of something else?

[IvanSanchez]

@maxammann I'm not confused, I'm just incredibly annoyed. There's layers in tiles, and in the stylesheet, but the concept of "either a feature or a coverage" is also called a layer; in Leaflet anything represented by a DOM element is a layer; therefore a symbol class is a layer class; a dataset is also called a layer; and pretty much everything can be called a layer in some place or another.

So if you render features as symbols in vector tiles and display that tile in a <canvas> DOM element, you're rendering layers as layers in layers into layers. Therefore, the style that a layer takes when drawn into a layer (i.e. which kind of layer(s) it becomes) depends on which layer it's contained within the vector tile.

(cc @anitagraser)

See what I mean?

[maxammann]

Yes, but I have to say I did not yet stumble upon the other usages of layer you mentioned. E.g. in maplibre-rs the term layer is only used for the data layers (vector tiles) and style layers (style).

But the first step would be to create a glossary for all terms related to the spec. Then we can try to iterate on that and improve it.

[ianthetechie]

My 2 cents: I am open to alternatives, but I do not agree that it is a problem because of a collision in this case. Vector tile data schema and style specifications are different bounded contexts. "Layer" is also used in docker, the OSI model, and 7 layer cakes without confusion.

I personally find the term (data) layer here to be intuitive enough, but perhaps as @maxammann is suggesting it'd be helpful to have terms defined someplace conspicuous in the documentation ;) I can probably contribute to this.

As for alternatives to layer, could we constructively brainstorm here? (Data)set or collection are my best alternatives at the moment, but I'm not really a fan of either over layers.

[mactrem]

GOAL: new feature (?)

Allow querying of only specific layers of a tile based on the used style.
Depending on the style only a subset of a tile may be needed, for example a light theme like the OpenMapTiles Positron style does not render the POI layer, the Basic style on the other hand does.
This has the advantage that only one tileset for different styles is needed and still only the required data can be requested.
The basic idea is to make a vector tile "cloud optimized", so that specific combinations of layers can be fetched via HTTP range requests from a tileset hosted on an cloud object storage or an CDN -> CDNs like AWS CloudFront also support multipart ranges, so the latency and costs shouldn't be that much higher for fetching a tile, nevertheless a overhead for an additional index (maybe as an sidecar) on a cloud optimized format like PMTiles would be created

[lseelenbinder]

Mapbox already does this at scale, so I think we just have to maintain the capabilities already present in MVTs.

The basic idea is to make a vector tile "cloud optimized", so that specific combinations of layers can be fetched via HTTP range requests from a tileset hosted on an cloud object storage or an CDN -> CDNs like AWS CloudFront also support multipart ranges, so the latency and costs shouldn't be that much higher for fetching a tile, nevertheless a overhead for an additional index (maybe as an sidecar) on a cloud optimized format like PMTiles would be created

This bit I like in concept, but in practice it feels like the overhead of N parts * M tiles requests would be prohibitive.

[mactrem]

Mapbox already does this at scale, so I think we just have to maintain the capabilities already present in MVTs.

yes, but i'm quite sure Mapbox is using an additional dedicated tileserver which the cloud optimized approach tries to avoid to reduce the costs.

This bit I like in concept, but in practice it feels like the overhead of N parts * M tiles requests would be prohibitive.

I agree that for directly accessing tiles hosted on an cloud object storage there are this disadvantages (because of the lack of multi range support) which would lead to too much overhead to bring any advantage. One optimization is to use HTTP/2 where you can parallelize the requests via multiplexing which reduces the overhead, but you still have to pay the additional request(s). Also the Google cloud storage is the only object storage which currently supports HTTP/2.

But in general if you want to deploy a cloud optimized tile archive most of the time a CDN is put in front to minimize the latency and enable the "slippy maps" user experience known from the map provider which are using dedicated tileserver.
On most (all?) CDNs like AWS Cloudfront multi ranges are supported and all the requests for groups of layer for a specific tile can be handled within one request/response.
I have tested the approach of fetching group of layers on an AWS Cloudfront and it had (nearly) the same latency compared to fetching the full tile.
In general there could be an optional additional index as a sidecar for filtering group of layers from a tile, like a secondary index on a database. If you want the full tile you can ignore the secondary index and only go with the primary index.
The advantage would be that in some cases in addition to a better latency the egress costs on the CDN also go down. For example in a lot of z14 tiles you could get rid of 50% of all features for some styles where no POI and address layer is needed.
On the vector tile site this can be easily supported by allowing an optional data agnostic compression on group of layers.

[pnorman]

I doubt this is desirable. For cases where only range requests are available, you'd increase the 1 request per tile of an xyz endpoint to at least two requests, which might be less data, but are more round trips.

If there's a server that can handle more sophisticated stuff, this is already possible.

[HarelM]

GOAL: standardize spec (?)

Have an initial spec that is the current one, and improve it later on (agile style).
Currently MVT is not an official spec/format in terms of OGC.
As a goal I would love to have something there (out-the-door) approved, and continue refinement and improve the spec/format as we continue working on it.

[lseelenbinder]

I like the idea (especially about OGC)!

However, serious question: do you think a widely used spec can be simultaneously with broad usage be effectively pushed forward in an agile style manner? I don't know, but it feels like once we lock in a v1 of the new stuff, we can expect future changes to be relatively slowly adopted at scale.

[HarelM]

I think the current spec is widely used, it's just a matter of establishing it as an official OGC format.
Afterwards, we can have a new/different one with the relevant improvements.

[IvanSanchez]

You folks gotta talk to @doublebyte re: OGC. I'l spin the idea around during the upcoming codesprint (https://developer.ogc.org/sprints/19/) but I think that the lowest-hanging fruit in terms of OGC standardization would be a JSON-FG encoding for vector tiles, and not a binary format.

[maxammann]

GOAL: new feature (?)

Vertex Buffer support

Support the ability to embed vertex buffers directly.

When storing models in games, one technique involves to deploy them as meshes (also called vertex buffers). MVTs do not contain the vertex buffers which can just be uploaded to GPUs directly. They contain a more abstract representation. This representation is more or less equivalent to how paths are stored in SVGs.

The reason for this design decision by mapbox probably was that they wanted to allow changing the rendered geometries during runtime based on the style.json. Now, that is a good design.

Though: I was wondering what exactly those style options are which can change the geometric shapes.
One example is the line caps for lines and outlines for polygons.

Maybe we can find a better sweet spot between performance and abstract representation of geometries.
By storing the vertex buffers for polygons directly we might not lose any features and gain huge performance benefits because we can skip the expensive tessellation step which MapLibre has to perform during runtime.

[StylianosVitalis-TomTom]

I like this idea. In fact, I think we should reconsider adjusting the scope of this discussion to consider using other existing formats (except for MVT) in a style.json for certain use cases.

For instance, what if instead of adding vertex buffer support in .mvt, we allow Batched 3D models (i.e. .b3dm) to be used in style.json for complex 3D geometries. Then, we have the benefit of reusing a WebGL optimized format with all the necessary semantics and attributes that 3D Tiles support. We just omit the over-complicated and bloated (in my opinion) part of custom tilesets that 3D Tiles dictate.

[maxammann]

Inlcluding .b3dm files in tiles goes a lot into the direction of existing 3D tile specifications.
But yes that would generally be the idea. Instead of specifying abstract geometries, we could concertize the data. Probably a mix is the best outcome. E.g. keep gemetric descriptions for lines. For polygons we should maybe only include the vertex buffers.

[StylianosVitalis-TomTom]

I understand that it is a bit overlapping with the 3D Tiles specification, but effectively .b3dm is just a glTF (thus, effectively vertex buffer) with a wrapper to link vertices with semantics/attributes. I am not sure if it's the best solution here, but it's an existing one which can be easily reused and building tools around it could, potentially, benefit both ecosystems: MVT and its style specification, and 3D Tiles.

[mactrem]

Though: I was wondering what exactly those style options are which can change the geometric shapes.
One example is the line caps for lines and outlines for polygons.

For lines in addition to the line-caps also line-joins are a style option which can change the layout of the geometry. Outlines of a polygon, on the other hand, are currently only rendered as WebGL lines in MapLibre, so no tesselation involved see draw_fill.
This leads to a limitation of the outline width of 1 px on most platforms.

When storing models in games, one technique involves to deploy them as meshes (also called vertex buffers). MVTs do not contain the vertex buffers which can just be uploaded to GPUs directly. They contain a more abstract representation. This representation is more or less equivalent to how paths are stored in SVGs.

I think the approach for directly encoding the vertex and index buffers like in glTF (3DTiles) works out well for displaying detailed 3D models like buildings but is more difficult for the "modern" cartography use cases. With the 3D Tiles styles for example only the color and visibility of the features can be changed.

Maybe we can find a better sweet spot between performance and abstract representation of geometries.
By storing the vertex buffers for polygons directly we might not lose any features and gain huge performance benefits because we can skip the expensive tessellation step which MapLibre has to perform during runtime.

I agree that especially for polygons by omitting the expensive tessellation step by directly storing the index and vertex buffers in the file could lead to real performance improvements. The same applies to polygons which are rendered as extruded buildings via the fill-extrusion layer. As buildings will not always be rendered and therefore would unnecessarily inflate the file size in some cases, there could be an an option where the tesselated polygons could by lazy loaded like with proposed "cloud optimized filter" approach for example. Points can be rendered as circles or symbols (icon and text) depending on the layer type and are transferred as tessellated quads to the GPU. For circles the tessellated quads could be directly stored, for symbols this approach doesn't work. But on the other hand the calculation on the client is not really expensive and probablly more kind of a micro optimization (if at all). Lines are the hardest part because their layout can be strongly affected by the style. But maybe storing the basic tessellated layout and then insert the line-caps and joins on the fly on client side when specified in the style could be an option? (thinking loud).

[AbelVM]

GOAL: new feature

Allow features with no geometry

Right now, MVT doesn't support null geometry features, they are just not encoded. But there are some common grids where the geometry is represented by a compact value (H3, S2, geohash...) and the geometry could be generated client side, lowering the tile payload.

Clientside we can use addProtocol or even add those now common grids as new source types in the library, alas H3Source or S2Source

[AbelVM]

GOAL: new feature

Add support for array and/or json properties

Sometimes you just want to encode

• a huge (fixed) number of properties (e.g.: values of temperature measurements at the feature geometry along a period)
• a variable number of categorized values within a huge pool (e.g.: number of PoIs per category within the feature geometry)

Because you want to play with filtering and styling client side. As of today the only way to do so is serialization/deserialization which severely hits performance.

[dabreegster]

@mem48 IIRC, you've hit issues encoding arbitrary floats before? This is a discussion for evolving the MVT spec, if you wanted to weigh in with your use cases

[mem48]

Well as you asked @dabreegster, here are my gripes with Vector Tiles. Some of these may be more to do with Mapbox GL / Maplibre but I think they are fairly interconnected.

For the benefit of others, I should explain my use case. I'm mostly making data interactive visualisations such as choropleth maps. Thes are usually for many small areas and so loading a GeoJSON is not a viable option. Thus I'm building and hosting my own vector tiles which contain the data and using Maplibre to visualise. For real examples see carbon.place and npt.scot.

I've run into several challenges.

1. The style does not have a concept of a basemap or style groups that can be added/removed together. This makes switching base maps complex because the only way to change all the layers that make up a basemap at the moment is to remove the whole style (which also removed your data layers). It also makes mixing vector and raster basemaps complex. Its even more complex when you don't want your data layer to be the top layer.

In this example, the choropleth data is below the roads and the place names. But different base maps have different layer names. So I have ended up making custom styles with placeholder layers that contain nothing but allow me to have standard names to refer to.

2. As far as I understand the MTV spec stores all data in a key:value format. This works well for things like OSM tags, which you would expect a high amount of repetition. But when making data visualisation you are much more likely to have numeric values with little repetition. If often not practical to compress the numeric data into a fewer categories as addtional functinality is required e.g. popups with numerical data or filters.

In this example, the road network has additional numerical data about the number of cyclists under different scenarios. The map allows filtering based on these values, so they need to be part of the vector tiles.

3. Incomplete styling options. There are some things that the MVT spec does not allow. E.g. you can set the line width of a polygon.

4. Zoom dependant styling. Its quiet common to have to define rules that are zoom dependent. E.g. roads get thicker as you zoom in. This is quite a lot of work for the developer and access to an "auto" mode that did this automatically would be helpful.

5. Performance, I suppose this could always be better. But I'm starting to run into bottlenecks. Especially with some of my more complex Dasymetric maps e.g.

6. Sprites, This may be more of a documentation issue but making custom sprites is a little confusing as is if/when the @2x and @3x versions are required.

7. Fonts, Similar issue to sprites. Why fonts require a folder of different files is unclear. For this reason, I tend to stick to a single font in my maps as the "known to work" option. Why can't we simply access normal web fonts?

[mem48]

I bet @bdon has useful ideas as well.

[nyurik]

@mem48 thx for the write up! In order for it to become actionable, let's try to break it into specific MVT specification change proposals. Note that this is different from the styling changes (which should be addressed by the MapLibre styling language change), but obviously some of the styling changes will depend on the underlying data changes. If you had the power of change anything you want about MVT spec at all, which of those 7 do you think apply, and in what way? Are they covered on this page already, or are they different? For example, "Incomplete styling options. There are some things that the MVT spec does not allow. E.g. you can set the line width of a polygon." -- do you want MVT to contain some value that becomes a line width? In that case i believe you can do it already. Or is this something else? Thx!!!

[mem48]

@nyurik I think I may be conflating the style specification and the MVT specification. I assume these are at least partially connected, but I lack the technical knowledge to say exactly how. The incomplete styling options I was referring to were https://docs.mapbox.com/mapbox-gl-js/style-spec/layers/#fill which has no boundary-width option. But that may be purely a styling issue. The one that to me seems most fundamental is the way attributes are stored as this is not an efficient way to store large amounts of numerical data. I have wondered if there would be a way to separate the geometry from the attributes and have data tiles, so that only the needed data is downloaded.

For example

The MVT with geometry: www.example.com/tiles/mytileset/geometry/{z}/{x}/{y}.pbf
Data for attribute 1: www.example.com/tiles/mytileset/attrbute-1/{z}/{x}/{y}.pbf
Data for attribute 2: www.example.com/tiles/mytileset/attrbute-2/{z}/{x}/{y}.pbf

This could be especially useful if I have hundreds of attributes, to visualise. For example https://www.ons.gov.uk/census/maps. This might be related to @mactrem suggestion above.

[AbelVM]

GOAL: new feature

Metadata

Add support for metadata per tile, with both schema-bond and schema-less areas.

This way the attribution, licensing, date, link to the recommended style.json, etc. might be watermarked in the tile instead of being optional parameters in the declaration of the source.

The schema-less area would be open for custom payload that would be accessible client side

[HarelM]

Tile hash and last modified can help the process of updating tiles, and allowing partial updates of a tile set (offline file usage).
sqlite like today (mbtiles) is not acting well when trying to update tiles in it - the file gets bigger and bigger. So I would also suggest not using sqlite for tiles as in most cases you don't really benefit from the database indexing etc when the main goal is to extract a single tile by x,y,z coordinates. In that case, I think pmtiles format might be better.

[ianthetechie]

Ooh, this is an interesting one.... This is something I've been thinking about lately with respect to satellite data attribution, as your data set could be from dozens of sources.

[nyurik]

GOAL: simplify tile generation and processing, possibly reduce size

Storing unclipped geometries in vector tiles without merge issues or duplicates

• compute bbox of a geometry
• store geometry once in a tile corresponding to the center of the bbox
• all other tiles within the bbox will store only the bbox-reference -- the bbox and the feature ID, but not the full geometry or the feature tags. Bbox could be stored as two XY points.
• when processing, a client starts only with the needed tiles. If it encounters any bbox-reference features, it would compute their center point, load corresponding tiles, and process just the needed feature IDs.
• possible optimization: a small enough feature can be duplicated. Client should treat two features with the same ID as identical instead of trying to merge them
• possible optimization: some tags could be duplicated in the bbox-reference so that the client could decide if the feature is needed before loading another tile
• possible optimization: use a single geopoint instead of a bbox reference. PROs: less space, can be done with existing MVT spec more easily (requires some user-specific magic tag to indicate that its a reference). CONs: harder to optimize location-based queries - i.e. ignore a feature because bbox is not interesting even though it overlaps with the tile currently being processed.

---

Pros

• simplifies tile generation because no geometry clipping or fixing is needed
• simplifies parsing because features do not need to be merged
• overall dataset size might be smaller because tags are not duplicated, and because each bbox reference is just 5 values (ID, x1, y1, x2, y2)

Cons

• large complex geometries cannot be stored this way - i.e. a detailed outline of a country stored in a single tile would make it extremely slow to load and process, defeating the purpose of tiles
• in some cases this could result in significant increase in processing and I/O, e.g. if neighboring tiles have just a few needed overlapping features.

[IvanSanchez]

Interesting approach. There'll be compromise solutions where a polygon is split once every 8x8 tiles (instead of in very tile).

I'd suggest allowing only a subset of tiles to store referenced features. e.g. only even coordinates, so that a feature spanning over 3-4 would be stored in 4, whereas 2-3 would be stored in 2. This should minimize the number of out-of-viewport tiles to be requested.

I'm somewhat skeptical about whether this does simplify tile generation and reduces tile size, or does the opposite.

[nyurik]

@IvanSanchez thx, bucketing is an interesting approach too - but would require a bit more research. Rounding would essentially consolidate all referenced features to 1 out of every 4 tiles, but we would need to run some prototyping tests to see if its worth the extra complexity.