How can i generate indices from vertex list in linear time?

Question

It's for my exporter plugin for 3D applications. My current solution is working fine, but it's very slow ( complexity O(n^2 * log n ) ).

It should be a function, where input is an array of object verticles and output as a list of verticles without duplications and index list.

Also, when two vertices are very very very close to each other ( let's say, diff about 0.001 ), algorithm will mark it as duplication.

My question is, is there a way to do it in linear time, or at least faster then in my solution ? Thank you very much.

Answer 1

You can do it in O(n log n) using set container from STL. What you basically do is:

1. Start with empty set of pairs (vertex, integer), empty array of indices and index = 0.
2. For each vertex check if it's in the set. If not, add a pair (vertex, index) to the set and increment index. Otherwise, get the index of the vertex from the set. In both cases add the index of the vertex to the index buffer.
3. Finally, you obtain the index buffer and the vertices in the set are the vertex buffer.

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