Incredibly impressive, especially to get it running this well optimized. Huge props, and good luck expanding on this! Excited to see where you take it :)
We must have been bitten by the same bug, because I am doing this exact thing in my current project. Though I'm not using surface nets, but rather full dual contouring. Your work is looking great. Keep it up. Subscribed!
@@thecodejar I'm not actually doing the full QEF for vertex placement. I'm somewhere between surface nets and full DC. I'm iteratively pushing the vertex toward the surface with partial derivatives. I also using ECS so that helps with performance. I'm excited to see where both our projects go :)
omg I have been trying to do something like this for months and you figured it out!! Some of the concepts you listed are new to me (like surface nets), so I'll have to look into them more. Thanks so much for sharing!!
It does not really affect performance. I currently only use the original SDF functions to construct an octree. If not edited, the octree is constructed once for a particular area, and the SDF does not have to be evaluated again, as it uses the values from the octree directly. If edited, the octree is currently fully constructed (that is, subdivided to the maximum depth only near the surface of the original SDF function) within an AABB around the the edited operation, and an operation (difference or union) is applied to all values in the tree and the new SDF function (e.g. a sphere). This does mean that the octree does not store a true SDF approximation as soon as it has been edited once, as values far away from edited regions are not updated accordingly. For isosurface extraction we only care about the surface, so that is not a problem. I am playing around with implementing a faster system that allows me to edit huge areas (sphere of r=1000 or larger) extremely quickly, but it is hard to debug and not really important for my intended use.
@@thecodejar So you're basically saying that any new edit is done to the geometry stored in the octree directly, without using any SDF that has been used previously. I.e. once the edit has been applied, you can discard the SDF (of the sphere in this case). Am I right?
Neat project! A question: is the initial terrain SDF (before edits) a heightfield? (it appears to be?) If so, have you considered using a terrain SDF that is fully 3D? (allowing for caves, overhangs, etc.)
This is seriously awesome. I tried something similar, but I never managed to tackle the difficulties connected with creating terrain. What kind of octree are you using? Mine helped with ram usage but greatly increased the time of reading/writing data from the octree. I created one that mainly used classes for each node containing possible references to other classes for other nodes. How did you manage draw calls? Are you using some kind of mesh batching for neighbouring chunks? And do you reuse vertices or do you generate 4 vertices for each new triangle, even if there is already a vertex at this position in space? In general, how is it possible to achieve that kind of performance at the beginning of the video. Generating a single chunk of 32 x 32 x 32 already takes kinda long for me in c#, so it's truly fascinating to see this kind of speed.
Frankly I am using arguably the simplest octree with hardly any optimizations, essentially like you described (reference to parent node, and reference to an array of child nodes). - As I use the godot game engine, I don't actually have very much control over the exact draw calls, and I believe there will be one for every terrain chunk (I do enable occlusion and frustum culling, which helps). It could be interesting to manually apply batching, but that makes editing the terrain more complex too. - I reuse vertices! It's rather simple to do with surface nets compared to marching cubes. - I use multithreading in two stages, first I generate the octree. once all threads are done, I use a scheduler to assign each chunk that needs to be meshed to a single thread, so I can mesh the entire world rather quickly. Overall, the process takes about a second for the entire terrain, running on 12 threads on my 5900x. I did try to create a rather optimized meshing function that operates linear time, by first creating a look up table of all the leaves in and directly around a chunk. that way neighbour lookup is in constant time during the two subfunctions of surface nets that iterate over all leaves (those stages being vertex placement & quad formation) I hope this helps! I am honestly not fully happy with my performance yet when it comes to moving to different parts of the terrain. it works well enough but there are some issues with updating colliders that slow the engine down, and in general my solution being too slow causing a delay in edits to the terrain while its changing level of detail.
Impressive work!! Is the initial SDF (before any edits) generated from a noise texture? For serialization, would you just store the deltas from the original SDF? So many possibilities…
Thank you!! Yep its primarily based on Fractal Simplex Noise. For serialization I was thinking of some way to only store modified parts of the octree, I suppose similar to "storing deltas from the original SDF". It's not something I have implemented yet, but might be interesting to tackle later on :)
This is amazing! Subscribed!What I can’t figure out is how you calculate the shape of the terrain from sdfs? Do you Boolean together a bunch of spheres or somehow make a Perlin height map into an sdf?
Thank you! I am still unsure what the best method is. Currently I have a TerrainSDF function that uses 2d fractal noise. I map this to a height, and apply this to a plane SDF. Additionally, I scale the distance proportional to the inverse magnitude of the gradient (i.e. steeper terrain is smaller distance values), which seems to work pretty well. I experimented with the techniques explained in this amazing article: iquilezles.org/articles/fbmsdf/ But I found that performance was much, much worse. I am honestly not really happy with the current SDF, and I want to experiment with some other techniques. For instance, I read a paper about using phasor noise to mimic erosion. I hope this answered your question!
Fabuous! one question: since you use SDF, how to handle the situation: numerous players * years modifying in a server? like when they Digging/Mining, or Filling the ocean, every Shovel is a SDF_sphere() right? then as more SDF accumulated, then more Evauluation time and Storage space are required right? is any solution to handle this 'issue'...? Thanks, i know SDF is cool, like the "Infinity Detail", Fast LoD, Percise CSG, etc
It is not really an issue, but at a cost. I use an SDF for the terrain to populate an octree, with higher detail closer to the camera and to the surface of this SDF (i.e. subdivide a node if close to the camera and the SDF value at its center is smaller than roughly the node's edge length.). Leaves have a minimum size, which means the resolution of the terrain is bounded by that (in the video that is edgelength 1.5, or volume 1.5^3 =3.375, I have played around with volume = 1) However, this constraint allows us to use boolean operations such as union and subtraction to combine values in the octree with new SDFs, the results of which are stored in the octree, instead of permanently evaluating the terrain SDF as a series of operations and SDFs. This means that yes, a more complex terrain will increase storage space (evaluation time not as much) as more octree nodes might be required, but it has so far not been an issue. For reference, I have not bothered to optimize memory usage with this particular implementation yet (an octree node instance is quite big, as I use multiple pointers, full 32 -bit floats, 128-bit color mask, 96 bit center, etc) As the LoD system keeps the node count to a relative minimum, costing under 1gb of memory when the scene is initially loaded. I hope this answered your question!
How does adding something like an entity out in the distance get affected by the LOD in this example? Say you populate the area with trees (which are not made of voxels): are they going to look like high detail trees painted on a low detail surface, or will they also get some kind of lowered resolution? I imagine that in the former situation, another service could handle entity rendering specifically, so that a forest doesn't look goofy off in the distance. This is very interesting and is exactly what I am looking for my project. The video is very well made! Edit: just saw your most recent video. Neat!
Yeah my most recent video answers this! I think its best solved with a secondary octree to allow for better control. For instance, you might need more/less terrain geometry without changing the tree count. Thanks for the complement :)
Cool video. I am an absolute beginner in the topic of procedural generation, but I want to know if it is possible to create a similar generation and destructibility using surface nets as in Deep rock galactic?
I love DRG! I think it could be possible, but it's not how DRG does it as far as I am aware. I'm sorry for not being able to back my claims, but somewhere I've read that DRG uses 2x2x2 meter chunks (very tiny!) and directly modifies the meshes using "Constructive solid geometry", similar to how you might use boolean operators to combine meshes in blender (or other 3d software). This has the great benefit of being able to represent complex geometry, notice how you can dig very precisely in that game. However, for large terrains, it would mean that you need a ton of drawcalls. I imagine DRG gets away with this because of their cave designs in combination with occlusion culling. As far as I am aware, DRG does use marching cubes to initially generate the caves, and you could use surface nets here instead. But, If you just need the player to dig "player-sized" tunnels, surface nets can absolutely work! It seems in my implementation that a diameter at least two to three times greater than the minimum voxel edge length results in smooth enough traversable tunnels. In conclusion, it could work, but i doubt it's what DRG uses.
@@thecodejar Thanks for the detailed answer. I've read a little bit about marching cubes and marching tetrahedra. To use them on a large scale, compute shader is used, for me this is a very difficult topic, since I am not a programmer and especially not a mathematician. Is it possible to implement a procedurally generated landscape of sufficient size (approximately like yours) using only GDScript with sufficient optimization (if divided into chunks and using LODs)?
This is cool, but it pretty much goes over the same stuff everyone else posts. The tricky part is the seams between chunks at any LOD. Would be nice to have more information about that as there's a lot less information about this online
@ would you be able to explain how you went about that portion of it? Or some psuedo code would be even more helpful No worries if not but that would be super appreciated 😁
Here is a quick overview: First realize that I only consider transitions between LOD of magnitude 1, i.e. only transitions between neighbouring level of details. This makes the algorithm easier, but imposes the constraint that only such transitions are generated by the algorithm. To achieve this, it helps to enforce LODs in the octree to child nodes (e.g., you might have a node that itself is LOD 1, but its children are split up being LOD 1 and 2, caused by determining LOD based on distance(camera,node_center). Here we enforce LOD2 children to be LOD 1.). Furthermore, LOD radius is exponential. To actually generate the mesh, I do the following: - collect set C: chunks (which are themselves nodes in the octree) that need to be meshed. - for each c in C: -- create a look up table (LUT) that arbitraty positions to the leaf nodes within (c union a shell of size min_node_size around c) -- each leaf is wrapped ina class that stores the maximum corner it takes up in this LUT. note: nodes of neighbouring chunks of lower LODS will be larger here, and will take up more spaces in the LUT. -- iterate through the nodes, and calculate vertex positions using the surface nets algorithm. this is done using the bag, or non exclusive set of neighbours found at every combination of : (stored maximum corner +1 in every dimension, i.e. 8 neighbours in 3d) -- now we connect the vertices: iterate through every node, and this time get the _unique_ set of neighbours in the 3 case: +yx dimension, +yz dimension, +xy dimension. We should here either get 3 or 4 nodes, 4 in case all neighbours are of equal size, 3 if it directly neighbours a full face or a node 1 LOD lower (thus double edgelength). Now its important to realize that this only works in the direction of decreasing level of detail (or increasing edge length). To ensure it works in all dimensions, we compute the octant the chunk is in relative to the camera, and change how we handle the maxmimum corner/neighbour finding accordingly. This essentially covers everything. It is quite a lot, and I will not expand on this much further in this comment thread. If it is still unclear, and I admit this comment was hastly put together, I will consider making a followup video on this, as I have seen more demand for a greater explanation of covering LOD seams.
I have not decided yet. My primary goal is building a portfolio with algorithms related to game technology / real time graphics, but I might decide to open source the code later on.
A while ago I did a cubemarching algorithm using godot and found it very difficult to continue the project because of how godots arraymesh res is structured, how did u handle this difficulty, did u even use array meshes??
Yes I am! I dont use the surface tool, but I directly create data buffers (index, vertex, normal, color), and assign those buffers to the right indices. It works quite well. I did notice performance issues when creating and deleting many nodes, so i created an objectpool system (Only recommended for C#, but may prove beneficial for GDScript also). For some reason godot would sometimes crash due to queuefree being called. I'm 99% sure that's an engine bug.
@@thecodejar hmmm, thanks for sharing, ill try to implement that when I eventually return to that project, may need to read more on exactly how surfaces are stored in array mesh cause the vertex info is quite a mystery to me rn, once again thanks for sharing
Yeah I do. I am working to optimise the system further to make it as seamless as possible, but it works reasonably well currently. I update the octree if the camera has moved 64 units, and I only remesh parts of the terrain that have a different LOD thanks to the camera shift.
Not sure! I am not designing this as a godot plug-in or game at the moment. This project is currently primarily a challenge for me to improve my practical software engineering and computer graphics skills :)
Its an incredibly hard problem, I tackle it as follows: First, I make the assumption that neighbouring chunks differ at most 1 Level of Detail (LoD). Secondly, when building the octree I ensure that within a chunk the LoD is the same (i.e. all leaves in the octree considered for meshing at the same size) Then, before meshing i collect all leaves in and directly around a chunk. I then create a look-up-table (LUT) with all the leaves in it. This takes O(|leaves|) time, but it allows me to find neighbours in O(1) time! Then, when meshing, I can basically use normal surface nets using the LUT, with the only exception that i need to check 4 neighbours per face instead of 1 if the current node we are considering is twice as large (hence the at most 1 LoD difference assumption!). I hope this helps! Let me know if you have any more questions :)
There are slightly more details in my blog post: jorisar.github.io/portfolio/posts/smoothvoxelterrain/ I am not planning on making a follow-up video unless I make some larger technical changes. I did just watch your awesome showcase of your terrain, looks great! If you want you could share your discord tag and we can share some insights :)
It's a smooth voxel terrain, so instead of rendering the voxels as "cubes" I create a smooth mesh that approximates the surface described by the voxel (or volume element) data better!
Yes I am! It's a lovely engine, and I prefer using it over unity. I might make it into a plugin, but I would probably create a C++ GDExtension version in that case.
Don't count on it too much i'm afraid... One of my next projects will likely be a GDExtension experiment, based on that I will see if it's worth converting the terrain to one :) For now, stick with technologies like Zylann's godot voxel (which is much more mature than my solution regardless).
If you already have an SDF for your terrain, why not render it directly? It's not terribly expensive to raymarch an sdf. A meshing solution is fine too, just seems kind of unnecessary if you already have an SDF.
The rasterization pipeline is still by far the most optimal way to render large scenes, especially in combination with level of detail. But most importantly, This allows me to keep most data on the CPU which allows me to do collisions more easily. I am planning to play around with volume visualisation on the GPU at some point :)
how large are your octrees (depth) because you seem to be dynamically changing them quite easily and this is usually an issue. I'm curious as to how you got past it.
I can get away with fairly large voxels, as I'm using surface nets with interpolated vertices. I recorded the video with an octree depth of 14, and an octree scale of 1.5. This means that the smallest voxel is actually (1.5x1.5x1.5)m^3. The overall octree has an edge length of 1.5 * 2^14, resulting roughly in a 25x25km terrain when seen from above. This resolution is way to course for mostly anything that is not terrain, so I'm working on a secondary system that populates the terrain, similar to how you would place trees on a heightmap terrain.
Hey @Code_Jar I'm currently working on a similar project. At this point i have managed to generate terrain using SDFs and fast surface nets. But i cant get rid of the gaps between chunks when using LODs. I would love to get your assistance on that, maybe have a look at your implementation, so i can reproduce your astonishing results. Is there any way to contact you? Greetings, Ben
For now I will leave my solutions closed source, as I am unsure about my end goals with the project. I will launch a discord server next video for further (technical) discussion, so stay tuned :)
Bro just dropped one of the most Impressive videos ever and expects us not to find it!!!!!!
Haha thanks :)
there's some serious 3Blue1Brown level of quality right here. Glad to be one of the first subscribers!
Thank you :D
This is amazing man, keep pushing on, and I love voxel procedural generation.
Thank you! I have quite a lot of ideas in mind :)
Incredibly impressive, especially to get it running this well optimized. Huge props, and good luck expanding on this! Excited to see where you take it :)
We must have been bitten by the same bug, because I am doing this exact thing in my current project. Though I'm not using surface nets, but rather full dual contouring. Your work is looking great. Keep it up. Subscribed!
Awesome! I could not find many implementations of this idea at the scale I wanted online, glad to see more people are tackling it!
@@thecodejar I'm not actually doing the full QEF for vertex placement. I'm somewhere between surface nets and full DC. I'm iteratively pushing the vertex toward the surface with partial derivatives. I also using ECS so that helps with performance. I'm excited to see where both our projects go :)
omg I have been trying to do something like this for months and you figured it out!!
Some of the concepts you listed are new to me (like surface nets), so I'll have to look into them more.
Thanks so much for sharing!!
It took me quite a while to piece together too!
I'm glad you found it useful, good luck with your project :D
@ thanks very much :)
@ good luck to you, as well!
Ive seen something similar in the past within Haubna's skyland dev vlogs was always curious why sdfs werent used more. cool to see it done
Heightmap based terrains are much easier to implement, so that might be why. They're a lot less interesting though ;)
Agh! This is so good right now!
ONLY 765?! nah you deserve more
So glad voxels are finally getting some use & love! I hope you can make a lot of money off of this!
really good video! Impressive work
great work. nice explanation.
does the sdf becomes slower to evaluate the more details you add? that is, the more shapes you add an substract?
It does not really affect performance.
I currently only use the original SDF functions to construct an octree. If not edited, the octree is constructed once for a particular area, and the SDF does not have to be evaluated again, as it uses the values from the octree directly. If edited, the octree is currently fully constructed (that is, subdivided to the maximum depth only near the surface of the original SDF function) within an AABB around the the edited operation, and an operation (difference or union) is applied to all values in the tree and the new SDF function (e.g. a sphere). This does mean that the octree does not store a true SDF approximation as soon as it has been edited once, as values far away from edited regions are not updated accordingly. For isosurface extraction we only care about the surface, so that is not a problem.
I am playing around with implementing a faster system that allows me to edit huge areas (sphere of r=1000 or larger) extremely quickly, but it is hard to debug and not really important for my intended use.
@@thecodejar So you're basically saying that any new edit is done to the geometry stored in the octree directly, without using any SDF that has been used previously. I.e. once the edit has been applied, you can discard the SDF (of the sphere in this case). Am I right?
@@sasjadevries Yes that's right!
Nice job dude keep up the good work.
Thanks!
Genius. Worms 3D!
That would be a fun application of this!
Neat project! A question: is the initial terrain SDF (before edits) a heightfield? (it appears to be?) If so, have you considered using a terrain SDF that is fully 3D? (allowing for caves, overhangs, etc.)
Really cool breakdown! Hope you'll make more videos
Fascinating. Liked & subscribed.
This is seriously awesome. I tried something similar, but I never managed to tackle the difficulties connected with creating terrain.
What kind of octree are you using? Mine helped with ram usage but greatly increased the time of reading/writing data from the octree. I created one that mainly used classes for each node containing possible references to other classes for other nodes.
How did you manage draw calls? Are you using some kind of mesh batching for neighbouring chunks?
And do you reuse vertices or do you generate 4 vertices for each new triangle, even if there is already a vertex at this position in space?
In general, how is it possible to achieve that kind of performance at the beginning of the video. Generating a single chunk of 32 x 32 x 32 already takes kinda long for me in c#, so it's truly fascinating to see this kind of speed.
Frankly I am using arguably the simplest octree with hardly any optimizations, essentially like you described (reference to parent node, and reference to an array of child nodes).
- As I use the godot game engine, I don't actually have very much control over the exact draw calls, and I believe there will be one for every terrain chunk (I do enable occlusion and frustum culling, which helps). It could be interesting to manually apply batching, but that makes editing the terrain more complex too.
- I reuse vertices! It's rather simple to do with surface nets compared to marching cubes.
- I use multithreading in two stages, first I generate the octree. once all threads are done, I use a scheduler to assign each chunk that needs to be meshed to a single thread, so I can mesh the entire world rather quickly. Overall, the process takes about a second for the entire terrain, running on 12 threads on my 5900x.
I did try to create a rather optimized meshing function that operates linear time, by first creating a look up table of all the leaves in and directly around a chunk. that way neighbour lookup is in constant time during the two subfunctions of surface nets that iterate over all leaves (those stages being vertex placement & quad formation)
I hope this helps! I am honestly not fully happy with my performance yet when it comes to moving to different parts of the terrain. it works well enough but there are some issues with updating colliders that slow the engine down, and in general my solution being too slow causing a delay in edits to the terrain while its changing level of detail.
a cool channel that is not well knowned yay
but you deserver way way more subs
Thanks :D
Impressive work!! Is the initial SDF (before any edits) generated from a noise texture? For serialization, would you just store the deltas from the original SDF? So many possibilities…
Thank you!!
Yep its primarily based on Fractal Simplex Noise. For serialization I was thinking of some way to only store modified parts of the octree, I suppose similar to "storing deltas from the original SDF". It's not something I have implemented yet, but might be interesting to tackle later on :)
This is amazing! Subscribed!What I can’t figure out is how you calculate the shape of the terrain from sdfs? Do you Boolean together a bunch of spheres or somehow make a Perlin height map into an sdf?
Thank you!
I am still unsure what the best method is. Currently I have a TerrainSDF function that uses 2d fractal noise. I map this to a height, and apply this to a plane SDF. Additionally, I scale the distance proportional to the inverse magnitude of the gradient (i.e. steeper terrain is smaller distance values), which seems to work pretty well.
I experimented with the techniques explained in this amazing article: iquilezles.org/articles/fbmsdf/
But I found that performance was much, much worse.
I am honestly not really happy with the current SDF, and I want to experiment with some other techniques. For instance, I read a paper about using phasor noise to mimic erosion.
I hope this answered your question!
huge bro
excellent work
Populating the world with objects in part 2? 😉
Yes :)
Fabuous! one question: since you use SDF, how to handle the situation: numerous players * years modifying in a server? like when they Digging/Mining, or Filling the ocean, every Shovel is a SDF_sphere() right? then as more SDF accumulated, then more Evauluation time and Storage space are required right? is any solution to handle this 'issue'...? Thanks, i know SDF is cool, like the "Infinity Detail", Fast LoD, Percise CSG, etc
It is not really an issue, but at a cost. I use an SDF for the terrain to populate an octree, with higher detail closer to the camera and to the surface of this SDF (i.e. subdivide a node if close to the camera and the SDF value at its center is smaller than roughly the node's edge length.).
Leaves have a minimum size, which means the resolution of the terrain is bounded by that (in the video that is edgelength 1.5, or volume 1.5^3 =3.375, I have played around with volume = 1)
However, this constraint allows us to use boolean operations such as union and subtraction to combine values in the octree with new SDFs, the results of which are stored in the octree, instead of permanently evaluating the terrain SDF as a series of operations and SDFs.
This means that yes, a more complex terrain will increase storage space (evaluation time not as much) as more octree nodes might be required, but it has so far not been an issue.
For reference, I have not bothered to optimize memory usage with this particular implementation yet (an octree node instance is quite big, as I use multiple pointers, full 32 -bit floats, 128-bit color mask, 96 bit center, etc) As the LoD system keeps the node count to a relative minimum, costing under 1gb of memory when the scene is initially loaded.
I hope this answered your question!
How does adding something like an entity out in the distance get affected by the LOD in this example?
Say you populate the area with trees (which are not made of voxels): are they going to look like high detail trees painted on a low detail surface, or will they also get some kind of lowered resolution? I imagine that in the former situation, another service could handle entity rendering specifically, so that a forest doesn't look goofy off in the distance.
This is very interesting and is exactly what I am looking for my project. The video is very well made!
Edit: just saw your most recent video. Neat!
Yeah my most recent video answers this! I think its best solved with a secondary octree to allow for better control. For instance, you might need more/less terrain geometry without changing the tree count.
Thanks for the complement :)
Cool video. I am an absolute beginner in the topic of procedural generation, but I want to know if it is possible to create a similar generation and destructibility using surface nets as in Deep rock galactic?
I love DRG!
I think it could be possible, but it's not how DRG does it as far as I am aware.
I'm sorry for not being able to back my claims, but somewhere I've read that DRG uses 2x2x2 meter chunks (very tiny!) and directly modifies the meshes using "Constructive solid geometry", similar to how you might use boolean operators to combine meshes in blender (or other 3d software).
This has the great benefit of being able to represent complex geometry, notice how you can dig very precisely in that game.
However, for large terrains, it would mean that you need a ton of drawcalls. I imagine DRG gets away with this because of their cave designs in combination with occlusion culling.
As far as I am aware, DRG does use marching cubes to initially generate the caves, and you could use surface nets here instead.
But, If you just need the player to dig "player-sized" tunnels, surface nets can absolutely work! It seems in my implementation that a diameter at least two to three times greater than the minimum voxel edge length results in smooth enough traversable tunnels.
In conclusion, it could work, but i doubt it's what DRG uses.
@@thecodejar Thanks for the detailed answer. I've read a little bit about marching cubes and marching tetrahedra. To use them on a large scale, compute shader is used, for me this is a very difficult topic, since I am not a programmer and especially not a mathematician.
Is it possible to implement a procedurally generated landscape of sufficient size (approximately like yours) using only GDScript with sufficient optimization (if divided into chunks and using LODs)?
neato
i like your magic words funni man
Engineering is our world's magic system :)
This is cool, but it pretty much goes over the same stuff everyone else posts. The tricky part is the seams between chunks at any LOD. Would be nice to have more information about that as there's a lot less information about this online
That's fair! I think it might be nice to do a follow-up at some point, but I am working on some other projects in the meantime.
@ would you be able to explain how you went about that portion of it? Or some psuedo code would be even more helpful
No worries if not but that would be super appreciated 😁
Here is a quick overview:
First realize that I only consider transitions between LOD of magnitude 1, i.e. only transitions between neighbouring level of details. This makes the algorithm easier, but imposes the constraint that only such transitions are generated by the algorithm. To achieve this, it helps to enforce LODs in the octree to child nodes (e.g., you might have a node that itself is LOD 1, but its children are split up being LOD 1 and 2, caused by determining LOD based on distance(camera,node_center). Here we enforce LOD2 children to be LOD 1.). Furthermore, LOD radius is exponential.
To actually generate the mesh, I do the following:
- collect set C: chunks (which are themselves nodes in the octree) that need to be meshed.
- for each c in C:
-- create a look up table (LUT) that arbitraty positions to the leaf nodes within (c union a shell of size min_node_size around c)
-- each leaf is wrapped ina class that stores the maximum corner it takes up in this LUT.
note: nodes of neighbouring chunks of lower LODS will be larger here, and will take up more spaces in the LUT.
-- iterate through the nodes, and calculate vertex positions using the surface nets algorithm. this is done using the bag, or non exclusive set of neighbours found at every combination of : (stored maximum corner +1 in every dimension, i.e. 8 neighbours in 3d)
-- now we connect the vertices: iterate through every node, and this time get the _unique_ set of neighbours in the 3 case: +yx dimension, +yz dimension, +xy dimension. We should here either get 3 or 4 nodes, 4 in case all neighbours are of equal size, 3 if it directly neighbours a full face or a node 1 LOD lower (thus double edgelength).
Now its important to realize that this only works in the direction of decreasing level of detail (or increasing edge length). To ensure it works in all dimensions, we compute the octant the chunk is in relative to the camera, and change how we handle the maxmimum corner/neighbour finding accordingly.
This essentially covers everything. It is quite a lot, and I will not expand on this much further in this comment thread.
If it is still unclear, and I admit this comment was hastly put together, I will consider making a followup video on this, as I have seen more demand for a greater explanation of covering LOD seams.
Curious, what do you plan on doing with it? Making a game? Open sourcing? Research paper?
I have not decided yet. My primary goal is building a portfolio with algorithms related to game technology / real time graphics, but I might decide to open source the code later on.
nice
A while ago I did a cubemarching algorithm using godot and found it very difficult to continue the project because of how godots arraymesh res is structured, how did u handle this difficulty, did u even use array meshes??
Yes I am! I dont use the surface tool, but I directly create data buffers (index, vertex, normal, color), and assign those buffers to the right indices. It works quite well. I did notice performance issues when creating and deleting many nodes, so i created an objectpool system (Only recommended for C#, but may prove beneficial for GDScript also). For some reason godot would sometimes crash due to queuefree being called. I'm 99% sure that's an engine bug.
@@thecodejar hmmm, thanks for sharing, ill try to implement that when I eventually return to that project, may need to read more on exactly how surfaces are stored in array mesh cause the vertex info is quite a mystery to me rn, once again thanks for sharing
Do you plan on releasing this for public use or is it just for your own game?
Not sure yet!
@@thecodejar would be awesome, maybe a patreon where you release the source code would be an nice idea too!
do you rebuild the octree every time the camera moves?
Yeah I do. I am working to optimise the system further to make it as seamless as possible, but it works reasonably well currently. I update the octree if the camera has moved 64 units, and I only remesh parts of the terrain that have a different LOD thanks to the camera shift.
release when?
Not sure! I am not designing this as a godot plug-in or game at the moment. This project is currently primarily a challenge for me to improve my practical software engineering and computer graphics skills :)
How did you solve seams
Its an incredibly hard problem, I tackle it as follows:
First, I make the assumption that neighbouring chunks differ at most 1 Level of Detail (LoD). Secondly, when building the octree I ensure that within a chunk the LoD is the same (i.e. all leaves in the octree considered for meshing at the same size)
Then, before meshing i collect all leaves in and directly around a chunk. I then create a look-up-table (LUT) with all the leaves in it. This takes O(|leaves|) time, but it allows me to find neighbours in O(1) time!
Then, when meshing, I can basically use normal surface nets using the LUT, with the only exception that i need to check 4 neighbours per face instead of 1 if the current node we are considering is twice as large (hence the at most 1 LoD difference assumption!).
I hope this helps! Let me know if you have any more questions :)
@@thecodejar thanks i would like to see a video about it
I also made similar system like yours but it is little bit faster, but i have to fix seams
There are slightly more details in my blog post: jorisar.github.io/portfolio/posts/smoothvoxelterrain/
I am not planning on making a follow-up video unless I make some larger technical changes. I did just watch your awesome showcase of your terrain, looks great! If you want you could share your discord tag and we can share some insights :)
Where are the voxels in the voxel terrain?
It's a smooth voxel terrain, so instead of rendering the voxels as "cubes" I create a smooth mesh that approximates the surface described by the voxel (or volume element) data better!
You're using godot? Will you publish this tool as a plugin?
Yes I am! It's a lovely engine, and I prefer using it over unity. I might make it into a plugin, but I would probably create a C++ GDExtension version in that case.
@@thecodejarI’m really looking forward to it, and would be glad to know the approximate timing
Don't count on it too much i'm afraid... One of my next projects will likely be a GDExtension experiment, based on that I will see if it's worth converting the terrain to one :) For now, stick with technologies like Zylann's godot voxel (which is much more mature than my solution regardless).
If you already have an SDF for your terrain, why not render it directly? It's not terribly expensive to raymarch an sdf.
A meshing solution is fine too, just seems kind of unnecessary if you already have an SDF.
The rasterization pipeline is still by far the most optimal way to render large scenes, especially in combination with level of detail. But most importantly, This allows me to keep most data on the CPU which allows me to do collisions more easily. I am planning to play around with volume visualisation on the GPU at some point :)
how large are your octrees (depth) because you seem to be dynamically changing them quite easily and this is usually an issue. I'm curious as to how you got past it.
I can get away with fairly large voxels, as I'm using surface nets with interpolated vertices. I recorded the video with an octree depth of 14, and an octree scale of 1.5. This means that the smallest voxel is actually (1.5x1.5x1.5)m^3. The overall octree has an edge length of 1.5 * 2^14, resulting roughly in a 25x25km terrain when seen from above.
This resolution is way to course for mostly anything that is not terrain, so I'm working on a secondary system that populates the terrain, similar to how you would place trees on a heightmap terrain.
Love this bro I subbed hope to see more from you
Thank you! Expect more hopefully soon enough ;)
Hey @Code_Jar I'm currently working on a similar project. At this point i have managed to generate terrain using SDFs and fast surface nets. But i cant get rid of the gaps between chunks when using LODs. I would love to get your assistance on that, maybe have a look at your implementation, so i can reproduce your astonishing results. Is there any way to contact you? Greetings, Ben
bro this isn't a letter
For now I will leave my solutions closed source, as I am unsure about my end goals with the project. I will launch a discord server next video for further (technical) discussion, so stay tuned :)
It's a pretty easy problem to solve. There's a good blog post here about it ngildea.blogspot.com/2014/09/dual-contouring-chunked-terrain.html