Hey all,

It's been a popular request, so I just wanted to let you know that I've been working on adding mesh decimation (simplification) to PolyVox. It seems to be working pretty well, though there is some tidying up to do. Here are the initial results:

Before decimation:



After decimation:



I need to check how it behaves when the mesh is only for a part of the volume, and to make sure that meshes from neighbouring chunks/regions will still line up properly after decimation. And I also need to make sure it work properly with multiple materials present. Because of Christmas it might be a couple of weeks before it is finished, but it is definitely on the way.

This looks REALLY good! Keep up the good work!
I assume this will speed up the world-rendering by a huge factor. And this means a lot more view distance

I hope so... but it also depends where the bottleneck is in your application. If you are limited by the vertex shader then this can make a big difference, otherwise it might not. At any rate there are no downsides (except the time taken for the decimation) and it's obviously going to reduce memory consumption.I don't have any peformance figures yet but I'll try and get some when it is more finished.

Great job David!

I got my netbook stolen and I'm between jobs at the moment, so I won't be able to code for a while :S

Looking forward to seeing this working with different materials!

Ok, I've been doing some more work on this recently and it's now in a reasonable state. It works for the cubic surface (only without normals) and the Marching Cubes surface. It does not currently work with the cubic surface which does have normals because the connectivity is different (duplicate vertices, etc)... I don't currently have any plans to address this but there is always onimatrix's code here.

This is how the decimation of a cubic surface looks:




And this is how the decimation of a marching cubes surface looks:




In the case of the marching cubes surface above, you can see that there are multiple materials present. The volume is also split into several regions. Handling triangles on the edge of regions is tricky because it is important for neighbouring regions to still line up, but I think this is working now. The algorithm does not even attempt decimation if a triangle is across a material border, so there might be room for improvement here.

The biggest catch is that it's currently very slow... in the case of the cubic surface above it took only 5ms to do the extraction but 380ms to decimate the resulting surface. I'm sure it can be sped up a lot, but in Thermite I intend to present the user with the high resolution version initially, then decimate in the background before switching over the meshes.

There's more work I'd like to do on this, but really I need to move on to other tasks. I'll probably come back to it in the future when the speed annoys me too much. Don't try using the code yet, I'll clean it up a little and write an example/documentation over the next couple of days.

Again looks very promising. I think the material border issue won't be relevant for me as I'm using a single texture atlas for the whole volume. Is this right?

Maybe beyzend or onimatrix can help out speeding up the code as they seem to have some previous experience in this field. Otherwise your idea seems pretty good to first show the normal volume mesh while calculating the decimated version in the background, then switch both for a rendering speed gain.
Please keep working on this

It's still relevant, but I guess how important it is will depend on you data. You are using the material ID to decide which part of the texture atlas to use on a given triangle. You have a well defined boundary between two materials, and a triangle with say grass on it can't be merged with another one which has rock on it. But this will only really matter if you are mixing up your materials, which you probably won't be. You will tend to have a large area of rock, with a large area of grass on top, rather than having voxels which go rock->grass->rock->grass, etc.

The main reason it's slow is because it is a general purpose decimation algorithm, rather than being one designed specifically for the cubic meshes. I already had some code which performed the decimation on the Marching Cubes surface using the edge collapse algorithm, and I have simply adjusted this to also work with the cubic surface. It could be much faster if I wrote one decimator specifically for the cubic mesh (which is what onimatrix did) and one for the Marching Cubes mesh... but of course that is more work.

Yep, and don't forget that you will probably have hundreds of decimated patches in the scene. When you change a voxel and have to tempoarily use a high resolution mesh, it is only one of these hundreds which is affected. So I don't really think it will make too much difference. Even if the decimation was really fast I would still probably do it this way.

Unfortunatly I do need to move onto other things (I'm thinking calculating ambient occlusion might be next...) but I will come back to this at some point. It's good to try it out in the wild for a bit before deciding where it should go. But I need to tidy up a little more first (just a day or two), then I will give an example.

Appreciate you adding this. Thanks.

BTW the above is what 128 by 128 by 128 or 64ish? It's not too bad. I can definitely see running this decimation in the background and let it converge over several frames. The end result is that it will reduce triangle count drastically. I for one don't mind that the game looks bad, or slows down for a few frames as long as it becomes much faster in the end.

No problem, I hope it's going to be useful to people.

The 380ms was for a 32x32x32 volume's mesh... but actually I've already improved on that. I'll give this one more evening (tomorrow) for some optimisations and then move on.

Nice work David! I left my project on standby after starting to work in Facebook games (Yeah... I have to eat). I need every minute I have to get inside the social game mindset. Hopefully, the games with which I have grown will overthrow this... thing.