¿Existe un algoritmo conocido 'más eficiente' para la detección de colisión AABB vs Ray?
Recientemente me topé con el algoritmo de colisión AABB vs Esfera de Arvo, y me pregunto si hay un algoritmo similarmente notable para esto.
Una condición que debe tener este algoritmo es que necesito tener la opción de consultar el resultado de la distancia desde el origen del rayo hasta el punto de colisión. Dicho esto, si hay otro algoritmo más rápido que no devuelve la distancia, además de publicar uno que sí lo haga, también sería muy útil publicar ese algoritmo.
Indique también cuál es el argumento de retorno de la función y cómo lo utiliza para devolver la distancia o un caso de "no colisión". Por ejemplo, ¿tiene un parámetro de salida para la distancia y un valor de retorno de bool? ¿O simplemente devuelve un flotador con la distancia, frente a un valor de -1 para ninguna colisión?
(Para aquellos que no saben: AABB = Cuadro delimitador alineado del eje)
fuente
Respuestas:
Andrew Woo, quien junto con John Amanatides desarrolló el algoritmo de marcado de rayos (DDA) utilizado de manera ubicua en los trazadores de rayos, escribió "Intersección rápida de la caja de rayos" (fuente alternativa aquí ) que se publicó en Graphics Gems, 1990, pp. 395-396. En lugar de ser construido específicamente para la integración a través de una cuadrícula (por ejemplo, un volumen de vóxel) como DDA es (ver la respuesta de zacharmarz), este algoritmo es específicamente adecuado para mundos que no están subdivididos de manera uniforme, como su mundo de poliedros típico que se encuentra en la mayoría de los 3D juegos.
El enfoque proporciona soporte para 3D y, opcionalmente, realiza el sacrificio de la cara posterior. El algoritmo se deriva de los mismos principios de integración utilizados en los DDA, por lo que es muy rápido. Se pueden encontrar más detalles en el volumen original de Graphics Gems (1990).
Se pueden encontrar muchos otros enfoques específicos para Ray-AABB en realtimerendering.com .
EDITAR: Aquí se puede encontrar un enfoque alternativo sin ramificaciones, que sería deseable tanto en GPU como en CPU .
fuente
Lo que he estado usando anteriormente en mi raytracer:
Si esto devuelve verdadero, se está intersectando, si devuelve falso, no se está intersectando.
Si usa el mismo rayo muchas veces, puede calcular previamente
dirfrac
(solo división en la prueba de intersección completa). Y luego es realmente rápido. Y también tiene una longitud de rayo hasta la intersección (almacenada ent
).fuente
Nadie describió el algoritmo aquí, pero el algoritmo Graphics Gems es simplemente:
Usando el vector de dirección de tu rayo, determina qué 3 de los 6 planos candidatos serían golpeados primero . Si su vector de dirección de rayos (no normalizado) es (-1, 1, -1), entonces los 3 planos que se pueden golpear son + x, -y y + z.
De los 3 planos candidatos, encuentre el valor t para la intersección de cada uno. Acepte el plano que obtiene el valor t más grande como el plano que recibió el impacto, y verifique que el impacto esté dentro de la casilla . El diagrama en el texto deja esto claro:
Mi implementacion:
fuente
Esta es mi intersección de rayos 3D / AABox que he estado usando:
fuente
tnear
ytfar
?Aquí hay una versión optimizada de lo anterior que utilizo para GPU:
fuente
Una cosa que es posible que desee investigar es rasterizar las caras frontal y posterior de su cuadro delimitador en dos búferes separados. Representa los valores x, y, z como rgb (esto funciona mejor para un cuadro delimitador con una esquina en (0,0,0) y el opuesto en (1,1,1).
Obviamente, esto tiene un uso limitado, pero me pareció genial para renderizar volúmenes simples.
Para más detalles y código:
http://www.daimi.au.dk/~trier/?page_id=98
fuente
Aquí está el código Line vs AABB que he estado usando:
fuente
Esto parece similar al código publicado por zacharmarz.
Obtuve este código del libro 'Detección de colisión en tiempo real' de Christer Ericson en la sección '5.3.3 Rayo o segmento de intersección contra la caja'
fuente
Me sorprende ver que nadie ha mencionado el método de losa sin ramas de Tavian
Explicación completa: https://tavianator.com/fast-branchless-raybounding-box-intersections/
fuente
He agregado a @zacharmarz la respuesta para manejar cuando el origen del rayo está dentro del AABB. En este caso, tmin será negativo y detrás del rayo, por lo que tmax es la primera intersección entre el rayo y AABB.
fuente