Generating a normal map from a height map?

I'm working on procedurally generating patches of dirt using randomized fractals for a video game. I've already generated a height map using the midpoint displacement algorithm and saved it to a texture. I have some ideas for how to turn that into a texture of normals, but some feedback would be much appreciated.

My height texture is currently a 257 x 257 gray-scale imag开发者_开发问答e (height values are scaled for visibility purposes):

My thinking is that each pixel of the image represents a lattice coordinate in a 256 x 256 grid (hence, why there are 257 x 257 heights). That would mean that the normal at coordinate (i, j) is determined by the heights at (i, j), (i, j + 1), (i + 1, j), and (i + 1, j + 1) (call those A, B, C, and D, respectively).

So given the 3D coordinates of A, B, C, and D, would it make sense to:

1. split the four into two triangles: ABC and BCD
2. calculate the normals of those two faces via cross product
3. split into two triangles: ACD and ABD
4. calculate the normals of those two faces
5. average the four normals

...or is there a much easier method that I'm missing?

Example GLSL code from my water surface rendering shader:

#version 130
uniform sampler2D unit_wave
noperspective in vec2 tex_coord;
const vec2 size = vec2(2.0,0.0);
const ivec3 off = ivec3(-1,0,1);

    vec4 wave = texture(unit_wave, tex_coord);
    float s11 = wave.x;
    float s01 = textureOffset(unit_wave, tex_coord, off.xy).x;
    float s21 = textureOffset(unit_wave, tex_coord, off.zy).x;
    float s10 = textureOffset(unit_wave, tex_coord, off.yx).x;
    float s12 = textureOffset(unit_wave, tex_coord, off.yz).x;
    vec3 va = normalize(vec3(size.xy,s21-s01));
    vec3 vb = normalize(vec3(size.yx,s12-s10));
    vec4 bump = vec4( cross(va,vb), s11 );

The result is a bump vector: xyz=normal, a=height

My thinking is that each pixel of the image represents a lattice coordinate in a 256 x 256 grid (hence, why there are 257 x 257 heights). That would mean that the normal at coordinate (i, j) is determined by the heights at (i, j), (i, j + 1), (i + 1, j), and (i + 1, j + 1) (call those A, B, C, and D, respectively).

No. Each pixel of the image represents a vertex of the grid, so intuitively, from symmetry, its normal is determined by heights of neighboring pixels (i-1,j), (i+1,j), (i,j-1), (i,j+1).

Given a function f : ℝ² → ℝ that describes a surface in ℝ³, a unit normal at (x,y) is given by

v = (−∂f/∂x, −∂f/∂y, 1) and n = v/|v|.

It can be proven that the best approximation to ∂f/∂x by two samples is archived by:

∂f/∂x(x,y) = (f(x+ε,y) − f(x−ε,y))/(2ε)

To get a better approximation you need to use at least four points, thus adding a third point (i.e. (x,y)) doesn't improve the result.

Your hightmap is a sampling of some function f on a regular grid. Taking ε=1 you get:

2v = (f(x−1,y) − f(x+1,y), f(x,y−1) − f(x,y+1), 2)

Putting it into code would look like:

// sample the height map:
float fx0 = f(x-1,y), fx1 = f(x+1,y);
float fy0 = f(x,y-1), fy1 = f(x,y+1);

// the spacing of the grid in same units as the height map
float eps = ... ;

// plug into the formulae above:
vec3 n = normalize(vec3((fx0 - fx1)/(2*eps), (fy0 - fy1)/(2*eps), 1));

A common method is using a Sobel filter for a weighted/smooth derivative in each direction.

Start by sampling a 3x3 area of heights around each texel (here, [4] is the pixel we want the normal for).

[6][7][8]
[3][4][5]
[0][1][2]

Then,

//float s[9] contains above samples
vec3 n;
n.x = scale * -(s[2]-s[0]+2*(s[5]-s[3])+s[8]-s[6]);
n.y = scale * -(s[6]-s[0]+2*(s[7]-s[1])+s[8]-s[2]);
n.z = 1.0;
n = normalize(n);

Where scale can be adjusted to match the heightmap real world depth relative to its size.

If you think of each pixel as a vertex rather than a face, you can generate a simple triangular mesh.

+--+--+
|\ |\ |
| \| \|
+--+--+
|\ |\ |
| \| \|
+--+--+

Each vertex has an x and y coordinate corresponding to the x and y of the pixel in the map. The z coordinate is based on the value in the map at that location. Triangles can be generated explicitly or implicitly by their position in the grid.

What you need is the normal at each vertex.

A vertex normal can be computed by taking an area-weighted average of the surface normals for each of the triangles that meet at that point.

If you have a triangle with vertices v0, v1, v2, then you can use a vector cross product (of two vectors that lie on two of the sides of the triangle) to compute a vector in the direction of the normal and scaled proportionally to the area of the triangle.

Vector3 contribution = Cross(v1 - v0, v2 - v1);

Each of your vertices that aren't on the edge will be shared by six triangles. You can loop through those triangles, summing up the contributions, and then normalize the vector sum.

Note: You have to compute the cross products in a consistent way to make sure the normals are all pointing in the same direction. Always pick two sides in the same order (clockwise or counterclockwise). If you mix some of them up, those contributions will be pointing in the opposite direction.

For vertices on the edge, you end up with a shorter loop and a lot of special cases. It's probably easier to create a border around your grid of fake vertices and then compute the normals for the interior ones and discard the fake borders.

for each interior vertex V {
  Vector3 sum(0.0, 0.0, 0.0);
  for each of the six triangles T that share V {
    const Vector3 side1 = T.v1 - T.v0;
    const Vector3 side2 = T.v2 - T.v1;
    const Vector3 contribution = Cross(side1, side2);
    sum += contribution;
  }
  sum.Normalize();
  V.normal = sum;
}

If you need the normal at a particular point on a triangle (other than one of the vertices), you can interpolate by weighing the normals of the three vertices by the barycentric coordinates of your point. This is how graphics rasterizers treat the normal for shading. It allows a triangle mesh to appear like smooth, curved surface rather than a bunch of adjacent flat triangles.

Tip: For your first test, use a perfectly flat grid and make sure all of the computed normals are pointing straight up.