Plücker line coordinates

From CGAFaq

A common convention is to write umlauted u (ü) as “ue”, so you’ll also see “Pluecker”. Lines in 3D can easily be given by listing the coordinates of two distinct points, for a total of six numbers. Or, they can be given as the coordinates of two distinct planes, eight numbers. What’s wrong with these? Nothing; but we can do better. Plücker coordinates are, in a sense, halfway between these extremes, and can trivially generate either. Neither extreme is as efficient as Plücker coordinates for computations.

When Plücker coordinates generalize to Grassmann coordinates, as laid out beautifully in [Hodge], Chapter VII, the determinant definition is clearly the one to use. But 3D lines can use a simpler definition. Take two distinct points on a line, say

P = (P_x,P_y,P_z)

Q = (Q_x,Q_y,Q_z)

Think of these as vectors from the origin, if you like. The Plücker coordinates for the line are essentially

U = P − Q

V = P × Q

Except for a scale factor, which we ignore, U and V do not depend on the specific P and Q! Cross products are perpendicular to their factors, so we always have U⋅V = 0. In [Stolfi] lines have orientation, so are the same only if their Plücker coordinates are related by a positive scale factor.

As determinants of homogeneous coordinates, begin with the 4×2 matrix

row x    [ Px  Qx ]
row y    [ Py  Qy ]
row z    [ Pz  Qz ]
row w    [ 1   1  ]

Define Plücker coordinate G_ij as the determinant of rows i and j, in that order. Notice that G_iw = P_i − Q_i, which is U_i. Now let (i,j,k) be a cyclic permutation of (x,y,z), namely (x,y,z) or (y,z,x) or (z,x,y), and notice that G_ij = V_k. Determinants are anti-symmetric in the rows, so G_ij = −G_ji. Thus all possible Plücker line coordinates are either zero (if i=j) or components of U or V, perhaps with a sign change. Taking the w component of a vector as 0, the determinant form will operate just as well on a point P and vector U as on two points. We can also begin with a 2×4 matrix whose rows are the coefficients of homogeneous plane equations, E⋅P=0, from which come dual coordinates G'_ij. Now if (h,i,j,k) is an even permutation of (x,y,z,w), then G_hi = G'_jk. (Just swap U and V!)

Got Plücker, want points? No problem. At least one component of U is non-zero, say U_i, which is G_iw. Create homogeneous points P_j = G_jw + G_ij, and Q_j = G_ij. (Don’t expect the P and Q that we started with, and don’t expect w=1.) Want plane equations? Let (i,j,k,w) be an even permutation of (x,y,z,w), so G'_jk = G_iw. Then create E_h = G'_hk, and F_h = G'_jh.

Example: Begin with P = (2,4,8) and Q = (2,3,5). Then U = (0,1,3) and V = (−4,6,−2). The direct determinant forms are G_xw=0, G_yw=1, G_zw=3, G_yz=−4, G_zx=6, G_xy=−2, and the dual forms are G'_yz=0, G'_zx=1, G'_xy=3, G'_xw=−4, G'_yw=6, G'_zw=−2. Take U_z = G_zw = G'_xy = 3 as a suitable non-zero element. Then two planes meeting in the line are

0 = (G'_xy G'_yy G'_zy G'_wy)⋅P

0 = (G'_xx G'_xy G'_xz G'_xw)⋅P

That is, a point P is on the line if it satisfies both these equations:

0 = 3 P_x + 0 P_y + 0 P_z − 6 P_w

0 = 0 P_x + 3 P_y − 1 P_z − 4 P_w

We can also easily determine if two lines meet, or if not, how they pass. If U1 and V1 are the coordinates of line L1, U2 and V2, of line L2, we look at the sign of U1⋅V2 + V1⋅U2. If it’s zero, they meet. The determinant form reveals even permutations of (x,y,z,w):

G1_xw G2_yz + G1_yw G2_zx + G1_zw G2_xy + G1_yz G2_xw + G1_zx G2_yw + G1_xy G2_zw

Two oriented lines L1 and L2 can relate in three different ways: L1 might intersect L2, L1 might go clockwise around L2, or L1 might go counterclockwise around L2. Here are some examples:

Line pair signature meaning

The first and second rows are just different views of the same lines, once from the “front” and once from the “back.” The last row is what they might look like if you look straight down line L2 (shown here as a dot).

The Plücker coordinates of L1 and L2 give you a quick way to test which of the three it is.

cw:	U1⋅V2 + V1⋅U2	<	0
ccw:	U1⋅V2 + V1⋅U2	>	0
thru:	U1⋅V2 + V1⋅U2	=	0

So why is this useful? Suppose you want to test if a ray intersects a triangle in 3-space. One way to do this is to represent the ray and the edges of the triangle with Plücker coordinates. The ray hits the triangle if and only if it hits one of the triangle’s edges, or it’s “clockwise” from all three edges, or it’s “counterclockwise” from all three edges. For example...

In this picture, the ray is oriented counterclockwise from all three edges, so it must intersect the triangle.

Using Plücker coordinates, ray shooting tests like this take only a few lines of code.

Grassmann coordinates allow similar methods to be used for points, lines, planes, and so on, and in a space of any dimension. In the case of lines in 2D, only three coordinates are required:

G_xw = P_x−Q_x = −G'_y

G_yw = P_y−Q_y = G'_x

G_xy = P_xQ_y−P_yQ_x = G'_w

Since P and Q are distinct, G_iw is non-zero for i = x or y. Then

(G_ix,G_iy,G_iw) is a point P1 on L

(G_xw,G_yw,G_ww)+P₁ is a point P2 on L

(G'_x,G'_y,G'_w)⋅P = 0 is an equation for L

Two lines in a 2D perspective plane always meet, perhaps in an ideal point (meaning they’re parallel in ordinary 2D). Calling their homogeneous point of intersection P, the computation from Grassmann coordinates nicely illustrates the convenience. (See “Intersecting line segments”.) For i = x,y,w, set

P_i = G'_j H'_k − G'_k H'_j, where (i,j,k) is even

See [Hodge] for a thorough discussion of the theory, [Stolfi] for a little theory with a concise implementation for low dimensions (see Subj. 0.04), and these articles for further discussion:

• J. Erickson, Pluecker Coordinates, Ray Tracing News 10(3) 1997,

http://www.acm.org/tog/resources/RTNews/html/rtnv10n3.html.

• Ken Shoemake, Pluecker Coordinate Tutorial, Ray Tracing News 11(1) 1998,

http://www.acm.org/tog/resources/RTNews/html/rtnv11n1.html.