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 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)
El árbol lógico
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?
fuente