GameFusion
Game Production and Pipeline Services

Geek Zone

Using GA to test if a point lies on a line

From the discussion about point-plane distance queries, we saw that pπpΠ = 0 when points and planes coincide.

Does the same apply to point-line distance queries as well?

Let's find out with a simple example:

Let L = | (1, 2, 3, 1) ∧ (4, 5, 6, 1) | =

(1 / √3) ( -e12 - 2e13 - e 23 - e14 - e24 - e34 ) be a normalized line in P3 .

Let p = (7e1 + 8e2 + 9e3 + e4 ) be a normalized point in P3 .

It's not hard to visualize that the point p = (7, 8, 9, 1) lies on the line passing through points (1, 2, 3, 1) and (4, 5, 6, 1) .

Does the math work?

Compute pL =

(1 / √3) (7e1 + 8e2 + 9e3 + e4 ) ( -e12 - 2e13 - e23 - e14 - e24 - e34 ) =

(1 / √3)( -7e123 - 7e124 - 7e134 - 16e213 - 8e214 - 8e234 - 9e312 - 9e314 - 9e324 -e412 - 2e413 - e423) .

Now is a good time to re-arrange (i.e., 'swap') basis blade indices so that they're ordered in 'canonical form'.

Negate the coefficient of basis elements whose indices require an odd number of swaps:

e213 ≡ -e123 so that -16e213 becomes +16e123 .

e214 ≡ -e124 so that -8e214 becomes +8e124 .

e314 ≡ -e134 so that -9e314 becomes +9e134 .

e324 ≡ -e234 so that -9e324 becomes +9e234 .

For an even number of swaps, just write the indices in order.

 

Now the equation reads:

(1 / √3)

( -7e123 - 7e124 - 7e134 + 16e123 + 8e124 - 8e234 - 9e123 + 9e134 + 9e234 - e124 - 2e134 - e234)

Grouping terms:

(1 / √3)( (-7 + 16 - 9)e123 + (-7 + 8 - 1)e124 + (-7 + 9 - 2)e134 + (-8 + 9 - 1)e234 )

Simplifying, we end up with:

pL = (1 / √3)( 0e123 + 0e124 + 0e134 + 0e234 )

which is the zero trivector (i.e., a degenerate plane formed by wedging together three collinear points), so the point does indeed lie on the line!

 

I'd also like to mention that while writing the calculations out by hand appears tedious (and it is), an efficient computer implementation of the above only performs 12 floating-point muls and 8 floating-point adds.

The ordering of basis blade indices, handling which coefficients go where, etc. can be performed at compile-time with template meta-programming techniques in the C++ or D programming languages.

Storage requirements are fairly undemanding: for 3-d k-flats, we need

  • 4 floats to store a point,
  • 4 floats for a plane, and
  • 6 floats for a line.

This is pretty much matches the storage requirements for these same entities within a standard 3-d engine setting. Note, however, that a line doesn't directly store any information about the points used to construct it (it's not a line segment).

 

Jason WoodComment