[GSoC 2013 - accepted] Improve Progressive Mesh

[sajty]

Hi!
I’m Peter Szücs and I’m studying Master of Computer Engineering at Budapest University of Technology and Economics.
Sorry for the late proposal. I hope it's not too late.

Motivation
It's waste of performance to have high quality models in faraway distance. Games can gain lot of performance by reducing faraway models and Ogre provides two methods for this: Manually created mesh LOD (for example in Blender) and generated mesh LOD. Blender supports nice reduction algorithms, why don't we just use that? First manually created mesh LOD creates a separated mesh for each LOD level, which means vertex data is duplicated for each LOD, which makes a big memory overhead. The memory overhead is needed, because Blender moves the vertices from original position to a calculated new position, so we need a separated vertex buffer too. Why don't we use Hoppe's algorithm or other more advanced techniques for reduction? These techniques have got the same problem as Blender. Also it would add limitations: For example if the mesh has bone weights or custom vertex data passed to a vertex shader than you can’t just insert a vertex. So the goal of my GSoC proposal is to improve current progressive mesh algorithm.

How to use it currently?
The progressive mesh algorithm was rewritten multiple times and the interface differs between v1.7, v1.8 and v1.9. I have created the MeshLod sample for v1.9 to show the LOD features. However if you just need more performance, you can run the following code on every mesh:

Code: Select all

Ogre::QueuedProgressiveMeshGenerator pm;
pm.generateAutoconfiguredLodLevels(mesh);

Proposal
I would like to do 6 independent tasks related to progressive mesh:

1. Compress LOD levels: I had an idea to compress LOD by up to 50% without performance degradation! My idea is to merge 2 index buffers into a single merged index buffer. The merged index buffer would consist of 3 parts. Let’s say we merge LOD1 + LOD2, then the beginning of the buffer would LOD1 faces only, second part would be LOD1+LOD2 shared faces and the third part would be LOD2 only. Imagine it as a frame shifting mechanism, where I just change the offset and size of the buffer instead of swapping buffer. (1 weeks of work)
   
2. Take into account vertex normals: This one is the most visible artifact in the output currently. Try out the MeshLod sample and check the color above the mouth while you reduce Sinbad.mesh. At 50% its dark, 52% its bright, 57% its dark. This is caused by self-shadowing. Fixing this would improve the quality of the output. <TODO: Create document explaining the possible algorithms and add references> (3 weeks of work)
   
3. Allow to profile LOD weights: Sometimes the generated LOD with high reduction looks nice…except just a single vertex which messes up the whole mesh. This may be a bug in the algorithm. In that case you need to reduce fewer vertices? Well what if you could just fix that single vertex. The idea is to create a small sample in the SampleBrowser where the artist can select (or step by step reduce each) vertex and change the weight of it manually. This also helps debugging progressive mesh algorithm. (2 weeks of work)
4. Weighted outer wall: This would be an optional feature and it may not be related to all kind of meshes. When I have made a visual benchmarking system for LOD in worldforge, we have noticed, that buildings are reduced less than other models. This is caused by the fact, that the wall has two sides and there are static objects inside the building. The algorithm currently doesn’t care on what is visible from outside and what not. The idea is to detect the outer wall of the reduced mesh in a pass before processing the progressive mesh algorithm. Also You can set the strength in the range 0-1 on how much should this influence the output (0=off;1=keep outer wall only) This would drastically increase efficiency of meshes which has internal faces like buildings. I couldn't find an algorithm for this problem, but I have planned my own algorithm and I would like to implement it. <TODO: Create document explaining the algorithm> (4 weeks of work)
   
5. Allow to mix automatic and manual LOD: The idea is that you can reduce LOD1 by 50%, for LOD2 you use a manual mesh and for LOD3 you reduce the manual mesh by 50%. So it would make a hierarchy of LOD levels, which allows mixing automatic and manual mesh LOD levels. (1 weeks of work)
6. Create effective manual mesh: The idea is that you can use your favorite editor (like Blender) and restructure faces and remove vertices there, but you should not create new vertex positions! Then with a tool (maybe OgreMeshUpgrader or MeshMagick) you can bake it into the mesh as index buffer only LOD. (2 weeks of work)

Schedule
In the past 2 GSoC years I had less time in the first month caused by exams, but this year it is shifted a month and I will have time from the beginning to the end! Also I normally go to holiday for a week during the summer, but the date is not yet specified. I would suggest the following schedule:

• Now - June 17: Community Bonding period
  In the bonding period I have most of the time exams, so I will not have much time. (Currently I’m having less time too). I’m focusing on how to implement new features into Ogre. I will create a prototype for the outer wall detection algorithm. Create algorithm documentations on how everything works mathematically, what kind of advantages/disadvantages it has and discussing this with the mentor.
• June 17: Coding starts ***
• June 17 – June 24: Compress LOD levels (1 week)
  This just needs changes in the baking, but baking is separated between threaded and non-threaded implementation and both needs changes.
  I need to change ProgressiveMeshGenerator::bakeLods, ProgressiveMeshGenerator::PMTriangle, PMWorker::bakeLods()and PMGenRequest structure
• June 24-July 15: Take into account vertex normals (3 weeks)
  This needs 3 weeks, because it also needs some experimenting, because there are multiple solutions. I could just compare the dot product from source to destination, but it may look better if I count the overall angle of the vertex before and after the reduction.
  I need to change ProgressiveMeshGenerator::PMVertex, ProgressiveMeshGenerator::PMTriangle, ProgressiveMeshGenerator::computeEdgeCollapseCost.
• July 15 - July 29: Allow to profile LOD weights (2 weeks)
  Create ProgressiveMeshGenerator::setProfileData, where you can pass the custom weights based on vertex position. Creating a sample with an interface for profiling LOD and allow to export the mesh with the MeshSerializer. ?How to select the mesh?Cross platform file selector?
• July 29-August 5: Catch up delays or holiday (1 week)
  NOTE: I may go later on holiday and I may already start next task before Mid.
• August 2: Mid Term Evaluation ***
  At this point I should be ready with first 3 tasks.
• August 5-August 26: Weighted outer wall (2 weeks)
  This will be an optional pass before progressive mesh. It will be in a separated class. The goal is to calculate convex hull and do the appropriate calculations on the data. However before coding starts, I want to create a prototype of this, so that I can prepare for issues and make the schedule more stable.
• August 26-September 9: Weighted outer wall improvements (2 weeks)
  I will implement an optional feature to use few ray traces to improve approximation quality, but I will decide this based on the results and current progress/delays. I may find other ideas at that date to improve it.
• September 9-September 16: Allow to mix automatic and manual LOD. (1 week)
  This needs some Core changes in the LOD handling.
• September 16: Soft pencils down ***
• September 16-September 23: Clean code, improve documentation. (1 week)
• September 23: Firm pencils down ***
• September 23-October 7: Create effective manual mesh (2 weeks)
  This will be an after GSoC task for completeness. This is not related to the core, but to the tools.

Why I’m The Person For This Project
I was participating in GSoC 2011 and GSoC 2012 at Worldforge on Ogre related tasks. Both were success. I know Ogre3D quiet well. I switched the GSoC organization, because I always worked on Ogre3D there (but I still like to contribute to worldforge too ). I know the workflow of GSoC quiet well too. I'm proficient in C++ and experienced in the internals (compiler/linker/OS). I have experience in free and open-source development on Windows, Linux and OSX. I have experience in 3D geometry algorithms, 3D graphics and shaders too. I have developed the current progressive mesh algorithm in Ogre3D v1.9, so maybe I know it the best on what/why is written as it is.

[PhilipLB]

Nice.

With Hoppe, you mean this paper?
http://research.microsoft.com/en-us/um/ ... eshopt.pdf

What about this one?
http://www.open3dcity.org/uploads/media/mcd_vmv02.pdf

Especially because when implemented, I really could use the Quadratic Error Metrics in the Volume Component.

[sajty]

With Hoppe I mean quadratic error (QEM), which is used by Hoppe's algorithm. Sorry for confusing. QEM produces better output, but it needs to move/create vertices. If you don't move vertices, just collapse to the nearest vertex, then the reduced surfaces will be bumpy.
So the current implementation is not using QEM, instead it uses curvature to determine reduction order described here: http://dev.gameres.com/program/visual/3 ... uction.pdf

What about this one?
http://www.open3dcity.org/uploads/media/mcd_vmv02.pdf

This is only optimizing performance by degrading quality a bit. Based on my benchmarks only 10% of the time is spent in the heap insert/delete (heap = std::multimap) so optimizing that would be less then 10%. The old implementation was using vector lookup Also progressive mesh can run in background thread, so performance is not that important anymore.

[sajty]

I have created a prototype of the Outer wall detection algorithm.
It needs lot of improvements and it isn't meant for publication/merging, but it produces quiet nice results already!
changes: https://bitbucket.org/sajty/ogre/commit ... 66a64b4a2e

Here is an image showing the outside and inside of the building(Weighten outside 100% means outside is never reduced):


Here is an extreme reduction quality improvement comparison:


I will soon write a document on how this works.

[TheSHEEEP]

I really like the idea of this.
If the performance is good, it would be extremely helpful to many projects.

[spacegaier]

Congratulations! This proposal has been selected as one of our this year's GSoC projects!

Best of luck and happy coding !

Mentor: Murat Sari <wolmanfx>

[PhilipLB]

Yay, congratz.

[TheSHEEEP]

Congrats!

Now, go, go, go!

[sajty]

Thanks for the feedback all and congratulations to other accepted students too!

Here is a slide showing how the outside detection technique works:
http://sajty.elementfx.com/gsoc2013/Out ... ection.pdf
I'm open for ideas improving the technique.

[sajty]

First GSoC coding day is today!!

Today, I have tested changing the size and offset of an index buffer.
Here is a proof image, where I draw the 50% reduced sinbad's first and second half of the index buffer:


I have tested it on openGL and directX too.
I have also looked through the whole Ogre codebase for locations which are incompatible and I have found some problems.

HW instancing: This is only changing original index buffer and I will merge only generated LOD (LOD1+LOD2) and keep original mesh as it is.
If I would merge to original index buffer (LOD0+LOD1), then HW instancing would make problems based on my review.

Mesh Serializing: First day, First bug. The mesh serializer is not serializing the offset of an index buffer.
So If you would export mesh with offset and import it back, you would get garbage output.
Also in merged LOD, it would be enough to export every second buffer.
So mesh serializing needs changes.

In MeshSerializerImpl::readSubMesh this line is bad:

Code: Select all

sm->indexData->indexStart = 0;

Can I change the mesh file format?
What should I be aware of when changing it?

[holocronweaver]

I hope all your screenshots are going to be this hilarious. Those poor ogres!

[sajty]

I hope all your screenshots are going to be this hilarious

A real pirate has only one eyeball, so both Sinbads are real pirates.

Today, I have started implementing the Lod compression, but its not yet complete.
I have also fixed a segfault, which happens when you destroy the WorkQueue without initializing the idle thread.

[sajty]

Today I've got the core of the compression working.
However it still needs more testing.
The threaded version is still not ready too.
The generation time is the same (if not faster) so you don't get any disadvantages with this compression.
However I needed to keep the normal baking for uneven Lod count (when the last Lod level can't be merged) and I will provide an option to disable compression too.

[PhilipLB]

Oh, do I understand that right, that normal maps are generated on the fly for the less detailed LOD levels? That's a nice idea!

[sajty]

Oh, do I understand that right, that normal maps are generated on the fly for the less detailed LOD levels? That's a nice idea!

No, It has nothing to do with normal maps.
What I'm doing is merging 2 Lod index buffers and reuse shared triangles. This can produce up to 50% compression.
I will do some benchmarks later on how much compression it is in practice.

Edit: If you want to have lower resolution normal map, then you can resize the normal map texture. Ogre supports that, but it has really nothing to do with mesh LOD.

[PhilipLB]

That's true, if there is already a normalmap available, you don't need to generate one. The idea here is, if no normalmap is there, you generate one from the highest resolution model variant. But actually, that doesn't sound like a part of OGRE but like a part of the modelling program and the artist.

[sajty]

Hi!
The compression is fully working!
You can try it here: https://bitbucket.org/sajty/ogre/commit ... e585c61761
The only remaining problem is with exporting the mesh with mesh serializer.

[Zonder]

That's true, if there is already a normalmap available, you don't need to generate one. The idea here is, if no normalmap is there, you generate one from the highest resolution model variant. But actually, that doesn't sound like a part of OGRE but like a part of the modelling program and the artist.

I think in this case OGRE should handle it. As you said though if one is available always use that.

[scrawl]

That will not work at all for tiled textures. If anything, it should be an optional, off-by-default feature, but in my opinion it does belong into the modeling application, not Ogre.

[sajty]

Here is the roadmap for the next two weeks working on adding normals into the collapse cost.

Environment:
-First of all, If the mesh doesn't have vertex normals in buffer, then the current algorithm works ok and we don't need to change that.
-If the mesh has vertex normals, then self shadowing will make big artifacts, which I want to prevent.
-Corner case: A vertex may be multiple times in the vertex buffer and each may have different vertex normal. This may be the case on very sharp edges, non-manifold vertices, two sided plane edge. Solution for now is to average them if not equal. This should be rare though. Also we need to handle zero vectors and set it in a direction.
-Currently the face normals are determined from edges, because we are not storing the vertex normals. I will try using vertex normals for that. This will not change much, but it should give a small speedup.

Goal:
-Take into account normals: As my first attempt I will try to add the curvature difference of the source and destination normal.
-Other methods are to use Gaussian curvature or compare it to 360 degree rounded surface rule, but these need more calculations.
-This may need multiple iterations/experiments based on previous results.

[sajty]

I have implemented the first prototype, but for some reason it's not fixing the shadowing issue.
I will create a better debug interface to find out the issue.
Also the self-shadowing can't be perfect after reduction, because the triangles are restructured.

For example here we collapse the vertex in the middle toward the vertex on the right:

Lets assume, that the vertex color is the vertex normal's self-shadowing color in theory.
Then in the above image we have collapsed from red to red, which should be zero difference, but the output still differs.

[sajty]

As my 6th experiment I've got nice improvements to show!
It provides smoother transient for self-shadowing (the goal was to reach this). Forcing too much normals will degrade quality, but I found a nice balanced solution for this.
Also the original curvature based reduction's weakness is rounded surfaces, which can transform into flat surfaces step by step. So normally you get sharp edges. This experiment is also taking into account the normals in a way which tries to save rounded surfaces to smoothen self-shadowing.
Leaving sharp edges to the end makes superior mesh structure, therefore more vertices can be reduced.

In short, the algorithm is looping through the edges, which are moved from source vertex to target vertex during collapse. The cost of each edge is determined by the dot product difference before and after collapse multiplied by the length difference. It will compare the highest cost edge to the original collapse cost and the biggest cost will be used.

Here is an image of the big improvements:

[sajty]

I'm one week before schedule so I have some spare time to try out a QEM based reduction and compare it to the current implementation.
http://pdf.aminer.org/000/346/870/a_new ... ucture.pdf
QEM is the most popular reduction algorithm, so the results will be interesting.
I'm not sure if it will have better quality, but QEM is faster.

[PhilipLB]

Ou, please shout loud when you implemented the QEFs. I could use them, too.

[sajty]

But I'm using half edges, you will need different QEM algorithm for terrain.
However it will give you some hints for sure.