From ksbooth@watcgl.waterloo.edu Sat Apr 29 22:30:40 1989
Path: leah!csd4.milw.wisc.edu!uxc!iuvax!watmath!watcgl!ksbooth
From: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Newsgroups: comp.graphics
Subject: Re: Computational geometry
Message-ID: <9455@watcgl.waterloo.edu>
Date: 30 Apr 89 02:30:40 GMT
References: <2053@incas.UUCP> <5397@cs.utexas.edu>
Reply-To: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Organization: U. of Waterloo, Ontario
Lines: 69

In article <5397@cs.utexas.edu> atc@cs.utexas.edu (Alvin T. Campbell III) writes:
>Now for the method.  Assume that we have a polygon with n 
>vertices, numbered v1, v2, ..., vn.  First, we find the vertex,
>vtop, with the largest y-coordinate.  The angle of the polygon
>at this vertex is guaranteed to be convex.

No.  This is a common mistake.  The "top" vertex may be co-linear with
the previous and next vertices.  Then the cross product that this
algorithm calculates becomes zero.  If the original data had no
co-linear vertices, floating-point operations used in the various
transformations could result in co-linear vertices.  Any transformation
to integer-based coordinates runs this risk.

For the application here (winding numbers) the algorithm can be fixed
by just looking for a vertex of maximum y with a predecessor having a
lower y value.  But of course this presumes that all of the vertices
have "correct" coordinates (i.e., that they have not been mangled by
floating-point transformations).

There have been many (too many to repeat) postings about this in this
newsgroup.  Computational geometry problems are deceptively simple to
state.  The solutions are often quite tricky, and extremely tricky if
all of the vagaries of floating-point representation are taken into
account.

Aside:  A similar algorithm is often presented for computing the normal
to a polygon (this is in fact what the cross product gives).  It fails
for the cases above.  Newell's formula (you can find it in one of the
appendices of Newman & Sproull's text, second edition) gives a much
more robust version of this technique.  This is more a less a
paraphrase of the version in N&S taken from a recent midterm exam.

| Newell's  formula  for  determining  surface  normals of a planar
| 
| polygon is given by
| 
|           n
|        a= > (y -y   )(z +z   )
|          k=0  k  k+1   k  k+1
| 
|           n
|        b= > (z -z   )(x +x   )
|          k=0  k  k+1   k  k+1
| 
|           n
|        c= > (x -x   )(y +y   )
|          k=0  k  k+1   k  k+1
| 
| In  these  equations, the planar polygon is defined by n vertices
| 
| whose coordinates are (x ,y ,z ), with k ranging from 0 to n-1.
|                         k  k  k
| 
| The subscript k+1 is evaluted modulo n.  The vector (a,b,c) is
| 
| perpendicular to the surface.

You can derive Newell's formula from the formula for a cross product
and induction on n, the number of vertices (for n=3, Newell's formula
IS the cross product).

The advantage of Newell's formula is that it is relatively insensitive
to perturbations in the coordinate values, since it effectively takes a
weighted average of all the cross products you might have computed.

The sign of c will give the orientation of the polygon (which is the
application on the midterm question -- determining when to cull
back-facing polygons).  If a, b, and c are subsequently normalized, the
true surface normal is obtained.