How can I generate indexes from a list of vertices in linear time?

Question

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

This should be a function in which the input is an array of object vertices and displayed as a list of vertices without duplication and an index list.

In addition, when two vertices are very very close to each other (let's say diff is about 0.001), the algorithm will mark this as duplication.

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

Answer 1

You can do this in O (n log n) using install container from STL . Basically you do:

• Start with an empty set of pairs (vertex, integer), an empty array of indices, and index = 0.
• For each vertex, check if it is part of 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 vertex index to the index buffer.
• Finally, you get 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; }