GORGEOUS, speedy terrain generation [Voxel Devlog #14]
Vložit
- čas přidán 9. 07. 2024
- Try CodeCrafters for free today: app.codecrafters.io/join?via=...
Online demo: github.com/DouglasDwyer/octo-...
During this devlog, I unveil my techniques for customizable, optimized voxel terrain generation. I discuss how it is accelerated using the GPU, describe how interval arithmetic is leveraged to predict when regions of the world are homogenous, and touch upon how to apply interval arithmetic to 3D models.
Music used in the video:
Punch Deck - Homestead
Chris Doerksen - The Feeling
Corbyn Kites - The Woods
Chris Doerksen - Re-Introduction
HOME - 34 - Hry
![Adding ambient occlusion to my game engine [Voxel Devlog #15]](http://i.ytimg.com/vi/3WaLMBiezMU/mqdefault.jpg)
![Adding ambient occlusion to my game engine [Voxel Devlog #15]](/img/tr.png)
![Doubling the speed of my game's graphics [Voxel Devlog #18]](http://i.ytimg.com/vi/P2bGF6GPmfc/mqdefault.jpg)
![Making voxels MOVE with the separating axis test [Voxel Devlog #11]](http://i.ytimg.com/vi/PW1Xwc3zzNc/mqdefault.jpg)
Do you enjoy digging into the details of how things work while writing high-performance code? Then be sure to check out CodeCrafters using the link below:
app.codecrafters.io/join?via=DouglasDwyer
They have one project which is completely free to complete during their beta, and you can begin any of their projects for free! Get 40% off if you upgrade to a paid account within three days.
Man, you gotta make a discord. This is by far one of the best vowel engine series I’ve seen on CZcams, your graphics sorta suck but you are a genius
I'm glad you're enjoying it!
I agree, the graphics could be improved. There are two parts to this:
- I need to improve my shading model. Right now, the lighting and shadows aren't very detailed. I want to add ambient occlusion, reflections, dynamic point lights, and refine the shadows (which are currently buggy). This will hopefully go a long way toward making the game aesthetically pleasing.
- The textures, models, and other art could be improved. This is more difficult, because I am a programmer and not an artist. I will probably need to build asset authoring tools and hire someone to make good textures for me, since I do not have that skillset.
Let me know if there's anything else actionable that you think could be improved about the graphics!
what you're doing sounds amazing, not just the resulting look of the terrain, but how efficient and moddable it is. can't wait of users to get their hands on.
That optimisation is absolutely genius!
Amazing! That's so awesome you managed to implement what we had talked about in discord!
We need to see more of such dedication to optimization in the gaming industry.
The optimizations are one of the main reasons that I continue to enjoy building this project - they make things actually challenging.
@@DouglasDwyeryou might wanna take a look at the Minecraft mod called Distant horizons, it deals with hundreds of voxels in an efficient way
great progress dude, excited for this to be a real game someday!
Dang this is amazing ! What you did right there is almost like a small DSL! Congrats mate :D (Also omg your optimisations !!! Your engine looks more and more runnable on my computer xD )
Really impressive work!
trees and plants often follow a fractal pattern. You can probably procedurally generate all plants using this, and get plant variants by tweaking the number, frequency, and sizes of branching out parts of the plants
So stoked for this!
This is my favorite devlog, amazing results! Please think about adding liquid
The bytecode translation is very clever
This looks great ❤
I've no clue on game dev, but this looks cool. Good luck with your progress man.
Amazing stuff Doug! You have a new avid follower
Thanks Stephen! Glad you enjoyed the video :)
Your method that you used to generate GPU shaders is similar to high-level DSL Halide, only it has additional directives for scheduling generated code on the GPU to improve it's speed
Ooo, more on this fascinating project.
I wonder at what point we stop calling them 'voxels' and start calling them 'atoms'?
this absolutely rocks
Very nice!
Very cool!
1:51 thank you for sacrificing your PC for us
I had a similar idea with terrain generation based on how people used to export terrain from World Machine into World Painter for MC, never thought of turning it into op code and passing it to the GPU though. Though you've not only implemented it but made it 10x better (had I done it, it would've been on CPU and missing the interval arithmetic optimization).
I'll buy this engine even if I never use it.
Hmm, you might want to add some variation in the snow layer
The thing that usually seems odd in voxel games is how stuff is vaporized when you break it, what if you turn the chunks you "erase" into a completely different object, like you're breaking a cookie
It's very inspiring how in-depth your approach to this project is. Been watching since the 1st or 2nd devlog and the amount of concepts you've implemented is insane. Any reason you went with making your own engine versus starting with Bevy? Was it just easier to port your existing engine to rust vs porting it to Bevy?
Thanks for the support! I like to build things from the ground-up, and since I wanted to implement a custom graphics backend, I thought that it would be more straightforward to do custom. (I was learning Rust at the same time, which was tough enough on its own - having to also learn the Bevy API would have been even harder). I have no doubt that Bevy is a great choice, but as development continues my event-dependency library Geese serves quite well as a framework for things.
Awesome! Although I was wondering how effective is the interval arithmetic at dealing with complex fractal noise functions?
As shown in the video, the surface level chunks (where the terrain is defined by fractal brownian motion of Perlin noise) usually end up processing between 20-40% of the voxels. So I would say that it's pretty effective! For chunks in the air and below the ground, the results are even better, since interval arithmetic detects that the voxels are beyond the noise functions' ranges.
You are making a lot of progress dude. Is the engine still allowing modifications? Congratulations and thanks for the update!
The goal of the engine remains the same - I want to make it as moddable and customizable, so that users can create their own experiences. This terrain generation system goes a long way toward that goal!
Just found your chanel and this is truely amazing work!
I've also played around with the idea of GPU voxel processing to implement truely realistic large scale explosions in Minecraft like flattening buildings and scattering the debris behind the building (from the explosion position). Not sure if I'll ever get around to fully implementing it though, especially as GPU compute probably isn't available on most servers.
Do you have any plans for self-hosted Multiplayer and if so, how do you plan on addressing this?
Yes, multiplayer is already fully implemented and working! I have some past videos explaining it (although the mic on those videos is pretty awful, please excuse it). In short, I use WebRTC to allow peer-to-peer networked gameplay. Users can host their own world as a server and allow others to connect to it. This makes playing with others frictionless, is less costly because I won't need to host dedicated servers, and works even on the web!
Absolutely amazing stuff. Im wondering if you are able to customize the voxel size or if the engine will be coded to work with one specific voxel size.
The engine is optimized for the scale shown in the video (about 20 voxels per meter)! It should, of course, be possible to use bigger voxels in principle.
You should make the builds of your game playable for free. One of the reasons why Minecraft became so big was that Notch made his early builds available for free up until Minecraft Alpha.
They are! The demos can be downloaded now and are linked in the description. That said, there's not much to do yet other than admire the visuals :)
🎉
🎉🎉🎉
first
One thing isn't quite clear to me.
I have been thinking about doing something like that, but the major roadblock has always been this:
How do you know where the models/structures are that might intersect with a given region?
You can't just iterate through all the models right? And even worse how can you know where the models are, without generating the terrain around it first and sampling some blue noise and stuff like that.
The way that tree placement was implemented was relatively rudimentary: the trees are in a grid, and for each grid cell I sample a random number to decide whether to place the tree there or not. I know where to place the model because I just sample a single location from the terrain heightmap at the center of each cell. So the model placements are procedurally random, and this system could be extended to rocks, flowers, and the like. The system also has the ability to select a model from a list at random, allowing for more flexibility. If you don't like the fact that the trees are in a grid, you could apply a random offset to each tree or just use multiple overlapping grids to make the effect less noticeable.
For more complicated terrain and procedural structures like villages, I think that this approach is probably suboptimal. So for allowing the generation of dungeons and whatnot, I'll probably create some kind of CPU-side post-processing pass. It should be quick because octree merging is fairly fast.
@@DouglasDwyer Have you also considered caves/overhangs? With your current approach you will end up with missing trees/vegetation below overhangs and in caves, as well as occasional floating trees at cave entrances, depending on your implementation.
You are correct - as usual, it's a tradeoff. You could use a separate noise function to sample the locations of cave floors (although that may be harder with 3D noise) and try to place vegetation there, I suppose! But I think that the best approach will be hybrid, using the GPU to generate smooth terrain and small props, and then placing larger structures by hand on the CPU.
Overall, I do think that having a *pure world generation function* - one that can be pointwise sampled in a single step, without having to do post-processing like placing objects - is very beneficial. With a pure pointwise function, you can sample at lower resolutions in order to generate LODs for distant terrain, which is something I am itching to implement :)
@@DouglasDwyer In my game I solved this by introducing a separate pass, that first generates the terrain shape(caves+surface) at a 1 bit per block resolution. Then the main pass, which places the structures, can look into that bitmap. Using some bit operations, like counting trailing zeroes, it's quite fast to find the surface at a given point.
You also mention generation low resolution terrain for lod. I'm actually doing that already(it's kind of a necessity if you want high render distances), but structures are a bit of pain. Specifically I quite often get trees that change height in lod when there is high slopes in terrain, or even worse some just appear out of nowhere, because a different biome is sampled in lod.
I'd be interested to see how well(and how performant) your approach turns out in that regards.
That’s awesome! Is there a way using distance field to not load what’s behind mountains or other object? I think you would not need them anyway because the camera vision is obstructed by what’s in the foreground
I'm not aware of any way to avoid loading them completely, but using occlusion culling techniques one could definitely avoid rendering them!
There are a lot of really insightful solutions in this video! I'm curious about the interval math part, do you know enough about the f(x) / height function to predict if it will continue to be homogenous in a given step? In the past I have wondered if it was possible to sample a noise function with a lower frequency to tell if it was occupying a cuboid chunk at all before beginning fine sampling, is this something you're doing/have considered?
Yes, I have implemented interval arithmetic for Perlin noise, which is used to generate the terrain shown in the video.
This is accomplished by use of a Lagrange error bound. The typical Perlin noise implementation samples some random values which are either -1 or 1, and then interpolates between them. The interpolation function is usually 6t^5 - 15t^4 + 10t^3. It can be shown that the maximum rate of change in this function is 1.875. So if you are sampling Perlin noise on an interval which extends by half-length d in each direction, the error bound is +/-1.875d for each direction. Let me know if you have any additional questions - I'm glad that you enjoyed the video!
Have you thought of VR support? With such a fast rendering engine it seems like a great fit.
In my opinion you should also look into adding ambient occlusion, as things still look a bit flat.
I'm mainly focused on desktop support currently (one platform is hard enough, haha) but VR would be awesome!
I really want to overhaul the graphics engine and add things like ambient occlusion, reflections, dynamic lights, and improved shadows. So that is definitely on the list :)
Impressive! Would it be possible to use your lower-detail version of terrain generation to generate further out for longer distance views?
Definitely - for creating low-res terrain you could even just sample at a lower resolution, but the interval arithmetic optimization should make that even faster as well. I am planning on implementing this; it is one of the main reasons that I redid the terrain generation engine.
@@DouglasDwyer Unbelievable.. looks amazing! 😃 i wonder how modding api development goes? or is it going to be like framework/game engine? honestly considering it can even run in browser it seems like most promising voxel game/engine of all time, im kinda surprised you can do that with triangles lol, pretty crazy performance and draw distance/detailing for meshed voxels, and voxels overall
Yes, even integrated GPUs can handle a lot of triangles. With greedy meshing and LODs nowadays, anything is possible! The modding API is in-progress, but I've been feeling more motivated toward the graphics/GPU stuff lately and so will be working on that.
@@DouglasDwyer Even better this way! working on engine/features is often recommended before making modding api/game, and you got pretty neat design anyway to implement that later.. so excited to see what features/optimizations you are gonna add to graphics!
Heya, this is super cool! I thought I followed on your last video, but alas, I must have forgotten. Followed now!
As a suggestion, the contour lines of your terrain are SUPER apparent; this is just the resolution of voxels, of course. BUT, it's a problem that is incredibly similar to colour banding on displays. As such, perhaps you could implement some kind of dithering into your height generation algorithm? Deterministically based on location, of course.
Might look like shit, might be okay but not worth the extra processing, or might be amazing; would be curious to see how it works out. :)
(I suppose adding an extra high frequency octave of noise would do something similar and be more standard. But dithering might be cooler!)
Dithering is a fun idea, but I think the contour lines are apparent just due to the way that I shade the voxels. I'm not really sure if there's anything I can do about it without computing and storing per-voxel normals, and my tech is not designed for that right now. So it probably just has to become part of the art style :)
Can interval arithmetic be used to create large scale, zoomed out version of the world (i mean world MAP)?
For sure - you could even use it to create low-res terrain to display out at the horizon! But you could also do that just by sampling the world at a lower resolution. Interval arithmetic serves mainly as an optimization.
hey now that's very neat, i do wonder though, can the user introduce new mathematical functions just like that or do they have to define the interval arithmetic stuff for that function ? also, does it work for functions with multidimensional I/O ?
The terrain pipeline bytecode represents a series of operations that are composed together! So if a user wants to create a new mathematical function, as long as it is a composition of existing functions, it works out-of-the-box. This should be possible for pretty much anything, since the bytecode operations are pretty much in one-to-one correspondence with WGSL functions.
When you say multidimensional IO, I assume that you are referring to vector math? Yes, all bytecode operations have overloads for different vector types, just as in shader languages :)
@@DouglasDwyer that is quite amazing !! can't wait to tinker with it hehe
Have you tried making different biomes using some of the bugged terrain generation? I think it would be cool to have a biome made of pillars
Yeah, that would be neat! Maybe a biome made of pillars could be some kind of city with buildings, or something. However, I need a better way to write the terrain generators (like a node editor) before adding biomes because editing the bytecode by hand gets tedious.
Can you explain the interval math in more detail? I understood the logic for a function that's monotonically increasing, but I don't know how you'd apply that to something as complex as terrain generation. Even a 2d noise pattern alone -- how would you know if a given region was always increasing without sampling all of the relevant points?
The function doesn't need to be monotonically increasing - all you need to be able to do is generate a lower/upper error estimate. For analytic functions (arithmetic, trigonometry, etc.) you can typically figure that out explicitly. For other functions, you can use a Lagrange error bound or find the maximum possible derivative.
For 2D Perlin noise, the maximum derivative technique is the one that I use. If I recall, Perlin noise involves an interpolation step (which has a max derivative of 1) followed by a smoothing step (which, in my implementation at least, has a max derivative of 1.625). So the max rate of change in any direction for Perlin is always 1.625. Hence, if you sample Perlin noise at a point A +/- E, the result is Perlin(A) +/- 1.625 * E
@@DouglasDwyer Thanks! I will try to figure that out, haha. Would love if you made a video about it, since you're so good at explaining these concepts.
I'm curious how you're getting the information from the GPU into the Octree. For me writing that much data to an Octree with 64^3 voxels takes 100ms, which is really slow in my opinion. Are you looping through the data and adding it voxel by voxel or is there some magic I'm not thinking of? I'm sure my octree isn't the fastest code out there, but I think I've got it reasonably efficient.
There are two optimizations at play here:
- The octree is constructed from the top-down. Because I separate generation into a coarse and a fine pass, I don't need to subdivide any regions that the coarse pass marked as homogenous, as described in the video. Those homogenous regions are written to the octree without sampling any voxels in them.
- For any sparse regions which require per-voxel generation, the GPU generates them in 4³ blocks, one block per workgroup. These 4³ blocks are converted to the octree format directly on the GPU using workgroup memory. On the CPU, I am then able to simply memcpy() the data for each 4³ block into the correct place.
That said, I think that there is room for improvement if an octree implementation takes 100 milliseconds for a 64³ volume. On a 3 GHz processor, that would imply that each voxel consumes 1144 cycles of processing (3 * 10^6 cycles/sec * 0.1 sec / 64³ voxels).
@@DouglasDwyer Quick reply! Thanks for the info, I'm sure it will be helpful.
I was skipping homogenous regions, but I didn't think to do the blocks method. Despite programming for over a decade, I'm pretty new to lower level stuff like memory so improvements there would likely help a lot.
For now I am going to settle with flat arrays and maybe revisit the octrees after more work is done on getting something visually appealing.
Will this be open source at some stage, or just for your own game?
I eventually hope to turn this into a publishable game or service, so I don't plan on open-sourcing the complete engine in the near future. However, many custom components of the engine (like the event library, networking library, etc.) are available and open-source on my GitHub!
Hey...I'm just getting started in game dev, I want to make a little voxel world -- I see people are making voxel game engines -- is there a reason not to use the Unreal engine to make a voxel world? (I don't have coding skills)
Have you ever wanted to create terrible terrain with horrible frame times? I have just the video for you!
Hey, the DSL your making is really sick. I know a bit about writing compilers with llvm if you are interested. LLVM has Just In Time compilation if you are interested in making anything run CPU side instead of as a shader.
Thanks for the suggestion! Compilers are a fun topic, but sadly I don't think that LLVM is a good fit for me. My project needs to run on the web where CPU-side JIT is impossible, and the terrain generation DSL is specifically designed to take advantage of GPUs' characteristics. The good news is that (once converted to a shader) the vendor-specific drivers will optimize the DSL, probably using LLVM under the hood!
hey, you should try recording voice using your phone
these are usually better than headsets/standalone pc mics
Thanks for the tip! I actually am recording on my phone, but I have a cheap Android. I'm intending to get a real podcast microphone in a few weeks :)
@@DouglasDwyer , ah, okay, but that's cool to hear you're getting an upgrade!
it is sad that you can't cut rigidbody, i mean when tree is cut , and in online preview you can't change building block. The preformance is impresive but i would like to see liquid some water as well as some basic vechicle. in multiplayer you can see number of players only in menu responsiveness/sync is nice
Thanks for trying out the demo! As you observed, it is only a tech demo. Things like menu and gameplay are nowhere close to finalized. Water in the future would be cool! :)
yes i know it's a demo, oh and server lagged out when i get to -3k so i suppose there is not optimization in that direction but it is a nice game already its like first versions of minecraft in browers with better looks
this will be minecraft 2.0 lol
epic.. but one important question: can i blow stuff up?
Haha, that would be a very fun feature to add, especially since I have physics implemented. However, I am still working on the core engine features - like rendering - and thus gameplay is still a ways off :)
huh. could you iterate, rather than just big box little box? like you have a 16x16 box---it's not homogenous, so break it into 8 8x8 boxes and check each one. If they are homogenous, set to material. If not, break down to 8 4x4 boxes. And so on and so forth.
Great question! You definitely could, and this would be an excellent top-down approach on the CPU. However, what you're describing involves lots of control flow, which would make it inefficient on the GPU. (You'd need a separate compute shader pass for every box level, probably.) Thus, the two-level approach is what I chose.
Implement hydraulic erosion
Hydraulic erosion unquestionably makes terrain look better. I'm focusing on adding other things right now, but the terrain generation system is user programmable. As such, it might be possible for end-users to do in the future!
Pff, you only spent 3 weeks making all this? I've spent waaaay longer to get waaay less. We aren't the same.
Well, I've been working on the project as a whole for two years, and these terrain generation ideas have been cooking in my head for months. So don't sell yourself short! Hard things take time.
@@DouglasDwyer Lol, I was just being sarcastic. Very good work, though! Was very interesting to watch.