# Calculating vertex normals on the GPU

I have some height-map sampled on a regular grid stored in an array. Now, I want to use the normals on the sampled vertices for some smoothing algorithm. The way I'm currently doing it is as follows:

1. For each vertex, generate triangles to all it's neighbours. This results in eight neighbours when using the 1-neighbourhood for all vertices except at the borders.

`````` +---+---+
¦ \ ¦ / ¦
+---o---+
¦ / ¦ \ ¦
+---+---+
``````
2. For each adjacent triangle, calculate it's normal by taking the cross product between the two distances.

3. As the triangles all have the same size when projected on the xy-plane, I simply average over all eight normals then and store it for this vertex.

However, as my data grows larger, this approach takes too much time and I would prefer doing it on the GPU in a shader code. Is there an easy method, maybe if I could store my height-map as a texture?

-
You want to smooth the normals of an already generated terrain, or you want to create the terrain from a height map? – Jonathan Connell Jun 22 '11 at 10:26
I want to get the normals for all my vertices, the heightmap is already there. – Etan Jun 22 '11 at 12:04
I don't quite understand the issue - where's the problem with taking the vertex that the vertex shaders gives you and calculating the normal in a straight forward manner? You could just apply that specific shader to whatever piece of geometry that you need it for. If you need the heightmap in the vertex shader, there are methods for texture fetching depending on what language you use (google should help you). – TravisG Jun 22 '11 at 12:21
Maybe you can simply use 4-connected pixels. This might result in similar results with half the performance hit. But if your heightmap is static your should consider a different approach: If it is static at compilation time: implement a pipeline extension, if it is static at runtime, use a onetime terrain generation algorithm. Vertex-displacement is only useful, when your heightmap changes during runtime, otherwise it is waste of GPU performance. – 0xBADF00D Sep 19 '13 at 6:39

You can use the slopes between vertices instead of the triangle normals to average the vertex normal. This could be easily ported to the GPU if you have vertex shader texture fetch support. Gottfried Chen sums it up here with code: http://www.flipcode.com/archives/Calculating_Vertex_Normals_for_Height_Maps.shtml

-

How big is your map? It could be that your grid sampling is blowing out the caches as it gets bigger, causing the sudden slow down. It could be that your loop needs optimizing. Also, how long is too long? Is your map static at run time? You said in passing that this is for smoothing and not rendering, how are you using this?

Eight normals is a little excessive, I think that you'd do fine with just four closest and ignoring the diagonals but suggest trying a before-and-after version to compare results. You could also march down the rows and carry forward results from the previous point to avoid some computation, it's an approximation but all lighting is an approximation.

If your map is static, pre-compute and save the data along with the map. If your map is generated at run time then embed the normal calculation into the generation code where you have all the data handy. If your map changes at run time then only recalculate the affected points.

-
The map is static, and is like 2000x2000 big. I want to tune the parameters of the smoothing algorithm with it and the normals of the 8 neighbours is just required for this. I'm wondering if it is possible to do such normal calculations on the gpu in the vertex shader, and `heishe`'s comment gave me quite a hint. Texture fetch in the vertex shader seems to be the best solution to do my normal calculation. – Etan Jun 22 '11 at 16:05
I suspect that the real work will be done in the pixel shader, but the idea of using a floating point texture as input is great. You may want to take a look at OpenCL, which is a standard for GPU computing that might make your job easier: khronos.org/opencl – Patrick Hughes Jun 22 '11 at 16:48