Arches: A Framework for Modeling Complex Terrains

In this paper, we present a framework for representing complex terrains with such features as overhangs, arches and caves and including different materials such as sand and rocks. Our hybrid model combines a volumetric discrete data structure that stores the different materials and an implicit representation for sculpting and reconstructing the surface of the terrain. Complex scenes can be edited and sculpted interactively with high level tools. We also propose an original rock generation technique that enables us to automatically generate complex rocky sceneries with piles of rocks without any computationally demanding physically-based simulation.

Categories and Subject Descriptors (according to ACM CCS): [Computer Graphics]: Three-Dimensional Graphics and Realism

There are numerous applications that make use of synthetic terrain, and very often the terrain is the dominant visual element in the scene. Such applications include landscape design, flight simulators, battleground simulations, feature film special effects and computer games.

Over the years, graphics researchers have made considerable progress towards developing efficient methods for generating and editing synthetic terrains. There are three main approaches to generating synthetic terrains: fractal landscape modeling, physical erosion simulation and terrain synthesis from images or sample terrain patches.

Existing methods have several limitations. First, they concentrate on large-scale features such as rivers, valleys and mountain ridges, which are usually important visual elements in large-scale terrains. Therefore, they rely on a height field representation and cannot represent overhangs, arches or even caves. Second, they generally do not explicitly model the different materials on the terrain such as sand or rocks: details are added afterwards by a texturing process. Although procedural texturing is often sufficient for generating realistic long-range views, it is necessary to generate the geometric details for closer views. In particular, piles of rocks play an important part in the overall realism of a natural rocky scenery.

In this paper, we present an original approach for author-

ing complex terrains with overhangs, arches and caves. Our goal is to propose a compact and efficient model that lends itself for real time editing. Therefore, our goal is not to focus on a physically based modeling system. Instead, we aim at generating physically plausible scenes in real time with physically inspired and phenomenological techniques. More precisely, the main contributions of this paper are as follows:

Hybrid terrain model We introduce a hybrid model that combines a compact volumetric discrete data-structure storing the different materials of the terrain with an implicit representation for efficiently sculpting and reconstructing the surface. Our discrete data structure relies on twodimensional grid of material layers stacks, whereas our implicit surface model is defined as a convolution surface.

Terrain authoring tools We propose a framework that combines some high level terrain modeling and sculpting tools with a simplified physically inspired simulation kernel which automatically stabilizes layers of sand and rocks according to their repose angle. This architecture enables the designer to create complex scenes without the burden of finely editing details by hand.

Procedural generation of rock piles Piles of rocks and pebbles play an important part in the overall realism of a natural rocky scene. We propose a phenomenological approach for simulating rocks detaching from the bedrock and piling together into compact piles. Since stabilizing hundreds of rock pieces would require computationally demanding collision detection and physical simulation, we propose an efficient tiling technique for generating rock piles.

Real time rendering We present a technique for rendering and texturing complex terrains in real time. Our method relies on a real time texturing technique which can be implemented as a GPU shader easily for shading the ground, and on the tiling algorithm for instancing rocks.

The remainder of this paper is organized as follows. In Section 2, we briefly review previous work on terrain modeling. Section 3, presents our hybrid model. We detail high level sculpting and erosion tools in Section 4. Section 5 addresses the automatic generation of piles of rocks. In Section 6, we describe our algorithms for generating the surface mesh and texturing the terrain. Section 7 shows several complex scenes created with our model before we finally conclude our work and propose some future research.

There are three main approaches to generating synthetic terrains: fractal landscape modeling, physical erosion simulation and terrain synthesis from images or sample terrain patches.

A variety of stochastic subdivision techniques have been introduced for synthesizing terrains: fractal landscape modeling [Man82], random midpoint displacement techniques [FFC82], square-square subdivision schemes [Mi86]. Szeliski et al. [ST89] addressed the problem of user control by combining deterministic splines and stochastic fractals into constrained fractals. An overview may be found in [EMP*98]. With the recent advances in algorithms and graphics hardware, GPU methods for real-time editing and rendering of procedural terrains have been proposed [SBW06].

Erosion simulation is another approach to synthesizing terrain details based on models of landscape formation and

stream erosion. It is often used as a refinement step after a height field is generated. With appropriately-tuned parameters, these techniques can generate realistic-appearing terrain. Early methods adapted the fractal rules with specific changes to produce eroded terrains [KMN88, PH93]. Physically-based erosion approaches approximate natural terrain formation by simulating the erosion of stream networks. Some material is dissolved and transported by the water flow, and finally deposited at another location. The water movement is determined by local gradient of the terrain in a simple diffusion algorithm [RPP93, Nag98, BF02]. Those methods are based on the simple diffusion model which is not accurate enough to describe the water movement and sediment transportation. Water movement and sediment transportation are closely related to the velocity field of the running water. Therefore fluid simulation methods were integrated into the erosion process by several researchers [CMF98]. Recently, hydraulic erosion simulation techniques have been optimized so as to take full advantage of the high parallel computing power offered by today's graphics processing units [NWD05, MDH07, SBBK08].

Both fractal and physical erosion techniques often involves complex parameter tuning. Image-based alternatives have been proposed [Lew84, PV95] to provide the user with more intuitive control over the synthesized terrain. Recently, an example-based system for terrain synthesis was proposed [ZSTR07], combining patches from samples applied to a user-sketches feature map that specifies where terrain features should occur.

Recent commercial software such as MojoWorld or Terrain 2 are based on fractal synthesis and noise generators and include geological erosion simulation to synthesize realistic-appearing terrain. Control is achieved by changing global parameters in the generation process. Some systems support the user-specified placement of large scale terrain features in the synthesis process.

The very limitation of all those methods is that they rely on a height field representation of the terrain and therefore cannot represent overhangs, arches or even caves. A general technique for generating overhangs was proposed in [GM01]. Overhangs are obtained by a horizontal displacement function to carve the height field. Terrains with overhangs have also been generated with procedural models [GM07]. While procedural terrains can extend over an infinite area or over the entire surface of a planet, they are expensive to render and require topology correction to ensure that the final terrain remains simply connected. Voxel representations have been used to simulate the influence of cracks and joints in the bedrock over the erosion process [IFMC03] and to simulate the geological formation of Goblins [BFO*07]. While those methods can simulate the formation of overhangs, they are computationally demanding and can be effectively used only to model geological features of a limited size.

In this section, we detail our model for representing terrains with overhangs, arches, or caves and with different materials including sand and rocks.

In this section, we present our algorithms for sculpting the bedrock layer and for adding layers of various materials. Our goal is to provide high level tools for authoring complex scenes without the burden of editing details by hand.

We have developed two methods for sculpting the bedrock layer. The first technique consists of locally deforming and carving the terrain in the direction of the normal to the surface. Since directly sculpting the bedrock proves to be a tedious task for editing complex terrain features such as large faults or tunnels, we also developed some specific algorithms for creating cracks or pierce networks of tunnels.

In this section, we present our method for efficiently generating a set of rocks into contact. Instead of modeling rocks separately and creating piles with physically-based collision detection techniques, we propose to directly generate rock models with contact points. Our method proceeds in three steps. First we generate a cubic tile containing Voronoi cells that can tile the entire space. Second, we create the geometry of rocks by eroding the Voronoi cells. The erosion if performed all over the surface of Voronoi cells but at some random contact points located on the faces so that rocks should nicely pack together. Finally, rock piles are created by instantiating some of the rock models in the cubic tile.

Voronoi cell distribution Let $\backslash mathcal\{C\}$ denote a cubic tile. We first generate a Poisson sphere distribution [LD06] with radius $r$ and whose centers will be denoted as $\backslash mathbf\{p\}\_i$ over the cubic tile $\backslash mathcal\{C\}$. Using a Poisson distribution of radius $r$ enables us to control the minimum size of the created Voronoi cells, hence the size of the rocks. We consider that the cube $\backslash mathcal\{C\}$ virtually tiles space so as to be able to construct closed Voronoi cells, denoted as $V\_i$ for every center $\backslash mathbf\{p\}\_i$. The resulting set of cells periodically tiles space. Creating an aperiodic tiling of Voronoi cells over a set of Corner Cubes using a modified Poisson sphere distribution [LD06] should be possible but needs further investigations beyond the scope of this paper. In practice, we did not observe disturbing repetitive patterns in the rock piles generated with our method.

Generating the rock geometry Rocks are created from the Voronoi cells by performing an erosion simulation step all over the surface of the cells but at some random contact points located on the faces. This method guarantees that rocks should collide and fake a stable arrangement. Recall that our goal is not to perform physically-based simulations but to generate realistic looking models. While we cannot guarantee that the piles are set in a stable configuration, our rock piles are still visually convincing.

Our method proceeds in two steps (Figure 17). We first create the contact points, denoted as $\backslash mathbf\{c\}\_\{ij\}$, by generating random points on the faces between the cells $V\_i$ and $V\_j$. For every contact point $\backslash mathbf\{c\}\_\{ij\}$, we define a function denoted as $\backslash rho\_\{ij\}(\backslash mathbf\{p\})$ representing the local resistance to erosion with respect to the distance $\backslash |\backslash mathbf\{p\}\; -\; \backslash mathbf\{c\}\_\{ij\}\backslash |$. The resistance should be a smoothly decreasing function of the distance between a point in space and the contact point $\backslash mathbf\{c\}\_\{ij\}$. Recall that $r$ is the Poisson radius, we propose to use the following Gaussian function:

For every Voronoi cell, we generate the corresponding rock geometry by simulating a uniform erosion weighted by the resistance functions (Figure 17). Our erosion simulation is based on the spheroidal erosion technique proposed in [BFO*07]. Note that this process is performed once and for all as a pre-processing step.

Rock instantiation We generate rocks on the ground by analyzing every corner cube straddling a rock material layer. We instantiate rocks whose corresponding Voronoi center $\backslash mathbf\{p\}$ lies within a rock material layer (Figure 18). Although rocks on the ground may often intersect the ground mesh, those artifacts are rarely seen.

In practice, for large rock piles, only the rocks on the top layers are visible and contribute to the final image. Therefore we eliminate rocks whose distance to the surface is larger than twice the maximum radius of Voronoi embedding spheres.

Our method creates convincing piles of rocks very efficiently by instantiating only a few different mesh models. While we cannot guarantee that the rocks are set in a stable configuration, they are into contact and the resulting arrangements look physically plausible and convincing (Figure 19).

In this section, we present our method for texturing and rendering terrains of arbitrary geometry. Our approach consists in creating only one textured triangle mesh for bedrock and sand - which will be referred to as the ground mesh - whereas rocks are treated separately with the specific instantiation process. The ground mesh is textured by blending different material textures according to the ratio of material layers surfacing the ground.

Ground mesh generation We generate a triangle mesh representing the ground by polygonizing the implicit representation $S\; =\; \backslash \{\backslash mathbf\{p\}\; \backslash in\; \backslash mathbf\{R\}^3\; |\; f(\backslash mathbf\{p\})\; =\; 0\backslash \}$ of the terrain. Instead of polygonizing the different material layers independently, we create one implicit surface from the skeleton defined as the union of sand and bedrock. Thus we use the following skeleton function:

Standard polygonization techniques [BW97] are used to generate the ground mesh.

Texturing terrains of arbitrary geometry The texture of the different materials can be generated procedurally [EMP*98]. While this method is efficient for off line rendering, it is computationally demanding for real time rendering as generating several procedural textures on the fly and blending them would overload the Graphics Processing Unit. Since we are dealing with terrains of arbitrary topology and geometry, computing the $(u,\; v)$ coordinates for texture mapping becomes a challenging problem.

We propose an automatic technique for mapping material textures onto the ground mesh in real time without computing and storing uv-coordinates. Our approach is inspired by [Gei07]. Let $\backslash mathbf\{p\}$ denote a vertex of a triangle of the ground mesh, and $\backslash mathbf\{n\}(x,\; y,\; z)$ denote its normal. Let $T(u,\; v)$ denote the texture color at $(u,\; v)$ coordinates and $T(\backslash mathbf\{p\})$ the texture color for vertex $\backslash mathbf\{p\}$. We define the color at vertex $\backslash mathbf\{p\}$ by blending the three colors obtained by texture mapping along the main three world axes:

The blending coefficients $\backslash alpha$, $\backslash beta$ and $\backslash gamma$ are computed as a function of the normal $\backslash mathbf\{n\}$ with a view to blending the contributing textures. Let $\backslash |\backslash mathbf\{n\}\backslash |\_p\; =\; (|x|^p\; +\; |y|^p\; +\; |z|^p)^\{1/p\}$ denote the $L^p$ norm of $\backslash mathbf\{n\}$, we define coefficients as:

The exponent $p\; \backslash geq\; 1$ characterizes the smoothness of the blend between axis projected textures. In our implementation, we use $p\; =\; 8$. We implemented this texturing technique both as a HLSL shader for real time rendering and as a Mental Ray® shader for producing the high quality images shown through out the paper as well as the accompanying video.

Texture blending The ground mesh is textured according to the type of materials at the surface of the ground. Our approach consists in blending the texture of every different material according to the ratio of neighboring materials.

For every vertex $\backslash mathbf\{p\}$ of the mesh, we evaluate the ratio of visible materials in a cubic box domain $\backslash Omega$ centered at $\backslash mathbf\{p\}$ (Figure 21). This is performed very efficiently by computing the visible surface of the material stacks intersecting $\backslash Omega$.

We have implemented our hybrid terrain model and the modeling tools into a modeling application coded in C++. We have applied our method to create different varieties of complex rocky sceneries with complex geological features including caves (Figure 20), cliffs with overhangs (Figure 22) and arches (Figure 23).

Our material layer data-structure can store non height field terrains very efficiently. Table 1 reports the amount of memory used for modeling different scenes and the effective resolution of the corresponding voxel decomposition of space.

For instance the large cave scene (Figure 20) has been created with an effective resolution exceeding $1000\; \backslash times\; 750\; \backslash times\; 8000$ (6 billion voxels) with less than 21 megabytes. Note that the cliff scene with a smaller effective resolution (4 billion voxels) requires more memory because its overall geometry is more complex with many different material layers.

The triangle meshes representing the cave, the canyon and the arches sceneries have 818 940, 760 769 and 360 698 triangles respectively. The images shown throughout the paper have a $2048\; \backslash times\; 2048$ resolution.

Our rock pile generation technique can create thousands of rocks piled together very efficiently. Table 2 reports the total number of rocks in different scenes, the number of rocks per tile as well as timings (in seconds) for generating the tiles and performing the instantiation process. Recall that the geometry of rocks in the cubic tile is generated once and for all as a preprocessing step.

Like with all periodic tiling methods, artifacts may appear such as recurring patterns of rocks arranged in the same orientation, or rocks on the ground with an unnatural unsteady position.

We have presented an original approach for representing complex terrains. Our framework can model overhangs, arches, or caves with granular materials such as sand and rocks. Our hybrid model combines a compact material layer data structure and an implicit representation for sculpting and reconstructing the surface of the terrain. We have proposed several high level tools for authoring complex scenes.

In particular, we presented a very efficient erosion tool as a modeling operator for automatically generating rock and sand piles. Our approach allows the designer to sculpt large complex rocky scenes without computationally demanding physically-based simulation. Our system has been used to successfully construct a vast variety of scenes with original and unique geological features.

In the future, we plan to develop new modeling and simulation tools. We are currently working on combining erosion and ecosystem simulation with a view to creating a unified framework for generating highly detailed and convincing grounds covered with vegetation but also with lichens, mosses, broken branches or fallen leaves. We also plan to investigate the generation of aperiodic rock tiles to improve the overall aspect of rocky sceneries.

This work was supported by Agence Nationale de la Recherche as ANR-06-MDCA-004-01 project. We wish to credit Eden Games and Widescreen Games for their participation to the project. Special thanks go to Pascal Bouvier and Robert Foriel (Widescreen Games) for developing the real time HLSL and Mental Ray shaders, and to Etienne Duranton (LIRIS) for participating to the implementation of the framework.