Chciałbym móc renderować dużą populację małych niezależnie poruszających się obiektów w czasie rzeczywistym. Mogą się one poruszać jak rój, ale ich pozycje względne nie będą spójne – ich pozycja może zmieniać się arbitralnie w roju, a roje mogą się rozpaść i zreformować w dowolnym momencie.
Jakie podejście do budowania hierarchii woluminów ograniczających najlepiej pasowałoby do tej sytuacji? sposób na utrzymanie hierarchii, która jest nieoptymalna, ale wystarczająco dobra, która wymaga tylko częściowej aktualizacji każdej klatki? A może istnieje sposób na zbudowanie od podstaw hierarchii każdej klatki, która jest wystarczająco szybka, aby zapewnić płynną animację?
Liczba obiektów będzie zbyt duża, aby renderować bez hierarchii, ale z tego samego powodu spodziewam się, że tworzenie hierarchii będzie czasochłonne.
Po komentarzu Johna Calsbeeka, jeśli moja skupienie się na ograniczaniu hierarchii woluminów jest błędne i w tej sytuacji istnieje lepsze podejście do partycjonowania przestrzeni Odpowiedzieć odpowiednio. Szukam czegoś, co poradzi sobie z tym, co opisuję, w tym wszystkim, o czym nie pomyślałem.
Komentarze
- Czy celowo ograniczasz pytanie dotyczące hierarchii woluminów, czy jesteś otwarty na inne formy partycjonowania przestrzennego?
- @JohnCalsbeek I ' zredagowałem w celu wyjaśnienia – dziękuję za wskazanie mojego nieumyślne ograniczenie.
- Rozważ traktowanie ” roju ” jako pojedynczej jednostki, gdy roje się łączą; połącz je w jeden rój, gdy samotnik odejdzie zbyt daleko, staje się ” rojem ” jednego. Działa to najlepiej, jeśli roje są zwykle spójne, a samotnicy są rzadkością. Istnieje wiele fajnych sposobów na zabawę z ” rojem to pojedyncza jednostka „, na przykład pozwalanie członkom na przełączanie rojów tylko wtedy, gdy są w kontakcie lista jest długa.
Odpowiedź
Rozważ użycie mieszania przestrzennego, zwłaszcza jeśli twoje obiekty mają podobne rozmiary.
Zasadniczo podziel swój świat na komórki siatki o jednakowych rozmiarach (zarówno 2D, jak i 3D są prawidłowymi możliwościami w zależności od ilości ruchu w pionie). Przy każdej aktualizacji przypisz swój obiekt do każdego kosza, na który się nakłada – jeśli komórki mają przyzwoity rozmiar w stosunku do obiektów, większość obiektów powinna znaleźć się w jednym koszu.
Każdy kosz jest wstawiany do tablicy skrótów kluczem są współrzędne pojemnika. (Możesz również myśleć o tym jako o tablicy skrótów z wieloma wartościami dla tego samego klucza i wstawianiu obiektu raz dla każdej komórki, na którą się nakłada.)
W tym schemacie nie ma hierarchii do odbudowania, co sprawia, że dobrze nadaje się do scen dynamicznych. Nadal możesz testować wymiary komórki w porównaniu z ściętym stożkiem lub z okluderami na grubym poziomie i odrzucać wiele obiektów na raz. Ponadto łatwiej jest zarządzać tą strukturą przyrostowo – możesz zachować tę samą tablicę skrótów z ramki do ramki i przenosić obiekty z jednego pojemnika do drugiego tylko wtedy, gdy przekraczają granice komórki.
Odpowiedź
Możesz po prostu spróbować zwiększyć woluminy ograniczające nieco większe niż to konieczne, aby obiekty nie przekraczały swoich granic przy każdym ruchu, ale z drugiej strony, i tak musiałbyś odbudować strukturę od czasu do czasu.
Lub istnieje Hierarchia przedziałów ograniczających , która próbuje dokładnie rozwiązać ten problem scenariusza.
Albo artykuł autorstwa Ingo Walda, Solomona Boulosa i Petera Shirleya, zatytułowany Zdeformowalne sceny z ray tracingu przy użyciu dynamicznych ograniczeń objętościowych zainteresowań.
Odpowiedź
Chciałbym dodać do tego praktyczną perspektywę.
Niech przedmowa, że działam tutaj na ograniczonych informacjach:
- Nie wiem, jak m wszelkie obiekty, z którymi masz do czynienia.
- Nie wiem, do czego dokładnie służy twoja struktura przyspieszenia. Odstrzał Frustum? Śledzenie promieni? Wykrywanie kolizji między obiektami w BVH?
Idąc dalej, założę, że mówisz o ubijaniu kilku tysięcy obiektów w kształcie frustum.
Liczba obiektów będzie zbyt duża, aby renderować bez hierarchii, ale z tego samego powodu oczekuję, że budowanie hierarchii będzie czasochłonne.
Twierdzę, że jeśli musisz odwiedzić każdy obiekt w każdej klatce, aby obliczyć BVH, eliminowanie ich bezpośrednio i bez BVH jest w rzeczywistości szybsze. To oczywiście zależy od implementacji uboju frustum. Objętości ograniczające wszystkich obiektów powinny być przechowywane w pamięci ciągłej. Powoduje to bardziej wydajne wykorzystanie pamięci podręcznej procesora i umożliwia dalszą optymalizację przy użyciu instrukcji SIMD. DICE zawiera całą prezentację na ten temat: Culling the Battlefield: Data Oriented Design in Practice
Prezentacja wspomina również o jeszcze większym przyspieszeniu uboju, używając prostej siatki.
Ponieważ zakładam, że większość baz kodu 3D / symulacji / gier ma już jakiś rodzaj Klasa BVH i nie wiem, jak ważne jest dla ciebie uzyskanie NAJLEPSZEJ wydajności uboju, chciałbym przedstawić kilka argumentów za trzymaniem się BVH:
W zależności od używanej metody, konstruowanie BVH może być szybkie i proste.
Moja obecna implementacja binarnego BVH (każdy węzeł może mieć tylko zero lub dwoje dzieci, a każdy węzeł-liść przechowuje tylko jeden element), która jest zaprojektowana do szybkiego zajmuje około 0,18 ms dla 1137 obiektów na jednym wątku i7-5960X @ 3,89 GHz . Jestem pewien, że może być szybsze. Konstrukcja jest wykonywana bez ponownego przydzielania pamięci w procesie (to podwoiło wydajność konstrukcji).
Chociaż SAH może wygenerować najlepszy współczynnik BVH, zajmuje to dużo czasu. SAH jest dobre dla rzeczy, które możesz wstępnie obliczyć, takich jak siatki kolizyjne. W czasie wykonywania możesz następnie umieścić siatki kolizyjne w BVH, który jest bardziej odpowiedni do konstrukcji w czasie rzeczywistym.
Szybka i prosta metoda konstrukcji BVH (ta, którą I „m używam obecnie) to sortowanie wszystkich obiektów na osi (na przykład najdłuższej osi nadrzędnego AABB”) i dzielenie kolekcji w środku.
Aby jeszcze bardziej przyspieszyć, oblicz węzły AABB PO skonstruowaniu drzewa, poprzez połączenie dwóch węzłów potomnych AABB węzła nadrzędnego. Pozwala to uniknąć iteracji przez wszystkie obiekty (kolejne 2x przyspieszenie). Jest to jednak możliwe tylko wtedy, gdy kryterium podziału nie opiera się na AABB rodzica.