An Overview of Procedurally Generating Virtual Environments
程序生成虚拟环境概述

Procedural generation; Parallax Mapping; Skeleton Algorithm; Shape Grammer; Tree-Map Algorithm; L-system
程序生成；视差映射；骨架算法；形状语法；树图算法；L 系统

In recent years, virtual worlds have been used in the film and video game industry, digital cultural heritage, simulation of urban phenomena and interior and exterior design planning. As virtual and augmented reality applications continue to evolve, there is an increasing demand for methods that enable fast, detailed and interactive 3D content. Hand-built virtual worlds are very rigorous and cannot be easily modified once they are finished, especially for some large-scale scenarios.
近年来，虚拟世界已被应用于电影和视频游戏行业、数字文化遗产、城市现象模拟以及室内和室外设计规划。随着虚拟和增强现实应用的不断发展，对能够快速、详细和互动的 3D 内容的方法需求不断增加。手工构建的虚拟世界非常严谨，一旦完成就很难轻易修改，尤其是对于一些大规模场景。

Procedural generation is an active research topic, the main goal is to be able to automatically create the desired object with minimal input, procedurally generated objects are also very easy to modify twice, it is used in a variety of fields, such as textures, plants, terrain, buildings, rivers and various artistic creations, this paper will introduce the generation methods for the most frequently procedurally generated content such as plants, buildings, terrain.
程序化生成是一个活跃的研究课题，其主要目标是能够通过最少的输入自动创建所需的对象，程序化生成的对象也非常容易进行二次修改，它被应用于多个领域，如纹理、植物、地形、建筑、河流和各种艺术创作。本文将介绍植物、建筑、地形等最常进行程序化生成的内容的生成方法。

The phenomenon of self-similarity is widespread in nature, and fractal structures are more stable and fault-tolerant than Euclidean geometry, with greater determinism, inspired by which was introduced into the field of computer graphics known as L-system [2], a context-independent band grammar that generates each rule that applies to only one symbol in the geometry, starting from the initial structure. Other symbols are not affected by the rules. A new object is formed by replacing some parts of the representation and iteratively applying some rules for string symbols to create branching structures. If a character is treated as an element of a language, then a set of rewrite rules might look like this:
自相似现象在自然界中广泛存在，分形结构比欧几里得几何更稳定、更容错，并具有更大的确定性，受此启发，引入了计算机图形学领域的 L 系统[2]，这是一种上下文无关的带状文法，从初始结构开始生成仅适用于几何中一个符号的每条规则。其他符号不受规则影响。通过替换表示的一些部分并迭代应用一些字符串符号规则来创建分支结构形成新对象。如果将字符视为语言的元素，那么一组重写规则可能如下所示：

This principle was originally used by Chomsky et al [1] in their description of a programming language.L-Systems requires that each rewrite rule be applied once in each round because plant growth is based on cell division and all cells occur in parallel. If “a” in the above example is used as the initial string, the process can be represented as shown in Figure 1.
这一原理最初由 Chomsky 等人[1]在他们对编程语言的描述中使用。L 系统要求每个重写规则在每轮中应用一次，因为植物生长是基于细胞分裂，所有细胞都是并行发生的。如果以上例子中的“a”被用作初始字符串，则该过程可以如图 1 所示。

Figure 1. String generation process
图 1. 字符串生成过程
In the L-system, this process describes how plants grow. In more common representations, we mark any substitutions that may occur with parentheses around the corresponding substrings. For example, an L -system can be defined as follows ( n is the number of times the rewrite rule is applied, ’ F ’ in the second line is the initial string, and $\delta$$\delta$delta\delta is the degree of bending):
在 L 系统中，这个过程描述了植物的生长。在更常见的表示中，我们用括号标记可能发生替换的对应子串。例如，一个 L 系统可以定义如下（n 是重写规则应用的次数，第二行中的“F”是初始字符串， $\delta$$\delta$delta\delta 是弯曲的程度）：

Figure 2. L-system generation results process
图 2. L 系统生成结果过程
The L-system makes it simple to generate plants with different shapes, and if 3D plants need to be generated, simply replace the initial left- and right-turn operations with movements in 3D space at each decision point [1], making the L-system by far the most widely used and successful method for procedurally generating plant content.
L 系统使得生成不同形状的植物变得简单，如果需要生成 3D 植物，只需在每个决策点将初始的左转和右转操作替换为在 3D 空间中的移动[1]，使得 L 系统成为迄今为止程序化生成植物内容最广泛使用和最成功的方法。

There are a large number of research papers on the development of procedurally generated buildings [3-6], but only a small number of concrete implementations [7 8]. Procedural generation has been a
关于程序生成建筑物的研究论文数量众多 [3-6]，但具体实现的数量却很少 [7 8]。程序生成自 2000 年以来一直是一个
popular research area since 2000.Procedurally generated buildings are generally divided into two parts.
热门的研究领域。程序生成的建筑物通常分为两部分。

These two together generate a complete building.
这两者共同生成一个完整的建筑。

Johnson et al. improved the Treemap [9] algorithm and proposed the Squarified Treemap algorithm [10] for filling rooms in a given rectangular building region.
Johnson 等人改进了 Treemap [9]算法，并提出了 Squarified Treemap 算法 [10]，用于填充给定矩形建筑区域内的房间。

Figure 3. Layout division results
图 3. 布局划分结果
As shown in Fig. 3, compared to the result Fig. 3(b) of the TreeMap algorithm, the result Fig. 3© produced by Squarified Treemap is much better in terms of the width to height ratio of the rooms, the rooms should be placed so that the width to height ratio of each room is as close to 1 as possible, to avoid generating rooms that are too long or narrow, but this result lacks utility in the sense that each room can only be connected to another individual room and the whole generated result has no corridor.Mirahmadi and Shami et al. proposed an improvement to the Squarified Treemap algorithm [22], which is able to find corridor paths connecting all individual rooms in a building.
如图 3 所示，与 TreeMap 算法的结果图 3(b)相比，Squarified Treemap 生成的结果图 3(c)在房间的宽高比方面要好得多，房间的放置应尽量使每个房间的宽高比接近 1，以避免生成过长或过窄的房间，但这个结果在实用性方面有所欠缺，因为每个房间只能与另一个独立房间相连，整个生成结果没有走廊。Mirahmadi 和 Shami 等人提出了一种对 Squarified Treemap 算法的改进[22]，能够找到连接建筑中所有独立房间的走廊路径。
Another limitation of the tree diagram algorithm is that it can only process rectangular regions.The constrained growth method for procedural floorplan generation proposed by Lopes et al [11] is able to process arbitrarily shaped regions. As shown in Fig. 4, the target region is first tiled.For each room, a cell is selected as the starting point, and it grows sequentially in a single direction until it reaches its predefined size. The next iteration is performed in the second iteration, in which a cell is assigned to a room connected to it. Then the next iteration is performed, and in the second iteration, each unfilled cell is assigned to a room connected to it.
树状图算法的另一个限制是它只能处理矩形区域。Lopes 等人提出的用于程序化平面图生成的约束增长方法能够处理任意形状的区域。如图 4 所示，目标区域首先被划分为小块。对于每个房间，选择一个单元格作为起点，并在单一方向上顺序增长，直到达到预定义的大小。下一次迭代在第二次迭代中进行，其中一个单元格被分配给与其相连的房间。然后进行下一次迭代，在第二次迭代中，每个未填充的单元格被分配给与其相连的房间。

Figure 4. Constrained growth method approach layout
图 4. 约束增长方法布局