December 04, 2020, 11:47:09 AM

Author Topic: [bb] Bresenham line tracing (2d) by Shagwana [ 1+ years ago ]  (Read 455 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
Title : Bresenham line tracing (2d)
Author : Shagwana
Posted : 1+ years ago

Description : This is for manily use in 2d, Its a nice example of how the bresenham line can be processed outside of a closed loop :). Possible uses include :- predicting the path of objects, Line-of-sight tracing, Collision prediction/detection between two or more objects or even just drawing lines like I have done here!. Code is provided as is, and maybe of use to someone!.  

Code :
Code: BlitzBasic
  1. ;###################################################
  2. ;Stephen Greener (aka Shagwana) line trace engine
  3. ;Shagwana@sublimegames.com
  4. ;www.sublimegames.com
  5. ;###################################################
  6. ;[Inline] = best when made inline functions!
  7. ;This will trace every coord in the line apart from the starting coord
  8. ;Can be used to continue drawing line in the started direction!
  9. ;###################################################
  10.  
  11. ;Used information in the algo
  12. Type tBresenhemInfo
  13.         Field iX1,iY1,iX2,iY2           ;Coords of the line in question (from 1->2)
  14.         Field iX,iY                                     ;Current location in the line!
  15.         Field iDeltaX,iDeltaY           ;Distance to travel
  16.         Field iAbsDeltaX,iAbsDeltaY     ;Postive version of the number above (for speed)
  17.         Field iIncX,iIncY                       ;What to increase by
  18.         Field iIncOne,iIncTwo  
  19.         Field iBuffer                           ;Counting buffer
  20.         Field iXY                                       ;Working buffer
  21.         Field iType                                     ;What type of line this is (X over Y or Y over Z)
  22.         Field iStepsNeeded                      ;How many iterations this line will take
  23.         Field iCurrentStep                      ;Current stop out of the needed steps!
  24.         End Type
  25.  
  26. ;Spawn a line to trace
  27. Function SpawnTrace.tBresenhemInfo(iX1,iY1,iX2,iY2)
  28.         Local tTrace.tBresenhemInfo=New tBresenhemInfo
  29.         ;Store the coords for the trace
  30.         tTraceiX1=iX1
  31.         tTraceiY1=iY1
  32.         tTraceiX2=iX2
  33.         tTraceiY2=iY2
  34.         ;Current postion
  35.         tTraceiX=iX1
  36.         tTraceiY=iY1
  37.         ;Calculate distance to travel (delta)
  38.         tTraceiDeltaX=iX1-iX2                                   ;Distance to travel
  39.         tTraceiDeltaY=iY1-iY2
  40.         tTraceiAbsDeltaX=Abs(tTraceiDeltaX)     ;Postive versions
  41.         tTraceiAbsDeltaY=Abs(tTraceiDeltaY)
  42.         ;Set direction of the add in bresenhem line algo
  43.         If tTraceiDeltaX<0
  44.                 tTraceiIncX=1
  45.                 Else
  46.                 tTraceiIncX=-1
  47.                 EndIf
  48.         If tTraceiDeltaY<0
  49.                 tTraceiIncY=1
  50.                 Else
  51.                 tTraceiIncY=-1
  52.                 EndIf  
  53.         ;Setup the start of the algo loop
  54.         If tTraceiAbsDeltaX>tTraceiAbsDeltaY
  55.                 tTraceiType=0
  56.                 tTraceiStepsNeeded=tTraceiAbsDeltaX
  57.                 tTraceiIncOne=2*tTraceiAbsDeltaY
  58.                 tTraceiIncTwo=2*(tTraceiAbsDeltaY-tTraceiAbsDeltaX)
  59.                 tTraceiBuffer=tTraceiIncOne-tTraceiAbsDeltaX
  60.                 tTraceiXY=iY1
  61.                 Else
  62.                 tTraceiType=1
  63.                 tTraceiStepsNeeded=tTraceiAbsDeltaY
  64.                 tTraceiIncOne=2*tTraceiAbsDeltaX
  65.                 tTraceiIncTwo=2*(tTraceiAbsDeltaX-tTraceiAbsDeltaY)
  66.                 tTraceiBuffer=tTraceiIncOne-tTraceiAbsDeltaY
  67.                 tTraceiXY=iX1
  68.                 EndIf
  69.         tTraceiCurrentStep=0
  70.         Return tTrace.tBresenhemInfo
  71.         End Function
  72.        
  73. ;Returns the number of steps needed to complete the trace!
  74. Function TraceStepsNeeded(tTrace.tBresenhemInfo) ;[Inline]
  75.         If tTrace.tBresenhemInfo<>Null
  76.                 Return tTraceiStepsNeeded
  77.                 EndIf
  78.         End Function
  79.  
  80. ;Will trace one along the given line, calculates the next coord towards the end coords
  81. Function ProcessTrace(tTrace.tBresenhemInfo) ;[Inline]
  82.         If tTrace.tBresenhemInfo<>Null
  83.                 Local bDone=False
  84.                 If tTraceiCurrentStep>=tTraceiStepsNeeded
  85.                         bDone=True
  86.                         EndIf
  87.                 tTraceiCurrentStep=tTraceiCurrentStep+1
  88.                 If tTraceiType=0
  89.                         If tTraceiBuffer<0
  90.                                 tTraceiBuffer=tTraceiBuffer+tTraceiIncOne
  91.                                 Else
  92.                                 tTraceiBuffer=tTraceiBuffer+tTraceiIncTwo
  93.                                 tTraceiXY=tTraceiXY+tTraceiIncY
  94.                                 EndIf
  95.                         tTraceiX=tTraceiX1+(tTraceiCurrentStep*tTraceiIncX)
  96.                         tTraceiY=tTraceiXY
  97.                         Else                           
  98.                         If tTraceiBuffer<0
  99.                                 tTraceiBuffer=tTraceiBuffer+tTraceiIncOne
  100.                                 Else
  101.                                 tTraceiBuffer=tTraceiBuffer+tTraceiIncTwo
  102.                                 tTraceiXY=tTraceiXY+tTraceiIncX
  103.                                 EndIf
  104.                         tTraceiX=tTraceiXY     
  105.                         tTraceiY=tTraceiY1+(tTraceiCurrentStep*tTraceiIncY)
  106.                         EndIf                  
  107.                 Return bDone
  108.                 Else
  109.                 Return True
  110.                 EndIf
  111.         End Function
  112.  
  113.  
  114. ;Return the current location in the trace!     
  115. Function TraceXPos(tTrace.tBresenhemInfo) ;[Inline]    
  116.         If tTrace.tBresenhemInfo<>Null
  117.                 Return tTraceiX
  118.                 EndIf
  119.         End Function    
  120. Function TraceYPos(tTrace.tBresenhemInfo) ;[Inline]
  121.         If tTrace.tBresenhemInfo<>Null
  122.                 Return tTraceiY
  123.                 EndIf
  124.         End Function   
  125.        
  126. ;Free used resources - can be used to stop a trace early :)
  127. Function KillTrace(tTrace.tBresenhemInfo)      
  128.         If tTrace.tBresenhemInfo<>Null
  129.                 Delete tTrace.tBresenhemInfo
  130.                 tTrace.tBresenhemInfo=Null
  131.                 EndIf
  132.         End Function
  133.        
  134. ;###################################################
  135. ;A example of using the functions above ...
  136.  
  137. Graphics 640,480,16,1
  138. SetBuffer FrontBuffer()
  139.  
  140. SeedRnd(MilliSecs())
  141.  
  142. Const TraceAmount=50
  143.  
  144. Dim Traces.tBresenhemInfo(TraceAmount)
  145. Dim TraceCounts(TraceAmount)
  146. For N=0 To TraceAmount-1
  147.         Traces.tBresenhemInfo(N)=SpawnTrace(Rand(GraphicsWidth()),Rand(GraphicsHeight()-17)+17,Rand(GraphicsWidth()),Rand(GraphicsHeight()-17)+17)
  148.         TraceCounts(N)=TraceStepsNeeded(Traces.tBresenhemInfo(N))
  149.        
  150.         Color 255,0,0                                                                           ;Big red rect at the start of a trace
  151.         Rect Traces(N)iX1-1,Traces(N)iY1-1,3,3,False   
  152.         Rect Traces(N)iX1-2,Traces(N)iY1-2,5,5,False
  153.         Color 0,255,0                                                                           ;Big green rect at the end of the trace
  154.         Rect Traces(N)iX2-1,Traces(N)iY2-1,3,3,False
  155.        
  156.         Next
  157.  
  158.  
  159.  
  160. ;Just to slow down the drawing of the line
  161. T=CreateTimer(30)
  162.  
  163. iLoop=0                 ;Will count the steps in the line drawing also
  164. Repeat
  165.  
  166.         VWait                                           ;Comment out to see the speed :-)
  167.         WaitTimer(T)                            ;Comment out to see the speed :-)
  168.         SetBuffer FrontBuffer()
  169.  
  170.         bDone=True
  171.         For tTrace.tBresenhemInfo =  Each tBresenhemInfo
  172.                 If ProcessTrace(tTrace.tBresenhemInfo)=False   
  173.                         bDone=False
  174.                         Color 128,128,128
  175.                         Plot tTraceiX,tTraceiY                 
  176.                         Else
  177.                         KillTrace(tTrace.tBresenhemInfo)
  178.                         EndIf
  179.                 Next
  180.  
  181.         Color 0,0,0
  182.         Rect 0,0,GraphicsWidth(),16
  183.         Color 255,255,255
  184.         If bDone=True
  185.                 Text 0,0,"Lines all drawn [biggest was "+iLoop+" steps]"
  186.                 VWait
  187.                 Else
  188.                 iLoop=iLoop+1  
  189.                 Text 0,0,"Processing step ("+iLoop+")"
  190.                 EndIf
  191.  
  192.         Until KeyDown(1)
  193. End    


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal