baer@cs.mcgill.ca (Lawrence BAER) (01/04/91)
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.cajfh@cs.brown.edu (John Forbes Hughes) (01/07/91)
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...
turk@Apple.COM (Ken "Turk" Turkowski) (02/01/91)
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. Each of the sums (a, b, c) is computing the area (scaled by a factor of two) of the polygon as projected onto the standard coordinate planes (xy, yz, zx). If you look at the term of summation closely, you will see that it is the formula for a trapezoid (times two): Area(trapezoid) = width * (leftHeight + rightHeight) / 2 So, the polygon's projected area is computed by decomposing it into trapezoids. A little thought game will show you that the components increase and decrease as expected, if you rotate the polygon. Proof? Do you understand the significance of the vector cross product? Area of a triangle (or rather a planar parallelogram), ... perpendicular to the plane of the triangle ... some grad student should be able to fill in the details. Here is a problem on a related question: Suppose you calculate the normals as with Newell's method, including the divide by 2, so that the A, B, and C's are all accurate measurements of the projected areas. Now compute D = Ax + By + Cz (or its negative). Do this for every polygonal face on a *closed* polyhedron. Add up all of the D's. What is the significance of this sum? (Hint: remember the divergence theorem?) Giving credit where credit is due: Martin Newell himself gave me this information, but left me with less of a proof than I've left you. -- Ken Turkowski @ Apple Computer, Inc., Cupertino, CA Internet: turk@apple.com Applelink: TURK UUCP: sun!apple!turk