Bresenham's line algorithm
BlitzMax Forums/BlitzMax Programming/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 |
   |