Algoritmo para encontrar bordes únicos desde malla poligonal

Question

Estoy buscando un buen algoritmo que pueda darme los bordes únicos de un conjunto de datos de polígono. En este caso, los polígonos están definidos por dos matrices. Una matriz es la cantidad de puntos por polígono, y la otra matriz es una lista de índices de vértices.

Tengo una versión que funciona, pero el rendimiento es lento cuando se alcanzan más de 500,000 polys. Mi versión camina sobre cada cara y agrega los vértices ordenados de cada borde a un stl :: set. Mi conjunto de datos será principalmente polígonos triangulares y cuádruples, y la mayoría de los bordes serán compartidos.

¿Existe un algoritmo más inteligente para esto?

Answer 1

Sí
Utilice un mapa doble hash.
Cada borde tiene dos índices A, B. digamos que A> B.
El primer mapa de hash de nivel superior asigna A a otro hash-map que a su vez asigna B a algún valor que representa la información que desea sobre cada borde. (o simplemente un bool si no necesita mantener la información de los bordes).
Básicamente, esto crea un árbol de dos niveles compuesto por mapas hash.

Para buscar un borde en esta estructura, tome el índice más grande, búsquelo en el nivel superior y termine con un mapa hash. luego tome el índice más pequeño y búsquelo en este segundo mapa hash.

Answer 2

Solo para aclarar, desea, para obtener una lista de polígonos como esto:

A +-----+ B 
    \ |\ 
    \ 1 | \ 
    \ | \ 
     \ | 2 \ 
     \| \ 
     C +-----+ D 

Entonces, en lugar de los bordes de la siguiente manera:

A - B -+ 
B - C +- first polygon 
C - A -+ 

B - D -+ 
D - C +- second polygon 
C - B -+ 

a continuación que desea eliminar el duplicado B - C vs . C - B edge y compartirlo?

¿Qué tipo de problema de rendimiento está viendo con su algoritmo? Yo diría que un conjunto que tiene una implementación de hash razonable debería funcionar bastante bien. Por otro lado, si su hash no es óptimo para los datos, tendrá muchas colisiones que pueden afectar negativamente al rendimiento.

Answer 3

Ambos son correctos. El uso de un buen hashset ha mejorado el rendimiento más allá de los niveles requeridos. Terminé de rodar mi pequeño juego de hash.

El número total de bordes estará entre N/2 y N. N es el número de vértices únicos en la malla. Todos los bordes compartidos serán N/2, y todos los bordes únicos serán N. A partir de ahí, asigno un buffer de uint64 y empaco mis índices en estos valores. Usando un pequeño conjunto de tablas únicas, ¡puedo encontrar los bordes únicos rápidamente!

Answer 4

Primero debes asegurarte de que tus vértices sean únicos. Eso es si solo quieres un borde en cierta posición. Luego utilizo esta estructura de datos

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edge contiene los índices de vértices que conforman el borde en forma ordenada. Por lo tanto, si sampleEdge es un borde formado por vértices con los números de índice 12 y 5, sampleEdge.first = 5 y sampleEdge.12

a continuación, puedes hacer

uniqueEdges[sampleEdge] = true;

para todos los bordes. uniqueEdges contendrá todos los bordes únicos.

Answer 5

he aquí una implementación en C de hashing de borde utilizado en Blender exactamente con el fin de crear rápidamente bordes de caras, puede dar algunos consejos para que otros puedan hacer los suyos.

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/edgehash.c

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_edgehash.h

Esto utiliza BLI_mempool, https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_mempool.h