Find unique vertices from a 'triangle-soup'
- by sum1stolemyname
I am building a CAD-file converter on top of two libraries (Opencascade and DWF Toolkit).
However, my question is plattform agnostic:
Given:
I have generated a mesh as a list of triangular faces form a model constructed through my application. Each Triangle is defined through three vertexes, which consist of three floats (x, y & z coordinate). Since the triangles form a mesh, most of the vertices are shared by more then one triangle.
Goal:
I need to find the list of unique vertices, and to generate an array of faces consisting of tuples of three indices in this list.
What i want to do is this:
//step 1: build a list of unique vertices
for each triangle
for each vertex in triangle
if not vertex in listOfVertices
Add vertex to listOfVertices
//step 2: build a list of faces
for each triangle
for each vertex in triangle
Get Vertex Index From listOfvertices
AddToMap(vertex Index, triangle)
While I do have an implementation which does this, step1 (the generation of the list of unique vertices) is really slow in the order of O(n!), since each vertex is compared to all vertices already in the list. I thought "Hey, lets build a hashmap of my vertices' components using std::map, that ought to speed things up!", only to find that generating a unique key from three floating point values is not a trivial task.
Here, the experts of stackoverflow come into play: I need some kind of hash-function which works on 3 floats, or any other function generating a unique value from a 3d-vertex position.
