Algoritmo para encontrar bordes únicos de malla poligonal

Question

Estoy buscando un buen algoritmo que pueda darme los bordes únicos de un conjunto de datos de polígonos. En este caso, los polígonos están definidos por dos matrices. Una matriz es el número 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 disminuye 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 conjunto stl ::. Mi conjunto de datos será principalmente triángulo y quad polys, y la mayoría de los bordes se compartirán.

¿Existe un algoritmo más inteligente para esto?

Answer 1

Sí
Use un mapa de 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 mapa de hash 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 guardar información para 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, si lo desea, para una lista de polígonos como esta:

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

Entonces, en lugar de bordes como este:

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

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

¿entonces quiere eliminar el borde duplicado B - C vs. C - B y compartirlo?

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

Answer 3

Ambos tienen razón. El uso de un buen hashset ha conseguido que el rendimiento supere los niveles requeridos. Terminé rodando mi propio pequeño conjunto de hash.

El número total de aristas 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 búfer 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

heres una implementación en C de hashing de bordes utilizada en Blender exactamente con el propósito de crear rápidamente bordes a partir de caras, puede dar algunas pistas para que otros hagan las suyas.

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 usa 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

Answer 5

Primero debes asegurarte de que tus vértices sean únicos. Eso es si solo quieres una ventaja en una posición determinada. Entonces uso esta estructura de datos

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

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

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

Entonces puedes hacer

uniqueEdges[sampleEdge] = true;

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