Introduction to Plücker Coordinates
     by Thouis Jones (rjones@pobox.com)

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 Plücker 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.