Find unique vertices from a 'triangle-soup'

Question

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.

Answer 1

Three solutions. There are certainly others

1. Use a hash map. This will only work if "same" means exactly the same
2. Use a binary space partition to divide up the points
3. Use a regular grid to divide up your points.

In cases 2 and 3 if you want to specify some tolerance you will need to search more than one part of the tree or grid. In the BSP case this means checking if you are within tolerance of the dividing plane, and if so recursing into both halves. In the grid case this means checking all neighbouring cells that are within tolerance. Neither of which is overly hard, but means it will be harder to use an "off the shelf" solution.

Answer 2

The common idea to get hash is to multiply each bitpattern of a float with a prime and add them together. Something like that:

unsigned int hash_point(float x, float y, float z)
{
   unsigned int* px = (unsigned int*)&x;
   unsigned int* py = (unsigned int*)&y;
   unsigned int* pz = (unsigned int*)&z;

   return (*px)*PRIME1 + (*py)*PRIME2 + (*pz)*PRIME3;
}

You should note that sizeof(unsigned int) is considered equal to sizeof(float) here. Sample here is only to illustrate the main idea, you should tune it for your needs.

Answer 3

Dump all the vertices in an array, then do unique(sort(array)). This should be O(k n log(n)), where k is the average number of triangles that share a vertex, usually k<7.

The only caveat I can think of is that your unique function should be able to take a pointer to a comparison function, since you probably want to consider your vertices equal if

distance(vertex1, vertex2) < threshold

but that seems to be OK.