From Rigs of Rods Wiki

Magna Terra is a new terrain engine for rendering truly massive landscapes in OGRE, whose first implementation will be in Rigs of Rods.  When I say truly massive, I am talking about the entire US at 30m resolution, or the whole world at 90m resolution, with enough fractal detail to bring it down to 1m or less perceived resolution.  The development is starting as an OGRE-only project, but will be included in RoR as early as possible to ensure that it leaves enough processing time for a game engine to function.  RoR is especially well suited for this task as it is already computationally heavy.  If Magna Terra can run alongside Rigs of Rods, it should be able to power almost any OGRE game.

Contents 1 Goals 2 Progress 2.1 Compression System 2.1.1 Results: 2.2 Climate Maps 2.3 Terrain Scale 3 Reading List

Goals

Magna Terra is designed to be a terrain engine that can render truly massive landscapes.  While rendering large, low-detail terrains is already possible (ala Grenoble), the goal is to create both much larger terrains, and much higher detail terrains, than are currently possible.  Here is a list of goals I hope to achieve:

• Support very large terrain datasets of 256Kx256K (65M) points or more.  For reference, the global SRTM data set at full 90m resolution is 432K x 144K (62M) points, and the US NED data set at full 30m resolution is 216K x 90K (19M) points.
  
• Support very high detail (1m or less horizontal resolution) for portions of the terrain close to the observer through fractal detail generation.
• All together, I want to support at least 8,000 km x 8,000 km land areas with 1m resolution with a data file that is less than 1GB (very good compression required).
• I'd like to be able to support the entire US (6480km across) in one data file (a zip of pgf images) with 30m resolution stored and 32 fractal subdivisions on the fly for sub-1m detail.
• Fractal parameters to control the roughness and scale of the fractal details.
• Climate maps to describe the climate over a large area in terms of mapping from elevation and normal to a specific texture (sand, dirt, grass, rock, snow, etc.).  This prevents the need to store huge blend maps along with the height data.
  
• Calculate normals for each node of the quadtree as they are loaded into memory.  This prevents the need to store those normals on disk along with the height maps.
  
• Use bezier curves to loop areas which will have different climates (everything from mountains, plains, and urban climates to parking lots and oases) or as a line for roads, paths, trails, rivers, etc. Width, edge-fading, and fractal parameters to make the edges more natural (think: dirt path) will satisfy most needs that are normally stored in a huge blend map covering the entire terrain at even higher resolution than the height data. The entire interstate system in the US should fit easily into a 1MB file, for instance. This will look similar to the road-laying options already available, except that you will be able to define truly curved roads, and they will be tesselated as needed based on the distance to the camera.
  
• Support loading of pages from disk or a URL.  URLs are a down-the-road feature, but will allow for dynamic terrain in massive games.
  
• Support view distance of 256km+ in any direction. This is the maximum view distance from an elevation of 5,000m due to the curvature of the earth. This gets you over Mt. Whitney, but not necessarily Mt. Everest (you'd need a 360km view distance for that).  In reality, the view distance will be closely tied to the size of a page to prevent having to keep too many pages in memory.  It currently looks like a page is going to be 108km wide (1 degree), so the view distance will be somewhere less than 216km to leave time to pre-load pages.  Support view distances of 390km in any direction.  This is the maximum view distance from an elevation of 12km (cruising altitude of commercial airlines) due to the curvature of the earth.  This also fits nicely into the page size, as one page is 128Km (1Km = 1024m), so 3 pages are 393,216 m accross.  This leaves 3,216 m to load/unload pages, ensuring that no more than 7x7 pages are in memory.
  
• All pages which are within the view distance must fit in memory easily, with plenty of room for everything else. This requires only loading the LOD's that are visible (or about to be visible) into the quad-tree, and aggressively unloading higher detail terrain as you move away from it.
  

Progress

Compression System

I've found an image coder that has some great properties for compressing heightmaps (see the link to PGF in the reading list). This codec is integer-based, which makes it much faster for the necessary CPU decompression. In fact, it seems to be almost as fast as JPEG, while being almost as accurate as JPEG2000 (which is 10 times slower). At a good quality level (quality 7, PSNR = 76 dB, average error RMS = 3.15 m), we get 110:1 compression ratios (the entire US fits in under 426MB). At a decent quality level (quality 10, PSNR = 66 dB, average error RMS = 8.9 m), we get 700:1 compression ratio (there is some visible smoothing on steeper cliffs, but the US fits in under 67MB). If you can tolerate a 23 m average error (about the same as the distance between two height samples), you can fit the entire US in under 20 MB (quality 13). On the other end of the spectrum, a DVD release that had room for 2.2GB of terrain data will have an average error around 0.8 m. The only thing left is to get these heightmaps rendered and see if there are any blocking artifacts or similar issues that are highlighted by the lighting and shading of the terrain.

The other good quality of this compression scheme is that it supports region of interest queries, as well as power-of-two level based queries. In other words, I can query any node at any level of the quadtree directly without having to decode anything but the node and its parents. This equates to, on my computer, the ability to extract any node in under 25 ms. To put that in perspective, an airplane flying at the speed of sound could decode 400 nodes in the amount of time it takes to cross one leaf (smallest) node. A leaf node is about 3400 m across, the speed of sound is 340 m/s, and 25 ms decode time is 40 nodes per second. So there will be plenty of capacity for other calculations (like physics) while the engine is running. JPEG2000 supports the same region of interest and progressive decoding features, but it takes a lot longer. For the test on my machine, I got 13 seconds to decode an entire 8192x8192 page in JPEG2000. The same page took 1.504 seconds to decode from the same compression ratio in PGF. The PGF file had an RMS error of 10.3, while the JPEG2000 file had an RMS error of 9.1. I'll take 1.2 extra feet of error over an aditional 12 seconds of loading for each page any day.

Bear in mind that these numbers are based on tests of the Grand Canyon area. When applied to the entire US, which is on average flatter and smoother, we will see better compression rates, lower error rates, and overall more quality for less space. I'm just testing with one of the more difficult to compress areas of the US to get a worst case scenario.

Results:

The entire US NED data set has now been compressed at quality 7, which seemed to yeild nice results even for the rugged landscape of the grand canyon region.  The results are better than expected.  Each 4097x4097 page was compressed in 0.4-0.5 seconds.  Bear in mind that a single terrain page represents 1024 multi-resolution nodes which themselves are 4km across.  The entire terrain page is 128km across.  Since the PGF algorithm is symmetric decompression times are expected to mirror compression times, meaning that extracting huge chunks of the world in under a second are easily acheivable.  To put it into perspective, it took less than 10 minutes to compress the entire US dataset.  Unless someone is planning on building a rocket that can cross the US 3 times in under 10 minutes, then I don't believe decompression is going to be a bottleneck.  The compression ratio turned out better than expected as well.  The US dataset is 143 MB. This represents an average compression ratio of 234:1, and an average download size per page of 140 kb. Given the world size of the page, that is plenty small enough even for people on dialup (you would have to go faster than the speed of sound to overwhelm a 56k modem's download rate). There is still a little room to increase compression around shorelines as the source data is a little noisy, but I doubt it will make much further impact.

Climate Maps

This is the kind of data the climate file would capture:

Climate 0 (and default climate parameters if no rule match in current climate): fractal scale = 10 (the maximum change to the height values from the interpolated height is 10 meters) fractal roughness = 0.5 (each octave of the fractal function is 1/2 the scale of its previous octave) for normals 45 degrees off vertical or more and heights below 3000, 80% rock, 0 grass density, 0 tree density for heights between -32768 and 0, 100% seafloor for heights between 0 and 10, 100% sand for heights between 10 and 50, 50% grass, 50% sand, .5 grass object density, .01 tree density for heights between 50 and 200, 75% grass, 25% dirt, .75 grass object density, .02 tree density for heights between 200 and 1000, 75% dirt, 25% grass, .001 scraggly tree density for heights between 1000 and 3000, 100% dirt (will mix with rock on slopes due to rule 1) for heights above 3000, 100% snow Climate 1: fractal scale = 0 fractal roughness = 0 for normals 0 degrees off vertical, 100% asphalt (this would be a parking lot or urban area, climate 0 would apply for non-flat areas) Climate 2: fractal scale = 50 fractal roughness = 0.9 for all heights, 50% rock, 50% lava

I'm still debating over whether climates should be implemented as vector or raster data.  My gut tells me that vast areas of most terrains will probably fall into one of a few default climates, and only certain areas will need to be edited.  However, if you give vector tools to an artist, they will probably end up slicing and dicing the terrain so much that it will look great, but the vector data file will be bigger than the terrain itself.  For now I will probably implement them as vector data to keep them as flexible as possible.  If they do take up more space than the terrain file, it's probably because they are at a higher resolution and that conscious decision has been made.  Each 4096x4096 terrain page could have 1024 control points in a 32x32 grid if it were raster data, or 113 arbitrarily placed control points if it were vector data in the same amount of space.  If you wanted to carve the land up into 10 acre fields, the vector data would be the only way to do it.  If you wanted each 108km^2 page to be in less than 10 sections, the vector data would give you centimeter precision over the boundaries between them, while still being the same data size as the raster data.  So I think vector is the way to go for climates too.

Terrain Scale

Due to floating point accuracy issues, terrain pages will need to be scaled to precise coordinates.  In particular, every vertex of the terrain page should be located at a power of two position (including negative powers, i.e. 1/2, 1/4, 1/8...).  Therefore, for the initial US map, terrain pages will still be 4097x4097, but will cover 128 Km (where 1Km = 1024m).  This will leave vertices at exactly 32m intervals, and fractal detail addition will subdivide by halves, bringing it down to exactly 1m at 5 levels of detail.

I have resampled the US National Elevation Dataset to these parameters.  The result is 50 pages wide and 21 pages tall.

Reading List

Here's a short list of articles that I've found useful while thinking about this terrain engine.

• Very Large, Very Detailed Terrain - procedural fractal detail generation (but missing any type of alpha splatting or vector overlays for user-specified detail like roads or parking lots)
• Four-Point Subdivision (edit) - The subdivision method used to divide the heightmap smoothly before applying fractal detail (note that this requires the two neighboring points to each page. This will be handled by asking the neighbor for the height values, and using linear interpolation if it is not yet loaded (it will be beyond the view distance anyway).
• Geometry Clipmaps - their compression method looks to be best-in-class, though their GPU representation seems a little weird - it doesn't account for portions of land that are detailed enough to be displayed at a higher LODs farther away, and large enough flat places nearby to be displayed at lower LODs. In other words it assumes all terrains are *perfect* fractals.
• PGF Compression (edit) - An image compression library which works especially well on natural images (of which heightmaps are model citizen).
• Vector-based terrains - this one talks about using a spline graph to create user specified detail at resolutions higher than that stored in the heightmap. This is perfect for roads, but their textures are cartoony-looking for a reason... the textures they generate still have pixels bigger than one inch even directly below you. If I use this approach, I'll have to subdivide further down to get a decent level of detail, and I'm not sure that there will be enough memory. (edit) If I generate the textures procedurally every frame in the pixel shader, it may work, but it may also kill the gpu. I may instead implement the flattening in the vertex shader, then use decals to actually draw the roads on top of the terrain.
• Real-time Terrain Rendering using Smooth Hardware Optimized Level of Detail describes the LOD approach used by Ogre's terrain engine (except Ogre uses skirts instead of stitching), which will be incorporated into mine. They don't care much about texturing or anything other than the underlying mesh.
• GPU Perlin Noise - Some variant of a 2D version of this will be used to supply the randomness to the fractal functions (instead of the blocky texture lookup used in terrain.dk).
• More GPU Noise - I'm still thinking about the noise generator... it has to be on the GPU and it has to be fast. This slideshow is a good overview of the concepts involved in this type of noise function.
• vTerrain.org - a good knowledge of terrain rendering requires reading this entire site (I haven't done it yet, but I've read almost everything in the Rendering section that looked like it applied to modern GPUs). Parts and pieces of any of these papers may slip into my terrain engine.