[bmx]Liang Barsky line clipping algorythm

Started by TomToad, July 10, 2017, 18:30:48

Previous topic - Next topic

TomToad

Didn't see this in the archives.  This will clip a line to an axis aligned bounding box using Liang Barsky algorythm.  Adapted the code from http://www.skytopia.com/project/articles/compsci/clipping.html
Also includes example under function to show use.
SuperStrict
Rem
// Liang-Barsky Function by Daniel White @ http://www.skytopia.com/project/articles/compsci/clipping.html
// This Function inputs 8 numbers, And outputs 4 New numbers (plus a boolean value To say whether the clipped line is drawn at all).
//
** Modified by TomToad for BlitzMax

bool LiangBarsky (Double edgeLeft, Double edgeRight, Double edgeBottom, Double edgeTop,   // Define the x/y clipping values For the border.
                  Double x0src, Double y0src, Double x1src, Double y1src,                 // Define the start And End points of the line.
                  Double &x0clip, Double &y0clip, Double &x1clip, Double &y1clip)         // The output values, so declare these outside.
{
End Rem
Function LiangBarsky:Int (edgeLeft:Double, edgeRight:Double, edgeBottom:Double, edgeTop:Double, ..
x0src:Double, y0src:Double,x1src:Double, y1src:Double, ..
x0clip:Double Var, y0clip:Double Var, x1clip:Double Var, y1clip:Double Var)   
    Local t0:Double = 0.0,   t1:Double = 1.0
    Local xdelta:Double = x1src-x0src
    Local ydelta:Double = y1src-y0src
    Local p:Double,q:Double,r:Double

    For Local edge:Int = 0 Until 4   '// Traverse through Left, Right, bottom, top edges.
        If (edge=0) Then  p = -xdelta;    q = -(edgeLeft-x0src);
        If (edge=1) Then  p = xdelta;     q =  (edgeRight-x0src);
        If (edge=2) Then  p = -ydelta;    q = -(edgeBottom-y0src);
        If (edge=3) Then  p = ydelta;     q =  (edgeTop-y0src);   
        r = q/p;
        If(p=0 And q<0) Then Return False;   '// Don't draw line at all. (parallel line outside)

        If(p<0)
            If(r>t1)
Return False;        ' // Don't draw line at all.
            Else If(r>t0)
t0=r;
End If           '// Line is clipped!
        Else If(p>0)
            If(r<t0)
Return False;      '// Don't draw line at all.
            Else If(r<t1)
t1=r;         '// Line is clipped!
End If
        End If
    Next

    x0clip = x0src + t0*xdelta;
    y0clip = y0src + t0*ydelta;
    x1clip = x0src + t1*xdelta;
    y1clip = y0src + t1*ydelta;

    Return True;        '// (clipped) line is drawn
End Function

Graphics 800,600
Local x1:Double, x2:Double, y1:Double, y2:Double
Local seed:Int = MilliSecs()
Local Visible:Int

While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()
Local MX:Int = MouseX() 'get the mouse coordinates
Local MY:Int = MouseY()

Cls
SetColor 255,0,0
SeedRnd(seed) 'we will use a common seed each loop so lines will plot in same place
For Local i:Int = 0 To 10
DrawLine Rand(0,799),Rand(0,599),Rand(0,799),Rand(0,599) 'first draw all the lines in red
Next
SetColor 255,255,255
DrawRect mx-100,my-75,200,150 'draw a white rectangle where the lines will be clipped
SetColor 0,255,0
SeedRnd(seed)
For Local i:Int = 0 To 10
'call function to clip line. 
' -first four paramters is the Left, Right, top, And bottom of AABB
' -second four parameters are the line to be drawn
' -third four parameters are passed by reference and will contain the endpoints of the clipped line
'    upon return from the function
' -will return true if any part of the line is within the AABB (so no need to draw anything outside)
Visible = LiangBarsky(mx-100,mx+99,my-75,my+74, ..
Rand(0,799),Rand(0,599),Rand(0,799),Rand(0,599), ..
x1, y1, x2, y2)
If Visible Then DrawLine x1,y1,x2,y2 'Draw all the clipped lines in green
Next
Flip
If KeyHit(KEY_SPACE) Then seed = MilliSecs() 'press SPACE to generate new lines
Wend

------------------------------------------------
8 rabbits equals 1 rabbyte.