Volumes Of Fun
http://www.volumesoffun.com/phpBB3/

Seamlessly aligning extracted meshes
http://www.volumesoffun.com/phpBB3/viewtopic.php?f=2&t=109		 Page 1 of 3
Author:  psquare [ Wed Dec 29, 2010 9:10 am ]
Post subject:  Seamlessly aligning extracted meshes
Hi, I am using PolyVox volumes as the building blocks for a terrain system and having some problems aligning meshes.

Let me explain the problem by oversimplifying:

-Let's say that I have a 32x32x32 volume. Each of the 3 cases below, I extract using extents (0,0,0) and (31, 31, 31)

1. Volume completely filled from (0,0,0) to (31, 31, 31), both inclusive. Extract mesh.

The mesh is completely devoid of geometry.

2.Fill the volume b/w (0,0,1) and (31,31,30), both inclusive.
Extract mesh.

The mesh is extracted, but is missing the geometry at the edges in the x & y dimensions. See image:

Image

3.Fill the volume b/w (1,1,1) and (30,30,30), both inclusive.
Extract mesh.

The mesh is extracted, but is 'rounded off' at the corners because of the interpolation in the extractor and also not at the exact boundaries. See image:

Image

I think this is a behavior of the algorithm itself, but this is a problem because I need to align my terrain volumes (pages) next to each other. Even if the edge gap is plugged(by scaling the mesh for example), I still have the problem at the 8 corners.

How can I workaround this? Alternatively, what can I change in the polyvox code such that generation of geometry at the region edges also works? I have been looking at the code, but I ended up confusing myself :-(
Author:  David Williams [ Wed Dec 29, 2010 11:28 am ]
Post subject:  Re: Seamlessly aligning extracted meshes
psquare wrote:
I think this is a behavior of the algorithm itself, but this is a problem because I need to align my terrain volumes (pages) next to each other.


Yes, this is the expected behaviour. The surface extractor (I assume you are using the Marching Cubes SurfaceExtractor?) only processes a single volume at a time, and this makes it very difficult to correctly join two different volumes. For example, consider you have one completely empty volume and one completely solid volume. Neither of these should have a surface in them, but if they were placed next to each other then you would expect to see a surface between these volumes. This can only be correctly achieved if the surface extractor were to consider all surrounding volumes as it is generating the surface.

Really, the problem is that this is not how I was expecting PolyVox to be used (though you are certainly not the first person to use it like this). The correct idea (and what Thermite3D does) is to only have a single volume, but to extract many meshes from it corresponding to different regions. So rather than having one volume for the data (0,0,0) to (31,31,31), and another volume for the data (0,0,32) to (31,31,63), etc, you would have a single volume going from (0,0,0) to (31,31,63) but you would extract two separate meshes from it.

However, the catch is that you mentioned the word 'paging'... Using the approach I describe above (and in Thermite3D) all data is in memory at all times. There is some compression but not much (it needs improving). So this places a limit on your maximum terrain size, which so far I have just lived with as I haven't needed particular large terrains.

psquare wrote:
How can I workaround this?

If you want to continue using multiple volumes then two approaches spring to mind. Firstly you can duplicate data along the faces of your volumes (essentially making your volumes overlap). The disadvantage to this is that when you update a voxel you might have to update it in more than one place.

Secondly, you could look at the Volume::setBorderValue() method. If you set the border to empty space (which is probably the default anyway) and then try to extract a mesh for a region which is slightly larger then you volume, then it should generate a surface between your solid voxels and the space outside the volume. This will give you a lot more triangles than you would like, but these will be hidden when you place your volumes next to each other. But I haven't really tested the border stuff very much...
Author:  beyzend [ Wed Dec 29, 2010 4:57 pm ]
Post subject:  Re: Seamlessly aligning extracted meshes
I've used the border value zero method. I changed that to a paging scheme where I page m x m x n chunks into multiple (possibly) larger n x n x n volumes. The triangle is reduced sure, but my program at this point is fill-rate bound. Also like David mentioned, I may need to update up to 4 (or is it two, I don't recall) neighboring chunks for boundary values.
Author:  psquare [ Thu Dec 30, 2010 8:18 am ]
Post subject:  Re: Seamlessly aligning extracted meshes
Hi David.

Quote:
I assume you are using the Marching Cubes SurfaceExtractor?

Yes. This is correct.

Quote:
However, the catch is that you mentioned the word 'paging'...

Quote:
as I haven't needed particular large terrains.

Yes, this is the problem. I am working on a project that needs very large terrains.

Regardless, I found out a workaround for my problem. As you see from my above post, currently I line up my volumes using an extraction/volume size like the 2nd image. This lines up the terrain perfectly in z dimension. But leaves ugly voids when 'digging' laterally across pages. However, as I found out, polyvox indeed will generate the lateral faces if I dig laterally, see image:

Image

Hence, all I need to do is plug the gaps across my pages by padding up empty space into the adjoining volumes, if a 'dig' ends up on the volume boundaries, the idea being to create seamless caves, overhangs, etc. This is working quite well right now.

To David and beyzend both:
I did try the border method, but I can't get it to work right. Can either of you please post a minimal code snippet? (volume dimensions, extraction region and what border values to set?)
Author:  David Williams [ Thu Dec 30, 2010 11:05 am ]
Post subject:  Re: Seamlessly aligning extracted meshes
beyzend wrote:
I've used the border value zero method.

psquare wrote:
To David and beyzend both:
I did try the border method, but I can't get it to work right. Can either of you please post a minimal code snippet? (volume dimensions, extraction region and what border values to set?)

Ok, I tried to write an example but it turns out there is a bug here. The volume class works correctly, but I haven't modified the surface extractors to take advantage of the borders. The idea is that you should be able to extract a region which is bigger then the volume, so that you could have a volume going from 0 to 31 in each axis but extract a region going from -1 to 32. If your volume is copletly full of data but the border is zero, then it should generate a mesh around the volume.

But it's broken... it looks like I simply haven't updated the surface extractors to use this border. Firstly they clamp the input region to the size of the volume, and secondly they do not handle negative coordinates. Neither of these are hard to fix, but allow a couple of days for me to get to it.
Author:  beyzend [ Thu Dec 30, 2010 6:18 pm ]
Post subject:  Re: Seamlessly aligning extracted meshes
oh right, I think the cubic surface extractor works. But I also messed around with it, and it's been awhile I don't recall the details.

It's works for me (I'm doing the cubic thing though), as far as I can tell I don't see anything wrong at the moment.
Author:  David Williams [ Thu Dec 30, 2010 10:07 pm ]
Post subject:  Re: Seamlessly aligning extracted meshes
Ok, I believe I have fixed the bug. Try getting latest from SVN.
beyzend wrote:
It's works for me (I'm doing the cubic thing though), as far as I can tell I don't see anything wrong at the moment.

Ah, it's possible the cubic version was ok (though I have also updated it to match the Marching Cubes version). The difference between the two is that the cubic version just looks at a single voxel at a time, where as the Marching Cubes version has to look at groups of 8 neighbouring voxels.

@psquare
When using the Marching Cubes extractor you should now be able to go outside the volume. The following code demonstrates and should result in a large cube being extracted which encompasses the volume.

Code:
//Create an empty volume and then place a sphere in it
Volume<MaterialDensityPair44> volData(32, 32, 32);
for (int z = 0; z < volData.getWidth(); z++)
{
   for (int y = 0; y < volData.getHeight(); y++)
   {
      for (int x = 0; x < volData.getDepth(); x++)
      {
         MaterialDensityPair44 voxel;
         voxel.setMaterial(1);
         voxel.setDensity(MaterialDensityPair44::getMaxDensity());
         volData.setVoxelAt(x,y,z,voxel);
      }
   }
}

//Extract the surface
Region regionToExtract(Vector3DInt16(-1, -1, -1), Vector3DInt16(32, 32, 32));
SurfaceMesh<PositionMaterialNormal> mesh;
CubicSurfaceExtractorWithNormals<MaterialDensityPair44> surfaceExtractor(&volData, regionToExtract, &mesh);
surfaceExtractor.execute();
Author:  psquare [ Fri Dec 31, 2010 5:03 am ]
Post subject:  Re: Seamlessly aligning extracted meshes
I tried it and its working like you mention/post.This really helps, thanks!
Author:  ape [ Mon Jan 17, 2011 7:40 pm ]
Post subject:  Re: Seamlessly aligning extracted meshes
I'm trying to get this working currently but it doesn't seem to work right.
I'm calling setBorderValue(0) on my 32x32x32 volumes and extracting a region from (-1, -1, -1) to (32, 32, 32), but it still gives me extra geometry at certain borders:
http://dl.dropbox.com/u/6281166/seams_good.jpg
http://dl.dropbox.com/u/6281166/seams_bad.jpg
http://dl.dropbox.com/u/6281166/seams_bad2.jpg
http://dl.dropbox.com/u/6281166/seams_bad3.jpg

Any idea what could be wrong?
Author:  David Williams [ Mon Jan 17, 2011 8:20 pm ]
Post subject:  Re: Seamlessly aligning extracted meshes
Do those screenshots show a single 32x32x32 volume? I'm guesing not, instead it's 8 32x32x32 volumes?

For testing, start by creating a single 32x32x32 volume, with a sphere of diameter 40 centered in it (so that part of the sphere pokes out of each face of the volume). Set the border to zero and generate a mesh from (-1,-1,-1) to (32,32,32). Do all volume's faces get closed of properly? If not, can you see which ones are the problem?

Even if you get it working, I think you will still end up with some seams between volumes. I believe the only way to completely avoid the seams is to use a single (much larger) volume, which is what Thermite does.
Page 1 of 3 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/