Adding DATA STRUCTURES to my Voxel Raytracing Engine | Devlog 1

Sdílet
Vložit
  • čas přidán 19. 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

Komentáře • 88

  • @darkfllame
    @darkfllame Před měsícem +35

    BABE WAKE UP, FROZEIN UPLOADED !!!

  • @thememermonkey
    @thememermonkey Před měsícem +22

    The technical side is the best side🙏

    • @coreC..
      @coreC.. Před 3 dny +1

      The only side? :)
      I'm all into optimizations, and your explanations are great.

  • @capslpop
    @capslpop Před měsícem +24

    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.

    • @frozein
      @frozein  Před měsícem +9

      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.

    • @AmaroqStarwind
      @AmaroqStarwind Před měsícem +2

      I’ve always felt that summed area tables are better than mipmaps.

    • @TheTentacola
      @TheTentacola Před měsícem +1

      ​@@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.

  • @sleepi5550
    @sleepi5550 Před měsícem +4

    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! 🙃

    • @frozein
      @frozein  Před měsícem +1

      That's a really cool assignment, I wish my CS classes were as interesting...

  • @RandomProduct
    @RandomProduct Před měsícem +2

    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.

  • @GabeRundlett
    @GabeRundlett Před měsícem +13

    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 😔

    • @GabeRundlett
      @GabeRundlett Před měsícem +3

      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.

    • @frozein
      @frozein  Před měsícem +3

      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.

  • @DreadKyller
    @DreadKyller Před měsícem +5

    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.

    • @frozein
      @frozein  Před měsícem

      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.

  • @shadamethyst1258
    @shadamethyst1258 Před měsícem +5

    It'd be interesting to support implicit volumes, with an optional signed distance field hint for the ray algorithm

    • @frozein
      @frozein  Před měsícem +1

      Interesting idea, I'll explore it when I get the chance

  • @aronseptianto8142
    @aronseptianto8142 Před měsícem +1

    having multiple data structure in one game engine make so much sense but I've never seen i done before. This look interesting

  • @alexdesander
    @alexdesander Před měsícem +4

    Wowzinga

  • @DeGandalf
    @DeGandalf Před měsícem +5

    I see someone read John Lin's blog post :) Great video though, as always!

    • @frozein
      @frozein  Před měsícem

      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.

  • @Skeffles
    @Skeffles Před měsícem +1

    Amazing to see how you've introduced these and the difference in performance. Fantastic work!

  • @maarten9222
    @maarten9222 Před měsícem +1

    awesome video. Cant wait to see the progress next time.

  • @user-vi7kp6re2l
    @user-vi7kp6re2l Před měsícem +2

    Amazing video ! Greatly explained!

  • @butta4683
    @butta4683 Před měsícem +1

    Great vlog and progress. Can’t wait to see the new system in action

  • @chasemarangu
    @chasemarangu Před měsícem +1

    Love the explanations and citing of research papers.

  • @sleepi5550
    @sleepi5550 Před měsícem +1

    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.

    • @frozein
      @frozein  Před měsícem +1

      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.

  • @LineOfThy
    @LineOfThy Před 10 dny

    Octree my beloved

  • @perodactyl490
    @perodactyl490 Před měsícem +4

    Yooo Amanatides and Woo are what the Teardown characters are named from!

    • @theneonbop
      @theneonbop Před měsícem +1

      I thought they sounded familiar, but I couldn't remember where I heard those names...

    • @frozein
      @frozein  Před měsícem +1

      Wow that's a pretty niche easter egg

  • @RedPoweredMinecraft
    @RedPoweredMinecraft Před měsícem +1

    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.

    • @frozein
      @frozein  Před měsícem

      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.

  • @tzor_182
    @tzor_182 Před měsícem +1

    very well explained.

  • @finndotbin
    @finndotbin Před měsícem +1

    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.

    • @frozein
      @frozein  Před měsícem +1

      Thank you! I'll spend more time on my thumbnails in the future.

  • @gottfrid_n
    @gottfrid_n Před měsícem +1

    very cool!

  • @DouglasDwyer
    @DouglasDwyer Před měsícem +1

    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.

    • @frozein
      @frozein  Před měsícem +1

      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 :)

  • @MirceaKitsune
    @MirceaKitsune Před měsícem +2

    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.

    • @frozein
      @frozein  Před měsícem

      Very nice, I like PyGame a lot.

    • @thegoldenatlas753
      @thegoldenatlas753 Před měsícem +2

      You could probably scrape more cpu performance if you move to something like Rust

    • @rgc-exists
      @rgc-exists Před měsícem +1

      @@frozein Rare footage of a low-level programmer liking pygame????

  • @lemonke8132
    @lemonke8132 Před měsícem +1

    Can't wait to see the same scene profiled with different data structures....

    • @frozein
      @frozein  Před měsícem

      I'm going to make some larger scenes and profile them for next video!

    • @lemonke8132
      @lemonke8132 Před měsícem

      @@frozein LFG

  • @Selsato
    @Selsato Před měsícem +1

    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

    • @frozein
      @frozein  Před měsícem +1

      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.

  • @samuelkeresztes5247
    @samuelkeresztes5247 Před 27 dny +1

    Very interesting...

  • @dottedboxguy
    @dottedboxguy Před měsícem +2

    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

    • @frozein
      @frozein  Před měsícem

      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.

  • @ultra_9861
    @ultra_9861 Před měsícem +2

    yoo new upload
    see you next month!!
    or whenever you upload

    • @frozein
      @frozein  Před měsícem

      Hopefully next month, but I've got finals going on now so we'll see :(

  • @scroungycat2489
    @scroungycat2489 Před měsícem +1

    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).

    • @frozein
      @frozein  Před měsícem +1

      Oh that sounds interesting, I'll check it out.

  • @AmaroqStarwind
    @AmaroqStarwind Před měsícem +1

    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.

    • @frozein
      @frozein  Před měsícem

      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 :)

  • @LineOfThy
    @LineOfThy Před 10 dny

    MONTH LATE BUT FROZEIN UPLOAD BABY~

  • @LemonHeadYT
    @LemonHeadYT Před měsícem +2

    RENDERING!!!!!!!!!!!!!!!

  • @randospawn7495
    @randospawn7495 Před měsícem

    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...)

    • @frozein
      @frozein  Před měsícem

      Like run length encoding?

  • @natecraver6362
    @natecraver6362 Před měsícem +1

    What language are you developing this in, and is it open source? Also, looks amazing!

    • @frozein
      @frozein  Před měsícem

      It's all in C with shaders in GLSL. It's not open source yet but I plan to release the code eventually!

  • @benrex7775
    @benrex7775 Před měsícem

    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.

    • @frozein
      @frozein  Před měsícem

      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.

    • @benrex7775
      @benrex7775 Před měsícem

      @@frozein Fair enough. Will you go by top down view or also add first person camera?

  • @Aerobiker1
    @Aerobiker1 Před měsícem

    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.

    • @CreativeGrey
      @CreativeGrey Před měsícem

      Each of the bounding boxes have boxes in the far corners, as seen on the last video. Hence the "protrusions" to the corners.

  • @nangld
    @nangld Před měsícem +1

    A viewer from Nederlands here! You pronounce dutch 'ij' as english 'y'. Because Dutch doesn't have y.

  • @brandonallen2301
    @brandonallen2301 Před měsícem +1

    The octree/dag just require some sort of auxiliary method to propagate the modification, right?

    • @frozein
      @frozein  Před měsícem

      Yes, you either need to store additional data or rebuilt the structures to modify them.

  • @Stevedawhoop
    @Stevedawhoop Před měsícem

    what if you use brick map but share the memory of identical space like DAG? what is that called?

    • @frozein
      @frozein  Před měsícem

      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.

  • @cvabds
    @cvabds Před měsícem +1

    I bet you can do that on a kernel 0 OS like TempleOS

    • @frozein
      @frozein  Před měsícem +1

      Probably, though I'm not sure how many people use TempleOS haha

  • @delphicdescant
    @delphicdescant Před měsícem

    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?

    • @frozein
      @frozein  Před měsícem

      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.

  • @StiekemeHenk
    @StiekemeHenk Před měsícem +1

    Hey, I noticed some "s" like sounds (essing) being a bit loud/annoying in your recordings.
    Would be neat if that could be reduced!

    • @frozein
      @frozein  Před měsícem

      Thanks for the feedback, I'll apply some processing next video to reduce it.

  • @kotofyt
    @kotofyt Před měsícem

    The reason why my tlas and blas didn't work is idk

  • @lyagva
    @lyagva Před měsícem +1

    I'm the first!!!

  • @astios2248
    @astios2248 Před měsícem

    Are you still using vulkan raytracing with octrees ?

    • @frozein
      @frozein  Před měsícem +1

      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.

    • @astios2248
      @astios2248 Před 26 dny

      @@frozein so you dont have to use acceleration structures ?

    • @frozein
      @frozein  Před 24 dny +1

      @@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.

  • @Conlexio
    @Conlexio Před měsícem

    are you still writing it in c?

    • @frozein
      @frozein  Před měsícem +1

      Yes, fully in C!