---

Translated from "fr dossier 2001 / projet_3d_terrain" and "fr dossier 2002 / Projet NeL - 3D - Amélioration rendu terrain REVIEWED". The 2002 version covers only the noise displacement and vertex shader work (sections iii and iv); the Bezier tessellation and tile texturing sections (i and ii) are from the 2001 version only. {.is-info}

Nevrax develops Ryzom, a 3D interactive MMORPG with a strong desire for immersion. The first-person view was chosen because it allows a stronger involvement and immersion in the character the player embodies, i.e. their avatar. Since the world of Ryzom is not enclosed and does not take place exclusively in dark corridors, techniques had to be researched and developed to display outdoor scenes as realistically as possible. It must be possible to display hills, plains, mountains and other landscapes, as far away as possible.

Not all MMORPGs use the same view and therefore do not have this problem. Some display the scenery with a top-down view, as if in a helicopter. MMORPGs with a first-person view that mainly take place outdoors often resort to two particular methods to display the terrain in real time: very low terrain tessellation and a very short clipping distance (for example 100 meters). To make it realistic that you cannot see further than 100 meters, games often use fog to make the rendering credible. However, this is not sufficient because the world of Ryzom does not always look like London in heavy fog.

The terrain rendering project solves this problem and allows real-time rendering while pushing the visibility distance to 1000 meters. Furthermore, the tessellation is very fine and can have a visible precision of 50 centimeters per polygon, thus virtually displaying 8 million polygons per animation frame (at 50 frames per second) on a card that can only handle 160,000.

This technology uses a principle called adaptive tessellation. This principle was beginning to emerge in research papers and in some applications. However, these works were not adapted to our needs, as they were all based on a heightmap terrain representation. Heightmaps allow modeling of relatively flat terrain with hills that are not too steep (<60° elevation). Nevrax wanted a world not solely made of valleys and hills. It also needed to represent caves, tunnels, arches, ravines, gigantic roots crossing a basin — complex structures that cannot be simulated with heightmaps.

Finally, a great research effort compared to the existing state of the art was made on terrain illumination as well as on its editing. The particular problem lies in the fact that Ryzom is very vast. The usual editing and illumination methods are not adapted to such surfaces. Compared to serious competitors like the upcoming Star Wars Galaxies, our technology manages to illuminate the terrain with techniques usually reserved for cinema, such as cast shadows, soft shadows, and radiosity simulation.

The state of the art in early 2001 regarding terrain rendering in MMORPGs was quite poor. The biggest competitor, EverQuest, did not use any particular algorithm and displayed large polygons (approximately 20x20 meters) over a relatively large distance (400 meters). This game was however intended for very small configurations and one cannot thus compare the rendering methods used for the terrain.

EverQuest. Coarse polygons and fairly long view distance.

On the non-MMO game side, a non-commercial demo of Halo, then still in preparation on PC, apparently used the ROAM algorithm [Duchaineau] (adaptive tessellation algorithm). By speculation, one could guess the use of heightmaps and a detail texture to add grain to a fairly coarse texture. The video showed in places certain triangle pops characteristic of the ROAM algorithm [Duchaineau] (without the use of geomorphing).

Halo. ROAM and detail texture.

The game Tribes also used an adaptive tessellation principle, similar to ROAM but quite limited, which allowed it to display large panoramas with fairly fine polygons. However, the terrain was still modeled as a heightmap. This time the use of geomorphing avoided triangle pops.

Tribes. "QuadTree" and Geomorph.

The principle of the ROAM algorithm [Duchaineau] is to subdivide or concatenate triangles according to an error metric, which dictates when to split triangles and when to merge them. The technique takes as input a heightmap defined as precisely as possible (e.g. 256x256 pixels for 256x256 meters). This level of definition serves as a base and one cannot display more polygons than are defined (at most 65,536 quads can be displayed in our example). At its lowest level, the tessellation is only 2 right isosceles triangles covering the 256x256 meters. As the camera gets closer, these triangles split according to a recursive principle: each isosceles triangle splits into 2 isosceles triangles always on the side opposite the right angle. Depending on needs, these same triangles can split and so on. Vertex positions are simply calculated directly from the heightmap. The problems of enforced split and the merge principle are explained in detail in [Duchaineau].

This algorithm has many advantages:

• Adaptive tessellation: more detail where needed, particularly near the camera.
• Execution speed thanks to a priority list system that avoids testing all triangles to know if they are candidates for a split or merge.
• Ability to build triangle strips to accelerate rendering.
• Low memory footprint: The heightmap can be defined on 8 or 16 bits. Furthermore, the implicit structure of the heightmap considerably reduces the memory footprint of the tessellation.

While predominantly popular, the ROAM algorithm still has shadow areas and important issues for us:

• It does not particularly define a technique for texturing the terrain. Applying one large map over the whole terrain remains feasible for a hectare, but is not applicable for an entire territory. Furthermore, the resolution remains quite poor (one texel per 50 cm for example), which might be acceptable for a flight simulation, but not in our case where the player is a pedestrian.
• It does not allow modeling the structures required for Ryzom (arches, caves, tunnels, roots).
• It implements a geomorph principle to avoid pops. The principle is not perfect because the geomorph is temporal. When the camera stops, one may see the terrain undulating due to triangles still in the process of geomorphing.
• At very high resolution, memory size can be problematic. For a 160x160 meter zone at 50 cm resolution, storing heights on 16 bits, one reaches 200 KB just for geometry. For comparison, our technology uses zones of the same size and memory footprint, but it also includes texturing information and zone connection information, all for the same maximum resolution of 50 cm.

Halo and many products today use a detail texture principle to solve the texturing problem. This principle simply adds a high-definition texture (e.g. 128 pixels per meter) that repeats over the low-definition texture (e.g. 1 pixel per 50 cm). This does add grain to the terrain, but at the cost of always seeing the same grain, whether on grass, sand or stone. Realism is thus affected.

Bibliography:

• [Hoppe1] Hoppe, H. "Smooth View-dependent Level-of-detail Control and its application to terrain rendering"
• [Duchaineau] Duchaineau, M. et al. "ROAMing Terrain: Real-time Optimally Adapting Meshes". October 19, 1997
• [Lee] Lee, A. "Displaced Subdivision Surfaces" Computer Graphics Proceedings 2000
• [Bézier] Foley, van Dam. "Computer Graphics", second Edition. ISBN 0-201-84840-6

Objectives:

• Render terrain with a view distance on the order of 1 km
• Allow significant diversity in geometry
• Display complex structures (arches, tunnels, ...)
• Allow significant diversity in texturing
• Have a realistic pixel ratio of approximately 128x128 pixels for 2m x 2m

Constraints:

• RAM memory size
• Hard disk size
• Target processor capacity: Pentium 1 GHz
• Target graphics card capacity: GeForce 2 GTS
• Time allocated to terrain rendering: 10 ms

Most of these points had not been addressed in any research paper found. Consequently it was difficult to know whether or not a solution would be found for all of them.

In the case where an adaptive tessellation algorithm is chosen, the problems are:

• Adapt or invent an algorithm that does not only work with heightmaps
• Find a solution to have both a good pixel ratio and significant diversity
• Have a rendering and tessellation time faster than the ROAM algorithm
• Have smooth transitions between triangle splits and merges

The following research tasks were performed:

1. Geometry. ROAM-type tessellation on Bezier patches.
2. Texturing. Tile principle, Far Texture.
3. Geometry. Adding noise maps to add detail to Bezier patches.
4. Geometry. Spatial geomorph and use of vertex programs.

Render with as much detail as possible a terrain composed of complex structures, and display it over a distance of approximately 1 km.

Brute force triangle display

Initially, one research direction was to try rendering the terrain without a particular algorithm, i.e. brute force. The primary advantage would have been that artists would have had complete freedom to render any complex structure. Tests showed that the GeForce 2 GTS could display 16 million polygons per second using strip lists, AGP memory, and the latest OpenGL extensions (NVVertexArrayRange, NVFence). For a 10 ms computation time, one could thus have 160,000 possible polygons ahead. This equates to approximately displaying quads of 5x5 meters on average. This might be acceptable but the real problem lies in memory size. For a 4x4 km territory, approximately 50 MB would be needed just to store vertices. Since AGP memory is a restricted resource (approximately 16 MB), this solution is not feasible.

Grouping terrain into parcels (e.g. 80x80 m zones) for instancing was considered, which would have reduced the memory footprint. However, problems related to 3D card precision and the use of matrices to position instances prevented this technique. At parcel junctions, small holes appeared on screen due to the card's internal calculations.

Another solution would have been to perform the matrix transformation (just a vector addition) on the CPU, precisely enough to avoid these holes. The parcel descriptions could then have been stored in RAM, copying only the needed instances to AGP each frame. This would have occupied only 4 MB of AGP memory. However, bandwidth was the problem here: at 150 MB/s, it would have taken 26 ms just to transfer these vertices (not counting the computation, which though light is significant for the number of vertices), which is unacceptable.

The technical limitations and constraints of this method (maximum tessellation of 5x5 m, heavy instancing to avoid memory problems) led to its abandonment.

Bezier patches

The final method is based on the ROAM algorithm but uses Bezier patches [Bézier] rather than heightmaps. The principle is to describe the terrain from curved surfaces — specifically, square or rectangular Bezier quad patches. These patches define the coarsest possible tessellation. At the lowest level, a patch is drawn with just 2 triangles. A patch measures 16x16 m on average. As one approaches a patch, it tessellates progressively following a principle similar to ROAM. The difference is that for each created point, instead of looking up a height from the heightmap, the 3D point is calculated using the Bezier formula for patches.

Apart from the split and merge principle on isosceles triangles which remains the same, the ROAM algorithm, mainly based on heightmaps, cannot be used as-is. The internal structure is modified to keep pointers between neighboring faces, parent faces, and child faces of the tessellation. Furthermore, enforced split and merge problems become more complicated on non-flat terrain. Here, a vertex of one patch can be shared by 5 or more patches. This poses intrinsic problems that do not appear in ROAM. A recursive solution was found to solve these problems.

For better editing comfort, triangular Bezier patches were considered, but continuity problems between patches appeared and led to abandoning this method. For more flexibility, two concepts were added: rectangular patches and the Multiple Bind principle (connecting smaller patches to one edge of a larger patch).

The idea of rectangular patches may seem odd (a 4-sided patch is a 4-sided patch regardless of its size and shape) but it arises from the tile principle explained below. Furthermore, without special treatment the tessellation of a rectangular patch is less aesthetic because the triangles are no longer isosceles. For these reasons, the tessellation of rectangular patches is special as shown in the following figure. The difference lies in the level 1 tessellation. At level 2, the standard tessellation scheme resumes. Even thinner rectangular patches (e.g. with a 4:1 aspect ratio) can also be edited, and normal tessellation resumes at a yet higher level.

The Multiple Bind principle is used to refine geometry in certain places. 2 or 4 patches can be connected directly to a larger patch on one of its edges, as shown in the following figure. The dotted lines show the actual tessellation used. To avoid holes between these connections, the larger patches are forced to subdivide enough for the tessellation to connect correctly.

Illustration of the Multiple Bind principle.

Finally, a notable innovation was made to the priority list system described in ROAM. The purpose of the priority list in ROAM is to minimize the number of triangles that must be tested for splits or merges. The principle is to maintain an ordered list, inserting each triangle based on its distance to the next split. Each frame, the list is shifted based on camera movement. Only triangles that fall out of the list due to this shift are processed.

The problem with this system is that it reduces a 3D function (the triangle's position relative to the camera) to a 1D function (distance). Thus, even if the camera moves away from a split point, the uniform shift of the list causes the triangle to be processed too early. Our algorithm improves performance by adding the quadrant principle. The direction space is divided into 32 quadrants (representing a solid angle of space). When processing a triangle, it is added to the priority list of the best quadrant. Each frame, the quadrant priority lists are shifted based on both the distance AND direction of camera movement. Thus, those whose quadrant direction is opposite to the camera direction are not shifted at all.

The Bezier Patch method achieves the required objectives. It can simulate cliffs, tunnels, etc. Furthermore, patches can be discontinuous (different tangents on an edge) allowing for steep escarpments. The following image illustrates the quality of the result.

The geometry is compressed and takes on average 15 KB per zone (compared to the 200 KB expected using heightmaps).

The algorithm is performant and can display 20,000 real polygons in 10 ms. Up to 50 meters, triangles measure 2x2 m, giving very smooth terrain and avoiding the polygonal appearance. For a small additional cost, one can even subdivide further to display up to 50 cm x 50 cm precision on the nearest triangles.

The priority list system divides the number of split tests by 2. Unfortunately, the system is not compatible with merge tests, so the number of merge tests remains the same as ROAM. In theory, the number of split tests should have been even lower, but the complexity of the error metric calculation prevents the system from being used in certain cases.

One disadvantage is tessellation memory size. Since the implicit heightmap structure cannot be used, real pointers and coordinates must be stored per face. The tessellation takes 10 times more RAM space than with ROAM.

The Bezier Patch tessellation method was retained and functions satisfactorily.

Lionel — 4 months, on a PC.

Find a solution for varied textures with satisfying grain. Existing solutions do not satisfy both criteria simultaneously.

The final principle uses a tile system. The tile system principle is mainly inspired by 2D top-down games. The terrain is divided into cells and each cell gets a particular fixed-size texture. An algorithm then generally automatically calculates transitions between different tile types (e.g. for transitioning from dirt to grass).

In our case, the entire problem lies in the fact that the terrain is not divided into fixed-size cells. The tessellation is variable and this principle cannot be trivially applied.

The solution combines global texture and tile techniques at the patch level. The artist defines a tile count per patch. Generally a tile is 2x2 m, so a 16x16 m patch has 8x8 tiles (only powers of 2 are possible). It is through this that the artist specifies whether a patch is rectangular or not (a patch of 8x4 tiles is rectangular).

Since a patch of 8x8 tiles at its lowest level is tessellated to only 2 triangles, it is not possible to apply tiles directly. The solution uses Far Textures. Beyond a certain camera distance, typically 50 meters, the patch switches to Far Texture mode. At that point, a single coarse texture (32x32 pixels) is applied representing the general tile appearance. Below this distance, tessellation is forced to the tile level, i.e. all triangles must be split to reach tile size (in our case the patch is defined with 8x8x2 = 128 triangles, as soon as it appears below 50 meters).

The error metric formula for deciding splits and merges is therefore made more complex to integrate this parameter. Additionally, a special transition in the formula is applied over a distance of 20 meters to avoid additional pops.

This system alone is not sufficient to limit memory problems. The Far Texture size is such that it would take 32 MB of VRAM. The solution is to repeat the detail degradation principle starting at 200 meters and again at 400 meters. At 200 meters, the Far Texture is defined with only 16x16 pixels for a patch of 8x8 tiles. At 400 meters, the Far Texture is defined with only 8x8 pixels for a patch of 8x8 tiles.

Finally, to avoid texture pop problems at the transitions between different Far Texture levels and at the transition to tile mode, an alpha blending transition is performed.

The method allows having very fine grain when close to the patch, while allowing a great diversity of that same grain, which is not possible with the methods used in Halo for example.

Far Textures take only 4 MB of VRAM. Tile texture memory depends only on the artists' needs.

The tiling method was retained and functions satisfactorily. The grain in tile mode is ideal. However, some monotony is observed at great distances (above 200 m) due to the limited number of different tiles (VRAM limitation) and the restricted colour palette visible at a distance.

Lionel — 2 months, on a PC. Cyril — 2 months, on a PC.

Bezier patches define smooth curved surfaces but lack the detail found in heightmap solutions. Tiling gives nice close-up rendering but distant rendering remains monotonous. A solution was needed for both defects.

The principle is based on displacement maps [Lee]. The main innovations are related to patch connection problems and displacement map size optimization.

Displacement maps adapt particularly well to adaptive tessellation on Bezier patches — the displacement calculation for a vertex only needs to be done at the moment it is created by a split. Since the number of splits per frame remains limited, the final cost is low.

Because C1 continuity of patches is not always respected, and because of concepts like MultipleBind, triangles can intersect neighbors after displacement. The solution smooths displaced vertices on patch edges and corners to avoid continuity problems.

To save space, the displacement map is instanced. About a hundred noise maps are created, and the artist can choose per tile which one to use. This choice is compressed to 4 bits, so noise information takes only 32 bytes per 8x8 tile patch. The noise maps themselves have 50 cm/pixel resolution.

Since noise maps may differ between adjacent tiles, the maps are interpolated when different.

The left image shows displacement maps [Lee] without correction — note the undesirable triangle intersection and "seam" effect. The right image shows the corrected result.

Although smoothing on edges corrects the tessellation, patch discontinuity constraints impose a strong limitation on the maximum amplitude of the noise. Perturbations of approximately ±1 meter can be applied, allowing gullies or streams to be carved into a patch.

Most importantly, this system adds additional grain to the texture for patches 200 meters or more away. As shown below, the Far Texture is less monotonous with noise. The left image has no lighting (to illustrate the difference), the right has lighting with noise.

Note the Bezier patch arch on the right side of this screenshot.

The research result is a success. The visual contribution is satisfying compared to the small additional computation time required.

Lionel — 2 months, on a PC.

Eliminate the visual artifacts of triangle popping that appear during splits and merges. ROAM already provides a solution but with the disadvantages described above.

ROAM performs temporal geomorphing on split vertices. When a vertex is created by a split, it does not immediately take its true value (derived from the heightmap in the case of ROAM). It is interpolated between its initial value at the middle of the triangle and its final value. This interpolation is done as a function of time.

Our method is more accurate because it calculates the geomorph based on the error metric. Since this depends partly on the camera-triangle distance, the geomorph is only really visible when the camera moves. The result is more stable and accurate.

The problem with this method is that it is more expensive — nearly all triangles must be tested to determine whether they need to be geomorphed or not. The solution was to use the new vertex shader functions of GeForce 3-class graphics cards. These are small programs executed per-vertex that the GPU handles itself. This research was quite complex because the error metric formula had to be encoded within vertex shader limitations.

Since the formula is complicated due to the tile/Far Texture transition, many attempts were made. Among these, one approach was to process most triangles outside the transition zone with vertex shaders and the transition zone with the CPU. The problem is that the graphics card does not handle data in exactly the same way with and without vertex shaders. Discontinuities between triangles appeared and this method had to be abandoned.

The final method uses vertex shaders for all triangles. The error metric calculations in the transition zone were modified, while keeping the original objectives, to be implementable as vertex shaders. In particular, rather than using the barycenter of the triangle to calculate its distance from the camera, the apex (the midpoint of the side opposite the right angle of the triangle) is now used.

The vertex shader implementation provides a 50% gain on rendering time. Indeed, the 3D card then handles most of the work needed for geomorphing.

As not all 3D cards support vertex shaders (like the GeForce 2 GTS), terrain rendering takes 50% additional time on these cards, as the geomorph is performed by the CPU.

This technique is used in the final system. It clearly brings an advantage over other methods, given the recent appearance of vertex shaders in 3D cards.

Lionel — 2 months, on a PC.

To show the progress made with our technology, let us compare Ryzom images with those of an upcoming major competitor: Star Wars Galaxies (SWG).

In the left image, one can see that SWG uses heightmaps, and only valleys and hills are possible. The right image shows that Ryzom's terrain structure is more complex. Note also the richness of grain that noise provides in the mid-ground, compared to the relative monotony of the SWG terrain. The quality of Ryzom's terrain lighting is also evident. By comparison, SWG appears to use simple Gouraud lighting on the terrain. Cast shadows and radiosity are not possible with that technique.

Here is another series of images (SWG left, Ryzom right):