NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/graphics/9360

Text File | 1992-09-01 | 9.0 KB | 160 lines

Newsgroups: comp.graphics
Path: sparky!uunet!elroy.jpl.nasa.gov!ames!pacbell.com!well!levine
From: [e-mail] (Ron Levine)
Subject: Re: Polygon normal direction?
Message-ID: <[e-mail]>
Sender: [e-mail]
Organization: Whole Earth 'Lectronic Link
References: <[e-mail]>
Date: Wed, 2 Sep 1992 01:09:02 GMT
Lines: 148

In article <[e-mail]> [e-mail] (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
>[e-mail]
>

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.