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.