Draw Hollow Ellipse Pixel by Pixel with Integer Math

This code has been declared by its author to be Public Domain code.

Draw Hollow Ellipse Pixel by Pixel with Integer Math by ImaginaryHuman

2005

This draws an unfilled ellipse one pixel at a time and uses only integer math to do it, except for one small part where two lines need to do a floating point calculation. Even so, there is no trigonometry involved. The ellipse is not rotatable unless the output method (ie Plot) can be drawn with rotated coordinates as part of the graphics system (ie rotating the camera, etc).

'Midpoint ellipse algorithm

Strict
Graphics 640,480,0

Local xCenter:Int=320
Local yCenter:Int=240
Local Rx,Ry:Int
Local p,px,py,x,y:Int
Local Rx2,Ry2,twoRx2,twoRy2:Int
Local pFloat:Float
Repeat
        Cls
        If MouseDown(1)
                xCenter=MouseX()
                yCenter=MouseY()
        EndIf
        Rx=Abs(xCenter-MouseX())
        Ry=Abs(yCenter-MouseY())
        DrawText String(Rx)+" x "+String(Ry),20,20
        Rx2=Rx*Rx
        Ry2=Ry*Ry
        twoRx2=Rx2 Shl 1
        twoRy2=Ry2 Shl 1
        'Region 1
        x=0
        y=Ry
        Plot xCenter+x,yCenter+y
        Plot xCenter-x,yCenter+y
        Plot xCenter+x,yCenter-y
        Plot xCenter-x,yCenter-y
        pFloat=(Ry2-(Rx2*Ry))+(0.25*Rx2)
        p=Int(pFloat)
        If pFloat Mod 1.0>=0.5 Then p:+1
        px=0
        py=twoRx2*y
        While px<py
                x:+1
                px:+twoRy2
                If p>=0
                        y:-1
                        py:-twoRx2
                EndIf
                If p<0 Then p:+Ry2+px Else p:+Ry2+px-py
                Plot xCenter+x,yCenter+y
                Plot xCenter-x,yCenter+y
                Plot xCenter+x,yCenter-y
                Plot xCenter-x,yCenter-y
        Wend
        'Region 2
        pFloat=(Ry2*(x+0.5)*(x+0.5))+(Rx2*(y-1.0)*(y-1.0))-(Rx2*(Float(Ry2)))
        p=Int(pFloat)
        If pFloat Mod 1.0>=0.5 Then p:+1
        While y>0
                y:-1
                py:-twoRx2
                If p<=0
                        x:+1
                        px:+twoRy2
                EndIf
                If p>0 Then p:+Rx2-py Else p:+Rx2-py+px
                Plot xCenter+x,yCenter+y
                Plot xCenter-x,yCenter+y
                Plot xCenter+x,yCenter-y
                Plot xCenter-x,yCenter-y
        Wend
        Flip
Until KeyHit(KEY_ESCAPE)
End

Comments

ImaginaryHuman

2005

This is meant to be in the BlitzMax code section. Sorry about that.

Rck

2005

;Midpoint ellipse algorithm

Graphics 640,480,0,2

Local xCenter% = 320
Local yCenter% = 240
Local Rx%, Ry%
Local p%, px%, py%, x%, y%
Local Rx2%, Ry2%, twoRx2%, twoRy2%
Local pFloat#

Repeat
        Cls
		WaitEvent()
		
		
        If MouseDown(1)
            xCenter = MouseX()
            yCenter = MouseY()
        EndIf
        Rx = Abs(xCenter - MouseX())
        Ry = Abs(yCenter - MouseY())
		
        Rx2 = Rx * Rx
        Ry2 = Ry * Ry
        twoRx2 = Rx2 Shl 1
        twoRy2 = Ry2 Shl 1
		
		msStart = MilliSecs()
		
        ;Region 1
        x = 0
        y = Ry

        Plot xCenter + x, yCenter + y
        Plot xCenter - x, yCenter + y
        Plot xCenter + x, yCenter - y
        Plot xCenter - x, yCenter - y
        pFloat = (Ry2 - (Rx2 * Ry)) + (0.25 * Rx2)
        p = Int(pFloat)
        If pFloat Mod 1.0 >= 0.5 Then p = p + 1

        px = 0
        py = twoRx2 * y

        While px < py
                x = x + 1
                px = px + twoRy2
                If p >= 0
                        y = y - 1
                        py = py - twoRx2
                EndIf
                If p < 0 Then p = p + Ry2 + px Else p = p + Ry2 + px - py
                Plot xCenter + x, yCenter + y
                Plot xCenter - x, yCenter + y
                Plot xCenter + x, yCenter - y
                Plot xCenter - x, yCenter - y
        Wend

        ;Region 2
        pFloat = (Ry2 * (x + 0.5) * (x + 0.5)) + (Rx2 * (y - 1.0) * (y - 1.0)) - (Rx2 * (Float(Ry2)))
        p = Int(pFloat)
        If pFloat Mod 1.0 >= 0.5 Then p = p + 1
        While y > 0
                y = y - 1
                py = py - twoRx2
                If p <= 0
                        x = x +1
                        px = px + twoRy2
                EndIf
                If p > 0 Then p = p + Rx2 - py Else p = p + Rx2 - py + px
                Plot xCenter + x, yCenter + y
                Plot xCenter - x, yCenter + y
                Plot xCenter + x, yCenter - y
                Plot xCenter - x, yCenter - y
        Wend

		timeToDraw = MilliSecs() - msStart
		Text 20, 20, Rx + " x " + Ry
		Text 20, 30, "Draw time " + timeToDraw + " ms"
		
        Flip(False)
Until KeyHit(1)

Here is a port to BlitzPlus code for those interested (and an additional waitevent - oh how i love progs that aren't always 100% on my CPU). Oh, and I added an ms counter to see how long the calculations and drawing take.

Rck

2005

;Midpoint ellipse algorithm

Const GAME_WIDTH = 800
Const GAME_HEIGHT = 600
Graphics  GAME_WIDTH, GAME_HEIGHT, 0, 2

Local xCenter% = GAME_WIDTH / 2
Local yCenter% = GAME_HEIGHT / 2
Local Rx%, Ry%
Local p%, px%, py%, x%, y%
Local Rx2%, Ry2%, twoRx2%, twoRy2%
Local pFloat#

Const fillColor% = $FF

Repeat
        Cls
		WaitEvent()
		
		
        If MouseDown(1)
            xCenter = MouseX()
            yCenter = MouseY()
        EndIf
        Rx = Abs(xCenter - MouseX())
        Ry = Abs(yCenter - MouseY())
		
        Rx2 = Rx * Rx
        Ry2 = Ry * Ry
        twoRx2 = Rx2 Shl 1
        twoRy2 = Ry2 Shl 1
		
		msStart = MilliSecs()
		
        ;Region 1
        x = 0
        y = Ry
		
		LockBuffer(BackBuffer)
		
		wpf(xCenter + x, yCenter + y)
        wpf(xCenter - x, yCenter + y)
        wpf(xCenter + x, yCenter - y)
        wpf(xCenter - x, yCenter - y)

        pFloat = (Ry2 - (Rx2 * Ry)) + (0.25 * Rx2)
        p = Int(pFloat)
        If pFloat Mod 1.0 >= 0.5 Then p = p + 1

        px = 0
        py = twoRx2 * y

        While px < py
                x = x + 1
                px = px + twoRy2
                If p >= 0
                        y = y - 1
                        py = py - twoRx2
                EndIf
                If p < 0 Then p = p + Ry2 + px Else p = p + Ry2 + px - py
                wpf(xCenter + x, yCenter + y)
                wpf(xCenter - x, yCenter + y)
                wpf(xCenter + x, yCenter - y)
                wpf(xCenter - x, yCenter - y)
        Wend

        ;Region 2
        pFloat = (Ry2 * (x + 0.5) * (x + 0.5)) + (Rx2 * (y - 1.0) * (y - 1.0)) - (Rx2 * (Float(Ry2)))
        p = Int(pFloat)
        If pFloat Mod 1.0 >= 0.5 Then p = p + 1
        While y > 0
                y = y - 1
                py = py - twoRx2
                If p <= 0
                        x = x +1
                        px = px + twoRy2
                EndIf
                If p > 0 Then p = p + Rx2 - py Else p = p + Rx2 - py + px
                wpf(xCenter + x, yCenter + y)
                wpf(xCenter - x, yCenter + y)
                wpf(xCenter + x, yCenter - y)
                wpf(xCenter - x, yCenter - y)
        Wend

		UnlockBuffer(BackBuffer)
		

		timeToDraw = MilliSecs() - msStart
		Text 20, 20, Rx + " x " + Ry
		Text 20, 30, "Draw time " + timeToDraw + " ms"
		
        Flip(False)
Until KeyHit(1)


Function wpf(x,y)
  ;safe WritePixelFast
  If x < 0 Or x >= GAME_WIDTH Then Return 0
  If y < 0 Or y >= GAME_HEIGHT Then Return 0
  WritePixelFast(x, y, fillColor%)
End Function

And here is virtually the same code just using writepixelfast on a locked buffer

ImaginaryHuman

2005

Cool, thanks.

Code Archives Forum