Jaki jest stan techniki Partycjonowania kosmicznego w grach? [Zamknięte]

Wiem o drzewach BSP, oktatach i portalach, które były używane przez długi czas. Ale współczesne gry nadal korzystają z tych systemów lub używają nowych rzeczy?

Jeśli jest to możliwe z zaletami i wadami, rozważ renderowanie i wykrywanie kolizji.

Tak, na przykład silnik Unreal 3 nadal używa BSP - głównie dlatego, że jest używany podczas procesu CSG. Doom3 / id tech 4 używa portali i myślę, że przeczytałem coś, co id Tech 5 powrócił do drzew BSP. Niektóre gry używają także oktetów. W grze rozumiem, że UE3 przeszedł na bardziej dynamiczne podejście z zapytaniami o okluzję, ale byłbym zaskoczony, gdyby nie używali BSP, aby przynajmniej określić, które siatki statyczne są widoczne. Inne gry mogą po prostu używać wygładzania widoku (np. Cywilizacja). To zależy od tego, jaki rodzaj gry wyglądasz.

Powodem, dla którego BSP i inne rzeczy są nadal dostępne, jest to, że nie możesz zrobić nic lepszego. Jeśli masz geometrię statyczną, BSP jest świetny, jeśli zbudujesz go poprawnie. Wymaga to jednak napisania konstruktora BSP, co jest trudne (ale może się zdarzyć za darmo, jeśli Twoje rozwiązanie CSG korzysta z jednego!) Oktawy i bardziej dynamiczne rozwiązania (takie jak poleganie na zapytaniach okluzji dla wszystkich) są prostsze do wdrożenia, mają dłuższy czas działania kosztuje, ale nie wymaga (kosztownego) wstępnego przetwarzania poziomów. Jest to kompromis, który niektóre gry są skłonne zrobić (na przykład Crytek chce, aby wszystko działało w czasie rzeczywistym, więc nie spędzają czasu na tworzeniu statycznej struktury akceleracji.) Inne podejścia uruchomieniowe to na przykład rasteryzacja oprogramowania na procesor i wykonywanie zapytań dotyczących okluzji na procesorze (jest to wykorzystywane przez silnik Frostbite).

Aby uzyskać naprawdę nowoczesne podejście, spójrz na Umbra , która jest oprogramowaniem pośrednim dla zapytań dotyczących widoczności. Jeśli przeszukujesz trochę Internet, powinieneś znaleźć tezę magisterską opisującą wczesne początki Umbry.

Konkluzja: To, czy chcesz użyć BSP / Octree / no AS, będzie w dużej mierze zależało od rodzaju gry, którą chcesz stworzyć. Jeśli twoje poziomy są w większości statyczne, powinieneś to wykorzystać i zbudować strukturę statycznego przyspieszenia. Jeśli wszystko jest dynamiczne, potrzebujesz oczywiście innego podejścia.

W celu wykrycia kolizji przyjrzałbym się Bullet i PhysX oraz ich algorytmom wykrywania kolizji. Ale mam wrażenie, że rozwiązania fizyki są mniej związane z widocznością niż kiedyś - rozwiązanie fizyki może chcieć użyć BVH opartego na GPU, w takim przypadku nie ma większego sensu próbować używać tego do zapytań o widoczność.

Naprawdę nie wiem, jakich silników nowej generacji używają obecnie, ale powiem ci, co wiem. Łatwo jest pomylić optymalizację ze strukturą danych wykorzystywaną do pomocy w tej optymalizacji. Wszystkie wymienione poniżej rzeczy są jednak przeznaczone do optymalizacji, ale wskażę, które są konkretnymi strukturami danych.

BSP : Struktura danych - Do wykrywania przecięcia dynamicznych obiektów ruchomych ze statyczną geometrią świata. Używany do prawidłowego wykrywania kolizji i renderowania geometrii bez zbuffera, ale nie jest już używany do renderowania, ponieważ mamy teraz wystarczającą pamięć na bufor az. Są one technicznie generowane nieco inaczej, ale nadal są uważane za ten sam typ drzewa. Wymaga wstępnego przetwarzania.

Octree lub Kd-Tree : Struktura danych - służy do określania, które obiekty znajdują się w tej samej „komórce” lub obszarze, aby uniknąć sprawdzania wszystkich obiektów dynamicznych n ^ 2.

Nie są to jedyne, ale prawdopodobnie najczęstsze. Istnieje również wiele optymalizacji, które pozwalają silnikowi ogólnie unikać renderowania geometrii. Ale następujące po prostu wycinają geometrię i to zwykle wszystko, czego używa:

Portale : Technicznie nie jest to struktura danych, ale wymaga specjalnego, aby wykonać culling. Służy do ograniczania widoczności geometrii świata i dynamicznej geometrii obiektu z widoku. Wymaga wstępnego przetwarzania, aby podzielić świat na obszary, które moim zdaniem. Ale tak naprawdę nie wdrożyłem tego, więc nie wiem.

Wyrównywanie okluzji : Optymalizacja - służy do wyrównywania widoczności dla dowolnych obiektów, prawdopodobnie obiektów dynamicznych.

Regularne maskowanie rzutni : Optymalizacja - eliminuje obiekty, których nie ma w widoku kamery.

Więcej wygładzania rzutni : Optymalizacja - Regularne wygłuszanie rzutni można jeszcze bardziej zoptymalizować za pomocą oktetu. Możesz wyciąć całe komórki oktetu, które znajdują się za kamerą lub nie są widoczne. Obejmuje to obszary terenu (jeśli jesteś na zewnątrz). Cokolwiek nie jest unicestwione przez oktodę, wykonasz „zwykłe wyrównywanie rzutni”. Następnie cokolwiek pozostało, oddałbyś.

Culling backface : Optimization - geometria culls odwrócona od kamery, aby zapobiec rasteryzacji. Zwykle odbywa się to sprzętowo, jeśli stan renderowania jest ustawiony poprawnie.

Struktury danych przypadków specjalnych:

Drzewa AABB lub Drzewa sferyczne : Są to swoiste struktury danych przypadków. Przekształcają wklęsły kształt w wypukły. Na przykład postać z kościami jest technicznie wklęsła. Rozbija go na mniejsze wypukłe kawałki. Może być stosowany jako optymalizacja do wykrywania kolizji, eliminacji widoczności obiektów dynamicznych (zwykle) i ułatwia wykonywanie testów przecięcia, ponieważ jest wypukły. Byłyby to np. Oktawa, ponieważ są to zwykle obiekty dynamiczne. Można je również wykorzystać do optymalizacji optymalizacji usuwania okluzji.

Nie ma powodu, dla którego musisz używać pojedynczej struktury do reprezentowania wszystkiego (np. Wykresu sceny). Moim zdaniem lepiej byłoby używać różnych struktur danych do różnych zadań, niż próbować użyć jednego drzewa ogólnego przeznaczenia. Na przykład, nad silnikiem, nad którym obecnie pracuję, planuję zaimplementować kombinację drzewa BSP / Octree / AABB z następującymi optymalizacjami: wygładzanie okluzji, rzutnia i, oczywiście, wygładzanie tylnej powierzchni. Oznacza to, że będę mieć jedno drzewo bsp, jeden oktytę i prawdopodobnie wiele drzew aabb w obrębie tego oktatu.

Wybór najlepszych struktur danych i algorytmów / optymalizacji jest prawdopodobnie największą i najbardziej korzystną rzeczą, jaką możesz zrobić dla swojego silnika.