Algoritmo per trovare bordi unici da mesh poligonali

Question

Sto cercando un buon algoritmo che possa darmi i bordi unici da un insieme di dati poligonali. In questo caso, i poligoni sono definiti da due matrici. Un array è il numero di punti per poligono e l'altro array è un elenco di indici di vertici.

Ho una versione che funziona, ma le prestazioni rallentano quando raggiungono oltre 500.000 polys. La mia versione cammina su ogni faccia e aggiunge i vertici ordinati di ogni bordo a uno stl :: set. Il mio set di dati sarà principalmente triangolare e quadruplo, e la maggior parte dei bordi sarà condivisa.

Esiste un algoritmo più intelligente per questo?

Answer 1

Si
Usa una doppia mappa hash.
Ogni fronte ha due indici A, B. diciamo che A > B.
La prima mappa di hash map di livello superiore A su un'altra mappa di hash che a sua volta mappa B su un valore che rappresenta le informazioni desiderate su ogni bordo. (o solo un bool se non hai bisogno di conservare le informazioni per i bordi).
In sostanza, questo crea un albero a due livelli composto da mappe hash.

Per cercare un bordo in questa struttura prendi l'indice più grande, cercalo nel livello superiore e finisci con una mappa hash. quindi prendi l'indice più piccolo e cercalo in questa seconda mappa hash.

Answer 2

Solo per chiarire, vuoi, un elenco di poligoni come questo:

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

Quindi, invece di bordi come questo:

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

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

quindi si desidera rimuovere il bordo duplicato B - C vs. C - B e condividerlo?

Che tipo di problema di prestazioni stai riscontrando con il tuo algoritmo? Direi che un set con un'implementazione hash ragionevole dovrebbe funzionare abbastanza bene. D'altra parte, se il tuo hash non è ottimale per i dati, avrai molte collisioni che potrebbero influire negativamente sulle prestazioni.

Answer 3

Siete entrambi corretti. L'uso di un buon hashset ha ottenuto prestazioni ben oltre i livelli richiesti. Ho finito per girare il mio piccolo set di hash.

Il numero totale di spigoli sarà compreso tra N / 2 e N. N, ovvero il numero di vertici univoci nella mesh. Tutti i bordi condivisi saranno N / 2 e tutti i bordi univoci saranno N. Da lì allocare un buffer di uint64 e comprimere i miei indici in questi valori. Usando un piccolo set di tabelle uniche, riesco a trovare velocemente i bordi unici!

Answer 4

ecco un'implementazione in C dell'hashing dei bordi usato in Blender esattamente allo scopo di creare rapidamente bordi dalle facce, può dare qualche suggerimento per gli altri di fare il proprio.

http: // gitorious. org / blenderprojects / frullatore / macchie / master / blender / source / frullatore / blenlib / stagista / edgehash.c

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

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

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

Answer 5

Per prima cosa devi assicurarti che i tuoi vertici siano unici. Cioè se si desidera solo un bordo in una determinata posizione. Quindi utilizzo questa struttura di dati

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

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Bordo contiene gli indici dei vertici che compongono il bordo in ordine ordinato. Quindi se sampleEdge è un bordo costituito da vertici con numeri di indice 12 e 5, sampleEdge.first = 5 e sampleEdge.12

Quindi puoi semplicemente

uniqueEdges[sampleEdge] = true;

per tutti i bordi. uniqueEdges manterrà tutti i bordi unici.