Compile-Time Mesh Construction

Each terrain patch contains a mesh representing the terrain in that area. The resolution of this mesh is not uniform. The complexity of the landscape in the Just Cause series varies a lot from one location to another, so the number of triangles required to accurately represent the terrain varies greatly too -- therefore we didn't want a uniform terrain mesh resolution since that would mean a lot of unnecessary vertices, which would cost both vertex performance and memory. Also, small triangles are more expensive per pixel to render than large triangles, so we only want to use small triangles where they really make a visual difference. However, this is just for the graphical representation. For the underlying physical representation we used the fixed-size height maps described above.

There are a number of adaptive-resolution mesh schemes that take the viewpoint into consideration and adjust the resolution in real-time, like "real-time optimally adapting mesh" (ROAM), for instance. One problem with these is that they often introduce "popping" artifacts when changing the viewpoint, but more importantly that the vertex count can vary from frame to frame. Particularly on older hardware this is a very bad thing, since this would mean uploading new vertex data each frame.

With that in mind, one of our requirements was to have a fixed static vertex buffer for the life-time of the terrain patch. Basically this meant that we disregard the viewpoint and focus only on terrain complexity and distance from the camera for determining the resolution. For the terrain complexity part we went with an offline mesh construction solution, and for the distance part we used run-time selection of different LOD representations of the same data.

For the mesh data representation we came up with an adaptive scheme based on binary triangle trees. Although we came up with it independently, there are now several references to binary triangle trees on the internet, and one that closely matches our approach is described in a Gamasutra article from 2006 written by Chris Dallaire. A binary triangle tree is simply a tree in which a node defines a triangle and where two child nodes define a uniform subdivision of the parent triangle (see Figure 3). So to represent a rectangular patch of terrain, two triangle trees are needed. The rectangular patch is split along the diagonal, and the two resulting triangles are the root nodes of the two triangle trees.

Figure 3: The same triangle tree in three different representations: Mesh, tree, and bit stream

An offline process in the terrain compiler generates these triangle trees by iterating over the terrain and measuring the topographic complexity. The more complex the terrain is, the deeper the resulting triangle trees are.

We also had heuristics other than complexity that influenced the tree depth. For instance, we always wanted maximum resolution along shorelines to get smooth looking island contours. The analysis works by starting with the root node and traversing over the height map within that triangle and summing up the differences between the triangle plane and height map samples. The tree is subdivided if this sum is above a specific threshold, and the process repeated for the child nodes. The resulting tree is stored as a bit-stream, where "1" indicates a node and "0" a leaf. This is an extremely compact representation of the terrain mesh. The X and Z positions are implicit by the tree structure, and the height value for each node is sampled from the height map in run time when the vertex buffers are generated.

In the original Just Cause game we actually stored the heights at each node in this structure too, and used planar interpolation to generate the height map values within a triangle. This was of course a very compact way to store the height map but we abandoned that in favor of simplicity with Just Cause 2, since we no longer supported PlayStation 2 and the original Xbox, and thus had higher memory budgets.

So, in essence, what's stored in each stream patch with regards to the terrain mesh is simply a bit-stream for each triangle tree. To make matter slightly more complex however, we actually do this process once for each patch size in the terrain patch maps. We basically store the terrain mesh twelve times over, with different resolutions, since there are twelve patch maps in the terrain patch system. The meshes that correspond to patch sizes that are smaller or equal to the stream patch size are stored in the stream patch and streamed in as part of the stream patch map, but the meshes that correspond to patch sizes larger than the stream patch are stored in an "always loaded" global repository.