Bresenham's line algorithm

Anyone familiar with this? It's a basic algorithm to plot pixels in a straight line between to points, and it's the basis for how all modern computers perform a DrawLine function.

I found this code in an article on Wikipedia but it's written in C, of which I admit I am wholly ignorant on, and as such I am confused on how to convert some of the lines. Anyone want to do a BlitzMax conversion?

function line(x0, x1, y0, y1)
     boolean steep := abs(y1 - y0) > abs(x1 - x0)
     if steep then
         swap(x0, y0)
         swap(x1, y1)
     int deltax := abs(x1 - x0)
     int deltay := abs(y1 - y0)
     int error := 0
     int deltaerr := deltay
     int x := x0
     int y := y0
     if x0 < x1 then xstep := 1 else xstep := -1
     if y0 < y1 then ystep := 1 else ystep := -1
     if steep then plot(y,x) else plot(x,y)
     while x != x1
         x := x + xstep
         error := error + deltaerr
         if 2×error > deltax
             y := y + ystep
             error := error - deltax
         if steep then plot(y,x) else plot(x,y)

This example uses a modified LockedLine routine from a Blitz3D example (skidracers I think ?)

' Bresenham Line example (Draws to pixmap)

Const sw=640 , sh=480

Graphics sw,sh,0,NOSYNC
pix:TPixmap=CreatePixmap(sw,sh,PF_RGB888)

For Local n=1 To 100
	BLine pix,Rand(sw),Rand(sh),Rand(sw),Rand(sh),Rand(16777216)
Next

DrawPixmap pix,0,0
Flip ; WaitKey
End

Function BLine(pm:TPixmap,x1#,y1#,x2#,y2#,rgb)
	Local steps , xI#
	x2:-x1 ; y2:-y1
	If Abs(x2)>Abs(y2) steps = Abs(x2) Else steps = Abs(y2)
	xI = x2 / steps ; y2:/steps
	For x2 = 1 To steps
 		WritePixel pm,x1,y1,rgb
		x1:+xI ; y1:+y2
	Next
End Function

Heres one Shaggy made earlier in Blitz3d :) It lets you step through the line a pixel at a time.

http://www.blitzbasic.co.nz/codearcs/codearcs.php?code=148

Steve.

If I recall, bresenham's line routine is really very easy. There are also bresenhams routines which are very similar, for drawing circles and ovals.

I might be remembering wrong, but basically I think you figure out the difference between the start and end X coords, call that XDiff, then figure out the difference between the start and and Y coords, call that YDiff.

Then, for as long as those numbers are divisible by two without it becoming a decimal, you divide both by two to make them as small as possible.

Then you just do a simple loop where you count from 0 to the bigger of the two differences, adding the smaller difference to the counter each time. When the value is more than the the bigger difference, you `wrap it around` by subtracting the bigger difference and keeping the remainder as the next counter value.

If you plot that as you go, from 0 to the biggest difference (ie in X or in Y), you end up basically plotting one pixel for every row or column and then you jump to the next adjacent row/column when there is a wraparound of the counter.

I hope I got that right and explained it okay. It's basically to do with wrapping an integer counter around based on X2-X1 and Y2-Y1. It's all simple integer additions/subtractions, nothing else, no floating point, and for integer math it is fast. It also lets you have control over how every single pixel is drawn, individually - dotted lines, color changes, clipping, etc.

There is a more complex version that draws circles and ovals but I don't quite understand it.

Nowadays, though, there is possibly a good argument for saying that f
floating-point math is as fast as integer math. The `lockedline` routin that jb posted is a floating point algorithm and has nothing to do with bresenhams.

Bresenham's doesn't have anything to do with using floats and it doesn't have anything to do with having separate xsteps and ysteps detached from the loopcounter. It's meant to be really straightforward. Once you've set up the initial values, the main loop is basically stepping through one of the directions one pixel at a time, and then occasionally when there is counter overflow, stepping one pixel in the other direction. There is nothing more to it. I think that original program is cheating and is not `pure` bresenhams.

Here is some code which portrays the basic bresenhams algorithm, but it only draws when x2>x1 and y2>y1, it doesn't have the swappping and absolutes etc as seen in the one above. Easily adapted though. Also it is ENTIRELY integer math, not sneaky use of floats anywhere, which is how bresenhams is supposed to be used. If you're gunna use floats in it you might as well make an entire float routine which is really easy.

'Bresenham lines in BlitzMax
Strict
Graphics 640,480,0

Local x1,y1,x2,y2,xdiff,ydiff,xdiff2,ydiff2,counter,x,y:Int
Repeat
	Cls
	x1:Int=320
	y1:Int=240
	x2=MouseX()
	y2=MouseY()
	If (x1=x2) And (y1=y2)	'Avoid infinite loop
		SetColor Rand(0,255),Rand(0,255),Rand(0,255)
		Plot x1,y1
	Else
		xdiff=x2-x1	'Distances between start and end
		ydiff=y2-y1
		xdiff2=xdiff	'Backup
		ydiff2=ydiff
		While (xdiff & $FFFFFFFE=xdiff) And (ydiff & $FFFFFFFE=ydiff)	'If dividing by 2 still gives integers
			xdiff:/2	'Okay to make smaller
			ydiff:/2
		Wend
		If xdiff>ydiff	'If doing a line that is wider than tall
			y=y1
			counter=0
			For x=x1 To x1+(xdiff2-1) Step 1		'Move 1 pixel in X each loop
				SetColor Rand(0,255),Rand(0,255),Rand(0,255)
				Plot x,y
				counter:+ydiff
				If counter>xdiff
					counter:-xdiff
					y:+1		'Only move in Y when there is overflow
				EndIf
			Next	
		Else		'Doing a line that is taller than wide
			x=x1
			counter=0
			For y:Int=y1 To y1+(ydiff2-1) Step 1		'Move 1 pixel in Y each loop
				SetColor Rand(0,255),Rand(0,255),Rand(0,255)
				Plot x,y
				counter:+xdiff
				If counter>ydiff
					counter:-ydiff
					x:+1		'Only move in X when there is overflow
				EndIf
			Next
		EndIf		
	EndIf
	Flip
Until KeyHit(KEY_ESCAPE)
End

I think the floating point version is simpler, not sure if it's as fast or not.

Please note I just typed this into the message, this is entirely untested, but it's something along these lines.

'Floating point line-draw in BlitzMax
Strict
Graphics 640,480,0

Local x1,y1,x2,y2,xdiff,ydiff,xstep,ystep:Float
Local pixels,x,y:Int
Repeat
   x1=320
   y1=240
   x2=MouseX()
   y2=MouseY()
   xdiff=x2-x1
   ydiff=y2-y1
   If xdiff>ydiff
      If xdiff>0 Then xstep=1 else xstep=-1
      ystep=Abs(ydiff)/Abs(xdiff)
      if ydiff<0 then ystep=-ystep
      pixels=Abs(xdiff)
   Else
      If ydiff>0 Then ystep=1 else ystep=-1
      xstep=Abs(xdiff)/Abs(ydiff)
      if xdiff<0 then xstep=-xstep
      pixels=Abs(ydiff)
   EndIf
   For local counter:Int=0 to pixels-1
      Plot x1,y1
      x1:+xstep
      y1:+ystep
   Next
Until KeyHit(KEY_ESCAPE)

Ok, scrap the above code. Here is a simple conversion of the original program (the original one posted by Tachyon), converted to BlitzMax. It is indeed a proper Bresenham routine, using only integer math. I like they way it handles all the different drawing directions.

It's also good in that is, visually, seems to be handling also the problem of how/when/where the `steps` on the line are produced, so that the step at the beginning of the line is the same length as the step at the end. Usually you'd get one pixel plotted, then another string of pixels immediately offset.

I happened to need a linedraw routine for my own project so it was worth converting. Thanks Tachyon for sharing.

'Bresenham linedraw in BlitzMax, adapted from C code

Strict
Graphics 640,480,0
Repeat
	Cls
	Line(320,240,MouseX(),MouseY())
	Flip
Until KeyHit(KEY_ESCAPE)
End

Function Line(X1:Int,Y1:Int,X2:Int,Y2:Int)
	'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle
 	Local Steep:Int=Abs(Y2-Y1) > Abs(X2-X1)			'Boolean
	If Steep
		Local Temp:Int=X1; X1=Y1; Y1=Temp		'Swap X1,Y1
		Temp=X2; X2=Y2; Y2=Temp		'Swap X2,Y2
	EndIf
	Local DeltaX:Int=Abs(X2-X1)		'X Difference
	Local DeltaY:Int=Abs(Y2-Y1)		'Y Difference
	Local Error:Int=0		'Overflow counter
	Local DeltaError:Int=DeltaY		'Counter adder
	Local X:Int=X1		'Start at X1,Y1
	Local Y:Int=Y1		
	Local XStep:Int
	Local YStep:Int
	If X1<X2 Then XStep=1 Else XStep=-1	'Direction
	If Y1<Y2 Then YStep=1 Else YStep=-1	'Direction
	If Steep Then Plot(Y,X) Else Plot(X,Y)		'Draw
	While X<>X2
		X:+XStep		'Move in X
		Error:+DeltaError		'Add to counter
		If (Error Shl 1)>DeltaX		'Would it overflow?
			Y:+YStep		'Move in Y
			Error=Error-DeltaX		'Overflow/wrap the counter
		EndIf
		If Steep Then Plot(Y,X) Else Plot(X,Y)		'Draw
	Wend
End Function

I put this in the code archives for good measure