In this article we will offer an overview of current best methods for building large scale 3D terrain maps and present two open source tools that will help you build your own: TIN Terrain and CesiumJS. TIN Terrain is our new open source tool that generates TIN meshes from raster terrain. CesiumJS will load these meshes and render them on a client.
Digital and web based maps have been stuck in 2D mode for many years, but with an ever increasing supply of good quality terrain data, there is now a race to provide 3D mapping services. Use cases for this are numerous. Terrain can help in routing and path finding, construction, visualisation, simulation or simply yield a better and more compelling user experience.
Crater Lake terrain rendered in 3D
Where does data come from?
Height data is measured by satellite or aerial vehicles using a number of techniques. The newest one of which is autonomous flying drones that can infer the 3D dimension from scene video using photogrammetry.
Why is 3D hard?
Large scale big data
These datasets can be very detailed with resolutions down to 20cm and are therefore extremely large. For example, raster terrain data covering 100 square kilometres at 20cm resolution comes to roughly 20GB of data. To map an area of a typical city like Berlin would generate around 180GB of data. This presents a challenge. Web-based and mobile maps must retrieve terrain data at the correct location and resolution, and transfer this over the network in reasonable time.
Once the data has arrived at the client, it must be rendered to produce visually appealing and realistic imagery. If we want to use hardware accelerated graphics, we need triangle meshes. Height data is however typically stored as raster data, so it must be converted first. To do this well, in an optimal way, is non-trivial and run-time intensive.
How can it be done?
So in practice, how do we overcome these challenges? In this section we will briefly outline the current best solutions for building 3D terrain maps.
Let's start with the data: Terrain data is collectively referred to as DEM: Digital Elevation Models. A distinction is also made between raw ground elevation (DTM: Digital Terrain Model) and height measures that include man made structures such as buildings (DSM: Digital Surface Models).
The difference between DSM and DTM
There is an increasing wealth of terrain data for many parts of the globe. These typically come in raster formats but at widely varying resolutions and accuracy. Raster data in this context means that height measurements are stored at a fixed spacing in a 2D grid. This is very similar to the way brightness is stored in a bitmap image or photographs. The data here is not truly 3D but “2.5D” because there is only one height measure for each surface point. This means that such data does not accurately model tunnels or overhangs, and is not ideal for mapping buildings and cities in detail.
However, 2.5D is sufficient to describe most natural terrains, while keeping things simple. Terrain can be stored in a number of file formats but is mostly delivered as GeoTIFF, a format which in addition to the data contains the size of the raster and the position in geo coordinates, plus projection information. As the files tend to be very large they are usually split into more manageable tiles.
Crater Lake DEM as "depth map": brightness represents height
If you want to build your own maps you can now get data from a number of popular free sources or even make your own. For small areas you can now gather this yourself by flying drones. For anything larger you are stuck with either buying or sourcing free data. Fortunately the free offering is getting very comprehensive.
Here is a list of some good free terrain data sources to get you started:
Tiling and quad tree zoom levels
Tiling is the current standard way to efficiently load and display web based maps. This method can be applied to both raster and vector content. For example, satellite images are stored and transferred as bitmaps. Roads and geographic geometry are typically stored as vector data. This data is then partitioned into tiles and for each zoom level there is a separate tile set with the appropriate level of detail. This method is called quad-tree tiling.
Tiling of images (same principle applies for terrain and vector data): All tiles have the same resolution, so for lower levels of detail, less tiles are used.
For lower levels of detail, fewer tiles are used. This is true for both terrain and vector data.
We can apply the same tiling principles to terrain data, since it is similar to image data. However, once transferred to the client, the terrain data needs to be displayed in 3D, and for this we need meshes. There are a number of ways to create these.
Meshing on the fly
In the simplest case we use an existing image tile server to transfer raster terrain and convert to a dense mesh on the client, just before rendering. This means every height measure in the raster becomes a vertex in the mesh. This places extra runtime demands on the client as meshes with many vertices are slow to render.
Height data can be efficiently stored in a raster format or converted for display to a regular mesh by adding edges to form triangles.
A better approach is to generate tiles of optimized meshes (or TIN's, see below) on the server, where it can be computed offline and free from runtime constraints and memory limitations. These type of meshes are also typically smaller than an equivalent raster (especially if it's compressed), so there are bandwidth advantages too.
One of the main engineering challenges is to generate good meshes from raster data. In the simplest case, 3D triangle meshes can be made directly by taking each height measurement in the original raster and adding a vertex for it. However, this makes for very large meshes that are inefficient to store and display. In many cases, not all of these vertices are needed to define a surface.
The difference between regular meshes and irregular meshes (TINs): the latter make more efficient use of vertices by placing them only where needed.
This is where TIN’s come in: Triangulated Irregular Networks. These are meshes that contain only vertices where they define meaningful change in surface height. In flat areas, where there is no extra data required, no vertices are added. To illustrate this, imagine a perfectly flat square: We can define this using two triangles and only four points, regardless of the resolution or area covered. By the same principle, we can define some areas almost perfectly with only a few points while for others we may need many more.
Single Crater Lake TIN tile
Putting it all together
So then, how can you build your own 3D terrain maps? There are basically two approaches:
- Raster tiles on server and dense meshing on client
- TIN mesh tiles on server and direct display on client
Crater lake terrain rendered in our quantised mesh viewer, showing tile coordinates.
Raster terrain tile sets: dense meshes only get created on the client.
TIN mesh tiles
Except not quite. Terrain tiles in this tool chain are still in raster format, which is inefficient to load and slow to render. So option 2. is a better solution: storing optimised irregular meshes (TIN's) on the server and transferring and displaying them efficiently on the client. This becomes especially lightweight if meshes are compressed using Cesium's modern quantised mesh format. This is our preferred and recommend path.
TIN mesh tiles created offline to reduce rendering overhead due to smaller vertex count
However, we found no viable open source software that generates these meshes. So, to make this all very easy, we developed our own: TIN Terrain, an open source tool for generating modern quantized meshes from large raster files. TIN Terrain generates a directory structure of quantised mesh tiles at multiple resolutions which can then be directly loaded in any CesiumJS based client.
Crater Lake terrain assembled from a mosaic of TIN-terrain meshes
Same set of mesh tiles with rendered surface
The open source tool Tin-Terrain in combination with CesiumJS allows you to privately or publicly host your own state of the art 3D terrain map. We have provided a sample client application, complete with tiled TIN meshes for you to get started.