Buscar vértices únicos de una 'sopa triangular'

Question

Estoy construyendo un convertidor de archivos CAD sobre dos bibliotecas (Opencascade y DWF Toolkit).

Sin embargo, mi pregunta es agnóstico plattform:

Dado:

He generado una malla como una lista de caras triangulares forman un modelo construido a través de mi solicitud. Cada triángulo se define a través de tres vértices, que consisten en tres flotantes (x, y & coordenada z). Como los triángulos forman una malla, la mayoría de los vértices son compartidos por más de un triángulo.

Objetivo:

Necesito encontrar la lista de vértices únicas, y para generar una serie de caras que consta de tuplas de tres índices en esta lista.

Lo que quiero hacer es esto:

//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) 

Aunque tengo una aplicación que hace esto, paso 1 (la generación de la lista de vértices únicas) es muy lento en el orden de O (n !), ya que cada vértice se compara con todos los vértices que ya están en la lista. Pensé: "Oye, permitamos construir un hashmap de los componentes de mis vértices usando std :: map, ¡eso debería acelerar las cosas!", Solo para descubrir que generar una clave única a partir de tres valores de punto flotante no es una tarea trivial.

Aquí entran en juego los expertos de stackoverflow: necesito algún tipo de función hash que funcione con 3 flotadores o cualquier otra función que genere un valor único desde una posición de vértice 3d.

Answer 1

Vuelca todos los vértices en una matriz, luego haz unique(sort(array)). Esto debería ser O (k n log (n)), donde k es el número promedio de triángulos que comparten un vértice, generalmente k < 7.

La única advertencia que ocurre es que su función unique debe ser capaz de tomar un puntero a una función de comparación, ya que es probable que desee tener en cuenta sus vértices iguales si

distance(vertex1, vertex2) < threshold 

pero que parece ser OK.

Answer 2

Tres soluciones. Ciertamente hay otros

1. Utilice un mapa hash. Esto solo funcionará si "lo mismo" significa exactamente lo mismo
2. Usa una partición de espacio binario para dividir los puntos
3. Usa una cuadrícula regular para dividir tus puntos.

En los casos 2 y 3, si desea especificar cierta tolerancia, deberá buscar más de una parte del árbol o la cuadrícula. En el caso de BSP, esto significa verificar si se está dentro de la tolerancia del plano divisor, y si es así recurriendo a ambas mitades. En el caso de la cuadrícula, esto significa verificar todas las celdas vecinas que están dentro de la tolerancia. Ninguno de los cuales es demasiado difícil, pero significa que será más difícil usar una solución "estándar".

Answer 3

La idea común de obtener hash es multiplicar cada patrón de bits de un flotante con un prime y agregarlos. Algo así:

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

Debe tener en cuenta que sizeof (unsigned int) se considera igual a sizeof (float) aquí. La muestra aquí es solo para ilustrar la idea principal, debe ajustarla para sus necesidades.