Line Plane intersection computation in Bwise

Image TV Wiki lineplane1.gif

In the context of three dimensional graphics, missing in prepared form currently from tcl, but very present in tcl driven applications, such as Maze in openGL om windows navigation controlled by Tcl/Tk and some wiki pages have subjects which can excellently well be extended to 3 dimensions, such as recently Cubic Splines and C compiled image processing on an interactive Bwise canvas, Interactive Polygon in Bwise, as well as that there are opengl links and regular questions on the news about 3D tcl/tk extensions, this page discusses the basic idea of computing the point where a line intersects a plane.

I did this problem once as assignment for a digital design course a Delft University before I graduated, where the intent was to make a hardware design, that is a chip like design, with digital gates and arithmetic units, which would very rapidly compute such intersections.

The interesting part there is that a analysis can be made of the basic components of such computation, such as additions and multiplication, which are also important in software analysis.

In tcl this is nearly always inefficient, but preparing a good 3D (or multi-D) library is a good idea, no matter for what implementation, and Bwise has partly been invented for graphically dealing with building blocks of the kind, which can give good insight in algorithms, and let users and programmers play with and research various topologies of computations.

The intersection I of a line spanned by vector V and plane P in mathematical sense is easier when we first take the plane to be unbounded and parallel to the x-y plane, so defined by

 z = a

The vector V is of course:

     (x)
     (y)
 V = (z)

The plane can also be taken to be defined by its normal vector, which in this simple case would be (0,0,1), and the plane equation:

 N . X = c

where N is the normal vector, X = (x,y,z), and c is a constant (real number), which can be found by filling in a single support vector for the plane.

When we take V to be a direction vector, possibly normalized, i.e. multiplied to have length 1, we want to find the point where the line spanned by V 'hits' the plane. Clearly, at that point the line equation and the plane equation must describe the same point in three dimensional space, so:

 a . V = (xi,yi,zi), where
 N . (xi,yi,zi) = c

The dot stands for inner product, i is subscript indicating intersection. The line is thought to be spanned by a single direction vector, not necessarily normalized (made to have length 1), and to contain the origin.

We can rewrite the line by distributing the variable a to the vector components, so that the line vector representation becomes:

       ( ax )
       ( ay )
 line: ( az )

and fill it in in the plane equation, so that we can find the intersection point which is part of both the line and the plane:

 N . a . V = c

or, reordereing and filling a given plane support point S in to find c:

 a . N . V = N . S   ==>
 a = N.S / N.V

So that the intersection point becomes

 a.V = V (N . S / (N . V))

When V is normalized, so that

       V
 Vn = ---
      |V|

and in the above Vn is used instead of V, the value for a becomes equal to the distance d which the intersection point is away from the origin.

In Tcl, the inproduct can be written as:

 proc inprod { {a} {b} } {
   set r 0 ; 
   for {set i 0} {$i < [llength $a]} {incr i} {
      set r [expr $r+[lindex $a $i] * [lindex $b $i]]
   } ;
   # puts "$a . $b = $r"
   return $r 
 }

Using this, the intersection can be computed by:

 proc line_plane_ic { line_dir_v plane_support_v plane_normal_v } {
   #compute the plane constant by 'filling in' the support vector
   set c [inprod $plane_support_v $plane_normal_v]
   set a [expr $c / [inprod $plane_normal_v $line_dir_v] ]
   # puts "c $c  a $a"
   set r {}
   for {set i 0} {$i < [llength $line_dir_v]} {incr i} {
      lappend r [expr $a * [lindex $line_dir_v $i]]
   }
   return $r
 }

Simple Testing:

  line_plane_ic {0.0 0.0 1.0} {0.0 0.0 1.0} {0.0 0.0 1.0}
 0.0 0.0 1.0

  line_plane_ic {2.0 0.0 2.0} {0.0 0.0 1.0} {0.0 0.0 1.0}
 1.0 0.0 1.0

Seems ok thus far.

For redrawing the above, I used the save_canvas routine from bwise and a console added to tkpaint to save a bwise loadable tcl version:

 .mw.c create line 165.0 42.0 165.0 248.0 91.0 336.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow both -arrowshape {8 10 4} -capstyle butt -fill black -dash {} -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag3} -width 1.0
 .mw.c create line 166.850626538 248.0 416.291910004 248.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow last -arrowshape {8 10 4} -capstyle butt -fill black -dash {} -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag4} -width 1.0
 .mw.c create text 79.0 347.0 -activefill {} -activestipple {} -anchor center -disabledfill {} -disabledstipple {} -fill black -font {Arial 10 {}} -justify left -offset 0,0 -state {} -stipple {} -tags {text obj utag5} -text X -width 0
 .mw.c create text 431.0 250.0 -activefill {} -activestipple {} -anchor center -disabledfill {} -disabledstipple {} -fill black -font {Arial 10 {}} -justify left -offset 0,0 -state {} -stipple {} -tags {text obj utag6} -text Y -width 0
 .mw.c create text 165.0 26.0 -activefill {} -activestipple {} -anchor center -disabledfill {} -disabledstipple {} -fill black -font {Arial 10 {}} -justify left -offset 0,0 -state {} -stipple {} -tags {text obj utag7} -text Z -width 0
 .mw.c create polygon 264.0 143.0 321.0 77.0 499.0 71.0 415.0 149.0 263.0 144.0 263.0 144.0 263.0 144.0 263.0 144.0 -activedash {} -activefill {} -activeoutline {} -activeoutlinestipple {} -activestipple {} -activewidth 0.0 -dash {} -dashoffset 0 -disableddash {} -disabledfill {} -disabledoutline {} -disabledoutlinestipple {} -disabledstipple {} -disabledwidth 0.0 -fill {} -joinstyle round -offset 0,0 -outline black -outlineoffset 0,0 -outlinestipple {} -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Polygon obj utag8} -width 1.0
 .mw.c create line 166.0 247.0 364.0 113.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow last -arrowshape {8 10 4} -capstyle butt -fill black -dash {} -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag9} -width 3.0
 .mw.c create line 362.0 114.0 165.0 126.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash - -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag11} -width 1.0
 .mw.c create line 360.0 115.0 360.0 313.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash - -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag12} -width 1.0
 .mw.c create line 375.0 248.0 361.0 311.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash - -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag13} -width 1.0
 .mw.c create line 360.0 311.0 111.0 311.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash - -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag14} -width 1.0
 .mw.c create line 166.0 248.0 359.0 310.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash . -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag15} -width 1.0
 .mw.c create line 294.0 109.0 447.0 120.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash . -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag18} -width 1.0
 .mw.c create line 337.0 147.0 393.0 75.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash . -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag19} -width 1.0
 .mw.c create line 362.0 113.0 413.0 74.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash -, -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag25} -width 1.0
 .mw.c create line 412.0 75.0 491.0 19.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow none -arrowshape {8 10 3} -capstyle butt -fill black -dash {} -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag26} -width 1.0
 .mw.c create text 240.0 180.0 -activefill {} -activestipple {} -anchor center -disabledfill {} -disabledstipple {} -fill black -font {Arial 14 bold} -justify left -offset 0,0 -state {} -stipple {} -tags {text obj utag27} -text V -width 0
 .mw.c create line 233.0 168.0 247.0 167.0 -activedash {} -activefill {} -activestipple {} -activewidth 0.0 -arrow last -arrowshape {8 10 4} -capstyle butt -fill black -dash {} -dashoffset 0 -disableddash {} -disabledfill {} -disabledstipple {} -disabledwidth 0.0 -joinstyle miter -offset 0,0 -smooth 0 -splinesteps 12 -state {} -stipple {} -tags {Line obj utag28} -width 2.0
 .mw.c create text 352.0 103.0 -activefill {} -activestipple {} -anchor center -disabledfill {} -disabledstipple {} -fill black -font {Arial 14 bold} -justify left -offset 0,0 -state {} -stipple {} -tags {text obj utag29} -text S -width 0

I'd be good to simplify such saves by checking which option can be taken to be right by default.

I've planned a tkpaint combined with bwise.

Category Bwise