Bug in PMP::compute_vertex_normal()

[lrineau]

Issue Details

There is a bug in PMP::compute_vertex_normal()

For a vertex of a surface mesh, it computes the normalized normals of all incident faces, and compute the unweighted mean of those normalized normals. ... That is wrong!

Steps to easily see the bug:

• Load the OFF file demo/Polyhedron/data/cube.off (that is a simple triangulated unit cube: 8 vertices, 12 faces), in the polyhedron demo,
• Use "create a point set from vertices". That will display the normals.
• For each vertex that is incident to four faces, you will see that the normal is wrong : all vertex normals of the 8 vertices of the cube should be proportional to the diagonal vectors (±1, ±1, ±1).

There are several methods to compute vertex normals of a mesh, and the unweighted mean is clearly always wrong (but if the mesh is very isotropic). See details our three different methods in this blog. The page points to articles, one comparing six different methods to compute normals. The best one seems to weight the mean with the angles of the face around the vertex.

Environment

• CGAL version: current master branch (pre-CGAL-4.10-beta1, commit 82286eb)

[lrineau]

And by the way, the name of that function should be construct_vertex_normal(), to comply with our naming convention!

[janetournois]

The blog @lrineau mentions above gives quite a few solutions that should be considered to make a decision.
Computing the normal at vertex v amounts to computing a weighted sum of normals n_i to the facets f_i that are incident to v in the mesh.

The question we have to answer is : which weight do we choose?

1. until now, the weight is 1
2. in [1], the weight is the angle of f_i at v. It requires to compute an arccos, but it seems to be a good option in terms of quality of the result
3. in [2], the weight is the sine of the angle of f_i at v, divided by the product of the lengths of the edges of f_i incident to v. It does not require any trigonometry, but it requires a sqrt.
4. in [3], the weight is area(f_i). It requires no trigonometry, but it requires a sqrt.
5. in PR WIP : fix PMP::compute_vertex_normal #2065, I implemented a variant of (2), that uses the sin(angle) instead of the angle. It is cheaper to compute, and should behave similarly.

Now, we have two options

• choose our favorite solution among the ones listed above
• implement more than one, and add a named parameter to PMP::compute_vertex_normal() to choose the one we want to be used. Note MeshLab does implement options 1 to 4.

So, what do you think?

[1] G. Thurmer, C. A. Wuthrich, "Computing vertex normals from polygonal facets"
Journal of Graphics Tools, 3 1998
[2] N. Max, "Weights for Computing Vertex Normals from Facet Normals", Journal of Graphics Tools, 4(2) (1999)
[3] S. Jin, R.R. Lewis, D. West, "A comparison of algorithms for vertex normal computations", The Visual Computer, 2005 - Springer