Progressive Mesh Buffer / Mesh simplification

Announce new projects or updates of Irrlicht Engine related tools, games, and applications.
Also check the Wiki
RdR
Competition winner
Posts: 273
Joined: Tue Mar 29, 2011 2:58 pm
Contact:

Progressive Mesh Buffer / Mesh simplification

Post by RdR »

Update 01-05-2012 Added optimization and is 4-5x faster (thanks to wing64)

Hello,

Already shared a screenshot of this project in Screenshot of the Month, and here it is!

With this class you can simplify existing meshes by contracting / collapsing edges.
This is very usefull for creating LOD meshes on the fly, instead of creating all meshes in your 3D editor.

Already using this in TANK@WAR 1.2 to create less detailed models of the tanks for the LOD system.

Features
- Contract / Collapse edges
- Texture support
- Bump/normal support
- Algorithms:
* Random
* Shortest
* Melax
* Quadric

How to use

Code: Select all

 
// Get original mesh
scene::IMesh* mesh = smgr->getMesh("media/cow.b3d");
 
// Create ProgressiveMeshBuffer
ProgressiveMeshBuffer::SimplificationAlgorithm algorithm = scene::ProgressiveMeshBuffer::MELAX;
scene::ProgressiveMeshBuffer* pmb = new scene::ProgressiveMeshBuffer(mesh ->getMeshBuffer(0), algorithm);
 
// Contract / collapse 50 edges
pmb->contract(50);
 
// Get new mesh buffer
scene::IMeshBuffer* mb = pmb->getCurrentMeshBuffer();
 
Screenshot
Image
Image

Download (Demo + Source)
Download
IrrExt mirror

TODO
- Optimize


I hope people want to optimize this further (and share it ofcourse) because I don't have the time anymore :(

Because it's still quite slow for big meshes. (See bunny model in demo)

NOTE: models are not mine, and can't remember where I got them from tho :oops:
Last edited by RdR on Tue May 01, 2012 4:09 pm, edited 3 times in total.
hendu
Posts: 2600
Joined: Sat Dec 18, 2010 12:53 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by hendu »

The bunny is free to use from the Stanford library.
ACE247
Posts: 704
Joined: Tue Mar 16, 2010 12:31 am

Re: Progressive Mesh Buffer / Mesh simplification

Post by ACE247 »

Super work! :) Definetly going to use this in my level editor, to auto generate lod meshes for repeating scene geometry.
Mel
Competition winner
Posts: 2292
Joined: Wed May 07, 2008 11:40 am
Location: Granada, Spain

Re: Progressive Mesh Buffer / Mesh simplification

Post by Mel »

That is definately great :) It should be added also the support for skinned meshes, and the work would be complete. Awesome.
"There is nothing truly useless, it always serves as a bad example". Arthur A. Schmitt
RdR
Competition winner
Posts: 273
Joined: Tue Mar 29, 2011 2:58 pm
Contact:

Re: Progressive Mesh Buffer / Mesh simplification

Post by RdR »

Mel wrote:That is definately great :) It should be added also the support for skinned meshes, and the work would be complete. Awesome.
ACE247 wrote:Super work! :) Definetly going to use this in my level editor, to auto generate lod meshes for repeating scene geometry.
Thanks!

Updated source:
- Fixed unique edge bug
- Fixed minor leaks ( forgot to delete/drop() some stuff -_- )

Added this project to IrrExt
http://irrext.svn.sourceforge.net/viewv ... eshBuffer/
mongoose7
Posts: 1227
Joined: Wed Apr 06, 2011 12:13 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by mongoose7 »

I played around with it, but when you try to reduce the number of vertices by a reasonable amount (say 50%), holes start appearing in the mesh. I'm wondering if it would be worth biasing towards curvature as the large flat areas are generally not simplified.
RdR
Competition winner
Posts: 273
Joined: Tue Mar 29, 2011 2:58 pm
Contact:

Re: Progressive Mesh Buffer / Mesh simplification

Post by RdR »

mongoose7 wrote:I played around with it, but when you try to reduce the number of vertices by a reasonable amount (say 50%), holes start appearing in the mesh. I'm wondering if it would be worth biasing towards curvature as the large flat areas are generally not simplified.
Its depending on the algorithm & mesh you are using. Creating all LOD meshes by hand is always better visually, but takes a lot of extra time.
If you want to use them on your own models, have to test a bit which algorithm is best for your needs.

Maybe you can create another algorithm? Or edit/improve an existing one. :D
mongoose7
Posts: 1227
Joined: Wed Apr 06, 2011 12:13 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by mongoose7 »

Well ... I don't think the algorithm is stable. It tends to pull all vertices towards the areas of greater complexity.

The idea that I was going to try to follow through on was, if a vertex is common to four quads (I was going to work with quad meshes), and the four quads share the four edges meeting at the vertex, then discard the vertex.

I haven't started working on it, but only one vertex out of nine is removed, and it may throw up situations that would have to be investigated. But this is the approach I will take.
RdR
Competition winner
Posts: 273
Joined: Tue Mar 29, 2011 2:58 pm
Contact:

Re: Progressive Mesh Buffer / Mesh simplification

Post by RdR »

mongoose7 wrote:Well ... I don't think the algorithm is stable. It tends to pull all vertices towards the areas of greater complexity.
Which algorithm are you talking about?
And could be there's still a bug in one of the algorithms.
mongoose7
Posts: 1227
Joined: Wed Apr 06, 2011 12:13 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by mongoose7 »

All algorithms are similar - move one vertex on an edge to meet the vertex at the other end and then delete the moved vertex. All the algorithms except "random" target short edges, with a bias for high curvature. Therefore, they all pull vertices towards areas of complexity. They create models made of stalactites and stalacmites.
mongoose7
Posts: 1227
Joined: Wed Apr 06, 2011 12:13 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by mongoose7 »

If anyone is interested in debugging the code, you can load the dwarf model from Irrlicht (by changing the source) and, well, you won't see anything because this model is 100 times bigger than the car, cow and bunny, so pull back and you should see the axe. Now type 'z' to remove an edge and you will see a two-triangle hole in the blade. I think that is probably not Stan's fault because, if you continue to type 'z', the blade will get smaller and smaller, even though Stan's method should preserve shape.
Lonesome Ducky
Competition winner
Posts: 1123
Joined: Sun Jun 10, 2007 11:14 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by Lonesome Ducky »

The hole has to do (I'm betting) with the fact that Irrlicht duplicates vertices along UV seams (this is necessary for proper rendering). So we perceive there being a single vertex along the UV seams, but in reality there are two or more duplicates to make sure that the UV mapping behaves correctly. The code (once again, I'm betting) treats these multiple vertices as different ones, so collapses them into different areas, creating the holes. When in reality, these vertices should be treated as the same one because, for almost all intents and purposes, they ARE the same vertex. This is the exact problem I ran into when I was working on a LOD scene node, and it was a pain in the butt to fix. If that doesn't make any sense, I'll try to come up with a more clear description
mongoose7
Posts: 1227
Joined: Wed Apr 06, 2011 12:13 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by mongoose7 »

I understand what you are saying. But it is the model loaders that create the mesh buffers and I didn't think Irrlicht touched those mesh buffers (could create animation problems), and I didn't think the model loaders did anything like that, so I'm wondering when it could occur. But if it is true, this would certainly cause holes to appear.

The code calls

Code: Select all

mesh = smgr->getMeshManipulator()->createMeshWelded(mesh);
but removing this line has no effect on the axe.
Lonesome Ducky
Competition winner
Posts: 1123
Joined: Sun Jun 10, 2007 11:14 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by Lonesome Ducky »

createMeshWelded only removes EXACT duplicate vertices, not similar vertices with different UVs so that won't fix the problem. I'll try coming up with a more detailed explanation and an example
Lonesome Ducky
Competition winner
Posts: 1123
Joined: Sun Jun 10, 2007 11:14 pm

Re: Progressive Mesh Buffer / Mesh simplification

Post by Lonesome Ducky »

For this example, we're going to create a simple pyramid mesh:
Image

To begin with, this pyramid has no UV's assigned to it. And, as expected, the vertex count of the mesh is 5. Now let's give it some UV's.
Image

Now that we've got our UV's assigned, let's go ahead and select our top vertex and see where it is on the UV map.
ImageImage

As you can see, the top vertex has two UV coordinates. A problem arises her in that a vertex may only have a single UV coordinate. So what do we do to fix this? We make 2 vertices with the exact same position but different UV coordinates! Let's go ahead and selected another vertex and see where its uv coordinates are.
ImageImage

This vertex has three UV coordinates! And, to repeat, since each vertex can only store one, it must be split into 3 vertices with the same position but differing UV's. Now, if what I'm saying is actually true, we'd expect Irrlicht to return a vertex count of 12. And it does!

If you're still skeptical, I uploaded a zip file of the pyramid mesh with and without UV's for you to test here.

One way of looking at it is that any triangles that are connected on the uv map will be connected on the mesh.
Post Reply