graphics - triangle - mesh 3d wikipedia
Algoritmo para encontrar bordes únicos desde malla poligonal (5)
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 se vuelve 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.
¿Hay un algoritmo más inteligente para esto?
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!
Sí
Use 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 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 mantener la información de los bordes).
Esencialmente, esto crea un árbol de dos niveles compuesto por mapas hash.
Para buscar una ventaja 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.
Solo para aclarar, quieres, para una lista de polígonos como esta:
A +-----+ B
/ |/
/ 1 | /
/ | /
/ | 2 /
/| /
C +-----+ D
Luego, en lugar de bordes como este:
A - B -+
B - C +- first polygon
C - A -+
B - D -+
D - C +- second polygon
C - B -+
entonces quieres eliminar el borde duplicado B - C vs. C - B y compartirlo?
¿Qué tipo de problema de rendimiento estás viendo con tu 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.
Primero debes asegurarte de que tus vértices sean únicos. Eso es si solo quieres un borde en cierta posición. Luego uso 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 componen el borde en orden ordenado. 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
Entonces puedes hacer
uniqueEdges[sampleEdge] = true;
para todos los bordes. uniqueEdges contendrá todos los bordes únicos.
Aquí hay una implementación en C de hash de borde usado en Blender exactamente con el propósito de crear rápidamente bordes de caras, puede dar algunos consejos para que otros puedan hacer los suyos.
Esto utiliza BLI_mempool, https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c