sparse voxel octree

rouncer 103 Oct 28, 2009 at 08:51

Ive got a little project going, and its a sparse voxel octree.
Right now as I type on my other computer im converting a course triangle terrain into a dense voxel model, and its TAKING AGES.

After I’ve done this, I then have to calculate all the larger mips and thats going to take ages too.

Setting up the streaming-render system isnt that hard, but actually getting a real unique model in it thats large is really difficult, especially since you have to calculate all the mips for it.

The terrain im making is 65536x65536 voxels on the y plane, and that is a huge amount, ill get back to you with how much disk space it took.

So far, its probably been calculating for an hour and its not finished yet, I havent coded a progress metre even though I probably should have, the computer is just sitting in stasis computing it.

So, as far as voxels go- would anyone have any suggestions for me about improving calculation speed (from hours to maybe 20 minutes maybe) especially when I get up to computing the mips.

So far, its not threaded to stream, but it is running ok considering,

When I finally implement threaded streaming you get to stream on the second cpu and render on the first, which is pretty cool.

Has anyone else coded this before?

Thanks for reading.

11 Replies

Please log in or register to post a reply.

rouncer 103 Oct 28, 2009 at 11:06

I got the terrain half finished, I had to abort the procedure because it took 3 hours just to do half of it!
The map hit 23.7 gigs, and itll probably be 50 gigs if it was all complete, thats uncompressed at this stage.

The voxels are all given random colours, the white lines are octree divisions.


Its not true voxels, because I actually just stream in a point cloud of “voxel corners” and connect them together with triangles, but its similar enough to make most the algorythm the same as the raycasted one.

Its not that its not streaming quick enough thats the problem, because I know I can probably fix that… the big problem is just it takes so long to create the level cause of the sheer amount of voxels to make.

There are no mips being displayed in the render, because I havent computed them yet, which is going to be the next problem to solve, hopefully I can implement some kind of automatic system where it builds the mips as the map displays, slowing the streaming down a bit but it seems like the best idea to me, aposed to doing it all in one big long hit (which would be ages…)

rouncer 103 Oct 28, 2009 at 13:15

Ive got it streaming in threaded now, just it takes too long to update the screen, if you go fast enough - the streaming wouldnt be able to keep up with the movement… but i think ive got enough detail for little grasslets, if i ever make a scene with it it would probably look pretty cool. :)

But if im not so anal about detail - it does work… the streaming only has trouble keeping up with the camera movement if i say the voxels are too small… if i say they are larger and move the camera slower then the streaming keeps up fine.

So I dunno if its a success or a failure… ill definitely finish it tho.

spacerat 103 Oct 28, 2009 at 18:58

do you have some screenshots ? I would be interested to see them :-)
I’m also experimenting with svo - however without streaming at the moment; also I have doubts that a large and complex scene containing rocks and trees fits into the graphics card at the moment.. Do you have tried complex scenes already?

rouncer 103 Oct 29, 2009 at 06:18

Thanks for the comment…

Im working with a fairly complex scene, its just its a boring flat terrain, but its very dense in points. (each colour in that last screenshot is a unique voxel)

Ill have some more screenies soon, but I wont have anything that nice looking until ive got the editing tools done. But the next shot I post will probably be when ive got the mips working and you can see right to the end of the map.

Its not really a voxel engine… its more of a streaming point cloud - but its very similar, i get to add 3d coat editing tools the same way.

One question, for anyone, is how do you improve the streaming capability of your computer? (including using a gpu) is there something you can buy to help you stream larger volumes of data??

spacerat 103 Oct 29, 2009 at 12:20

I am thinking about streaming too - its the hardest problem with voxels. If you would just load the entire scene on the screenshot into GPU ram, it would cost you probably something like 10GB - even considering LOD and basic color/normal compression.

rouncer 103 Oct 29, 2009 at 12:39

I streamed from the start of this project.
I ditch the geometry that isnt in view as soon as it goes out of view… im probably going to have problems with pop outs and pop ins, but ill get to that later.
That way I can do it in under 200 megs of gpu ram, or something like that I havent calculated it exactly yet.

Maybe I shouldnt have called this thread SVO, because my implementation is more of a point cloud, but the points are dispersed single units apart just like voxels.

What youve got there is true voxels, mines only similar.


Heres a version of mine with the more distant mips calculated, it takes about 3 seconds for the whole visible point cloud to stream in.
The octree isnt streaming the mips right yet (they are all overlapping each other) and theres floating geometry and that might be because they arent computed properly… its full of bugs.

If you walk relatively slow through it the streaming keeps up with the camera…. but if you go too quick youll hit a lot of temporarily unstreamed space.

The map itself is about 4 billion points if it all was there, and its taking about 60 gigs of hard disk space.

Ill post again when I get the bugs out of it, and I might spawn some spheres in the air.

And im eventually planning on rastering the points with small rectangles to get rid of the gaps between.

Hopefully ill have something as pretty as your scene soon. :) at the moment its a bit of a mess.

skynet 101 Oct 29, 2009 at 13:52

rouncer, you need to read up on “Out of Core” processing strategies for generating the mipmaps of such huge datasets. Basically it means, you always only operate on a subset (which fits into main memory) of the whole dataset. It is also very imortant to schedule reads/writes from/to harddrive very carefully, in order to leverage maximum read write speeds. Simplified it works like this:
1. read 512mb of data (512 is arbitrary, you want to make this as big as possible)
2. process data
3. write results
4. if (not finsihed) goto 1

Second, voxels are not much unlike texels. For texels there are approaches (Clipmapping, Megatextures, Virtual Texturing etc….) that try to be “output sensitive”. That means, the size of the working set of data is only dependent on the size of the ouput (i.e. screen resolution!), NOT of the dataset itself. It basically means, no matter how big your voxel dataset is, for a given screen resolution you only need to process a certain (fixed) amount of data in memory for rendering. Mind you,if your screen resolution is only ca. 2mio pixels, there is simply NO ROOM for displaying 16gigavoxels! The other voxels are:
a) out of frustum (you do frustum culling)
b) hidden behind other voxels (raycasting solves occlusion culling for you)
c) too small to be visible (mipmapping solves this problem)

A good example where all these principles are included is the “GigaVoxels” system. Just google for it.

rouncer 103 Oct 30, 2009 at 08:21

hey thanks for the input… projects going well, will post more shots soon. yeh, gigavoxels is my main inspiration for this.

rouncer 103 Oct 30, 2009 at 14:31

fully streamed and working, i think its time to finally join the dots.


Its streaming real nice, next pic should be good… itll get rid of the see through thats ruining the shot.

I should be able to support a really dense environment, i ended up being able to stream more than I thought!!

The secret is loading them the mip chunks up 8 at a time instead of 1 at a time…

rouncer 103 Oct 31, 2009 at 09:21
rouncer 103 Nov 06, 2009 at 14:14

Moved it to dx10, now the voxels all draw with point sprites.


Up close shot of the voxels:


next job to add, csg - sculpting and painting!