Static Level-of-Detail for FlightGear
Freely following a concept of Jonathan Blow in his column "The Inner Product", work has started on a static Level-of-Detail implementation for the FlightGear terrain engine.
As a first step, a multi-level simplifier for FlightGear scenery structures was implemented.
Given a triangle limit n, a scenery tile is subdivided by a BSP-tree so that each leaf of the tree contains at least n/2 and at most n triangles. The tree is then traversed bottom-up, combining children of a node and simplifying them to n+/-1 triangles. After that, the nodes of each level combined make up a common level of detail, with the leaf-level representing the original details and the root representing an n+/-1-triangle model of the complete tile.
For each of the BSP-nodes a minimum viewer distance can be given. For rendering, the BSP-tree is to be traversed top-down. For each node the distance to the viewer is checked. If the viewer is farther away than the minimum viewer distance, the node is rendered and traversal of the current branch is stopped. If the viewer is nearer than the minimum viewer distance, traversal continues with the children of the current node.
As example the tile 3105386 from the South Germany scenery containing the northern part of EDNY was used. The original version contains 30.987 triangles. For n=2000, the partitioning requires 4 levels including root and leaf-level. The final simplified node uses 126.520 different faces, where common faces are shared between levels.
The image to the right shows the transition from level 0 (upper left) via level 1 (upper right) and level 2 (lower left) to the fully detailed level 3 (lower right). Click here for an animated version.
All triangles are filled in light grey color and the edges are drawn in red. Black edges represent edges which cannot be collapsed in the given level, including boundaries between BSP-nodes, tile and hole boundaries as well as edges connecting boundary vertices. Note how the node boundaries vanish on higher levels, as nodes are combined.
Instead of using connection triangles for stitching node borders as suggested by Jonathan Blow, node, tile and hole borders are left intact. The triangles adjacent to node borders use the same vertex indices as their respective counterpart on the other side of the border. Tile borders, which are carefully stitched by TerraGear, as well as holes - most of which coincide with airport boundaries - are left unchanged in all simplification steps.
Further differing from Jonathan Blow's suggestion, new nodes may be introduced in order to minimize the approximation error.
In addition to simple surface error, material boundaries are also considered in error quadrics - as described in Michael Garland's paper - in order to keep the shape of landcover structures such as shorelines, forest limits, etc. as good as possible. The system specifically makes use of the fact that the error quadrics suggested by Garland describe the curvature of both surface and - if the extension for material boundaries is used - on-surface structures. As has been shown in the experiments for line simplification, the approximation of curved features is notably better than the results of simple vertex-removal techniques.
Currently the data is read directly from .btg.gz-files, but the system is designed in a way which allows direct integration with TerraGear after the second triangulation stage.
Statistics on storage size still have to be collected from experiments. Due to the higher amount of faces (>factor 4 in this experiment) and the already large size of detailed scenery files, it is to be hoped that the coarser levels of detail posess better fanification qualities than the original files.
File size may also be one reason for changing the file format, besides the need for storing the hierarchical information from the BSP-tree. As tile loading times are already quite long for the current detailed scenery files, it is desirable to create a file format which allows incremental loading of the graphics data.
Actual in-flight results are still missing, as the infrastructure is not yet integrated with FlightGear. Particular interest lies in the adaption of minimum viewing distance based on the root mean square error as suggested by Jonathan Blow, as well as on popping effects. Looking at the progression of the levels in detail it can be seen that line features such as roads and smaller rivers vanish already on the first simplification steps.
It was suggested to combine the introduction of the level-of-detail infrastructure with the transition of the terrain engine to OpenSceneGraph.