graphics - segmentos - ¿Cuál es el mejor enfoque para calcular eficientemente la primera intersección entre un rayo de visión y un conjunto de objetos?
punto de interseccion de una funcion (4)
Por ejemplo:
Una aproximación para calcular eficientemente la primera intersección entre un rayo de visión y un conjunto de tres objetos: una esfera, un cono y un cilindro (otras primitivas 3D).
"computacionalmente eficiente" depende de qué tan grande sea el conjunto.
Para un conjunto trivial de tres, simplemente prueba cada uno de ellos, realmente no vale la pena tratar de optimizarlo.
Para conjuntos más grandes, observe las estructuras de datos que dividen el espacio (por ejemplo, árboles KD). Capítulos enteros (y, de hecho, libros enteros) están dedicados a este problema. Mi libro de referencia favorito es Una introducción a Ray Tracing (editor Andrew S. Glassner)
Alternativamente, si he leído mal tu pregunta y en realidad estás pidiendo algoritmos para intersecciones de objetos con rayos para tipos específicos de objetos, ¡mira el mismo libro!
Lo que estás buscando es un esquema de partición espacial. Hay muchas opciones para lidiar con esto, y mucha investigación también en esta área. Una buena lectura sería la Detección de colisiones en tiempo real de Christer Ericsson.
Un enfoque fácil cubierto en ese libro sería definir una cuadrícula, asignar todos los objetos a todas las celdas que cruza, y caminar a lo largo de las celdas de la cuadrícula que cruzan la línea, de adelante hacia atrás, intersectando con cada objeto asociado con esa celda de cuadrícula. Tenga en cuenta que un objeto puede estar asociado con más celdas de cuadrícula, por lo que el punto de intersección calculado en realidad podría no estar en la celda actual, sino más adelante.
La siguiente pregunta sería cómo definir esa grilla. Desafortunadamente, no hay una buena respuesta, y debe considerar qué enfoque se ajusta mejor a su situación.
Otros esquemas de partición de interés son diferentes estructuras de árbol, como kd- , Oct- y BSP-trees . Incluso podría considerar usar árboles combinados con una grilla.
EDITAR
Como se señaló, si su conjunto es en realidad estos tres objetos, definitivamente es mejor interceptar cada uno, y simplemente elija el más antiguo. Si está buscando pruebas de intersección de ray-sphere, ray-cylinder, etc., estas no son realmente difíciles y un google rápido debería proporcionar todas las matemáticas que pueda necesitar. :)
Supongo que tiene un rayo d = (dx, dy, dz), comenzando en o = (ox, oy, oz) y está encontrando el parámetro t tal que el punto de intersección p = o + d * t. (Como esta página, que describe la intersección del plano de rayos usando P2-P1 para d, P1 para o y u para t)
La primera pregunta que haría sería "¿Se cruzan estos objetos"?
Si no, entonces puede hacer trampa un poco y verificar colisiones de rayos en orden. Como tiene tres objetos que pueden moverse o no por cuadro, vale la pena calcular previamente su distancia desde la cámara (por ejemplo, desde sus puntos centrales). Pruebe cada objeto por turno, por distancia de la cámara, desde el más pequeño hasta el más grande. Aunque el espacio vacío es la parte más cara del render ahora, es más efectivo que solo probar contra los tres y tomar un valor mínimo. Si su imagen es de alta resolución, esto es especialmente eficiente ya que amortiza el costo en función del número de píxeles.
De lo contrario, prueba contra los tres y toma un valor mínimo ...
En otras situaciones, es posible que desee hacer un híbrido de los dos métodos. Si puede probar dos de los objetos en orden, hágalo (por ejemplo, una esfera y un cubo que se mueven por un túnel cilíndrico), pero pruebe el tercero y tome un valor mínimo para encontrar el objeto final.
Bueno, depende de lo que realmente estás tratando de hacer. Si desea producir una solución que sea correcta para casi cada píxel en una escena simple, un método extremadamente rápido es precalcular "qué hay delante" para cada píxel precribiendo todos los objetos con una identificación única colorear en un búfer de elementos de fondo mediante la conversión de escaneo (también conocido como z-buffer). Esto a veces se denomina buffer de elementos.
Utilizando ese cómputo previo, sabrá qué será visible para casi todos los rayos que grabará en la escena. Como resultado, su problema de intersección rayo-entorno se simplifica enormemente: cada rayo golpea un objeto específico.
Cuando estaba haciendo esto hace muchos años , estaba produciendo imágenes de raytraced en tiempo real de escenas ciertamente simples. No he vuelto a visitar ese código en bastante tiempo, pero sospecho que con compiladores modernos y hardware de gráficos, el rendimiento sería mucho mejor de lo que estaba viendo en ese momento.
PD: La primera vez que leí sobre la idea del búfer de elementos fue cuando estaba haciendo mi búsqueda bibliográfica a principios de los 90. Originalmente encontré mencionado en (creo) un documento de ACM de finales de los 70. Tristemente, no tengo la referencia de fuente disponible, pero, en resumen, es una idea muy antigua y funciona muy bien en el hardware de conversión de escaneo.