From: levine@well.sf.ca.us (Ron Levine)
Subject: Re: Polygon normal direction?
Organization: Whole Earth 'Lectronic Link
Date: Wed, 2 Sep 1992 01:09:02 GMT

In article <1992Sep1.054514.2272@jyu.fi> ap@jyu.fi (Patric Aalto) writes:
>Hi!
>
>Sorry for this FAQ-like question, but I didn't find a reference to it in
>the FAQ, nor in any of the graphics books and articles I have.
>
>I have a set of 3D objects, consisting of polygons (triangles). I would
>like to render these objects effectively on my 486. In order to do that,
>I need to do backface elimination, among other things. The problem is,
>the polygon vertices are in no particular order (about 50% are clockwise,
>50% anti-clockwise, I could quess). I can easily calculate normal vectors
>for the polygons, but I would need some algorithm to select the correct
>direction to this normal. What is the correct algorithm?
>
>I tried to use common sense, and coded an algorithm that sends a ray from
>a point in the middle of the polygon to the direction of the normal. I
>then checked this ray against all the other polygons, and decided that
>if the number of intersections is odd, I must negate the normal direction.
>This method works somewhat (after this around 80% of the normals point
>to the correct direction). But this obviously is not the final solution.
>
>Could you please help me with this, or point me to a book/article that
>would be helpfull?
>
>Thanks in advance,
>
>Patrick Aalto
>ap@tukki.jyu.fi
>

Your question is a good one, and not in any FAQ that I know of.  But its 
best answer depends on the exact nature of your "objects", which you don't 
make precisely clear.   In any case, I don't agree that your proposed 
algorithm makes "common sense". 

Before addressing your main question, I would like to point out that it is 
important to understand that "clockwise" and "anti-clockwise" have no intrinsic 
meaning in 3-space.  That is, the "clockwise" ordering for the vertices of a 
plane polygon in 3-space is defined only with respect to a definite choice for 
the normal vector direction.  

The key concept needed to address your question is "oriented polygon".   An 
ordered set of coplanar vertices in 3-space defines an oriented polygon.  As 
you already understand, an oriented polygon has a well-defined normal vector 
direction, conventionally specified by a right hand rule.  Any cyclic 
permutation of a given ordered set of vertices defines the same oriented 
polygon.  The reverse ordering of a given ordered set of vertices, or any 
cyclic permutation of the reverse ordering, defines the same polygon, 
considered as a point set, but with the opposite orientation; it is 
considered a different oriented polygon and its corresponding unit normal 
vector is the negative of the unit normal vector of the given oriented 
polygon.  Any other permutation of a given ordered set of vertices defines, in 
general, a different polygon, a different point set. 
 
In addition to "oriented polygon", we have the concept of "oriented edge".  An 
edge of a polygon is a line segment joining an adjacent pair of its vertices.  
The edge is oriented by specifying the two vertices in a definite order.  
Clearly, an orientation of a polygon induces an orientation on each of its 
edges, and reversing the orientation of the polygon reverses the induced 
orientation of each of its edges. 

Now, to address your question:

There is, of course, no canonical way to select an orientation for an isolated 
polygon in 3-space.  Rather, your goal is to select orientations for all of 
the polygons together in a coherent way.  To say what this means, we have to 
be a little more explicit about the nature of your "objects". 

Let me suppose that each of your "objects" is defined by a set of simple 
(i.e. non-self-intersecting) polygons that form a well-behaved connected 
polyhedral surface.  That is, the simple polygons meet pairwise in common 
edges, each edge belongs to at most two polygons, and any two polygons in an 
object belong to a chain of pairwise adjacent polygons. The polygons of a 
polyhedral surface are usually called "faces". 
 
It is probably also the case, although you don't state it explicitly, that 
your "objects" are polyhedral solids.   The boundary surface of a solid is 
closed, which means that every edge must belong to exactly two faces.  I do 
not assume that your surfaces are closed in what follows, but will mention 
some important consequences that follow when they are closed.

Now, if a selection of normal vector directions for all the faces of a 
connected polyhedral surface is to have any usefulness at all, it must be 
coherent.  This means that the normal vectors of any pair of adjacent faces 
must be consistent, that is, they must point to the "same side" of the 
dihedral surface formed by the two adjacent faces.  I won't try to give a 
formal proof, but it should be easy to convince yourself that an adjacent pair 
of oriented faces is oriented consistently if the two face orientations induce 
opposite orientations on their common edge. 

Now we have the tools to describe the correct algorithm for orienting the 
faces of a connected polyhedral surface.  First, you need some basis for 
orienting at least one of the faces.  I'll come back to this later.  Given one 
oriented face, check each of its edges.  I've assumed that each edge belongs 
to at most one other face.  For each edge, find the other face, if any, 
that contains that edge and orient it so that it induces the opposite 
orientation on the common edge.  Then repeat the process for each of the 
remaining edges of each of the faces meeting the first face, and so on.  
Because the surface is connected, you will eventually reach all of its faces.  
However, during this process, while trying to consistently orient all the 
faces meeting the current face, you are practically certain to encounter faces 
that have been previously encountered and oriented in the process.  What 
happens if the orientation induced on this face by the current oriented face 
does not agree with its previous orientation?  If this happens, it is 
impossible to coherently orient the faces of the surface.  You have an example 
of what is called a non-orientable surface. 

Non-orientable surfaces exist.  The Moebius strip is a non-closed non-
orientable surface and the Klein bottle is a closed non-orientable surface.  I 
don't know any examples of closed non-orientable surfaces in 3-space that are 
not self-intersecting.   I believe that any polyhedral surface that is the 
boundary surface of a solid is orientable.  I don't know your method of 
generating the objects in your application, but if it is sensible, the chances 
are you will not have to deal with non-orientability.

Now let's return to the question of selecting an orientation of an initial 
polygon in the algorithm, and so an orientation of the surface.  Just as there 
is no canonical way to select a proper orientation of an isolated face, there 
is no intrinsic way to select a proper orientation of a non-closed orientable 
surface--to distinguish a "top side" from a "bottom side".  You need some 
external criterion.  However, for a bounded closed orientable surface, a 
surface that is the boundary surface of a solid of finite extent (as I suspect 
you are dealing with), there is a natural distinction between an "inside" and 
an "outside".  Such a surface divides the 3-space into two pieces; the outside 
is the part of space that runs out to infinity.  It is common practice to 
orient such a surface so that the normal vector points from the inside towards 
the outside.   However, an algorithm which could determine this direction in 
the most general case would be very complex.   Hopefully, your application 
adds special conditions which will make it easy to find at least one face for 
which it is easy to distinguish the inside from the outside. 

The algorithm I've just described is appropriate if your model data structure 
is some sort of face-vertex representation, in which you have a single array 
of vertices (with floating point coordinates) and represent the faces by lists 
of indices into the vertex array.  If you represent each polygon by an 
independent list of vertex representation, then you have a real messy problem 
in determining the adjacent faces.

I've never had to code up this algorithm in the extensive geometric modeling 
work I've done, because I always take care to coherently orient the faces in 
the process of generating the model objects.  Unfortunately, not all existing 
libraries of 3D model objects take care to do this.  

One final point.  I've mentioned several times that I think you are modeling 
solids and so your surface objects are closed.  If this is not the case then 
you should think twice before using back face elimination.  For closed 
polyhedral surfaces, back faces are hidden, so can be eliminated, but non-
closed surfaces may well have back faces that are visible.