Estructura de datos para determinar la intersección entre la línea y el polígono en 3D

7

Tengo una colección de polígonos simples P que no se superponen. En realidad, son triángulos 2D en el espacio 3D.

Estoy buscando una estructura de datos que, dada una línea L, tenga una búsqueda relativamente rápida para todos los polígonos p en P con los que L se interseca. Si me puede dar el punto de intersección, eso es un bono, pero puedo calcularlo yo mismo si acabo de obtener los polígonos, en cualquier caso.

He usado kd-trees y red-black-trees antes, pero como se trata de puntos, espero que haya una estructura de datos que se adapte mejor a mi problema. Espero que sea una especie de árbol BSP, pero estoy abierto a otras sugerencias.

    
pregunta elsurudo 07.04.2016 - 12:53

2 respuestas

2

Puede intentar utilizar un octree para esto. Esto no le dará exactamente el conjunto de polígonos que está buscando, sino un superconjunto que puede ser significativamente más pequeño que todo el conjunto de polígonos (por supuesto, la forma en que funciona depende de los polígonos y de cómo se distribuyen en el espacio).

Elija un cierto "máximo de profundidad" para el árbol que sea apropiado para la escala de su problema. Asocie a cada cubo "hoja" los polígonos cuyo cuadro delimitador toque ese cubo. Al buscar los polígonos, determine los cubos de hojas que son tocados por la línea y tenga en cuenta solo los polígonos asociados.

    
respondido por el Doc Brown 07.04.2016 - 17:20
1

Si su escena es estática (es decir, sus triángulos no se mueven, por lo que puede amortizar la construcción de su estructura de datos de aceleración en todas sus líneas), entonces creo que a kd-tree altamente optimizado todavía es lo último en tecnología para este propósito. Debido a que tienen una extensión finita, sus triángulos pueden superponerse a más de una rama del árbol kd-tree; sin embargo, eso será cierto para cualquier estructura de aceleración de tipo BSP.

El R-tree ejemplifica una clase alternativa de estructura de aceleración. Al igual que el árbol kd, los nodos del árbol R tienen cajas delimitadoras alineadas con el eje; sin embargo, en un árbol R, los cuadros delimitadores de los nodos hermanos pueden superponerse.

En un sentido generalizado, la mayoría de las estructuras de aceleración conocidas son como R-tree o BSP.

    
respondido por el comingstorm 07.06.2016 - 20:38

Lea otras preguntas en las etiquetas