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
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 .