Kiedy używać partycjonowania binarnego, Quadtree, Octree?

Największa praktyczna różnica między drzewami BSP a innymi rodzajami drzew 3d polega na tym, że drzewa BSP mogą być bardziej optymalne, ale działają tylko na geometrii statycznej. Dzieje się tak dlatego, że drzewa BSP są zazwyczaj bardzo powolne w budowie, często trwają godziny lub dni dla typowego statycznego poziomu gry miejskiej.

Dwa główne powody, dla których drzewa BSP potrzebują więcej czasu na budowę, to (a) używają nieosiowych płaszczyzn podziału, które optymalnie znajdują się dłużej, oraz (b) dzielą geometrię na osi granice, zapewniając, że żadne obiekty nie przekraczają podzielonych płaszczyzn.

Inne typy drzew trójwymiarowych (Oktrees, Quadtrees, KD-tree, Bounding-Volume-Hierarchy) używają obwiedni wyrównanych do osi, a woluminy mogą (opcjonalnie) nakładać się na siebie, więc zawarte obiekty nie muszą być wycinane na granicach woluminów. Oba te elementy sprawiają, że drzewa są mniej optymalne niż drzewa BSP, ale są szybsze w budowie i łatwiejsze do zmiany dla obiektów dynamicznych.

Ekstrapolowanie tych czynników na sytuacje...

Outdoor areas zazwyczaj stosuje się reprezentacje terenu oparte na polu wysokości, proste mapy wysokości lub bardziej złożone techniki mapowania geo-mip, takie jak ROAM. Sama ziemia nie uczestniczy w podziale przestrzeni 3d, tylko obiekty umieszczone na ziemi.

Światy z wieloma przykładami prostszej i podobnej geometrii (Domy, Drzewa, asteroidy itp.) często używają nie-BSP-tree (np. BVH), ponieważ umieszczenie geometrii w BSP-tree oznaczałoby powielanie i dzielenie geometrii szczegółów dla każdy przypadek.

Odwrotnie, duża niestandardowa siatka statyczna bez instancjonowania, taka jak scena miejska lub złożone środowisko wewnętrzne, zwykle używa drzewa BSP w celu poprawy wydajności pracy. Fakt, że BSP-Tree dzieli geometrię na granicach węzłów jest pomocny dla wydajności renderowania, ponieważ węzły BSP mogą być używane jako wstępnie zorganizowane partie renderowania trójkątów. Drzewo BSP może być również zoptymalizowane pod kątem okluzji, unikając konieczności rysowania części drzewa BSP, które są wiadomo, że stoi za inną geometrią.

Zobacz też: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial .

BSP jest najlepszy w środowisku miejskim.

Quadtree jest najlepszy, gdy używasz mapy wysokości dla terenu, itp.

Oktr jest najlepszy, gdy masz kępy geometrii w przestrzeni 3d, takich jak układ słoneczny.

BSP są dobrym rozwiązaniem do przyspieszania wykrywania kolizji, w zależności od używanego smaku. Są one szczególnie szybkie w testach punktowych i liniowych lub ray, nieco mniej szybkie i trochę bardziej skomplikowane dla rzeczy z głośnością.

Jeśli chodzi o ich wykorzystanie w grafice, BSP są dość przestarzałe. Ośmiornice dobrze sprawdzają się przy takich rzeczach jak ubój widoczności, podobnie jak drzewa AABB.

Nie mam dużego doświadczenia z BSP, ale mogę powiedzieć, że powinieneś iść z oktrees nad quadtrees, gdy scena, którą renderujesz, jest wysoka. Oznacza to, że wysokość jest większa niż połowa szerokości i głębokości-mała zasada. Ogólnie rzecz biorąc, oktrees nie przyniesie ogromnych kosztów w stosunku do quadtrees i mają potencjał, aby przyspieszyć wszystko przyzwoicie. YMMV.

Zazwyczaj te rzeczy nie mają jasnej odpowiedzi. Sugerowałbym, że A, B I C są wynikiem funkcji wielkości twojej przestrzeni i ilości rzeczy, które różnicujesz.

BSP jest lepszy dla mniejszej, prostszej przestrzeni, z którą chcesz zrobić tylko okluzję. Jeśli chcesz wszystkie przecięcia dla danego promienia, musisz uaktualnić do quad/octree.

Co do quadtree vs. octree-ile wymiarów Ci zależy? Dwa wymiary oznaczają czworokąt, cztery ośmiokąt. Jak wspomniano, jako quadtree może pracować w trzech przestrzeni, ale jeśli chcesz, aby każdy wymiar został odpowiednio potraktowany, oktree jest drogą do zrobienia.