# Pseudocode for calculating per vertex normals for a trianglestrip mesh

I have a terrain that is defined as a trianglestrip mesh. Now I'm trying to calculate the normals of each vertex but I've realised that my normal way of calculating vertex normals only works with triangle meshes. I'm finding it hard to wrap around my head how to get the triangles from trianglestrip to calculate the normal in code. I can imagine it but just can't understand how that translates into code.

Can someone help me with some pseudocode or anything of that matter that demonstrates how I could cycle an array that contains indices used in a trianglestrip to calculate the normals?

EDIT:

I ended up finding this answer on stackoverflow and it looked like a very efficient and easy way to generate normals from a heightmap: https://stackoverflow.com/questions/49640250/calculate-normals-from-heightmap/49640606?noredirect=1#

The question defines the point and it's neighbours as follows for clarity. O being the vertex we're calculating a normal for:

  T
L O R
B


Having translated it to my own cordinate system (right handed because of opengl), I ended up with the calculation of a normal of a vertex as:

Vec3 normal = Normalize(Vec3((R-L)/2, 1.0f, (B-T)/2));


I implemented that. Here's the constructor for a terrain in my code (fair warning, I am writing my own engine with its own math library. You should be able to infer the meanings of some things by their names though):

Terrain :: Terrain(unsigned int size)
{
unsigned int xSegments = size;
unsigned int ySegments = size;

srand(time(NULL));
m_NoiseMap = CreateScope<NoiseMap>(xSegments + 1, ySegments + 1);
m_NoiseMap->GenerateNoise(rand() % 9999, 25, 0.015, 0.52, Vec2(0.4), 4);

float dX = (float)size  / xSegments;
float dY = (float)size / ySegments;

auto heightMap = *m_NoiseMap;

for (unsigned int y = 0; y <= ySegments; ++y)
{
for (unsigned int x = 0; x <= xSegments; ++x)
{
auto height = heightMap[x][y];
auto position = Vec3(dX * x * 2.0f - 1.0f, height, dY * y * 2.0f - 1.0f);

Positions.push_back(position);
UV.push_back(Vec2(dX * x, 1.0f - y * dY));

float heightR, heightL, heightU, heightD = height;

if (y > 0)
heightU = heightMap[x][y - 1];

if (x > 0)
heightL = heightMap[x - 1][y];

if ( y < ySegments)
heightD = heightMap[x][y + 1];

if (x < xSegments)
heightR = heightMap[x + 1][y];

Normals.push_back(Normalize(Vec3((heightR - heightL)  / 2, 1.0f, (heightD - heightU) / 2)));
}
}

bool oddRow = false;

for (int y = 0; y < ySegments; ++y)
{
if (!oddRow)
{
for (int x = 0; x <= xSegments; ++x)
{
Indices.push_back(y       * (xSegments + 1) + x);
Indices.push_back((y + 1) * (xSegments + 1) + x);
}
}
else
{
for (int x = xSegments; x >= 0; --x)
{
Indices.push_back((y + 1) * (xSegments + 1) + x);
Indices.push_back(y       * (xSegments + 1) + x);
}
}
oddRow = !oddRow;
}

Topology = TRIANGLE_STRIP;
Finalize();
}


Unfortunately, when I do this, I get this as the result once I'm done lighting the mesh:

Which just looks random if you ask me. I've set the normal to be flat in the shader as I'm trying to make low poly terrain and do not need smooth shading. Anyone have any clues where I'm going wrong?

Thank you

• For a terrain, we'd usually calculate the normals from the terrain's height map. Do you have access to that in this part of your code? – DMGregory Apr 23 '20 at 18:45
• @DMGregory Yes, I do. I have a height map class that holds the height map as an array of floats. – Sammi3 Apr 23 '20 at 19:05
• Great. Now imagine the height at your vertex position, and the heights of the 4 positions around it in a +, form 4 triangles meeting at that point. Now you can compute a normal for each triangle and average them to get a vertex normal in the way you're used to. Does that get you enough to write up your solution as an answer? – DMGregory Apr 23 '20 at 19:21
• Yes, that actually made perfect sense and gave me insight into how I would do it with a triangle strip. Still will do it this way because it's less of a hassle. Thanks! – Sammi3 Apr 23 '20 at 20:30
• If you've solved your problem, please feel free to document it in an Answer below. This can help other users with similar questions, and earn you some upvote rep too. :) – DMGregory Apr 23 '20 at 21:14

After coming across this resource: http://www.videotutorialsrock.com/opengl_tutorial/terrain/home.php and reading the comment from DMGregory, I decided to get the cross products in each triangle surrounding the vertex on the heightmap. The code for generating the normals looks as follows:

Vec3 sum(0.0f, 0.0f, 0.0f);

Vec3 out;
if (y > 0)
out = Vec3(0.0f, heightMap[x][y - 1] - heightMap[x][y], -1.0f);

Vec3 in;
if (y < ySegments - 1)
in = Vec3(0.0f, heightMap[x][y + 1] - heightMap[x][y], 1.0f);

Vec3 left;
if (x > 0)
left = Vec3(-1.0f, heightMap[x - 1][y] - heightMap[x][y], 0.0f);

Vec3 right;
if (x < xSegments - 1)
right = Vec3(1.0f, heightMap[x + 1][y] - heightMap[x][y], 0.0f);

if (x > 0 && y > 0)
sum += Normalize(Cross(out, left));

if (x > 0 && y < ySegments - 1)
sum += Normalize(Cross(left, in));

if (x < xSegments - 1 && y < ySegments - 1)
sum += Normalize(Cross(in, right));

if (x < xSegments - 1 && y > 0)
sum += Normalize(Cross(right, out));

tempNormals.push_back(sum);


After storing the normals in a temporary vector, I smoothed the normals like this to get nicer edges:

Normals.resize(tempNormals.size(), Vec3(0.0f, 1.0f, 0.0f));

const float FALLOUT_RATIO = 0.5f;

for (unsigned int y = 0; y <= height; y++)
{
for (unsigned int x = 0; x <= width; x++)
{
Vec3 sum = tempNormals[(y * width) + x];

if (x > 0)
sum += tempNormals[(y * width) + (x - 1)] * FALLOUT_RATIO;

if (x < xSegments - 1)
sum += tempNormals[(y * width) + x + 1] * FALLOUT_RATIO;

if (y > 0)
sum += tempNormals[((y - 1) * width) + x] * FALLOUT_RATIO;

if (y < ySegments - 1)
sum += tempNormals[((y + 1) * width) + x] * FALLOUT_RATIO;

auto magnitude = sqrt(pow(sum.x, 2) + pow(sum.y, 2) + pow(sum.z, 2));

if (magnitude == 0)
sum = Vec3(0.0f, 1.0f, 0.0f);

Normals[(y * width) + x] = sum;
}
}


Results:

DISCLAIMER: While I did manage to get it done using the finite difference method, it didn't look good on low poly meshes. Using the cross product of each triangle yielded much more accurate results