Octree-based voxel LOD - best way to calculate voxel volume at low LODs?

Hello, everyone! First post here.

I know a lot of Unity folks are working with this sort of thing lately so I'm hoping you guys can help.

I'm creating an octree-based voxel LOD system and so far it's going well, but I'm hitting a snag with voxels underestimating their volume at lower levels of detail.

In the system voxels are generated using a height map plus some procedural noise as sweetener. For now I calculate voxel intersection / volume by subdividing the voxel and checking whether each subdivision point is above or below the height map elevation.

This works pretty well at high levels of detail but at lower levels of detail (where a single voxel covers a lot of terrain) voxels underestimate how much they intersect with the height map. The result is that mesh edges at a single LOD line up, but mesh edges across separate LODs are at different elevations.

If I calculate voxel volume using a 'pure' method like sampling Perlin noise at the center of each voxel and using the result as the volume, the different LODs line up quite a bit better, though it's still not perfect. Same goes If I dramatically increase the number of subsamples based on voxel size - but that method is slow as hell.

Any suggestions?

For clarity, there will obviously still be seams between meshes at different LODs no matter how well they line up - I'm handling that problem separately. I just want to get them as close as possible before I fill the gaps.

Thanks!

 

Best look at the plenthora of articles on Geomipmap terrains and how they handle T-junction (thats the problem you see there, 'mipmap level jumps / gaps').
There are a handfull of books that cover approaches, two of them are mentioned at http://www.opengl.org/discussion_boards/showthread.php/149424-How-to-fight-with-t-junctions

The standard approaches on terrains normally are either:

1. 'smooth out the gap' (can be computationally costly and complex to achieve, especially when the lod change is more than 1 lod level)
2. create gap fillers that bridge the difference (can be problematic if the lod levels are badly done).


A first step required for your problem is definitely that you extend the lod level calculation to go '1 unit beyond the border' to normalize heights and other border related data with the neighboring chunk. Right now you seem to stop at the border which not only causes that gap but would in practice even without the gap not work correctly as the normals wouldn't match either yielding pretty ugly light seams (thats the problem you see when putting multiple unity terrains next to each other that were created from adjacent heightmaps for example)

 

Thank you, checking out the link now.

>A first step required for your problem is definitely that you extend the lod level calculation to go '1 unit beyond the border' to normalize heights and other border related data with the neighboring chunk.

Makes sense. Do you mean border related data for the actual voxels or just the meshes? Currently each voxel chunk isn't aware of its upper and lower LODs, only its neighbors in the same level. And if I can keep it that way I'd like to for simplicity's sake. Meshes can swap data pretty easily though.

If I can ever power through the math I plan to fill the mesh gaps with this method: http://www.terathon.com/voxels/ But as you point out that'll look crummy if the elevation differences are too extreme.

>especially when the lod change is more than 1 lod level

I can commit to LODs never being more than 1 level apart, if that buys me anything.

Gap filling and smoothing aside, I still want to find a way to calculate voxel volume more accurately. Using perlin noise showed me I can close the gap by about 80% if I get the volume correct. Any thoughts on that problem as well?

 

I think if you look into polyvox or http://www.terathon.com/lengyel/ He has produced a paper with lookup tables necessary to compute the edge vertices.

 

Thanks, I've got that paper bookmarked for the future. But until I find a way to calculate voxel volume more accurately, the seams will look ugly even if I fill them using that method. So my short-term goal is figuring out how to accurately calculate voxel volume, specifically when using a height map to generate voxels. Any thoughts on that problem?

 

OK here are some more pics, the first two weren't totally clear.

The first is an image of two side-by-side tiles of different LODs from the top down:


The second is the same two tiles from the side. You can see that if the lower LOD wasn't suffering from shrinkage, they would actually line up pretty well. But filling in gaps as-is would produce a pretty harsh cliff.


In the third picture, I've set the isolevel to 0.001 - where basically ANY intersection fills the voxel. This is just a test case to show what happens when the volumes of the two tiles are more 'accurate.' The meshes I get when using this isolevel are close enough to use polyvox to fill in the remaining seams.


Of course an isolevel of 0.001 isn't very good, I'd like to keep it around 0.5. But to do that the voxels need more accurate volumes.

So my goal is to first find a good way of calculating voxel volumes based on height maps, and then fill in the gaps once I've got that.

Hope I'm making sense, it's been a long morning.

 

okay, I'm not really mathy, but this might work, in calculating normals for my marching cubes editor stuff, I used the derivative of the iso density field to create the normals.

section 1.4 of this article. http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html

could you do something similar when sampling the heights.

 

>I'm not really mathy

You and me both... thanks for the link, I'm checking it out now.