In this video I will give a quick overview of what a sparse voxel octree is. This is a concept that is brought up a lot in voxel development and I wanted to shed some light on it.
Duude this is great! - No 2 minutes long intro - No 2 minutes long outro - Gets straight to the point - Explains code clearly and concisely - Great visuals + animation - Not too fast - Not too slow Love it! Keep it up!
Nice video! The next step is "brickmaps" where you store a small, dense voxel grid at each leaf instead of a single voxels, such as 8x8x8 or 32x32x32. Since surface details tend to exist around the same boundary, this can get you a lot more detail without as much overhead from the tree structure.
Very nice work. The animations are very smooth and the explanations are very clean. Some people would take 20 minutes to explain the concept so this is amazing!
Nice, this video inspires me to make my own voxel engine, but I'm too dumb and too tired in life to attempt such a task. However it's good to know the concepts. Helps you understand how it works. Thanks 👍
Really happy that the video could help! I would also like to add that I am definitely not qualified either, I was just really interested in the topic so I pushed through the difficulty.
@@Ozown I think for everybody they start off feeling not qualified, and then one day you're trying to optimize memory or something similar in your voxel engine and you realize you've just invented some new efficient algorithm :')
Great video Ozown! I wish this explanation style was more common. Since childhood I always felt my mind had a fast CPU but limited RAM, so I prefer _fast & repetitive_ over _slow & elaborate._ Alas, all school systems adhere to the latter, which never worked for me.
Minor clarification: SVO's work pretty well for collision detection, but it depends what exactly you need. Checking a point is a tree simple traversal. There are algorithms to do efficient ray traversal in an SVO such that you walk the leaf nodes while sweeping the ray. The algorithm is not simple, but it is doable. I suspect you can sweep a box efficiently as well, but I've not done it myself.
Great video! Good quality, good explanation, good stuff :) It's probably going to blow up with a few thousand views in the following days and you deserve it!
An excellent video! Short and full of all the information one may need while looking for the solution! Especially liked the end when you said what it isn't good for.
For the animation I use 3b1b's math animation library. Here is the GitHub link: github.com/3b1b/manim. For the voice I use a blue yeti as the microphone and audacity as the software. Hope that helps!
Yeah it would be really cool. The project that motivated me to try out voxels was john lin's. Seems like games made with voxels would be really interesting!
So basically the 3D version of how maps are stored first you assume the map is flat, divide into 4 quadrants until each quadrants has less than n number of points of interests or details in the sector
Close but a bit different if I am not mistaken on the data-structure you are describing. An Octree has a fixed depth, which means that how many subdivisions that will be done is decided before hand. The information is only stored at the lowest depth. Hope that helps and thanks for watching!
I have a question: Where are all these nodes allocated in memory? Are all the child nodes heap allocated in different places somewhere? Or do we do one big arena allocation upfront that has enough space for the entire oct-tree if it was completely filled with voxels?
I went with a dynamic array route. Everything is stored in a 32 bit int vector where different bits represent different parts of the node data. For example the first 8 bits represent the 8 different children nodes and whether they exist or not. I did however start with dynamically allocating everything in the heap and then changed it over to a dynamic array after getting that to work.
Nice video! Is the code you displayed in the video available anywhere online? I'm working on my own SVO implementation and having that would be very helpful :)
Broo! I really like this video. Can you dhare the source code you used to create the animations? Can you tell us what tools you used to create this video as well?
I thought about exactly this without knowing it is an existing technique. The only thing I am curious about is how we should check if a node is intersecting with a mesh. Do we just do a collision check with the node against the mesh you want to base this SVO of? I am using UE5 where they have a box collision check, but it requires a lot of variables to be set for each operation, which seems expensive if we have to do it for each node. I don't know what software you are using but how would you go and do this check in a performant way?
That's really cool that you came up with it on your own! For the collision checks - to be honest I did it the sub optimal way of just checking against the mesh. The process of making a mesh into a SVO is called voxelization and it is whole complex topic on its own - if you search "mesh voxelization" you will find many different approaches to the problem. Hope that helps!
I didn't understand the part about not always dividing into 8 octants. By definition, doesn't an octree node always have either exactly 0 or exactly 8 children?
You are correct in the fact that there is always 8 children. Every node technically has 8 children because you still keep track of the octants that does not exist. However those octants without points in them do not have any memory allocated for them.
Great video I really liked your explanation but I can't figure out how to render them. You cant just use dda on them also gpu s usually dont like branching and complex code how can this be more optimized
Ngl it is kinda complicated. I did something based on the research paper "Efficient Sparse Voxel Octrees - Analysis, Extensions, and Implementation" by NVIDIA. Basically you shoot a ray onto the SVO in the GPU and based on ray - box intersection you go down the tree in correct order. This website explains the collision well: www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection.html Here is the github repo if you want to look at it: github.com/OzownYT/SVO-Raycaster.git Hope that helps!
It depends, if you want to traverse it normally you can go down the tree as usual by calling a traversal function recursively on exisiting children. For traversing it with raycasting which is what you usually do for rendering it is a lot more complicated. For the raycasting traversal I used this paper: research.nvidia.com/sites/default/files/pubs/2010-02_Efficient-Sparse-Voxel/laine2010tr1_paper.pdf
I watch all RUclips videos on 1.5x speed, so I naturally gravitated towards it. I usually talk fast in real life too but English isn't my native language so not used to speaking it. Will most likely get better with time though. I do appreciate the feedback though, I will try to speak in a more comfortable speed for the next one!
Наука![Doubling the speed of my game's graphics [Voxel Devlog #18]](http://i.ytimg.com/vi/P2bGF6GPmfc/mqdefault.jpg)
![Doubling the speed of my game's graphics [Voxel Devlog #18]](/img/tr.png)
"if you've been around the voxel dev SPHERE", pun chance missed
wasted potential 😞
Duude this is great!
- No 2 minutes long intro
- No 2 minutes long outro
- Gets straight to the point
- Explains code clearly and concisely
- Great visuals + animation
- Not too fast
- Not too slow
Love it! Keep it up!
Thanks, that means a lot! I am new to this and still trying to figure things out.
Nice video! The next step is "brickmaps" where you store a small, dense voxel grid at each leaf instead of a single voxels, such as 8x8x8 or 32x32x32. Since surface details tend to exist around the same boundary, this can get you a lot more detail without as much overhead from the tree structure.
That sounds interesting, I will give it a shot, thanks!
Very nice work. The animations are very smooth and the explanations are very clean. Some people would take 20 minutes to explain the concept so this is amazing!
Thanks, I'm happy that you enjoyed!
Nice, this video inspires me to make my own voxel engine, but I'm too dumb and too tired in life to attempt such a task. However it's good to know the concepts. Helps you understand how it works.
Thanks 👍
Really happy that the video could help! I would also like to add that I am definitely not qualified either, I was just really interested in the topic so I pushed through the difficulty.
@@Ozown I think for everybody they start off feeling not qualified, and then one day you're trying to optimize memory or something similar in your voxel engine and you realize you've just invented some new efficient algorithm :')
Love this video. Was looking for this. To the point, crystal clear, excellent work.
Glad you enjoyed it!
Great video Ozown! I wish this explanation style was more common. Since childhood I always felt my mind had a fast CPU but limited RAM, so I prefer _fast & repetitive_ over _slow & elaborate._ Alas, all school systems adhere to the latter, which never worked for me.
That is the style I like so I tried to replicate it in my own videos. Glad that you enjoyed!
Nice video! Never new about the difference between the two algorithms. Nice animations, but the explenations are a bit fast.
Thanks! I realized in post how fast the video went 😅 I will keep that in mind for the next!
First time I’ve ever set playback to 0.75x 😂
Fantastic explanation though
Minor clarification:
SVO's work pretty well for collision detection, but it depends what exactly you need.
Checking a point is a tree simple traversal.
There are algorithms to do efficient ray traversal in an SVO such that you walk the leaf nodes while sweeping the ray. The algorithm is not simple, but it is doable.
I suspect you can sweep a box efficiently as well, but I've not done it myself.
Great video! Good quality, good explanation, good stuff :)
It's probably going to blow up with a few thousand views in the following days and you deserve it!
Wow, thanks! Glad that you enjoyed it!
An excellent video! Short and full of all the information one may need while looking for the solution! Especially liked the end when you said what it isn't good for.
Thank you!
Another storage optimization you could take is to only store the outer "shell" of the voxel object, and generate inner voxels as needed.
Yep, I also did that for my project!
@@OzownYou still track whether a node is inside or not?
Very nice!
Thanks!
Man, really cool video! How do you create the animations and the voiceover? Is the source code for the animations open source?
For the animation I use 3b1b's math animation library. Here is the GitHub link: github.com/3b1b/manim. For the voice I use a blue yeti as the microphone and audacity as the software. Hope that helps!
Damn. Wish one day we'd have advanced our hardware to the point where you can make a game with a high-resolution grid without octrees
Yeah it would be really cool. The project that motivated me to try out voxels was john lin's. Seems like games made with voxels would be really interesting!
So basically the 3D version of how maps are stored
first you assume the map is flat, divide into 4 quadrants until each quadrants has less than n number of points of interests or details in the sector
Close but a bit different if I am not mistaken on the data-structure you are describing. An Octree has a fixed depth, which means that how many subdivisions that will be done is decided before hand. The information is only stored at the lowest depth. Hope that helps and thanks for watching!
I have a question: Where are all these nodes allocated in memory? Are all the child nodes heap allocated in different places somewhere? Or do we do one big arena allocation upfront that has enough space for the entire oct-tree if it was completely filled with voxels?
I went with a dynamic array route. Everything is stored in a 32 bit int vector where different bits represent different parts of the node data. For example the first 8 bits represent the 8 different children nodes and whether they exist or not. I did however start with dynamically allocating everything in the heap and then changed it over to a dynamic array after getting that to work.
Nice video! Is the code you displayed in the video available anywhere online? I'm working on my own SVO implementation and having that would be very helpful :)
Hi, wasn't posted anywhere but I've made it available here: github.com/OzownYT/SVO-Raycaster.git
Although I do warn you, it is messy. Hope it helps!
Your theme looks nice, which theme do you use?
I use the monochrome theme, hope that helps!
Broo! I really like this video. Can you dhare the source code you used to create the animations? Can you tell us what tools you used to create this video as well?
Here is the code for the final project: github.com/OzownYT/SVO-Raycaster.git Although I do warn you that it isn't well written. Hope that helps!
I thought about exactly this without knowing it is an existing technique.
The only thing I am curious about is how we should check if a node is intersecting with a mesh. Do we just do a collision check with the node against the mesh you want to base this SVO of? I am using UE5 where they have a box collision check, but it requires a lot of variables to be set for each operation, which seems expensive if we have to do it for each node. I don't know what software you are using but how would you go and do this check in a performant way?
That's really cool that you came up with it on your own! For the collision checks - to be honest I did it the sub optimal way of just checking against the mesh. The process of making a mesh into a SVO is called voxelization and it is whole complex topic on its own - if you search "mesh voxelization" you will find many different approaches to the problem. Hope that helps!
Thank you for your super quick response! I will try my best to find an answer.
I didn't understand the part about not always dividing into 8 octants. By definition, doesn't an octree node always have either exactly 0 or exactly 8 children?
You are correct in the fact that there is always 8 children. Every node technically has 8 children because you still keep track of the octants that does not exist. However those octants without points in them do not have any memory allocated for them.
subscribed holy shit
also you got on my recommended so it seems your effort on this may be paying off
Thanks! happy that you liked it!
Great video I really liked your explanation but I can't figure out how to render them. You cant just use dda on them also gpu s usually dont like branching and complex code how can this be more optimized
Ngl it is kinda complicated. I did something based on the research paper "Efficient Sparse Voxel Octrees - Analysis, Extensions, and Implementation" by NVIDIA.
Basically you shoot a ray onto the SVO in the GPU and based on ray - box intersection you go down the tree in correct order. This website explains the collision well: www.scratchapixel.com/lessons/3d-basic-rendering/minimal-ray-tracer-rendering-simple-shapes/ray-box-intersection.html
Here is the github repo if you want to look at it: github.com/OzownYT/SVO-Raycaster.git
Hope that helps!
nice, thanks !
but how to traverse the octree ?
It depends, if you want to traverse it normally you can go down the tree as usual by calling a traversal function recursively on exisiting children. For traversing it with raycasting which is what you usually do for rendering it is a lot more complicated. For the raycasting traversal I used this paper: research.nvidia.com/sites/default/files/pubs/2010-02_Efficient-Sparse-Voxel/laine2010tr1_paper.pdf
@@Ozown this is hard
@@sedenion9524 Unfortunately yeah, however I do intend on making a video on this so that might help out
Bools in structs?
Yeah, to keep track of the status of a node!
🇳🇴🇳🇴
ʸᵉˢʸᵉˢ
voxel is pixel in 3d
True!
That struct packing though, cringe!
It be like that😔
Kd-Tree are better 😎
Maybe 😔✊
Where are you rushing so much?... You vocal ability is not capable of pronouncing words properly at such speeds.
I watch all RUclips videos on 1.5x speed, so I naturally gravitated towards it. I usually talk fast in real life too but English isn't my native language so not used to speaking it. Will most likely get better with time though. I do appreciate the feedback though, I will try to speak in a more comfortable speed for the next one!
@@Ozown I really thought I had it set to 1.5. Honestly, you gotta try rapping.