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 defined by its height function where is open subset, and is domain of the mapping . Euclidean metric in induces metric on :

(1)

where we assume that has smooth partial derivatives and . 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)

where parameter characterizes the penalty for travelling on an uneven terrain. By definition:

.

## Bounds on Geodesics

With parameter growing, the imaginary elastic cord used to represent the geodesics becomes more stretched in horizontal directions rather in vertical 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 and with 2D Euclidean distance between them . A geodesic curve connecting and in metric will be denoted by . Let’s also denote by length of the curve .

**Lemma.** *If height function has limited gradient in : then projection of the shortest geodesic curve to resides in -vicinity of the line cut where .*

**Proof.** Consider lift of straight line to the terrain manifold . The length of is less or equal since we have to travel distance horizontally and no more than vertically. In metric the same reasoning leads to the upper bound for the same lift . The shortest geodesic will be no longer than . On the other hand it can’t be shorter than . Hence the shortest geodesic curve will project inside elliptic vicinity of with foci at and and semi-minor axis . **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.