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 :)

Answer 1

When having a simple continuous triangle mesh which is closed, each edge of a triangle is used twice. So two triangles share one edge. Each face (Triangle) consists of 3 vertices. Here the winding order is from major importance.

You can hash the edges by a hash key which must be the same for v0-v1 and v1-v0.

When iterating all triangles add the three edges to the hashtable. There you need to store the order of the two vertices so that you know if it is v0-v1 or v1-v0.

During this iteration you will have half of the time an empty hash slot. There you add the edge. Else you check winding order. This time it need to be the opposite winding order. Otherwise you have two neighboring faces with different face direction.

EDIT:

#include <iostream>
#include <vector>
#include <map>

struct Vertex
{
public:

    bool operator > (const Vertex& otherVertex) const
    {
        if (positionX > otherVertex.positionX)
        {
            return true;
        }
        else if (positionX == otherVertex.positionX)
        {
            if (positionY > otherVertex.positionY)
            {
                return true;
            }
            else if (positionY == otherVertex.positionY)
            {
                if (positionZ > otherVertex.positionZ)
                {
                    return true;
                }
            }
        }       
        return false;
    }

    bool operator == (const Vertex& otherVertex) const
    {
        return positionX == otherVertex.positionX &&
            positionY == otherVertex.positionY &&
            positionZ == otherVertex.positionZ;
    }

    float positionX;
    float positionY;
    float positionZ;
};

struct Face
{
public:
    Vertex vertex0;
    Vertex vertex1;
    Vertex vertex2;
};

/**
Doesn't matter which vertex is the first of the two. This is important!
**/
struct EdgeHashKey
{
public:
    static EdgeHashKey generateHashKey(const Vertex& vertex0, const Vertex& vertex1)
    {
        EdgeHashKey result;
        if (vertex0 > vertex1)
        {
            result.lowerVertex = vertex1;
            result.higherVertex = vertex0;
        }
        else
        {
            result.lowerVertex = vertex0;
            result.higherVertex = vertex1;
        }
        return result;
    }

    bool operator < (const EdgeHashKey& otherHashKey) const
    {
        if (lowerVertex < otherHashKey.lowerVertex)
        {
            return true;
        }
        if (lowerVertex == otherHashKey.lowerVertex)
        {
            if (higherVertex < otherHashKey.higherVertex)
            {
                return true;
            }
        }
        return false;
    }

private:
    Vertex lowerVertex;
    Vertex higherVertex;
};

std::vector<Face> loadMesh()
{
    //in here you can bring your mesh into the correct format (struct Vertex and struct Face)
    std::vector<Face> result;
    //...
    return result;
}

bool faceDirectionTest(const std::vector<Face>& mesh)
{
    std::map<EdgeHashKey, bool> hashTable; //the edge is the hashkey. The boolian: true => first lowerVertex, secound higherVertex. false => first higherVertex, secound lowerVertex

    for (std::vector<Face>::const_iterator it = mesh.cbegin(); it != mesh.cend(); ++it)
    {
        //Step1: generate hashkey for all three edges
        //Also get the additional boolian value for all three edges
        EdgeHashKey hashKeyV01 = EdgeHashKey::generateHashKey(it->vertex0, it->vertex1);
        EdgeHashKey hashKeyV12 = EdgeHashKey::generateHashKey(it->vertex1, it->vertex2);
        EdgeHashKey hashKeyV20 = EdgeHashKey::generateHashKey(it->vertex2, it->vertex0);
        bool directionV01 = it->vertex0 > it->vertex1;
        bool directionV12 = it->vertex1 > it->vertex2;
        bool directionV20 = it->vertex2 > it->vertex0;

        //Step2: get the hash slot:
        std::map<EdgeHashKey, bool>::iterator hashSlotV01 = hashTable.find(hashKeyV01);
        std::map<EdgeHashKey, bool>::iterator hashSlotV12 = hashTable.find(hashKeyV12);
        std::map<EdgeHashKey, bool>::iterator hashSlotV20 = hashTable.find(hashKeyV20);


        ///Edge 01
        //per check there are two possibilitiers: 1 => this edge is not in the list: store it. 2 => this edge is already in the list: check it!
        if (hashSlotV01 == hashTable.cend()) //not in hash table, so we add it
        {
            hashTable[hashKeyV01] = directionV01;
        }
        else //this edge is inside the hash table, so we check the winding order
        {
            if (hashSlotV01->second == directionV01) // two neighboring faces have different face direction!!!
            {
                return false;
            }
        }

        ///Edge 12
        //per check there are two possibilitiers: 1 => this edge is not in the list: store it. 2 => this edge is already in the list: check it!
        if (hashSlotV12 == hashTable.cend()) //not in hash table, so we add it
        {
            hashTable[hashKeyV12] = directionV12;
        }
        else //this edge is inside the hash table, so we check the winding order
        {
            if (hashSlotV12->second == directionV12) // two neighboring faces have different face direction!!!
            {
                return false;
            }
        }

        ///Edge 20
        //per check there are two possibilitiers: 1 => this edge is not in the list: store it. 2 => this edge is already in the list: check it!
        if (hashSlotV20 == hashTable.cend()) //not in hash table, so we add it
        {
            hashTable[hashKeyV20] = directionV20;
        }
        else //this edge is inside the hash table, so we check the winding order
        {
            if (hashSlotV20->second == directionV20) // two neighboring faces have different face direction!!!
            {
                return false;
            }
        }
    }
    return true;
}

Answer 2

A simple way to determine mesh orientation is to compute the winding order of each triangle. Where winding order is either clockwise (CW) or counter clockwise (CCW).

Swapping the winding order of a triangle swaps the direction of the normal for that triangle. So checking that normal vectors are facing "outward" is a matter of verifying that all triangles are wound in the same direction.

Keep in mind that the coordinate system also plays a role in handedness. Determining that the mesh is wound consistently is a better indicator of a valid mesh since sometimes a mesh is intentionally wound in the opposite direction so that we only see the "inside" of the faces.

I well specified system will have all these details in it so that the facing can be determined to be consistent with that system. This way we aren't throwing a random mesh at a random system to do coin flips on the problem.

There are many ways to go about checking this.

---

One way to check winding without doing any computations is to check that the edge of any connected triangles have the vertices ordered in the opposite direction. If any of the edges have the same order the connected triangle has opposite winding and can be fixed by swapping the order of the vertices. This method is very reliable and very easy to implement. For example if we have triangle ABC where AB, BC, and CA are the edges then the connected triangles should have edges BA, BC, and CA.

Implementation:

The property "connected triangles with the same winding have edges with the opposite order" makes this particularly easy to implement since this means that if edge AB is repeated anywhere then there is a problem. IE AB is unique in the mesh. Implementation is just a matter of picking your favorite data structure and using insert unique. That's it we're done. Non-unique means there is a problem, reverse the winding of that triangle and continue. Done.

---

More Rigorous solutions

Some interesting information on the subject can be found by searching for the shoelace formula and greene's algorithm. Also search for shoelace in 3D. Search for curve orientation (here is a wikipidia page on it) can be useful too.

A much more rigorous solution can be created by generating edge information... pick a single triangle determine its orientation, then use its edges to find and check the orientation of neighboring triangles. Save orientation with the edges and compare new triangles against that orientation. Repeat until all triangles are traversed.