hi,
I've recently been working with the 2d drawing commands
and discovered that LineXY() is very slow (i'm using 3.81)
so i decided to write my own line algorithm and stumbled
across a bresenham tutorial, to my delight it is much faster
than LineXY. I wonder if this has been speeded up since
3.81?
While i was reading the tutorial i decided to also write out a
circle and ellipse algorithm because i noticed the Circle() and
Ellipse() commands only allow filling the shapes. After
optimizing these are now the same speed as the original
commands! But now they have the option for outline.
So if anyone might have a use for these I am posting them here!
Code: Select all
;-
; Bresenham's Line, Circle and Ellipse Algorithms -> Purebasic 3.81
; For convenience all variables in these functions starts with "b".
; Author: hagibaba.
; Date: 09/7/05.
;Fps Globals
Global Fps, Timer, NewTime, Frames
Declare DisplayFps()
;Declares
Declare DrawCircle(bcenter_x, bcenter_y, bradi, bfill, bclr)
Declare DrawEllipse(bcenter_x, bcenter_y, bradi_x, bradi_y, bfill, bclr)
Declare DrawLine(bplot_x1, bplot_y1, bplot_x2, bplot_y2, bclr)
Declare PlotLineX(bplot_x1, bplot_x2, bplot_y, bclr)
Declare PlotLineY(bplot_x, bplot_y1, bplot_y2, bclr)
Declare PlotPixel(bplot_x, bplot_y, bclr)
;Constants
#Win = 0
#WSM = #PB_Window_SystemMenu
#WSC = #PB_Window_ScreenCentered
;Screen dimensions, used in PlotPixel
#Xmin = 0
#Ymin = 0
#Xmax = 640
#Ymax = 480
;- Open Window
If InitSprite() ;init directdraw 7
If OpenWindow(#Win,#Xmin-3,#Ymin-3,#Xmax,#Ymax,"BresAlgorithms",#WSM|#WSC)
If OpenWindowedScreen(WindowID(#Win),#Xmin,#Ymin,#Xmax,#Ymax,0,0,0)
Repeat
EventID = WindowEvent()
MouseX = WindowMouseX(#Win)
MouseY = WindowMouseY(#Win)
Select EventID
Case #WM_LBUTTONDOWN ;leftmouse close
Quit=1
Case #PB_Event_CloseWindow ;close button
Quit=1
EndSelect
StartDrawing(ScreenOutput())
DrawEllipse(MouseX, MouseY, MouseX/2, MouseY/2, 1, RGB(64,64,192))
DrawEllipse(MouseX, MouseY, MouseX/2, MouseY/2, 0, RGB(64,192,64))
DrawCircle(MouseX, MouseY, MouseX/3, 1, RGB(192,192,64))
DrawCircle(MouseX, MouseY, MouseX/3, 0, RGB(192,64,64))
DrawLine(MouseX/2,MouseY/2,MouseX,MouseY,RGB(0,0,220))
StopDrawing()
DisplayFps()
FlipBuffers()
ClearScreen(RGB(0,0,0)) ;black
Until Quit=1
EndIf
EndIf
EndIf
;- Start Functions
Procedure DisplayFps()
; DrawingBuffer.pb -> http://www.purearea.net/
; Author: ??
; Display Frames-per-second count as returned from GetTickCount,
; number of milliseconds that have elapsed since Windows was started.
Frames + 1
NewTime = GetTickCount_()
If NewTime - Timer > 1000
Fps = Frames
Frames = 0
Timer = NewTime
EndIf
StartDrawing(ScreenOutput())
DrawingMode(1) : FrontColor(RGB(250, 250, 250)) ;white
DrawText(5, 5, "Fps " + Str(Fps)) ;top-left
StopDrawing()
EndProcedure
Procedure DrawCircle(bcenter_x, bcenter_y, bradi, bfill, bclr)
; Circle algorithm in Pascal -> http://www.gamedev.net/
; An implementation of Bresenham's circle algorithm.
; By Mark Feldman.
;
; Calculates the locations of the pixels in the first 45 degrees
; and draws a pixel for each of the 8 octants of the circle.
; It assumes that the circle is centered on the origin.
;
; Includes a fill parameter, 0 for outline and 1 for fill.
;initialize decision variable and circle points
bdi = 3 - (bradi << 1)
bxi = bradi
byi = 0
;draw the first octant, until y = x
While byi <= bxi
If bfill > 0 ;draw lines across inner octants, w-nw>e-ne and w-sw>e-se
PlotLineX(bcenter_x - bxi, bcenter_x + bxi, bcenter_y - byi, bclr)
PlotLineX(bcenter_x - bxi, bcenter_x + bxi, bcenter_y + byi, bclr)
If bdi >= 0 ;if x changed fill outer octants, n-nw>n-ne and s-sw>s-se
PlotLineX(bcenter_x - byi, bcenter_x + byi, bcenter_y - bxi, bclr)
PlotLineX(bcenter_x - byi, bcenter_x + byi, bcenter_y + bxi, bclr)
EndIf
Else ;draw the 8 circle pixels, for each octant
PlotPixel(bcenter_x - byi, bcenter_y - bxi, bclr) ;n-nw
PlotPixel(bcenter_x + byi, bcenter_y - bxi, bclr) ;n-ne
PlotPixel(bcenter_x - bxi, bcenter_y - byi, bclr) ;w-nw
PlotPixel(bcenter_x + bxi, bcenter_y - byi, bclr) ;e-ne
PlotPixel(bcenter_x - bxi, bcenter_y + byi, bclr) ;e-sw
PlotPixel(bcenter_x + bxi, bcenter_y + byi, bclr) ;e-se
PlotPixel(bcenter_x - byi, bcenter_y + bxi, bclr) ;s-sw
PlotPixel(bcenter_x + byi, bcenter_y + bxi, bclr) ;s-se
EndIf
If bdi < 0
bdi = bdi + (byi << 2) + 6
Else
bdi = bdi + (byi - bxi) << 2 + 10
bxi = bxi - 1 ;move left
EndIf
byi = byi + 1 ;always move up
Wend
EndProcedure
Procedure DrawEllipse(bcenter_x, bcenter_y, bradi_x, bradi_y, bfill, bclr)
; Ellipse algorithm in C -> http://www.programmersheaven.com/
; Bresenham's algorithm from IEEE CG&A Sept 1984 p.24
; Jack C. Morrison - Jet Propulsion Laboratory
;
; A few requests for ellipses have prompted me to include this code. It
; draws ellipses (including circles, of course) of varying line width
; on a SUN bitmap display. (It's part of a paint-type program). I don't
; know how this compares to the earlier posting of an ellipse algorithm,
; but it's fairly fast.
;
; Includes a fill parameter, 0 for outline and 1 for fill.
;initialize intermediate terms to speed up loop
bxi = bradi_x * bradi_x
bx1 = bxi << 1
bx2 = bx1 << 1
byi = bradi_y * bradi_y
by1 = byi << 1
by2 = by1 << 1
bf1 = bradi_x * by1
bf2 = bf1 << 1
bdi = 0
;error terms and ellipse points, can reuse bxi and byi
bd1 = bx1 - bf1 + (byi >> 1)
bd2 = (bxi >> 1) - bf2 + by1
bxi = bradi_x
byi = 0
;draw top right quadrant, until slope = -1
While bd2 < 0
If bfill > 0 ;draw lines across inner octants, w-nw>e-ne and w-sw>e-se
PlotLineX(bcenter_x - bxi, bcenter_x + bxi, bcenter_y - byi, bclr)
PlotLineX(bcenter_x - bxi, bcenter_x + bxi, bcenter_y + byi, bclr)
Else ;draw 4 points using symmetry
PlotPixel(bcenter_x + bxi, bcenter_y + byi, bclr) ;e-se
PlotPixel(bcenter_x + bxi, bcenter_y - byi, bclr) ;e-ne
PlotPixel(bcenter_x - bxi, bcenter_y + byi, bclr) ;w-sw
PlotPixel(bcenter_x - bxi, bcenter_y - byi, bclr) ;w-nw
EndIf
If bd1 < 0 ;move straight up
bd1 = bd1 + bdi + bx1
bd2 = bd2 + bdi
Else ;move up and left
bxi = bxi - 1
bf2 = bf2 - by2
bd1 = bd1 + bdi + bx1 - bf2
bd2 = bd2 + bdi + by1 - bf2
EndIf
byi = byi + 1 ;always move up
bdi = bdi + bx2
Wend
;draw rest of top right quadrant, until x = 0
While bxi >= 0
If bfill > 0 ;draw lines across outer octants, n-nw>n-ne and s-sw>s-se
If bd2 < 0 ;if y changed fill outer octants, no overlap
PlotLineX(bcenter_x - bxi, bcenter_x + bxi, bcenter_y - byi, bclr)
PlotLineX(bcenter_x - bxi, bcenter_x + bxi, bcenter_y + byi, bclr)
EndIf
Else ;draw 4 points using symmetry
PlotPixel(bcenter_x + bxi, bcenter_y + byi, bclr) ;s-se
PlotPixel(bcenter_x + bxi, bcenter_y - byi, bclr) ;n-ne
PlotPixel(bcenter_x - bxi, bcenter_y + byi, bclr) ;s-sw
PlotPixel(bcenter_x - bxi, bcenter_y - byi, bclr) ;n-nw
EndIf
If bd2 < 0 ;move up and left
byi = byi + 1
bdi = bdi + bx2
bd2 = bd2 + bdi + by1 - bf2
Else ;move straight left
bd2 = bd2 + by1 - bf2
EndIf
bxi = bxi - 1 ;always move left
bf2 = bf2 - by2
Wend
EndProcedure
Procedure DrawLine(bplot_x1, bplot_y1, bplot_x2, bplot_y2, bclr)
; Line drawing algorithm in Pascal -> http://www.gamedev.net/
; A general-purpose implementation of Bresenham's line algorithm.
; By Mark Feldman.
;deltax and deltay
bdx = Abs(bplot_x2 - bplot_x1)
bdy = Abs(bplot_y2 - bplot_y1)
;always 1
bx2 = 1
by2 = 1
;initialize vars based on which is the independent variable
If bdx >= bdy ;x is independent variable
bnp = bdx + 1
bd1 = bdy << 1
bdi = bd1 - bdx
bd2 = (bdy - bdx) << 1
bx1 = 1
by1 = 0
Else ;y is independent variable
bnp = bdy + 1
bd1 = bdx << 1
bdi = bd1 - bdy
bd2 = (bdx - bdy) << 1
bx1 = 0
by1 = 1
EndIf
;make sure x and y move in the right directions
If bplot_x1 > bplot_x2
bx1 = -bx1
bx2 = -bx2
EndIf
If bplot_y1 > bplot_y2
by1 = -by1
by2 = -by2
EndIf
;start drawing at
bxi = bplot_x1
byi = bplot_y1
;draw the pixels
For bli = 1 To bnp
PlotPixel(bxi, byi, bclr)
If bdi < 0
bdi = bdi + bd1
bxi = bxi + bx1
byi = byi + by1
Else
bdi = bdi + bd2
bxi = bxi + bx2
byi = byi + by2
EndIf
Next bli
EndProcedure
Procedure PlotLineX(bplot_x1, bplot_x2, bplot_y, bclr)
; Plot a line of pixels across the screen from x1 To x2 at the y value.
; Since only increments are involved it is optimised.
If bplot_x2 < bplot_x1 ;if x2 less, switch plot directions
bli = bplot_x2 ;store = x2
bplot_x2 = bplot_x1 ;x2 = x1
bplot_x1 = bli ;x1 = store
EndIf
For bli = bplot_x1 To bplot_x2 ;Step 2
PlotPixel(bli, bplot_y, bclr)
Next bli
EndProcedure
Procedure PlotLineY(bplot_x, bplot_y1, bplot_y2, bclr)
; Plot a line of pixels down the screen from y1 To y2 at the x value.
; Since only increments are involved it is optimised.
If bplot_y2 < bplot_y1 ;if y2 less, switch plot directions
bli = bplot_y2 ;store = y2
bplot_y2 = bplot_y1 ;y2 = y1
bplot_y1 = bli ;y1 = store
EndIf
For bli = bplot_y1 To bplot_y2
PlotPixel(bplot_x, bli, bclr)
Next bli
EndProcedure
Procedure PlotPixel(bplot_x, bplot_y, bclr)
; Plot a pixel if values are inside this area, screen dimensions here.
; Shorten code and prevent screen garbage.
If bplot_x >= #Xmin And bplot_x < #Xmax
If bplot_y >= #Ymin And bplot_y < #Ymax
Plot(bplot_x, bplot_y, bclr)
EndIf
EndIf
EndProcedure
