Clarification about octrees and how they work in a Voxel world

Question

I read about octrees and I didn't fully understand how they world work/be implemented in a voxel world where the octree's purpose is to lower the amount of voxels you would render by connecting repeating voxels to one big "voxel".

Here are the questions I want clarification about:

• What type of data structure would you use? How could turn a 3-D array of voxels into and array that has different sized voxels that take multiple locations in the array?
• What are the nodes and what are they used for?
• Does the octree connect the voxels so there are ONLY square shapes or could it be a rectangle or a L shape or an entire Y column of voxels or what?
• Do the octrees really improve performance of a voxel game? If so usually by how much?

Answer 1

Quick answers:

• A tree:
  Each node has 8 children, top-back-left, top-back-right, etc. down to a certain level
  The code for this can get quite complex, especially if the voxels can change at runtime.
• The type of voxel (colour, material, a list of items)
• yep. Cubes only
  More specifically 1x1, 2x2, 4x4, 8x8 etc. It must be an entire node.
  If you really want to you could define some sort of patterns, but its no longer a octdtree.
• yeah, but it depends on your data. Imagine describing 256 identical blocks individually, or describing it once (like air in Minecraft)

I'd start with trying to understand quadtrees first. You can do that on paper, or make a test program with it. You'll answer these questions yourself if you experiment

Answer 2

An octree done correctly can also help you with neighbour searches which enable you to determine if a face is considered to be "visible" (ie so you end up with a hull of voxels visible). Once you've established your octree you then use this to store your XYZ coords which you then extract into a single array. You then feed this array into your VERTEX Buffer (GL solutions require this) which you can then render in chunk forms as needed (as the camera moves forward etc).

Octree's also by there very nature collapse Cubes into bigger ones if there are ones of the same type... much like Tetris does when you have colors/shapes that "fit" one another.. this in turn can reduce your vertex count and at render you're really drawing a combination of squares and rectangles

If done correctly you will end up with a lot of chunks that only have the outfacing "faces" visible in the vertex buffers. Now you then have to also build your own Occlusion Culling algorithm which then reduces the visibility ontop of this resulting in less rendering required.

I did an example here:

https://vimeo.com/71330826

notice how the outside is only being rendered but the chunks themselves go all the way down to the bottom even though the chunks depth faces should cancel each other out? (needs more optimisation). Also note how the camera turns around and the faces are removed from the rendering buffers?