voxel osm vector tile algo

voxel-openstreetmap.md

This is a rough spec for an implementation of a realtime virtual world using OpenStreetMap data and voxel.js. The basic idea is to encode feature data pulled from Mapbox vector tiles as overzoomed tiles, which can be represented as voxels. This allows for easy scalability, since it utilizes existing algorithms and architecture.

The initial implementation is going on here.

###general

• 1 voxel = 1 tile at zoom 17 = 1.1943 sq meters
• the world is a 33,554,432 x 33,554,432 voxel grid
• assume that a server is serving up vector tile pbfs at z15 (mapbox.com, local, etc.)
• vector tiles are loaded at zoom 15 and geometry is encoded as 4096x4096 pixel coordinates, which is equivalent to tiles at zoom 24

---

---

#algorithm

###load tile

1. get current position game.controls.target().position
2. GET surrounding vector tiles at zoom 15

###process tile

1. use vector-tile-js to convert the vector tile pbf to in memory features
2. for each feature:
3. run tile-cover.tiles() on the feature at zoom 17
4. push each tile to master array of [[x,y,z, material],[x,y,z, material],...]
5. depending on the feature attributes, push duplicates for y levels (height) (ie: a building would go up 10 y tiles x number of stories)

###voxel-engine 'generate' function

1. check for a matching x,y,z in the master array
2. if one exists, return the tiles material code
3. if one does not exist, return 0

---

---

###optimizations

• cache vector tile pbfs, and only GET if the desired tile does not exist
• zoom 15 is maximum detail; if this is too costly, just load a lower zoom and sacrafice a bit of detail
• load lower zoom level tiles at higher chunk distances; reload those chunks at zoom 15 when you get close
• cache voxel arrays, and only reprocess vector tiles as needed (since tilecover is likely to tax the cpu)
• tilecover at {min_zoom: 1, max_zoom: 17} for optimum cover performance; then do some fancy fast math to detect if a voxel is in tiles larger than z17

###realism 'process tile'(see above) could utilize feature specific algorithms, such as:

• if a building is detected, generate voxel patterns for generic doors, windows, roofs, etc.
• if a tree is detected, generate voxel trees
• if a road is detected, draw at different widths depending on the roadway type attribute; could use turf-buffer to easily treat these like regular polygons
• various recreational feature styles like tennis courts, baseball diamonds, swimming pools, etc.
• add a skybox using voxel-sky
• realistic terrain - vary the y (height) baseline using contour line generalization or a secondary elevation dataset interpolated to zoom 15 tiles as a grid
• support world "wrapping", so that you do not fall off the edges
• use osm landcover data to draw snow, grass, sand, vegetation coverage, etc.

###zany ideas

• if a lower zoom level (for performance) was used for the 'load tile' step, a voxel flight sim would be pretty simple to build using a modified voxel-player and voxel-fly with some basic plane physics and a HUD display overlaid on the DOM.
• issue reporting - some sort of feedback mechanism back to OSM. This is more pie-in-the-sky than anything, but if users were able to report data issues through an interface like this, it could increase the OSM userbase.
• the players altitude could dynamically determine the zoom level that tiles are queried at. This would allow someone to have detailed data at a street level, but generalized data at bird's-eye or higher.

###prior art

• voxel-osm
  • open code and stack
  • limited in that it loads a geojson file for all geography form disc; would not scale beyond a few city blocks
  • this approach could be feasable using leveldb with level-geography for indexing and fast geometry querying
  • no movement on this project in the last year
  • code is tightly coupled to the implementation (aka, prototype phase)
• minecraft implementation
  • closed (uses minecraft, and I could not find source code)
  • looks like it uses some custom Feature Manipulation Engine models
  • uses some sort of LIDAR point cloud, as opposed to well defined vector geometry
  • impresive results
• gamedev.stackexchange question
  • purely theoretical
  • goal was to create a [1 voxel]:[1 meter] earth (similar to this)
  • had the requirement of infinite draw distances (only achievable through rendering lower res with modern hardware)
  • interesting ideas for generating landcover data from satellite imagry