0
$\begingroup$

I am using c++. I have to find vertex normal in mesh. The mesh is triangle soup. The winding order is inconsistent. I know that it is the sum of all faces normals arround the vertex. But I don't know how to set correct direction of faces (triangles) normals. I want to know for algorythm for this.

$\endgroup$
2
  • $\begingroup$ Do you mean that you have a mesh with inconsistent winding order on the triangles and you need to standardize it? $\endgroup$ Sep 3, 2022 at 22:17
  • $\begingroup$ @Nathan Reed. Yes I mean this $\endgroup$ Sep 4, 2022 at 9:24

1 Answer 1

4
$\begingroup$

A very simple, but computationally expensive, way to do this is to pick a triangle, preferably one that you know has the winding you want.

Then search every triangle in the soup for triangles that share an edge with the chosen triangle.

For every triangle that shares an edge, check that its winding is the same as the chosen triangle. The winding is the same iff the ordering of the vertices on the shared edge are the same are the opposite. If the ordering is different swap the order of any two vertices on the found triangle.

Remove found triangles from the original set as they are discovered.

Wash rinse repeat.

It is usually easiest to implement this algorithm using indexed triangles, it is straight forward to index a set of vertices. (1:iterate over every vertex and assign a new index to only those that are unique, then 2:iterate over every triangle and assign an index from the index pool created in step 1.)

One nice thing about this algorithm is there are extra "whistle while you work" things that can be done to check the integrity of the polyhedron.

  1. Keep a count of edges that don't share an edge with any other triangle. At the end if this number is non-zero then the polyhedron is not "water tight". This can be a good starting point for making the polyhedron water tight.

  2. It is possible to have triangles that are not connected to the original chosen triangle, meaning the soup is either inconsistent, or defines multiple polyhedrons.

Lastly, this algorithm is so easy to code up it can be used to compare other more advance techniques against.

$\endgroup$
2
  • 2
    $\begingroup$ An easy enhancement is to build a hash table mapping edges (as ordered pairs of vertex IDs) to triangles, so given an edge it's easy to find the other triangle that shares it, rather than searching through the whole mesh in a quadratic fashion. $\endgroup$ Sep 4, 2022 at 15:57
  • $\begingroup$ The winding is the same iff the ordering of the vertices on the shared edge are different, though. $\endgroup$ Sep 7, 2022 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.