Newsgroups: comp.graphics
Path: cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!fs7.ece.cmu.edu!europa.eng.gtefsd.com!gatech!willis1.cis.uab.edu!sloan
From: sloan@cis.uab.edu (Kenneth Sloan)
Subject: Re: Surface normal orientations
Message-ID: <1993Apr6.175117.1848@cis.uab.edu>
Organization: CIS, University of Alabama at Birmingham
References: <1pscti$aqe@travis.csd.harris.com>
Date: Tue, 6 Apr 1993 17:51:17 GMT
Lines: 42

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
