Przechowywanie wokseli dla silnika wokseli w C ++

Próbuję napisać mały silnik wokseli, ponieważ jest fajny, ale staram się znaleźć najlepszy sposób przechowywania rzeczywistych wokseli. Wiem, że będę potrzebować kawałków, więc nie muszę mieć całego świata w pamięci, i wiem, że muszę je renderować z rozsądną wydajnością.

Czytam o oktatach i z tego, co rozumiem, zaczyna się od 1 sześcianu, w tym sześcianie może być jeszcze 8 kostek, a we wszystkich tych 8 kostkach może być kolejne 8 kostek itp. Ale nie sądzę, że pasuje to do mojego silnika wokseli, ponieważ moje kostki wokseli / przedmioty będą miały dokładnie ten sam rozmiar.

Tak więc inną opcją jest po prostu utworzenie tablicy o rozmiarze 16 * 16 * 16 i utworzenie z niej jednego kawałka i wypełnienie jej przedmiotami. Części, w których nie ma żadnych przedmiotów, będą miały wartość 0 (0 = powietrze). Ale obawiam się, że to zmarnuje dużo pamięci i nie będzie bardzo szybkie.

Następnie inną opcją jest wektor dla każdej porcji i wypełnienie go kostkami. A sześcian utrzymuje swoją pozycję we fragmencie. Oszczędza to pamięć (bez bloków powietrznych), ale znacznie wolniej szuka kostki w określonym miejscu.

Tak naprawdę nie mogę znaleźć dobrego rozwiązania i mam nadzieję, że ktoś może mi w tym pomóc. Więc czego byś użył i dlaczego?

Ale innym problemem jest renderowanie. Sam odczyt każdego fragmentu i przesłanie go do GPU przy użyciu OpenGL jest łatwe, ale bardzo powolne. Generowanie jednej siatki na porcję byłoby lepsze, ale oznacza to, że za każdym razem, gdy łamię jeden blok, muszę odbudowywać cały fragment, co może zająć trochę czasu, powodując niewielką, ale zauważalną czkawkę, czego oczywiście też nie chcę. To byłoby trudniejsze. Jak więc renderowałbym kostki? Po prostu utwórz wszystkie kostki w jednym buforze wierzchołków na porcję i renderuj to, a może spróbuj umieścić to w innym wątku, czy jest inny sposób?

Dzięki!

Przechowywanie bloków jako pozycji i wartości jest w rzeczywistości bardzo nieefektywne. Nawet bez narzutu spowodowanego przez używaną strukturę lub obiekt, musisz przechowywać 4 różne wartości na blok. Sensowne byłoby użycie go zamiast metody „przechowywania bloków w stałych tablicach” (tej, którą opisałeś wcześniej), gdy tylko jedna czwarta bloków jest solidna, a w ten sposób nie bierzesz nawet innych metod optymalizacji konto.

Octrees są w rzeczywistości świetne dla gier opartych na wokselach, ponieważ specjalizują się w przechowywaniu danych z większymi funkcjami (np. Łatkami tego samego bloku). Aby to zilustrować, użyłem kwadratu (w zasadzie oktetów w 2d):

To jest mój zestaw początkowy zawierający kafelki 32x32, co równa się 1024 wartościom:

Przechowywanie tego jako 1024 osobnych wartości nie wydaje się tak nieefektywne, ale po osiągnięciu rozmiarów map podobnych do gier, takich jak Terraria , ładowanie ekranów zajęłoby wiele sekund. A jeśli zwiększysz go do trzeciego wymiaru, zacznie on zajmować całą przestrzeń w systemie.

Czwórki (lub ósemki w 3D) mogą pomóc w tej sytuacji. Aby je utworzyć, możesz albo przejść z kafelków i zgrupować je razem, albo przejść z jednej ogromnej komórki i dzielić ją, aż dotrzesz do płytek. Wykorzystam pierwsze podejście, ponieważ łatwiej jest to wyobrazić.

Tak więc w pierwszej iteracji grupujesz wszystko w komórki 2x2, a jeśli komórka zawiera tylko kafelki tego samego typu, upuszczasz kafelki i po prostu przechowujesz typ. Po jednej iteracji nasza mapa będzie wyglądać następująco:

Czerwone linie oznaczają to, co przechowujemy. Każdy kwadrat ma tylko 1 wartość. Spowodowało to zmniejszenie rozmiaru z 1024 wartości do 439, co stanowi spadek o 57%.

Ale znasz mantrę . Przejdźmy krok dalej i zgrupuj je w komórki:

Zmniejszyło to liczbę przechowywanych wartości do 367. To tylko 36% oryginalnego rozmiaru.

Musisz oczywiście dokonać tego podziału, dopóki każda 4 sąsiednia komórka (8 sąsiadujących bloków w 3d) wewnątrz fragmentu nie zostanie zapisana w jednej komórce, zasadniczo przekształcając fragment w jedną dużą komórkę.

Ma to również inne zalety, głównie podczas kolizji, ale możesz chcieć utworzyć do tego osobny oktytę, który dba tylko o to, czy pojedynczy blok jest bryły, czy nie. W ten sposób zamiast sprawdzania kolizji dla każdego bloku wewnątrz porcji, możesz po prostu zrobić to z komórkami.

Istnieją ósemki, aby rozwiązać dokładnie opisany problem, umożliwiając gęste przechowywanie rzadkich danych bez dużych czasów wyszukiwania.

Fakt, że woksele są tego samego rozmiaru, oznacza po prostu, że oktawa ma stałą głębokość. na przykład. dla fragmentu 16 x 16 x 16 potrzebujesz maksymalnie 5 poziomów drzewa:

• korzeń porcji (16 x 16 x 16)
  • oktant pierwszego poziomu (8x8x8)
    • oktant drugiego poziomu (4x4x4)
      • oktant trzeciego poziomu (2x2x2)
        • pojedynczy woksel (1x1x1)

Oznacza to, że masz co najwyżej 5 kroków, aby dowiedzieć się, czy woksel jest w określonej pozycji w części:

• korzeń porcji: czy cały fragment ma tę samą wartość (np. całe powietrze)? Jeśli tak, to koniec. Jeśli nie...
  • pierwszy poziom: czy oktant zawierający tę pozycję ma tę samą wartość? Jeśli nie...
    • drugi rząd...
      • trzeci poziom ...
        • teraz adresujemy pojedynczy woksel i możemy zwrócić jego wartość.

Znacznie krótszy niż skanowanie nawet 1% drogi przez zestaw do 4096 wokseli!

Zauważ, że pozwala nam to kompresować dane wszędzie tam, gdzie występuje pełny oktant o tej samej wartości - niezależnie od tego, czy jest to całe powietrze, cała skała, czy coś innego. Tylko tam, gdzie oktany zawierają mieszane wartości, musimy dalej dzielić, aż do limitu pojedynczych wokseli liściowych węzłów.

Aby zwrócić się do dzieci z kawałka, zwykle postępujemy w kolejności Mortona , coś takiego:

1. X- Y- Z-
2. X- Y- Z +
3. X- Y + Z-
4. X- Y + Z +
5. X + Y- Z-
6. X + Y- Z +
7. X + Y + Z-
8. X + Y + Z +

Nasza nawigacja w węźle Octree może wyglądać mniej więcej tak:

GetOctreeValue(OctreeNode node, int depth, int3 nodeOrigin, int3 queryPoint) {
    if(node.IsAllOneValue)
        return node.Value;

    int childIndex =  0;
    childIndex += (queryPoint.x > nodeOrigin.x) ? 4 : 0;
    childIndex += (queryPoint.y > nodeOrigin.y) ? 2 : 0;
    childIndex += (queryPoint.z > nodeOrigin.z) ? 1 : 0;

    OctreeNode child = node.GetChild(childIndex);

    return GetOctreeValue(
                child, 
                depth + 1,
                nodeOrigin + childOffset[depth, childIndex],
                queryPoint
    );
}