Jaką strukturę danych należy zastosować do przedstawienia terenu wokselowego?

Według strony Wikipedii o wokselach „[...] pozycja woksela jest wywnioskowana na podstawie jego pozycji względem innych wokseli (tj. Jego pozycji w strukturze danych, która tworzy pojedynczy obraz wolumetryczny)”.

Jak wdrożyć taką strukturę danych? Myślałem o oktawie, ale zastanawiam się, czy jest coś jeszcze, o czym nigdy nie słyszałem.

Pierwszy. Napiszmy, co wiemy o każdym wokselu:

voxel = (x, y, z, color) // or some other information

Ogólne miejsce do przechowywania

Ogólny sposób jest po prostu następujący:

set of voxels = set of (x,y,z, color)

Zauważ, że tryplet (x, y, z) jednoznacznie identyfikuje każdy woksel, ponieważ woksel jest punktem w przestrzeni i nie ma możliwości, aby dwa punkty zajmowały jedno miejsce (myślę, że mówimy o statycznych danych wokseli).

Proste dane powinny wystarczyć. Ale w żadnym wypadku nie jest to szybka struktura danych.

Renderowanie jest AFAIK wykonywane przez algorytm scanline. Artykuł Tom's Hardware na temat wokseli zawiera obraz algorytmu scanline .

Szybkie wyszukiwanie

Jeśli potrzebne jest szybkie wyszukiwanie, najszybszą strukturą danych dla wyszukiwania jest skrót (inaczej tablica, mapa ...). Musisz więc zrobić z niego skrót. Naiwnie chcemy po prostu najszybszego sposobu na uzyskanie dowolnego elementu:

array [x][y][z] of (color)

• Ma O (1) do wyszukiwania wokseli za pomocą współrzędnych x, y, z.

• Problem polega na tym, że jego wymagania przestrzenne to O (D ^ 3), gdzie D jest zakresem każdej liczby x, y i z (zapomnij liczbę rzeczywistą, ponieważ gdyby były znakami, które mają zakres 256 wartości, byłoby 256 ^ 3 = 2 ^ 24 == 16 777 216 elementów w tablicy).

Ale to zależy od tego, co chcesz zrobić z wokselami. Jeśli renderowanie jest tym, czego chcesz, to prawdopodobnie ta tablica jest tym, czego chcesz. Ale problem z magazynowaniem wciąż pozostaje ...

Jeśli problemem jest przechowywanie

Jedną z metod jest użycie kompresji RLE w tablicy. Wyobraź sobie kawałek wokseli (zbiór wokseli, w których woksele mają stałą wartość jednej współrzędnej ... jak płaszczyzna, na przykład z = 13). Taki kawałek wokseli wyglądałby jak prosty rysunek w MSPaint . Powiedziałbym, że model wokselowy zajmuje zwykle ułamek wszystkich możliwych miejsc (przestrzeń D ^ 3 wszystkich możliwych wokseli). Wierzę, że „weź parę z tripletu współrzędnych i ściśnij pozostałą oś” załatwi sprawę (na przykład weź [x] [y] i dla każdego elementu ściśnij wszystkie woksele na osi z przy danym x, y .. . powinno być 0 do kilku elementów, RLE dobrze by się tu spisało):

array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color 

• Używa go Ken Silverman w swoim Voxlap. Jego kompresja RLE może różnić się od odmiany mojej.
• Carmack wspomniał także o kompresji RLE na wokselach. Btw, John Carmack zoptymalizował PVS w Quake, kompresując go przez RLE .
• Może nie być najlepszym sposobem przechowywania dowolnych danych wokseli, takich jak ten.

Inną metodą rozwiązania problemu z pamięcią byłoby użycie tablicy zamiast struktury danych drzewa:

tree data structure  = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to

• Octree, jak wspomniał Nick. Powinien kompresować woksele. Octree ma nawet przyzwoitą prędkość wyszukiwania, myślę, że to trochę O (log N), gdzie N to liczba wokseli.
• Octree powinien mieć możliwość przechowywania przyzwoicie dowolnych danych wokseli.

Jeśli woksele są uproszczoną mapą wysokości, możesz przechowywać właśnie to. Lub Możesz przechowywać parametry do funkcji, która generuje mapę wysokości, czyli procedury generuje ją ...

I oczywiście możesz połączyć wszystkie możliwe podejścia. Ale nie przesadzaj, chyba że sprawdzisz, czy Twój kod działa i zmierzysz, że jest NAPRAWDĘ szybszy (więc warto go zoptymalizować).

TL; DR

Oprócz Octrees jest kompresja RLE z wokselami, Google „Voxlap”, „Ken Silverman” ...

Zasoby

Istnieje lista zasobów i dyskusja na temat sposobu szybkiego renderowania wokseli, w tym dokumenty i kod źródłowy .

Istnieją dwa różne aspekty struktury danych, o których mogą mówić.

Struktury tablicowe

Gdy odwołujesz się do elementu tablicy o dowolnej liczbie wymiarów, weź pod uwagę, że sama tablica po przejściu wskaźników (np. myArray[4][6][15]) Wie, co jest w tej lokalizacji. Jeśli to, co znajduje się w tym miejscu, to woksel, woksel nie musi dodatkowo rejestrować własnych współrzędnych x, y i z - tablica zawierająca woksel określa domyślnie swoją lokalizację na świecie na podstawie lokalizacji indeksowanej przez tablicę.

Powodem tego jest to, że arytmetyka wskaźnika używana do tego rodzaju dostępu do tablicy jest z natury szybka i ogólnie mówiąc, stanowi podstawę dla większości szybkich (często nazywanych „natywnymi”) tablic występujących w różnych językach. Minusem tych tablic jest to, że muszą mieć elementy o równej wielkości w bajtach, aby wspomniana arytmetyka wskaźnika mogła być zastosowana.

Octrees

(Zwracam uwagę na tę sekundę, ponieważ jest to mniej prawdopodobne, do czego odnosi się wikipedia, a implementacje wokseli nie wymagają użycia oktetów, chociaż prawie wszystkie współczesne używają oktetów).

Węzeł główny oktetu jest pojedynczą, niepodzielną kostką. Ustawmy przykład. Powiedzmy, że korzeń waszego oktetu, sam środek sześcianu, znajduje się {0, 0, 0}w przestrzeni 3D. Gdy zaczniesz umieszczać obiekty w tej przestrzeni (czytaj: więcej niż jeden obiekt), nadszedł czas, aby dalej podzielić oktodę. W tym miejscu dzieli się na 8 ( okt ), dzieląc go na 3 płaszczyzny, przy czym płaszczyzny te to płaszczyzny xy, xz i yz. Twoja oryginalna kostka zawiera teraz dokładnie 8 mniejszych kostek. Każdy z tych podwęzłów jest ustawiony jako odsunięcie od centralnej kostki nadrzędnej . To znaczy, że na przykład sześcian leżący w dodatniej oktanie xyz miałby przesunięcie od środka rodzica / zawierającego środek dokładnie{root.width / 4, root.height / 4, root.depth / 4}. Zamiast określać pozycję bezwzględną dla każdego podwęzła, bardziej logiczne jest rozważenie węzła nadrzędnego jako źródła jego przestrzeni potomnej. W ten sam sposób działają wykresy scen.

Wystarczy to zobaczyć na rysunku 2D, gdzie narysujesz kwadrat i podzielisz go na 4 równe regiony. Gdyby, podobnie jak nasz główny węzeł oktowy, środek kwadratu nadrzędnego został uznany za {0, 0}, wówczas 4 środki kwadratów podrzędnych byłyby

{root.width / 4, root.height / 4}, {-root.width / 4, root.height / 4}, {root.width / 4, -root.height / 4}, {-root.width / 4, -root.height / 4}

... W stosunku do ich rodzica - ta sama zasada jak w 3D.

Możesz użyć RLE. Ale możesz użyć SVO (Sparse Voxel Octree), id Tech 6 używa SVO. SVO jest techniką renderowania grafiki komputerowej 3D z wykorzystaniem metody raycasting lub czasami ray tracingu do reprezentacji danych w postaci oktetów.

Technika ta jest nieco inna, ale ogólnie polega na generowaniu i przetwarzaniu kadłuba punktów (rzadkich wokseli), które są widoczne lub mogą być widoczne, biorąc pod uwagę rozdzielczość i rozmiar ekranu.

Użyj raycastingu, ponieważ jest szybszy.

Zasadniczo można uniknąć struktury danych 3D dla terenu. Zamiast tego możesz użyć mapy wysokości . Może to być bardzo tanio i skutecznie weryfikowane w środowisku uruchomieniowym. Z mojego doświadczenia wynika, że ​​śledzenie minimalnej wysokości, którą musisz wyrenderować w każdej kolumnie, a także czasami kąty start-stop-top, opłaca się, abyś mógł również wyrównać kolumny tła.

Oto jeden, który zrobiłem dawno temu: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash

Jeśli w terenie znajduje się niewielka liczba nawisów, jaskiń lub innych elementów, których nie można przedstawić za pomocą mapy wysokości, możesz mieć otwory w mapie wysokości i mieć alternatywną reprezentację, np. Prawdziwe obiekty wokselowe 3D, które wypełniają tylko te zlokalizowane miejsca, w których kosztują środowisko wykonawcze jest uzasadnione.

Rzadkie reprezentacje wokselowe są tego warte, gdy masz duże prawdziwe światy wokselowe. John Carmack rozmawia o nich od kilku lat ...