Structure

Internally, the terrain consists of a list of biomes. Each biome in turn consists of a list of points $(p_0, p_2, \dots, p_n)$. For a reasonably smooth terrain, we decided to use 2D $C^1$-continuous Hermite-Splines to interpolate in between the points. Here, every spline interpolates between a start $p_i = (x_i, y_i)^T$ and end point $p_{i+1} = (x_{i+1}, y_{i+1})^T$ given in 2D space. To do this, we use separate 1D $C^1$-continuous hermite splines $H_x(t), H_y(t)$ for $x$- and $y$-direction that are both dependent on an artificial third prameter $t$. This parameter $t$ is roughly equivalent to the distance along the terrain. Therefore, it is set to $t_0 = 0$ for the first point and calculated using euclidian distance for every further point.

To get the position of the terrain at a given $t$ we combine the two spline evaluations into a point $(H_x(t), H_y(t))^T$. We can calculate the $C^1$-continuous Hermite-Spline $H_{i,x}(t)$ between a given start and end point $x_{i}, x_{i+1}$ using start and end derivatives $dx_{i}, dx_{i+1}$ and a start value $t_i$ for $t$ as follows. The procedure is analogous for $H_{i,y}(t)$.

$$t_{i+1} = t_{i} + \sqrt{(x_{i+1} - x_{i})^2 + (y_{i+1} - y_{i})^2}$$ $$H_{i,x}(t) = (1- 3t^2 + 2t^3)x_{i} + (3t^2 - 2t^3)x_{i+1} + (t-2t^2 + t^3)(x_{i+1}-x_{i})dx_{i} + (t^3 - t^2)(x_{i+1}-x_{i})dx_{i+1}$$

We also experimented with $C^2$-continuous splines. In contrast to our method, here the first derivatives at the start and end of a spline are determined by conditions for the second order derivatives and do not need to be provided. However, these splines typically require us to know all interpolated points at once. Consequently, this approach is unsuitable for our generation that is performed in an online manner. For this reason, we chose to stick with $C^1$-continuous splines and provide the first order derivatives.

These first order derivatives can be freely chosen but need to match at the borders between splines since the splines are $C^1$-continuous. Therefore, we provided the start derivative $(dx_0, dy_0)^T = (1, 0)^T$ that corresponds to even terrain. From there, we set the derivative of the end of a spline piece to the slope for piecewise linear interpolation: $$\forall i\in{0,1, \dots, n-1}:\quad (dx_{i+1}, dy_{i+1}) = (x_{i+1} - x_i, y_{i+1} - y_i)$$

The individual spline pieces $H_i(t) = (H_{i, x}(t), H_{i, y}(t))^T$ are then combined into one continuous function $H(t)$, that allows us to interpolate the terrain at any $t$-value between the first and last point. Using this method, we can generate a spline-based interpolation of the ground points in an online setting which we need for the terrain generation.