Determing the direction of face normals consistently?

Question

I'm a newbie to computer graphics so I apologize if some of my language is inexact or the question misses something basic.

Is it possible to calculate face normals correctly, given a list of vertices, and a list of faces like this:

v1: x_1, y_1, z_1
v2: x_2, y_2, z_2
...
v_n: x_n, y_n, z_n
f1: v1,v2,v3
f2: v4,v2,v5
...
f_m: v_j, v_k, v_l

Each x_i, y_i , z_i specifies the vertices position in 3d space (but isn't neccesarily a vector)

Each f_i contains the indices of the three vertices specifying it.

I understand that you can use the cross product of two sides of a face to get a normal, but the direction of that normal depends on the order and choice of sides (from what I understand).

Given this is the only data I have is it possible to correctly determine the direction of the normals? or is it possible to determine them consistently atleast? (all normals may be pointing in the wrong direction?)

Answer 1

In general there is no way to assign normal "consistently" all over a set of 3d faces... consider as an example the famous Möbius strip...

You will notice that if you start walking on it after one loop you get to the same point but on the opposite side. In other words this strip doesn't have two faces, but only one. If you build such a shape with a strip of triangles of course there's no way to assign normals in a consistent way and you'll necessarily end up having two adjacent triangles with normals pointing in opposite directions.

That said, if your collection of triangles is indeed orientable (i.e. there actually exist a consistent normal assignment) a solution is to start from one triangle and then propagate to neighbors like in a flood-fill algorithm. For example in Python it would look something like:

active = [triangles[0]]
oriented = set([triangles[0]])
while active:
    next_active = []
    for tri in active:
        for other in neighbors(tri):
            if other not in oriented:
                if not agree(tri, other):
                    flip(other)
                oriented.add(other)
                next_active.append(other)
    active = next_active

Answer 2

In CG its done by polygon winding rule. That means all the faces are defined so the points are in CW (or CCW) order when looked on the face directly. Then using cross product will lead to consistent normals.

However many meshes out there does not comply the winding rule (some faces are CW others CCW not all the same) and for those its a problem. There are two approaches I know of:

1. for simple shapes (not too much concave)

   the sign of dot product of your face_normal and face_center-cube_center will tell you if the normal points inside or outside of the object.

   

   if ( dot( face_normal , face_center-cube_center ) >= 0.0 ) normal_points_out
   

   You can even use any point of face instead of the face center too. Anyway for more complex concave shapes this will not work correctly.

2. test if point above face is inside or not

   simply displace center of face by some small distance (not too big) in normal direction and then test if the point is inside polygonal mesh or not:

   

   if ( !inside( face_center+0.001*face_normal ) ) normal_points_out
   

   to check if point is inside or not you can use hit test.

However if the normal is used just for lighting computations then its usage is usually inside a dot product. So we can use its abs value instead and that will solve all lighting problems regardless of the normal side. For example:

output_color = face_color * abs(dot(face_normal,light_direction))

some gfx apis have implemented this already (look for double sided materials or normals, turning them on usually use the abs value ...) For example in OpenGL:

glLightModeli(GL_LIGHT_MODEL_TWO_SIDE, GL_TRUE);