flipcode - Dirtypunk's Column

Dirtypunk's Column - Issue 02 - Line Dualities: Plucker Space And You
by (16 March 2000)

Introduction

Hello ladies, gentlemen, and the various life forms that reside in #flipcode. This week's column (following up next weeks-bumper column on visibility) is about something that may help you understand the stuff in next week's column much better. I actually wrote that column first (I'm doing pictures as we speak) but I decided this should go first.

Actually, the topic of this week's article will be something heavy that I had trouble coming to terms with (mainly due to lack of simple explanation), called Plücker space.

What In The Name Of Yo' Momma Is Plücker Space

What is this portal, this gateway to another dimension of which I speak? Well, pretty simply it's a coordinate space 6D that determines the relative orientation of directed lines. In other words given a line with direction, you can find the position of a directed line in relation to that of another. Do you remember the right hand rules of physics, for a magnetic field from a circuit carrying wire? Well, imagine it like this, your thumb points in the direction of the line, and your fingers collapsed around it show the orientation for the forward direction. Another directed line is either going with this direction or against it, or the two lines are intersecting.

A directed line in Plücker space is actually a single 6d coordinate. It is also a hyper-plane that divides the space in two. This hyper-plane is defined by a simple dot product equated to zero (the dot product for the space is described below).

Not all coordinates in Plücker space correspond to real lines. They must be intersected with the Plücker Hyper-surface (Also know as the Klein Quadric and Grassman manifold). This will also be described in the section below.

Maths Make You Cry

Okay, now the idea sounds cool - But your saying wait a sec, this constant reference to maths sounds less than pleasant. Well, actually it's not too hard at all.

Firstly we start with 2 3d coordinates, defining a directed line. Lets call these P and Q (note, these aren't end points, the line is infinite). The parametric representation of the line would be N=P + (Q-P)*t. We can say this line is directed because as t increases, the line advances the direction (Q-P). If we swapped the points, the equation would be N=Q + (P-Q)*t. This means the direction advanced in is opposite.

Okay, now given these two points, P and Q, how do we define a Plücker space coordinate? Like this:

Where N=(N.0,N.1,N.2,N.3,N.4,N.5)

N=((P.x*Q.y - Q.x*P.y),(P.x*Q.z - Q.x*P.z),(P.x - Q.x),
   (P.y*Q.z - Q.y*P.z),(P.z - Q.z),(Q.y - P.y))

And how do we define a dot product between two coordinates?

Where Side(A,B) returns a scalar value and its sign determines the side of the line. If Side() is zero, both lines intersect.

Side(A,B) = A dot B = (A.0*B.4 + A.1*B.5 + A.2*B.3 + A.3*B.2 + A.4*B.0 + A.5*B.1)

Now, we know how to turn 3d lines into our space, and do a dot product, we need to do some more advanced stuff. A Plücker hyper-plane is defined by L dot A=0. Where L is our hyper-plane line (a single line) and A is our line to test against the plane. So, a hyper-plane is defined by all lines which stab (intersect) line L. Using the dot product above, side tests can also be done to determine orientation.

As mentioned before not all coordinates in the space represent real lines. Some represent lines that have complex coefficients. To find real lines, we need to do the test for intersection with the Plücker hyper-surface. This sounds hard. Seems the surface is quadric most people assume that you have to do multi-dimensional quadric root finding. Luckily this is not the case. The hyper surface is defined as A dot A = 0, or in other words, a line that is real when dotted with itself produces a scalar product of 0.

What The Hell Is This Useful For?

Well, for one thing a ray polygon intersection in 6 multiplies and 5 additions per edge. But we will get on to that soon. These coordinates are useful for finding stabbing lines, for finding if lines intersects multiple objects and for visible surface operations in general.

First things to know - polygon edges can be defined as directed lines. A convex polygon's edges define a convex volume in Plücker space, made up of the hyper-planes defined by the edges. This convex volume defines all the lines that pass through an object. This can lead us to the real use of Plücker space for visibility computations.

How do we find if a ray stabs a polygon. Well, just for a second imagine this - We have a ray. A ray is a directed line with an origin. So, we can convert it to a coordinate in our lovely space. If a plucker space coordinate is either on the same side or intersecting all the edges on the polygon, then the ray stabs the polygon. Storing all edges of polygons as Plücker coordinates is pretty low cost. Turning the ray into a Plücker space coordinate only has to happen when we create the ray. After that, we can just perform a dot product between the edges and the ray in the space to see if the ray stabs the polygon. Since each dot product in the space is 6 muls and 5 adds, you can see where my numbers come from. To test if a ray stabs a convex volume (ie a bounding box) you would need to test each face of the bounding box, to see if any intersection occurred, but each edge needs only one dot product test per ray.

Another interesting couple of topics are binary space partitions in Plücker space and CSG in Plücker space (the first something I've run into recently, the second something I came up with myself). Binary space partitions are useful for finding visibility relations, and such queries as finding if a ray stabs a set of objects or polygons. CSG operations are something I find more interesting, in that the hyper-volume bounded by the hyper-planes is the all the lines that run through it. As defined in papers on the ASP, we can find visibility between objects using the set of lines that run through them, and simple operations, such as unions, intersections and subtractions. This is something for later though.

Plücker space is also useful for finding if there is ever a line that stabs a set of convex polygons (for visibilty), finding lines which stab other lines etc.

Links To Algorithms In Plücker Space

Thanks to Thouis for some of these links. Most of them are ones I found for myself though.

http://ls7-www.cs.uni-dortmund.de/~hinkenja/papers/VisibilityReport.ps.gz

Okay, the above link is to finding visibility sets between objects using a linespace partioning (It talks mainly in terms of Plücker spaces 2d conterpart, but is expandable to the space).

http://graphics.lcs.mit.edu/~fredo/THESE/

This link is to Fredo Durand's thesis, in which multiple references to linespace are found, including algorithm to find an EEE swath in the space.

ftp://ftp.cs.umd.edu/pub/faculty/mount/Papers/alenex99.ps.gz

This one is also a link to binary partitioning in the space for visibility reasons.

http://graphics.lcs.mit.edu/~seth/pubs/pubs.html

Here is a link to Seth Teller's publication page. His thesis and various other documents contain references to algorithms using the space, such as finding out if there is a line which stabs a set of polygons (for portal visibility), finding the lines stabbing four lines, finding the antipenumbra of an area lightsource through a series of openings etc.

Conclusion

Well that ends another installment in the latest assortment of debauchery and lunacy in which I have deliberately surrounded myself, eg yo' momma. Tune in Next week for some visibility theory.

Conor "DirtyPunk" Stokes

Article Series:

Dirtypunk's Column - Issue 01 - Hardware Rendering Optimizations
Dirtypunk's Column - Issue 02 - Line Dualities: Plucker Space And You
Dirtypunk's Column - Issue 03 - Visibility Theory
Dirtypunk's Column - Issue 04 - View Independent Progressive Meshes
Dirtypunk's Column - Issue 05 - AABB Trees - Back To Playing With Blocks