Page 1 of 13

[GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Wed Mar 21, 2012 3:51 pm
by PhilipLB
Project Proposal

I plan to implement a volume renderer for large meshes like terrains. Ideally this would become a full fledged volume terrain component for Ogre over time which I will support and be responsible for the ongoing development. After the summer I will maintain this subproject, complete existing features and add new. This GSoC is aimed at creating a prototype. The license will be the same as OGRE itself, MIT.

The heart of something like this is a LOD algorithm. One of the few current available resources here is the Transvoxel algorithm [1]. But I think it has a major drawback: So many triangles due to the modified Marching Cubes. So my idea is to take Dual Marching Cubes [2], which is much sparser in triangles where they aren't needed. It also preserves sharp edges.

This image compares the source (upper left), the marching cubes version (lower left), the dual contouring version (lower right) and the dual marching cubes version (upper right).

Image

One nice thing about it is, that it is a somehow simple concept made of several quite independend steps (generating the octree, isolating features, creating the dual grid, applying marching cubes to the dual grid). So there are several options to modify it to the needs or to save some time (like not isolating features via QEFs but to take the center of the octree cells for it).
The LOD part of it would be similar to Chunked LOD Terrain [3] where the single chunks are closed so the cracks are already filled. With closed I mean this: To generate a chunk, there's always a part of the volume data, a cube, to be used. At the planes of this cube, the isosurface would have open parts as it is "cut" out of the rest. See the dark gray part of the following image (lousy programmer art). When this open parts are triangulated and closed, no gaps can occure anymore when two chunks of different resolutions are drawn together.

Image

This triangulation can be achieved in two ways and it must be evaluated, which one is better.
a) Use some kind of CSG to cut the volume data cube out of the complete volume data
b) "Just" triangulate the open parts.
b) seems to be much more complicated and my feelings are, that a) is the way to go.

Another thing to consider and evaluate while the project is running, is the generation time of the chunks. If it is too long, the generation can be a preprocess with the binary data being saved to a file. The loading time for the user would be then just the reading of the file from the disc.

Polyvox could be a valuable library. This evaluation comes after implementing the dualgrid (which is the biggest part). It might be used for:
  • loading the volume data
  • applying the marching cubes to the dualgrid
Here is a rough UML sketch about the planned architecture.

Image

The central part for generating the meshes is the MeshGenerator. It uses a VolumeSource as representation of the density function with getValue(x, y, z). There the three steps of the DMC mesh generation happen. The Octree is generated via the VolumeOctree classes, FeatureIsolator and Contourer have it's own creation classes (maybe they aren't needed and can also be directly in the MeshGenerator, implementation will show). The outcome is an instance of TerrainChunk.

The OcreeGenerator will create the volume octree consisting of VolumeOctreeNodes. The octree starts with a root node containing the complete volume and splits into octants if the VolumeOctreeSplitPolicy says so. This goes on recursivly until the policy says false. The first implementation uses the VolumeOctreeNodeGridSplitPolicy which is a regular grid over the VolumeSource and split if there are enough gridpoints near the isosurface (== density < epsilon). The dual marching cubes paper proposes splitting with quadric error functions (QEF) which would be VolumeOctreeNodeQEFSplitPolicy using the class QEF. But the grid approach will be good enough for the first octree generation.

VolumeSource is an abstract class which is the source of the volume data. The first implementation is a small CSG. It consists of the following classes:
  • CSGSphereVolumeSource: Generator for a sphere volume, center and radius given
  • CSGPlaneVolumeSource: Generator for a plane volume, hessian normal form given
  • CSGCubeVolumeSource: Generator for a cube, center and dimension given
  • CSGOperationVolumeSource: Abstract class for the CSG operations, holds two pointers to a VolumeSource as operants
  • CSGIntersectionVolumeSource: Intersection of two VolumeSources
  • CSGUnionVolumeSource: Union of two VolumeSources
  • CSGDifferenceVolumeSource: Difference of two VolumeSources
  • CSGNegateVolumeSource: Negation of a VolumeSource
The implementations PerlinNoiseVolumeGenerator and FileVolumeGenerator are in a red tone as they won't be in the prototype but imaginable examples what could be done after the summer. PerlinNoiseVolumeGenerator could generate volumes like in [4]. FileVolumeGenerator loads dumps of volume informations from files which were dumped by the function writeToFile() of the parent class.
TextureVolumeSource (also already implemented) loads volume data from volume textures. This is usefull for tools like Acropora [5] which can export the volume data as 3D dds. It uses either trilinear interpolation or nearest neighbour to access the discret values.

TerrainChunk is the octree with the separate LOD meshes and used for rendering. activateLODLevels() traverses the octree and en- / disables the LOD chunks depending on the position of the given camera. It is derived from SimpleRenderable which offers a nice base for the actual rendered things in OGRE.

Of course, there is the risk, that not everything works out as I imagine as this is a more or less new approach for volume LOD, but I'm very confident here. :)

Schedule
  • Mai 21. - Mai 27.: GSoC start. Evaluation of what's done (Masterthesis starts earlier) and planned. Setting up the exact implementation plans for the GSoC part which also might shift this roadmap.
  • Mai 28. - June 03.: Working on Octree generation
  • June 04. - June 10.: Octree generation done
  • June 11. - June 17.: Working on Dualgrid generation
  • June 18. - June 24.: Working on Dualgrid generation
  • June 25. - July 01.: Dualgrid generation done
  • July 02. - July 08.: Working on Marching Cubes
  • July 09. - July 15.: Marching Cubes done
  • July 16. - July 22.: Working on LOD part
  • July 23. - July 29.: LOD part done
  • July 30. - August 05.: Working on simple material system with triplanar mapping*
  • August 06. - August 12.: Simple material system with triplanar mapping done*
  • August 13. - August 19.: Refactoring and generalizing, buffer
  • August 20. - August 26.: Refactoring and generalizing, buffer
  • August 27. - August 31.: Final GSoC touches and handing in
* This could be a feature which could also be implemented after GSoC when Murphy kicks in with nasty bugs or unseen difficulties.

This roadmap is outdated and only kept to have the initial proposal intact. The most current roadmap is in the Wiki article!

Why You're The Person For This Project

I've finished my bachelors degree in media computer science in 2009, worked then for a year as a developer in a small game studio and then started my master in 2010. This project is my masterthesis and so I have a lot of motivation to make it a success. ;) As a side-effect, a lot of documentation would be there.
I'm a experienced C++ programmer, using this language in some projects now since ~7 years. This includes the implementation of a scenemanager in Ogre providing an implementation of Chunked LOD Terrain and with occlusion culling which resulted in a paper being published at the "
6. GI-Workshop "Virtuelle und Erweiterte Realit├Ąt"" (6th workshop of the society of computer science "Virtual and Augmented Reality") [6].

Why OGRE?

OGRE is a great 3D graphics library. The main use case for this project is of course volume terrain with cliffs, hangs and caves. A component like this would give OGRE something which is not (yet) often seen.

For me, OGRE is also the ideal platform because I have some experience with it and don't need to start this project from scratch with low level OpenGL.

Infrastructure [1] http://www.terathon.com/voxels/
[2] http://faculty.cs.tamu.edu/schaefer/research/dmc.pdf
[3] http://tulrich.com/geekstuff/chunklod.html
[4] http://http.developer.nvidia.com/GPUGem ... _ch01.html
[5] http://www.voxelogic.com/index.php?opti ... &Itemid=21
[6] http://www.dlr.de/sc/en/desktopdefault. ... ead-17273/

Re: [GSoC 2012] Volume Rendering with LOD

Posted: Wed Mar 21, 2012 4:47 pm
by tuan kuranes
Did you check PolyVox work http://www.ogre3d.org/forums/viewtopic.php?t=27394 ?
Could you build upon it to deliver improvements or help ogre integration ?

Re: [GSoC 2012] Volume Rendering with LOD

Posted: Wed Mar 21, 2012 5:04 pm
by PhilipLB
Hi,

yep, I followed every thread arround here about this topic. :) Polyvox could be indeed usefull when countouring the dual grid via marching cubes.

Re: [GSoC 2012] Volume Rendering with LOD

Posted: Wed Mar 21, 2012 5:08 pm
by jacmoe
If you could expand this idea - or rather 'refine' it - to become a voxel/volume terrain component using Polyvox as dependency, that would really be awesome. :)
That is volume rendering with LOD in practice.

Re: [GSoC 2012] Volume Rendering with LOD

Posted: Wed Mar 21, 2012 5:56 pm
by PhilipLB
Nice. :)
I added some sentences about Polyvox. :)

Re: [GSoC 2012] Volume Rendering with LOD

Posted: Thu Mar 22, 2012 7:51 am
by Assaf Raman
Nice start.

Volume rendering is a topic that has has so many articles about...

What I am missing from this proposal is what uses are for the end product, give some use case for potential OGRE users using it.

BTW: Look at this: A Survey of GPU-Based Volume Rendering of Unstructured Grids - a bit old, but I think it may be relevant to your topic.

Re: [GSoC 2012] Volume Rendering with LOD

Posted: Thu Mar 22, 2012 11:21 am
by PhilipLB
Specified the main use case (terrain) a bit more in the "Why OGRE"-section. :) Please tell me if there's something missing.
This paper is indeed interesting, but seems to handle mostly direct volume rendering and not generating isosurface meshes. And it's true, there are so many papers out there about this topic. Read so much the last weeks... Conclusion so far for me is still, that DMC is a good choice.

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sat Mar 24, 2012 12:10 pm
by jacmoe
The author of Polyvox has an article in Game Engine Gems 1 on voxel terrain using Polyvox.
May I suggest that you check that out?

And in addition to that, it would be helpful to check out the C4 Engine which uses similar ideas:
[youtube]9gf3sFBNOMk[/youtube]

http://www.terathon.com/voxels/

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sat Mar 24, 2012 12:56 pm
by PhilipLB
The C4 Engine Terrain is exactly the mentioned Transvoxel algorithm. :)

Don't have the Gems book arround here. :/ Does it cover LOD? Can't tell while looking in the content table.

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sat Mar 24, 2012 10:50 pm
by jacmoe

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sun Mar 25, 2012 3:02 pm
by duststorm
This is a very promising project proposal.

It would be nice if it can offer separate functionality libraries, like CSG boolean operations or other geometric operators. (of course only if those are in scope of the project itself too)
They could in turn be very useful for libraries like OgreProcedural or for creating destructible objects in combination with physics engines.

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sun Mar 25, 2012 6:30 pm
by jacmoe
I am so looking forward to this - please succeed! :D

If you do, I'll lose my main reason for using the C4 Engine instead of Ogre. :)

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sun Mar 25, 2012 10:03 pm
by PhilipLB
Hi,

thanks for the link, but the relevant pages aren't visible (at least not in Germany). :) Too bad, this book isn't available in the uni library. And not in a single library in Berlin (according to https://www.voebb.de/ ...). O_o But I'll try to order it over the uni lib. :)
And thanks for the encouraging words! :)

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Mon Mar 26, 2012 11:24 pm
by PhilipLB
I added a first version of the roadmap. This is of course a first rough estimate and subject of change in the next days. :)

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Tue Mar 27, 2012 7:20 am
by jacmoe
Looks great! :D

Would it be possible to work on triplanar mapping in parallel - that feature alone would be killer! Would be disappointing if it got scrapped due to time constraints.

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Tue Mar 27, 2012 9:28 am
by PhilipLB
Triplanar mapping alone doesn't seem that much work? At least if you look at [1]. Something like Indirection Mapping, THAT seems complicated. And that's it what I've found which creates nice fitting UVs. :)

There would be several iterations:
- First version would have just one texture and the planar projection being chosen by the normal
- Next one blending together up to three textures like in the article
- Next one with bump mapping
etc. This is something which splits up nicely. :) But I added a sentence about it being actually one feature which could be delayed after GSoC if something seriously fails.

[1] http://http.developer.nvidia.com/GPUGem ... _ch01.html
[2] http://graphics.cs.williams.edu/papers/ ... tionI3D08/

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Wed Mar 28, 2012 9:58 am
by duststorm
Where would this project fit in with the exisiting Ogre codebase?
Would it be an extension of Ogre::Terrain or is it a completely novel polyvox terrain component?

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Wed Mar 28, 2012 11:36 am
by PhilipLB
Hi,

actual code design isn't done or decided yet. :) But my intuition says, that it would be an own component as it wouldn't have something to do with the existing terrain codewhise.

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Thu Mar 29, 2012 7:44 pm
by Cygon
I fully support this proposal :)

Someone has already implemented the "Transvoxel" algorithm from C4 in Ogre: voxelTerrain - marching cubes, transvoxel - demo - vid - src, though right now his licensing plans sound incompatible with packaging as a core Ogre component.

The time table might be a slight bit optimistic given the complexity of terrain rendering algorithms, but you do know your stuff and you've added 2+2 weeks of buffer time.

It would be nice if this could be somehow integrated with Ogre's paging component.

Regarding your remark on the generation time of chunks, this sounds like an ideal task that could be done in a background thread. Taking care of thread synchronization and work distribution would be too much for the GSoC schedule (I think), but at least keeping the chunk generation code isolated enough so that it could be run in parallel later on could be worthwhile goal.

Just a long-time lurker's $0.02 :)

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Thu Mar 29, 2012 8:40 pm
by jacmoe
Cygon wrote:Someone has already implemented the "Transvoxel" algorithm from C4 in Ogre: voxelTerrain - marching cubes, transvoxel - demo - vid - src, though right now his licensing plans sound incompatible with packaging as a core Ogre component.
Wow - that's really a fucked up license!! I didn't know he changed it. A pity.

That doesn't prevent people from having a look at it, though.
But I really don't like duplicate efforts. :(

<edit>
Would be nice to work with, nudge, whatever the Polyvox author into implementing the transvoxel algorithm into Polyvox. :)
</edit>

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Fri Mar 30, 2012 3:22 pm
by PhilipLB
To the schedule: There are the buffer weeks, the slightly optional (but as last escape ;)) triplanar mapping and the time until May 21th. :)

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sun Apr 01, 2012 9:44 am
by PolyVox
PhilipLB wrote:Hi,

thanks for the link, but the relevant pages aren't visible (at least not in Germany). :) Too bad, this book isn't available in the uni library. And not in a single library in Berlin (according to https://www.voebb.de/ ...). O_o But I'll try to order it over the uni lib. :)
And thanks for the encouraging words! :)
When I clicked on that link it also said an error message (in German), but when I scrolled down to later pages and then scrolled back up it was there :?

Anyway, I gave up copyright when I submitted the article to Game Engine Gems, but since Google then made it freely available I took the liberty of saving each of the pages from Google as a .png image. So if you can't read the chapter online then PM me your email address and I'll send you the pages.
jacmoe wrote:Would be nice to work with, nudge, whatever the Polyvox author into implementing the transvoxel algorithm into Polyvox. :)
Actually someone is already working on TransVoxel. It'll be a couple of months before we get it integrated though. See this thread: http://www.volumesoffun.com/phpBB3/view ... ?f=2&t=338

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sun Apr 01, 2012 12:59 pm
by madmarx
Someone has already implemented the "Transvoxel" algorithm from C4 in Ogre: voxelTerrain - marching cubes, transvoxel - demo - vid - src, though right now his licensing plans sound incompatible with packaging as a core Ogre component.
I think I can oppose this.
I have found inside the linked demo, code that I did, namely the triplanar texturing shader.
And I can assure you this part of the code was NOT GPL-only compliant. It was do-what-you-want compliant ^^, something I posted in another thread long ago.
Not a problem for me (i don't care), but if you are knowlegdeable about licences maybe this could help you.

Anyway I doubt the guy has sold any copy, so you can still try to make him change his mind! Send him a mail, explain the situation, maybe he will switch his mind? Also add that 'everyone is doing unity3d these days, nobody will buy your code' that should help :lol: !

Just my 2 cents of course
EDIT: I made several version of the triplanar shader for ogre, some including normals, skeleton, flowshader, specular. I can provide them.

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sun Apr 01, 2012 9:19 pm
by qwertzui11
jacmoe wrote:
Cygon wrote:Someone has already implemented the "Transvoxel" algorithm from C4 in Ogre: voxelTerrain - marching cubes, transvoxel - demo - vid - src, though right now his licensing plans sound incompatible with packaging as a core Ogre component.
Wow - that's really a fucked up license!! I didn't know he changed it. A pity.
madmarx wrote:
Someone has already implemented the "Transvoxel" algorithm from C4 in Ogre: voxelTerrain - marching cubes, transvoxel - demo - vid - src, though right now his licensing plans sound incompatible with packaging as a core Ogre component.
I think I can oppose this.
I have found inside the linked demo, code that I did, namely the triplanar texturing shader.
And I can assure you this part of the code was NOT GPL-only compliant. It was do-what-you-want compliant ^^, something I posted in another thread long ago.
changed the license; so Do What The Fuck You Want. Next time ask me before so talking bad about my hard work ;) As far as I know my src is the first OS impl; im a bit hurt :D

Markus

Re: [GSoC 2012] Volume Rendering with LOD aimed at terrain

Posted: Sun Apr 01, 2012 9:52 pm
by jacmoe
Qwertzui11 : I didn't badmouth you. :)

I just hate the GPL license for libraries.
That's all.

I think it's really cool of you to change the license, but I think you ought to consider to change it to ZLIB, BSD, MIT or Apache.
You really deserve the credit.
I haven't read the DWFYW license, but...

Don't feel bad - feel wanted. :mrgreen:

I would have respected any decision - including the GPL - but I still hate that license for libs. :twisted:

Thanks a lot. :D