Testbed-12 Vector Tiling Engineering Report

The render-based tiling approach is mainly focused on high-quality and high-performance rendering of vector data. With this approach, tiles are generated starting from a render-ready version of the vector features. This render-ready version can be seen as a tile with rendering instructions, ready to be submitted to the client device’s rendering engine. For instance, a tile might contain instructions to move to a pixel position (moveTo) or to render a line to another pixel position (lineTo). This approach is somewhat similar to SVG geometry primitives. The data is projected up front. Clients can read the tiles without the need to do any feature geometry assembly, reprojections or other intensive operations.

Compared to rasterizing the vector data and then using raster tiles, the above approach avoids rendering artifacts when rendering tiles at scales other than the available levels of detail. Additionally, it gives users the flexibility to customize the styling of the data client-side. Although the original geometry is no longer present, a tile can offer access to the feature’s properties. If a unique ID is present, it could be used to retrieve a feature’s geometry from a separate service (e.g., an OGC Web Feature Service (WFS)).

From an OGC web services perspective, this best relates to OGC WMTS. This web service is focused on serving tiles for rendering; each tile can be individually interpreted and rendered.

Typical use cases are rendering and slippy map.

The benefits are high-performance and high-quality.

A feature-based tiling approach is mainly focused on giving users efficient access to the source geometry (coordinates) and feature properties in a vector data set, regardless of their physical size and amount of detail. In this approach, features are split into component pieces based upon their geometry and the tile grid pattern used. A resulting tile contains the geometry pieces of the feature that are geographically contained in that tile. Apart from the geometry, the tile offers access to the feature’s properties, similar to the render-based tiling approach (either as a link or embedded in the tile). This will be discussed in the Performance and Memory Usage chapter. The tile also offers access to information necessary to reconstruct the feature’s original complete geometry. If required, the client has responsibility for reconstructing the features and displaying them in the client’s map projection. The tiled geometries may be defined in the data’s native reference or reprojected to another reference.

Typical use cases are rendering and analysis.

The benefits are high-quality and the fact that the original feature data are no longer needed.

A popular and widely adopted vector tiling specification is the Mapbox Vector Tile Specification [5]. The approach followed by Mapbox' specification can be classified as render-based tiling.

Cesium 3D Tiles is a public specification to stream 3D content, including buildings, trees, point clouds, and vector data to web applications [6]. Vector data tiles include WebGL calls, classifying the approach as render-based tiling. At the time of writing this ER, the specification has been submitted to the OGC as a candidate Community Standard [7].

Indexed 3d Scene Layer (I3S) [8] originated from investigations into technologies for rapidly streaming and distributing large volumes of 3D content across enterprise systems that may consist of server components, cloud hosted components, and a variety of client software from desktop to web and mobile applications. A single I3S data set, referred to as a Scene Layer, is a container for arbitrarily large amounts of heterogeneously distributed 3D geographic data. A Scene Layer is structured as a set of hierarchically structured nodes, which are analogous to tiles, and Levels of Detail (LoD). A Scene Layer is characterized by a combination of layer type and profile to fully describe the behavior of the layer. At the time of writing this ER, the I3S specification has been submitted to the OGC as a candidate Community Standard [9].

CDB is an OGC standard defining an open format and encoding for the storage, access and modification of a representation of the natural and built environment for simulation applications [10][11]. CDB makes use of several commercial and simulation data formats that are in widespread use within the simulation industry. For vector data storage, the Esri Shapefile format is used as a best practice [12]. One of the core CDB concepts is the use of a tiled representation of the Earth with multiple levels of detail. Each tile can link to data, such as a Shapefile dataset consisting of vector features. Consequently, CDB can be classified as a variant of feature-based tiling. CDB does not define a stand-alone vector tile format but it does define the means to use tiling and multiple levels of detail with existing vector formats that are unaware of these concepts.

Next to open specifications listed above, the industry also defined proprietary implementations on the topic. The following is a non-exhaustive list identifying several representative implementations and their classification with respect to the vector tiling approach:

.

An easy approach to provide feature access is to store a link or id in the vector tile, which can be used by an application to request the native feature from a data back-end / server. This approach is ideally suited for a client/server environment in combination with render-based tiling: the render-based tiles are sufficient for standard visualization purposes, while the link / id can still be used to retrieve the underlying feature, if needed. From an OGC perspective, this corresponds to the goal of the GetFeatureInfo request available in the OGC WMS and WMTS standards: give the user the ability to retrieve additional information about a selected location on a map / tile.

For the case of feature-based tiling, data coherence can be supported by storing the necessary information in the tile to assemble the feature in an application. This also avoids the need for an external connection to retrieve the feature. The information to be stored should enable an application to differentiate between geometry natively available in the feature (possibly simplified) and geometry introduced by the tiling.

While the approaches listed above provide a solution to achieve data coherence, they either require accessing the feature on a server or the ability of an application to assemble a feature (which can be computationally intensive for large datasets). If complex styling is the primary use case (on-path labeling, complex stroking, etc.), an alternative solution consists of generating vector tiles with bounds slightly larger than the tile bounds and rendering them with a clip on the tile bounds. Chapter 13 discusses this approach in practice.

While generalizing the geometry of a line can be relatively easy for an isolated feature, special attention needs to be paid to the topological relationship between geometries in case of multiple features. Even within a single feature, topological relationships between the individual line segments exist that can make the line generalization process more complex. The images below illustrate this with an example.

The first image shows a variation of the previous feature, represented by a black line. The second image shows a generalized version, represented by the blue line. The generalized version includes an intersection between two line segments of the feature which was not present before, hence a change in the topological relationship. The same can happen between segments that belong to different features. A common real-world example is an island located close to a coast; regardless of the generalization, both features should remain distinct at all scales.

Extensions to Ramer-Douglas-Peucker and alternative algorithms are available to also take into account topological relationships between line segments within a single feature or across multiple features.

A special case of topology preservation is shared segment generalization. Consider two features with adjacent line segments - for instance, two country border features. To make sure that the adjacent line segments remain adjacent, they need to be generalized in the exact same way. Although topology preserving line generalization techniques could be used to address this, another approach is to represent the adjacent segments as a single set of segments. Apart from solving the topology preservation issue, it also reduces the amount of data needed to represent a data set.

Probably the most widely used and one of WMTS' well-known tiling schemes is the GoogleMapsCompatible tiling scheme [13][14]. This approach specifies a Web Mercator map projection (EPSG:3857), a square layout, a fixed tile size of 256 x 256 pixels and 18 zoom levels.

The GoogleCRS84Quad is defined by WMTS as a well-known tiling scheme. Apart from the projection this approach is equivalent to the GoogleMapsCompatible tiling scheme. It uses a geodetic reference instead of a Spherical Mercator projection.

The GlobalCRS84Scale tiling scheme is defined by WMTS as a well-known tiling scheme. This approach specifies a geodetic tile pyramid (CRS:84), a square layout, a fixed tile size of 256 x 256 pixels and 21 zoom levels.

The World Mercator tiling scheme is defined by NGA’s NSG WMTS 1.0 Implementation Profile [15]. That profile specifies a Mercator map projection (EPSG:3395), a square layout, a fixed tile size of 256 x 256 pixels and 25 zoom levels.

The WGS 84 Geodetic tiling scheme is defined by NGA’s NSG WMTS 1.0 Implementation Profile. This approach specifies a geodetic tile pyramid (EPSG:4326), an equirectangular layout, a fixed tile size of 256 x 256 pixels and 24 zoom levels.

The choice of a coordinate reference system (CRS) is an important question and is impacted by the intended use of the vector tiles. If visualization in a fixed projection is the main use case, then choosing a tiling scheme built around that projection makes sense. An example is the Mapbox Vector Tile Specification which specifies the Web Mercator projection. In use cases where there is no single projection specified and reprojection is needed, and/or if feature processing is required, then choosing a tiling scheme built around a geodetic reference (in case of geodetic source data), not specifically tied to a projection, would be preferred.

By definition, a tile pyramid has a set of levels or tile matrices, each representing a set of tiles at a given scale. In case of raster data, the deepest level of detail typically corresponds to the scale needed to be able to represent the original raster data. For example, in the case of raster data with 10 cm/pixel and NGA’s World Mercator projection, you need 22 levels to represent the detail down to the original source. This is based on the quad-tree tiling scheme’s zoom level scale set table ([15], Table 8). With less zoom levels, you will not reach a 10 cm/pixel resolution.

The choice for a maximum level of detail is different for vector data, as there is no concept of resolution or pixel density. Additional levels of detail are mainly needed if something changes to the state of a feature. Examples of changes:

If there are no further changes beyond a given level of detail, there is no enhanced value in adding more levels of detail, since vector data can be rendered with infinite precision - in contrast with raster data. An application can simply use the latest level of detail and use the associated features, regardless whether the current map scale is at a higher level of detail.

The tiling schemes discussed above are all built-around a similar quad-tree structure. Although a quad-tree tiling scheme structure is the most common one in practice because of its efficiency and simplicity, other tiling scheme structures exist that focus on specific use cases, such as:

As an example, the I3S specification supports the use of multiple indexing schemes. I3S is agnostic with respect to the model used to index objects/features in 3D space. Both regular partitions of space (e.g. “Quadtrees” and “Octrees”) as well as density dependent partitioning of space (e.g. R-Trees) are supported by I3S.

A major decision is the choice between tiling on a pixel level or at a coordinate level. This directly relates to the two vector tiling approaches discussed at the beginning of this Engineering Report, render-based tiling and feature-based tiling.

When tiling on a pixel level, vector features are rendered during the vector tile production process. This is done to determine the instructions needed to render the data in an application. These render instructions should be directly usable by a rendering engine in a consumer (client or (rendering) service). Consequently, this is the easiest approach from a consumer’s point of view.

The SVG format is a good example of how such rendering instructions appear. The instructions are typically in the form of moveTo pixel position A, lineTo pixel position B, etc. The resulting rendering instructions are clipped according to the tile boundary and stored in a tile.

When tiling at the geometry and coordinate level, vector features are tiled using their original geometry (transformations can be optionally used, as indicated in the previous chapter). Consumers need to transform them to pixel coordinates, using a projection of choice. Consequently, this increases the complexity in the consumer (client or (rendering) service), compared to pixel level tiling. It does have the advantage of being projection-independent, which can be important for certain use cases.

Depending on the geometry type, multiple tiling strategies can be defined.

For the render-based approach, assembly of features is generally not required. The targeted use case is high-performance & high-quality visualization. To maximize the performance, consumers should be able to directly read and visualize a tile’s contents.

For the feature-based approach, assembly of features may be required to support operations that require the representation of the original feature - aligned with the targeted use cases of feature-focused vector tiling. The ability to assemble a feature contained in multiple tiles does make it considerably more complex for a producer and consumer:

When visualization is the primary use case, special clipping techniques can be used by both the raster and feature-based tiling approaches to avoid tile-related rendering artifacts with common styling, without the need to have the full geometry. The Styling chapter will further discuss this.

One solution is to include attributes in the vector feature tiles. This enables direct use of the attributes in applications, to support a variety of use cases:

An attention point for this approach is the amount of storage needed to store the attributes. A simple but effective solution is the introduction of an anchor tile.

Depending on the vector feature’s data type, the number of attributes can be significant. For instance, in case of the AIXM 5.1 aeronautical data format, a vast number of attributes can be defined for a feature, including an entire ISO 19115 metadata description. Depending on the targeted use case and available transfer bandwidth, there might be too much information to store in a tile. A tile with too much information can reduce the performance benefits related to vector tiling. An alternative solution is to keep the attributes in a separate data store and make them available upon request - potentially through a web service. A tile (possibly only the anchor tile) could include a link to this store, so that users can access it. Conceptually, this approach is comparable to the OGC WMS GetFeatureInfo request, which enables users to request more information for a given location on a map retrieved via the WMS.

Hybrid approaches can be defined that use a combination of attribute storage in the tile and on the server. This enables users to make the most important attribute information readily available in the tile, while less frequently used information can be requested from a server.

In case of the feature-based tiling approach, by reassembling the geometry pieces across the different tiles, the feature’s original geometry can be reconstructed. By applying the style on the resulting feature, there will be no impact anymore from the tile boundaries.

Another solution that works both with the feature-based and rendering-based tiling approaches is to define the vector tiles with a boundary slightly larger than the bounds of the tile. When the data gets rendered, the rendering engine needs to apply the tile bounds as clipping bounds, hence avoiding the boundary rendering artifact.

The figure below illustrates this by showing the rendering of the feature’s segment that is located in the left tile. The grey line represents the tile boundary. Without any clipping bounds the result would look like the rendered road in this figure.

By applying the clipping bounds, the piece right from the grey line will not be rendered, as shown in the figure below.

By applying the same clipping technique to the other tile, as illustrated in the figures below, the end result will be as in the initial figure, without any tile boundary lines.

When the requirement is to store the attributes of features directly into the tile (for fast access by an application), consider the concept of an anchor tile allowing the storage of the feature attributes only once. In case of large datasets with many attributes, this can result in a significant reduction of required memory, both in the application reading the tiles and in the data container storing the tiles. In the application, this typically outweighs the cost of one extra request to get the anchor tile.

With render-based tiling, a tile is optimized for high-performance visualization: an application reading tile needs to apply the rendering instruction to have the tile contents displayed on the screen. Performance-wise, this typically outperforms a feature-based tiling approach, since there are no geometry assembly and/or reprojection steps involved.

In case of render-based tiling, a feature’s geometry is already projected to screen coordinates, avoiding the cost of any additional projection logic. In case of feature-based tiling, this is not the case. However, if there is a commonly used target reference, it does make sense to transform a feature’s geometry to this reference. This avoids the need for an application to do the transformation on-the-fly for each tile. For instance, in case of source data defined using one or multiple references and an application that always uses Mercator, it is recommended performance-wise to transform the data to Mercator during the vector tile production process.