KDTree Dzielenie

Question

Obecnie piszę KDTree dla silnika fizyki (projekt Hobby).

KDTree nie zawiera punktów. Zamiast tego zawiera wyrównane do osi ramki ograniczające różne obiekty w otoczeniu.

Mój problem polega na decydowaniu o tym, jak rozdzielić węzły KDTree, kiedy się rozładują. Próbuję 2 metody:

Metoda 1: Zawsze podziel węzeł dokładnie w połowie na największej osi.

• Ma to zalety dość równomiernie rozłożonego drzewa.
• Duża wada: Jeśli obiekty są skoncentrowane na małej powierzchni węzła, tworzone będą nadmiarowe podziały. Dzieje się tak dlatego, że wszystkie woluminy są podzielone dokładnie na połowę.

Metoda 2: Znajdź obszar węzła, który zawiera obiekty. Podziel węzeł na płaszczyźnie, która podzieli ten obszar na pół na jego największą oś. Przykład - Jeśli wszystkie obiekty są skoncentrowane na dnie węzła, dzieli się on długością, dzieląc dno na dwie części.

• To rozwiązuje problem z powyższą metodą
• Przy indeksowaniu coś, co istnieje na tej samej płaszczyźnie (terenu), na przykład, tworzy długi i wąski węzłów. Jeśli mam później dodać inne obiekty, które nie znajdują się na tej samej płaszczyźnie, te wydłużone węzły zapewniają bardzo słabe indeksowanie.

To, czego szukam, to lepszy sposób na podzielenie węzła drzewa KD. Biorąc pod uwagę, że to będzie silnik fizyki, decyzja musi być na tyle prosta, aby była podejmowana w czasie rzeczywistym.

Answer 1

"Heuristic area" (SAH) jest uważany za najlepszą metodę dzielenia dla budowania drzewek kd, przynajmniej w obrębie społeczności Raytracing. Chodzi o to, aby dodać płaszczyznę, aby powierzchnia obu przestrzeni dziecięcych, ważona liczbą przedmiotów na każdym dziecku, była równa.

Dobre referencje na ten temat to Ingo Wald's thesis, w szczególności rozdział 7.3, "Wysokiej jakości konstrukcja BSP", która wyjaśnia SAH lepiej niż ja.

Nie mogę znaleźć dobrego linka w tej chwili, ale powinieneś rozejrzeć się za dokumentami na "binned" SAH, który jest przybliżeniem do prawdziwej SAH, ale znacznie szybciej.

Wszystko to, co zostało powiedziane, wydaje się, że hierarchie ograniczających objętości (BVH) a.k.a. AABB są znacznie bardziej popularne niż drzewa kd. Ponownie, Ingo Wald's publication page jest dobrym punktem wyjścia, prawdopodobnie w przypadku "Szybkiej budowy opartych na SAH bazujących na hierarchii poziomów głośności", chociaż minęło trochę czasu, odkąd go przeczytałem.

The OMPF forums są również dobrym miejscem do omawiania tego rodzaju rzeczy.

Nadzieję, że pomaga. Powodzenia!

Answer 2

Z pewnością dla silnika fizyki, w którym założenie jest dużo ruchomej geometrii, bvh jest prawdopodobnie lepszym wyborem, nie przechodzą tak szybko, ale są o wiele szybsze do zbudowania i są o wiele łatwiejsze do odnowienia/restrukturyzacji na podstawie ramki na ramkę, i offen nie potrzebują kompletnej przebudowy, każdej ramki (coś, co można zrobić równolegle w serii ramek, podczas gdy uzupełniony bvh wystarcza w międzyczasie, ponownie, odnoszą się do wald).

Wyjątkiem od tego w fizyce może być, gdy mamy do czynienia z obiektami, które nie mają objętości, takich jak cząstki lub fotony, budowa drzewa kd jest uproszczona przez fakt, że nie trzeba rozwiązywać ograniczeń pojedynczego prymitywu. To naprawdę zależy od aplikacji. Dobry silnik fizyki powinien wykorzystywać zrównoważoną kombinację struktur przyspieszenia przestrzennego, powszechną praktyką jest rozdzielanie szerszego podziału faz, na przykład o płytką liczbę ósemek, a następnie rozszerzanie węzłów liści o inny schemat, który lepiej pasuje do charakteru tego, co robisz, BSP są idealne do Geometria statyczna, zwłaszcza w 2d i kiedy struktura się nie zmienia, najlepiej jest eksperymentować z tak wieloma różnymi schematami i strukturami, aby poczuć, jak i kiedy działają najlepiej.