4

No duplicate of Most efficient algorithm to calculate vertex normals from set of triangles for Gouraud shading, as the edge-detection issue is not discussed.

How to computationally calculate normals for every vertex in a triangulated geometry, to be used in a Gouraud shader for a nice display, but with keeping track of edges? Is there a free, fast and performant standard solution for this?

I have been assigned the above mentioned task to fix a routine that produces visible artefacts. The normals should be input data to a simple Gouraud shader to "smoothen" the displayed geometry at coherent face. The routine should also be able to find edges so that they could be used by some other part of the software later on and not be "smoothened over".

The data is read from .stl files that do not contain any normal information, so all face normals must be calculated using the triangles' coordinates.

This is how the geometry looks without interpolation:

enter image description here

This is what the interpolation algorithm does so far:

enter image description here

The rounded plains look quite well, but the interpolation gravely fails at places where the found edge next to a flat surface is not strong enough to trigger the edge-detection algorithm, but also not weak enough to not be visible. The consequence is a misplaced normal that is propagated through the whole triangle(s).

I wonder if there is a standard solution for this, as this problem should occur quite often when working with this type of geometry. And even if there isn't, does anyone of you know common problems with this task and how to avoid them to get some decent results?

Any help would be much appreciated!

Edit: On the algorithm: The edge detection is not just about the triangle normal. Please consider the following example (the problem is essentially the same in 3D):

Triangle normal angle edge detection

All vertices share the same angle, i.e. 30°. (The angles are not exactly correct, but you get the idea...) However, only the outer two of them should be recognised as an edge, so there has to be another measure relevant for this question. So far, I have tried a triangle's

  1. circumcircle radius
  2. longest edge
  3. GTS triangle quality measure

that can modify the "minimum angle" at which two triangles are considered to share an edge. The longest edge method looks most promising (although far from perfect), but I think there is still something I overlooked...

Community
  • 1
  • 1
Brokenmind
  • 41
  • 3
  • What do you mean by edge "detection"? Is it that if 2 triangles that share an edge have surface normals that are different enough (e.g. small enough dot product) there is deemed to be a "hard edge" between them, otherwise not? – j_random_hacker Jun 04 '14 at 04:16
  • In any case, I think what you need to do is to look at the "hard" edges around a given vertex v in clockwise order and consider them to partition the triangles touching v into 1 or more parts, each consisting of a "path" of triangles in which adjacent triangles in the path share a "soft" edge. Then for each part in the partition you need to calculate a separate vertex normal for v, and use it for Gouraud-shading that part. This works if there are no hard edges incident on v, or if there are 2 or more -- the only problem case is if there's exactly 1, and then I don't know what should be done. – j_random_hacker Jun 04 '14 at 04:23
  • @j_random_hacker ->first comment: That's right, but unfortunately, the decision whether they share a "hard" edge is not only up to the normal, but also to the dimension(s) of the triangles. And ->second comment, that's exactly where the problem is. Now that I can post images, I will elaborate on what I did so far, maybe the problem will become more clear. – Brokenmind Jun 04 '14 at 07:12
  • Have you tried the distance to the edge's opposite vertex? – Nico Schertler Jun 04 '14 at 08:25

1 Answers1

0

There is a publicly available publication about this coming from Cal-Tech, in a form of a technical report, called "Discrete Differential-Geometry Operators for Triangulated 2-Manifolds".

The algorithms proposed there propose

a unified derivation that ensures accuracy and tight error bounds, leading to simple formulae that are straightforward to implement.

In the report, the algorithms are used for curvature calculations, but the curvature calculation involves an accurate mean curvature normal calculation. This information enables you to incorporate feature edge detection - the authors have used it for that purpose for feature detection on noisy meshes. Also, the mean curvature normal can be then used for shading.

tmaric
  • 5,347
  • 4
  • 42
  • 75