Algoritmo per generare una maglia triangolare da una nuvola di punti

Question

In alcuni programmi di simulazione generiamo superfici oggetto in termini di punti, ogni punto ha coordinate 3D e il vettore che rappresenta la normale alla superficie in quel punto. Per scopi di visualizzazione vorremmo generare una mesh composta da triangoli; ogni tre punti di chiusura formano un triangolo con il suo normale. Quindi possiamo inviare queste informazioni ad alcuni programmi di visualizzazione standard che rendono la superficie come VMD (Visual Molecular Dynamics).

Ci chiediamo quale sia l'algoritmo più veloce/disponibile per farlo.

Answer 1

Date un'occhiata a Jonathan Shewchuk 's lavoro, in particolare sui suoi (insieme ai suoi colleghi) famose carte e implementazioni di:

• Streaming Computation of Delaunay Triangulations

• A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator

Ci è anche un'implementazione veloce di nuvole di punti non ordinate implementate nella libreria Point Cloud (PCL). Controlla la loro presentazione su Fast triangulation of unordered point clouds.

Answer 2

L'algoritmo di poesia di Misha Kazhdan potrebbe funzionare correttamente sui dati. La sua pagina software è here. Si noti che esiste anche una versione CGAL. Il manuale è here e pronto per l'uso demo di Windows here (purché siano stati installati questi dlls).

Answer 3

Si noti che le triangolazioni di Delaunay potrebbero non essere adatte alla propria applicazione in quanto le triangolazioni di Delaunay non sono adatte a veri problemi 3D (vale a dire dove i punti sono ben distribuiti in R3). Sono più appropriati per i problemi di collettore 2D (cioè terreno, ecc.).

Per generare superfici in R3, osservare il lavoro di Hugues Hoppe e il suo lavoro di "ricostruzione superficiale".

La ricostruzione della superficie viene utilizzata per trovare una superficie a maglie per adattarsi alla nuvola di punti; tuttavia, questo metodo produce alti conteggi triangolari. Se questo è un problema, puoi applicare una tecnica di riduzione mesh per ridurre il numero di poligoni in modo da minimizzare l'errore. Ad esempio, puoi guardare i metodi di decimazione di OpenMesh.

Hugues Hoppe

OpenMesh