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
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?