How (sometimes) assuming the Earth is “flat” helps speed up rendering in deck.gl
deck.gl is an open-source WebGL-powered framework for visual exploratory data analysis of large datasets. The latest v6.2 release includes a new feature that improves the rendering performance of geospatial visualization by up to 48x. This article will review in-depth how it works.
The challenge of shader-based Web Mercator projection
At runtime, deck.gl’s MapView uses the Web Mercator projection to place geographical features on screen. When rendering each frame, based on the zoom level set by user interaction, deck.gl performs the following transform for each coordinate from [longitude, latitude, altitude] to [X, Y] on the Mercator plane:
As you can see, the mapping from latitude to Y is non-linear. The calculation relies on expensive trigonometric and logarithmic operations and must be executed for every single coordinate in a potentially very large dataset. This is because the earth is not flat!
Unlike most mapping libraries (such as Mapbox GL JS), deck.gl does not do this on the CPU. Because deck.gl is designed to work with millions of data points that change frequently, doing Web Mercator projection on the CPU has a severe performance penalty. Instead, it passes the coordinates as-is to the GPU and performs these transforms in a vertex shader.
When we pass geo-locations into the WebGL shader, a new problem emerges. According to the WebGL reference card, The precisions for floating point numbers are as follows:
Consider the following location: [-122.4000588, 37.7900699]. Casting it to 32-bit floats, we end up with [-122.40006256103516, 37.790069580078125]. The real-world difference between these two points is 0.3325 meters — more than a foot.
The consequence is that, while everything works fine for broad overviews, when zoomed in, precision issues start to show as points visibly being deformed and “dancing” around with even the slightest viewport change.
Introduction of emulated 64-bit floats
To reduce this artifact, deck.gl v3 introduced emulated 64-bit precision float numbers. Each number is sent to the GPU in two parts:
highPart = Math.fround(x)
lowPart = x-highPart
Then, we emulate 64-bit floating point operations with a cascade of operations using 32-bit floats at the expense of more GPU computing cycles. For example, one 64-bit division operation will map to eleven 32bit arithmetic operations, and a mat4-to-vec4 multiplication in 64-bit requires 1952 32bit operations. The details of the algorithm are beyond the scope of this post, but if you are interested the actual code can be found here.
Despite its near-perfect results, the emulated 64-bit matrix operations impose a severe hit at runtime performance. Due to the mammoth size of the shader code, some older graphics card drivers are incompatible, while some others take more than a few seconds to compile it, causing the browser to freeze.
Alternative solution: offset mode
As a cheaper alternative to the emulated fp64 solution, deck.gl v5 introduced the LNGLAT_OFFSETS coordinate system. In this mode, instead of using [lng, lat], each geolocation is specified in [Δlng, Δlat] as the “offset” from a fixed point — the coordinate origin. In the shader, a linear approximation is used to project the degree difference to pixel difference on the Mercator plane:
Where the constants K[ij] are determined by the latitude of the coordinate origin using 2nd-order Taylor series expansion.
(calculation based on zoom level 12)
While the error of this linear approximation increases with the offset, within ±0.1 degrees range (well covers the size of a city), the error is generally imperceptible. When looking at things at the local level we can assume that the Earth is flat. When the offsets are so small, 32-bit float numbers can sufficiently capture the required precision, thus eliminating the need for complex emulated 64-bit operations. As no trigonometric functions are involved, the shader execution is lightning fast.
Yet there are significant disadvantages to using this coordinate system. Firstly, the user is required to write extra code to extract the offsets out of the raw data. Moreover, any predetermined coordinate origin can only ensure tolerable error for points within a limited geographical region. When dealing with a sprawling dataset, strategic slicing may be required.
A new idea
While working on heavy-duty, precision-sensitive mapping applications, we find ourselves wishing to have the best of both worlds: the convenience of the traditional LNGLAT coordinate system, and the performance of the LNGLAT_OFFSETS coordinate system. The idea is simple: instead of specifying fixed coordinate origins, all coordinates are converted to “offsets” on the GPU from the center of the viewport.
The dynamic choice of coordinate origin works in our favor: the viewport has a limited size, which means that any far-away points that are projected with significant errors are cut off by the edge of the screen. Better yet, the coverage of a viewport shrinks exponentially as the zoom level increases, canceling out the scalar effect of the error:
(calculation based on 2000x2000 viewport)
Comparing this graph with that of the 32-bit web mercator projection, we created a new coordinate system that combines the normal mode and auto offset mode: when the zoom level is below a threshold, we will use the “proper” projection; other, we will use the coordinate offset “flat” mode, setting the center point at the center of the viewport. We always take the mode with the smaller error at any given zoom level.
At every frame, deck.gl compares the zoom level and changes the projection method accordingly. Switching between projection modes only requires updating a handful of uniforms, and can be done at almost zero cost to CPU or GPU time.
Result
Accuracy
The new hybrid coordinate system (yellow) has comparable accuracy to the 64-bit mode (red), even though it only uses 32-bit. The legacy 32-bit mode (blue) is unstable at the same zoom level.
Performance
The new hybrid coordinate system is faster than the old 32-bit mode and up to 48x faster than the old 64-bit mode.
Acknowledgements
Thanks Xiaoji Chen and Yang Wang for helping me edit this.
