bink.eu.org Open in urlscan Pro
121.74.247.119  Public Scan

Form analysis
0 forms found in the DOM

Text Content

BINK STUDIOS menu dark_mode


ABOUT BINK

Bink was created in 2015 as a random word to put in the company feild of an app
I was testing. Since then, Bink has become the front for all my work

close


PAGES

Fast Voxel Data Structures Procedual Planets Octree Raytracer Early Days


PROJECTS

Black Hole Snake Dicewars


OLD SITES

Old Website Very Old Website


FAST VOXEL DATA STRUCTURES

Voxels are a promising alternative to conventional rasterisation. If managed
right they allow for huge worlds, mass editing and fast ray tracing. I'm going
to teach you how to use the best data structures for managing your voxels.

I'm going to go over all the most common voxel data structures, how they work
and their advantages and disadvantages. I won't go too in depth into each data
structure but rather help you figure out what data structure is best for you.
One other thing to note is that the terminology to do with voxel data structures
is quite inconsistent within the community, so I'll be using the terminology I
see the most.


TLDR

Data StructureLarge WorldsFast EditsFast Ray Tracing Flat Grid✅ Grid Hierarchy✅✅
Octree/SVO/DAG✅🆗 Brickmap✅✅ SDF✅


FLAT GRID

A flat grid is the simplest way to store voxels. It's exactly what it sounds
like, a grid of voxels. A basic implementation would look like this:

let voxel_grid = [[[Voxel; X_SIZE]; Y_SIZE]; Z_SIZE];


Usually though it is implemented as a flat array for performance reasons:

let voxel_grid = [Voxel; X_SIZE * Y_SIZE * Z_SIZE];
let voxel = voxel_grid[x + y * X_SIZE + z * X_SIZE * Y_SIZE];


While it is very fast to edit it has some drawbacks. The first is that the
memory usage grows very fast (n3) giving an upper limit on how much of your
world can be loaded at once. The second is that it is slow to traverse as you
have to look up every voxel along the ray.


GRID HIERARCHY

A grid hierarchy is quite similar to a flat grid. It's different in that you
have multiple flat grids at different resolutions. At the bottom layer you have
the same flat grid as before. You then have grids of lower resolution that only
contain a single bit per voxel that indicate weather there is a voxel in the
grid below. When traversing a grid hierarchy you can use the lower resolution
grids to skip over large areas of empty space. This gives a very similar ray
traversal to an octree but without any pointers allowing you to do a lookup for
every layer at once making it much faster than an octree.

A grid hierarchy is not sparse, so its memory still grows at n3, but it is much
faster to traverse. It is also very fast to edit as you only need to set 1 bit
per layer, and you can set them all at once making it GPU friendly. Grid
hierarchies are so fast to create that I can rebuild the whole hierarchy every
frame when using a small world. They also are only slightly bigger than a flat
grid so all in all they are a great improvement over a flat grid.




OCTREE

So what if you want to load more data? Both a flat grid and a grid hierarchy
grow at n3, so you will run out of memory quite quickly. The solution is a
sparse data structure. The most simple sparse data structure is an octree. An
octree is a tree where each node has 8 children. The root node represents a cube
containing the whole world. Each child then represents ⅛ of the parent. This
continues until you reach a leaf node which represents a single voxel. A simple
implementation of an octree would have nodes that look like this:

struct Node {
    children: Option<[Node; 8]>,
    voxel: Option<Voxel>,
}


Each node stores its 8 children until you get to the bottom of the tree where
instead of storing its children a node stores the voxel data. But this isn't
great for performance. A better implementation is to store the octree in an
array. Now each node is represented as a u32 that either stores the index of its
8 children or some voxel data. This makes it a lot easier to edit and allows you
to easily send it to GPU.

struct Octree {
    nodes: Vec<u32>,
}


An octree looks like this (represented in 2D):

The advantage of an octree is that it greatly reduces memory usage. As you can
see in the picture above, the octree doesn't store the entire top left quadrant
of the world as there is nothing there. The disadvantage is that it is much
slower to traverse. To access a particular voxel you have to traverse down the
tree using the children pointers. But if you want a large world a sparse data
structure is a necessity. It is possible to use a hash map for faster access to
the nodes, but this uses more memory and is not very GPU friendly.


SPARSE OCTREE

A sparse octree is an octree, but each node doesn't have to have 8 children.
Instead of just storing a pointer to all 8 children it stores an index and a
child mask. The child mask is a bit mask that indicates weather each of the 8
children exist. The child pointer then points to however many of those children
exist.

A sparse octree can use up to an eighth of the memory of a normal octree without
losing any performance, so it is a nice improvement.


BRICK MAP

The implementation of a brick map is a bit out of scope, but you can read the
paper here. As a brick map has LOD you can do voxel cone tracing for fast global
illumination. It also can be streamed in and out allowing huge worlds to be
rendered. But due to the hierarchical nature it is still relatively slow to
edit.


SDF

A voxel SDF is a flat data structure where every air voxel stores the distance
to the closest solid voxel. This is the fastest data structure for ray tracing
allowing the most space to be skipped and only taking 1 lookup per DDA step.


CONCLUSION

As you can see, there are many voxel data structures for different purposes.
I've summarized the results in this table:

Data StructureLarge WorldsFast EditsFast Ray Tracing Flat Grid✅ Grid Hierarchy✅✅
Octree/SVO/DAG✅🆗 Brickmap✅✅ SDF✅

The best data structure is usually some combination of datastructures. For
example I use a brickmap with a grid hierarchy in alex. You could then have
another acceleration structure for doing physics and a different datastrucure
for writing to disk.

© 2024 Bink
freedns.afraid.org