-
Notifications
You must be signed in to change notification settings - Fork 2.2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
rethink tiling geojson #464
Comments
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 |
@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? |
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:
|
Another idea to explore: tile on demand. Don't cut GeoJSON tiles until you actually zoom to a corresponding zoom / area. |
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). |
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. |
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. |
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? |
@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. |
@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). |
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 |
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. |
Yes. I almost got the algorithm working — will probably crack this today. Starting From the top The new approach should run much faster, scale better with growing data size and lead to faster and better quality GeoJSON rendering. |
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. |
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:
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. |
Looks like I need to relax and have a beer right now to figure out the best solution. |
Awesome. Is this specific to GeoJSON? Or just similarly-structured data? |
@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. |
Here are some further ideas that seem simple enough and worth implementing:
|
A work-in-progress repo here: https://github.com/mapbox/tilegeojson |
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! |
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: |
Done, w00t! |
Wow, impressive work! |
that is really impressive, great work mourner |
👍 👍 |
* WIP: model conversion gltf to mapbox * WIP: Model loading and naive rendering * Fixes review comments * Add linter to 3d-style and do a pass
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?
The text was updated successfully, but these errors were encountered: