Procedural Generation of Villages on Arbitrary Terrains

Offering the richest possible user experience in flight simulators, video games and 3D movies, requires the creation of an increasing amount of complex, textured 3D models. Modeling a large number of these by hand using standard software is a tedious task. This is especially true for landscapes, which should ideally combine arbitrary terrains with rivers, lakes, forests, and adapted human settlement. Several procedural modeling techniques have been developed to automatically generate such complex content. However, the modeling of human settlement has been restricted, up to now, to the generation of large cities, where building blocks are used to populate regular street networks. Adaptation to rough terrain has been scarcely studied, and no previous work was conducted, to our knowledge, on the generation sparser settlements.

This paper addresses the procedural modeling of small villages on arbitrary terrains, where bodies of water have possibly been predefined. Our method generates all the elements defining a village, from the road network to the individual parcels of land and to 3D houses adapted to the local slope.

Contrary to the large cities usually studied in Computer Graphics, most human settlements did not result from some pre-defined land-use plan, but from people progressively settling in safe, well served, sunny or convenient location for farming or fishing. Meanwhile, the road networks progressively grew and in turn attracted new settlers [2]. The result of such progressive settlement can still be observed in many regions over the world. For instance, it is the cause of the unique look of typical highland hamlets in the European Alps or of ancient villages on the banks of the Mediterranean Sea. Generating scattered settlements is a challenging problem that requires stepping away from the standard modeling paradigm used for cities [15]. In addition, modeling villages on hilly terrains requires generating complex land parcels, driven by both curved roads and un-even terrain slopes, and houses with non-regular doors and windows positions.

Our main contributions are as follows. First, we propose a new, hybrid settlement/road generation process that progressively creates a village layout on arbitrary terrain based on a growth scenario and on dynamic interest maps (Section 4). Secondly, we introduce an anisotropic conquest process that creates plausible individual parcels of land (Section 5). Finally, we present an open shape grammar able to adapt the geometry of houses to the local terrain slope (Section 6). Our method is illustrated by the generation of a variety of typical villages, validated through comparison with real layouts and pictures (Section 7).

Generating villages requires the generation of road networks, land tessellation into parcels and the creation of 3D buildings. This section reviews previous work in these domains. A complete survey on procedural city modeling can be found in [17].

Road networks Several interactive techniques have been introduced for editing or sketching road networks on arbitrary terrains. Roads were either represented by Bezier curves [3], or by clothoids enabling to express curvature constraints [12]. Closer to our concerns, automatic generation of roads on rough terrains was addressed by Galin [7,6]. Finding a path from a starting point to an end point subject to maximal slope and curvature constraints was expressed as an anisotropic shortest path problem. It enabled to take into account the environment, such as the presence of vegetation or water. Our method extends this approach to the case of road networks between hamlets or houses, leading us to a new, road re-use strategy.

Procedural modeling of cities Existing methods for modeling cities start by generating a street network. The cycles formed by neighboring streets are tessellated into blocks serving as footprints for buildings. Inspired from L-Systems [14], Parish pioneer work for street network generation was fully automatic [15]. User control through interactive editing was later allowed [9,11]. In parallel, other approaches were introduced such as tensor fields based or example-based city layout generation [4, 1]. Those methods first define the road network and then create the parcels in a second step. Therefore, they cannot be applied in the case of scattered settlement, where modeling the interaction between progressive settlement and road network extension is mandatory. Although not addressing the same problem, our progressive generation approach is closer to resource management methods introduced to simulate city growth or optimize land use [18,16].

When a city layout defining footprints for buildings is set, grammars such as L-Systems [15], split grammars [19] or shape grammars [13] are used for automatically generating their geometry. Our method for generating houses on hilly terrains extends existing grammar-based approaches: we define an open shape grammar enabling façade elements to self adapt to external constraints.

Non-urban settlements To our knowledge, the only work addressing the generation of non-urban settlements was dedicated to South African informal settlements [8]. After using a particle system to generate settlement seeds, different combinations of Voronoi diagrams were used to tessellate the terrain. This inspired our work on land parcels generation, although we had to develop a new, anisotropic land conquest method to account for alignments with road paths and terrain features, observed on real village layouts.

Lastly, progressive growth of non-urban settlements based on environmental constraints is somewhat similar to the spread of biological species. Inspiring from a model for lichen spreading on a support [5], we rely on particles to progressively seed settlement based on interest maps. However, villages develop in more structured ways, requiring us to take the road network into account in the simulation loop.

In this work, we call village any non-urban, sparse settlement, for instance a group of terraced houses around a church, a couple of remote hamlets and a few isolated farms between them. We define the region of interest on which the village is to be created as a compact $\backslash Omega\; \backslash in\; \backslash mathbb\{R\}^2$. $\backslash Omega$ is supposed to be connected to the outside world through a set of connection points $\backslash Psi$, located at the edges of $\backslash Omega$, and that will serve as extremities for the future road network. The nature of the environment is pre-defined using functions over $\backslash Omega$. $h(\backslash mathbf\{p\})$, $w(\backslash mathbf\{p\})$ and $v(\backslash mathbf\{p\})$ respectively denote the elevation, the water height and the vegetation density at a given point $\backslash mathbf\{p\}$.

To enable the creation on the same terrain, of various villages, we use a village type $\backslash mathcal\{V\}$ (e.g. high-land settlement, defensive village, fisherman village). A growth scenario sets $\backslash mathcal\{V\}$ over time and launches the creation of settlement seeds $B\_i$ – marking the future locations of buildings, and of the roads $R\_j$ that serve them. We call Village Skeleton $\backslash mathcal\{S\}\; =\; (\backslash \{B\_i\backslash \},\; \backslash \{R\_j\backslash \})$ the result of this step. A settlement seed is defined as $B\_i\; =\; (\backslash mathcal\{B\},\; \backslash mathbf\{p\})$, where $\backslash mathcal\{B\}$ is the building type (e.g. castle, church, terraced house or farm), and $\backslash mathbf\{p\}\; \backslash in\; \backslash Omega$ is a position. A road $R\_j$ is defined by a set of nodes positions $\backslash \{\backslash mathbf\{p\}\_k\backslash \}$ controlling its central curve. During the generation process, we call building encyclopedia a function that returns, for each pair $(\backslash mathcal\{V\},\; \backslash mathcal\{B\})$, the set of parameters used to seed a building.

The village layout we need to compute is not only composed of the village skeleton, but also includes a tessellation of $\backslash Omega$ into individual land parcels $\backslash mathcal\{P\}\_i$ around buildings. We call $F\_i$ the footprint of the building $B\_i$, defined as a sub-part of $\backslash mathcal\{P\}\_i$. This footprint will serve as foundation for the geometry of the building.

Our algorithm for generating villages on arbitrary terrains is summarized in Figure 2. Given $\backslash Omega$, a few environment maps and a user-defined growth scenario, we first grow the village skeleton, then generate land parcels and building footprints to get the village layout, and finally create 3D geometry. These three steps are detailed in Sections 4 to 6.

In this section, we explain how we generate the building seeds and the road network that form the village skeleton. We use an iterative particle-based method for seeding buildings while considering environmental constraints and interest functions depending on the building type. The key feature of our simulation loop is to

alternate seeding steps with creation of road segments connecting newly created buildings to the network (Figure 3). This approach allows for dynamic update of interest regions when new roads are created.

Computing a village skeleton (roads trajectories and building seeds) is not sufficient for generating the layout of a village: we also need to tessellate the terrain into individual parcels of land, where houses, gardens or fields will be defined. A first approach, investigated in [8], is to rely on Voronoi diagrams to define a parcel of land around each building seed. This approach leads to rather isotropic parcels that lack structure and are not aligned with roads.

After carefully analyzing the layout of parcels in real villages, we observed that most parcels have one side neighboring a road and two sides perpendicular to it, the shape of the last side being driven by other constraints such as the presence of neighbors or large changes in terrain slope. Therefore, we rely on a three steps, anisotropic land conquest method to define adapted land parcels. First seeds conquer their road territory. Then, they expand from the road using anisotropic conquest. Lastly, the resulting parcel is simplified to avoid sharp angles (Figure 7).

The final step of our method is the creation of the three-dimensional geometry of the village, including roads, buildings and vegetation. While existing methods such as [7] can be used to generate accurate road geometry, existing methods for generating houses from their footprint [10] need to be extended to allow the generation of plausible houses on hilly terrain. In small mountain villages, windows and doors often have unusual shapes

and façades often have complex layouts so as to conform to architectural constraints such as non-collision with the ground, alignment with floors whenever possible, and guaranteeing at least a door and a window per room. In this section, we introduce Open Shape Grammar to adapt geometry generation to such constraints.

Our village modeling system is coded in C++. Renderings were performed by using Mental Ray on the textured meshes we output.

Parcels generation To validate our parcel generation method, we compared the shapes of the parcels we create with those of real village layouts, with similar building distributions and road networks. One of our results is depicted in Figure 12. Parcels have similar shapes and the mean number of neighbors (2.873 with our model, 2.812 in the real data) and of contour edges (4.29 with our model, 4.068 in the real data) are similar.

Geometry generation Our method of buildings generation with an Open Shape Grammar allows us to create homes on steep slopes without the doors and windows that are in collision with the ground. Note on the Figure 9 the change of position and shape of these elements. Appendix A details the rules we use to generate windows on building façades, and compare them to standard grammar rules.

Village diversity Figures 14, 13, 15 and 1 show different kinds of villages generated by our method. Figure 14 shows mountain villages, for which geographical domination was the main factor influencing seeding. Figure 13 shows a fortified village on a top of cliff where the main criteria were geographical domination and being protected by fortifications. These results demonstrate the effectiveness of our approach for generating settlements that conform to European layout styles. We believe that non-European village types could be created as well by modifying and tuning the growth scenario and the cost functions. A complete comparison and validation is beyond the scope of this paper.

Influence of parameters Figure 15 shows the influence of parameters during seeding. Distance to the sea was the main criterion for the creation of the first village, whereas the second was seeking for domination.

Performance Table 1 gives the time spent in each phase of the generation process. Land parcel generation is the most compute intensive part of our algorithm, due to the size of the grid used to perform the spread (we used a $4096\; \backslash times\; 4096$ grid). Note that depending on the desired output (with or without individual gardens around houses), this step can be skipped.

Limitations The main limitation of our method is the number of user-set parameters, currently 150 per village type. Fortunately, these parameters, stored in the building encyclopedia, can be reused to create a large variety of villages, depending on the terrain and on easily specified growth scenario typically created in 2 minutes. Displaying the interest values on the terrain helps users understand and parameterize the method, although their goals may still be obtained after a long series of trials and errors, as in every procedural generation method.

This paper presented an original method for generating scattered settlements on arbitrary terrains, enabling villages and hamlets, with the associated roads, forests and fields to be built on arbitrary landscapes. We demonstrated that our method can generate different types of villages with a coherent and adapted geometry. We validated our results through comparison with real layouts and pictures. In the future, we would like to focus on a user-controlled generation framework allowing real-time editing of villages. Our target application is an interactive system to enabling quick authoring of landscapes rather than a fully automated system. As it is, our method provides a very good starting point to develop such a system.

Acknowledgements This work was funded by the ERC advanced grant EXPRESSIVE.

WindowFacade → while (∃ shape in shapes priority queue)
                while (∃ pos in positions priority queue)
                if (try (Window(pos, shape)))
                { Walls } = { extract Window
                            from WindowFacade }
                throw success
            throw failure

Window (pos, shape) → if (external constraints (pos, shape))
                    { Woodent parts | Shutters | ... }
                    throw success
                else
                    throw failure

Arnaud Emilien is a doctoral student at LJK, University of Grenoble, France, and at LIGUM, University of Montreal, Canada. He completed his Master degree in Computer Science at Grenoble Institute of Technology - Ensimag in 2011. His research interests range from real-time rendering to the procedural modeling of virtual worlds.

Adrien Bernhardt is a doctoral student at LJK, University of Grenoble, France. He received a Master degree in Computer Science at Grenoble Institute of Technology - Ensimag in 2006. His research interests include implicit modeling, sketch-based interfaces, and terrain modeling software.

Adrien Peytavie is an Assistant Professor of Computer Science at the Universit Claude Bernard Lyon 1, France. He received a PhD in Computer Science from Universit Claude Bernard Lyon 1 in Computer Science in 2010. His research interests include procedural modeling of virtual worlds and simulating natural phenomena.

Eric Galin is Professor of Computer Science at the Universit Lumre Lyon 2, France. He received an engineering degree from Ecole Centrale de Lyon in 1993 and a PhD in Computer Science from Universit Claude Bernard Lyon 1 in 1997. His research interests include procedural modelling of virtual worlds, simulating natural phenomena and modelling with implicit surfaces.

Marie-Paule Cani is Professor of Computer Science at Grenoble Institute of Technology. A graduate from the Ecole Normale Suprieure, she received a PhD from the University Paris 11 in 1990. Her research focus is making the creation of animated virtual worlds more intuitive, thanks to sketch-based interfaces, procedural models and interactive animation methods.