How can I optimize my Soft Normal calculation function?

Question

I need to generate soft normals for my OpenGL application, but the processing time on this function is absurd. After profiling it, it seems that my multimap emplace processing times are absurdly high. I did some research and found out you can use hints on insertion/emplaces but don't know how to implement it or even if my method is the best way of generating normals. If you know of a better method or a way to speed up this code segment I would love to hear it.

void Controller::TerrainFactory::GenerateNormals(std::vector<Blue::Vertex> &verticies,
                                             std::vector<unsigned int> indicies) {
std::vector<Blue::Faces> faces;
std::multimap<unsigned int, size_t> setFaces;

for (size_t index = 0; index < indicies.size(); index += 3) {
    faces.push_back(Blue::Faces{});
    auto &face       = faces.at(faces.size() - 1);
    face.indicies[0] = indicies.at(index);
    face.indicies[1] = indicies.at(index + 1);
    face.indicies[2] = indicies.at(index + 2);
    face.normal      = glm::triangleNormal(verticies.at(face.indicies[0]).position,
                                      verticies.at(face.indicies[1]).position,
                                      verticies.at(face.indicies[2]).position);
    const auto size  = faces.size() - 1;
    setFaces.emplace(face.indicies[0], size);
    setFaces.emplace(face.indicies[1], size);
    setFaces.emplace(face.indicies[2], size);
}

for (unsigned index = 0; index < verticies.size(); ++index) {
    int count      = 0;
    auto itr1      = setFaces.lower_bound(index);
    auto itr2      = setFaces.upper_bound(index);
    auto avgNormal = glm::vec3{};
    while (itr1 != itr2) {
        if (itr1->first == index) {
            avgNormal += faces.at(itr1->second).normal;
            ++count;
        }
        ++itr1;
    }
    verticies.at(index).normals = avgNormal / static_cast<float>(count);
}


struct Vertex {
    glm::vec3 position = {};
    glm::vec2 texCoords = {};
    glm::vec3 normals = {};
};

struct Faces {
    unsigned int indicies[3] = {};
    glm::vec3 normal = {};
};

Answer 1

Collecting per-face normals into dedicated structures like std::multimap are not necessary for this task. As there is no need to distinguish one face from another and normals are normalized vectors - it is simpler and more straightforward accumulating per-triangle normals directly into vertex data and then normalize it.

Copying indicies parameter instead of passing it by reference also sound redundant and expensive.

glm::triangleNormal() probably normalizes computed vector, but for these calculation it is faster (and better - smaller triangles will have smaller impact on result normal) to skip normalization of triangle normal at this step.

void Controller::TerrainFactory::GenerateNormals(std::vector<Blue::Vertex>& verticies,
                                                 const std::vector<unsigned int>& indicies)
{
  // first loop could be skipped, if verticies[i].normals were no spoiled before
  for (size_t vert = 0; vert < verticies.size(); ++vert)
  {
    verticies[vert].normals = glm::vec3();
  }

  // append triangle normals to every vertex
  for (size_t index = 0; index < indicies.size(); index += 3)
  {
    Blue::Vertex& vert1 = verticies[indicies[index]];
    Blue::Vertex& vert2 = verticies[indicies[index + 1]];
    Blue::Vertex& vert3 = verticies[indicies[index + 2]];
    // glm::triangleNormal() probably returns normalized vector,
    // which is better to compute unnormalized
    glm::vec3 triNormal = glm::triangleNormal(vert1.position,
                                              vert2.position,
                                              vert3.position);
    vert1.normals += triNormal;
    vert2.normals += triNormal;
    vert3.normals += triNormal;
  }

  // normalize normal vectors
  for (size_t vert = 0; vert < verticies.size(); ++vert)
  {
    Blue::Vertex& vertBlue = verticies[vert];
    vertBlue.normals = glm::normalize(vertBlue.normals);
  }