Accelerating Creation of Large Terrains Using Incredibuild
Tomas Skacel, VR Group
This article describes how Incredibuild was efficiently utilized to accelerate building of terrain tiles from elevation and imagery data for large terrain surfaces. These tiles are rendered for use in VR Group System’s flight simulation software. The generation and rendering process is based on the “Planet-Sized Batched Dynamic Adaptive Meshes (P-BDAM)” paper by P. Cignoni et al.
VR Group offers flight trainer and simulator solutions. An important aspect of these solutions is high quality visualization, which implies using an effective terrain renderer. Our previous solution, based on commercial products, stopped satisfying our needs a long time ago so we decided to develop our visualization system and terrain renderer in-house.
Displaying massive terrain datasets at interactive frame rates is a complex problem. The texture and geometry sizes can easily exceed current hardware limitations. Because of this, some sort of Level of Detail (LOD) aspect has to be incorporated into the process. Most terrain LOD algorithms use on-the-fly construction of adaptively approximated terrain representation. The main bottleneck of these algorithms is that they tend to be very CPU intensive and consequently do not produce enough triangles to satisfy the potential of today’s modern graphics cards.
Recently, many new methods have arisen which free up CPU load and utilize graphics hardware more efficiently. This results in the rendering of considerably more triangles, thus achieving greater visible detail. Following a short research, we found that P-BDAM based on BDAM suits the best to our needs.
A BDAM structure consists of paired tree structures: a tiled quad-tree for textures and a pair of right triangle hierarchy of small triangular patches stored as two binary trees for the geometry. Contrary to previously described algorithms, the smallest primitive to work with isn’t a single triangle but rather whole batches of triangles. These geometry patches are constructed off-line and are highly optimized. The BDAM structure is rendered for each frame by a stateless traversal algorithm which renders a continuous adaptive terrain by assembling these small patches. This algorithm is not processor intensive, and thanks to batched host-to-graphics communication it fully harnesses the power of current graphics hardware.
P-BDAM is an extension of BDAM that allows correct handling of non-flat planet-size datasets. The main idea is to partition planet surfaces into a number of square tiles, thus managing a forest of BDAM hierarchies.
Please refer to  and  for an in-depth description of BDAM and P-BDAM algorithms.
P-BDAM is built bottom-up, level by level. Firstly, geometry patches are generated for leaves of the BDAM tree from world elevation data. Secondly, parents of these nodes are recursively created by merging and simplifying geometry of their children nodes using quadric error metric driven edge collapse. Before saving, patches are optimized using a high quality stripification algorithm to cache coherent triangle strips. Textures are similarly created using world imagery data for color channels and elevation data to create normal maps for per-pixel lighting. Parent nodes are created by merging and scaling down textures of child nodes.
As a result of these requirements a simple command line tool was created. Its task is to create a new tile from given data or create a new parent tile by merging existing child tiles. The tool also works similarly with texture nodes.
Despite the fact that there’s still room for optimization, the tool’s execution is quite fast and creating a single tile is only a matter of a few seconds. The challenge rises from the number of tiles involved. For detailed terrain, 15 or more levels in the tree, meaning geometry nodes and 1+ texture nodes must be created. In the case of P-BDAM partitioning the planet into six squares, this means six times more nodes.
After realizing the number of nodes we would require it was obvious that it would take a few days to create tiles for the entire Earth on a single machine. A more powerful machine wouldn’t result in a significant speedup no matter how fast it was. Fortunately, because the process was inherently parallel the best option was to distribute the work to other CPUs on the local network.
Our first implementation was based on Python and xmlrpclib. Although this solution was close to working it was far from perfect. It wasn’t based on a system service so starting the process and mapping source data to each client machine was done manually. We also suffered from occasional problems related to concurrent access to data files. Finally, results were not satisfying in terms of performance.
Luckily, while we were searching for a solution to our distributed computing requirements, Incredibuild’s extensibility interfaces were announced. Out of the three available distribution interfaces (XML, Automatic Interception and Submission) we chose the XML interface for its convenient ability to define task dependencies reflecting BDAM tree nodes via an XML file. In the future we plan to create a terrain editor, and may switch to the Submission Interface which will allow us to skip the XML file creation and feed Incredibuild directly from the terrain editor.
The XML file structure is very easy to understand, and thanks to that writing the code to automatically generate the appropriate generation script for the entire terrain was a quick process. The 30-day trial version of Incredibuild was more than enough to thoroughly test the entire process. Incredibuild handles all of the synchronization and data exchange between working machines transparently, and task dependencies are well defined.
As a test terrain we chose the Czech Republic and Andalucia (south of Spain). The geometry was generated from SRTM03 DEM data. For each test we created two geometry trees and one texture tree in various depths. First, the entire process was run on a single machine with an Intel® XEON™ CPU 2.2 GHz processor and 1GB RAM. Then, the process was distributed via Incredibuild across five CPUs.
The results were as follows:
- Andalusia: Description – 8 levels (510 geometry nodes, 85 texture nodes, 595 files). 1 CPU (approx. 2.26 GHz) – 28:22 minutes. 5 CPUs (approx. 11.3 GHz) – 5:56 minutes.
- Czech Republic #1: Description – 10 levels (2,046 geometry nodes, 341 texture nodes, 2,387 files). 1 CPU (approx. 2.26 GHz) – 1:52:14 hours. 5 CPUs (approx. 11.3 GHz) – 22:53 minutes.
- Czech Republic #2: Description – 12 levels (8,190 geometry nodes, 1,365 texture nodes, 9,555 files). 1 CPU (approx. 2.26 GHz) – 7:25:25 hours. 5 CPUs (approx. 11.3 GHz) – 2:22:28 hours.
Following the evaluation we faced a decision: either spend more time developing and debugging our own Python based solution, or use Incredibuild with all its performance and ease of use. We’ve been happy distributing Visual Studio builds with Incredibuild for a long time so this was a win situation for Incredibuild.
The Incredibuild-based implementation resulted in the following benefits:
- It’s easy to understand and easy to use, achieving excellent performance that depends mainly on number of CPUs used.
- A “complete package” offering the Coordinator Monitor for management and Build Monitor for visually tracking the build process.
- A well maintained solution that’s part of the robust “Incredibuild” project.
This article demonstrates how Incredibuild was used for distributed generation of terrain tiles to be rendered in flight simulation software. Thanks to Incredibuild, a complete off-line preprocessing step could be easily accelerated from days to hours.
About VR Group
VR Group is the Czech Republic leader in the design, development, manufactory and integrated logistic support (ILS) of flight trainers, simulators and comprehensive training systems. Offered products and solutions are primarily aimed for air forces and based on the latest modelling and simulation technologies and state-of-the-art 3D visualization and they fulfill consistently relevant international standards and regulations. Products include wide range of training devices for Su-22, Aero L-39 and Aero L-159 aircraft, from Desktop Flight Trainers to a Full Mission Simulators as well as Research Studies of the Implementation of the Simulation and Training Technologies to the Czech Air Force.
About the Author
After graduating from the Faculty of Informatics of Masaryk University Brno where he studied Computer Graphics, Tomas Skacel now works in the field of computer visualization for VR Group as a 3D Graphics Programmer. His responsibility is visualization systems which consist mainly of terrain visualization and rendering of various atmospheric effects and conditions.
References CIGNONI, P., GANOVELLI, F., GOBBETTI, E., MARTON, F., PONCHIO, F., SCOPIGNO, R.: BDAM: Batched dynamic adaptive meshes for high performance terrain visualization. Computer Graphics Forum 22,3 (Sept. 2003), 505-514.  CIGNONI, P., GANOVELLI, F., GOBBETTI, E., MARTON, F., PONCHIO, F., SCOPIGNO, R.: Planet-sized batched dynamic adaptive meshes (P-BDAM). In IEEE Visualization (2003), pp.147-154.