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.