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

Question

它适用于我的 3D 应用程序导出器插件。我当前的解决方案运行良好，但速度很慢（复杂度 O(n^2 * log n) ）。

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

此外，当两个顶点彼此非常非常接近时（例如，差异约为 0.001 ），算法会将其标记为重复。

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

Answer 1

您可以使用来自 STL 的 set container在 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;
}