Bresenham like Circle and Ellipse functions

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|608\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Snippet Home -> Graphical Effects

Andy_A	Created : 24 January 2011 Edited : 24 January 2011 Language : Blitz Bresenham like Circle and Ellipse functions Both of these functions are faster than 'Oval'
I stumbled upon these algos on the internet and have made them into functions that will display filled and unfilled circles/ellipses - just like the Blitz "Oval()" function. However, scan line filled ovals are about 10x slower than Blitz's If you have lots of circles or ovals to plot, these functions will allow you to have 5 to 10 times as many ovals as Blitz 'Oval()'. It appears that the slower your machine the faster these functions will perform compared to 'Oval()'. In timing these compared to the intrinsic Blitz 'Oval()', I noticed that Blitz filled ovals are much faster that an unfilled oval. P.S. Maybe someone could code these in Cobra to see how they stack up to Graham's intrinsics. Circle: ;Source: ; https://homepage.smc.edu/kennedy_john/papers.htm ; https://homepage.smc.edu/kennedy_john/bcircle.pdf ; A Fast Bresenham Type Algorithm For Drawing Circles ; by ; John Kennedy ; Blitzplus/Blitz 3D port by Andy_A AppTitle "Bresenham circle" Graphics 800,600,32,2 SetBuffer BackBuffer() numIterations% = 100 LockBuffer GraphicsBuffer() st = MilliSecs() For i = 1 To numIterations PlotCircle(400, 300, 290, $FFE020, 1) Next et1# = MilliSecs()-st st = MilliSecs() For i = 1 To numIterations Oval 110, 10, 580, 580, 1 Next et2# = MilliSecs()-st UnlockBuffer Text 5, 5,"Avg/Circle: "+(et1/Float(numIterations))+"ms" Text 5,20," Avg/Oval: "+(et2/Float(numIterations))+"ms" Flip WaitMouse() End Function PlotCircle(CX%, CY%, R%, colr%, fill% = 0) Local X%, Y% Local XChange%, YChange% Local RadiusError% Color (colr And $FF0000) Shr 16, (colr And $FF00) Shr 8, colr And $FF X = R Y = 0 XChange = 1 - (R Shl 1) YChange = 1 RadiusError = 0 While X >= Y If fill <> 0 Then Line(CX-X, CY+Y, CX+X, CY+Y) ;used calc'd values to draw Line(CX-X, CY-Y, CX+X, CY-Y) ;scan lines from points Line(CX-Y, CY+X, CX+Y, CY+X) ;in opposite octants Line(CX-Y, CY-X, CX+Y, CY-X) Else WritePixelFast(CX+X, CY+Y, colr) ; {point in octant 1} WritePixelFast(CX-X, CY+Y, colr) ; {point in octant 4} WritePixelFast(CX-X, CY-Y, colr) ; {point in octant 5} WritePixelFast(CX+X, CY-Y, colr) ; {point in octant 8} WritePixelFast(CX+Y, CY+X, colr) ; {point in octant 2} WritePixelFast(CX-Y, CY+X, colr) ; {point in octant 3} WritePixelFast(CX-Y, CY-X, colr) ; {point in octant 6} WritePixelFast(CX+Y, CY-X, colr) ; {point in octant 7} End If Y = Y + 1 RadiusError = RadiusError + YChange YChange = YChange + 2 If (RadiusError Shl 1) + XChange > 0 Then X = X - 1 RadiusError = RadiusError + XChange XChange = XChange + 2 End If Wend End Function --v Ellipse: ;Source: ; https://homepage.smc.edu/kennedy_john/papers.htm ; https://homepage.smc.edu/kennedy_john/belipse.pdf ; A Fast Bresenham Type Algorithm For Drawing Ellipses ; by ; John Kennedy ; Blitzplus/Blitz 3D port by Andy_A AppTitle "Bresenham Ellipse" Graphics 800,600,32,2 SetBuffer BackBuffer() numRepeats% = 1000 LockBuffer GraphicsBuffer() st = MilliSecs() For i = 1 To numRepeats Ellipse(400, 300, 390, 290,$FFE020, 0) Next et1# = MilliSecs()-st st = MilliSecs() For i = 1 To numRepeats Oval 10, 10, 780, 580, 0 Next et2# = MilliSecs()-st UnlockBuffer Text 5, 5,"Avg/Ellipse: "+(et1/Float(numRepeats))+"ms" Text 5,20," Avg/Oval: "+(et2/Float(numRepeats))+"ms" Flip WaitMouse() End Function Ellipse(CX%, CY%, XRadius%, YRadius%, colr%, fill%); Local X%, Y% Local XChange%, YChange% Local EllipseError% Local TwoASquare%, TwoBSquare% Local StoppingX%, StoppingY% Color (colr And $FF0000) Shr 16, (colr And $FF00) Shr 8, colr And $FF TwoASquare = (XRadiusXRadius) Shl 1 TwoBSquare = (YRadiusYRadius) Shl 1 X = XRadius Y = 0 XChange = YRadiusYRadius(1-(XRadius Shl 1)) YChange = XRadiusXRadius EllipseError = 0 StoppingX = TwoBSquareXRadius StoppingY = 0 While StoppingX >= StoppingY ; do {1st set of points, y' > -1} If fill <> 0 Then Line(CX-X, CY+Y, CX+X, CY+Y) ; used calc'd points to draw scan Line(CX-X, CY-Y, CX+X, CY-Y) ; lines from opposite quadrants Else WritePixelFast(CX+X, CY+Y, colr) ; {point in quadrant 1} WritePixelFast(CX-X, CY+Y, colr) ; {point in quadrant 2} WritePixelFast(CX-X, CY-Y, colr) ; {point in quadrant 3} WritePixelFast(CX+X, CY-Y, colr) ; {point in quadrant 4} End If Y = Y + 1 StoppingY = StoppingY + TwoASquare EllipseError = EllipseError + YChange YChange = YChange + TwoASquare If (EllipseError Shl 1) + XChange > 0 Then X = X - 1 StoppingX = StoppingX - TwoBSquare EllipseError = EllipseError + XChange XChange = XChange + TwoBSquare End If Wend ;{ 1st set of points is done; start the 2nd set of points } X = 0 Y = YRadius XChange = YRadiusYRadius YChange = XRadiusXRadius(1 - (YRadius Shl 1)) EllipseError = 0 StoppingX = 0 StoppingY = TwoASquareYRadius While StoppingX <= StoppingY ;do {2nd set of points, y' < -1} If fill <> 0 Then Line(CX-X, CY+Y, CX+X, CY+Y) ; used calc'd points to draw scan Line(CX-X, CY-Y, CX+X, CY-Y) ; lines from opposite quadrants Else WritePixelFast(CX+X, CY+Y, colr) ; {point in quadrant 1} WritePixelFast(CX-X, CY+Y, colr) ; {point in quadrant 2} WritePixelFast(CX-X, CY-Y, colr) ; {point in quadrant 3} WritePixelFast(CX+X, CY-Y, colr) ; {point in quadrant 4} End If X = X + 1 StoppingX = StoppingX + TwoBSquare EllipseError = EllipseError + XChange XChange = XChange + TwoBSquare If (EllipseError Shl 1) + YChange > 0 Then Y = Y - 1 StoppingY = StoppingY - TwoASquare EllipseError = EllipseError + YChange YChange = YChange + TwoASquare End If Wend End Function --v

Comments
Wednesday, 26 January 2011, 04:42
Jayenkai	Can't argue there! Them's some nice circles!!
Wednesday, 26 January 2011, 12:53
Andy_A	I'm blushing... No one ever commented on my circles!

Bresenham like Circle and Ellipse functions

Comments