¿Cuál es la lógica de intersección del árbol kd?

12

Estoy tratando de descubrir cómo implementar un árbol KD.

En la página 322 de "Detección de colisión en tiempo real" por Ericson

La sección de texto se incluye a continuación en caso de que la vista previa del libro de Google no le permita verla al hacer clic en el enlace

sección de texto

Sección relevante:

La idea básica detrás de la intersección de un rayo o segmento de línea dirigida con un árbol kd es directa. La línea se cruza con el plano de división del nodo y se calcula el valor t de la intersección. Si t está dentro del intervalo de la línea, 0 <= t <= tmax, la línea se extiende a ambos lados del plano y ambos hijos del árbol descienden recursivamente. De lo contrario, solo se visita recursivamente el lado que contiene el origen del segmento.

Así que esto es lo que tengo: ( abra la imagen en una nueva pestaña si no puede ver las letras)

imagen

El árbol lógico

divs

Aquí el rayo naranja atraviesa la escena 3D. Las x representan la intersección con un plano. Desde la IZQUIERDA, el rayo golpea:

  • La cara frontal del cubo envolvente de la escena,
  • El (1) plano de división
  • El plano de división (2.2)
  • El lado derecho del cubo envolvente de la escena.

Pero esto es lo que sucedería, ingenuamente siguiendo la descripción básica de Ericson anterior:

  • Prueba contra el plano de división (1). Ray golpea el plano de división (1), por lo que los hijos izquierdo y derecho del plano de división (1) se incluyen en la siguiente prueba.
  • Prueba contra el plano de división (2.1). Ray realmente golpea ese avión (muy a la derecha), por lo que ambos niños se incluyen en el siguiente nivel de pruebas. (Esto es contrario a la intuición: no solo se debe incluir el nodo inferior en las pruebas posteriores)

¿Alguien puede describir lo que sucede cuando el rayo naranja atraviesa la escena correctamente?

bobobobo
fuente

Respuestas:

14

Es bastante simple en realidad; la prueba contra el plano de división (2.1) debería fallar debido a lo siguiente:

Cuando el rayo golpea el plano de división (1), usted "divide el rayo", o; establece el trango para el que es válido y continúa hacia abajo en el árbol con las partes resultantes.

Por lo tanto, cuando se verifica contra el plano (2.1), debe verificar si solo la parte del rayo que queda del plano (1) se cruza con el plano (2.1), lo que no ocurre. La intersección "muy a la derecha" de la que habla tiene un t> tvalor donde divide el rayo con el plano (1).

Espero que sea lo suficientemente claro.

Resumen: Las intersecciones posteriores de rayo / plano deben hacerse solo con la parte del rayo restante después de dividirlo con el plano en cuestión.

Tormentoso
fuente
1
Grr !! (abreviatura de gran respuesta)
bobobobo
Buena respuesta Torious! Bienvenido a GDSE.
MichaelHouse