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

Question

这是我的3D应用程序的导出器插件.我目前的解决方案工作正常,但速度非常慢(复杂度为O(n ^ 2*log n)).

它应该是一个函数,其中input是一个对象Verticle数组,并作为Verticle列表输出,没有重复和索引列表.

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

我的问题是,有没有办法在线性时间内完成,或者至少在我的解决方案中更快？非常感谢你.

Answer 1

您可以使用STL 中的 set 容器以 O(n log n) 的速度完成此操作。你基本上做的是：

1. 从空的对集（顶点、整数）、空的索引数组和索引 = 0 开始。
2. 对于每个顶点检查它是否在集合中。如果没有，则将一对（顶点，索引）添加到集合并增量索引中。否则，从集合中获取顶点的索引。在这两种情况下，都将顶点索引添加到索引缓冲区。
3. 最后，您获得索引缓冲区，并且集合中的顶点是顶点缓冲区。

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