Advanced Game Tech All

Procedural Generation of Roads





In this paper, we propose an automatic method for generating roads based on a weighted anisotropic shortest path algorithm. Given an input scene, we automatically create a path connecting an initial and a final point. The trajectory of the road minimizes a cost function that takes into account the different parameters of the scene including the slope of the terrain, natural obstacles such as rivers, lakes, mountains and forests. The road is generated by excavating the terrain along the path and instantiating generic parameterized models.

【在本文中,我们提出了一种基于加权各向异性最短路径算法的自动生成道路的方法。 给定一个输入场景,我们将自动创建一条连接起点和终点的路径。 道路轨迹使成本函数最小化,该成本函数考虑了场景的不同参数,包括地形的坡度,自然障碍物(如河流,湖泊,山脉和森林)。 通过沿路径挖掘地形并实例化通用参数化模型来生成道路。】








Modeling and rendering realistic images of landscapes and cities is an important problem in computer graphics. The creation of compelling models is a crucial task, not only in the entertainment industry but also in various training, planning and simulation applications.

【对景观和城市的逼真的图像进行建模和渲染是计算机图形学中的一个重要问题。 创建引人注目的模型是一项至关重要的任务,不仅在娱乐行业,而且在各种培训,计划和模拟应用中。】


Over the years, researchers have made considerable progress towards developing efficient techniques for generating natural landscapes covered with vegetation [DHL 98] and cities [PM01, MWH 06]. Procedural algorithms have been developed for generating large cities with complex street networks [CEW 08]. Several methods have been proposed for sketching [BN08] and editing [MS09] roads. The major limitation of editing approaches is that they require a considerable effort to carefully control the trajectories to obtain realistic roads. In contrast, the procedural generation of countryside roads and highways with tunnels and bridges remains an open area of research.

【多年来,研究人员在开发有效的技术以生成覆盖有植被[DHL * 98]和城市[PM01MWH * 06]的自然景观方面取得了长足的进步。已经开发了程序算法来生成具有复杂街道网络的大城市[CEW * 08]。已经提出了几种方法来绘制[BN08]和绘制[MS09]道路。编辑方法的主要局限性在于,它们需要大量的精力来仔细控制轨迹以获得真实的道路。相比之下,带有隧道和桥梁的乡村道路和高速公路的程序生成仍然是一个开放的研究领域。】


In this paper, we present an algorithm for generating a road connecting an initial and a final point that adapts to the characteristics of an input scene. Given an input scene, we compute the shortest path connecting an initial and a final point that minimizes a cost function that takes into account the slope of the terrain as well as natural obstacles such as rivers, lakes and forests. The discrete shortest path is then converted into a set of piecewise clothoid splines representing the trajectory of the road. This trajectory is further segmented according to the elevation of the terrain as well as rivers to identify which parts are surface roads and which parts should be instantiated as tunnels and bridges. Finally, we excavate the terrain along the path and rely on generic procedural road, bridge and tunnel models to create the final mesh models. Our contributions are as follows.



Control We present a class of parameterized and controllable cost functions that takes into account the different parameters of the scene including the slope of the terrain, natural obstacles such as rivers, lakes, mountains and forests (Section 4). Our generic cost function can also handle the evaluation of the cost of tunnels and bridges between two points in a consistent way.



Anisotropic shortest path We address the computation of the weighted anisotropic shortest path problem on a continuous domain, i.e. the creation of a path that minimizes the line integral of the cost function.



We present an algorithm that reduces the complex problem to an optimization over an implicit finite graph (Section 5). Our method restricts the search to paths formed by the concatenation of straight-line segments between grid aligned points from a uniform discretization of the continuous region. To overcome the limit-on-direction problem, we introduce k-neighborhood connectivity masks so as to generate realistic smooth paths.



We show that our anisotropic shortest path algorithm can generate tunnels and bridges in a consistent way by simply generalizing the optimization process over a more complex finite graph involving a huge number of arcs. Therefore, we propose an accelerated technique based on a stochastic sampling to speed up computations, at the expense of slightly less accurate shortest path.



Procedural generation We present a compact procedural model for representing roads, tunnels and bridges with a few parameters describing their geometrical characteristics. Our method automatically generates the smooth trajectory of the road from the piecewise segment paths, excavates the terrain around the path of the roads and generates the road mesh as well as bridges and tunnels with the appropriate size and characteristics (Section 6).







Related work


In this section, we briefly review research describing road generation and editing techniques, variational curve design on surfaces and shortest path algorithms.



City street modeling Several procedural techniques have been proposed to generate street networks [MWH 06] in cities in the context of large-scale urban modeling. Parish and Müller [PM01] first presented a solution to model street networks based on L-systems. Sun et al. [SYBG02] proposed a technique based on template road pattern and Voronoï diagrams. Another approach consists in using tensor fields to guide the generation of street graphs [CEW 08], which allows the user to interactively edit the street graph by either modifying the underlying tensor field or changing the graph directly. Alternatively, example based methods [AVB08, VABW09] have been proposed for interactively synthesizing urban street networks.

【城市街道建模在大规模城市建模的背景下,已提出了几种程序技术来在城市中生成街道网络[MWH * 06] ParishMüller[PM01]首先提出了一种基于L系统建模街道网络的解决方案。 Sun等。 [SYBG02]提出了一种基于模板道路模式和Voronoï图的技术。另一种方法是使用张量场来指导街道图的生成[CEW * 08],这允许用户通过修改基础张量场或直接更改图来交互式地编辑街道图。可替代地,已经提出了基于示例的方法[AVB08VABW09]用于交互式地合成城市街道网络。】


Interactive road editing and sketching Several techniques have been proposed for interactively editing and sketching roads. Bruneton et al. [BN08] presented a system to interactively edit very large terrains with very detailed features such as roads, rivers, lakes and fields. McCrae et al. [MS09] proposed a system for interactively editing a road network on a terrain based on user controlled piecewise clothoïd curves [MS08]. Cabral et al. [CLDD09] proposed an approach for modeling architectural scenes by reshaping and combining existing textured models, and demonstrated that this technique could be successfully applied to build complex road structures from simple initial pieces.

【交互式道路编辑和草图绘制已提出了几种用于交互式道路编辑和草图绘制的技术。 Bruneton等。 [BN08]提出了一种用于交互式编辑非常大的地形并具有非常详细的功能(例如道路,河流,湖泊和田野)的系统。 McCrae等。 [MS09]提出了一种基于用户控制的分段衣物曲线[MS08]来交互式编辑地形上的道路网络的系统。 Cabral等。 [CLDD09]提出了一种通过重塑和合并现有纹理模型来对建筑场景建模的方法,并证明该技术可以成功地用于从简单的初始零件构建复杂的道路结构。】


Variational path computation Paths can be generated using variational curve design on surfaces as presented in [HP04]. The proposed algorithm minimizes quadratic energy functionals involving first and second derivatives, but with the nonlinear side condition that the solution curves are confined to surfaces.



Anisotropic shortest path problem The solution to shortest-path problem is an active area of research in computational geometry. When strong assumptions on the costweighting functions are imposed, efficient algorithms can be used to compute the shortest-path.



A lot of techniques focus on the isotropic case when the cost function only depend on the position. Several algorithms have been proposed for planar regions and obstacle spaces defined by polygons and when the cost function is independent of velocity [MM97, HS99]. The complexity of the problem increases when the cost-weighting function is continuous but still independent of the velocity [MP91, AMS00]. Several efficient algorithms have been proposed to solve an isotropic shortest-path problem by solving a discretized Hamilton Jacobi Bellmann equation [Tsi95, PBT98]. However, none of these algorithms seems to generalize to the anisotropic case.

【当成本函数仅取决于位置时,许多技术都集中在各向同性情况下。对于由多边形定义的平面区域和障碍空间,以及当代价函数与速度无关时,已经提出了几种算法[MM97HS99]。当成本加权函数连续但仍与速度无关时,问题的复杂性就会增加[MP91AMS00]。通过求解离散化的Hamilton Jacobi Bellmann方程[Tsi95PBT98],提出了几种有效的算法来解决各向同性的最短路径问题。但是,这些算法似乎都不能推广到各向异性情况。】


Much less work has been devoted to the anisotropic case when the cost function depends on the position, velocity and acceleration. Several techniques were proposed for vehicles taking into account the grade of the climb [RR90, LMS99]. Aleksandrov et al. [AMS00, AMS05] proposed a discretization technique to solve the shortest path problem on a weighted terrain. The method involves inserting Steiner points on the edges of the polygonal terrain and then constructing an edge weighted graph. Therefore, the problem simplifies to finding a shortest path between two points in the graph. Kim et al. [KH03] proposed a method based on a nonuniform discretization of the continuous region obtained by a honeycomb sampling algorithm. An alternative technique has been presented in [JV04] using a rectangular grid to discretize the region. Because the cost is anisotropic, rectilinear paths connecting adjacent grid points may not approximate the optimal path. To overcome this limit-on-direction problem, the method searches over shifted versions of the rectilinear paths.

【当成本函数取决于位置,速度和加速度时,各向异性情况的工作量就更少了。考虑到爬坡的坡度,提出了几种针对车辆的技术[RR90LMS99] Aleksandrov等。 [AMS00AMS05]提出了一种离散化技术来解决加权地形上的最短路径问题。该方法包括在多边形地形的边缘上插入Steiner点,然后构造一个边缘加权图。因此,该问题简化为找到图中两点之间的最短路径。 Kim等。 [KH03]提出了一种基于通过蜂窝采样算法获得的连续区域的非均匀离散化的方法。在[JV04]中提出了一种替代技术,该技术使用矩形网格来离散化区域。由于成本是各向异性的,因此连接相邻网格点的直线路径可能无法逼近最佳路径。为了克服该方向限制问题,该方法搜索直线路径的移位版本。】







Discrete anisotropic shortest path algorithm


In this section, we present an overview of our discrete anisotropic shortest path algorithm for generating roads, tunnels and bridges over complex terrains.



Anisotropic shortest path problem Our paper addresses the weighted anisotropic shortest-path problem on a continuous domain, i.e., the computation of a path between two points that minimizes the line integral of a cost-weighting function along the path.



Consider a compact region Ω R 2 and two initial and final points denoted as a and b. Our goal is to compute a continuous path ρ from a to b that minimizes the line integral over the path of a cost weighting function c(p,p˙,p¨) that depends on the position p and the first two derivatives denoted as p˙ and p¨ respectively.

【考虑一个紧致区域ΩR 2和两个初始点和终点,分别表示为ab。我们的目标是计算从ab的连续路径ρ,以使成本加权函数cp)的路径上的线积分最小化,该函数取决于位置p和表示为p的前两个导数˙。】


To formalize the problem, we denote P the set of all continuous paths in Ω from a to b that are piecewise twice continuously differentiable, i.e., P denotes the set of continuous functions ρ : [0,T] → Ω, T > 0 for which ρ(0) = a and ρ(T) = b. Let C : P → [0,∞( denote the functional characterizing the cost of a path ρ P:

【为了使这个问题形式化,我们将P中从ab的所有连续路径的集合表示为P,它们是分段两次连续可微的,即P表示连续函数ρ的集合:[0T]→Ω,对于其中ρ0= aρT= b。令CP→[0(表示表征路径成本ρP的函数:】



The continuous anisotropic shortest path problem consists in finding a path ρ that minimizes the functional C(ρ):





Discrete anisotropic shortest path To overcome the difficulties that arise in solving the weighted anisotropic shortest path problem exactly, we approximate the solution by performing a uniform discretization of the region Ω into a grid. We define the path as a concatenation of segments between points on the grid. For a finite number of grid points, this procedure converts the original continuous shortest-path problem into a shortest-path problem on a finite graph G.

【离散各向异性最短路径为克服精确解决加权各向异性最短路径问题时出现的困难,我们通过将区域Ω均匀离散化为网格来近似求解。 我们将路径定义为网格上各点之间的线段的串联。 对于有限数量的网格点,此过程将原始的连续最短路径问题转换为有限图G上的最短路径问题。】



Grid sampling and graph definition Let pi j, (i, j) [0,n − 1] 2 denote the grid points uniformly sampling the search domain. Those points correspond to the nodes of the graph G. Because the cost function c is anisotropic, the segments connecting a point pi j to adjacent grid points may not give a good approximation of the optimal path [JV04]. The originality of our approach is to consider that every grid point pi j is implicitly connected to a large set of neighboring grid points within distance r. We define this subset as:

【网格采样和图定义令pi,(ij[0n-1] 2表示对采样域进行均匀采样的网格点。 这些点对应于图G的节点。由于成本函数c是各向异性的,因此将点pi j连接到相邻网格点的线段可能无法很好地逼近最佳路径[JV04]。 我们方法的独创性是考虑到每个网格点pi j隐式地连接到距离r内的大量相邻网格点。 我们将此子集定义为:】



Since explicitly storing those arcs would be memory demanding, we rely on generic path segment masks, denoted as Mk that will store the connectivity patterns between grid points (Section 5). This technique enables us to overcome the limit on direction problem that arise when considering only 4 or 8 connectivity between the grid points pi j.

【由于显式存储这些弧将需要大量内存,因此我们依赖于通用路径段掩码(表示为Mk),它将存储网格点之间的连通性模式(第5节)。 该技术使我们能够克服仅考虑网格点pi j之间的48个连通性时出现的方向问题的限制。】


Shortest path computation We compute the discrete shortest path by applying an A* algorithm to the graph G.

【最短路径计算我们通过对图G应用A *算法来计算离散最短路径。】


Recall that A* is a best-first graph search algorithm that finds the least-cost path from a given initial node to a goal node. We use the cost function c(p) plus an admissible heuristic cost estimate function e(p) to determine the order in which the search visits nodes. We define the function e(p) as the cost of a straight-line road to the goal b so that it never overestimates the actual minimal cost of reaching b. The heuristic function e is monotonic, therefore A* itself is admissible.

【回想一下A *是最佳优先图搜索算法,它查找从给定初始节点到目标节点的成本最低的路径。 我们使用成本函数cp)加上可允许的启发式成本估算函数ep)来确定搜索访问节点的顺序。 我们将函数ep)定义为到达目标b的直线道路的成本,因此它永远不会高估达到b的实际最小成本。 启发式函数e是单调的,因此A *本身是允许的。】


Let us present the outline of the algorithm. For every grid point, we define its corresponding cost value c(pi j) and its predecessor as p(pi j). The cost value of all the points c(pi j) is first initialized with ∞, whereas the value of the starting point c(a) is set to h(b). We initialize a priority queue Q with the initial point a. The main loop of the algorithm can be written as follows:

【让我们介绍算法的概述。 对于每个网格点,我们将其对应的成本值cpi j)定义为ppi j)。 首先用初始化所有点cpi j)的成本值,而起点ca)的值设置为hb)。 我们用初始点a初始化优先级队列Q。 该算法的主循环可编写如下:】


1. While Q is not empty, select the point pi j from the priority queue with the smallest cost value c(pi j).

2. If destination has been found pi j = b, stop the algorithm.

3. For all points q Mk(pi j), evaluate the cost c(pi j,q) over the segments [pi j,q]. If c(pi j,q) < c(q) then set the predecessor of q as pi j.

1.Q不为空时,从优先级队列中选择成本值cpi j)最小的点pi j

2.如果找到目的地pi j = b,则停止算法。

3.对于所有点qMkpi j),评估段[pi jq]上的成本cpi jq)。 如果cpi jq<cq),则将q的前任设置为pi j


This algorithm generates a discrete path characterized by a set of grid points and denoted as ρ = {pk}, k [0,n].

【该算法生成以一组网格点为特征的离散路径,并表示为ρ = {pk}k[0n]。】


Step 3 of the algorithm involves the computation of the set of grid points Mk(pi j) to define which nodes are connected together. It also requires the evaluation of the cost function along line segments connecting two grid points.This cost will be computed on the fly as follows. Let [pk ,pk+1] denote a segments of the path and tk , tk+1 the parameters corresponding to pk and pk+1. The line integral is defined as:

【该算法的第3步涉及计算一组网格点Mkpi j),以定义将哪些节点连接在一起。 它还需要沿着连接两个网格点的线段评估成本函数,该成本将按以下方式即时计算。 令[pkpk + 1]表示路径的一部分,tktk + 1表示与pkpk + 1对应的参数。 线积分定义为:】


We approximate the line integral as a finite sum by discretizing the integration domain into n intervals.



Cost functions definition We define a set of parameterized cost functions c(p(t),p˙(t),p¨(t)) that will be used to evaluate the line integral of the cost function. Those functions are defined by the user and indirectly control the trajectory of the path by constraining the shortest path research. In the next section, we address the computation of the cost functions.

【成本函数定义我们定义了一组参数化成本函数cpt),t),t)),将用于评估成本函数的线积分。 这些功能由用户定义,并通过限制最短路径研究来间接控制路径轨迹。 在下一节中,我们将讨论成本函数的计算。】







Cost functions


In this section, we present a class of cost functions that define the influence of the slope of the terrain and the natural obstacles over the shortest path computation. We define the global cost function c as a sum of several weighting functions that evaluate relative influence of the different characteristics of the terrain and the road. We propose to define the cost function as follows:

【在本节中,我们介绍一类成本函数,这些函数定义了地形的坡度和自然障碍物对最短路径计算的影响。 我们将全局成本函数c定义为评估地形和道路不同特征的相对影响的几个加权函数的总和。 我们建议将成本函数定义如下:】



The set of functions κi : R 3 ×R 3 ×R 3 → R evaluate the different characteristics of the terrain and the geometric characteristics of the trajectory of the road at point p. The functions µi are transfer functions that weight and combine the influence of the characteristics κi(p,p˙,p¨). Transfer functions allow the user to control the relative influence of the parameters of the scene and therefore control the shape of the minimum shortest path.

【函数集κiR 3×R 3×R 3→R评估地形的不同特征以及在点p处的道路轨迹的几何特征。 函数µi是传递函数,权重并组合了特征κip)的影响。 传递函数使用户可以控制场景参数的相对影响,从而控制最小最短路径的形状。】




Surface roads


The trajectory of a road on the surface of a terrain should be constrained by the slope of the terrain and natural obstacles such as rivers, lakes and forests (Figure 3). The cost function also takes into account the curvature of the road so as to control and constrain whether the generated road should avoid sharp curves.

【地形表面上的道路轨迹应受地形坡度和自然障碍物(如河流,湖泊和森林)的约束(图3)。 成本函数还考虑了道路的曲率,以控制和约束生成的道路是否应避免出现急弯。】




Characteristic functions Let p denote a point on the trajectory of a road on the surface of the terrain. We compute the following characteristic functions: the density of vegetation v(p), the water height w(p), the slope of the terrain in the direction of the trajectory of the road s(p,p˙) and the curvature of the trajectory of the road c(p,p˙,p¨).

【特征函数:令p表示地形表面上道路轨迹上的一个点。 我们计算出以下特征函数:植被密度vp),水高wp),地形在道路sp)的方向上的坡度以及道路的曲率 cp)的轨迹。】


The water height w(p) is defined as the maximum height of water in a small area Ω(p,r) around the projection of p onto the ground. Ω(p,r) denotes a sphere centered at point p and of radius r. The density of vegetation v(p) is computed by evaluating the number of trees that lie within Ω(p,r).

【水的高度wp)定义为p在地面上的投影周围的小区域ppr)中的最大水高度。 Ωpr)表示一个以点p为中心且半径为r的球体。 植被的密度vp)通过评估Ωpr)内的树木数量来计算。】


Transfer functions In this section, we present transfer functions that weight the influence of the characteristics of the scene and road trajectory. In our system, transfer functions are characterized by their graph which is edited interactively (Figure 4).

【传递函数在本节中,我们介绍权重场景和道路轨迹特性影响的传递函数。 在我们的系统中,传递函数的特征在于它们的图形,该图形可以进行交互式编辑(图4)。】



Transfer functions are characterized by a threshold value, denoted as κ0. If the input characteristic κ is greater than κ0, the corresponding transfer function µ(κ) should return infinity. This enables us to control the definition of regions where path cannot be created. Let us review two transfer functions.



Slope Let s(p,p˙) denote the slope of the terrain at point p. If the slope is too steep, the transfer function should return infinity so as to prevent paths from climbing very steep slopes which would generate unrealistic roads. Otherwise, we use a function of the slope controlled by the maximum cost value µ(κ0).



Water Let w(p) denote the maximum water depth in Ω(p,r). If the water is too deep, it is impossible to create a road and the water transfer function should return infinity. Otherwise, the water height is small enough to create the road at the expense of some banking. In that case, we use a function of the water depth, and µ(κ0) represents the maximum cost corresponding to the maximum water depth.






Bridges and tunnels


Bridges and tunnels are complex structures whose creation cost depends on many parameters including the geological properties of the ground. In our system, the cost for bridges is parameterized by the height of the bridge h(p), its slope and the depth of water bodies the bridges crosses (Figure 5).

【桥梁和隧道是复杂的结构,其建造成本取决于许多参数,包括地面的地质特性。 在我们的系统中,桥梁的成本由桥梁的高度hp),坡度和桥梁所穿过的水体深度来参数化(图5)。】



The cost function also takes into account the curvature so as to avoid the generation of dangerous bridges with sharp curves. The function h(p) denotes the vertical height of the bridge at point p with respect to the ground. The corresponding transfer function µheight is a piecewise function that returns infinity if the height is greater than maximum height value for the considered type of bridge.

【成本函数还考虑了曲率,以避免生成带有尖锐曲线的危险桥梁。 函数hp)表示桥梁在p点相对于地面的垂直高度。 相应的传递函数µheight是一种分段函数,如果高度大于所考虑桥类型的最大高度值,则该函数将返回无穷大。】


In the case of tunnels, the cost is parameterized by the depth of the tunnel to the surface d(p), its slope, and the depth of water bodies that may exist above the tunnel (Figure 6). This latter parameter enables us to simulate expensive tunnels passing under rivers or seas.

【在隧道的情况下,成本由隧道到地表的深度dp),坡度和隧道上方可能存在的水体的深度来参数化(图6)。 后一个参数使我们能够模拟穿越河流或海底的昂贵隧道。】






Segment path masks


In this section, we describe our method for computing the anisotropic shortest path over a uniformly sampled grid.



The limit on direction problem An important problem of uniform grid sampling is that it is not efficient as the number of grid points grows very fast if we want the shortest discrete path to approximate the position and direction of the shortest continuous path. This is because of the limit-on-direction effect (Figure 7).

【方向问题的限制统一网格采样的一个重要问题是,如果我们希望最短的离散路径近似于最短的连续路径的位置和方向,则网格点的数量会非常快地增长,因此效率很低。 这是因为方向限制效应(图7)。】



Recall that the discrete path is a rectilinear path composed of straight segments connecting sample points. Existing techniques only consider 4 or 8 connectivity between sample points. Therefore, the segments of the discrete path can only have 4 or 8 directions, with a maximal angle resolution of 45 degrees. Shift paths [JV04] can partially overcome this problem by allowing paths to shift away from the grid points, but require a computationally demanding relaxation step to shift path segments.

【回想一下,离散路径是由连接采样点的直线段组成的直线路径。 现有技术仅考虑采样点之间的48个连通性。 因此,离散路径的线段只能具有4个或8个方向,最大角度分辨率为45度。 移位路径[JV04]可以通过允许路径偏离网格点来部分克服此问题,但是需要计算上需要放松的步骤才能移位路径段。】


Overview To overcome the limit on direction problem, we propose to increase the neighborhood distance so as to introduce more directions, which enables us to improve the angle accuracy between path segments. This approach also allows us to consider very long arcs connecting distant grid points, which enables us to create bridge and tunnels.

【概述为了克服方向问题的局限性,我们建议增加邻域距离以引入更多方向,从而使我们能够提高路径段之间的角度精度。 这种方法还允许我们考虑连接远方网格点的很长的弧,这使我们能够创建桥梁和隧道。】




Path segment masks


Since explicitly storing all the arcs between grid points would be memory consuming, we propose to store the connectivity information between grid points using a set of path segment masks, denoted as Mk (Figure 8).




Definition We define the path segment masks Mk as the set of segments connecting the origin (0,0) to a point (i, j) [−k, k] 2 such that the greatest common divisor of i and j is 1 (Figure 8). Using this definition instead of all the (2k +1) 2 segments with (i, j) [−k, k] 2 avoids redundant path checking when applying the discrete shortest path algorithm.

【定义我们将路径段掩码Mk定义为将原点(0,0)连接到点(ij[−kk] 2的段的集合,以使ij的最大公约数为1( 图8)。 当使用离散最短路径算法时,使用此定义代替(ij[-kk] 2的所有(2k +12个段可避免冗余路径检查。】



Influence of the size of the masks Increasing the size of the segment path masks enables us to detect paths with a better angle resolution and to reduce the limit on direction effect, at the cost of an increasing number of iterations in the shortest path algorithm. Table 1 reports the number of path segments nk as well as the maximum angle α.



Figure 9 shows the influence of the parameter k over the computation of the shortest path between an initial point in a valley and a final point at the top of a steep hill. The cost function has been set to take into account the slope. For k = 1, the limited connectivity between grid points results in a shortest path following an unrealistic direct path to the top, ignoring the influence of the slope. As k increases, the resulting path gets more realistic.

【图9显示了参数k对计算山谷中起始点和陡峭山坡顶部终点之间最短路径的影响。已设置成本函数以考虑斜率。对于k = 1,网格点之间有限的连通性导致一条最短的路径,沿着一条不切实际的直达顶部的路径,而忽略了坡度的影响。随着k的增加,结果路径变得更加真实。】


Table 2 reports timings (in seconds) as well as the cost (in arbitrary unit) and the length (in meters) for computing the anisotropic shortest path with different path segment masks over a 60×60 grid. Timings increase in O(k 2 ).

【表2报告了在60×60网格上使用不同路径段掩码计算各向异性最短路径的时间(以秒为单位)以及成本(以任意单位为单位)和长度(以米为单位)。 Ok 2)的时间增加。】


Experiments demonstrate that the cost of the shortest path converges to a limit as the size of the mask increases. In general, chosing k = 5 proved to be a good compromise between speed and the angle resolution to generate realistic paths.

【实验表明,随着掩模尺寸的增加,最短路径的成本收敛到极限。通常,选择k = 5是在速度和角度分辨率之间产生真实路径的良好折衷方案。】






While segment path masks enable us to overcome the limit on direction problem, the generated path often have too many shape turns (Figure 9). Therefore, taking the curvature into account is crucial to obtain realistic paths. Instead of using a two-dimensional discretization of the domain Ω R 2 , we perform a three-dimensional discretization of the continuous domain Ω × [0,2π] which represents all the positions in Ω with all the possible orientations (Figure 10). We discretize the angular domain [0,2π] into m intervals. Thus, our approach consists in computing the discrete anisotropic shortest path over a n 2 × m three-dimensional grid of oriented points, denoted as pi ja, (i, j) [0,n] 2 , a [0,m − 1]. The segments path masks M generalize to extended masks, denoted as E, such that E(pi ja) refers to the set of all the points M(pi j) replicated for all a [0,m−1].

【虽然段路径蒙版使我们能够克服方向问题的限制,但生成的路径通常具有太多的形状转弯(图9)。 因此,考虑曲率对于获得真实路径至关重要。 代替使用域R 2的二维离散化,我们执行连续域Ω×[0,2π]的三维离散化,它表示in中具有所有可能方向的所有位置(图10) 。 我们将角域[0,2π]离散为m个间隔。 因此,我们的方法在于计算定向点的2×m三维网格上的离散各向异性最短路径,表示为pi ja,(ij[0n] 2a[0m- 1]。 段路径掩码M泛化为扩展掩码,表示为E,使得Epi ja)指的是对所有a[0m-1]复制的所有点Mpi j)的集合。】




This technique, combined with cost functions taking account the curvature of the path, enable us to keep track of the influence of the curvature cost and to generate more realistic paths, at the expense of more computations (Figure 11). Table 3 reports the corresponding statistics for a 60×60 grid with an angle discretization set to m = 12.

【这项技术与考虑路径曲率的成本函数相结合,使我们能够跟踪曲率成本的影响并生成更多逼真的路径,但要花更多的时间(图11)。 表3报告了角度离散化设置为m = 1260×60网格的相应统计量。】



Tunnels and bridges


Tunnels and bridges can be processed in a consistent way using an extension of path segments mask. The fundamental concept is to consider bridges and tunnels as long path segments connecting two distant grid points.

【可以使用扩展的路径段掩码以一致的方式处理隧道和桥梁。 基本概念是将桥梁和隧道视为连接两个遥远网格点的长路径段。】


Without loss of generality, let us first consider tunnels. As for surface roads, we introduce generic tunnel masks, denoted as T , that represent which paths connecting two grid points should be processed as tunnels by the shortest path algorithm (Figure 12).

【在不失一般性的前提下,让我们首先考虑一下隧道。 对于地面道路,我们引入通用隧道掩码,表示为T,该掩码表示连接两个网格点的哪些路径应通过最短路径算法处理为隧道(图12)。】


Those path segments have a minimum and a maximum distance, denoted as ri and re, which correspond to the minimum and maximum length a given type of tunnel or bridge can have. Therefore, we define:

【这些路径段具有最小距离和最大距离,分别表示为rire,它们对应于给定类型的隧道或桥梁可以具有的最小和最大长度。 因此,我们定义:】




Step 3 of the graph search algorithm is modified as follows. When processing a candidate grid point pi j, we compute and update the value of the grid points in two sets q M(pi j) and q T (pi j).

【图搜索算法的步骤3进行了如下修改。 在处理候选网格点pi j时,我们计算并更新两组qMpi j)和qTpi j)中的网格点的值。】


3. For all points q M(pi j), evaluate the surface road cost c(pi j,q), and for all points q T (pi j), evaluate the tunnel cost c(pi j,q). If c(pi j,q) < c(q) then set the ancestor of q as pi j.

3.对于所有点qMpi j),评估地面道路成本cpi jq),对于所有点qTpi j),评估隧道成本cpi jq)。 如果cpi jq<cq),则将q的祖先设置为pi j。】


Bridges are defined in the same way, the corresponding masks for bridges will be referred to as B.




Figure 13 presents two different roads generated with and without bridges. The corresponding statistics (Table 4) demonstrate that enabling bridges effectively reduces the cost of the path, at the expense of demanding computations.

【图13显示了使用和不使用桥梁生成的两条不同的道路。 相应的统计数据(表4)表明,启用网桥可以有效地降低路径成本,但需要付出大量的计算费用。】





Stochastic sampling


Detecting all the possible tunnels and bridges in a scene involves evaluating the corresponding cost function for a huge number of arcs. The number of arcs becomes quadratic as the external radius of the search region re increases.

【检测场景中所有可能的隧道和桥梁涉及评估大量弧线的相应成本函数。 随着搜索区域的外半径的增加,弧的数量变为二次方。】



Therefore, we propose a stochastic sampling technique to speed up computations. Instead of evaluating the tunnel and bridge functions values for all the grid points in the set T (pi j) at every step of the algorithm, we only perform computations for a restricted subset of segment paths S(pi j) Tk(pi j). Candidate grid points are obtained by stochastically selecting some of the grid points inside the hollow disc with a low discrepancy sequence (Figure 14) at every iteration of the algorithm.

【因此,我们提出了一种随机采样技术来加快计算速度。 代替在算法的每个步骤中评估集合Tpi j)中所有网格点的隧道和桥梁函数值,我们仅对段路径Spi jTkpi j )。 候选网格点是通过在算法的每次迭代中随机选择具有低差异序列(图14)的中空圆盘内的一些网格点来获得的。】



Table 5 reports statistics corresponding to the shortest paths illustrated in Figure 15 and demonstrating the efficiency of the sampling technique. The tunnel and bridge mask areas were set with ri = 50m and re = 300m over a 300 × 300 grid with a sampling grid size of 10m. The corresponding number of grid points visited at every iteration was equal to #T = 2728. In contrast, the number of sample grid points in the stochastic approach was set to #S = 50. Timings demonstrate that the speed up is proportional to the ratio #S/#T .

【表5报告了与图15中所示的最短路径相对应的统计信息,并证明了采样技术的效率。 在300×300的网格上,将隧道和桥梁的遮罩区域设置为ri = 50mre = 300m,采样网格大小为10m。 每次迭代时访问的相应网格点数等于#T =2728。相比之下,随机方法中的示例网格点数设为#S =50。时间表明,加速与比率成比例 #S /T。】



Timings demonstrate that our stochastic algorithm dramatically speeds up the computation of tunnels and bridges, with a very small cost overhead.









Procedural generation of road models


In this section, we present our method for generating the road, tunnel and bridge models from the discrete shortest path. Our method proceeds in three steps. First, the discrete shortest path is converted into a set of piecewise clothoid splines representing the trajectory of the road. We rely on a piecewise clothoid splines as these curves matches real world curvature constraints. The trajectory is further segmented to identify which parts should be instantiated as roads, tunnels or bridges. We modify the terrain and the vegetation along the trajectory, performing excavations and embankments, and generate the mesh representation of roads, tunnels and bridges from generic parameterized procedural models.

【在本节中,我们介绍了从离散最短路径生成道路,隧道和桥梁模型的方法。 我们的方法分三步进行。 首先,将离散的最短路径转换为代表道路轨迹的一组分段回旋样条样条。 我们依赖分段回旋样条,因为这些曲线与现实世界的曲率约束相匹配。 进一步细分轨迹,以标识应实例化为道路,隧道或桥梁的部分。 我们沿着轨迹修改地形和植被,执行挖掘和堤防,并从通用参数化程序模型生成道路,隧道和桥梁的网格表示。】



Generic models Roads, tunnels and bridges are implemented as procedural geometric models. This technique enables us to adapt the geometry to the constraints of the trajectory. Roads are characterized by a profile curve C parameterized by the width r of the asphalt section and the width R of a blending region (Figure 17). The blending region will be used to characterize the shape of excavations and embankments performed along the trajectory of the road.

【通用模型道路,隧道和桥梁被实现为过程几何模型。 这种技术使我们能够使几何形状适应轨迹的约束。 道路的轮廓曲线C由沥青截面的宽度r和混合区域的宽度R参数化(图17)。 融合区域将用于表征沿道路轨迹进行的开挖和路堤的形状。】




Trajectory computation


Recall that our discrete anisotropic shortest path algorithm generates a path defined as ρ = {pk}k[0,n] where the points pk are located on the grid points pi j discretizing the search domain Ω. We create a piecewise clothoid curve, denoted as Γ, from the control points pk as proposed in [WM05]. This enables us to generate smooth and realistic road trajectories.

【回想一下,我们的离散各向异性最短路径算法生成的路径定义为ρ = {pk}k[0n],其中点pk位于离散搜索域the的网格点pi j上。 我们根据[WM05]中提出的控制点pk创建了分段回旋曲线,表示为Γ。 这使我们能够生成平滑逼真的道路轨迹。】



Because of the smoothing process, some parts of the curve Γ corresponding to surface path segments may lie slightly inside or above the terrain. Therefore, we perform a segmentation of the trajectory with respect to the elevation of the terrain so as to identify which parts should be generated using the generic road, tunnel or bridge models (Figure 18).



The segmentation is performed by uniformly sampling Γ so as to generate a piecewise linear curve denoted as Γ = {qk}, k [0,n]. For every point in the discrete curve, we compute h(qk) as the difference between the height of the point qk and the height of its projection on the surface of the terrain. Let hT the minimum height value for creating a tunnel, and hB the minimum height value for creating a bridge. The segmentation is performed as follows: if h(qk) < hT : label qk as a tunnel point, if hT < h(qk) < hB: label qk as a road point, otherwise label qk as a bridge point.

【通过均匀采样Γ进行分割,以生成表示为Γ = {qk}k[0n]的分段线性曲线。对于离散曲线中的每个点,我们将hqk)计算为点qk的高度与其在地形表面上的投影高度之间的差。令hT为创建隧道的最小高度值,令hB为创建桥梁的最小高度值。分段执行如下:如果hqk<hT:将qk标记为隧道点,如果hT <hqk<hB:将qk标记为道路点,否则将qk标记为桥点。】


At the end of this process, the trajectory Γ is consistently defined as a piecewise linear curve created from clothoid splines and every point qk is unambiguously labeled as road, tunnel or bridge.

【在此过程的最后,将轨迹∗ ∗一致地定义为由回旋样条曲线创建的分段线性曲线,每个点qk都明确地标记为道路,隧道或桥梁。】



Road generation


Recall that R denotes the width of the road model, we define the neighborhood of the curve Γ as:



The road generation proceeds in two steps. First, we remove the existing vegetation in the vicinity of the road by removing tree instances that lie in ΩΓ. The terrain is also modified in the neighborhood of the trajectory as follows. First, we perform an adaptive refinement of the mesh of the terrain in the region ΩΓ (Figure 20). For every vertex v of the refined mesh, we compute the distance d(v,Γ) to the trajectory. Excavation and embankment are performed as follows:

【道路建设分两个步骤进行。 首先,我们通过移除ΩΓ中的树实例来移除道路附近的现有植被。 如下所示,还可以在轨迹附近修改地形。 首先,我们对ΩΓ区域的地形网格进行自适应细化(图20)。 对于精制网格的每个顶点v,我们计算到轨迹的距离dvΓ)。 开挖和堤防的执行方法如下:】


1. If d(v,Γ) < r, set the height of vertex v to the height of the corresponding nearest point on the curve.

2. If r < d(v,Γ) < R, compute the height of the vertex by interpolating the profile curve of the road C(d(v,Γ)) with the height of the terrain.


2.如果r <dvΓ<R,则通过将道路CdvΓ))的轮廓曲线与地形的高度插值来计算顶点的高度。



Finally, we generate the road, tunnel and bridge models from their parameterized definition and the discrete segmented trajectory which enables us to adapt to the characteristics of the terrain automatically.









We have implemented our procedural road generation technique into a modeling application coded in C++. We have applied our method to create the different images shown throughout this paper. Renderings were performed by using Mental Ray on the textured meshes produced by our method

【我们已经将过程道路生成技术实施到以C ++编码的建模应用程序中。我们已应用我们的方法来创建贯穿本文显示的不同图像。通过使用Mental Ray对通过我们的方法产生的纹理化网格进行渲染】


Realism Our method creates realistic trajectories and compares favorably in terms of efficiency and quality to existing editing and sketching techniques [MS09]. The main reason for this is that our algorithm generates an optimal path that satisfies a combination of realistic cost constraints. In particular, combining slope and curvature based costs enables us to automatically create very realistic mountain roads (Figure 16). Our algorithm also finds the best locations to create bridges and tunnels with a view to avoiding long detours.



Control A very interesting and powerful feature of our approach is its simplicity and control. The road generation process can be controlled very efficiently by tuning a few transfer functions (slope, curvature, vegetation, water height). In our system, the curves of those functions can be interactively modified.




Figure 21 illustrates the influence of the forest and water cost functions over the trajectory of the road. When the cost function of the forest is high and the bridge cost is low, our algorithm generates a long bridge crossing the river (left image). In contrast, when the impact of the forest over the global cost function is low and when the bridge cost is high, the method generates a longer road passing through forests with two small bridges (right image).

【图21说明了森林和水成本函数对道路轨迹的影响。 当森林的成本函数较高且桥梁成本较低时,我们的算法会生成一条过河的长桥(左图)。 相反,当森林对全球成本函数的影响较低且桥梁成本较高时,该方法会生成一条较长的道路,该道路穿过具有两座小桥的森林(右图)。】



Figure 22 shows the influence of the slope cost function over the trajectory. By setting the maximum authorized slope to a high value and lowering the influence of the slope cost function over the global cost, the generated path is a long surface road (left image). In contrast, if the maximum authorized slope is very low, it is no longer possible to create a road going up the hills and the algorithm creates a tunnel (right image).

【图22显示了坡度成本函数对轨迹的影响。 通过将最大授权坡度设置为较高的值并降低坡度成本函数对整体成本的影响,生成的路径是一条较长的路面(左图)。 相反,如果最大许可坡度非常低,则不再可能创建一条上山的道路,并且该算法会创建一条隧道(右图)。】


Efficiency The performance of our algorithm depends on the resolution of the underlying sampling grid. Our experiments show that our optimized algorithm can generate realistic trajectories in less than 1 second when using a 100×100 grid with both curvature control and tunnel and bridge detection activated.

【效率我们算法的性能取决于基础采样网格的分辨率。 我们的实验表明,当使用具有曲率控制以及隧道和桥梁检测功能的100×100网格时,我们的优化算法可以在不到1秒的时间内生成逼真的轨迹。】








We have proposed a complete framework for generating realistic roads in complex scenes. Our approach relies on a discrete anisotropic shortest path algorithm applied to a graph whose nodes are obtained by a uniform sampling of the scene and whose arcs are implicitly defined using generic segment path masks. The trajectory of roads can be easily controlled by adjusting the parameters of the transfer functions that weight the relative influence of the characteristics of the terrain.

【我们已经提出了用于在复杂场景中生成逼真的道路的完整框架。 我们的方法依赖于应用于图的离散各向异性最短路径算法,该图的节点是通过场景的均匀采样获得的,其弧线是使用通用段路径掩码隐式定义的。 可以通过调整传递函数的参数来轻松控制道路轨迹,这些传递函数会权衡地形特征的相对影响。】


This work is the first step towards a solution to the much more complex and general problem of modeling a complete hierarchical road network connecting cities. We are currently investigating this research field.

【这项工作是解决建模连接城市的完整分层道路网络这一更为复杂和普遍的问题的第一步。 我们目前正在研究这个研究领域。】