rethink tiling geojson

[ansis]

This isn't important right now because the current approach works.

Currently geojson is tiled. If we use 2x32bits per position, we should have enough precision for the entire world without tiling. What would be the performance hit of using the extra space for vector tile features? Could we have different precision for different sources? Would we need to bump up to highp precision in shaders?

[incanus]

Starting to think about this on the native side again, too: mapbox/mapbox-gl-native#328 Original attempt was the same tiling as on WebGL: mapbox/mapbox-gl-native#170

[incanus]

@ansis Could you elaborate a bit more on your thoughts here? I'd like to get cracking on the native side, eventually to the extent of allowing arbitrary features that aren't necessarily backed by GeoJSON.

i.e. should we be thinking about a more generalized data store for non-VT features that GeoJSON or on-the-fly APIs could tap into?

[mourner]

@ansis would love further thoughts on this too. Tiling GeoJSON is currently a problem. #694

[mourner]

Looking at this now... Another way to approach this problem that seems more feasible to me right now is rewriting the tiling algorithm instead of going the precision route. The latter won't solve the problem of loading relatively large GeoJSON data (think 100k OSRM car route across Eurasia), because you'd have to render out-of-view data on higher zoom levels (well pointed out by @kkaefer) and unnecessary precise geometry on lower zoom levels.

So here are 3 things I want to look at:

• a more efficient tiling algorithm — the current one doesn't scale well, see GeoJSON-triggered Chrome crash test case #790 (comment) for how fast it fails
• possibly figuring out the proper zooms levels (instead of hardcoded 1-5-9-13) based on original data precision
• simplifying geometry on each tiling zoom level

[mourner]

Another idea to explore: tile on demand. Don't cut GeoJSON tiles until you actually zoom to a corresponding zoom / area.

[incanus]

The related umbrella issue on the native side is mapbox/mapbox-gl-native#507. With that in mind, and the fact that we'll want to keep the renderers working similarly, the on-demand approach likely won't work as there cannot be a delay between pan/zoom activity and display of overlay data (GeoJSON or otherwise).

[mourner]

there cannot be a delay between pan/zoom activity and display of overlay data (GeoJSON or otherwise)

Why? There's a delay when displaying vector tile data while it is loaded/processed, so a similar (maybe smalllish) delay for GeoJSON when panning and zooming wouldn't look out of place.

[incanus]

so a similar (maybe smalllish) delay for GeoJSON when panning and zooming wouldn't look out of place.

It would on native mobile. There is a delay for the basemap, but never for the point/polyline data on top of it. I'll try to work up a demo.

[mourner]

OK. I'm currently thinking of an adaptive tiling approach that wouldn't make a delay: split the GeoJSON data top-down in a Quadtree-like fashion, keeping track of the number of vertices in each tile, and stop splitting when we reach a certain number. This way we could minimize the number of actual tiles unlike here, making tiling adaptive based on data density instead of a hardcoded zoom range.

The only problem with this approach (which looks kinda cool) is that we would need to rethink tile loading logic as well, because getting the covering GeoJSON tiles for a particular map view would involve messaging the worker. @jfirebaugh what do you think? Is this feasible?

[mourner]

@jfirebaugh ha, just realized that all GeoJSON tiles are sent back to the main thread after parsing the data. This is very inefficient — instead we should keep the data in the workers just like we do for vector data, and load on demand.

@incanus would it be acceptable to have a delay, but a very tiny one, just for loading the tile from another thread (without any tiling/processing work)? The delay would be similar to cached VT and probably not noticeable much.

[mourner]

@jfirebaugh or, for the tile loading, we could return the resulting tile cover (which shouldn't be too big), but not the data itself, so that it's loaded on demand. This way we can keep the tile loading logic but change the way GeoJSON tiles are loaded (so that data is loaded asynchronously when corresponding tile is requested, just like VT).

[incanus]

Based on some load testing, actually I think a tiny delay is ok. Parse delay is naturally acceptable, but in testing 1,000 and 3,000 points in Apple's MapKit on an iPhone 5s, I do sometimes see a slight pan/display delay for the 3,000.

Sample project: https://github.com/incanus/PointTest

1,000 points: https://dl.dropboxusercontent.com/u/575564/1000points.mov
3,000 points: https://dl.dropboxusercontent.com/u/575564/3000points.mov

[jfirebaugh]

_getCoveringTiles is called only by _updateTiles, and both of those are private implementation details of Source. The only public interface is update (which is inherently asynchronous), and if necessary GeoJSONSource can override that to do something special.

Do you have a candidate fast tiling/clipping algorithm that can do tile buffering (which rendering depends on for polygon outlines and cross-tile labeling) and handle the complete range of GeoJSON?

Agreed that a small delay is fine.

[mourner]

Do you have a candidate fast tiling/clipping algorithm that can do tile buffering (which rendering depends on for polygon outlines and cross-tile labeling) and handle the complete range of GeoJSON?

Yes. I almost got the algorithm working — will probably crack this today. Starting From the top 0,0,0 tile, it recursively cuts each tile into 4 tiles with a buffer, simplifies geometry for each tile based on zoom, and stops recursion when we either reached max zoom level or got below a certain threshold of points total across tile features.

The new approach should run much faster, scale better with growing data size and lead to faster and better quality GeoJSON rendering.

[mourner]

stops recursion when we either reached max zoom level or got below a certain threshold of points total across tile features

Just got an idea of a much smarter metric! If simplification run on a tile didn't throw out any points, don't tile further.

[mourner]

So, my tiling algo (although not yet made to work in GL JS) seems to work really well. I'm currently stuck figuring out the right logic of determining whether the tile is nice enough to stop tiling it further so that it works well with different types of data.

The logic can be based on any combination of the following metrics:

1. Total number of features in a tile;
2. Total number of coordinates in a tile;
3. How many points were thrown out during simplification for the current zoom

Obviously the logic heavily affects tiling performance and the final number of tiles. We need to adapt this to handle lots of features, features with lots of points, and lots of features that don't get simplified (such as a million point features) of different density and precision.

[mourner]

Looks like I need to relax and have a beer right now to figure out the best solution.

[incanus]

Awesome. Is this specific to GeoJSON? Or just similarly-structured data?

[mourner]

@incanus not specific, can be rewritten for any geometries. Currently it only supports points, polylines and non-holed polygons, but the rest can be done later as the current GeoJSON code doesn't handle it either.

[mourner]

Here are some further ideas that seem simple enough and worth implementing:

• run through all coordinates of all features; for each point, calculate and save the first zoom at which the margin of error for the point encoded into 4096 integers goes below some small threshold; when considering a tile for cutting, we can determine whether to cut or not by looking at the maximum of calculated zooms for each point in the tile. This way we don't compromise precision while not doing unnecessary tiling
• don't simplify features for each tile; instead run Douglas-Peucker algorithm (fast O(n log n)) once for all features before tiling, saving the deviation of each coord instead of throwing out points; then for each zoom, simplification will be a matter of picking out points less then a particular threshold, making it fast and enabling easier simplification-based heuristics

[mourner]

A work-in-progress repo here: https://github.com/mapbox/tilegeojson
Making this a separate repo because adaptive GeoJSON slicing can be useful outside the GL land.

[mourner]

Can't believe I didn't think of the following super-simple idea earlier. @jfirebaugh @incanus

We want to do all the expensive CPU work by preprocessing GeoJSON on load, and then display it at any area/zoom without noticeable delay. But tiling up to z14 to keep precision usually produces too many tiles and is often too slow (imagine the use case of low-coordinate shapes covering most of the world).

A solution to both problems (load delay & too many tiles): tile the data until we did most of the work; stop tiling when further tiling of a particular tile is cheap. Cheap usually means that the number of coordinates in a tile is low enough. If it's cheap, we can tile further on-demand almost instantly, without delay. Awesome!

[mourner]

The current algorithm in GL JS crashes on 250Kb GeoJSON, but I thought it wouldn't be unreasonable to eventually make it work with a 100Mb file (zip codes, not simplified) that has 33k features with 5.4 million points. Not that it's very practical to load files like this in a web app, but it's a good stress test:

These are all clipped and simplified 4096 vector tiles (with tiny features filtering), initially sliced to z4 but with on-demand slicing of higher zoom tiles (the viz is a simple canvas app to help debugging). Integrating into GL JS should be easy now. cc @springmeyer @yhahn @tmcw

update: noticed a bug in the drilldown code, it should be 3 times faster now:

[mourner]

Made it a bit faster since the last comment (in parallel to cooking a dinner):

[mourner]

Done, w00t!

[mourner]

Watch that 100Mb zip code file:

[kkaefer]

Wow, impressive work!

[bFlood]

that is really impressive, great work mourner

[wboykinm]

👍 👍