Hi! I wrote the "Binary greedy meshing" algorithm. Very cool to see this video on my youtube frontpage today, I love your video and explanations :)

You just casually made a spatially mapped datamodel lol

Thanks for the video, I can advise you not to make a greedy mesh for each type of block, but to make for all complete solid blocks, and then transfer to the GPU data structure with the help of which you can calculate the block type and texture by pixel position, it will simplify the mesh many times as well as the algorithm itself.

Found a way to make it even faster: you are initializing the 2 initial vectors with chunk_size_p³, but it can also be done with chunk_size_p² because the 3rd dimension is in the bits. this way you can use arrays because there is no longer a stack overflow

When you explained the part in 14:40, where you explained how to find the faces looking right just by modify an interger, I was so surprise at how simple it is an yet amazingly complex

this is insane! i have my own culled and greedy meshing implementations and i know they're not the fastest, but i'd never have thought it could get THIS fast. you could literally remesh every chunk every frame with this and still get good fps, which is mind-boggling. good job with the explanations, too.

I now fully understand the concepts used to achieve such high performance. I also fully understand that if I were to try to write it. Every line of code would have an off-by-one error.

You can speed up the data setup part by using stack arrays instead of using "Vec"s

This video is honestly so well explained and even though I don't know anything about voxel engines or game development I was able to understand it. This is probably one of the best resources for making a voxel engine. If I ever make one, I'll probably take a look at this again, thanks for your amazing work!

Oh my god I wish i had this video like 2 months ago when i was trying to write a greedy mesher. Thank you so much for this resource! Will definetly save it for the future!!

This is incredible! I did something extremely close to this for counting strings within DNA sequences and got immense speedup. Binary manipulation is insanely speedy if you can comprehend it. Great job figuring this out and explaining it.

I haven’t tried greedy meshing but I’ve seen some demos of greedy meshes where it doesn’t care about block type, it constructs the triangles while remembering where the different block types are, so it’s possible to make the greedy meshes not slow down when you increase the block type count

Looking at this made me realise that I clearly need to lurn bitwise manipulation

Use an array for the data instead of a vector (since you know exactly how many entries it will contain) and it should have essentially zero allocation time since it'll be allocated on the stack instead of the heap

This is some Big Brain Calculation right here, great video Tantan!

If your friends CPU has significantly larger L2 or L3 cache, the performance difference could perhaps be cache misses? Aligning data for CPU cache optimization is another beast to tackle though 😅

Man amazing video. You made it sound so hard but I feel like I grasp all of it pretty well. The visuals make it soo much easy to follow, hats off to your work.

Thank you Tantan for somehow releasing a video on the exact topic I was worried about for my next project, very cool.

I'm making a game that has voxels and I implemented this also using Rust and something very similar to the slow approach. This video came out with such a great timing. Thanks for sharing this. Maybe it can be even faster if SIMD or parallelization are included? 😁

Great video! I wrote a basic algorithm for doing this on culled meshes, but I'm glad to see it's possible with greedy meshes too!

What a coincidence, I currently need a good voxel algorithm for my project :D Will definitely look into it! thanks

Now i understood why this video take a while to be made! This was a really good video!

The brings back memories. I recognized some code I wrote about 15 years ago after being blown away by Minecraft. The & operation on the shifted bits specifically. The merging of the meshes was clever and much better than what I ever came up with. I put it all in a fancy octree though so I only rendered on-screen chunks. I hit a brick wall getting the lighting to work on merged meshes and it all fell apart once I had more than, say, 6 block types. Your code will do so too. But it's a great exercise and good job. A more modern way would no doubt be raycasting, there are many more triangles than pixels on the screen if you scale things up and it parallelizes better. Nice video, keep them coming!

phenomenal video explaining this. you are very good at explaning these topics

Now do it with SIMD

I came from Dani's video, and I'm glad I did :) Great video!

I like how you mostly pronounce "Chunk" as "Shunk", always made me smile :D

It's like a gift for me. It was a problem no matter how much I optimized it before but now I have no problem loading and rendering faster than before. thanks for your video

One final thought, if you use 30x30 chunks you can fit the left/right neighbors into a 32bit int rather than expanding to 64. It'd halve your memory bandwidth requirements at minimum and if you use SIMD it will let you double the number of calculations performed per cycle.

i love everything about this your awkward presentation, the handdrawn sketches, the weird pronounciation, the focus on speed, your manbun, your long hair that makes you look like a metalhead, the jokes, the effort you made, everything, everything in this video is just *right* .

Love this. I remember building a 2048 AI and going from loop-type grid transformations to bitwise operations. Bitwise stuff is hard to grok but there are sooo many orders of magnitude of improvement and it's so satisfying :)

You succeeded very well in explaining something complex in a simple manner! Well done!

Woah, love the bit shift and negation. That's a great way to generate the culling indices instead of iterating through every single block.

I would love to see a full bevy tutorial on your channel

Wow man, mad props. That was some heavy stuff and yiu actually explained it extremely well. Thanks, and keep up the good work!

That is cool revelation and use of bits.

I dont watch your videos (but still subscribed (I want to learn rust&bevy some day)), but every time I see your videos it feels like a new scientific experiment.

Pretty cool project and interesting technique and considering that it is within the context of a voxel engine, it is very fitting to say the least. Outside of that, if one isn't referring to a pure voxel engine; there are many other interesting techniques that are also very interesting. These range from: Quad and Octrees, The use of Quaternions, Octonions, Sparse Matrices, FFTs (Fast Fourier Transforms) and their inverses, Instancing through referencing, other types of procedural generation techniques, Perlin Noise Sampling, Batch Processing through a priority queue, Fractal Generation, and so much more. Don't forget, you can also do a lot of interesting things with a plethora of available techniques not just within the engine itself, but also within the context of shaders. The Graphics Pipeline in general is a very interesting field of study.

this videos singlehandedly makes me wanna try to make a 3D game from scratch

The reason, why the code was equally fast is, that bit operations are single instructions. The reason, why new CPUs are usually faster, is other than clock speeds, which are generally about the same, because chip engineering hit a limit on that one (any faster and CPUs melt basically). However, I am not sure, why the standard mesher is faster. But I am suspecting CPU cache size, since improvement in pipelining or superscalar execution would also lead to improvements in the first comparison and the clock speed is about the same, as I mentioned before

WOW you did a really phenomenal job at explaining your algorithm

You explained this really well! Thanks!

Epic games had a wonderful talk about nanite, and the part that blowed my mind is: Gpu’s are very slow at rendering extremely small triangles. So what they did? They just wrote a SOFTWARE RASTERIZER, that is faster than the hardware one I think when the size of a triangle is less then 40*40 pixels. The difference is really impactfull, and they showed the code and implementation for everybody to use it!

Oh! Great catch. Initially in my rendering I've used 64 bitmasks, because my chunks (not rendering chunks) were always 4x4x4 voxels. Tho I haven't implemented a greedy meshing, because I need to support much more than a solid block, so different shapes etc. End up with custom rasterizer.

Now write it in SIMD using WIDE bit registers. imagine what you could do with 4x256 bits :P

Just want you to kmow that this video was so good that at 11:27 there was a solid 5 seconds where I actually scrambled to rewind the video to try to desperately see the code

This was so clearly explained! You finally made me understand a usecase for bit-shifting!

1:03 missed opportunity for the vsauce intro ost

Amazing work, You can make this dramatically faster using SIMD now that its a bitwise op game

You can go farther. In my greedy mesher I store both block and ambient-occlusion lighting in textures, as bytes, using a bin-packing algorithm. One 2kx2k texture has always been enough, but I also added the ability to track which is needed by each chunk in case I needed many. This is particularly useful in city-like terrain where the geometry has a lot of flat faces made up of different types of blocks.

This is cool, I remember playing with greedy mesher but end up going back to a traditional one because I didn't find a good way to get rid of T-junction artifacts

I have an exam in relational databanks in 3 days. And this video and the bitwise manipulation really, really didnt help me at all. But its very cool stuff and im looking forward to try something like this as soon as i finished my exam

Loved the Flight of the Conchords reference

Why can't the mesher be happy with what it has

BLAZINGLY FAST

Thanks to practicing image manipulation in JS, this was surprisingly easy to understand and clicked right away for me. 1D data models and traversal is not simple, so I understand your pain.

God damn bitwise wizards, I really have to learn how to use that stuff, because in theory I understand it, but I don't know how to use it

This voxel engine looks incredibly advanced and would make a brilliant base for games! For future videos I'd love to see you implement a scripting language into an existing Rust project like Lua or Angelscript.

Lmao I wrote an algorithm yesterday for greedy meshing which does a bunch of neighbour checks for each block and then creates a bit mask from that. Definitely stealing the bitshifted comparison optimisation. This must be the most amazingly timed video I've ever seen.

15:04 this was the point I verbally said “this guys psychotic” but in a good way. This is a crazy way to think about this data but it makes so much sense! Good work man!

Nice technique. Possible considerations for the future: - With SIMD you can implement masking for each block type without having to split them into different array. Though it does mean a hard limit on the block types and chunk size. - I'm pretty sure SIMD could be used to "instantly" (

Several people have mentioned looking into SIMD optimization, but a few other ideas: 1) Using a fixed sized allocation instead of a Vec since the size is known. Not sure whether the entire arrays would fit on the stack but if so that may provide several speed improvements over a Vec on the heap. 2) It might be possible to combine both positive and negative edge detection into a single operation by using an XOR, but would require a slightly different method of iterating over them to pass into the greedy meshing. 3) Your structure for axis_cols has the data for each grid separated, a format similar as such: (y1, y2, y3, y4... x1, x2, x3, x4... z1, z2, z3, z4...) this means when setting the values you're writing into separate parts of the vec that might be far enough from each other to cause frequent cache misses. A layout where the three axis all are interwoven beside beside each others might be faster, such as (y1, x1, z1, y2, x2, z2, y3, x3, z3, y4, x4, z4...) 4) It would require a bit of rework but this seems very reasonably practical for a compute shader. 5) Would take a fair amount of work, but rethinking how you store the actual voxel data in general may make it faster to convert. 6) Again it would be a change in direction, but there are approaches people have taken where you can greedy mesh any flat surface, regardless of different types of blocks. The way that achieve this is usually to pack the color data for the chunk into a 3D texture and use it in the material/shader for the chunk mesh, then, rather than each triangle having a color, the fragment shader can use world coordinates to query from the color data as a 3D texture at the position of the face. Allowing a single triangle to have multiple colors on it. This makes the fragment shader slightly more complex, but in most examples of people using this technique it tends to improve performance in both rendering and construction because it can result in a massive reduction of polygons, especially as you add more and more materials.

I wonder if the data layout could be improved as it looked like you use sequences of array indices that are far apart from another. Depending on how large the data is, this could theoretically lead to cache misses as not the entire array is loaded into the cache at the same time. But it's only 0.8% of runtime and the Compiler probably already optimizes this. But if there was a slowdown caused by cache misses, improving the data layout could speed up the code a lot

3:00 as I always say "paint is the most important software for software developers"

This is the same algorithm as bitmap edge detection. Shift-not-and-ing is really common in other applications 🤙

Coincidentally I just implemented nearly the same thing a week ago, though I support octree blocks so it's a bit more involved, but cool to compare implementations. I made use of xor to detect my faces, never thought of just flipping the neighbor... My meshing ended up about 50% faster somehow after implementing it, even though it feels like more work is being done

Very very cool - gonna start on fire if you add more than 20 block types tho 😅

Amazing to see the level of performance you can get out of using the binary representation and this has me wondering if I can use any in my own projects. I suspect I will need something similar to create an AI navmesh in the near future. Fantastic video once again TanTan!

You're using bitwise operations to calculate binary derivatives. That's dope :')

This is awesome! I'm looking forward to attempting to implement this myself. I'd love it if you would cover ambient occlusion in the future or at least provide some resources for where you learned about it

I think this can be made even faster using SIMD-instructions. Most of these problems are similar to problems in parsing where I know that those instructions can make a big difference. Especially in that data preparation step.

Yes! He's back! Let's goooo!

My first idea was to just bitmask. If you have a 1x4 area and want to check the area next to it, it'd be far faster and cheaper to just get the area next to it, use the first one as a bit mask over it and if there are no differences then it's all good and you can proceed. If it isn't, you can check where the differences begin and then you can discard from the conflicting side and then keep going. Okay, seems like that's pretty much exactly what's done.

Fun fact, you can further reduce polygon count by allowing polygons cross (each other in) the same block type or culled space. z-fighting is not an issue as it is the same texture or not visible. I have demo and thesis on this. The following "donut" example requires only a single polygon :D 01110 01x10 01110

Very cool. I bet you can double the performance with some tweaks to how you manage memory. I see a lot allocations happening in loops when you could make 1 allocation outside the loop and reuse the variable for each cycle of the loop.

You love to see it! I've also been optimizing the Rust code of my Chess engine, although this seems exponentially more complicated 😅

a tip go further decrease the data creation time: You're always creating and releasing memory with those Vec's. You should find a way to allocate memory once and reuse it instead. Also, don't use the stack because it can heavily limit you.

Thanks from a godot developer (csharp) this is very useful there as well since bitwise operations work very similarly and especially with multimesh instancing! Cheers :)

I tried out the mesher in my own project with a different chunk storage scheme. I ran benchmarks on my project and got around 500 µs (microseconds) per chunk. When I ran your benchmark I was getting around 32 µs. Initially I thought it was just inefficiencies in retrieving voxel data since I'm using palette based compression. After some more testing I found that if I use your chunk generation code the benchmark result was around 50 µs. Turns out there's only a few solid voxels in the benchmark chunk which is why it runs much faster. The first chunk I tested/benchmarked had solid voxels in a sphere shape. Still my voxel retrievel from the chunk is significantly slower then simply indexing into a Vec. Mainly because I use bitpacking for the indices.

Babe wake up another tantan video has dropped

Idk if this would be any better, but I'd like to see an algorithm that doesn't mesh it at all, but uses the GPU to figure it out. Basically, you have a 32x32x32 chunk, with 32 quads from each of 3 directions, all facing the camera. When it comes time to render, you send those quads to the GPU along with an array with the 32768 voxel types, and the GPU would be able to draw each quad with the respective colors. To draw it in the correct layer position, draw all of the chunks that the camera isn't in order from furthest to closest, and do the same with the quads.

Funny and fascinating! Thank you!

Thak You! That video and research are so usefull! After watching your video, my greedy mesher looks so sloooooow :c

Really cool. I wonder how this would relate to the optimizations that Vercidium uses to get voxel rendering running at a claimed 12000 fps.

I watched this video and barely understood any of it, but it was a good watch

Mine is faster I dont use any meshes just face information and send that to the gpu Then with a shader you can procedurally make vertices and triangles

Less go. great video as always sensei

16:30 🤯whooooa, kudos on visualizing that! That really clicked well! 👏 Also this is a bit of a loop-unrolling idea, not sure if the unexplained ambient occlusion part defeats it, but instead of iterating over the 6 axis separately could you iterate over just the 3 (X, Y, Z, no reverse) and do the reverse calculations in the same portion handling the same axis? So grouping X and XReverse into the same iteration. Honestly it's a shot in the dark, and it's also not even a major fraction of the computation time anymore even if it did somehow manage to shave any time, but figured I'd contribute something while I'm here 😅

there are some weird similarities with your binary greedy mesher and my implementation of 2048 in the desmos graphing calculator. I love things like that

This is so cool and such a good explanation.

Could also generate the vertices on the GPU based on the block's coordinates if sending them over is a worry Edit: also this would let you run the code on the GPU which may lead to even faster execution

I think your memory layout can probably benefit a little from ordering by which stage of execution needs the direction. The newer CPU has a better cache and branch prediction, and that's why it outperformed on the culled renderer. The greedy mesher caused it to stall more, so these advantages were likely nullified. Your greedy mesher seems to tax the cache a lot - your blocks are 32x32x32 bits (right?), and interleaved in triples; but it could be better to somehow make them fit into 64x8=8x8x8 bits (64 bytes, a cache line) for each of their core operations. So, making the block smaller by a factor of 2 to 4 in every dimension AND ordering the memory according to execution order / ordering execution to be doing operations on directly adjacent memory blocks directly after one another could probably give you another big boost.

6:40 there’s a faster way to calculate h_as_mask (though maybe a very clever compiler might optimise it this way anyway) - start with all ones (ie UINT32_MAX) and shift right (32 - h).

Even before the OLC console game engine, back when computers didn't have bitmap graphics modes, all there was were "console" / terminal / text mode "graphics." You might be familiar with a game from that time called "Rogue," which is the "rogue" in "rougelike." :) What came before Fortnite? Gears of War. Before it? Unreal. What started it all? ZZT, a text mode DOS game from 1991. :D

Excellent video. The animations are easy to follow along with. Thanks for sharing. I'm curious about the method you used to profile your code to determine the execution time of various sections. I didn't see any particular video in your catalog that seemed to cover this, so perhaps a "How Tantan profiles his Rust code" could be an idea for another video.

Buffers can be prealocated and reused, that should speed up a bit more

damn i always had wanted to play around with bitwise manipulations, really cool video

I imagine, there should be a way to optimise the procedure at ~3:35 so that the whole meshing step is complete in the smallest number of expansions possible (for the general case).

Theres even more space for optimization when using SIMD and vector register, on xmm ones there is space for 128 bits, the main problem would be portability between architectures

Imagine doing all of that when you can just use instancing of a single quad of the chunk size, referencing a slice of the data and discarding empty air, and using data to write the proper texture tile on the quad, drawn front to back top to bottom. For each visible chunk. And get 1000x the speed 😅