VOXEL Rendering And Traversal Algorithms | Devlog #7
HTML-код
- Опубликовано: 17 авг 2024
- Join The Discord Server - / discord
If you like the video and want to see more, please give it a thumbs up and share. More devlogs coming every month so subscribe to be notified.
This has been a long month! I've been working on lots of different voxel traversal algorithms such as the DDA algorithm and also looking into signed distance fields to store the voxels.
This custom c++ engine is using Vulkan to do voxel octree ray casting to render the scene. This allows complex LOD systems to be used to optimise rendering. My goal is to create an open world game based of voxels at a scale never seen before!
Links to discord challenge games:
thibsworkshop....
mrsharkgames.i...
Thibs Workshop channel:
/ @thibsworkshop
Fast voxel traversal algorithm:
citeseerx.ist....
♫ - Music:
"Lukrembo" - "Wine"
/ wine
"Lukrembo" - "Night"
/ night
As a mechanical engineering major, I still have basically no clue what's happening here, but you say fun coding words and you make fun colors appear onscreen so I'm enjoying this regardless, definitely cool to see someone progress on a project they're passionate about
The Efficient Sparse Voxel Octree paper proposed a great stack-based traversal algorithm for sparse octrees. If traversing a sparse data structure is a problem for you, just implement that.
That is very similar to what I previously used. Also I want to not use a stack if possible as that mean the we can run more threads per work group on the GPU
@@voxelbee How do you use stack on GPU without CUDA? As far as I know there is no stack in HLSL and GLSL.
@@kerzhemanov stack can be basically fixed sized array plus integer that points to the top of this stack
@@anonymousanonymous1934I understand that. That wasn't what I asked. It was a technical question, not theoretical. Though I agree that I should make it more clear.
Using stack on such architecture often leads to lower performance because of higher thread divergence. It seems that algorithms which always start from root and so do not use stack, work better. Also I suspect that CUDA does some optimizations for stack based code, but I may be wrong here.
Voxelbee: I'm limited by the technology of my time
Yes, just need to see if there's a hyper-detail spud.
Haha I have to do this at some point now!
Potato.
YES.
and a hyper-detail cannon
Nice, this is pretty similar to some of my favorite Shadertoy demos.
I've also got a similar thing going in my own C++/Vulkan engine I want to eventually make into something.
2:09 "DISTANCE FEILD" lol
I just realized! lol
This is exactly the kind of coding video I like. 🎉 interested in continuing to hear more about the unique challenges you face and how you decided to move through or solve them.
I think it may be worth mentioning that GPUs already use some kind of tiling or curve (like morton codes) in their texture memory layout to increase cache coherence.
Yeah that's true!
I’m honestly so confused, why in the world don’t these have more views??
Great video! It's interesting to hear your approach on this.
woot! well done dude, keep it up
Nice video and very interesting algorithms! Thanks for the shout-out!
What I'm wondering is how you'll do dynamic scenes with your datastructure? Or are you mostly aiming at implementing static voxel scenes
Fascinating stuff, keep it up!
Nice!
4:42 you invented a quantum physics simulation without realising
I learn a lot from these devlogs!
Great vid! I can’t wait for the next one
Tbh I was pretty confused when I read the title haha but I really liked the video great job
I work full-time as an app developer and at least understand what an array is and buffers etc. But as soon as you talk about graphical stuff I don't understand anything anymore but it's still very interesting.
keep it up man!
SDFs seem really efficient, but wouldn't updating the shape and hence also updating the SDF be rather slow?
At first it looked so nice and then everything came to a halt. But it looks like you start to solve the problem. I'm looking forward to the video where you explain what solution you picked.
If you like Morton Codes, you might like k-d trees. (Octrees might be a red herring for your sparse data model)
K-D would be my choice as well
What if instead of giving each voxel a coordinate system you give to each voxel an information that says wheter it has a near voxel? Like, imagine a 8x8x8 chunk of voxels... You'll need three coordinates of 3 bits to identify each voxel inside the chunk (an effective total of 9 bits for voxel). What if you change completely the way voxels are stored and you create a data structure where only ONE voxel in the chunk has coordinates and then each other voxel starts from that one like a chain? Immagine a 2D example of this: You have an 8x8 grid and you wanna create an "L" character, which is 4 pixel tall and 3 pixel wide. You identify the voxel neighbor position with 2 bits (00 up, 01 right, 10 down, 11 left). Now, you give the coordinates of the first voxel and then you build the chain:
first voxel: (000,000). Then you start the chain: (10),(10),(10),(10),(01),(01),(01). In real life direction that means "down,down,down,down,down,right,right,right,right".
Now, an 8x8 grid requires at lest 3 digits for the X and 3 for the Y, so you have a total of 8 bits for each voxel. So a traditional model would be:
(000,000)
(000,001)
(000,010)
(000,011)
(000,100)
(001,100)
(010,100)
(011,100)
And this gets bigger if your grid becames larger, and WAY bigger if your grid becames tridimensional. But Identifying a neighbor voxel will ALWAYS require 2 bits (3 at most, with a three dimensional grid). So this model is WAY heavier, compared to a chain model, which is just:
(000,000)
(10)
(10)
(10)
(10)
(01)
(01)
(01)
And the difference only gets bigger with bigger voxels. Hope you can find this useful (:
You're a pretty smart bee.
Voxels are the future.
Cool :-)
Every voxel saves a reference to next visible voxel with degrees? From center to center? When a voxel moves this needs to be recalculated. Maybe than the next voxel is matchable with the pixelbeam?
Could be alot of references. Maybe a hybrid of herachie and references in some ways. Also an max step definition for a pixel beam should be applyed and for the beams for recalculating near by voxels for the moved voxel. Maybe if you have intelligent datastructure for the degrees than you also dont need to check every angle.
Just a theory. Maybe overconstructed :D
Check out the gigavoxels paper. I think a references a similar idea to store neighbours bit gigavoxels doesn’t to keep memory lower
@@oystercatcher943 thank you
@@oystercatcher943 Hmmm still think voxel grouping is much more easy/effective.
Second!
Edit: oh yeah SDFs are cool!
Edit2: i wonder how he's going to use Octtrees with SDFs...
Edit3: i knew he was going to mention Shadertoy
Edit4: dealing with floats is annoying
Edit5: this is why I gave up on graphics programming...
Edit6: noice games and noice video!
WARNING TO VIEWERS: I don’t think the author of this video understands the sparse voxel oct tree concept properly, and that is the reason there is no supercover/DDA algorithm for a sparse grid. You traverse the Oct tree to determine if you have a hit, and contact is already encoded in that data structure. It looks like what happened here is mix up the concepts so there’s grid traversal on an oct tree-like setup. If you understand why SVOs are a powerful technique for ray casting, then one would never make this mistake, and certainly not reintroduce complexity to the algorithm. I recommend reading some paper by Nvidia on the topic. You can find them for free.
KEEP GOING
just fyi, the link to the paper seems to be broken
02:09 Distance Field
CPU instruction calls are substantially cheaper than fetching memory. Be not afraid of more CPU calls if it means reducing the amount of memory accesses you need to do. Obviously, there is a tipping point and you should benchmark, but avoiding a data structure because it requires more instructions is a little silly.
Imagine if this voxel engine is so advanced, you cant tell things are made of voxels until you look REALLY closely
As a mechanical engineer, I am now a software engineer.
where is the shader link?
plugin algorithms, separate "complex" from "take care"
assume you have falling leaves or snow all over the scene, to choose proper optimization/algorithm, the grid is the best in most cases, on average
worst case scenario rendering algorithm considerations, best for that case, acceptable for all
if you dont care about "second" intersections, then the octree is the best for all cases
Remember to not over engineer too much