Intersezioni mesh a mesh

Question

Sto cercando una libreria o una carta che descriva come determinare se una maglia triangolare interseca un'altra.

È interessante notare che sto arrivando vuoto. Se c'è un modo per farlo in CGAL, mi sfugge.

Sembra che sia chiaramente possibile, perché l'intersezione del triangolo è possibile e perché ogni mesh contiene un numero finito di triangoli. Ma suppongo che ci debba essere un modo migliore per farlo rispetto all'ovvio approccio O (n * m) in cui una maglia ha n triangoli e l'altra ha m triangoli.

Answer 1

Penso che il termine di ricerca che ti manca sia overlay. Ad esempio, ecco una pagina web su Surface Mesh Overlay. Quel sito ha una breve bibliografia, tutti degli stessi autori. Ecco un altro articolo sull'argomento: "Overlay mesh construction using interleaved spanning trees," INFOCOM 2004: Ventitreesima conferenza congiunta annuale delle società di computer e comunicazioni IEEE. Vedere anche la domanda GIS SE, "Performing Overlay of Two Triangulated Irregular Networks (TIN)".

Answer 2

Il libro Real-Time Collision Detection ha alcuni buoni suggerimenti per l'implementazione di tali algoritmi. L'approccio di base consiste nell'utilizzare partizionamento spaziale o volumi di delimitazione per ridurre il numero di test di intersezione tri-tri che è necessario eseguire.

Ci sono un certo numero di buoni pacchetti accademici che affrontano questo problema compreso il Proximity Query Package, e l'altro lavoro del GAMMA research group at University of North Carolina, SWIFT, I-scontrano, e RAPID sono tutti ben noti. Verifica che le licenze su queste librerie siano accettabili.

Open Dynamics Engine (ODE), è un motore fisico che contiene implementazioni ottimizzate di un gran numero di primitive di intersezione. Puoi consultare la documentazione per il test di intersezione triangolo-triangolo sul loro wiki.

Anche se non è esattamente quello che stai cercando, credo che questo è possibile anche con CGAL - Tree of Triangles, for Intersection and Distance Queries

Answer 3

Il modo in cui facciamo di solito utilizzando CGAL è con CGAL::box_intersection_d.

È possibile eseguire questa operazione mescolando questo example con questo one.

Answer 4

Per aggiungere alle altre risposte, ci sono anche tecniche che riguardano la somma 3D Minkowski di poliedri convessi: i poliedri concavi possono essere scomposti in parti convesse. Controlla this.

Answer 5

In libigl, spostiamo in su CGAL di CGAL::box_intersection_d intersecare una maglia con vertici V e facce F con un'altra maglia con vertici U e facce G, memorizzare coppie di intersezione sfaccettature come righe in IF:

igl::intersect_other(V,F,U,G,false,IF); 

Questo ignorerà le autointersezioni. Per completezza, io detto che abbiamo anche il supporto auto-intersezioni in una funzione separata:

igl::self_intersect(V,F,...,IF);