Roads

Added support for vector data which is currently used for simple roads, later it will be used also for rivers and similar stuff.
The points are interpolated using Catmull-Rom spline, and the generated path is baked into tile's material map with specific artifical material. Tile height map is modified too by setting the elevation from the path but gradually blending the borders to terrain.
The roads can also be slanted.



The actual algorithm runs in shader, finding the distance to spline from each point and outputs a blending coefficient and elevation. Asphalt material id is generated where the coefficient is one, otherwise only the height map is modified by blending.
Once the map is created it incurs no additional performance penalty - it's just another set of materials used.



While the algorithm can also generate the road surface markings as specific materials, the resolution of the material map for the tile isn't sufficient for such highly contrasting stuff. This will have to be drawn separately as an overlay on the tile, possibly using the same algorithm but when drawing to the screen.

The algorithm

I'm drawing quads with road segments into an intermediate texture that contains elevation (as interpolated by the spline) and blending coefficient which is 1 for road surface and slowly falling to 0 on road borders.
To get the distance to spline for particular pixel I had to transform world coordinates to road segment's lengthwise and crosswise coordinates.

The final solution got somewhat more complicated, though.

Since the linear interpolation on quads is ambiguous, I had to treat the segment as a bilinear surface and compute the inverse of it so as to get these lengthwise/crosswise coordinates. See http://stackoverflow.com/questions/808441/inverse-bilinear-interpolation for explanation.

But as it turned out this wasn't sufficient enough, because of course the spline road segment isn't a bilinear surface. It led to roads that narrowed in sharper turns or disappeared.
Actual road segment surface equation could be:

    p = q(s) + t*n(s)

where q(s) is the spline equation, n(s) is 2D normal to the spline, s is the lengthwise coordinate and finally t is the crosswise coordinate. However, this would lead to solving 5th degree polynomial and one would have to pick the correct root too ...

But ultimately I used this equation to take one step of Newton-Raphson approximation, seeding it with value of s computed by the inverse bilinear transform. The approximation converges rapidly so one step was enough.
The equation for one step of Newton-Raphson is:

    s1 = s0 - f(s0)/f'(s0)

with

    f(s) = (px - qx(s)) * qx'(s) + (py - qy(s)) * qy'(s)
f'(s) = (px - qx(s)) * qx"(s) - qx'(s) * qx'(s)
+ (py - qy(s)) * qy"(s) - qy'(s) * qy'(s)

So you need the first and second derivative of the spline equation to compute it.