Pseudocode for calculating per vertex normals for a trianglestrip mesh

Question

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

Answer 1

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