Code archives/Algorithms/Bresenham line tracing (2d)
This code has been declared by its author to be Public Domain code.
Download source code
| |||||
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!. | |||||
;################################################### ;Stephen Greener (aka Shagwana) line trace engine ;Shagwana@sublimegames.com ;www.sublimegames.com ;################################################### ;[Inline] = best when made inline functions! ;This will trace every coord in the line apart from the starting coord ;Can be used to continue drawing line in the started direction! ;################################################### ;Used information in the algo Type tBresenhemInfo Field iX1,iY1,iX2,iY2 ;Coords of the line in question (from 1->2) Field iX,iY ;Current location in the line! Field iDeltaX,iDeltaY ;Distance to travel Field iAbsDeltaX,iAbsDeltaY ;Postive version of the number above (for speed) Field iIncX,iIncY ;What to increase by Field iIncOne,iIncTwo Field iBuffer ;Counting buffer Field iXY ;Working buffer Field iType ;What type of line this is (X over Y or Y over Z) Field iStepsNeeded ;How many iterations this line will take Field iCurrentStep ;Current stop out of the needed steps! End Type ;Spawn a line to trace Function SpawnTrace.tBresenhemInfo(iX1,iY1,iX2,iY2) Local tTrace.tBresenhemInfo=New tBresenhemInfo ;Store the coords for the trace tTrace\iX1=iX1 tTrace\iY1=iY1 tTrace\iX2=iX2 tTrace\iY2=iY2 ;Current postion tTrace\iX=iX1 tTrace\iY=iY1 ;Calculate distance to travel (delta) tTrace\iDeltaX=iX1-iX2 ;Distance to travel tTrace\iDeltaY=iY1-iY2 tTrace\iAbsDeltaX=Abs(tTrace\iDeltaX) ;Postive versions tTrace\iAbsDeltaY=Abs(tTrace\iDeltaY) ;Set direction of the add in bresenhem line algo If tTrace\iDeltaX<0 tTrace\iIncX=1 Else tTrace\iIncX=-1 EndIf If tTrace\iDeltaY<0 tTrace\iIncY=1 Else tTrace\iIncY=-1 EndIf ;Setup the start of the algo loop If tTrace\iAbsDeltaX>tTrace\iAbsDeltaY tTrace\iType=0 tTrace\iStepsNeeded=tTrace\iAbsDeltaX tTrace\iIncOne=2*tTrace\iAbsDeltaY tTrace\iIncTwo=2*(tTrace\iAbsDeltaY-tTrace\iAbsDeltaX) tTrace\iBuffer=tTrace\iIncOne-tTrace\iAbsDeltaX tTrace\iXY=iY1 Else tTrace\iType=1 tTrace\iStepsNeeded=tTrace\iAbsDeltaY tTrace\iIncOne=2*tTrace\iAbsDeltaX tTrace\iIncTwo=2*(tTrace\iAbsDeltaX-tTrace\iAbsDeltaY) tTrace\iBuffer=tTrace\iIncOne-tTrace\iAbsDeltaY tTrace\iXY=iX1 EndIf tTrace\iCurrentStep=0 Return tTrace.tBresenhemInfo End Function ;Returns the number of steps needed to complete the trace! Function TraceStepsNeeded(tTrace.tBresenhemInfo) ;[Inline] If tTrace.tBresenhemInfo<>Null Return tTrace\iStepsNeeded EndIf End Function ;Will trace one along the given line, calculates the next coord towards the end coords Function ProcessTrace(tTrace.tBresenhemInfo) ;[Inline] If tTrace.tBresenhemInfo<>Null Local bDone=False If tTrace\iCurrentStep>=tTrace\iStepsNeeded bDone=True EndIf tTrace\iCurrentStep=tTrace\iCurrentStep+1 If tTrace\iType=0 If tTrace\iBuffer<0 tTrace\iBuffer=tTrace\iBuffer+tTrace\iIncOne Else tTrace\iBuffer=tTrace\iBuffer+tTrace\iIncTwo tTrace\iXY=tTrace\iXY+tTrace\iIncY EndIf tTrace\iX=tTrace\iX1+(tTrace\iCurrentStep*tTrace\iIncX) tTrace\iY=tTrace\iXY Else If tTrace\iBuffer<0 tTrace\iBuffer=tTrace\iBuffer+tTrace\iIncOne Else tTrace\iBuffer=tTrace\iBuffer+tTrace\iIncTwo tTrace\iXY=tTrace\iXY+tTrace\iIncX EndIf tTrace\iX=tTrace\iXY tTrace\iY=tTrace\iY1+(tTrace\iCurrentStep*tTrace\iIncY) EndIf Return bDone Else Return True EndIf End Function ;Return the current location in the trace! Function TraceXPos(tTrace.tBresenhemInfo) ;[Inline] If tTrace.tBresenhemInfo<>Null Return tTrace\iX EndIf End Function Function TraceYPos(tTrace.tBresenhemInfo) ;[Inline] If tTrace.tBresenhemInfo<>Null Return tTrace\iY EndIf End Function ;Free used resources - can be used to stop a trace early :) Function KillTrace(tTrace.tBresenhemInfo) If tTrace.tBresenhemInfo<>Null Delete tTrace.tBresenhemInfo tTrace.tBresenhemInfo=Null EndIf End Function ;################################################### ;A example of using the functions above ... Graphics 640,480,16,1 SetBuffer FrontBuffer() SeedRnd(MilliSecs()) Const TraceAmount=50 Dim Traces.tBresenhemInfo(TraceAmount) Dim TraceCounts(TraceAmount) For N=0 To TraceAmount-1 Traces.tBresenhemInfo(N)=SpawnTrace(Rand(GraphicsWidth()),Rand(GraphicsHeight()-17)+17,Rand(GraphicsWidth()),Rand(GraphicsHeight()-17)+17) TraceCounts(N)=TraceStepsNeeded(Traces.tBresenhemInfo(N)) Color 255,0,0 ;Big red rect at the start of a trace Rect Traces(N)\iX1-1,Traces(N)\iY1-1,3,3,False Rect Traces(N)\iX1-2,Traces(N)\iY1-2,5,5,False Color 0,255,0 ;Big green rect at the end of the trace Rect Traces(N)\iX2-1,Traces(N)\iY2-1,3,3,False Next ;Just to slow down the drawing of the line T=CreateTimer(30) iLoop=0 ;Will count the steps in the line drawing also Repeat VWait ;Comment out to see the speed :-) WaitTimer(T) ;Comment out to see the speed :-) SetBuffer FrontBuffer() bDone=True For tTrace.tBresenhemInfo = Each tBresenhemInfo If ProcessTrace(tTrace.tBresenhemInfo)=False bDone=False Color 128,128,128 Plot tTrace\iX,tTrace\iY Else KillTrace(tTrace.tBresenhemInfo) EndIf Next Color 0,0,0 Rect 0,0,GraphicsWidth(),16 Color 255,255,255 If bDone=True Text 0,0,"Lines all drawn [biggest was "+iLoop+" steps]" VWait Else iLoop=iLoop+1 Text 0,0,"Processing step ("+iLoop+")" EndIf Until KeyDown(1) End |
Comments
None.
Code Archives Forum