Surface Extractor Mesh Simplification

kklouzal · **Posted:** Thu Aug 14, 2014 5:45 am

This may or may not fall under the category of "should be handled by an external, dedicated, mesh library" however I see major relevance towards implementation inside PolyVox itself.

Do the surface extractors simplify the extracted mesh vertices?

To elaborate, say you extract a cube made of 64x64x64 voxels. Each side of the cube would have 64 faces equating to 4 vertices per face. leaving you with 256 vertices per face and 1536 vertices for the entire cube. Due to the fact that each face is perfectly flat all but 4 vertices on each face could be combined to leave you with only 4 vertices per face and a total of 24 vertices for the entire cube yet still retaining the exact same visual shape as was with the 1536 vertices.

Taking this at face value you could easily say such a task would be better suited to a dedicated mesh library such as OpenMesh however since Cubiquity is built off PolyVox both sides of the fence would see a huge performance increase when rendering said mesh which leaves me wondering why the feature is not taken care of by PolyVox. Not to mention if the processing of combining vertices were done on the GPU with a shader.

That's just my 2 cents and look forward to hearing back

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

The new 'extractCubicMesh()' function and old 'CubicSurfaceExtractor' class both provide this functionality if you set the 'bMergeQuads' parameter, but the old 'CubicSurfaceExtractorWithNormals' class does not. The marching cubes surface extraction also does not provide this functionality.

The reason that we provide simplification for cubic meshes but not smooth ones is that the cubic meshes can be considered a special case, which are much easier and faster to simplify. For example, a cubic mesh can be considered as a number of separate layers which can never merge with each other, and so the 3D simplification problem is reduced to a series of 2D simplifications. A generic (external) library would not have knowledge of this property.

Try rendering a wireframe if you want to make sure it is working properly?

kklouzal · **Posted:** Fri Aug 15, 2014 7:23 pm

Oh awesome! I wasn't saying it didn't work or anything, I was just proposing an idea you may or may not have already thought about, but it seems you have!

Are there plans to have this feature with the MarchingCubesExtractor also? Because that would be simply amazing (no pun intended)

milliams · **Posted:** Fri Aug 15, 2014 7:38 pm

The issue with using this with the Marching Cubes extractor is that having large flat planes is much less common and so the work to integrate it would only give a small boost.

petersvp · **Joined:** Tue Apr 08, 2014 5:10 pm **Posts:** 124

You can use the old MeshDecimator from Polyvox 0.2.1 and modify it a little bit

0.95 factor for rendering and 0.85 to 0.9 for physics then works good.

kklouzal · **Posted:** Sun Aug 17, 2014 7:34 am

milliams wrote:

The issue with using this with the Marching Cubes extractor is that having large flat planes is much less common and so the work to integrate it would only give a small boost.

Ultimately you two have the final decision here however I would strongly urge you to reconsider, or at least think about the possibility of incorporating this into the MarchingCubesExtractor at some point in time.

I definitely agree large flat planes are much less common with smooth extraction although I would have to say that it would be very common for there to be many small flat areas which would benefit from simplification. I also completely agree that the boost for smooth vs cubic would not be as drastic however I would wait to write it off as negligible. I also see where your coming from when you mention the work required, but since the cubic extractor is already functional in this reguard, would it not be possible to refactor it into the smooth extractor?

I only push so hard here because any performance gains are performance gains nonetheless, not to mention its a giant step towards a LOD implementation.

I want to pause here and tell you guys how amazing I think the work that's being done here is and that I can't put into words my gratitude towards your time and effort into this project. I only wish to see its ultimate perfection achieved! :twisted:

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

I do think the simplification of smooth meshes is useful. As Matt says, there are less opportunities for 'perfect' simplification, but if you accept a minor quality loss then you can remove quite a few triangles. It would probably be most useful for collision meshes, but rendering would benefit too.

The main issue is really that I don't know much about mesh processing, whereas I do know a lot about voxel graphics. I was able to write the old MeshDecimator of course, but I never felt is was optimal or very robust. The algorithm itself is not so complicated, but the underlying data structure should support efficient adding/removing of vertices and a way of finding the neighbours of a given vertex. In PolyVox we just output index/vertex buffers which are ideal for rendering but don't have the above properties.

I then found that downsampling the volume data worked quite well, and that you could then generate a low resolution mesh from that. Actually there is an example of this in PolyVox though I admit that the example is rather unclear. The approach seemed promising and so I lost some interest in mesh decimation.

Really the whole thing needs more research. In Cubiquity we expect to downsample the volume to create lower LODs (we already protoyped this), but actually it should be possible to do MeshDecimation as well. But for this I would at least like to try external mesh libraries to see how they work out, because mesh simplification feels like it should be a separate task and doesn't need to be part of PolyVox.

Note that all the above only applies to smooth (marching cubes) meshes, as we already have a solution for cubic ones.

petersvp · **Joined:** Tue Apr 08, 2014 5:10 pm **Posts:** 124

Downsampling the volume data itself is vvery heavy operation. In Crafterria, I generate LODs based on the mesh decimator. Downsampling may require TransVoxel for seamliss meshes, while the decimator approach does not introduce any seams if I modify the function to never merge vertices of region boundaries.

This is why I chose the Decimator as a final decision for my project and preferred over downsampling.

kklouzal · **Posted:** Mon Aug 18, 2014 10:48 pm

I am very glad you think it would be useful. petersvp makes a good point, not merging vertices lying on region boundaries is a quick and easy way to avoid creating seams. Personally I think this is the best approach but should be something that could be turned on or off, if a user wants to shave off those last few vertices then they could turn it off and use some external means to get rid of the seams.

As far as the simplification process goes, could you not iterate through each vertex and check it's neighbor vertices, if any two combination of axis position are within a threshold then merge the vertices? This I'm sure is a very crude way of doing it but that's all I can come up with at the moment. Adding an entire mesh manipulation library for a single feature seems like a big waste.

David Williams · **Joined:** Sun May 04, 2008 6:35 pm **Posts:** 1827

kklouzal wrote:

...could you not iterate through each vertex and check it's neighbor vertices, if any two combination of axis position are within a threshold then merge the vertices?

This is what the now deprecated MeshDecimator does (as I recall?). The problem is that when storing data as a vertex and index buffer it is not easy to find the neightbours of a vertex. You need to iterate over the index buffer to find which triangles are using a given vertex, and then get the other vertices which are part of those triangles. Removing elements from the middle of such a buffer is also painful.

A better approach is to store the mesh as in a more adcvanced format such as a 'winged-edge' mesh. In this case the vertices are keeping pointers to their neighbours, so they are easy to find, but of course you need to keep these neighbourhood pointers up to date as you remove vertices. However, this format is not good for rendering so you need to convert back to vertex/index buffes for the GPU.

You can read more here: https://en.wikipedia.org/wiki/Polygon_m ... dge_meshes

It's basically this 'data structure' aspect which was complex, rather than the decimation algorithm. Not impossible, but where there are mesh processing libraries available it seemed like it was worth checking these out further first.

kklouzal wrote:

Adding an entire mesh manipulation library for a single feature seems like a big waste.

We wouldn't add such a library to PolyVox, just suggest users choose whichever one is appropriate for their needs.

Surface Extractor Mesh Simplification

Who is online