how to check if all the faces face outward

Question

Situation: I am using Open3D python,The mesh generation algorithm ( like ball pivot, poisson reconstruction ) are dependent on normal direction. I used estimate_normals and orient_normals_consistent_tangent_plane methods on the point cloud to make sure vertex normals are facing outward. After generating the mesh, i want to check if the face normals are facing outward. If not, I need to flip it.

**Help **: how to represent "outward" condition for a face normal, mathematically. I can get face normal from mesh.triangle_normals.

**context **: I am rookie engineer, so Any links to theory or examples would help me understand. open3d solution is also welcome :)

I looked into open3d documentation to check for existing methods. But no methods exist.

Answer 1

I've run into a similar issue with my own tesselations and wrote about it in a blog here and code here. Here's the algorithm I devised to fix the issue. The two requirements of this algorithm are that you know the correct direction of one of the triangles in the mesh and that neighboring triangles share a common vertex.

The algorithm is as follows:

1. We start by building a lookup table to map each triangle to all of its corresponding neighbors. We can be lazy here and define two triangles as “neighbors” by whether or not the two triangles share a common vertex.
2. We then initialize a queue with the triangle we want to use as our basis for the “forward” direction and begin processing.
3. To process an item on our queue, we iterate through each of its neighbors. If a neighbor is a triangle that we’ve already processed, we skip it. If the triangle is one that we haven’t processed completely, we compute its normal direction and its inverted normal direction.
4. If the dot product between a triangle’s normal and its neighbor’s normal is less than the dot product between a triangle’s normal and its neighbor’s inverted normal, then we need to flip the neighbor’s vertices to change its facing direction.
5. For each neighbor we process, we add them to the queue to be processed next.
6. We continue to run until the queue is empty.

The resulting mesh should have all the triangles facing the correct direction!

Answer 2

The best strategy depends on the properties of your mesh. Some definitions:

• Manifold: Faces connect only at edges. Each edge connects at most two faces. (That is, there's no "T-junction" edges.
• Connected: You can reach any face from any other face, by a path along connected faces. (That is, the mesh isn't in multiple pieces.)
• Closed: Each edge connects two faces. (That is, there are no "boundary edges".)
• Orientable: It is possible to consistently wind each face, such that faces connected by an edge have consistent winding. A Klein bottle is an example of a non-orientable mesh.)

First, if your mesh is not orientable, you're screwed. Non-orientable meshes are not produced by mesh generation algorithms, though. Similarly, if your mesh is not manifold, these methods won't work; orientability is only really defined for manifold meshes. So the rest of this refers to orientable manifold meshes.

If your mesh is not connected, you can still use these methods, by splitting them into multiple meshes (one for each connected set of faces) and processing them one at a time. That doesn't give you consistent orientation of cavities, but I suspect that's not something you're concerned about.

To orient a connected orientable manifold mesh, you first need to identify or make a face which is correctly oriented, then flood that orientation to all other faces.

If that mesh is also closed, the easiest way to do this is to identify the extremal vertex in some direction, and make sure that a face which is on that vertex is wound such that its normal points in that direction. For instance, find the vertex with the greatest X coordinate; take a face which uses that vertex; calculate the face normal with its current winding; if that normal has a negative X component, flip the winding. If your mesh is not closed then you can still take this approach but it's more of a heuristic than a dependable rule.

That face becomes your "seed" face. Make it the first (and so far only) element of a set of faces, called the "open set".

Now you do a graph traversal. In each iteration, you'll take one face off the open set, add it to the closed set, and process it. Depending on how your open set is stored this will be either a depth-first or a breadth-first traversal. The remainder of this description is of that graph traversal.

To process a face, first add it to the "closed set" [no relation to whether the mesh is a closed mesh]. Now examine all faces it shares an edge with. If a face has an edge with vertices (in counterclockwise order) a,b, then the other face (and it's manifold, so there should be only one at most) with an edge with those vertices should have them in the order b,a. If the other face has them in the order a,b, flip its winding. After you examine and maybe flip each of those faces, add them to the open set, unless they were already in the closed set. (If they were in the closed set, and you flipped them, that means your mesh is not orientable and you should exit with an error. If you are sure your mesh is orientable and you want to make this procedure more efficient, don't check the winding of neighbors if they're on the closed set already.)

Eventually you'll run out of faces in the open set, and all faces will have been added to the closed set. At that point, your mesh is consistently oriented.