3d - 如何在线性时间内从顶点列表生成索引？

Question

它适用于我的 3D 应用程序导出器插件。我目前的解决方案工作正常，但速度很慢(复杂度 O(n^2 * log n) )。

它应该是一个函数，其中输入是一个对象顶点数组，输出为一个没有重复的顶点列表和索引列表。

此外，当两个顶点彼此非常接近时(假设差异约为 0.001 )，算法会将其标记为重复。

我的问题是，有没有办法在线性时间内做到这一点，或者至少比我的解决方案更快？
非常感谢。

Answer 1

您可以使用 set container from STL 在 O(n log n) 中完成它.你基本上做的是:

从空对集(顶点、整数)、空索引数组和索引 = 0 开始。

对于每个顶点检查它是否在集合中。如果没有，则向集合中添加一对(顶点，索引)并增加索引。否则，从集合中获取顶点的索引。在这两种情况下，都将顶点的索引添加到索引缓冲区。

最后，您获得索引缓冲区，集合中的顶点就是顶点缓冲区。

在 C++ 中的实现:

#include<set>
#include<vector>
#include<cmath>
using namespace std;

struct Vertex
{
    float x, y, z;
};

typedef pair<Vertex, int> VPair;

float eps = 0.001;

struct CmpClass // class comparing vertices in the set
{
    bool operator() (const VPair& p1, const VPair& p2) const
    {
        if (fabs(p1.first.x-p2.first.x) > eps) return p1.first.x < p2.first.x;
        if (fabs(p1.first.y-p2.first.y) > eps) return p1.first.y < p2.first.y;
        if (fabs(p1.first.z-p2.first.z) > eps) return p1.first.z < p2.first.z;
        return false;
    }
};

vector<Vertex> input, vbuffer;
set<VPair, CmpClass> vertices;
vector<int> indices;
int index = 0;

void ComputeBuffers()
{
    for (int i=0; i<input.size(); i++)
    {
        set<VPair>::iterator it = vertices.find(make_pair(input[i], 0/*this value doesn't matter*/));
        if (it!=vertices.end()) indices.push_back(it->second);
        else
        {
            vertices.insert(make_pair(input[i], index));
            indices.push_back(index++);
        }
    }

    // Notice that the vertices in the set are not sorted by the index
    // so you'll have to rearrange them like this:
    vbuffer.resize(vertices.size());
    for (set<VPair>::iterator it=vertices.begin(); it!=vertices.end(); it++)
        vbuffer[it->second] = it->first;
}