Intersecciones de malla a malla

Estoy buscando una biblioteca o un documento que describa cómo determinar si una malla triangular se cruza con otra.Intersecciones de malla a malla

Curiosamente, estoy llegando vacío. Si hay alguna forma de hacerlo en CGAL, me está eludiendo.

Parece que claramente debería ser posible, porque la intersección del triángulo es posible y porque cada malla contiene un número finito de triángulos. Pero supongo que debe haber una forma mejor de hacerlo que el obvio O (n * m) enfoque donde una malla tiene n triángulos y la otra tiene m triángulos.

Fuente

2011-11-01 Doug McClean

El enfoque 'obvio' a dar falsos negativos si una de las mallas es completamente dentro de la otra. – cmannett85

Me interesan las colisiones entre las mallas como superficies de grosor cero.Veo cómo sucedería si estuviera interesado en las colisiones entre las mallas que se interpretan como poliedros. –

[Ver también triángulo-triángulo aquí] (http://www.realtimerendering.com/intersections.html) – bobobobo

Creo que el término de búsqueda que se está perdiendo es superposición. Por ejemplo, aquí hay una página web en Surface Mesh Overlay. Ese sitio tiene una breve bibliografía, todos de los mismos autores. Aquí hay otro documento sobre el tema: "Overlay mesh construction using interleaved spanning trees," INFOCOM 2004: Vigésima Tercera Conferencia Conjunta Anual de las Sociedades de Informática y Comunicaciones IEEE. Vea también la pregunta GIS SE, "Performing Overlay of Two Triangulated Irregular Networks (TIN)."

Fuente

2011-11-02 01:09:59

El libro Real-Time Collision Detection tiene algunas buenas sugerencias para implementar tales algoritmos. El enfoque básico es utilizar particiones espaciales o volúmenes de limitación para reducir el número de pruebas de intersección tri-tri que debe realizar.

Hay una serie de buenos paquetes académicos que abordan este problema, incluido el Proximity Query Package, y el otro trabajo de GAMMA research group at University of North Carolina, SWIFT, I-COLLIDE y RAPID son bien conocidos. Verifique que las licencias en estas bibliotecas sean aceptables.

Open Dynamics Engine (ODE), es un motor de física que contiene implementaciones optimizadas de un gran número de primitivas de intersección. Puede consultar la documentación de la prueba de intersección triángulo-triángulo en su wiki.

Si bien no es exactamente lo que está buscando, creo que esto también es posible con CGAL - Tree of Triangles, for Intersection and Distance Queries

Fuente

2011-11-02 04:54:01

Gran recomendación de libro – Fattie

La forma en que normalmente lo hacemos utilizando CGAL es con CGAL::box_intersection_d.

Puede hacerlo mezclando example con este one.

Fuente

2011-11-02 07:19:18 sloriot

Los ejemplos 4 y 5 son muy útiles para principiantes. Sin embargo, no está claro cómo crear una estructura en árbol de AABB para acelerar todo el proceso. Además, los ejemplos son más claros para el caso de autointersección. En el caso de dos mallas separadas, no está muy claro (y supongo que arrojar todos los triángulos/cajas en un vector no es óptimo en absoluto). Alguna sugerencia uno arriba? –

Debe usar un vector por malla y usar [CGAL :: box_intersection_d()] (http://doc.cgal.org/latest/Box_intersection_d/group__PkgBoxIntersectionD__box__intersection__d.html). – sloriot

Para agregar a las otras respuestas, también hay técnicas que involucran la suma 3D Minkowski de poliedros convexos: los poliedros cóncavos se pueden descomponer en partes convexas. Consulte this.

Fuente

2011-11-02 07:27:03 cmannett85

En libigl, Hemos terminado CGAL de CGAL::box_intersection_d para intersectar una malla con vértices V y caras F con otra malla con vértices U y caras G, almacenar pares de intersección de facetas como filas en IF:

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

Este ignorará las autointersecciones. Para completar, voy a mencionar que también apoyamos autointersecciones en una función separada:

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

Fuente

2014-04-26 02:17:43

Intersecciones de malla a malla

Respuesta

Cuestiones relacionadas