Progressive Mesh Buffer / Mesh simplification

[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



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

[hendu]

The bunny is free to use from the Stanford library.

[ACE247]

Super work! Definetly going to use this in my level editor, to auto generate lod meshes for repeating scene geometry.

[Mel]

That is definately great It should be added also the support for skinned meshes, and the work would be complete. Awesome.

[RdR]

That is definately great It should be added also the support for skinned meshes, and the work would be complete. Awesome.

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]

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]

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.

[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]

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]

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]

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]

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]

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]

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]

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


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.


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.


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.


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.