1

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 = {};
};
Rabbid76
  • 202,892
  • 27
  • 131
  • 174
Arkwolf
  • 37
  • 3

2 Answers2

2

The algorithm is so slow, because the runtime of the algorithm quadratic (O(n2)). Actually you have a nested loop, where you iterate all the vertices and and search for each vertex the faces the adjacent faces. That can be simplified. When you compute the face normal vectors, then the face normal vectors of the adjacent vertices can be summed up in the same loop:

for (size_t i = 0; i < indicies.size(); i += 3)
{
    // compute face normal
    glm::vec3 faceNormal = glm::triangleNormal(
      verticies[indicies[i]].position,
      verticies[indicies[i+1]].position,
      verticies[indicies[i+2]].position);

    // add face normal to each of the 3 vertex normal of the face
    for (int j = 0; j < 3; ++j)
    {
      verticies[indicies[i+j]].normals += faceNormal;
    }
}

Finally normalize Unit vector the normal attribute of each vertex:

for (auto &vertex : verticies)
{
  vertex.normals = glm::normalize(vertex.normals);
}

Note, the mapping of the indices to its faces is superfluous, even the list of faces is unnecessary.

Rabbid76
  • 202,892
  • 27
  • 131
  • 174
2

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);
  }
gkv311
  • 2,612
  • 1
  • 10
  • 11