Calculate Normal's from Heightmap

[SpiderPig]

I want to calculate the normal's from a height-map image by checking the neighboring pixels but I'm unsure on the correct way of doing it. This is the code I'm using below so far;

 

unsigned int map_index = 0;

for (int y = 0; y < map_size; y++)
{
for (int x = 0; x < map_size; x++)
{
unsigned int current_index = (y * map_size) + x;

if (x == 0) { center_l = map[current_index]; }
else {
 map_index = (y * map_size) + (x - 1);
 center_l = map[map_index];
}

if(x == (map_size - 1)){ center_r = map[current_index]; }
else {
 map_index = (y * map_size) + (x + 1);
 center_r = map[map_index];
}
if (y == 0) { center_u = map[current_index]; }
else {
 map_index = ((y - 1) * map_size) + x;
 center_u = map[map_index];
}
if (y == (map_size - 1)) { center_d =map[current_index]; }
else {
 map_index = ((y + 1) * map_size) + x;
 center_d = map[map_index];
}

normal_buffer.x = center_l - center_r;
normal_buffer.y = 2.0;
normal_buffer.z = center_u - center_d;
normal_buffer = normal_buffer.Normalize();

n_x[id] = normal_buffer.x;
n_y[id] = normal_buffer.y;
n_z[id] = normal_buffer.z;
id++;
}
}

 

"map" is just a collecting of floats representing the height for each vertex.

 

I think there's another way of calculating the normal's for each vertex using the cross product of two vectors? But I'm not sure how to do this. Any help is appreciated.

[nick.ace]

This should work:

tangent = normalize(vec3(2.0, center_l - center_r, 2.0))
bitangent = normalize(vec3(2.0, center_u - center_d, 2.0))
normal = cross(bitangent, tangent)

[SpiderPig]

Unfortunately that didn't work.

 

Using the old code:

 

 

Using the new code:

 

Vec3 tangent = Vec3(2.0, center_l - center_r, 2.0).Normalize();
Vec3 bitangent = Vec3(2.0, center_u - center_d, 2.0).Normalize();
normal_buffer = bitangent.Cross(tangent);

 

 

Here is a picture in wire-frame so you can see the different levels of details:

 

 

The normal's for the different levels are calculated using the same loop but with a different step value as it goes through the map.

[nick.ace]

I switched the two around:

tangent = normalize(vec3(2.0, center_r - center_l, 2.0))
bitangent = normalize(vec3(2.0, center_d - center_u, 2.0))
normal = cross(tangent, bitangent)

 

Also, I put 2.0 for the distance since I wasn't sure what scale your heightmap was at.

[Ma-Shell]

You are right, this can be done by using the crossproduct.

For calculating the normal of the point p with coordinates [x; y; f(x,y)], (whereas f(x,y) is the height-value at point x, y) the following four neighbouring points are of interest:

Left: l [x-1; y; f(x-1, y)]

Right: r [x+1; y; f(x+1, y)]

Up: u [x; y-1; f(x, y-1)]

Down: d [x; y+1; f(x, y+1)]

 

This means, you have the following four vectors:

l -> p: lp [x-(x-1), y-y, f(x,y)-f(x-1,y)] = [1; 0; f(x,y)-f(x-1,y)]

p -> r: pr [(x+1)-x, y-y, f(x+1,y)-f(x,y)] = [1; 0; f(x+1,y)-f(x,y)]

u -> p: up [x-x, y-(y-1), f(x,y)-f(x,y-1)] = [0; 1; f(x,y)-f(x,y-1)]

p -> d: pd [x-x; (y+1)-y; f(x,y+1)-f(x,y)] = [0; 1; f(x,y+1)-f(x,y)]

 

You can build the four cross-products: up x lp, up x pr, pd x lp, pd x pr (I used the right-hand-rule to determine which directions to take the crossproduct) and then take their average for your normal. Since every vector has one component 1 and one 0, the crossproducts are fairly simple:

up x lp: [f(x,y)-f(x-1,y); f(x,y)-f(x,y-1); -1]

up x pr: [f(x+1,y)-f(x,y); f(x,y)-f(x,y-1); -1]

pd x lp: [f(x,y)-f(x-1,y); f(x,y+1)-f(x,y); -1]

pd x pr: [f(x+1,y)-f(x,y); f(x,y+1)-f(x,y); -1]

 

Adding these four vectors and then normalizing them should yield your normal.

 

EDIT:

You can also just take the two vectors

u -> d: ud [x-x; (y+1)-(y-1); f(x,y+1)-f(x,y-1)] = [0; 2; f(x,y+1)-f(x,y-1)]

l -> r: lr [(x+1)-(x-1); y-y; f(x+1,y)-f(x-1,y)] = [2; 0; f(x+1,y)-f(x-1,y)]

And their crossproduct:

ud x lr = [2(f(x+1,y)-f(x-1,y)); 2(f(x,y+1)-f(x,y-1)); -4]

And normalize that. Doing so, yields a less accurate version but might be faster, since you only need to calculate one vector instead of four.

Edited May 7, 2017 by Ma-Shell

[SpiderPig]

Thanks for the reply Ma-Shell. I'm finding the code a little hard to translate for use in Leadwerks though.

 

I'm assuming these are meant to Vec3? The x and y are to be the coordinates and the z the height value?

 

Left: l [x-1; y; f(x-1, y)]
Right: r [x+1; y; f(x+1, y)]
Up: u [x; y-1; f(x, y-1)]
Down: d [x; y+1; f(x, y+1)]

 

 

Is this meant to be like this;

 

Vec3 Left = Vec3(1,0,height_value);
Vec3 Right = Vec3(0,1,height_value);
Vec3 Up = Vec3(0,1,height_value);
Vec3 Down = Vec3(0,1,height_value);

 

Thanks for you help.

[SpiderPig]

I've also noticed that the problem with my normal's are not entirely the way I'm calculating them. It seems that the lower mesh resolution toward the edges of the terrain are always going to look less detailed in lighting because they are less detailed in the mesh. i know the the terrain shipped with Leadwerks doesn't have lower resolution normal's in the lower detailed patches though, is there a technique for terrain normal's on different LOD patches that may help?

 

#edited

[Ma-Shell]

Yes, they are meant to be vec3.

Given, your method has the following inputs:

<code>unsigned int x, unsigned int y, float map[]</code>

When I wrote f(x,y), I meant map evaluated for the given coordinates, so they correspond to your center_X - variables. i.e.:

f(x,y) = map[current_index]

f(x-1,y) = center_l

f(x+1,y) = center_r

f(x,y-1) = center_u

f(x,y+1) = center_d

 

This means, you can calculate the left, right, up, down vectors as:

Vec3 Left = Vec3(x-1, y, center_l);
Vec3 Right = Vec3(x+1, y, center_r);
Vec3 Up = Vec3(x, y-1, center_u);
Vec3 Down = Vec3(x, y+1, center_d);

However, you don't need to define these, as you can see in my post, you can directly represent the results:

 

You would end up with:

Vec3 normal = Vec3(2*(center_r-center_l), 2*(center_d-center_u), -4).Normalize();

 

You can see, this actually ends up the same as what you wrote in your initial post (after it is normalized) only with y and z flipped, which is my fault for assuming, z was the height-coordinate.

 

So in conclusion: What you are doing in your initial post is exactly the result of the cross-product. If you actually DO use the cross-product instead of what you did there, you don't gain anything, but instead you only lose efficiency.

[Ma-Shell]

If you DO want to explicitly use the cross-product (which is less efficient), nick.ace's approach has two small errors in the initial vectors for tangent and bitangent (and it's OK to normalize after calculating the cross-product). It should be:

Vec3 tangent = Vec3(2.0, center_r - center_l, 0.0)
Vec3 bitangent = Vec3(0.0, center_d - center_u, 2.0)
Vec3 normal = cross(tangent, bitangent).Normalize()

[SpiderPig]

Thanks for the explanation it makes sense now. This is the code I use now for the normal;

 

Vec3 Normal = Vec3(2.0*(center_r-center_l),2.0*(center_d-center_u),-4.0).Normalize();

 

I must be doing something else wrong somewhere though. This image is with the code above;

 

 

And this image is with the command Surface->UpdateNormals()

 

 

You can see the difference, the later being the desired result.

 

I can see that the higher detailed mesh in the center of the terrain is pretty good in the first image as well as the second, but it's the lower detailed mesh that doesn't look great. Does the size of the LOD patches need to influence the length of the normal to get a softer transition?

 

Or perhaps it's because I'm pre-calculating all the normal's for the different LOD levels and storing each LOD level in an array of Vec3's. One Vec3 for each vertex (or pixel of the height-map).

 

This is the entire code for one 16 bit height-map;

 

unsigned int total_indices = map_size * map_size;
hills = (float*)malloc(total_indices * sizeof(float));
cFile* map = new cFile();
unsigned short* data_buffer = (unsigned short*)map->LoadBinary("Maps/Hills.r16", DATA_TYPE::UNSIGNED_SHORT);
for (int e = 0; e < total_indices; e++) { hills[e] = data_buffer[e] * 0.00390625; }
//this should be save as floats in a file

//MAKE NORMAL BUFFERS FOR EACH LOD LEVEL//////////////////////////////////////
int lod_levels = 7;
int _skip_value[7] = { 1,2,4,8,16,32,64 };

n_x = (float**)malloc(_start_lod * sizeof(float));
n_y = (float**)malloc(_start_lod * sizeof(float));
n_z = (float**)malloc(_start_lod * sizeof(float));
for (int n_index = 0; n_index < 7; n_index++)//_start_lod
{
//perhaps make each array only the size of the vertexes needed
int _lodsize = ((map_size - 1) / _skip_value[n_index]) + 1;
n_x[n_index] = (float*)malloc(_lodsize*_lodsize * sizeof(float));
n_y[n_index] = (float*)malloc(_lodsize*_lodsize * sizeof(float));
n_z[n_index] = (float*)malloc(_lodsize*_lodsize * sizeof(float));
unsigned int id = 0, map_index = 0, current_index = 0;
float center_l, center_r, center_u, center_d, center;
Vec3 normal_buffer;
//get the normals for each lod level?
//int skip_value = (map_size - 1) / _lodsize;
for (int y = 0; y < map_size; y += _skip_value[n_index])
{
for (int x = 0; x < map_size; x += _skip_value[n_index])
{
//if (x != 0 && x != map_size - 1 && y != 0 && y != map_size - 1)
//{
 //all the normals can be pre-calculated for speed increase
 //make a normal collection for each lod level
current_index = (y * map_size) + x;
center = HeightMaps->hills[current_index];
//HANDLE THE LEFT VERTEX//////////////////////////////////////////
if (x == 0) { center_l = center; }
else {
 map_index = (y * map_size) + (x - _skip_value[n_index]);
 center_l = HeightMaps->hills[map_index];
}
/////////////////////////////////////////////////////////////////
if(x == (map_size - 1)){ center_r = HeightMaps->hills[current_index]; }
else {
 map_index = (y * map_size) + (x + _skip_value[n_index]);
 center_r = HeightMaps->hills[map_index];
}
if (y == 0) { center_d = HeightMaps->hills[current_index]; }
else {
 map_index = ((y - _skip_value[n_index]) * map_size) + x;
 center_d = HeightMaps->hills[map_index];
}
if (y == (map_size - 1)) { center_u = HeightMaps->hills[current_index]; }
else {
 map_index = ((y + _skip_value[n_index]) * map_size) + x;
 center_u = HeightMaps->hills[map_index];
}

normal_buffer = Vec3(2.0*(center_r-center_l),2.0*(center_d-center_u),-4.0).Normalize();

n_x[n_index][id] = normal_buffer.x;
n_y[n_index][id] = normal_buffer.y;
n_z[n_index][id] = normal_buffer.z;
id++;
}
}
}

 

EDIT : I think I've found the issue. The problem was not setting the normal_buffer up to use the large distance between the vertices on the lower LOD levels. I used the following line and it looks good now;

 

normal_buffer = Vec3(center_r-center_l, center_d-center_u,-(_skip_value[n_index]*10.0)).Normalize();

 

Multiplying by 10 made it less dark.