Are perfectly symmetrical circles impossible to create?

[Pixel_Outlaw]

I'm making a circle generation program for some fellow pixel artists. We often deal in small images with high levels of accuracy. My dellima is creating a perfect raster circle. I often in the past have used a for loop to create a perimeter of connected points. This approach should work in theroy but many times the shapes are not as you would expect. They are sometimes asymmetrical at the pixel level or they have extra "clusters" of connected pixels. By clusters I mean groups of more than two pixels touching side by side. I know this seems like a VERY nitpicky problem but I need some 8 way symmetrical circles. I've never seen a program pull this off, even Paint makes lopsided circles from time to time and I have no idea why. I have tried rounding the output points which seems to help in some cases but does not totally eleminate the problem. I know that this is a rounding error but I don't know where or how to solve it. Even polygons drawn with for loops have sides with slopes varying by one or two minute degrees. Why does this rounding error happen and how can I fix it? I know that OpenGL is not pixel perfect so does this mean that I can never create 8 way symmetry in my circles?

An example notice the differing slopes in the sides of this included hexagon:

Similar things happen with circles:


The source code is also at the bottom. If you don't have blitzmax, you can still view it with a notepad program.

[Jim]

You can draw them a different way (instead of subdividing the circumference).
Something like this

Code: [Select]

for y = -r to r
x = sqrt(r*r - y*y)
plot cx+x,cy+y
plot cx-x,cy+y
next
circle drawn with origin cx,cy radius r.
That will at least be symmetric about the horizontal and vertical axes.

Jim

[Pixel_Outlaw]

OK this is an excellent (and prompt) start Jim!

What about doing the same for the x axis then comparing values keeping shared pixels?

A pic of your algorithm:

[Jim]

Admittedly it's a better algorithm for filled circles - you just draw a line between the two x values.
You need to be googling for Bresenham's Circle Algorithm,
eg. http://www.gamedev.net/reference/articles/article767.asp

Jim

[relsoft]

How about this?

Code: [Select]

screenres 800,600,32





dim stepsize as single



dim radius as single



'c= 2*PI*r

's= r*theta



radius = 400

stepsize = 2 * 3.141593/radius



for i as single = 0 to 360 step stepsize



pset(400+cos(i*3.141593/180)*radius,300+sin(i*3.141593/180)*radius),rgb(255,255,255)



next

sleep



[zawran]

How about this one I found on blitz forum.

Code: [Select]

'Midpoint Circle algorithm

Strict
Graphics 640,480,0

Local xCenter:Int=320
Local yCenter:Int=240
Local radius:Int
Local p,x,y:Int
Repeat
        Cls
        If MouseDown(1)
                xCenter=MouseX()
                yCenter=MouseY()
        EndIf
        radius=Abs(xCenter-MouseX())
        x=0
        y=radius
        Plot xCenter+x,yCenter+y
        Plot xCenter-x,yCenter+y
        Plot xCenter+x,yCenter-y
        Plot xCenter-x,yCenter-y
        Plot xCenter+y,yCenter+x
        Plot xCenter-y,yCenter+x
        Plot xCenter+y,yCenter-x
        Plot xCenter-y,yCenter-x
        p=1-radius
        While x<y
                If p<0
                        x:+1
                Else
                        x:+1
                        y:-1
                EndIf
                If p<0
                        p=p+(x Shl 1)+1
                Else
                        p=p+((x-y) Shl 1)+1
                EndIf
                Plot xCenter+x,yCenter+y
                Plot xCenter-x,yCenter+y
                Plot xCenter+x,yCenter-y
                Plot xCenter-x,yCenter-y
                Plot xCenter+y,yCenter+x
                Plot xCenter-y,yCenter+x
                Plot xCenter+y,yCenter-x
                Plot xCenter-y,yCenter-x
        Wend
        Flip
Until KeyHit(KEY_ESCAPE)
End


[Stonemonkey]

This reminds me of the anti aliased circles discussion on the yab forum, might be something worth thinking about.

[Pixel_Outlaw]

Ah thanks for the help so far. Rel, I'm going to convert your code and test it after lunch. Zawran, that code works excellent and has good 8 way symmetry, however could it be adapted to produce circles with an even pixel diameter? The center would lie between a cluster of 4 center pixels. Thanks for all the help so far.

[zawran]

however could it be adapted to produce circles with an even pixel diameter?

Not sure I know what you are asking. If I set the radius to 50 (an even number) and remark out the mouse part, then it draws a circle which is symetrical. But as I say, I am not sure what you are asking.

[Pixel_Outlaw]

Well that methods insists that all circles have a center pixel. Since the midpoint of a 128x128 canvas has no central pixel the image goes outside the frame. I have taken a picture. You can clearly see a single central pixel in the image. If the circle did have a diameter of 128 pixels it would be able to fit into the window. So the problem is 50 percent solved, for odd width canvases this solution works well, now for the even width canvases a new algorithm is needed. This problem has plagued me for some time.

[Stonemonkey]

Knocked up an example of anti ailiased circles, a different method from what I used before and pretty slow and the code's a bit mixed up:

The white circle moves by 0.1 pixel at a time

the circle at the bottom left is drawn with FB circle command.
Fryer.

[Jim]

I'd totally forgotten about that - very pretty!
Jim

[zawran]

Ok, now I see what you are getting at. I haven't found anything on the internet yet that does that. It looks to me like you are going to have to make some code that does 45 degrees of the circle and then mirror that over. All the code I have found so far has a center origin, which is also how drawing applications does it. They all work with a radius which needs a center which is why you will end up with that center pixel and an uneven number as the diameter.

[Pixel_Outlaw]

Ok, now I see what you are getting at. I haven't found anything on the internet yet that does that. It looks to me like you are going to have to make some code that does 45 degrees of the circle and then mirror that over. All the code I have found so far has a center origin, which is also how drawing applications does it. They all work with a radius which needs a center which is why you will end up with that center pixel and an uneven number as the diameter.

Exactly! Basically I'm making a drawing program that fixes MS Paint's odd imperfect circles. If you hold the shift key while you draw a circle, you will see that it makes both odd pixel width circles as well as even width circles. The funny thing is that the program sometimes produces imperfect circles. It does produce both kinds but the inconsistency with symmetry drives my crazy, sometimes you get a perfect circle and sometimes it creates odd little mistakes. I don't know if it has anything to do with odd or even pixel diameters but I've seen both types of circle drawn correctly in regard to symmetry.

[Stonemonkey]

I've just thought of something that should maybe be mentioned here, maybe you already know this though:


Imagine a circle with centre at 100,100 and a radius of 5

the far left pixel to be filled is (95,100) and the filled pixel lies inside the radius

the far right pixel to be filled is (105,100) but this time the filled pixel lies outside the radius of the circle.

The same applies all round the edge and needs to be taken into account as well as the way the coordinates are rounded.


To show what I mean, the blue lines are the centre lines and the red squares are some of the filled pixels:

[Pixel_Outlaw]

I hope I'm not seeming like a nit-picky pain in the ass guys. This is one of those problems that seems simple on the outside but finding the proper algorithem is quite hard for me. I don't want people to think that I have not tried evry example and looked at many different web pages. This is for making raster images in a drawing like program so it would be nice to get correct. If people are wanting to make a circle 32x32 pixels across then I can't give them a 31x31 or a 33x33 pixel circle. I've thought about iterating through every point in the canvas and even tried to find algorithems for ignoring the central point. Perhaps there needs to be a pixel by pixel scan with rounding to find the edges. Again, orry if I'm coming off as a knit picker. Speed is not a huge factor here either just getting the result is important. It appears that ms paint uses polygons rather than true circles but I've seen the polygons produce unpredictable results due to things like too many points or not enough points aswell as rounding errors.

[zawran]

It seems like this tweek of the one I previously posted works the way you want it to.

Code: [Select]

SuperStrict

Graphics 640,480,0
Cls
SetColor 255,0,0
DrawRect 0,0,128,128
dCircle(64,64,64,255,255,255)
SetColor 0,0,128
Flip

While Not KeyHit(KEY_ESCAPE)
Wend
End

Function dCircle(xCenter:Int,yCenter:Int,radius:Int,cRed:Int,cGre:Int,cBlu:Int)
Local cR:Int,cG:Int,cB:Int
Local p:Int,x:Int,y:Int

' store current color
cR = GetColor(cR,cG,cB)
' set draw color
SetColor cRed,cGre,cBlu

x=0
y=radius
Plot xCenter+x-1,yCenter+y-1
Plot xCenter-x,yCenter+y-1
Plot xCenter+x-1,yCenter-y
Plot xCenter-x,yCenter-y
Plot xCenter+y-1,yCenter+x-1
Plot xCenter-y,yCenter+x-1
Plot xCenter+y-1,yCenter-x
Plot xCenter-y,yCenter-x
p=1-radius
While x<y
If p<0
x:+1
Else
x:+1
y:-1
EndIf
If p<0
p=p+(x Shl 1)+1
Else
p=p+((x-y) Shl 1)+1
EndIf
Plot xCenter+x-1,yCenter+y-1
Plot xCenter-x,yCenter+y-1
Plot xCenter+x-1,yCenter-y
Plot xCenter-x,yCenter-y
Plot xCenter+y-1,yCenter+x-1
Plot xCenter-y,yCenter+x-1
Plot xCenter+y-1,yCenter-x
Plot xCenter-y,yCenter-x
Wend
' restore drawing color
SetColor cR,cG,cB
End Function


[Pixel_Outlaw]

Excellent work! have some karma.

[Stonemonkey]

I don't know if you've looked into the anti aliased circles I suggested but if it's for some sort of artwork it's something worth considering:

the image on the left is drawn into a 128*128 window with centre coords 64.0 , 64.0 and radius 64.0

the image on the right is draw into a 127*127 window with centre coords 63.5 , 63.5 and radius 63.5

[zawran]

Excellent work! have some karma.

Thanks, glad I could help.