Algorithm 4
|
|
|
| About Planes |
 Plane
Equations |
|
Computing
Parametric Coordinates |
| Distance of a Point to a Plane |
| Implementations |
|
pbase_Plane() |
| References |
Here we present basic information about representing planes, and how to compute the distance of a point to a plane. This will be used in algorithms about the Intersections of Lines, Segments and Planes.
A surface is that which has length and breadth only. [Book I,
Definition 5]
The extremities of a surface are lines. [Book I, Definition 6]
A plane surface is a surface which lies evenly with the straight lines on
itself. [Book I, Definition 7]
If two straight lines cut one another, they are in one plane,
and
every triangle is in one plane. [Book XI, Proposition 2]
If two planes cut one another, their common section is a straight line. [Book
XI, Proposition 3]
From the same point two straight lines cannot be set up at right
angles to the same plane on the same side. [Book XI, Proposition 13]
[Euclid, 300 BC]
Although Euclid defined a plane in Book I as the third primitive after the point and line, he did not prove anything about planes until much later in Book XI. And even then, he did not appeal to the definition from Book I in his proofs of Propositions in Book XI [Heath, 1956]. In modern times, [Coxeter, 1989a] gives a more exact definition of a plane as:
Definition. If A, B, C are three non-collinear points, the plane ABC is the set of all points collinear with pairs of points on one or two sides of the triangle ABC.
which is used to prove properties of incidence in a plane. Nevertheless, Euclid's Propositions XI.2 and XI.13 make it clear the Greeks knew that a plane is uniquely determined by any of the following data:
by three non-collinear points,
by two straight lines meeting one another,
by a straight line and a point not on it, and
a point and a perpendicular line.
Thus, there are many ways to represent a plane p. Some work in any dimension, and some work only in 3D. In any dimension, one can always specify 3 non-collinear points V0=(x0,y0,z0), V1=(x1,y1,z1), V2=(x2,y2,z2) as the vertices of a triangle, the most primitive planar object. In 3D, this uniquely defines the plane of points (x,y,z) satisfying the implicit equation:
.
Also in any dimension, similar to the parametric line equation, one can replace either or both of the two specified points V1 and V2 by direction vectors u=V1-V0 and v=V2-V0. Then, given one point V0 and two nonparallel line direction vectors u and v, there is a natural parametric equation for the plane p; namely:
where s and t are real numbers which are coordinates for the plane relative to the origin V0 and the basis vectors u and v. When 0<=s, 0<=t, and s+t<=1, P=V(s,t) is inside the triangle T = V0V1V2.
The pair of parameters (s,t) is referred to as the parametric coordinate of P=V(s,t) relative to T. Note that the point P is on an edge of T whenever one of the conditions s=0, t=0, or s+t=1 is true (each condition corresponds to one edge). Also, the three vertices of T are given by: V0=V(0,0), V1=V(1,0), and V2=V(0,1).
A similar representation is given by the areal barycentric coordinate [Coxeter, 1989b] of a point P relative to a triangle T = V0V1V2. This method associates a triple (b0,b1,b2) with the centroid P of three masses b0, b1, and b2 located at the triangle's three vertices. Negative numbers are treated as negative masses (like helium balloons). This gives:
The triple (b0,b1,b2) is called a (homogeneous) barycentric coordinate for P relative to the triangle T. The normalized triple (a0,a1,a2) satisfying a0 + a1 + a2 = 1 is called the areal (barycentric) coordinate of P. Clearly, we have P(a0,a1,a2) = a0V0 + a1V1 + a2V2, and thus any triple (a0,a1,a2) which sums to 1 is a valid areal coordinate. Further, there is a 1-to-1 correspondence between areal coordinates and all points on the plane. This can be seen by noting the equivalence of areal barycentric and parametric coordinate representations gotten by setting: a0 = (1-s-t), a1 = s, and a2 = t.
Areal coordinates have a number of useful properties with respect to the triangle T. For example, the point P lies inside the triangle T only when all components of its areal barycentric coordinate are nonnegative, that is a0³0, a1³0, and a2³0. Further interesting properties, especially ones related to area ratios, are given by [Coxeter, 1989b].
In 3D, another popular and useful representation for a plane is the normal form that specifies point V0 on the plane and a vector n which is normal (perpendicular) to it. This representation can be used to compute intersections since it results in compact and efficient formulas. But, it only defines a plane in 3D space. In a higher n-dimensional space, this representation defines an (n-1)-dimensional linear subspace. We will not pursue this further except to say that many of the results for planes in 3D carry over to hyperplanes of n-D space (see [Hanson, 1994] for further information).
In 3D, a plane normal vector n can be computed from a triangle V0V1V2 of points on the plane as the cross-product n = u×v = (V1-V0)×(V2-V0). Then, any point P on the plane satisfies the implicit equation:
 |
 |
For n = (a,b,c), P = (x,y,z) and d = -(n · V0), the equation is:
Note that the coefficients (a,b,c) of a linear equation describing a plane p always give a vector which is perpendicular to the plane. Also, when d=0, p passes through the origin.
It is often useful to have a unit normal vector which simplifies some formulas. This is done by simply dividing n by |n|=sqrt(a2+b2+c2). Then, the associated implicit equation ax+by+cz+d=0 is said to be normalized. Further, when |n|=1, then the coefficients a,b,c of n are the direction cosines of the angles that the vector n makes with the xyz-axes. Also note that, when |n|=1, then d = the perpendicular distance from the origin to the plane as we will show in the next section.
One can convert from any of these representations to another when convenient. For example, given two direction vectors for nonparallel lines on a plane, their cross-product gives a normal vector. Conversely, given a normal vector, one can easily find two other independent vectors perpendicular to it. For example, given a n = (a,b,c) with a¹0, then u=(-b,a,0) and v=(-c,0,a) are both perpendicular to n since both u · n = 0 and v · n = 0. Also, three non-collinear points on the plane are: V0, V0+u, and V0+v. Most other conversions are at least as easy.
However, one conversion involves more than trivial computation; namely, finding the parametric or barycentric coordinates (defined above) of a given 3D point P=(x,y,z) relative to a triangle T=V0V1V2 in the plane. We start by putting u = V1-V0 and v = V2-V0 as before, as well as w = P-V0. Then, we find the parametric coordinates (s,t) of P as the solution of the equation: w = su + tv. This solution exists and is unique when P lies in the plane of T. Finally, the barycentric coordinates of P = b0V0 + b1V1 + b2V2 are equal to: b0 = (1-s-t), b1 = s, and b2 = t which satisfy: b0 + b1 + b2 = 1.
To solve this equation, we define a 3D generalization of Hill's "perp-dot" product [Hill, 1994]. For an embedded 2D plane p with a normal vector n, and any vector a in the plane (that is, a satisfies n·a=0), define the "generalized perp operator on p" by: a^ = n×a. Then, a^ is another vector in the plane p (since n·a^=0), and it is perpendicular to a (since a·a^=0). Further, this new perp operator is linear on vectors in p; that is, (Aa+Bb)^=Aa^+Bb^ where a and b are vectors in p, and A and B are scalars. Note that if p is the 2D xy-plane (z=0) with n=(0,0,1), then this is exactly the same 2D perp operator given by [Hill, 1994].
Now, we will solve the equation: w = su + tv for s and t. First, take the dot product of both sides with v^ to get: w · v^ = su · v^ + tv · v^ = su · v^, and solve for s. Similarly, taking the dot product with u^, we get: w · u^ = su · u^ + tv · u^ = tv · u^, and solve for t. We get:
 |
and |
 |
The denominators are nonzero whenever the triangle T is nondegenerate (that is, has a nonzero area). When T is degenerate, it is either a segment or a point, and in either case does not uniquely define a plane.
Altogether we have used 3 cross products (one to compute n) which is a lot of computation. However, for any three vectors a b c, the following identity holds for left association of the cross product: (a × b) × c = (a · c) b - (b · c) a. [Note: the cross product is not associative, and so there is a different (but similar) identity for right association]. Applying the left association identity results in the simplifications:
And we can now compute the solutions for s and t using only dot products as:
with 5 distinct dot products. We have arranged terms so that the two denominators are the same and only need to be calculated once.
The distance from an arbitrary 3D point P0=(x0,y0,z0) to the plane p: ax+by+cz+d=0 can be computed by using the dot product to get the projection of the vector (P0-V0) onto n as shown in the diagram:
which results in the formula:
For a unit normal, when |n| = 1, this formula simplifies to:
showing that d is the distance from the origin (0,0,0) to the plane p.
These formulas give a signed distance which is positive on one side of the plane and negative on the other. So, take the absolute value of them to get an absolute distance. Otherwise, the distance is positive for points on the side pointed to by the normal vector n. Because of this, the sign of d(P0,p) can be used to simply test which side of the plane a point is on. For example, if P0P1 is a finite line segment, then it intersects p only when the two endpoints are on opposite sides of the plane; that is, if d(P0,p)d(P1,p)<0. Conversely, when d(P0,p)d(P1,p)>0, there cannot be an intersection. Also, if d(P0,p)d(P1,p)=0, then either one or both of the endpoints are on p. When both are on p, the whole segment P0P1 lies in the plane.
Note the resemblance of these formulas to the ones for the distance of a point to a line in 2D space (see: Distance of a Point to a Line, Ray or Segment). Also note that we did not calculate the base point of the perpendicular from the point to the plane which some authors do. If one just wants the distance, then directly computing it without going through an intermediate calculation is fastest.
Nevertheless, there are situations where one wants to know the orthogonal (perpendicular) projection of P0 onto p. It can be computed by taking a line through P0 that is perpendicular to p (that is, one which is parallel to n), and computing it's intersection with the plane. The perpendicular line through P0 is given by: P(s) = P0 + sn. As shown in the next section, it intersects p when P(s) satisfies the plane equation n · (P(s)-V0) = 0. Solving this for sp at the intersection point, we get:
And the base of the perpendicular is the intersection point:
For the special case when P0=(0,0,0), one has: Pp = -dn / |n|2 as the orthogonal projection of the origin onto the plane. Again, we see that d(0,p) = d(0,Pp) = d / |n|, and when n is a unit normal: d(0,p) = d.
Here are some sample "C++" implementations of these algorithms.
// Copyright 2001, softSurfer (www.softsurfer.com)
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.
// Assume that classes are
already given for the objects:
// Point and Vector with
// coordinates {float x, y, z;}
// operators for:
// Point
= Point ± Vector
// Vector =
Point - Point
// Vector =
Scalar * Vector (scalar product)
// Plane with a point and a normal {Point V0; Vector
n;}
//===================================================================
// dot product (3D) which
allows vector operations in arguments
#define dot(u,v) ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)
#define norm(v) sqrt(dot(v,v)) // norm = length of
vector
#define d(u,v) norm(u-v)
// distance = norm of difference
//
pbase_Plane(): get base of perpendicular from point to a plane
// Input: P = a 3D point
// PL = a
plane with point V0 and normal n
// Output: *B = base point on PL of perpendicular from P
// Return: the distance from P to the plane PL
float
pbase_Plane( Point P, Plane PL, Point* B)
{
float sb, sn, sd;
sn = -dot( PL.n, (P - PL.V0));
sd = dot(PL.n, PL.n);
sb = sn / sd;
*B = P + sb * PL.n;
return d(P, *B);
}
//===================================================================
Donald Coxeter, Introduction to Geometry (2nd Edition), Sect 12.4 "Planes and Hyperplanes", John Wiley & Sons (1989a)
Donald Coxeter, Introduction to Geometry (2nd Edition), Sect 13.7 "Barycentric Coordinates", John Wiley & Sons (1989b)
Euclid, The Elements, Alexandria (300 BC)
Andrew Hanson, "Geometry for N-Dimensional Graphics" in Graphics Gems IV (1994)
Thomas Heath, The Thirteen Books of Euclid's Elements, Vol 1 (Books I and II) (1956)
Thomas Heath, The Thirteen Books of Euclid's Elements, Vol 3 (Books X-XIII) (1956)
Francis Hill, "The Pleasures of 'Perp
Dot' Products" in
Graphics Gems IV (1994)
[Note: the first critical definition has a typo, and should be: a^
= (-ay, ax).]
|
Copyright ©
2001-2006 softSurfer. All rights reserved. |
