Qual é a lógica de interseção da árvore kd?

Estou tentando descobrir como implementar uma árvore KD.

Na página 322 de "Detecção de colisão em tempo real" por Ericson

A seção de texto está incluída abaixo, caso a visualização do livro do Google não permita que você a veja quando clicar no link

seção de texto

Seção relevante:

A idéia básica por trás da interseção de um raio ou segmento de linha direcionada com uma árvore kd é direta. A linha é cruzada com o plano de divisão do nó e o valor t da interseção é calculado. Se t estiver dentro do intervalo da linha, 0 <= t <= tmax, a linha ultrapassa o plano e os dois filhos da árvore são descendentes recursivamente. Caso contrário, apenas o lado que contém a origem do segmento é visitado recursivamente.

Então, aqui está o que eu tenho: ( abra a imagem em uma nova guia, se você não conseguir ver as letras)

A árvore lógica

Aqui o raio laranja está passando pela cena 3d. Os x representam interseção com um plano. Da esquerda, o raio atinge:

• A face frontal do cubo anexo da cena,
• O (1) plano de divisão
• O plano de divisão (2.2)
• O lado direito do cubo anexo da cena

Mas eis o que aconteceria, seguindo ingenuamente a descrição básica de Ericson acima:

• Teste contra o plano de divisão (1). Ray atinge o plano de divisão (1), portanto, os filhos esquerdo e direito do plano de divisão (1) são incluídos no próximo teste.
• Teste contra o plano de divisão (2.1). Na verdade, Ray atinge esse plano (muito à direita) para que as duas crianças sejam incluídas no próximo nível de testes. (Isso é contra-intuitivo - o nó inferior não deve ser incluído nos testes subsequentes)

Alguém pode descrever o que acontece quando o raio laranja passa pela cena corretamente?

É realmente muito simples; o teste contra o plano de divisão (2.1) deve falhar, devido ao seguinte:

Quando o raio atinge o plano de divisão (1), você "divide o raio", ou; você define o tintervalo para o qual é válido e continua na árvore com as partes resultantes.

Portanto, ao verificar o plano (2.1), verifique se apenas a parte do raio que resta do plano (1) cruza com o plano (2.1), o que não ocorre. A interseção "mais à direita" de que você fala tem um valor t> tonde você divide o raio com o plano (1).

Espero que esteja claro o suficiente.

Resumo: As interseções subsequentes de raio / plano devem ser feitas apenas com a parte do raio restante após dividi-lo com o plano em questão.