Adding DATA STRUCTURES to my Voxel Raytracing Engine | Devlog 1
Vložit
- čas přidán 26. 06. 2024
- In this video, I discuss the implementation of 3 new data structures I added to my voxel raytracing engine. Namely, a brickmap, an octree, and a SVDAG. I also share some of my philosophy behind the engine.
Papers referenced (in order):
www.cse.yorku.ca/~amana/resear...
studenttheses.uu.nl/handle/20...
research.nvidia.com/publicati...
Check out my game:
store.steampowered.com/app/24...
Music (in order):
Madison James Smith - And the Press of a Key (Terra Toy OST): • Terra Toy OST - And Th...
C418 - Preliminary Art Form: • Preliminary Art Form
Madison James Smith - The World Began (Terra Toy OST): • Terra Toy OST - The Wo... - Věda a technologie
BABE WAKE UP, FROZEIN UPLOADED !!!
The technical side is the best side🙏
The only side? :)
I'm all into optimizations, and your explanations are great.
We as Year 1 game programming students at Breda University were tasked to make a CPU voxel ray tracer. We were encouraged to implement Brickmaps or a BVH. This video would’ve been perfect 2 months ago! 🙃
That's a really cool assignment, I wish my CS classes were as interesting...
Just a small detail about your videos I appreciate (on top of everything else): your graphics have a real Baba Is You vibe and I love it.
You probably already know this stuf but. You can use a flat 3D texture and do mipmaps each level so that you can skip large sections also. I feel like this method is possibly the fastest to transverse because there are no pointers and the cauching is really good. However, it comes with the detrament of a lot more memory. Also, instead of using rtx for forard rendering you can rastirize the volumes as big cubes then use the rtx pipeline for secondary rays. This can help a ton too.
Good ideas, though mixing rasterization with the Vulkan ray tracing API may prove difficult. I'll experiment with mipmapping and see if it's worth the extra memory.
I’ve always felt that summed area tables are better than mipmaps.
@@frozein
Mip maps are also way faster to create compared to octrees/dags.
So for dynamic scenes with lots of changes this could be useful.
Amazing work. I love it. The ESVO paper you mentioned (and its extension paper) go into pretty great detail and is one of the best voxel papers that exists. That being said, I think it may be beneficial to widen the ESVO tree to have 4x4x4 or even 8x8x8 nodes. I am excited to play around with these things soon... I've been so busy 😔
Another thing - For traversal especially for the basic DDA one, I really recommend separating the geometry from the shading attributes, so that you only load bitmask data while traversing (improving cache coherency). You may already do this but I bring it up because I don't think you mention it in the video.
I agree, the paper was a godsend for implementing octrees. I'll experiment with different tree widths once I get the chance, definitely room for improvement.
Good idea about the bitmask, I was planning on implementing that eventually. Each voxel will only be 1-byte (unless I add per-voxel normals), so I'll have to profile and see if the extra memory is worth it.
From what I've seen the slowest part of traversing an Octree or DAG is the near constant descension and ascension, with 2x2x2 structure you're ascending and descending frequently, so the overhead of setting up DDA becomes larger considering DDA becomes more efficient after the initial computations. a 4x4x4 tree or higher allows for similar empty/homogenous region reduction in memory, while also reducing the number of ascents and descents necessary and reducing the number of levels of the tree needed to represent the data, honestly if you use an 8x8x8 tree you can think of it like a brickmap of brickmaps.. Another trick that was discussed in a different Nvidia paper (though I can't remember the name off the top of my head) was to establish and maintain the DDA at multiple levels, so that descending and ascending don't require the relatively more complex initialization to be performed often.
A few people have mentioned similar ideas, I'm definitely going to be trying different tree widths. There seems to be a lot of potential for improvement.
It'd be interesting to support implicit volumes, with an optional signed distance field hint for the ray algorithm
Interesting idea, I'll explore it when I get the chance
having multiple data structure in one game engine make so much sense but I've never seen i done before. This look interesting
I see someone read John Lin's blog post :) Great video though, as always!
You know it haha. I think there's a lot of potential with this idea, but I still have yet to do a detailed profile so we'll see.
Amazing to see how you've introduced these and the difference in performance. Fantastic work!
Wowzinga
Love the explanations and citing of research papers.
Great vlog and progress. Can’t wait to see the new system in action
Amazing video ! Greatly explained!
Yooo Amanatides and Woo are what the Teardown characters are named from!
I thought they sounded familiar, but I couldn't remember where I heard those names...
Wow that's a pretty niche easter egg
awesome video. Cant wait to see the progress next time.
Octree my beloved
Very nice stuff! To gain even more performance you could try constructing your outer BLAS that you feed to the hardware accelerated ray tracer out of multiple brick AABBs instead. This would allow significantly higher utilization of the hardware. We tried this in an SDF rendering project and saw massive success, particularly in complicated lighting scenarios that heavily used the hardware ray tracer.
Thank you! I'm keeping the engine very flexible, so if a programmer wants to implement their own brickmap by using multiple BLAS's, all of the functionality is there. I'll do a lot of experimentation once the engine is more feature-complete.
One extra thing you could add is more brickmap layers. In my experience, it’s much more performant in certain scenes. Say you have a 128^3 world with cube-like shapes of size 8^3 in it. You could have one brickmap level at size 8, and one at 16 or 32 to skip sparse volumes.
That's more or less what an octree is. I do plan to experiment with trees of different widths, for example one that recursively splits the volume into a 4x4x4 region. This should be a good compromise.
Your videos are always an absolute treat! This is a great introduction to data structures that any voxel developer should watch :)
Do you have any plans for the engine yet, feature-wise? Will you be making another game, or open-sourcing parts of it? Either way, looking forward to what you do - especially the next video about voxel shading. I also need to explore voxel shading more, right now I am just using diffuse and not taking advantage of ray marching's full capabilities.
Thank you! I'm not sure of my plans at the moment, for now I just want to see how far I can take the engine. I will definitely be open-sourcing at least parts of it once the codebase matures a bit.
I will also probably implement the data structure your engine uses - a 64-tree. It seems like a good way to reduce the number of ascensions/descensions :)
your videos are super high quality and very informative. i'm really enjoying following along with you're projects but a feel like putting more thought/effort into you're videos titles and thumbnails could significantly improve their performance.
Thank you! I'll spend more time on my thumbnails in the future.
I'm mostly unfamiliar with the dirty details of how octree navigation works, but I've got a few hunches on improvements from my own experience with raytracing.
It seems like the octree unfortunately suffers pretty badly with sparse geometry. The brick map will likely help with that, but I wonder about the merits of possibly wrapping the geometry in an AABB you can check against first before performing full octree navigation. AABB checks using the slab method are probably only marginally more expensive than those performed to navigate the octree, and could save an insane amount of time on grazing angle rays.
Id imagine this technique would further allow you to spawn a smaller octree, essentially cutting out the empty cells an AABB miss would let you skip. It would still have to be sized to a power of two and aligned to the cell grid, but you could size it more appropriately to the geometry. Check the AABB, then navigate the smaller octree if you hit
The techniques used in BVH based acceleration in general may be of practical use to you. But, my experience is with building triangle based ray tracers, so I apologize if this is all just fanciful speculation
Thanks for your ideas! I am using the vulkan raytracing pipeline, which automatically constructs and navigates a BVH given a list of instances. Each data structure is its own instance, with a tight-fitting AABB, so this behavior is already implemented. That is, if my understanding of what you are saying is correct.
Very interesting...
Can't wait to see the same scene profiled with different data structures....
I'm going to make some larger scenes and profile them for next video!
@@frozein LFG
very well explained.
yoo new upload
see you next month!!
or whenever you upload
Hopefully next month, but I've got finals going on now so we'll see :(
I recently attempted my own voxel engine in Python and PyGame. To my own shock I managed to code one from scratch and it's actually quite physically accurate! But I don't want to bother with shaders so I made it fully CPU based: I've reached the limit of how far I can optimize it even at super-low resolutions with lots of tricks to speed up perceived FPS.
Very nice, I like PyGame a lot.
You could probably scrape more cpu performance if you move to something like Rust
@@frozein Rare footage of a low-level programmer liking pygame????
Cool so far! You should look into the HashDAG paper made around 2020 for a modifiable DAG structure. There's a video somewhere on YT (altho its audio quality is awful).
Oh that sounds interesting, I'll check it out.
should've used gvox 😔 really cool tho !!
what are the real performance numbers in these little scenes btw ? it would've been nice to have the frametime, cuz less steps doesn't always mean faster rendering time
The scene at the end was running at around 500fps, but that's also the framerate for a blank scene. I'm not sure yet how Vulkan ray tracing's performance scales, next video I'll have a much larger scene to get more accurate data from.
very cool!
MONTH LATE BUT FROZEIN UPLOAD BABY~
Needs more data structures.
Besides computation cost... What about file size? These different data structures could be used as the basis for a compression algorithm and thus a shareable file format.
Exactly, I plan to write serialization functions for each of these structures so they can be saved/shared. I do also plan to add more data structures :)
What language are you developing this in, and is it open source? Also, looks amazing!
It's all in C with shaders in GLSL. It's not open source yet but I plan to release the code eventually!
A viewer from Nederlands here! You pronounce dutch 'ij' as english 'y'. Because Dutch doesn't have y.
RENDERING!!!!!!!!!!!!!!!
I had an idea, instead of storing the air period, just take the very first element of the array and turn it into an indicator that the first & second digit of any given number is the offset between where the rest says it is and where it is. (With a minecraft like chunking system this should be fine, assuming each new chunk is it's own array that is...)
Like run length encoding?
You are giving your best to not be the last of all the voxel developers.
I just write down a few thoughts of mine to understand your goals a bit better. If I understood you correctly, the engine can work with several data structures at once. So could you make a large landscape in the DAG version because it is memory efficient. And instead of having empty space as air, you fill those up with a brickmap which you can actually modify in real time. So you have a landscape with a nice beach where you can build your sandcastles. And where you can cut down trees.
How about creatures? Are they also in voxel style? In the video _"I’ve Finally Added a New Biome to my Voxel Game - Lay of the Land"_ of Tooley1998 I noticed, that voxel animals look cool, but they blend in too nicely. Of course if you have an animal that intends to blend in then that could be considered a feature. But what I mean is the texture. His creatures look like statues or the landscape. Actual creatures have fur or feathers or chitin, which all have a texture that looks different than the rock or the vegetation surrounding them. One way to change that would be to make triangle based animals, not voxel based animals.
Are there any standardized voxel datatypes? I ask because if I want to create something in blender or import it from a marketplace, could I do it? Also will you add scaling while doing the data conversion? For example if your game has 10x10cm cubes and you import a minecraft build it will be off by a factor of 10.
I'm not working on a game yet, so I can't really answer your questions. Right now I'm just working on an engine, and once it has enough features I may work on another game.
@@frozein Fair enough. Will you go by top down view or also add first person camera?
Hey, superb video, but i feel that the octree is wrong. Wouldn't the resolution of the cubes augment closer to the sphere than in the corner of the bounding box? Maybe i didn't quite understand how its formed.
Each of the bounding boxes have boxes in the far corners, as seen on the last video. Hence the "protrusions" to the corners.
The octree/dag just require some sort of auxiliary method to propagate the modification, right?
Yes, you either need to store additional data or rebuilt the structures to modify them.
Hey, I noticed some "s" like sounds (essing) being a bit loud/annoying in your recordings.
Would be neat if that could be reduced!
Thanks for the feedback, I'll apply some processing next video to reduce it.
I bet you can do that on a kernel 0 OS like TempleOS
Probably, though I'm not sure how many people use TempleOS haha
what if you use brick map but share the memory of identical space like DAG? what is that called?
I haven't heard of anyone doing that before, I don't think it has a name. There are lots of ways to mix and match features from different data structures.
All of this could be happening in a fragment shader without the hardware raytracing, right?
Do you know how much benefit you're getting out of using hardware RT?
Yes I could definitely write this all in a frag shader, though I don't plan on writing one for comparison. I'm confident that the hardware acceleration is notably increasing performance though, I can already render very large scenes with high framerate without spending much time on optimization.
The reason why my tlas and blas didn't work is idk
I'm the first!!!
Are you still using vulkan raytracing with octrees ?
Yes, Vulkan ray tracing allows you to define custom intersection functions. So I have 4 intersection functions, 1 for each data structure, and I tag each object in the scene to tell Vulkan which function to use.
@@frozein so you dont have to use acceleration structures ?
@@astios2248 Each object (think for example an individual tree, creature, car, etc) has it's own acceleration structure which I create and write code to intersect (octrees, brickmaps, etc.). I then send a list of all of these objects to Vulkan, which itself creates a top-level acceleration structure (most likely a BVH). Vulkan traverses the top level structure, and calls my code when it hits an object.
are you still writing it in c?
Yes, fully in C!