Sparse Voxel Octrees

if you've been around the voxel Dev sphere  you might have heard sparse voxel octree or   SVO for short get thrown around but what is it  actually? well let's start by breaking down the   name starting from the end according to Wikipedia  a Voxel represents a value on a regular Grid in   three-dimensional space which might come off as  weird as we usually think of voxels as just Cubes   but just like the 2D counterparts voxels are just  values on the grid but they're usually represented   by a cube this also leads to the main issues of  voxels if you want the high resolution model you   have to have a high resolution grid which takes  a lot of memory especially since a lot of the   grid will represent nothing more than empty space  that's where svos come in the idea behind SVO is   that we only store voxels that we need instead of  filling up every single voxel in 3D space we only   create voxels where they're actually something  to render now what is a SVO well before we can   understand that let's understand what an octree is  an octree is a data structure used to partition 3D   space into hierarchy of smaller cubes called  octants these octins can also divide their own   space into octans this happens recursively until  you hit the desired resolution The difference between an octree and a sparse vocal octree is how the handle dividing sparse voxel octree does  not always subdivide into eight octants while octrees always do now the implementation of a sparse voxel octree can be a bit complicated  but the basic idea is pretty simple we start   off by creating a large Cube that represents our  3D space an example of the structure might look   something like this where we have an node class  which includes a Boolean for whether it's a leaf   node or not eight children pointers and some voxel  data we might want to store this node struct is   then used in an octree class that keeps track of  the size of the tree the maximum resolution of the   tree and the root node to populate the tree we  need an insert function but before we get into   the insert function we have some groundwork to  cover take this simple octree as an example   each of these octants have a position of 0 or  1 in X Y and Z if we take the binary value of   those three axis for every single octant we get  an index that goes from 0 to 7. the octant with position 0 0 0 is index 0 and the octant with position 1 0 0 is index 1 and so on now that   we know how to get the index value we can look  at the insert function the goal of the insert   function is to call itself recursively with the  correct octant to do that we need these lines of   code the first line finds the size of the parent  node using the size of the tree and depth, depth being how far down the tree we are root being at  zero after finding the size we can use it to find   the center of the parent node which is a bit more  complicated finding the center of the root node   is easy we just add half of the size but how do  we find the center if we're further down the tree? taking this simple quadtree as an example to find  the center of this corner we first have to know   how we got here our parent in this case is at  position 1 1 so that's the path we took to get   here if we take that and multiply with the size  of our parent we get the position of our parent   after finding the paraent position finding the  centers as easy as adding half the size now if   we were to go even further down the tree we would  have to share every choice we made to do that with   put our position in front of the position given  to us and pass it down that would look like this   here's the code for the algorithm this takes  into account which octant that point belongs   to by comparing it to the center of the parent  and keeps recursively creating nodes for the   octant the point is in so what are the benefits  of using a sparse voxel octree well first off it   can dramatically improve performance by only rendering in the voxels that we actually need we reduce the   amount of processing power required to render  a 3D scene but it also allows us to store a   lot more voxels in memory because of the memory  optimized way it stores the voxels but as always   there's drawbacks SVOs are great at storing  and rendering voxels but they struggle with   collision detection and dynamic objects so there  you have it that's a quick overview of sparse voxel octrees if you have any questions feel free  to leave them down below thanks for watching

Channel: Ozown

Views: 11,231

Keywords: octree, voxel, rendering, opengl, c++, explained

Id: NjCp-HIZTcA

Length: 3min 24sec (204 seconds)

Published: Sun Apr 02 2023