Computing the best-fit plane normal from n points

Question

I've been working steadily through "3D Math Primer for Graphics and Game Development" and am stuck on how the authors derived their equation for the best-fit plane normal given n points. Please note, I'm not necessarily looking for someone to derive the proof, a good book/reference/technique name would suffice.

I'll describe the problem but for a quick view, see section 9.5.3: https://gamemath.com/book/geomprims.html#plane_best_fit

Given $n$ points, $p_1 = [x_1, y_1, z_1], [x_2, y_2, z_2], ..., [x_n, y_n, z_n]$

The normal $x,y,z$ components are as follows but with no explanation of derivation.

$n_x = \sum\limits_{i=1}^n(z_i + z_{i+1})(y_i - y_{i+1})$

A similar equation is given for each component of the normal vector.

Thanks!

Answer 1

Here's the deal: Plucker and others of his generation figured out that if you took a polygon in space and projected it down to the xy-plane, you could compute the area $A_{xy}$ of the resulting polygon. And the same goes for $A_{zy}$ and $A_{zx}$. In fact, you can compute the signed area, so that counterclockwise polygons are counted as positive and clockwise ones are negative. The formula for $n_z$ that you've got is exactly twice the formula for the area $A_{xy}$. I'll come back to that in a minute.

The cool thing is that these three projected areas, when assembled into a vector, turn out to produce the vector normal to the polygon. This is pretty easy to see when the polygon is parallel to one of the planes: two of the projected areas are zero, and the third's nonzero. For the more general case, the quickest proof I know involves some linear algebra and the change-of-area formula for double integrals, and I don't want to write it out here.

Let's go back to the planar area question: WHY is that the right formula (except for the missing factor of $\dfrac{1}{2}$)?

Answer:

First of all, let's consider the case where there are just 3 points. Since every polygon can be broken into a collection of triangles, that'll do the job.

Second, if you subtracted some number $c$ from all the $y$-coordinates, the number you got wouldn't change. Same goes for $z$-coordinates. So let's subtract $z_1$ from all the $z$ coords, adn $y_1$ from all the $y$-coords. Now we've got a triangle with one vertex at the origin. The other two verts are $(y_1 -y_0, z_1 - z_0)$ and $(y_2 - y_0, z_2 - z_0)$. And if you know about cross products of vectors, you can work out that the area of the triangle is just the cross product of the two edge-vectors (up to a factor of $\dfrac{1}{2}$).

The usual version of the cross-product formula for area has an absolute value so that you get the area....but if you remove the absolute value, you get the signed area, which is exactly what you need in Plucker's formula for the normal. It's a win-win thing!

Shameless plug: this is worked out in detail in the graphics book I just finished writing. But I believe that I'm not supposed to say what book that is.

One additional bit of trivia: If you computed the normal vector for your set of point by just taking vectors between 3 of the points (say $AB$ and $AC$) and finding the cross product, that'd work, most of the time. But if $A$, $B$, and $C$ happened to be collinear, you'd get the $0$-vector as an answer, and have to try again. Furthermore, the Plucker method has the charm that if the points all almost lie in a plane, but happen to have suffered roundoff error or something, the method still produces a very good approximation to the plane normal. In fact, if the points are perturbed uniformly and independently along the true normal, I think that the computed Plucker normal may have an expected value that's the true normal, under some weak assumputions about the distribution of original points, but I don't know that for sure.