It is currently Wed Dec 11, 2019 1:06 am


All times are UTC




Post new topic Reply to topic  [ 17 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Octree based voxel implementation
PostPosted: Tue Sep 20, 2011 6:03 pm 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
Hello,

Not really PolyVox as such since I wrote this from scratch, but I thought you guys might be interested to see this:

http://www.youtube.com/watch?v=7bQXz80gIbU

This is an octree-based voxel implementation I wrote over the last couple of weeks. Still pretty buggy at this stage.

The tree automatically expands/collapses as necessary. The blue wireframe block shows the tree simplifying automatically when filling a branch with duplicate leaf data.

Not sure how this will go performance-wise once the scene gets more complicated. Poorly, I would expect. But I am not intending to use it for landscapes etc so it should be OK for my purposes.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Tue Sep 20, 2011 9:57 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Very nice - though I actually saw this earlier as YouTube linked it to my own video. It looked a bit strange at about 15 seconds in though, when you have placed seven cubes but not the eighth? The triangles don't look right for the missing cube?

I'll be interested to see how big you can go with this as octrees should allow for efficient storage.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Wed Sep 21, 2011 3:45 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
The triangles are actually correct, it just looks odd because some of the wireframe lines become obscured. This seems to happen in Ogre when rendering a color pass then a wireframe pass at right angle like that.

I have only done preliminary testing for memory yet. As expected with octrees it is very efficient with large contigious areas, but a lot of complexity at small scales blows out the memory usage badly.

I was thinking this could be rectified by either trying a paging LOD approach, or by replacing leaf nodes below a certain depth with polyvox style RLE compressed linear arrays.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Wed Sep 21, 2011 8:55 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Ah, I see what you mean about the wireframe lines.

With an octree, the other thing you might want to watch out for is to make sure you can get fast access to the neighbouring voxels. This is important for surface extraction and also in a few other places. That's the main reason I went for a linear layout in PolyVox though I didn't actually test the octree approach so maybe it's not really a bottle neck. Just something to keep in mind.

I'll look forward to seeing how it develops...


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Sat Oct 08, 2011 3:12 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
Here are 2 updated videos of my octree implementation:

http://www.youtube.com/watch?v=zimQcGQdSZ4
http://www.youtube.com/watch?v=jmjmlXdyLgg

Since I am still re-extracting the entire domain every time a change is made, once the scene becomes complex making changes becomes very slow.

Not 100% sure what to do about that yet. I would like to avoid breaking the scene up if possible since I don't want to increase batch count and create seams. I wonder if mesh decimation would help (since would mean won't have to clear/create such large vertex buffers each time)

I am not even sure where the bottleneck is yet, since I can't get any profiling to work. I am trying to use VerySleepy 64-bit in windows, but it always crashes :-\


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Sat Oct 08, 2011 3:35 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Wow, this is getting interesting, but let's just check my understanding. Rather than really extracting a mesh in the way the PolyVox does, you are starting at the top of the octree and checking if the root not is copletely solid. If so, you simple draw one large cube. If not, you go down to the next level and check each of its children. So rather than extracting a surface you are simply drawing cubes of different sizes?

I considered something similar before I built decimation into the cubic surface extractor. In my case, the idea was that I would find a solid shape in the volume and find the largest cube which would fit inside it. I would then find the largest cube which would fit in each of the peices which was left, and so forth. Like you, I would then end up with a number of variably sized cubes to draw.

In my case the tricky part was creating an algorithm to identify these largest cubes, but using an octree means you have this information readily available.

DefiniteIntegral wrote:
Since I am still re-extracting the entire domain every time a change is made, once the scene becomes complex making changes becomes very slow.

Not 100% sure what to do about that yet. I would like to avoid breaking the scene up if possible since I don't want to increase batch count and create seams. I wonder if mesh decimation would help (since would mean won't have to clear/create such large vertex buffers each time)


How about just drawing the cubes individually using instancing? This thread (http://www.ogre3d.org/forums/viewtopic.php?f=1&t=57693) demostrates how you can draw 300000 cubes at 60FPS by expanding points in the geometry shader. Of course you still need to perform updates as your structure changes.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Sat Oct 08, 2011 6:28 pm 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
I can't instance cubes because my material system / extractor supports transparent & non-solid materials, so some faces need to be specifically omitted for transparents to render correctly or added facing backward for non-solids. Also, the faces only generate on the smaller side of two neighboring leaf nodes, so 1 cube might have 2 triangles on one face, and 32 triangles on another face. Finally, depending upon material interaction triangles may be generated facing both directions with different materials specified.

I do store neighbor node pointers in each branch/leaf node, so material comparisons aren't too slow.

I guess for adding voxels I could just instance temporary cubes then remove them once extraction completes. Not much to be done when removing voxels, I suppose...

As you said when iterating the tree to extract the mesh, it is just creating a cube based on tree position/depth, but it selectively includes/excludes faces dependent upon material interactions as above. All triangles extracted of the same material are added to a single list and converted into an Ogre::ManualObject (so ogre batch count is equal to number of materials in use.)

At this stage no mesh decimation is done, so there is some room for improvement in regards to triangle count.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Sun Oct 09, 2011 9:27 am 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Good point regarding the transparent materials - that does make the use of large cubes a bit difficult. Another problem would be that per-vertex properties wouldn't work well. I don't know if you need these anyway, but I'm thinking about adding some per-vertex ambient occlusion into PolyVox.

Another thing you could consider would be to store one mesh for the parent node and then eight meshes for the children. Normally you just draw the parent mesh, but if a single voxel changes you switch to drawing the eight child meshes instead and reextract one of them (which is faster that regenerating the parent mesh - especially in a much deeper hierarchy). The you regenerate the parent mesh at your lesiure and swap back to it when finished.

Obviously you would want to reduce the amount of geometry duplication... maybe the parent could use the same vertex buffer as it's children and just have it's own index buffer? But then all the children have to share a vertex buffer which could get complex. I haven't really thought this through properly, but I had it in mind for the future and maybe it fit's into your system.

Anyway, it will be good to see how your system works out.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Tue Dec 20, 2011 12:56 pm 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
Hi David,

Just thought I would let you know about this latest video: http://www.youtube.com/watch?v=w1b1jp3CI6A

This is after re-writing the entire extraction process and adding tree traversal optimizations. After thinking about your previously reply, I created a persistent mesh that shares vertices across all materials. Those vertices only exist on CPU though, each time a particular material is modified it's vertex/index lists are re-compiled and re-uploaded to the GPU. So it isn't great, but worlds apart from my previous version.

As you were interested in seeing how octrees work, I'll let you know that the scene in that video brings my applications RAM usage to 450MB, and the scene saves to disk at around 129KB (compressed with GZIP into about 400 files, one for each tree section). If the scene were a normal array based implementation, it would probably be around 1024^3 on rough estimation.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: Octree based voxel implementation
PostPosted: Tue Dec 20, 2011 1:44 pm 
User avatar

Joined: Wed Jan 26, 2011 3:20 pm
Posts: 203
Location: Germany
Wow, this looks really great! Especially what you did with the furniture
just out of curiosity, have you thought about raycast rendering on the octree? (just cpu, gpu would be hard due to the pointer stuff of the octree)

in an octree raycasting could be really fast


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

All times are UTC


Who is online

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