0
$\begingroup$

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

$\endgroup$

2 Answers 2

0
$\begingroup$

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;
}
$\endgroup$
4
  • $\begingroup$ Is there an example / reference implementation of the hash function mentioned, either in python or c++. Thanks for sharing the idea $\endgroup$
    – uk2797
    Feb 3 at 6:39
  • $\begingroup$ How is your mesh stored? Do the triangles share the vertices? Or does each triangle have its own vertices? (flat shading VS gouraud shading) $\endgroup$
    – Thomas
    Feb 3 at 9:09
  • $\begingroup$ @uk2797 havent tested the code... But I'll do when I'm at home =) $\endgroup$
    – Thomas
    Feb 3 at 17:11
  • $\begingroup$ In my case, triangles share the vertices. My initial problem statement of mesh reconstruction changed to reconstructing the entire 3D object. So I am exploring voxel based methods for this new problem statement. Thanks for the code, But I haven't had the chance to try this code. This has been an exciting stuff to learn as a engineer. And I am looking forward to your results $\endgroup$
    – uk2797
    Feb 8 at 1:14
0
$\begingroup$

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.


Method 1:

This is more of a quick check but is fairly effective in practice. Given a mesh with averaged normals, for each triangle compute the faceted normal and compute the cos of the angle between the averaged normal and the faceted normal using the dot product. A positive result indicates clockwise, a negative result indicates counter clockwise, and zero indicates that the two normals are very close to each other. Keeping a count of clockwise and counter clockwise where one of the two should be zero depending on the winding order of the mesh.

If all the triangles have the same winding order then the mesh can be accepted as being consistent and "outward" is defined as all faces having either clock wise or counter clock wise orientation depending on the handedness of the mesh.

The rational behind this method is that most normal vectors are computed as averaged values. So if you have a mesh that is largely valid then the averaged normal will very likely face the correct direction.


Method 2:

Another 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.

$\endgroup$
3
  • $\begingroup$ This had some stupid mistakes that I fixed. $\endgroup$
    – pmw1234
    Feb 2 at 14:54
  • $\begingroup$ Thanks, Can you please explain what do you refer as the given normal here ? "Then compute the dot product of the given normal and our computed vector (which is a faceted normal)" $\endgroup$
    – uk2797
    Feb 3 at 6:47
  • $\begingroup$ Most Mesh data comes with precomputed normals, that is what I was referring to as the given normal. $\endgroup$
    – pmw1234
    Feb 3 at 10:24

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.