3D World Generation: #3 (Quadtree & LOD)
Vložit
- čas přidán 13. 04. 2020
- 3D World Generation: #3 (Quadtree & LOD)
This is the third in a series of 3d world generation tutorials, covering my quadtree implementation, terrain level-of-detail, and leading to infinite procedural terrain.
What's covered:
* What are Quadtrees
Go over my quadtree implementation and how I ended up using it for LOD (level-of-detail) on the terrain.
* Optimizations
Some optimizations I threw at the implementation to reduce the framerate drops when generating the terrain.
In the future:
This is intended to be part 3 in a series of tutorials on the topic of 3d world generation. Planning on making this a planetary scale thing in a coming tutorial, so look out for that.
Full source code for the project is available, so if you're interested in fiddling with the code, screwing around with it, or improving it.
Github: github.com/simondevyoutube/
Clip Credits:
Travel Albert: • (Remember to Breathe) ...
Justus2utube: • Lord of the Rings - La...
Edson Flausino Junior: • Video
BBC Studios: • Jumping From Space! - ...
#proceduralterrain #gamedevelopment - Věda a technologie
Like & Subscribe, thanks!
Hello, how do you blend the vertices for each plane in the quadtree?
@@diegomacias7727 i guess he does not... but I am not sure
One possibility is to check the camera distance from the origin, when it reachs a threshold, move it back to the origin and update the chunks heightmap, so you fake movement and also you need to move the placements. But this way you deal with the problem of precision of the position, when you use the usual 32 bit floats, avoiding other problems when you reach huge numbers.
Maaaaan. This channel, what a treasure chest.
Amazing video, didnt even know Javascript was this powerful
Thank you for these tutorials!!! I hope you never stop
ty, got anything you wanna see covered in future vids?
It would be awesome if you could explain 3d Gaussian splatting.
I'm struggling and your videos make things so clear.
Wow, your tutorials are so awesome. Very informative, concept are very well explained. Instant subscribe
This is exactly what I need for my current project. Thank you for sharing!
Np, what are you building?
@@simondev758 An open world game that runs well on my phone. I'm particularly interested in having the land change based on climate, rockiness etc instead of biomes
im working on a very different project and needed to understand quad trees and how to approach it. This vid was soo helpful thanks!
Amazing work Simon thank you 😆
How this quadtree would be combined with a tesselation shader? I've got rendered 64 * 64 quad instances and tessellated them in a shader that when the plane is closer to the camera its inner and outer level increases. Although it works, the world is still quite small and I've no idea if I need to extend my shader code or do some stuff on a cpu side. I've found your videos incredibly interesting, but also I'd love to learn more about tesselation shaders and I cannot find any articles that described this topic as if I were an idiot :( and I don't quite understand them.
if it generates a noise for a plane with a certain number of segments, how do these vertices join the vertices of the planes adjacent to it?
Awesome! True gem!
do you keep the textures resolution high between different size nodes?
because it looks funky when texture resolution changes if it has less reference points
i mean the resolution of moisture texture
i wanted to access those also on CPU so i can do gameplay stuff based on those too
These are just vertex shaded IIRC, I don't touch on textures until a later video.
Do you, in general, de-quad areas when they are not close anymore? Is that what you did with the pool?
Also, I saw an inmplementation, where the quad remaind the same, and only the noise moved “through” the mesh, when the player was moving.
Worked great for an infinite plain, but wouldn’t work for interplanetary rendering I guess.
Dynamic tessellation is definitely something I'd like to add, but hasn't been high on the TODO list.
re: second idea, yeah I think I've read about that idea, although I haven't tried it myself. The only concern I have there is that as you move, you want to do it incrementally so that the entire mesh doesn't bounce around. It's an interesting approach though.
@@simondev758 thanks.
It’s awesome, that you invest the time to reply.
Hey I want to draw a line between 2 points in terrain .....line does not attach with terrain ..how to solve this ??can u plz help ..
Hi Simon, thanks for the videos. This content is really helpful and unique.
I wanted to know that if you recreate QuadTree every frame? If yes, wouldnt that be too slow?
No problem, glad you're finding it useful.
As for your question, yeah I'm recreating it every frame. Is it the best possible way to do this? Almost certainly no, but it's more than fast enough for showing off the technique, and it's simple to understand. I'm a big fan of profiling to decide when to optimize, and this runs at 60fps easily, so I doubt that the quad tree code contributes much per frame.
@@simondev758 Yeah. You're doing it the standard way. It's faster to rebuild the tree than try to adjust it every frame
how did you stitch the lod difference between neighboring chunk?
I haven't yet, coming in a later tutorial. I swear, I'll actually make one at some point. I actually have the code for some later stages done, but getting around to making a video takes me forever.
How did you manage to get the chunks match with each other if the algorithm is random
Noise is random but continuous
Hey SimonDev! I cloned the repo for this, but I am noticing it is not infinite. The terrain is huge, but you can reach the end of it. Is there an easy fix for that?
I think in this video I was working towards a planet for a later video, so the structure isn't appropriate for infinite size.
Very Nice 'N' Helpful
Thanks, are you working on something related?
@@simondev758 Nah. But I Like To Watch Javascript Based 3D Modeling, Images, Video
Hi, did you try webworkers for the terrain builder? Maybe it wouldn't fit your need, but instead of spreading the generation in the UI thread, i could allow to process it in an independent thread without freezing the UI. Or maybe I'm totally wrong :-)
Anyway, I'm a huge (huge!!) fan of all your video and the way you present them. Thanks for sharing them!
Great idea! Yeah that'll totally work, I actually do it later in the series, I think it's #7.
Is this on WebGL, WebGPU, or threeJS?
All in JavaScript?
Hi. I really enjoy soaking your knowledge, gerat stuff!
In the seams between each terrain chunk I get a visable seam duo to normals. I am gueesing that it comes from the lack of interpolaton done by the vertex shader since everything is drawn seperatly.
If I am not way off, how do you solve this?
So I have it fixed locally, but haven't made the video yet. I'll describe the fix.
Assuming you've fixed the actual gaps between different chunks, you've still got lighting discontinuities caused by the normals. You're on the right track, the normals are the issue. The problem is that the normals are generated by generating face normals, and then averaging all the face normals for each vertex.
Imagin3 2 triangles that share an edge. The 2 vertices that form that edge, when you calculate the normals, will get a normal that's averaged from the 2 different triangle faces. Then imaging if those 2 triangles had the exact same edge, but you didn't average those normals for the edge vertices, you'd see a lighting discontinuity there.
There's a bunch of complexity here because you're calculating different levels of detail, and additionally they're being generated on different threads. What I did was used a stable way of generating normals for those edges, by taking finite differences instead of face normals. It worked pretty well, not 100% sure it's the way to go, but so far it works.
@@simondev758 Oh thanks! I got the normals looking good by generating an extra column and row on each side of the chunk to get the correct normal at the edge of the chunk.
@@DomainDrivenDavid Nice! Are you using different levels of detail too? I tried that approach, but wasn't able to fully get rid of the lighting discontinuities.
@@simondev758 Yes, 88 quads of 100x100. I am no pro tho, so it may very well be that you see lighting discontinuities where I do not. I can link short video if you like.
@@DomainDrivenDavid I'm kinda curious, can you run a test where you reduce the chunk resolution super low, like 4x4, and see if the lighting holds up between neighbouring chunks of different resolutions? Need to make the terrain pretty bumpy. This is how I got mine to show the problems prominently.
hey, newbie game dev. i got a question, and maybe you can make a video on this. why is there so much emphasis on triangles but majority of the systems like grid partitioning is done with right angle triangles which creates squares. wouldn't equilateral triangles and a hexagon grid system be better?
i did see your latest video and i think it was a bit of an oversight but even then, your explanation of wasted computational power on the clusters of quad pixels was far less then the right angle triangle compared to the equilateral triangle. (edit: the time stamps at 13:10 vs 13:40 in your latest video - When Optimisations Work, But for the Wrong Reasons)
maybe its the simplicity of the code when writing a square grid system compared to a hexagon system?
Great video!
I wonder which algorithm are you using for the water?
Pretty sure it's just one of the canned ones with three.js.
@@simondev758 Thank you!
I see in the wireframe that smaller chunks are not being stitched together with bigger neighbor chunks. Wouldn't this normally create cracks since the smaller chunks have extra vertices on the edges that wont match up correctly with the edges that have less vertices.
Btw, src isnt up on github.
Yep, fixing the seams is on my todo list :)
When I get a minute away from the kids, I'll just go over every project and make sure they're all up. Hopefully today.
Yeah, I pretty much came across the same issue. It was impossible to not notice the seams when the camera is closer to the ground, like how a player standing on the ground would see things.
Although I haven't quite figured out how to work it out, my theoretical solution for this was to have a transition when a smaller chunk meets a larger one. The idea is that the row of vertices in the larger chunk are the same distance apart where the large chunk meets the small chunk, and the row after it is normal. In that row of squares only, you have 3 triangles per square instead of 2. It's hard to explain in just words, so I left a link to a picture of what I mean: gyazo.com/45369ef94042c0d66c8b1425a587aee5
I haven't quite figured out how to put that idea into code, since it basically alters the foundation of triangle generation that I set up earlier, but that's the idea of it.
I ran into this with LOD planets and would also like a solution
Sorry for the late reply, these reply comments don't seem to show up in the admin dashboard in youtube so I had no idea anybody had asked.
I haven't revisited this yet, but off the top of my head I think you need to create a skirt around the quadtree cells. I'd imagine that you could either tessellate the lower resolution cell near the edges, or (easier) just force the vertices near the edges of the higher resolution cell to match their neighbours. This should just require a cell to have the edges of the graph and to use neighbouring cells for guidance when generating.
hiw did you solve the crack problem
Are there compute shaders in three.js?
WebGPU just landed in a recent version of chrome, so yeah as of now it's available.
I gave it a try to the github repo and I happily fined out that it is possible use the mouse to rotate infinitely the camera when the cursor is hidden
nice
Checking chunks for division can be implemented branchless (without if)
Interesting, got some code with the changes? And any idea how much of a speedup that provides?
@@simondev758 instead of using if checking every chunck you can just round position to exact chunk origin and get chunk id (thou to go deeper you must use loop). Example: floor(x*chunksizex)/chunksizex - gives x origin of the chunk that contain that x coordinate. Dividing again by chunksizex will return chunk number from 0 x
I dont know by how much exactlcy it speedup, because I were doing something simillar before these tutorials on GML
Good job! Was helpful, even tho I don't do this in JS.
Awesome, yeah I try to explain it in a way that isn't platform specific. What did you end up implementing it in?
@@simondev758 Well, I implemented a quadtree before, I was just trying to get into it even more.
FYI, I implemented QuadTree in Godot, it's freely available. github.com/sairam4123/QuadTree-Godot
Nice, haven't tried Godot yet, on my TODO list of things to try.
Don't forget to check it, it's cool. I've been using it to develop my big game.
Are there no seems ?
I deal with them in a later video
All of this is running on the CPU instead of the GPU? If so, why? Shouldn't ThreeJS optimize for that? Is it not its responsibility?
Not quite, Three.js is a wrapper over WebGL. Its' responsibility is to make that easier, add additional functionality like texture/model loading, scene management, that sort of thing. There's really nothing that will "move" things from the cpu to the gpu except you, the programmer.
Writing these for the cpu is just easier, making this all run on the gpu is totally doable but adds an extra layer of complexity to these tutorials.
@@simondev758 Thanks, that clears it up. Follow up question, where exactly do you need to implement changes to make it run in the GPU? In the custom shaders you're writing?
@@ezequielgarrido51 In WebGL2 yeah, you'll write it in the vertex shader to deform the mesh.
@@simondev758 Thanks!
Do you have the source code?
It's all on github: github.com/simondevyoutube
google maps and nasa whirlwind (open source c#) use threads.
Thanks! I'll check those out. This series also integrates threading later, I think around #6.
like
Isn't this an octree not a quadtree since it's in 3d?
Octree divides 3d space into 8 children, along each axis. This only takes xz into account.
@@simondev758 gotcha thanks for the explanation