flipcode - Introduction To Plücker Coordinates

Introduction To Plücker Coordinates
by (23 June 2000)

Plücker Coordinates

This is an introduction to Plücker coordinates, a useful tool for some geometric problems. You may have already seen Plücker coordinates on flipcode in DirtyPunk's Column[0]. This introduction borrows from many sources, in particular a couple of articles in Ray Tracing News[1,2] and a paper by Seth Teller and Michael Hohmeyer[3]. You should probably check those out after this tutorial to get an idea what else you can do with Plücker coordinates, as well as get pointers to sources of more information.

Plücker coordinates are a representation of directed[4] lines in 3-space. Each 3D directed line corresponds to a homogeneous[5] point in 6D Plücker space (in other words, a non-homogeneous point in 5D space). That we need this many dimensions makes sense, since pairs of 3D points define lines, but we can remove one dimension by realizing that the lines defined by (0,0,0) -> (1,1,1) and (0,0,0) -> (2,2,2) are the same, except for a scale factor.

First, some notation. I've borrowed this from [2]:


   (U:0) - A homogeneous vector, with U = (Ux,Uy,Uz)
   (P:1) or (P:w) - A homogeneous point, P = (Px,Py,Pz)
   [D:d] - A plane with equation ax+by+cz+dw=0, D = (a,b,c) being the
           normal to the plane
   {U:V} - A Pluecker coordinate, with U,V 3 element vectors
    U.V  - The dot product of vectors U and V
    UxV  - The cross product of vectors U and V

The first thing I should explain is how to create the Plücker coordinate for a particular line. There are two common cases:

Given a 3D point P and a direction U:

L = {U:UxP}

Given two 3D points, P and Q, the line from Q to P:

L = {P-Q:PxQ}

Now, the first useful thing you can do once you have Plücker coordinates: Two lines L1 and L2 are the same if:

L1 = s * L2 for some value s > 0

If s is negative, then the lines point in the opposite directions.

Two lines L1 = {U1:V1}, L2 = {U2:V2} are parallel if

U1xU2 = 0.

Finally, and much more usefully, you can tell whether two lines intersect, or how they pass each other in space:


     w = U1.V1 + U2.V2
     If...  w = 0     L1,L2 Intersect
            w > 0     L1,L2 pass Counterclockwise
            w < 0     L1,L2 pass Clockwise

The CCW/CW directions are what you see looking down either one of the lines. Here, one of the lines is shown as a dot, and is pointing into the page (borrowed from [1]):


                     ---------->
         o                o
    ---------->
  counterclockwise    clockwise

The computation above is called the "permuted inner product"[6]. It allows for a very straightforward Ray/Triangle intersection test as explained in RTNews by Jeff Erickson (again from [1]):


              ^ 
            / |   
           /  |    
    ----------|--->
         /    |
        /     |
       L------>

Compute the interactions between each edge of the triangle and the ray. If they all have the same sign, the ray must intersect the triangle. In the figure above, all the edges are counterclockwise around the ray.

A couple more equations. Given two planes [E:e] and [F:f], the Plücker line coordinates for their intersection are given as:

{ExF:fE-eF}

Note how similar this form is to the "two points" method of defining Plücker coordinates.

The intersection point of a line {U:V} and a plane [N:n] is:

(VxN-nU:U.N)
Note that this is in homogeneous coordinates.

Finally, one more rule. Not every set of 6 numbers corresponds to a line in 3D space. In fact, this is only true if, for a line {U:V}

U.V = 0

The points in 6D space where this is true are called the "Grassman manifold. When solving problems using Plücker coordinates, sometimes you end up with a line in Plücker space, and you need to find the intersection of that line with the Grassman manifold to find the Plücker points that correspond to the real solutions to the problem. More discussion of that particular operation is beyond the scope of this introduction, however.

Plücker coordinates are a powerful tool for geometric computations, as explained by Ken Shoemake (in [2]):

"The striking similarity of the point and plane definitions tell us Plücker 3D line coordinates precisely balance these extremes. Many computational benefits accrue. Also, many questions come in dual pairs, with the answers for one obtained by swapping U and V in the answers for the other."

I strongly suggest reading Ken Shoemake's tutorial[2], or at least skimming it. Even if you don't understand everything you read, it will give you a good overview of the other uses of Plücker coordinates.

That's probably enough for now. I hope this has been a gentle introduction to Plücker coordinates. Writing this, I've decided that a few more intros of this sort might be useful (homogeneous coordinates, the math behind Plücker coordinates, calculating the barycentric coordinates of ray-triangled intersections via the method above, etc.) Let me know what you think about this introduction, and what you'd like to hear more about.

Thouis (Ray) Jones
rjones@pobox.com

References

[0] http://www.flipcode.com/dp/issue02.shtml

[1] http://www.acm.org/tog/resources/RTNews/html/rtnv10n3.html#art11

[2] http://www.acm.org/tog/resources/RTNews/html/rtnv11n1.html#art3 - This is an excellent explanation of what you can do with Plücker coordinates, along with the reasons why.

[3] http://graphics.lcs.mit.edu/~seth/pubs/TellerHohmeyerJGT2000.pdf - (located at http://graphics.lcs.mit.edu/~seth/pubs/pubs.html)

[4] Directed - as opposed to undirected, for which the line going from A to B is the same as the line from B to A

[5] Homogeneous coordinates are a way of representing N-dimensional coordinates with N+1 numbers. The homogeneous coordinate (x,y,z,w) is (x/w, y/w, z/w) in non-homogeneous coordinates. In the standard graphics pipeline, 4D homogeneous points are used to represent points in 3D space. In the discussion here, 6D homogeneous points are used to represent points in 5D space.

Homogeneous coordinates are useful for many geometric tasks, and show up in graphics and geometry calculations on a regular basis.

[6] The inner product of two vectors is also known as the dot product. For Plücker coordinates, it would be U1.U2 + V1.V2.