Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!clyde.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!apple!usc!cs.utexas.edu!tut.cis.ohio-state.edu!att!bellcore!uunet!brunix!jfh
From: jfh@cs.brown.edu (John Forbes Hughes)
Newsgroups: comp.graphics
Subject: Re: Plane Equation using Newell's method
Message-ID: <60827@brunix.UUCP>
Date: 7 Jan 91 05:09:21 GMT
References: <1991Jan3.163452.27481@cs.mcgill.ca>
Sender: news@brunix.UUCP
Reply-To: jfh@cs.brown.edu (John Forbes Hughes)
Distribution: na
Organization: Brown University Department of Computer Science
Lines: 93

In article <1991Jan3.163452.27481@cs.mcgill.ca> baer@cs.mcgill.ca (Lawrence BAER) writes:
>Given n not quite planar points meant to define a plane in 3-D, Newman and
>Sproull (2nd ed., Appendix II, p.499 I believe) define Newell's method for 
>calculating the plane equation coefficients (ax +by +cz +d = 0):
>
>   Let the coordinates of the ith point be stored in X[i],Y[i],Z[i]. Then
>   a=sum[1..n]{(Y[i]-Y[(i+1)mod n])(Z[i]+Z[(i+1)mod n])}
>   b=sum[1..n]{(Z[i]-Z[(i+1)mod n])(X[i]+X[(i+1)mod n])}
>   c=sum[1..n]{(X[i]-Z[(i+1)mod n])(Y[i]+Y[(i+1)mod n])}
>
>   and d is obtained by requiring one of the points to lie on the plane.
>
>I am looking for an explanation or proof of reasonableness of Newell's
>method i.e. where does it come from.  A reference would be great.
>
>Thanks in advance,
>
>Larry Baer
>School of Computer Science
>McGill University
>e-mail: baer@cs.mcgill.ca

Sounding like a broken record, I can recommend "Computer Graphics: Principles
and Practice," by Foley, van Dam, Feiner, and me; this is discussed both in the
section on surfaces and (indirectly) in the Appendix on Math for Computer
Graphics. But the underlying idea is far more interesting. Although Newell
might reasonably be credited with its reinvention for the world of computer
graphics, the idea was originally due to the mathematician Plucker (with an
umlaut over the "u"), sometime in the 1700s, I think. His notion was that a
k-dimensional plane P in n-space is determined by the areas (or really
"measures") of the projection of the unit cube of P onto all the k-dimensional
principal subspaces. Thus a line in 3-space is detemined by knowing how the unit
line segment in the line projects to the three axes, and a plane in 4-space is
determined by the projections of the unit square onto the 6 basic planes: XY,
XZ, YZ, XW, YW, ZW. 
  In the particular case you are asking about, you are taking a polygon, rather
than a unit square, but the results will be the same, scaled up by the area
of the polygon. You are "determining" the plane by computing the planar area of
the projected polygon onto each of the three coordinate planes. [Actually, you
are getting the *signed* area, but that's a technicality--it's what you really
wanted anyhow]. 
  Why does the formula give you the signed area of the projection? Well, let's
look at the formula for "c": it involves only the X and Y coordinates of the
points, so it's pretty clearly a property of the XY-plane projection of the
polygon. {your formula is wrong, by the way--the "Z" should be an "X"}
If you look at it carefully, you find that it's the sum of a bunch of signed
areas of triangles from the origin (0,0) to the points of the projected
polygon. These triangles, when added and subtracted, actually give the area of
the polygon. You can "see" this by drawing the triangles in XOR mode, which
makes a nifty polygon drawing routine... (by the way, the formulas should all
have a .5 in front, but that makes no difference in the final plane equation, so
let's ignore it...)

   The next question is why the three areas of the planar projections should
have anything to do with the coefficients of the plane equation. First fact:
the coefficients of the plane equation, when placed in a vector, make a vector
that is perpendicular to the plane. (Proof is an exercise).

Second fact: since this is going to work for any polygon, we might as well
use a nice one, like the one whose vertices are the intersections of 
the plane with the three coordinate axes. This triangle will be projected 
to three triangles, one in each of the XY, XZ, and YZ planes. Lets call 
their (signed) areas C, B, and A, respectively. Let's also suppose that the 
three points of intersection with the axes are (p, 0, 0), (0, q, 0) and 
(0, 0, r). Consider the function

f(x, y, z) = Ax + By + Cz

If we take f(p, 0, 0) we get Ap; this is just the volume of the pyramid whose
base is the projection of the triangle to the xy-plane and whose height is p,
i.e. the pyramid whose vertices are (p, 0, 0), (0, q, 0), (0, 0, r) and 
(0, 0, 0). In the same way, f(0, q, 0) is the volume of the same pyramid, and
f(0, 0, r) is too.

Let's call this volume d. Then the linear function Ax + By + Cz - d is 
zero on three points of the plane. A linear function on 3-space is 
determined (up to constant multiples) by its value on 3 points, hence this 
must be (up to constant multiples) the equation of the plane. 

I should note that I've made a few assumptions: the plane must not pass through
the origin, and it must not be parallel to any coordinate plane; the fact is,
however, that the proof given is correct on a set whose closure is the entire
set of planes (in a natural topology); since it is a statement about contiuous
functions, it's true on the whole set, including the apparent exceptions to the
proof. If this sounds bogus to you, you can work it out by hand for the special
cases. 

-John Hughes

PS I apologize if this telegraphic description is a little vague--it's after
midnight, and SIGGRAPH papers are due. You can find Plucker's original papers
if you can find a monograph by Crelle on "The complete works of Plucker." I've
only seen it in Italian, though...