Lack of mesh smoothing

[robmar]

I tried to use MeshManipulator::recalculatenormals() as it mentions smoothing, and even calculate a weight for normal smoothing, but after having to dig through the subject at some time cost has become clear that it never worked!!!

Most of routines to handle mesh smoothing through adjusting normals, looks very complicated with esoteric names of functions like "SpatialSearch" etc.

So I thought about this, and on most mesh surfaces there are just 5 interconnected triangles, so how hard can this be?

So I wrote a routine to scan thro the vertices looking for up to 5 near identical positions, I then sum their normals and normalize, and keep matching. I also added a dot producto test of the normals to exclude any with a 30º or greater difference, so that the shape of the model and sharp edges is not deformed, and it worked perfectly.

I wonder why, since this has been available in 3D computing since 1998 in DirectX, that this never got fixed in Irrlicht?

[Mel]

I faced a similar issue building a 3DS loader (although i admit, i never displayed anything with it) Also, 5 interconnected triangles isn't necesarily true, really.

(I hope it displays correctly...)

Recalculating normals is actually a cumulative process, the results of the normal calculations can be added, you just need to normalize each time you add a new normal, and that should do it . You need to build an model which holds the adjacencies of the triangles, but i advise you to use some memory management (memory pools) or the process of reserving/releasing memory for the adjacencies list can slow down the whole algorithm a lot.

[devsh]

Recalculating normals is actually a cumulative process, the results of the normal calculations can be added, you just need to normalize each time you add a new normal,

That will just make your algorithm order dependant and give more weight to the normals added at the end, just keep adding the normals and normalize at the end.

You need to build an model which holds the adjacencies of the triangles, but i advise you to use some memory management (memory pools) or the process of reserving/releasing memory for the adjacencies list can slow down the whole algorithm a lot.

Or you can just initialize each vertex normal to 0, and blast throught the index list 3 at a time, calculating the plane normal of each triangle and atomically accumulate the normal back at the triangle's vertices. Then do a final pass to normalize the accumulated normals. Hell you can even weigh the normals by triangle area

Nice, easy, no memory allocation and order independent.

P.S. Its trivial to do on CPU and on GPU with 2 pass compute shaders.

[devsh]

On a second thought that simple algo would not work if you needed to duplicate your vertices because of UVs or something like that.

However you could build a redirect list from every vertex to the first vertex with same position and smooth group, just like in mesh-welding (the kind that would ignore the normals).

Then accumulate your normals at the first vertex using the redirects as described above.
In the final pass (normalization), simply gather the final normalized normal from the first vertex from each non-primary vertex at the same position and smooth-group.

[robmar]

Yes, as yu say, its not always up to 5 triangles with interconnected points, on high points 8 or even more can connect, but I found that on most models its up to 5, and up to 8 on more curved models with peaks, such as character models.
I accumulate and add as you say, scanning through the vertices, but there is another routine that works twice as fast, using a "spatial search", which somehow reuses previous searches. My technique is to maintain an elimination list, and as I search forward finding matches, mark them as smoothed, so my outer search loop passes its current position to the inner loop, which ignore previously matched vertices.
But, I need to look at this spatial sort because its so fast and for the life of me I can't see how they can do that!

[CuteAlien]

Simple spatial search - use a map (std::map or irr::core::map) and compare vertices with some epsilon (vector3df::equals with a small non-zero tolerance value). It's not perfect as when there are for example 3 vertices close together and the first 2 are outside the tolerance and the 3rd in between inside tolerance to the others, then the result is kinda random. But a good mesh shouldn't have such cases anyway, so it'll work in general.

[devsh]

You'd have to compare more than the position attribute to not merge stuff that shoudn't be merged, such as UV coords.

Generally speaking you'd get best performance (O(n) ) if you implemented a good hash function for multidimensional voxel grids (3D pos + 2D uv + whatever else), then used std::unordered_set to find your candidate similar vertices with 2^K (where K is number of dimensions) hash lookups per vertex. The trick is finding a good hash function that has the desired property of not giving you nonsense collisions, simply making a string out of the vertex bytes and hashing that won't cut it.

An O(n^2) approach with no adjacency lists is totally appropriate, as this sort of stuff should be precomputed (either with your model editor such as Blender or your own preprocessing tool) and not done at runtime, even if the cost is O(n).

[CuteAlien]

No, we already have smoothing which regards UV's in Irrlicht (by simply checking for all faces connected to a vertex). The problem is that this is sometimes not what you want. You might still want to smooth adjacent faces even if they use different uv's. That's what robmar's function seems to do. And yeah, map or hashmap, whatever works fast enough.

[robmar]

The problem is speed smoothing large meshes, each and every vertex must be compared with all others to find those vertices sharing the same space with similar face positions, within < 50 degrees perhaps, and thats a lot of checking.
Keeping a table of checked vertices helps, and the double loop reduces with each vertex checked off, but its still a very slow process when there are tens of thousands of vertices. I have to look at Assimps spatial search, because that seems to work really fast.I´ll post my routine, which works perfectly and respects sharp angles on the mesh.

[robmar]

I´m posting a smoothing routine I added to CMeshManipulator class that works nicely with 3DS models and others.
It scans all normals and blends them together so that surface normals are not perpendicular to each triangle, resulting in smoothing.
It also maintains correct lighting on sharp edges, but its not as fast as the smoother in Assimp, and I don't know why... yet

Its in Code Snippets.