[Solved] Calculating normal vectors

Hello JGO,

I’ve been trying to solve this problem for several days, and can’t come with a working solution. Perhaps my math knowledge is lacking. Does anyone know how to calculate the normal vectors for a heightmap or a random terrain?

This is what I got now:


		float[] vdata = new float[(width-1) * height * 6]; // The vertex data for the heightmap.
		int i = 0;
		for (int z = 0; z < data.length - 1; z++) {
			for (int x = 0; x < data[z].length; x++) {
				// Take a vertex from the current strip
				vdata[i++] = x;
				vdata[i++] = data[z][x];
				vdata[i++] = z;
				// Take a vertex from the next strip
				vdata[i++] = x;
				vdata[i++] = data[z + 1][x];
				vdata[i++] = z + 1;
			}
			z++;
			if(z < data.length - 1) {
				for (int x = data[z].length - 1; x >= 0; x--) {
					// Take a vertex from the current strip
					vdata[i++] = x;
					vdata[i++] = data[z][x];
					vdata[i++] = z;
					// Take a vertex from the next strip
					vdata[i++] = x;
					vdata[i++] = data[z + 1][x];
					vdata[i++] = z + 1;
				}
			}
		}
		
		float[] ndata = new float[vdata.length]; // The normal data for the heightmap
		i = 0;
		for(int n = 0; n < vdata.length/3; n++) {
			Vector3f v0 = new Vector3f(vdata[n], vdata[n+1], vdata[n+2]);
			Vector3f v1;
			if(n < vdata.length - 5) { // Prevent IndexOutOfBoundsException
				v1 = new Vector3f(vdata[n+3], vdata[n+4], vdata[n+5]);
			} else {
				v1 = v0;
			}
			Vector3f v2;
			if(n < vdata.length - 8) { // Prevent IndexOutOfBoundsException
				v2 = new Vector3f(vdata[n+6], vdata[n+7], vdata[n+8]);
			} else {
				v2 = v0;
			}

			Vector3f dv1 = Vector3f.sub(v1, v0, new Vector3f());
			Vector3f dv2 = Vector3f.sub(v2, v0, new Vector3f());
			Vector3f nv = Vector3f.cross(dv1, dv2, new Vector3f());
			
			ndata[i++] = nv.x;
			ndata[i++] = nv.y;
			ndata[i++] = nv.z;
		}
		
		setVertexData(vdata);
		setNormalData(ndata);
		setDrawType(GL_TRIANGLE_STRIP);

But the normals are totally wrong, as you can see in the image:

There will be a single normal for each face. Since our faces are triangles, we need three vectors for three vertices.


Vector3f v0;
Vector3f v1;
Vector3f v2;

Then we need the sides of the triangle. This can be achieved by simply subtracting them.


Vector3f s1 = Vector3f.sub(v1, v0, null);
Vector3f s2 = Vector3f.sub(v2, v0, null);

Now, the normal for all those vertices will be the cross product of the sides.


Vector3f n = Vector3f.cross(s1, s2, null);

Now, we have to calculate the normals for all the vertices in the [icode]vdata[][/icode] array. Keep in mind that all the faces will be connected.


for (i=0; i<vdata.length; i+=9)
{
    // Grab the vertices
    Vector3f v0 = new Vector3f(vdata[i], vdata[i+1], vdata[i+2]);
    Vector3f v1 = new Vector3f(vdata[i+3], vdata[i+4], vdata[i+5]);
    Vector3f v2 = new Vector3f(vdata[i+6], vdata[i+7], vdata[i+8]);

    // Calculate the normal
    Vector3f n = calcNormal(v0, v1, v2);

    // Add to ndata three times (for three vertices)
    for (int j=0; j<3; j++)
    {
        ndata[i+j] = n.x;
        ndata[i+j+1] = n.y;
        ndata[i+j+2] = n.z;
    }
}

And that should correct the normals. Hope this helps.

Thank you for your reply SHC,

Here is the new code:


		float[] vdata = new float[(width - 1) * height * 6];
		int i = 0;
		for (int z = 0; z < data.length - 1; z++) {
			for (int x = 0; x < data[z].length; x++) {
				// Take a vertex from the current strip
				vdata[i++] = x;
				vdata[i++] = data[z][x];
				vdata[i++] = z;
				// Take a vertex from the next strip
				vdata[i++] = x;
				vdata[i++] = data[z + 1][x];
				vdata[i++] = z + 1;
			}
			z++;
			if (z < data.length - 1) {
				for (int x = data[z].length - 1; x >= 0; x--) {
					// Take a vertex from the current strip
					vdata[i++] = x;
					vdata[i++] = data[z][x];
					vdata[i++] = z;
					// Take a vertex from the next strip
					vdata[i++] = x;
					vdata[i++] = data[z + 1][x];
					vdata[i++] = z + 1;
				}
			}
		}

		float[] ndata = new float[vdata.length];
		for (i = 0; i < vdata.length - 9; i += 9) {
			// Grab the vertices
			Vector3f v0 = new Vector3f(vdata[i], vdata[i + 1], vdata[i + 2]);
			Vector3f v1 = new Vector3f(vdata[i + 3], vdata[i + 4], vdata[i + 5]);
			Vector3f v2 = new Vector3f(vdata[i + 6], vdata[i + 7], vdata[i + 8]);

			// Calculate the normal
			Vector3f n = calcNormal(v0, v1, v2);

			// Add to ndata three times (for three vertices)
			for (int j = 0; j < 3; j++) {
				ndata[i + j] = n.x;
				ndata[i + j + 1] = n.y;
				ndata[i + j + 2] = n.z;
			}
		}

		setVertexData(vdata);
		setNormalData(ndata);
		setDrawType(GL_TRIANGLE_STRIP);
	}
	
	private Vector3f calcNormal(Vector3f v0, Vector3f v1, Vector3f v2) {
		Vector3f s1 = Vector3f.sub(v1, v0, null);
		Vector3f s2 = Vector3f.sub(v2, v0, null);
		return Vector3f.cross(s1, s2, null);
	}

And the new result is:

As you can see, it still isn’t the way it should be. Anyone can discover a mistake I’ve made, because I can’t find it :clue:?

Try normalizing the normal. I forgot that.

Didn’t make any difference:


	private Vector3f calcNormal(Vector3f v0, Vector3f v1, Vector3f v2) {
		Vector3f s1 = Vector3f.sub(v1, v0, null);
		Vector3f s2 = Vector3f.sub(v2, v0, null);
		Vector3f nv = Vector3f.cross(s1, s2, null);
		float length = (float) Math.sqrt(nv.x * nv.x + nv.y * nv.y + nv.z * nv.z);
		nv.x /= length;
		nv.y /= length;
		nv.z /= length;
		return nv;
	}

I think the problem is the triangle strip. Can you generate them as triangles instead? This is because normals change per face and every two faces share two vertices. Vertices can be shared but normals cannot be shared.

It is possible to do it with triangle strips, and I tried this lighthouse3d tutorial, but still can’t find how to implement this.

I have some working code for heightmap terrain normals, as seen in this video: https://www.youtube.com/watch?v=lt9kYDb9p78


	private void calculateVertexNormals() {
		for (int z = 0; z < vertexInfos.length; z++) {
			for (int x = 0; x < vertexInfos[z].length; x++) {
				MeshPartBuilder.VertexInfo vert = vertexInfos[z][x];
				// calculate normals
				vert.setNor(calculateNormalForVertex(z, x));
			}
		}
	}

and:


	/** Return vertex normal based on average of surrounding triangle face normals
              parameters z and x are heightmap coordinates*/
	private Vector3 calculateNormalForVertex(int z, int x) {
		tmp.set(0f, 0f, 0f);
		Triangle[] neighbors = getTrianglesNeighboringVertex(z, x);
		int triCount = 0;
		for (int i = 0; i < neighbors.length; i++) {
			Triangle tri = neighbors[i];
			if (tri != null) { // edge of the map will not have a full list of triangles
				triCount++;
				tmp.add(tri.faceNormal);
			}
		}
		tmp.scl(1f / triCount); // divide the total by the count to get the average
		return tmp;
	}

and here is how I get the neighbors:
also see this: http://stackoverflow.com/questions/6656358/calculating-normals-in-a-triangle-mesh


        private Triangle[] neighborStorage = new Triangle[4];  // we are interested in 4 specific neighbors

	private Triangle[] getTrianglesNeighboringVertex(int baseZ, int baseX) {
		Triangle[] neighbors = neighborStorage;
		// base triangle index
		int x = baseX * 2;
		int z = baseZ;
		int maxZ = tris.length - 1;
		int maxX = tris[0].length - 1;
		int slot = 0;
		// bottom row
		for (int i = -1; i <= 0; i++) {
			x--;
			if (z < 0 || x < 0 || z > maxZ || x > maxX) {
				neighbors[slot++] = null;
			} else {
				neighbors[slot++] = tris[z][x];
			}
		}
		// top row
		z -= 1;
		for (int i = -1; i <= 0; i++) {
			x = baseX - i;
			if (z < 0 || x < 0 || z > maxZ || x > maxX) {
				neighbors[slot++] = null;
			} else {
				neighbors[slot++] = tris[z][x];
			}
		}
		return neighbors;
	}

Thank you for your replies, combining all reactions got it working. I still use triangle strips and have a normal per vertex. ;D

Congratulations.

a good way to calculate the normal from a height map, is to use the sobel filter on the height data.

I’m adding tangent and bitangent calculation to my code, but am not sure wether it is correct or not, could anyone check it?


	private Vector3f[] calcNormals(int x1, int z1, int x2, int z2, int x3, int z3, int uvx1, int uvy1, int uvx2, int uvy2, int uvx3, int uvy3) {
		Vector3f v1 = new Vector3f(), v2 = new Vector3f(); // delta vectors

		v1.x = (x2 - x1);
		v1.y = -data[z1][x1] + data[z2][x2];
		v1.z = (z2 - z1);

		v2.x = (x3 - x1);
		v2.y = -data[z1][x1] + data[z3][x3];
		v2.z = (z3 - z1);
		
		Vector3f normal = Vector3f.cross(v1, v2, null); // this is correct
		
		Vector2f uv1 = new Vector2f(), uv2 = new Vector2f(); // delta UVs
		// Is the following correct?

		uv1.x = (uvx2 - uvx1);
		uv1.y = (uvy2 - uvy1);

		uv2.x = (uvx3 - uvx1);
		uv2.y = (uvy3 - uvy1);

		float r = 1f / (uv1.x * uv2.y - uv1.y * uv2.x);
		Vector3f tangent = new Vector3f(v1.x * uv2.y - v2.x * uv1.y * r, v1.y * uv2.y - v2.y * uv1.y * r, v1.z * uv2.y - v2.z * uv1.y * r);
		Vector3f bitangent = new Vector3f(v2.x * uv1.x - v1.x * uv2.x * r, v2.y * uv1.x - v1.y * uv2.x * r, v2.z * uv1.x - v1.z * uv2.x * r);

		return new Vector3f[] {normal, tangent, bitangent};
	}

Anybody, I can’t find where it goes wrong, so would like to know wether this is wrong or something else. :frowning:

The code for your normal looks like the code I use to derive my bitangent/binormal.

Anyway have you tried normalizing your normal and tangent?

When I call the [icode]calcNormals{…};[/icode] for every triangle I normalize the results.

Yeah, but did you re-normalize before you calculated the binormal/bitangent? Your latest post w/code says no.

Anyway, it looks wrong to me, but you’re calculating edge normals, correct? I did face normals and then averaged them together. So you could be doing it right, but I’m not sure on the math.

Basically what you should be doing is getting the normal and normalizing it. (normal)

Then you can grab a perpendicular vector that passes through the normal, normalize that. (tangent)

Then you cross the normal and tangent together for the binormal. Sorry I couldn’t be of more help :frowning:

Thanks for your reply. When I use [icode]Vector3f.angle(normal, tangent);[/icode] and turn it into degrees it is always 90. I think that is what you mean by “grab a perpendicular vector”.

I will try to replace my bitangent with the cross product of the normal and tangent.

Yeah that should mean that you’re getting a perpendicular vector to the normal. Good luck! Maybe someone else with better math skills will come along soon…

Just to explain the problem a bit more:

I’m trying to add bump mapping to my (idk what I should call it, it isn’t actually a game yet) thing, and I get the following weird result:

A closer look:

Some things changed with normal/tangent calculation (this is for every triangle):


	private Vector3f[] calcNormals(int x1, int z1, int x2, int z2, int x3, int z3, float uvx1, float uvy1, float uvx2, float uvy2, float uvx3, float uvy3) {
		
		Vector3f v1 = new Vector3f(), v2 = new Vector3f();

		v1.x = (x2 - x1);
		v1.y = -data[z1][x1] + data[z2][x2];
		v1.z = (z2 - z1);

		v2.x = (x3 - x1);
		v2.y = -data[z1][x1] + data[z3][x3];
		v2.z = (z3 - z1);
		
		Vector3f normal = Vector3f.cross(v1, v2, null);
		normal.normalise();
		
		Vector2f uv1 = new Vector2f(), uv2 = new Vector2f();

		uv1.x = (uvx2 - uvx1);
		uv1.y = (uvy2 - uvy1);

		uv2.x = (uvx3 - uvx1);
		uv2.y = (uvy3 - uvy1);

		float r = 1f / (uv1.x * uv2.y - uv1.y * uv2.x);
		Vector3f tangent = new Vector3f(v1.x * uv2.y - v2.x * uv1.y * r, v1.y * uv2.y - v2.y * uv1.y * r, v1.z * uv2.y - v2.z * uv1.y * r);
		tangent.normalise();
		Vector3f bitangent = Vector3f.cross(normal, tangent, null);
		bitangent.normalise();

		return new Vector3f[] {normal, tangent, bitangent};
	}

Vertex shader (yes I have to change the names here :D):


#version 330

layout(location = 0)in vec3 vertex;
layout(location = 1)in vec3 normal;
layout(location = 2)in vec3 color;
layout(location = 3)in vec2 texCoord;
layout(location = 4)in vec3 tangent;
layout(location = 5)in vec3 bitangent;

layout(location = 0)out vec3 Position;
layout(location = 1)out vec2 TexCoord;

out vec3 EyeDirection_cameraspace;
out vec3 LightDirection_cameraspace;

out vec3 LightDirection_tangentspace;
out vec3 EyeDirection_tangentspace;

uniform mat4 ModelMatrix;
uniform mat4 ViewMatrix;
uniform mat4 ProjectionMatrix;

void main( void )
{
	mat4 MVP = ProjectionMatrix * ViewMatrix * ModelMatrix;
	
	gl_Position = MVP * vec4(vertex, 1.0f);
	TexCoord = texCoord;
	vec3 Normal = normalize(gl_NormalMatrix * normal);
	Position = (ModelMatrix * vec4(vertex, 1.0f)).xyz;
	
	vec3 LightPosition_worldspace = vec3(64, 20, 64); // Just a pre-set location for testing
	
	// Vector that goes from the vertex to the camera, in camera space.
	// In camera space, the camera is at the origin (0,0,0).
	vec3 vertexPosition_cameraspace = (ViewMatrix * ModelMatrix * vec4(vertex, 1.0f)).xyz;
	EyeDirection_cameraspace = vec3(0.0f) - vertexPosition_cameraspace;

	// Vector that goes from the vertex to the light, in camera space. M is ommited because it's identity.
	vec3 LightPosition_cameraspace = (ViewMatrix * vec4(LightPosition_worldspace, 1.0f)).xyz;
	LightDirection_cameraspace = LightPosition_cameraspace + EyeDirection_cameraspace;
	
	// model to camera = ModelView
	mat3 MV3x3 = mat3(ViewMatrix * ModelMatrix);
	vec3 vertexTangent_cameraspace = MV3x3 * tangent;
	vec3 vertexBitangent_cameraspace = MV3x3 * bitangent;
	vec3 vertexNormal_cameraspace = MV3x3 * Normal;
	
	mat3 TBN = transpose(mat3(
		vertexTangent_cameraspace,
		vertexBitangent_cameraspace,
		vertexNormal_cameraspace	
	));

	LightDirection_tangentspace = TBN * LightDirection_cameraspace;
	EyeDirection_tangentspace =  TBN * EyeDirection_cameraspace;
}

Fragment shader:


#version 330

layout(location = 0)in vec3	position;
layout(location = 1)in vec2 texCoord;

in vec3 EyeDirection_cameraspace;
in vec3 LightDirection_cameraspace;

in vec3 LightDirection_tangentspace;
in vec3 EyeDirection_tangentspace;

layout(location = 0)out vec4 Color;

uniform sampler2D diffuseMap;
uniform sampler2D normalMap;
uniform vec3 cameraPosition;

void main( void )
{
	vec3 LightPosition_worldspace = vec3(64, 20, 64); // Just a pre-set location for testing
	
	// Light emission properties
	// You probably want to put them as uniforms
	vec3 LightColor = vec3(1,1,1);
	float LightPower = 400.0;
	
	// Material properties
	float Shininess = 0.3f;
	vec3 MaterialDiffuseColor = texture2D(diffuseMap, texCoord).rgb;
	vec3 MaterialAmbientColor = vec3(0.1,0.1,0.1) * MaterialDiffuseColor;
	vec3 MaterialSpecularColor = vec3(1.0f) * Shininess;//texture2D( SpecularTextureSampler, texCoord ).rgb * Shininess;

	vec3 TextureNormal_tangentspace = normalize(texture2D( normalMap, texCoord).rgb * 2.0 - 1.0);
	
	// Distance to the light
	float distance = length( LightPosition_worldspace - position );

	// Normal of the computed fragment, in camera space
	vec3 n = TextureNormal_tangentspace;
	// Direction of the light (from the fragment to the light)
	vec3 l = normalize(LightDirection_tangentspace);
	// Cosine of the angle between the normal and the light direction, 
	// clamped above 0
	//  - light is at the vertical of the triangle -> 1
	//  - light is perpendicular to the triangle -> 0
	//  - light is behind the triangle -> 0
	float cosTheta = clamp( dot( n,l ), 0,1 );

	// Eye vector (towards the camera)
	vec3 E = normalize(EyeDirection_tangentspace);
	// Direction in which the triangle reflects the light
	vec3 R = reflect(-l,n);
	// Cosine of the angle between the Eye vector and the Reflect vector,
	// clamped to 0
	//  - Looking into the reflection -> 1
	//  - Looking elsewhere -> < 1
	float cosAlpha = clamp( dot( E,R ), 0,1 );
	
	Color = vec4(
		// Ambient : simulates indirect lighting
		MaterialAmbientColor +
		// Diffuse : "color" of the object
		MaterialDiffuseColor * LightColor * LightPower * cosTheta / (distance*distance) +
		// Specular : reflective highlight, like a mirror
		MaterialSpecularColor * LightColor * LightPower * pow(cosAlpha,5) / (distance*distance), 1.0f);
}

When you move your camera do the tiles flip from being correct to incorrect and vice versa?

If so, then it is most likely problem within your shader.
If not, then it’s still how you are calculating the normals/tangent/binormal.

You’re tangent still looks suspect to me. An easy way to calculate a perpendicular vector is to inverse the slope of the normal, you can do this easily by inverting the normal’s x value and then swapping the x and y

something like this: tangent = n_normal.y, -n_normal.x, n_normal.z

However, I could be wrong, basically I don’t know what this is doing:

uv1.x = (uvx2 - uvx1);
      uv1.y = (uvy2 - uvy1);

      uv2.x = (uvx3 - uvx1);
      uv2.y = (uvy3 - uvy1);

      float r = 1f / (uv1.x * uv2.y - uv1.y * uv2.x);

If you could tell me what you are doing there I might be able to help some more.