graphics - 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