Jump to content
  • Advertisement
MasterReDWinD

DX11 3D smooth voxel terrain LOD on GPU

Recommended Posts

5 hours ago, MasterReDWinD said:

I also found this algorithm that I really like the sound of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.7091&rep=rep1&type=pdf

While reading this, i noticed it's a similar approach to the method from @spacerat from my first post.

Which made me aware of this: IIRC, Spacerat used indexed meshes, and eventually this also leads to a simpler edge collapse function. (You should look up his code to compare)

The thing is, researchers working on geometry processing will just use Half-Edge for everything because it can do everything and they have thier frameworks. (I think Leif Kobbelt also worked on https://www.openmesh.org/ which is a Half-Edge library)

I don't think Half-Edge is necessarily the best chioce for simplification in a game. (Although physics engines use it too for collision detection... really not sure)

Share this post


Link to post
Share on other sites
Advertisement
7 hours ago, Gnollrunner said:

However it's a bit more involved because my entire voxel area is an octree (or 20 rather since I build around an icosahedron since I'm doing planets) so what I'm really doing is going down the octree and applying certain rules for splitting, merging, growing and shrinking chunks.  The chunks themselves are just pointers to points in the octree.

I had some code for simplification but it's disabled right now because I want to keep the collision meshes which are only generated at max LOD the same as the view meshes and there were some issues at chunk borders.

So your approach is to have one global octree for your whole world and then chunks are octrees inside that?

Are the LOD issues at the chunk borders similar to the issues Joe is describing below?

4 hours ago, JoeJ said:

Do you already have some physics? Here a LOD approach might not work because abrupt changes on the mesh cause collision issues, and continuous changes would still add energy to the physics system. Having chunks of constant detail and downloading those nearby dynamic objects sounds more robust and practical. (I never heared about LOD for physics, although it would be an interesting topic.)

If so, all you would need the whole scene for would be path finding. And this alone would not justify the efford we discuss here IMO.

Pathfinding on GPU could be an option too. (Diffusion approach could work better here than the usual graph algorithms, depending on what you need.)

 

 

So far I only have Unity physics, which depend on me creating the Unity collision mesh.  It does sound like I would run into the issues you're talking about on chunk boundaries, as I plan to have terrain which has lots of verticality.  I'm not quite following you on this sentence 'Having chunks of constant detail and downloading those nearby dynamic objects sounds more robust and practical.'  Do you mind expanding on it a bit?

If I could get the pathfinding running on the GPU and cut out sending back the mesh for physics that would give me a massive performance boost (in theory).  The downside would be the complexity of having to deal with all the physics responses.  I've looked into this a bit and I gather it would begin with me implementing my own GPU ray casting system.  I'll definitely look into the Diffusion approach you mentioned.

3 hours ago, JoeJ said:

While reading this, i noticed it's a similar approach to the method from @spacerat from my first post.

Which made me aware of this: IIRC, Spacerat used indexed meshes, and eventually this also leads to a simpler edge collapse function. (You should look up his code to compare)

The thing is, researchers working on geometry processing will just use Half-Edge for everything because it can do everything and they have thier frameworks. (I think Leif Kobbelt also worked on https://www.openmesh.org/ which is a Half-Edge library)

I don't think Half-Edge is necessarily the best chioce for simplification in a game. (Although physics engines use it too for collision detection... really not sure)

I found this post from @spacerat .  I'll look at it along with the link you posted earlier.  The multiple choice method is essentially quadric mesh simplification but with only a small number of edge checks per round, rather than evaluating them all.  Perhaps you're right though, if I can avoid using the half-edge format it would really simplify the simplification ;).

 

Share this post


Link to post
Share on other sites
2 hours ago, MasterReDWinD said:

So far I only have Unity physics, which depend on me creating the Unity collision mesh.  It does sound like I would run into the issues you're talking about on chunk boundaries, as I plan to have terrain which has lots of verticality.  I'm not quite following you on this sentence 'Having chunks of constant detail and downloading those nearby dynamic objects sounds more robust and practical.'  Do you mind expanding on it a bit?

Probably a missunderstanding on my side - because you metioned LOD i assumed you want more details near the player and less at the distance. So if the player would move around, the terrain would change and a resting stack of boxes could fall over for example. I did not mean the transition issues like gaps and discontinuities that often arise in LOD terrain approaches.

2 hours ago, MasterReDWinD said:

The downside would be the complexity of having to deal with all the physics responses.

A compromise might be to only detect contacts on GPU and send them to PhysX used by Unity, but that's still difficult and likely messes with contact caching the engine uses internally. So i would stick at your idea to download geometry. (Be sure to observe performance cost of submitting new gemetry to physics - usually this involves building an acceleration structure if it's not just a height map, so another reason to use low poly meshes.)

2 hours ago, MasterReDWinD said:

I'll definitely look into the Diffusion approach you mentioned.

I rough idea of mine - not sure if this ever has been used for games. I talked about it recently in a PM, copy paste:

Quote

I'm not very informed / interested in tactics / pathfinding for games in general, but i often think about an alternative to usual navmesh with Dijkstra / A* approaches.

In geometry processing it's quite common to use local maxima search instead. E.g. in this famous paper: https://www.cs.cmu.edu/~kmcrane/Projects/HeatMethod/ This solves two linear systems, the second one to get exact distance, which we do not need for shortest paths.

The idea is to have a usual discrete graph representation (mesh, grid, volume, etc), and the ability to diffuse energy between the vertices of the graph. Then you set energy to the targets (can be many at no extra cost), diffuse until the energy distributes over the whole graph, and after that the closest target can be found from anywhere in linear time using simple local maxima search.

I use this to build inital edge paths for my quadrangualtion stufff, see the image. Main limitation is only the closest target can be found, not an arbitary target. But with many targets and many enemies searching for them, the algorithm could be the fastest option.

Assuming we have moving targets, the diffusion would need to happen in realtime. This rules out the faster option which is backwards euler integration over an arbitary timestep in one go (first eq. system from above paper). For games we would prefer the usual forward integration with small timesteps. (The largest possible stable timestep depends on the shortest edge in the graph, so we want to avoid a single tiny edge! Multi-level, LOD approach to speed things up would be possible)

Doing one Intergation step per frame would be cheaper than usual pathfinding algorithms. Constant time and memory, parallel friendly. As a result the scalar field representing the distance to targets would behave a bit like fluid, changing slightly and improving paths over over time. It would just work without any side effects, because enemies need time to reach their targets as well. Things would maybe even behave more natural than the instant best solution Dijkstra & co. provides.

 

image.png.525ba69732e9f7cd8844106a9331ec70.png

So the idea is, if you have a maze, put water to the target until it flows out at the source, and then just follow the path where height of water increases the most.

 

 

 

Share this post


Link to post
Share on other sites
Posted (edited)
6 hours ago, MasterReDWinD said:

So your approach is to have one global octree for your whole world and then chunks are octrees inside that?

Almost.  The root actually has 20 children, but this is simply because I'm using an extruded icosahedron to generate my top 20 prism voxels. After that it's a normal octree.  If you're not doing planets there is no advantage in this.  It's realy done to meet my requirements.  a) I'm building voxels on a sphere. b) voxels have to be oriented the same way in relation to the surface of the sphere and c) I want voxel size to be as as consistent as possible over the sphere. These last two are so that similar terrain generated at any point on the planet will give similar mesh results. Also I'm going to try to do voxel morphing to generate reasonably realistic looking trees (i.e. not blocky) so the starting orientation is important.

 

Quote

Are the LOD issues at the chunk borders similar to the issues Joe is describing below?

Well ..... with certain algorithms like marching cubes, you can't easily change voxel size (i.e. adjacent voxels can't easily have a different size).  To take care of this you have to use something like the transvoxel algorithm. I'm using voxel tessellation. However you mentioned you use surface nets so I don't think that's a problem with that algorithm.  The down side with that is you can end up with non-manifold geometry, which can't happen with marching cubes (or prisms in my case)

For physics you can normally just use your smallest voxel size for calculation of meshes, so it's not a problem. However depending on what you are dong you may have other issues.  For instance if you are using the same set of voxels for collision as you are for graphics, you can end up with some race conditions especially if a player is moving fast.  In my case I'm generating everything from functions at run time and I use a completely separate set of voxels for physics to avoid that problem altogether.  With the physics there is no LOD supported, and geometry is regenerated just around the player. I actually don't even build meshes for physics. Since the geometry is already generated in an octree I just use it as it is. That's one other advantage of algorithms that keep geometry confined to a single voxel.

Edited by Gnollrunner

Share this post


Link to post
Share on other sites
Posted (edited)
23 hours ago, JoeJ said:

Probably a missunderstanding on my side - because you metioned LOD i assumed you want more details near the player and less at the distance. So if the player would move around, the terrain would change and a resting stack of boxes could fall over for example.

I rough idea of mine - not sure if this ever has been used for games. I talked about it recently in a PM, copy paste:

So the idea is, if you have a maze, put water to the target until it flows out at the source, and then just follow the path where height of water increases the most.

You had it right, that's the situation I'm after LOD wise.  I hadn't thought far ahead enough to realise that it would cause problems like that with the physics.  It sounds like fixing that would require keeping the physics mesh at a constant downsampling rate across all chunks?

I might come back to you on that pathfinding algorithm when I get a bit further along.

19 hours ago, Gnollrunner said:

Well ..... with certain algorithms like marching cubes, you can't easily change voxel size (i.e. adjacent voxels can't easily have a different size).  To take care of this you have to use something like the transvoxel algorithm. I'm using voxel tessellation. However you mentioned you use surface nets so I don't think that's a problem with that algorithm.  The down side with that is you can end up with non-manifold geometry, which can't happen with marching cubes (or prisms in my case)

For physics you can normally just use your smallest voxel size for calculation of meshes, so it's not a problem. However depending on what you are dong you may have other issues.  For instance if you are using the same set of voxels for collision as you are for graphics, you can end up with some race conditions especially if a player is moving fast.  In my case I'm generating everything from functions at run time and I use a completely separate set of voxels for physics to avoid that problem altogether.  With the physics there is no LOD supported, and geometry is regenerated just around the player. I actually don't even build meshes for physics. Since the geometry is already generated in an octree I just use it as it is. That's one other advantage of algorithms that keep geometry confined to a single voxel.

Ah, yes, I've looked into the Transvoxel algorithm and some 'stitching'/'skirt' techniques.

So you generate and store the geometry around the player in a separate octree and use that for player physics?

Edited by MasterReDWinD

Share this post


Link to post
Share on other sites
10 minutes ago, MasterReDWinD said:

Ah, yes, I've looked into the Transvoxel algorithm and some 'stitching'/'skirt' techniques.

So you generate and store the geometry around the player in a separate octree and use that for player physics?

The thing is I'm targeting very large worlds with sub half meter triangle sizes.  Even something like a matrix of values that are fed into a voxel algorithm would take up far too much disk space on a players system. I therefore generate everything from terrain functions at run-time as a player walks around.  That all takes some CPU cycles.  The FPS can't actually bog because it's in a separate thread that's using the "current" build of the world while the next build is being calculated in the background.   Also ideally I should be able to do sub second world builds. However in some odd cases where the world build lags, I don't want the physics to be affected.  So as I said I have a second voxel tree where leaf voxels only exist right around the player for physics.  They can also be built ahead of ranged projectiles and stuff like that if necessary.  The general idea is to only build terrain right ahead of any possible collisions so it's fast.  For physics I don't care about voxel level transitions because it's all at one level so that simplifies things.  I also don't actually need a mesh because I can access triangles in the tree directly.  

.....So yes physics is done in an entirely separate octree in the same thread that calculates collision. However since it uses the same functions it matches the graphics terrain at it's highest resolution.  This whole system is really particular to my project. If you aren't using run-time procedural generation there are probably better ways (I'm sure there are better ways anyway :P) .  For one you don't have all the terrain available for path-finding at any given time, which is a problem.  However I thought of a cheating way of doing path-finding but I'll have to try it out when I get that far.

I'm basically forced to do all this because I want to  support several thousand large planets. That's why I was saying I'm not sure how much help I can be since my project is kind of odd.

Share this post


Link to post
Share on other sites
2 hours ago, MasterReDWinD said:

It sounds like fixing that would require keeping the physics mesh at a constant downsampling rate across all chunks?

Yes, but depends on what physics you need. If it's just enemies / vehicles but no box stacks, LOD could work.

Also you could replace physics simulation with procedural animation at the distance.

Share this post


Link to post
Share on other sites
5 hours ago, Gnollrunner said:

The thing is I'm targeting very large worlds with sub half meter triangle sizes.  Even something like a matrix of values that are fed into a voxel algorithm would take up far too much disk space on a players system. I therefore generate everything from terrain functions at run-time as a player walks around.  That all takes some CPU cycles.  The FPS can't actually bog because it's in a separate thread that's using the "current" build of the world while the next build is being calculated in the background.   Also ideally I should be able to do sub second world builds. However in some odd cases where the world build lags, I don't want the physics to be affected.  So as I said I have a second voxel tree where leaf voxels only exist right around the player for physics.  They can also be built ahead of ranged projectiles and stuff like that if necessary.  The general idea is to only build terrain right ahead of any possible collisions so it's fast.  For physics I don't care about voxel level transitions because it's all at one level so that simplifies things.  I also don't actually need a mesh because I can access triangles in the tree directly.  

.....So yes physics is done in an entirely separate octree in the same thread that calculates collision. However since it uses the same functions it matches the graphics terrain at it's highest resolution.  This whole system is really particular to my project. If you aren't using run-time procedural generation there are probably better ways (I'm sure there are better ways anyway :P) .  For one you don't have all the terrain available for path-finding at any given time, which is a problem.  However I thought of a cheating way of doing path-finding but I'll have to try it out when I get that far.

I'm basically forced to do all this because I want to  support several thousand large planets. That's why I was saying I'm not sure how much help I can be since my project is kind of odd.

Thanks for the extra detail, it's helping me to foresee future issues.

I'd like to pursue the clipmap idea if it can be made to work for 3D terrain rather than just heightmaps.  I believe Miguel on the Procworld blog managed to achieve this somehow.  Generating 'spheres' of chunks of terrain around the player that halve in sampling resolution with each sphere but double in size to take advantage of the perspective projection.

I think I'll need to move to an octree structure to progress.  I did explore this route before (on the CPU) but I found that I needed to generate the octree from the bottom up, with leaf nodes representing a single voxel.  Collapsing the leaf nodes into single parent nodes one level up proved tricky, along with the (Dual Contouring at the time) triangulation.  Ideally I'd like to do all the LOD on the GPU where my noise and meshes are generated.

3 hours ago, JoeJ said:

Yes, but depends on what physics you need. If it's just enemies / vehicles but no box stacks, LOD could work.

Also you could replace physics simulation with procedural animation at the distance.

That's a great point, thanks.  I had planned to look into procedural animation later on.

Share this post


Link to post
Share on other sites
On 10/8/2019 at 8:36 PM, Gnollrunner said:

The down side with that is you can end up with non-manifold geometry, which can't happen with marching cubes

Do you guys know any resources on how such non-manifold cases look like, or how they can be fixed?

I have just tried it (https://github.com/mikolalysenko/mikolalysenko.github.com/blob/master/Isosurface/js/surfacenets.js), and i like the resulting quads will cause less sharp angled triangles than marching cubes. I need this so solvers behave well. But manifold is more important, although things like self intersections would be ok.

Share this post


Link to post
Share on other sites
37 minutes ago, JoeJ said:

Do you guys know any resources on how such non-manifold cases look like, or how they can be fixed?

I have just tried it (https://github.com/mikolalysenko/mikolalysenko.github.com/blob/master/Isosurface/js/surfacenets.js), and i like the resulting quads will cause less sharp angled triangles than marching cubes. I need this so solvers behave well. But manifold is more important, although things like self intersections would be ok.

I don't think I've seen anything on Surface Nets but it came up a lot regarding Dual Contouring.  In examples I've seen the non-manifold sections usually look like hourglass shapes where two parts of a surface converge at the same vertex.

This link (https://www.boristhebrave.com/2018/04/15/dual-contouring-tutorial/) describes it a little under the 'Manifolds' section.  There is also a paper for Manifold DC (https://web.archive.org/web/20161020191119/http://faculty.cs.tamu.edu/schaefer/research/dualsimp_tvcg.pdf).  As Surface Nets and DC only really differ in how they position the vertex inside the cell it might be possible to use the same solution.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!