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

Estoy tratando de descubrir cómo implementar un tree KD.

En página 322 de "detección de colisión en time real" por Ericson

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

sección de text

Sección relevante:

La idea básica detrás de la intersección de un rayo o segmento de línea dirigida con un tree kd es directa. La línea se interseca con el plano de split 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 tree 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 image en una nueva pestaña si no puede ver las letras)

imagen

El tree lógico

divs

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

  • La cara frontal del cubo circundante de la escena,
  • El (1) plano de split
  • El plano de split (2.2)
  • El lado derecho del cubo circundante de la escena

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

  • Prueba contra el plano de split (1). Ray golpea el plano de split (1), por lo que los hijos de izquierda y derecha del plano de split (1) se incluyen en la siguiente testing.
  • Prueba contra el plano de split (2.1). Ray realmente golpea ese avión, (path a la derecha) por lo que ambos niños están incluidos en el siguiente nivel de testings. (Esto es contrario a la intuición: no solo debería includese el nodo inferior en testings posteriores)

¿Puede alguien describir lo que sucede cuando el rayo naranja atraviesa la escena correctamente?

Es bastante simple realmente; la testing contra el plano de split (2.1) debería fallar debido a lo siguiente:

Cuando el rayo golpea el plano de split (1), "divide el rayo", o; configura el t range para el que es válido, y continúa descendiendo por el tree con las partes resultantes.

Por lo tanto, al verificar 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 de "lejos hacia la derecha" de la que hablas tiene un valor t > t donde divides el rayo con el plano (1).

Espero que eso sea lo suficientemente claro.

Resumen: las intersecciones subsiguientes entre el rayo y el plano solo deben hacerse con la parte del rayo restante después de dividirlo con el plano en cuestión.

    Intereting Posts