It is currently Wed Dec 11, 2019 9:59 am


All times are UTC




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Transvoxel Algorithm for LOD
PostPosted: Thu Feb 17, 2011 5:28 am 

Joined: Sat Dec 04, 2010 12:10 pm
Posts: 11
(( Note: This is diamondf, posting with permission from psquare. My account is waiting approval. ))

Hello :)

So as you probably already know from experience with psquare, we've been working on a system involving polyvox for a while now. We've come along quite nicely. psquare has worked his magic on the system, and we've now got things set up to a point where we're doing paging/threading, and LOD is currently in the works.

As of right now, though, we need the transvoxel algorithm implemented for the lod, because with lods and current polyvox, there's undesirable popping.

Right now, LOD is not fully turned on in the game because of the popping issue. The lower resolution meshes aren't lining up with the high resolution meshes when the view changes.

The issue I'm referring to isn't shown here, but if you want to take a look at the progress we've made, I designed a quick tech demo to show off what the system we've got is dealing with right now: http://www.youtube.com/watch?v=hm8z09h1cvw

Two weeks ago, I also posted a video on the basic building system that we implemented. It goes more in-depth on the playability of the system. You can view that video here: http://www.youtube.com/watch?v=RrRvDeUWGBM

Unless there's something that would hinder this, could we request this addition for polyvox? The support from polyvox has been really great in the past, and we're hoping to have that assistance again, since we can't really continue in the right direction on LOD without the appropriate polyvox work. David, you've been personally thanked in our game for what you've helped us with :) Anyway, I look forward to working more with polyvox!


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Transvoxel Algorithm for LOD
PostPosted: Thu Feb 17, 2011 8:04 pm 

Joined: Sat Jan 15, 2011 3:49 pm
Posts: 38
Seconding the request for transvoxel implementation, hehe. Nice work on the marquee style building tools. I wish minecraft would implement those, it would make a lot of stuff so much easier.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Transvoxel Algorithm for LOD
PostPosted: Thu Feb 17, 2011 9:47 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Wow, very impressive! I hadn't seen your project before so it's great to see what you've achieved.

However, I'm also a little confused as to what you're doing and what you're after. From your video it's quite clear you're working with the cubic surface extractor for Minecraft style terrain. However, the Transvoxel algorithm you ask for is not for Minecraft style terrain, it's for extracting smooth terrain from a volume with density values.

With smooth terrain the LOD can be implemented by subsampling the volume and running the Marching Cubes surface extractor on the different sized volumes. In each subsampled volume the density can be computed as the average of the densities in the larger volume, and these subsampled volumes (and hence LOD levels) can be several levels deep. Unfortunately this results in small gaps between adjacent LOD levels which is what the Transvoxel algorithm addresses.

But it doesn't really make sense to apply the same concept to Minecraft style terrain. There's no sensible way to make a subsampled volume the average of it's parent, and you will end up with gaps between LOD levels of at least 1 block (between the highest LOD levels) and much more between the lower LOD levels. LOD works on smooth terrain because each level is a good approximation of the one above it, but there is no way to approximate Minecraft terrain without introducing obvious visual artifacts.

However, Minecraft style terrain is much better from a different perspective, in that it tends to have large flat areas which can be represented by a small number of triangles. This is not an approximation (it still looks exactly the same) and it doesn't make sense to have different levels with this approach - it should simply be used all the time. This is what the MeshDecimator is for and you should see this thread for details: http://www.thermite3d.org/phpBB3/viewtopic.php?f=2&t=106. Or are you using this already?

There's more stuff I can explain, but it's probably best to find out more about what you are currently doing and what problems you are encountering.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Transvoxel Algorithm for LOD
PostPosted: Fri Feb 18, 2011 12:53 am 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
I thought maybe I could do LOD minecraft style by just fading in between different LOD levels, since this will happen at some distance I was hoping it wouldn't be as noticeble.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Transvoxel Algorithm for LOD
PostPosted: Fri Feb 18, 2011 1:55 pm 

Joined: Sat Dec 04, 2010 12:10 pm
Posts: 11
Hello David,

Quote:
There's more stuff I can explain, but it's probably best to find out more about what you are currently doing and what problems you are encountering.

We are using the cubic surface extractor. We chop up the world into pages. Each page is associated with a volume and a corresponding extracted mesh. Pages are loaded/unloaded using threading. Building is done by looking into the volume(s) corresponding to the page(s) we are building on, modifying the voxels and re-extracting the meshes.

To counter the usual problem of dealing with batch count, number of triangles, etc, I was looking at LODS.

I did try subsampling, etc., but, as you rightly pointed out:
Quote:
There's no sensible way to make a subsampled volume the average of it's parent, and you will end up with gaps between LOD levels of at least 1 block (between the highest LOD levels) and much more between the lower LOD levels

I do understand that the transvoxel algorithm is aimed at smooth terrains geared at iso-surface extraction. However, looking at Eric’s thesis, specifically the ‘surface shifting’ part (pages 43-44), it occurred to me that the trans-voxel algorithm or a variant of it thereof could be used in conjunction with cubic-extractor as well to minimize this error. This seems to not be the case based on your post. Even if such a method existed, probably a different LOD method would be needed for some of the possible structures that the user could build (bridges, cave type things, etc).

Having said that, I think gross errors can be tucked away using fog, etc and some other tricks, along the lines of what beyzend mentions. So a ‘reasonably’ accurate LOD might do.

Quote:
This is what the MeshDecimator is for and you should see this thread for details

Quote:
and it doesn't make sense to have different levels with this approach - it should simply be used all the time

Yes, I did notice that mesh decimation was recently introduced and was going to look at exactly that next. Interestingly though, my basic testing though shows that just the sheer number of batches is killing the fps, especially at large draw distances. I would expect just stitching adjacent pages’ meshes (say, 2x2) and drawing them instead of even a proper LOD might give performance improvements.

Btw, here’s a slightly longer ‘tech’ demo:
http://www.youtube.com/watch?v=8I93r4CjkDA

I am not very good at building worlds :-), so I refer you to diamondf’s original teaser trailer video that he posted above.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Transvoxel Algorithm for LOD
PostPosted: Fri Feb 18, 2011 10:11 pm 

Joined: Sat Jan 15, 2011 3:49 pm
Posts: 38
psquare wrote:
Interestingly though, my basic testing though shows that just the sheer number of batches is killing the fps, especially at large draw distances. I would expect just stitching adjacent pages’ meshes (say, 2x2) and drawing them instead of even a proper LOD might give performance improvements.


Yeah, framerate is highly dependent on how many draw calls you have, so either drawing all the chunks in one call with a vertex/index buffer or lowering the number of chunks should help you out.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Transvoxel Algorithm for LOD
PostPosted: Sat Feb 19, 2011 4:38 am 

Joined: Sat Dec 04, 2010 12:10 pm
Posts: 11
Well sure. Reducing batches is clear. However I can't just combine a lot of chunks together because then I would not get advantage out of culling, cause overdraw, etc.

Not to mention that this is editable geo/terrain, so making one very large vertex/index buffers which can be updated (when voxels in a region change) may be too large a (cpu) overhead.

I guess only testing different granularities/sizes will tell.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Transvoxel Algorithm for LOD
PostPosted: Sat Feb 19, 2011 3:10 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Sorry for the slow reply guys, I wasn't around yesterday.

psquare wrote:
I do understand that the transvoxel algorithm is aimed at smooth terrains geared at iso-surface extraction. However, looking at Eric’s thesis, specifically the ‘surface shifting’ part (pages 43-44), it occurred to me that the trans-voxel algorithm or a variant of it thereof could be used in conjunction with cubic-extractor as well to minimize this error. This seems to not be the case based on your post. Even if such a method existed, probably a different LOD method would be needed for some of the possible structures that the user could build (bridges, cave type things, etc).


Possibly, I think the same principles could be applied to Minecraft style terrain but I just don't think it would look very nice. Even if you fix the holes it's still going to look strange when it transitions from a course mesh to a finer one.

psquare wrote:
Having said that, I think gross errors can be tucked away using fog, etc and some other tricks, along the lines of what beyzend mentions. So a ‘reasonably’ accurate LOD might do.


During the transition period you could render both high and low res meshes (possibly stitched to be a single batch). That will hide any holes. Probably cross fade between them as well. Still not sure how good it will look :-)

psquare wrote:
Interestingly though, my basic testing though shows that just the sheer number of batches is killing the fps, especially at large draw distances. I would expect just stitching adjacent pages’ meshes (say, 2x2) and drawing them instead of even a proper LOD might give performance improvements.


Yep, this doesn't suprise me. So rather than LOD, you're really looking for a way to reduce the batch count. Now, I haven't had a need for anything like this yet but I can loosely describe what I was planning if/when the need arises (but not in PolyVox, it would be at a higher level).

I expect that I will perform the kind of stitching you describe, so that 4 adjacent regions will be stitched together into a single larger mesh. However, I will also keep the seperate meshes in memomy as well (obiously you should be clever about the way you duplicate the data here but I haven't looked at the details). I general I would aim to draw the single large mesh most of the time.

When a voxel get modified, I would switch the single large mesh for the four smaller ones and then update only the smaller one which is affected by the change. Then, in the backgound, I would redo the stiching to make the single large mesh. The result is that batch count would reduce temporaily when editing was being performed, but this would only happen in small parts of the world at a time.

Naterually I would then take this a step further, and merge 4 large meshes into another even larger one. Essentially building a hierarchy here, where potenially the top level could be one mesh representing the whole world. Of course this depends on how much vertex/index can be shared between the different levels.

As fo culling, well you have some flexibility now. If the whole volume is visible use the top level (single mesh), as you zoom in you might just use parts of the hierarchy. Really some experimentation is needed here. As I said, I haven't implemented it so the idea may not work, but it's where I would start.

psquare wrote:
Btw, here’s a slightly longer ‘tech’ demo:
http://www.youtube.com/watch?v=8I93r4CjkDA

I am not very good at building worlds :-), so I refer you to diamondf’s original teaser trailer video that he posted above.


Thanks, but I already downloaded the demo :-)


Top
Offline Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 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