In recent article in Game Programming Gems 8 on roads modeling [1], roads are generated as geodesic curves on terrain surface. The idea presented in the article is to modify the standard metric, induced on the terrain surface, with a metric, which penalizes travelling up and down terrain slopes. It was mentioned that a high penalty for slopes may lead to computational instability with roads taking increasingly longer detours. Here we discuss upper bound on the detour length.

Roads, as geodesics, are bounded: the missing lemma

Please refer to [1] for additional details regarding definitions and motivations.

Roads as Geodesics

Terrain surface can be modeled as 2D projectable manifold $M$ defined by its height function $f:\Omega \to R$ where $\Omega \in R^2$ is open subset, and is domain of the mapping $f=f(x,y)$ . Euclidean metric in $R^3$ induces metric on $M$ :

(1) $dl^2 = dx^2 + dy^2 + df(x,y)^2 = dx^2 + dy^2 + (f_x dx + f_y dy)^2$

where we assume that $f(x,y)$ has smooth partial derivatives $f_x$ and $f_y$ . The metric (1) results in geodesics that can be viewed as elastic cord lines snapped to the terrain surface along their entire length. They tend to minimize their length while staying on the terrain.

For more realistic modeling outcome we can introduce additional penalty for traveling up or down the slopes. This (very) roughly corresponds to the logic of how roads are placed in the real word. The modified metric:

(2) $dL^2(\lambda) = dl^2 + \lambda (f_x dx + f_y dy)^2$

where parameter $\lambda \ge 0$ characterizes the penalty for travelling on an uneven terrain. By definition:

$dL^2(0)=dl^2$ .

Bounds on Geodesics

With parameter $\lambda$ growing, the imaginary elastic cord used to represent the geodesics becomes more stretched in horizontal directions rather in vertical $z$ direction. This may lead to an increasingly long geodesics taking longer detours around uneven terrain. One of the practical questions is how far they can deviate from the geodesics induced by the original metric (1).

Let’s introduce some notations to formulate and prove a lemma on the boundary for a possible detour distance. Consider two points $a=(x_0,y_0) \in \Omega$ and $b=(x_1,y_1) \in \Omega$ with 2D Euclidean distance between them $D=|a-b|$ . A geodesic curve connecting $a$ and $b$ in metric $dL^2(\lambda)$ will be denoted by $\gamma(\lambda)$ . Let’s also denote by $l_{\lambda}(\gamma)$ length of the curve $\gamma(\lambda)$ .

Lemma. If height function $f$ has limited gradient in $\Omega$ : $|df| < G$ then projection of the shortest geodesic curve $\gamma(\lambda)$ to $R^2$ resides in $r$ -vicinity of the line cut $(a,b)$ where $r \le \sqrt{1+\lambda} D G$ .

Proof. Consider lift $\theta (a,b)$ of straight line $(a,b)$ to the terrain manifold $M$ . The length $l_0(\theta)$ of $\theta$ is less or equal $D \sqrt{ 1+G^2}$ since we have to travel distance $D$ horizontally and no more than $DG$ vertically. In metric $dL^2(\lambda)$ the same reasoning leads to the upper bound $l_{\lambda}(\theta) = D \sqrt{ 1+(1+\lambda) G^2}$ for the same lift $\theta$ . The shortest geodesic $\gamma(\lambda)$ will be no longer than $l_{\theta}(\lambda)$ . On the other hand it can’t be shorter than $D$ . Hence the shortest geodesic curve will project inside elliptic vicinity of $(a,b)$ with foci at $a$ and $b$ and semi-minor axis $\frac{1}{2}D G \sqrt{1+\lambda}$ . Q.E.D.

Note: this Lemma still does not guarantee computation stability in the extreme cases as it doesn’t account for any particular computational procedure for building the approximation to the shortest path.

References

[1] Igor Borovikov, Aleksey Kadukin, “Road Creation for Projectable Terrain Meshes” in Game Programming Gems 8, 2010, pp. 453-461.

3DMatics

Roads on Projectable Terrain

Roads, as geodesics, are bounded: the missing lemma