如何优化我的 Soft Normal 计算函数？

Question

我需要为我的 OpenGL 应用程序生成软法线，但此函数的处理时间很荒谬。对其进行分析后，我的多图放置处理时间似乎高得离谱。我做了一些研究，发现您可以在 insertion/emplaces 上使用提示，但不知道如何实现它，或者即使我的方法是生成法线的最佳方法。如果您知道更好的方法或加速此代码段的方法，我很乐意听到。

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

该算法之所以如此缓慢，是因为该算法的运行时间是二次方 (O(n2))。实际上，您有一个嵌套循环，您可以在其中迭代所有顶点，并搜索每个面向相邻面的顶点。那可以简化。当你计算面法向量时，相邻顶点的面法向量可以在同一个循环中求和：

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;
    }
}

最后归一化Unit vector每个顶点的法线属性：

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

请注意，索引到其面的映射是多余的，甚至不需要面列表。

Answer 2

将每个面的法线收集到像 std::multimap 这样的专用结构中对于此任务没有必要。由于不需要将一个面与另一个面区分开来，而且法线是归一化向量 - 将每个三角形的法线直接累积到顶点数据中然后对其进行归一化会更简单、更直接。

复制 indicies 参数而不是通过引用传递它听起来既多余又昂贵。

glm::triangleNormal() 可能对计算的向量进行归一化，但对于这些计算，在这一步跳过三角形法线的归一化会更快（而且更好 - 较小的三角形对结果法线的影响更小）。

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);
  }

如何优化我的 Soft Normal 计算函数？

How can I optimize my Soft Normal calculation function?

c++

opengl

optimization

multimap

normals