IsoSurface Mesh Simplifier

User Code & Projects
1

Since like me, most people playing around with isosurfaces are going to stumble on the issue of level of detail, I stumbled upon probably the quickest and most usable mesh simplifier after numerous attempts.

This class doesn’t take UV co-ords into account because my isosurface uses world co-ordinates, but the links in the header point you to code that does implement them. You are free to impose that burden upon yourself should you so desire.

It only simplifies vertices, indexes and normals - perfect for an isosurface.

The algorithm is relatively fast if you don’t generate complex normals - and almost double if you do - I guess some things just take time. The following results were achieved on a 6 year old 4.5GHZ Intel i7. The mesh is a 128x128x128 isosurface shown in the image below.

Simplify: 44418 / 88836 50% removed in 218 ms
Simplify: 35534 / 88836 60% removed in 186 ms
Simplify: 17766 / 88836 80% removed in 224 ms
Simplify: 8882 / 88836 90% removed in 223 ms

Any advice on improvement would be greatly appreciated. Sharing is caring :heart:

Useage:

Mesh mesh = myMesh; // a jMonkey mesh.
float desiredPercent = 0.25f // 25% of the original tris.
int aggression = 12; // between 4 and 20 is recommended. Lower = better distribution / more expense.
boolean expensiveNorms = true; // calculate per-vertex norms or just use the face normal.
int desiredTris = mesh.getTriangleCount / 3; // a third.

SimplifyMesh simplifer = new SimplifyMesh(mesh);

Mesh newMesh = simplifier.simplify(desiredPercent, aggression, expensiveNorms);

or

Mesh newMesh = simplifier.simplify(desiredTris, aggression, expensiveNorms);

12 Likes
2

Do you have an overview of the approach you ended up with or is the code obvious if I look through it?

3

Sure - It uses Quadric Error Metrics - which is nothing new to the maths world, but it works faster because it avoids sorting by using a predetermined incremental threshold instead. I believe the original method calculated a cost (which is an exhaustive iterative procedure in itself) to determine which edge to remove, and removed the edge with the least cost (sorting), whereas this method just removes the edge if the cost is lower than the threshold, so ignores the cost calculation entirely. The result is slightly “uglier” than the former method, but is offset by speed. In practice it’s actually not that bad at all - especially since the whole point is reducing meshes for the purposes of detail over distance (we’re not going to be up close to them anyway).

The threshold is increased per iteration, and the aggression level increases the threshold per iteration. So the lower the aggression, the lower the threshold will increase per iteration, hence more iterations, the better the quality. Or inversely if the aggression is higher, the threshold will increase quicker per iteration, and as such less iterations are necessary to achieve the desired count, and the “uglier” it is.

described as:

final double threshold = 0.000000001d * Math.pow(iteration + 3d, agressiveness);

In reality a lower aggression level tends leave more vertices in the detailed areas and focuses more on flat areas, and a higher aggression level tends to “average out” the removal distribution across the whole mesh. Which makes sense if you think about it.

A picture says a thousand words and all that story:

Low Aggression:

High Aggression:

Some reading if you’re interested:

Surface Simplification Using Quadric Error Metrics:

Mesh Simplification

There are implementations I looked through that do implement sorting - along with exhaustive documentation (Paul Burke seems to have his hand in almost everything I read lately) - and I did find this link in particular very educational and comes with source code, too.

The link died many moons ago. All hail the wayback machine.

https://web.archive.org/web/20110822015336/http://jsomers.com/vipm_demo/meshsimp.html

4 Likes
4

Can this method also work for simplifying regular 3d model mesh ?

1 Like
5

Er… Yes and I’m not sure. My implementation does not include UV mapping, but it wouldn’t take very long to put them in (I didnt need them). I’m not sure about mesh weights and stuff, though. Animated meshes might be a bit out of my reach.

2 Likes
6

In those pictures, it’s only simplifying the right half, right?

1 Like
7

Correct. I put them together like that to make sure they joined properly in all situations.

1 Like
8

Makes sense.

I guess the algorithm always considers the boundary edges “important” edges and so doesn’t reduce them. It’s a nice feature that prevents gaps.

For normal height-map sort of terrain data, dropping skirts is sufficient for hiding the gaps but it doesn’t work for general iso-surfaces with overhangs and stuff… so it’s neat to see a solution that covers that. I’m not sure I’ve seen an iso-surface mesh reducer like this before.

9

Is SimplifyMesh.java still available? It seems to be truncated here, and the link to GitHub is broken :frowning:

10

Sorry about that. The link has been updated with a fresh working link.

11

I seem to have missed this post the first time around…

This I love:

        for (Triangle face : triangles) {

            final int ia = face.v[0];
            final int ib = face.v[1];
            final int ic = face.v[2];

            final Vector3f e1 = verts.get(ia).p.subtract(verts.get(ib).p);
            final Vector3f e2 = verts.get(ic).p.subtract(verts.get(ib).p);
            final Vector3f no = e2.cross(e1); //cross( e1, e2 );

            norms[ia].addLocal(no);
            norms[ib].addLocal(no);
            norms[ic].addLocal(no);

        }

        for (Vector3f norm : norms) {
            norm.normalizeLocal();
        }

…smoothed averaged normals if the verts are shared, while independently uniform per face if verts are not shared. And no mess from keeping track of neighbor faces!

I might have to steal this part.

2 Likes
12

Really great tool!
Is it possible to also reduce the number of border vertices? It looks like they are never discarded, as can be seen in the simplify method (// border check). But if I remove this check, whole triangles are cut out (which is not exactly what I want). I just want to remove border vertices (simplify triangles) which are (nearly) coplanar.

13

Ok, found a solution, just use the border check from the original method Fast-Quadric-Mesh-Simplification/Simplify.h at master · sp4cerat/Fast-Quadric-Mesh-Simplification · GitHub

2 Likes
14

My implementation was primarily designed for terrain. You wouldn’t want the edges to be manipulated in that case so they join regardless of how simplified they become.

Glad you found a solution.

2 Likes
15

Excellent job! Thanks a lot. Do you think is it easy to adjust this algorithm for using JavaFX meshes? I could not find any algorithms for JavaFX, I am planning to use this one with some modifications for JavaFX library.

1 Like
16

Wow, it looks great! I have transplanted a version of c/c++ before, through jni binding, optimized from 1790668 triangles to 537200, which is more than 70%. On my computer, the time is only 15-20 milliseconds. :slightly_smiling_face:
You can have a look:simplify

1599635181(1)
1599635181(1)1475×1038 139 KB

17

c/c++ source:sqlim

18

This isn’t just a mesh simplifier. It ignores edges - which is important for terrain because the edges will still line up if you use this as a LOD control.

In the end it’s just vertex modification so it will work with anything that deals with vertices.

3 Likes
19

Hi again I also cannot render JME mesh as only triangles as you shared the photos above. Mesh.Mode.Lines, Mesh.Mode.Triangles vs does not produce it like that.

20

Correct. It can only simplify a mesh made of triangles.