It is currently Tue Dec 10, 2019 11:43 am


All times are UTC




Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Mesh decimation in PolyVox
PostPosted: Sat Dec 18, 2010 12:26 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
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:

Image

After decimation:

Image

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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Sat Dec 18, 2010 5:24 pm 

Joined: Sun Oct 03, 2010 10:13 pm
Posts: 73
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 :)


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Sat Dec 18, 2010 7:37 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Sun Dec 19, 2010 1:18 am 

Joined: Wed Dec 08, 2010 5:54 am
Posts: 27
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!


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Tue Jan 04, 2011 9:34 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
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:

Image
Image

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

Image
Image

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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Wed Jan 05, 2011 3:30 pm 

Joined: Sun Oct 03, 2010 10:13 pm
Posts: 73
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 :)


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Wed Jan 05, 2011 7:51 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
AndiNo wrote:
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?

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.
AndiNo wrote:
Maybe beyzend or onimatrix can help out speeding up the code as they seem to have some previous experience in this field.

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.
AndiNo wrote:
...to first show the normal volume mesh while calculating the decimated version in the background, then switch both for a rendering speed gain.

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.
AndiNo wrote:
Please keep working on this :)

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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Wed Jan 05, 2011 8:25 pm 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Wed Jan 05, 2011 10:52 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
beyzend wrote:
Appreciate you adding this. Thanks.

No problem, I hope it's going to be useful to people.
beyzend wrote:
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.

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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Mesh decimation in PolyVox
PostPosted: Thu Jan 06, 2011 12:50 am 

Joined: Wed Dec 08, 2010 5:54 am
Posts: 27
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.


Top
Offline Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: Majestic-12 [Bot] and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created StylerBB.net