From Google Maps to a 3D Voxel World

PepeDev BlogLeave a Comment

Adventure Box Google Maps Import The Earth

We have seen in a previous post how we texture greedy meshes in voxel worlds, which is one of the pieces of technology we’ve developed to make the rendering of Adventure Box worlds possible. Today we’re going to take a look at of one the ways we create voxel worlds – specifically, how we generate Adventure Box worlds from Google Maps (seems impossible? …Try it right now on adventurebox.com : )

We’ve tested various different services and approaches to make map imports as accurate as possible – but we’re always improving, so we’ll talk in future posts about some of the latest upgrades we’re working on.

The basic map import process is divided into 3 steps:

Retrieving Elevation Data

This is probably the most important step in map import. In the screenshot below, you can see the interface that players use to choose an area of the world to import.  The Adventure Box engine doesn’t use any of this image data – but it does use the coordinates of the corners of the area chosen by the player, to produce a table of x/y values. For example, from the image below we retrieve the corner coordinates:

  • North-West corner: Latitude: 63.782486 | Longitude: -140.361328
  • South-West corner: Latitude: 3.162456 | Longitude: -140.361328
  • South-East corner: Latitude: 3.162456 | Longitude: -57.392578
  • North-East corner: Latitude: 63.782486 | Longitude: -57.392578

Adventure Box Google Maps Import

Once we have the corner coordinates, the next step is to retrieve a grid of elevation points (vertical distances from sea-level) covering the area between the corners, in order to produce a 2-dimension elevation map that we can use to manufacture a voxel terrain.  We do this by requesting elevation data from the Google Elevation API.

We know the size of the world we’re going to create, measured in voxels, so ideally we would like retrieve an elevation point for each surface voxel in the world.  However, if we were to do this, we’d run into a kind of problem that comes up again and again when working with voxel worlds – the amount of data required explodes. Imagine a voxel world with just 256 voxels on each side (which is a small world), for just that area, if we retrieved elevation data for every voxel, we’d need more than 65 thousand points.. Which might be a little slow for the average user, and would very quickly exhaust our Google API request limit!

So, we scale the elevation grid to a resolution that will be more efficient to process – less than 100 points on each side -so “only” about 10 thousand elevation points. This means we lose a little detail, but we can mathematically estimate the missing data later in the process.

To make the retrieval of elevation data faster and more reliable we optimize our requests to the Elevation API by grouping together coordinate requests into rows. A simplified version of the code might look like this:

var path = [
 {lat: 45.55, lng: -18.23}, 
 {lat: 45.65, lng: -18.08}, 
 {lat: 45.75, lng: -17.83},
 ...
 {lat: 47.55, lng: -15.68}];

elevator.getElevationForLocations({'locations' : path }, function(results, status) {
   if (status === google.maps.ElevationStatus.OK) {
       for (var i = 0; i < path.length; i++) {
            saveElevation(results[i].elevation);
       }
   }
});

Once we have our table of elevation points, we also need to scale them vertically.  We know the maximum height of worlds in our engine, and we know the elevations of the highest and lowest points on Earth: the summit of Mount Everest (8848 meters) and the nadir of the Mariana Trench (-11034 meters). With these two bounding values we can scale vertical elevations to fit inside our voxel worlds cleanly, while retaining relative elevations between points.

The final step in processing the data is to estimate the missing elevation points. What we currently have is a low resolution grid with lots of gaps in it – but what we need in order to produce a regular terrain is a smooth elevation surface.

 

3d interpolation

 

To produce a smooth surface we use a mathematical technique called Bicubic Interpolation.  Interpolation functions are used to estimate intermediate values between a set of input values.  For example, the most simple type of interpolation (linear interpolation) might take as input two values: 0 and 1, and a required resolution, 0.25, and output the values 0.25, 0.5, 0.75.. Which are the values that lie between the inputs at a distance of 0.25.  Bicubic interpolation is an extrapolation of linear interpolation into 2 dimensions – so we can use it to estimate missing values on a surface.

This approach allows us to reduce the number of request to the API with little loss of accuracy in the resulting map – allowing us to produce larger Adventure Box map imports, faster.

Texturing the world

So now we have we have a set of smoothed elevation points associated with thousands of coordinates. What next?

We have to transform these elevation points into voxels. This means that we need to identify which voxels in our imported world are air, water, grass… even rock or snow. The most simple approach is to make all negative elevations values (less than sea level) water, and all positive values earth.  This produces the outline of a terrain – but it’s not very interesting! (and players tend to fall out the bottom of the world by just swimming downwards far enough : ) In fact, this is a non-trivial problem. We’re still working on upgrades in this area – but we already produce varied environments using a set of rules applied to elevation data, and by pulling in extra data from other sources.  We use rules like:

  • We map the elevation x/y coordinate to the corresponding voxel world coordinate – for example x=12 (west to east) and y=3 (south to north). Then we iterate over all the voxels on the vertical axis. All voxels under -3000 meters are made sand, then between -3000 and 0 will be water voxel and the rest, from 0 to the top of the map, will be air.

Producing the voxel meshes

The Adventure Box engine already supports a variety of terrain generation and import systems – so, once we’ve prepared voxel data by analysing the imported elevation grid, we can fed this data to our meshing servers, and voila!

The whole world:

Adventure Box Google Maps Import The Earth

The Spanish peninsula and a little of North Africa:

Adventure Box Google Maps Import Spain

Greece and Turkey:

Adventure Box Google Maps Import Spain

That’s where we are for now – you can try it out for yourself on AdventureBox.com.

Next up, we’re going to be working on hooking up our vegetation systems to add plants, trees and flowers to imported maps… And after that – who knows – maybe animal-life!

Thanks for reading – feedback is more than welcome – happy voxeling!

Leave a Reply

Your email address will not be published. Required fields are marked *

twenty three − nineteen =