Feb 23, 2013

Heightmaps, like the one below, can make our lives a lot easier. When making a terrain, for example, we can use the height map's color to specify the height. If the heightmap is placed on the x-y plane, we can use the RGB values of the image to define a certain height (z) at that point. It makes terrain creation much easier than hard-coding the points in and it's easy to change!

For each pixel, we can use displacement mapping and add a point with a cooresponding height. After calculating each (x, y, z) component, the previous heightmap will look similar to this (with green coloring):

This looks bland because there's no feel of depth. We really want something more realistic. That means we need to add normals for each vertex. This is the fun part. I have a bunch of points, and need to find the normal at that point (or at least approximate it). An easy way to do this is to take the cross product of two vectors.

A vector can be made from subtracting the points immediately left, right, in, and out from the point of interest. Let's call our result the out, left, in, and right vectors. Cross the out and left vector, the left and in vector, the in and right vector, and the right and out vector. Then, we add the four crossed results to get the normal at the point of interest. This website has a good explanation as to why we add the four crossed vectors. Now our terrain looks something like this:

Zooming in, we can see a bit of the triangle strips in action. The terrain is not completely smooth. We can take the sum of all the normals around the point of interest to give it more of a smooth look.

Then there's the question of "can we optimize this?" Can we exclude the cross product with its numerous subtractions and multiplications? This is where we can use approximations. The next section will be theoretical but it will be useful, I promise :)

If there is a surface

\( z(t) = f( x(t), y(t) )\), it can be changed into the function \( U( x(t), y(t), z(t) ) = k \) where k is a constant. If we differentiate both sides:
$$ \frac{dU}{dt} = \frac{dU}{dx}\frac{dx}{dt}+\frac{dU}{dy}\frac{dy}{dt}+\frac{dU}{dz}\frac{dz}{dt}.$$

We can define the gradient:

$$ gradient = \left ( \frac{dU}{dx}, \frac{dU}{dy}, \frac{dU}{dz} ) \right )$$

The vector \( ( \frac{dx}{dt}, \frac{dy}{dt}, \frac{dz}{dt} ) \) is tangent to the surface, which makes the gradient a normal to the surface. We don't have an exact equation to our surface, but we can approximate the change in the different directions using the finite difference method. If we are on an x-y plane with z as the height:

$$ \frac{dU}{dx} = \frac{\text{ heightOfRightPoint} - \text{heightOfLeftVector}}{2}$$

$$ \frac{dU}{dy} = \frac{\text{ heightOfOutPoint} - \text{heightOfInVector}}{2} $$

$$ \frac{dU}{dz} = 1 $$

Multiplying the gradient vector by 2, we get:

$$ normal = ( \\ \text{heightOfRightPoint} - \text{heightOfLeftPoint}, \\ \text{heightOfUpPoint} - \text{heightOfDownPoint}, \\ 2 ); $$

That takes out the cross product. With the estimations, the final result looks similar to the one before! :) Another way of optimization is pre-calculating all of the normals before rendering and calculating only when the terrain is changed. Then, we don't have to recalculate the normals each frame unless it's necessary.