robusto algoritmo per la ricostruzione della superficie dalla nuvola di punti 3D?

https://stackoverflow.com/questions/838761

22-07-2019
|

Domanda

Sto cercando di capire quali algoritmi ci sono per fare la ricostruzione di superficie dai dati di portata 3D. A prima vista, sembra che l'algoritmo Ball pivoting ( BPA ) e ricostruzione della superficie di Poisson siano i metodi più affermati?

Quali sono gli algoritmi consolidati e più robusti nel campo diverso dall'algoritmo di ricostruzione della superficie BPA e Poisson?
Pubblicazioni di ricerca consigliate?
Esiste un codice sorgente disponibile?

Soluzione

Sto affrontando questo dilemma da alcuni mesi ormai e ho fatto ricerche approfondite.

Algoritmi

Principalmente ci sono 2 categorie di algoritmi: geometria di calcolo e superfici implicite.

Geometria di calcolo

Si adattano alla mesh sui punti esistenti.

Probabilmente l'algoritmo più famoso di questo gruppo è powercrust , perché teoricamente ben consolidato, garantisce una rete a tenuta stagna.

Ball Pivoting è brevettato da IBM. Inoltre, non è adatto a nuvole di punti con densità di punti variabile.

Funzioni implicite

Uno si adatta alle funzioni implicite sulla nuvola di punti, quindi utilizza un algoritmo simile a un cubo in marcia per estrarre il set zero della funzione in una mesh.

I metodi in questa categoria differiscono principalmente per le diverse funzioni implicite utilizzate.

Poisson , Hoppe's e MPU sono gli algoritmi più famosi in questa categoria. Se sei nuovo sull'argomento, ti consiglio di leggere la tesi di Hoppe, è molto esplicativo.

Gli algoritmi di questa categoria di solito possono essere implementati in modo che siano in grado di elaborare enormi input in modo molto efficiente e si può ridimensionare la loro qualità! <<>> lt; - > trade-off di velocità. Non sono disturbati da rumori, densità dei punti variabile, buchi. Uno svantaggio di questi è che richiedono punti normali di superficie orientati in modo coerente nei punti di ingresso.

Implementazioni

Troverai un numero limitato di implementazioni gratuite. Tuttavia dipende dal fatto che lo integrerai nel software libero (in questo caso la licenza GPL è accettabile per te) o in un software commerciale (in questo caso hai bisogno di una licenza più liberale). Quest'ultimo è molto raro.

Uno è in VTK . Ho il sospetto che sia difficile da integrare (nessuna documentazione è disponibile gratuitamente), ha un'architettura strana, troppo complicata e non è progettata per applicazioni ad alte prestazioni. Presenta anche alcune limitazioni per i punti di input consentiti.

Dai un'occhiata a questa implementazione di Poisson e dopo quella condivisione la tua esperienza con me per favore.

Inoltre: qui sono alcuni algoritmi ad alte prestazioni, tra cui la ricostruzione della superficie.

CGAL è una famosa libreria 3d, ma è gratuita solo per progetti gratuiti. Meshlab è una famosa applicazione con GPL.

Anche (aggiunto agosto 2013): La libreria PCL ha un modulo dedicato alla ricostruzione delle superfici ed è in fase di sviluppo attivo (e fa parte del Summer of Code di Google). Il modulo di superficie contiene una serie di algoritmi diversi per la ricostruzione. PCL inoltre ha la capacità di stimare le normali di superficie, nel caso in cui non le abbiate fornite con il vostro dati puntuali, questa funzionalità è disponibile nelle funzioni module . PCL è rilasciato secondo i termini della licenza BSD ed è un software open source, è gratuito per uso commerciale e di ricerca.

Altri suggerimenti

Se vuoi fare alcuni esperimenti diretti con vari algoritmi di ricostruzione della superficie, dovresti provare MeshLab , il sistema di elaborazione mesh, è open source e contiene implementazioni di molti degli algoritmi di ricostruzione della superficie citati in precedenza, come:

Poisson Surface Recon
un paio di approccio basato su MLS,
un'implementazione pivotante su palla
una variante dell'approccio basato sul volume Curless
Tecniche basate su Delaunay (forme alfa e filtro Voronoi)
strumenti per il calcolo di normali da set di punti sparsi
e molti altri strumenti per confrontare / misurare / pulire / semplificare le mesh risultanti.

Le fonti sono protette da GPL, quindi non è possibile utilizzarle in un progetto commerciale a fonte chiusa, ma è molto importante avere la giusta sensazione circa le proprietà dei vari algoritmi di ricostruzione della superficie (quanto sono sensibili al rumore, il la velocità, la solidità ai valori anomali, il modo in cui conservano dettagli precisi, ecc. ecc.) prima di iniziare a implementarne uno.

Potresti iniziare a guardare alcuni lavori recenti sul campo - attualmente qualcosa come Ricostruzione MLS in streaming a bassa memoria veloce di superfici punti campionate di Gianmauro Cuccuru, Enrico Gobbetti, Fabio Marton, Renato Pajarola e Ruggero Pintus. Le sue citazioni possono farti passare in rassegna la letteratura abbastanza rapidamente.

Pur non essendo una rappresentazione mesh, un ex collega mi ha consigliato questo link al codice sorgente per un metodo Spline Thin Plate:

Link

Qualcuno l'ha provato?

Non sono sicuro che sia esattamente giusto per il tuo caso, poiché sembra strano che tu lo abbia omesso, ma in marcia cubi è comunemente menzionato in casi come questi.

Qui su GitHub, è un open source Libreria di elaborazione mesh in C ++ da Dott. Hugues Hoppe , in cui il programma di ricostruzione della superficie Ricognizione è una buona opzione per il tuo problema ...

Esiste strumento 3D Delaunay di Geometric Tools . Questo strumento viene utilizzato DirecX e OpenGL. Sfortunatamente, potrebbe essere necessario acquistare un libro per vedere l'attuale codice di esempio della biblioteca. Leggi ancora il codice e capisci.

Matlab ha anche introdotto uno strumento di ricostruzione della superficie utilizzando Delaunay, delaunayTriangulation class .

Dato che avevo anche questo problema, ho sviluppato e implementato il mio algoritmo di crosta di nuvole di punti. Le fonti e la documentazione sono disponibili su github.com: https://github.com/ricebean net / PointCloudCrust . L'algoritmo è implementato in Java.

Forse, questo può aiutarti. Puoi anche trovare un breve script Python sulla pagina che illustra come usare la libreria. Buon divertimento!

Potresti essere interessato a Alpha Shapes .

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow