Auto LOD - Quadratic Error Decimation

[RaananW]

Howdy folks,

 

I have ported a wonderful simplification algorithm written in c to babylonJS.

It is based on http://www.cs.cmu.edu/afs/cs.cmu.edu/user/garland/www/Papers/quadric2.pdf and http://voxels.blogspot.de/2014/05/quadric-mesh-simplification-with-source.html .

What can you do with it? It can be used to automatically create LOD objects for meshes (if the user has time for that) directly in the browser.

 

It is surprisingly fast - it is reducing ca. 130000 triangles to 65000 in less than 5 seconds on my good ol' laptop.

 

Example can be seen here - http://babylonjsexperiments.raananweber.com/?rate=0.5 , the fractal object (generated using meshlab) contains ca. 131000 triangles. Wait a few seconds for it to load and decimate. The object on the right is the original, on the left is the reduced.

The rate can be change in the URL. At 0.3 it is still relativly hard to find the difference. At 0.1 it is very clear. But this is exactly what's needed for LOD.

 

At the moment I am not analyzing the UVs (meshlab doesn't generate them as well), this would be the next step. Making it Async is also on the todo list :-)

 

Edit - Preview site changed, check my following post about the new async implementation.

Edited January 14, 2015 by raananw

[joshcamas]

wow! This is something that lots of us have been waiting for!

Excellent work, can't wait for more of it!

[GameMonetize]

Wooooot. we need a mesh.simplify function now

[RaananW]

working on it :-)

[reddozen]

could this be made to write the decimated mesh to a new babylon file etc for future loading instead of constantly recreating it? Maybe some flag for saving if not existing.

[RaananW]

It is currently writing the position, normal and UV Buffer to a new mesh and not changing the old one, I think this is what you meant. Or did I misunderstand you?

The idea is to make auto-asyns-LOD after loading a mesh (thus saving bandwidth and server space :-) )

[reddozen]

New mesh, yes, but I was referring to a potential option of saving the new mesh to a new babylon file, but if the new mesh could be created async to the render loop without impacting frame rate etc, then this would be even more amazing. I wouldn't have to waste the time making 3~4 LOD meshes for all my objects, and we have thousands of meshes for our game...

[RaananW]

Would be interesting to see how well it performs.

When i finish the async version that plays nicely with textures I'll test and publish the results here.

[reddozen]

I'm looking forward to it... I have a pretty massive scene that would push it pretty hard and it's about 1/6 of what we want it to be.

[RaananW]

So, reached another demo level.

 

The decimation now runs completely async and doesn't affect the rendering (well, not as much as you would expect!). LOD levels can be calculated parallel or one after the other. The decrease in FPS is not that serious (going down to 50-55 with not-so-complex meshes, down to 40 with more complex meshes. 

There is still work to do in regards to UV textures, but other than that it works.

 

http://babylonjsexperiments.raananweber.com/

 

the url accepts the following parameters:

 

mesh - the mesh to load, selection between dude (babylon's famous dude, LOD will run on all meshes), danceMoves (single textured mesh. not dancing, sorry), fractal (the one from the last example, a complex mesh with ca. 130000 triangles). default is danceMoves

levels - the number of levels to generate (5 is default, no max). 5 will generate 100%, 80%, 60%, 40%,20% . You can guess what comes out of 4. Or 10 :-)

parallel - should all LOD levels of all meshes be calculated parallel or one after the other. true or false, default false.

offset - the distance offset to set between each level of LOD. default is 100. Good level would be 50-100 to be able to actually see what the decimation does.

 

Links to try:

 

http://babylonjsexperiments.raananweber.com/?parallel=true&levels=8&mesh=dude

http://babylonjsexperiments.raananweber.com/?parallel=false&levels=8&mesh=fractal

http://babylonjsexperiments.raananweber.com/?parallel=true&levels=8&mesh=danceMoves&offset=50

 

Pay attention to the total meshes rising after loading and the active vertices changes while zooming in or out. This will be a great indication as to what it actually does. 

[GameMonetize]

Hey THIS IS AWESOME!!!!! Can't wait for the PR (You will save me a lot of time )

[joshcamas]

Amazing! I think this feature will most useful for terrain and fancy decorations in the background and such! So cool!

[RaananW]

I will soon test it on an entire scene and post the results here. Would be interesting to see what it does to the Train scene :-)

 

@Deltakosh - PR is coming soon! :-) Just working out the fine details. Do you think a new Decimation/Simplification module be in order? Or just integrate it in (Abstract)Mesh? A new module might come in handy if more types of simplification will be implemented. And then afterwards integrate it in the SceneOptimizer?

There are many small things to be made before integrating it. Best example are sub meshes - they should be recalculated, which is an almost impossible job (at the current state), as the decimation "rearranges" the indices and vertices. I'll think of something. Another thing that i actually tried solving yesterday was bones and skeleton. This, just like the submeshes, will be influenced quite a lot from decimation. 

 

If anyone is interested - the code is in my github (together with the new head-tracking experiment I made, but this is for another post :-) ) here - https://github.com/raananw/BabylonJS-Experiments

[GameMonetize]

First version could be limited to mesh with just one sub-mesh

 

If possible I prefer keeping it in the mesh or abstract mesh file but if you think it worth moving it to a separate file this is your call. The main goal to keep in mind is simplicity for users. 

[RaananW]

Since it is quite a lot of code, I think separating it would make sense. I can put the code in a different file in the Mesh directory and add the Mesh class a "simplify" function that will accept a map of quality and distance (together with other needed parameters). No real need of uber-complicating the process you are right :-)

Will work on the easiest way for the developer to use it and send you a PR when I am done.

[GameMonetize]

Sounds good. do not forget to update these files with the new file:

https://github.com/BabylonJS/Babylon.js/blob/master/Tools/Gulp/gulpfile.js

https://github.com/BabylonJS/Babylon.js/blob/master/Tools/BuildOurOwnBabylonJS/BuildOurOwnBabylonJS/babylonJS.xml

 

 

Thank you for your contribution!

[dbawel]

RaananW,

 

Very useful! I used this to test evaluation time on vertex weight maps today, and it saved me considerable time optimizing poly count local to skeleton bones - specifically joint areas. If you think you'll continue development and provide a gui for loading, hiding, and unhiding - models, assets, and scene elements, I'm sure this would become a regularly used tool by developers.  I know I would link directly to this.  Please let the community know if you plan to add addtional features and to keep this online and active.

 

Thanks! 

 

DBawel

[RaananW]

Hi,

 

I can keep this alive and add functionality, if you think it will benefit someone.

At the moment I am working on integrating it into babylon (a simplification method). When i finish that, I am probably going to continue playing with decimation (other types maybe), but I can also extend the tool's functionality. I have already implemented something similar to Scene/Object loading in the material editor, shouldn't be too hard adding it here.

If you ever want to give me a list of functions you  think will be helpful (apart from those that you wrote), I can try finding the time to implement them. All open sourced for the community :-)

[Seyren]

Thank you so much!, i'm looking foward to it!

 

Just had a question about the meshes being displayed on the example, where are the other LOD meshes stored at?, since we can see each example can have like 9 meshes for example, assuming they are not constantly calculated all the time.

 

I'm curious about this because if i ever refresh the webpage again would this mean the 9 meshes are calculated again or they are somewhere stored in my cache or even in the webpage? I hope i was clear with this question

 

Keep it up, i'm totally loving it!

[RaananW]

Hi Seyren,

 

the meshes are calculated ad hoc and stored at the LOD Array of the mesh after the decimation process. each time the page is reloaded your browser is recalculating them, but once they are calculated they stay in RAM until the page is closed (or until they are disposed).

 

Would be interesting to see if the LODs can be stored in the cache much like the other resources (if the manifest allows it). Haven't thought about it! Will ad that to the ToDo list.

[RaananW]

Pull request submitted - https://github.com/BabylonJS/Babylon.js/pull/366 . Mesh has a "simplify" function, I will write a short tutorial after the merge, if needed. Technically all needed is this :

mesh.simplify([{ quality: 0.9, distance: 25 }, { quality: 0.3, distance: 50 }]);

further parameters are also available (parallel processing etc'),

[Dad72]

Great!

[reddozen]

Awesome man!

[Dad72]

Hi,

I can not find the tutorial on the wiki? Maybe he is still ongoing?

[RaananW]

The tutorial is here - https://github.com/BabylonJS/Babylon.js/wiki/In-Browser-Mesh-simplification-(Auto-LOD)

There is a small bug that i needed to fix (I tried adding support for meshes with Color Vertex Data, which cause the others to... not work correctly :-) ), I just sent a pull request with a fix.

Wait before testing the demos. Next time the babylon.js file of the editor will be updated (after the pull request merge) It will work. I will then extend the demos to Height Maps and the Skull object.

I will update here when it is all there and working. 

 

The link to the tutorial doesn't work for some reason. Try searching LOD in the Wiki's search field. Let me know if you find it.

@Deltakosh, I can't edit the tutorial anymore, is it intended?