Jaka jest logika przecięcia drzewa KD?

Próbuję wymyślić, jak zaimplementować drzewo KD.

Na stronie 322 „Wykrywanie kolizji w czasie rzeczywistym” autorstwa Ericsona

Sekcja tekstowa znajduje się poniżej w przypadku, gdy podgląd książki Google nie pozwala jej zobaczyć po kliknięciu linku

sekcja tekstowa

Odpowiednia sekcja:

Podstawowa idea przecinania promienia lub ukierunkowanego odcinka linii z drzewem kd jest prosta. Linia przecina się z płaszczyzną podziału węzła i obliczana jest wartość t przecięcia. Jeśli t mieści się w przedziale linii, 0 <= t <= tmax, linia otacza płaszczyznę i oba potomki drzewa są rekurencyjnie zstępowane. Jeśli nie, rekursywnie odwiedzana jest tylko strona zawierająca początek segmentu.

Oto co mam: ( otwórz zdjęcie w nowej karcie, jeśli nie widzisz napisu)

Drzewo logiczne

Tutaj pomarańczowy promień przechodzi przez scenę 3D. Wartości x oznaczają przecięcie z płaszczyzną. Z LEWEJ promień uderza:

• Przednia ściana otaczającego sześcianu sceny,
• Płaszczyzna podziału (1)
• Płaszczyzna podziału (2.2)
• Prawa strona otaczającego sześcianu sceny

Ale oto, co by się stało, naiwnie podążając za podstawowym opisem Ericsona powyżej:

• Test na płaszczyźnie podziału (1). Promień uderza płaszczyznę podziału (1), więc lewe i prawe dzieci płaszczyzny podziału (1) są uwzględniane w następnym teście.
• Test na płaszczyźnie podziału (2.1). Ray faktycznie uderza w ten samolot (daleko w prawo), więc oboje dzieci są włączani do następnego poziomu testów. (Jest to sprzeczne z intuicją - nie powinno się uwzględniać tylko dolnego węzła w kolejnych testach)

Czy ktoś może opisać, co się stanie, gdy pomarańczowy promień przejdzie przez scenę poprawnie?

To naprawdę bardzo proste; test na płaszczyźnie podziału (2.1) powinien zakończyć się niepowodzeniem z następujących powodów:

Kiedy promień uderza w płaszczyznę podziału (1), „dzielisz promień” lub; ustawiasz tzakres, dla którego jest poprawny, i kontynuujesz w dół drzewa z wynikowymi częściami.

Dlatego podczas sprawdzania względem płaszczyzny (2.1) powinieneś sprawdzić, czy tylko część promienia na lewo od płaszczyzny (1) przecina się z płaszczyzną (2.1), czego nie robi. Przecięcie „daleko w prawo”, o którym mówisz, ma t> twartość, w której dzielisz promień na płaszczyznę (1).

Mam nadzieję, że to wystarczająco jasne.

Podsumowanie: Kolejne przecięcia promień / płaszczyzna powinny być wykonywane tylko z tą częścią promienia, która pozostała po podzieleniu jej na daną płaszczyznę.