In <1pscti$aqe@travis.csd.harris.com> srp@travis.csd.harris.com (Stephen Pietrowicz) writes:
>How do you go about orienting all normals in the same direction, given a 
>set of points, edges and faces?

This algorithm works well for me:

Algorithm to attempt to find outward-facing normals:
---------------------------------------------------
First, mark all faces as UNKNOWN.

Then create an edge dictionary that allows you to find all of the
faces sharing a given edge (where an edge is two integers representing
the two shared vertices).

Pick an arbitrary face and mark it COUNTER_CLOCKWISE.  Using the edge
dictionary, orient all surrounding faces based on the orientation of
this face.  And recurse for all surrounding faces, consistently
orienting the entire surface.

Find the average of the vertices in this surface.  Using that point,
calculate a volume measurement, taking into account the face's
orientation.  If the volume turns out to be positive, assume the faces
are oriented correctly.  If it is negative, reverse their orientations
(mark them CLOCKWISE).

If any faces are still UNKNOWN after this, choose another face
and go through the algorithm again.

At the end, faces marked CLOCKWISE must have their indices reversed
before facet normals are found.

(Note: if you are running on Silicon Graphics machines and buy the
IRIS Inventor 3D toolkit developers package you have the source to
this algorithm-- see /usr/src/Inventor/tools/ivnorm/.  If you're
not... sorry, I can't give out the source, and even if I could it
relies heavily on Inventor).
--
--gavin     (gavin@sgi.com,  (415)390-1024)



In article <1pscti$aqe@travis.csd.harris.com> srp@travis.csd.harris.com (Stephen Pietrowicz) writes:
>...
>How do you go about orienting all normals in the same direction, given a 
>set of points, edges and faces? 

Look for edge inconsistencies.  Consider two vertices, p and q, which
are connected by at least one edge.

If (p,q) is an edge, then (q,p) should *not* appear.  

If *both* (p,q) and (q,p) appear as edges, then the surface "flips" when
you travel across that edge.  This is bad.  

Assuming (warning...warning...warning) that you have an otherwise
acceptable surface - you can pick an edge, any edge, and traverse the
surface enforcing consistency with that edge.  

    0) pick an edge (p,q), and mark it as "OK"
    1) for each face, F, containing this edge (if more than 2, oops)
       make sure that all edges in F are consistent (i.e., the Face
       should be [(p,q),(q,r),(r,s),(s,t),(t,p)]).  Flip those which
       are wrong. Mark all of the edges in F as "OK",
       and add them to a queue (check for duplicates, and especially
       inconsistencies - don't let the queue have both (p,q) and (q,p)). 
    2) remove an edge from the queue, and go to 1).

If a *marked* edge is discovered to be inconsistent, then you lose.

If step 1) finds more than one face sharing a particular edge, then you
lose. 
    
Otherwise, when done, all of the edges will be consistent.  Which means
that all of the surface normals will either point IN or OUT.  Deciding
which way is OUT is left as an exercise...



-- 
Kenneth Sloan                   Computer and Information Sciences
sloan@cis.uab.edu               University of Alabama at Birmingham
(205) 934-2213                  115A Campbell Hall, UAB Station 
(205) 934-5473 FAX              Birmingham, AL 35294-1170