Jump to content

Auto LOD - Quadratic Error Decimation


RaananW
 Share

Recommended Posts

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 by raananw
Link to comment
Share on other sites

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...

Link to comment
Share on other sites

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. 

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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 :-)

Link to comment
Share on other sites

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!

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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'),

Link to comment
Share on other sites

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?

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...