Dark Bit Factory & Gravity
PROGRAMMING => General coding questions => Topic started by: Pixel_Outlaw on December 18, 2007
-
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.
-
You can draw them a different way (instead of subdividing the circumference).
Something like this
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
-
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:
-
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 (http://www.gamedev.net/reference/articles/article767.asp)
Jim
-
How about this?
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
-
How about this one I found on blitz forum.
'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
-
This reminds me of the anti aliased circles discussion on the yab forum, might be something worth thinking about.
-
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.
-
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.
-
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.
-
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.
-
I'd totally forgotten about that - very pretty!
Jim
-
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.
-
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.
-
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:
-
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.
-
It seems like this tweek of the one I previously posted works the way you want it to.
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
-
Excellent work! have some karma.
-
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
-
Excellent work! have some karma.
Thanks, glad I could help.
-
I have considered anti aliased circles but those crazy nit-picking pixel artists like to have full control of every pixel. I myself like to use low color counts in my images just for the challenge. Most of the time I try to keep individual colors in an image down to below 12 or so, just crazy self imposed rules. There is a certain charm to working within frustrating constraints. I myself don't usually dither but many of my fellow pixel artists will spend hours hand dithering an image with no mathematical understanding. The same goes for anti aliasing.
You can poke around a bit here : http://www.pixeljoint.com/default.asp
Be forewarned that the forum section is full of retards with loud mouths and faulty opinions and most of the mods are not much better.
-
[Offtopic, hopes its alright] Which drawing program are you using now, and what kind of drawing program do you need this circle code for? I have been thinking about doing a DeluxePaint like windows version with fixed palette (256 colors and less) and geared towards pixel pushing, but I do not know if there is any need for such program. I have the basic framework for it coded, but still needs various tools coded.
-
Ah ok, I see now.
For the antialiasing I had to check which of each pixels corners were within the circles radius and have come up with a similar idea for what you're looking for:
sub draw_circle(byval cx as single,byval cy as single,byval rad as single,byval argb as unsigned integer)
dim as single s=int(rad+1.0)
dim as single rad2=rad*rad
dim as single dy=cy-int(cy-0.5)
dim as single dx=cx-int(cx-0.5)
dim as integer corner_count
for y as single =-s-dy to s-dy step 1.0
for x as single =-s-dx to s-dx step 1.0
corner_count=0
if (x*x+y*y)<=rad2 then corner_count+=1
if ((x+1.0)*(x+1.0)+y*y)<=rad2 then corner_count+=1
if (x*x+(y+1.0)*(y+1.0))<=rad2 then corner_count+=1
if ((x+1.0)*(x+1.0)+(y+1.0)*(y+1.0))<=rad2 then corner_count+=1
if (corner_count and 2) then pset(int(x+cx),int(y+cy)),argb
next
next
end sub
-
[Offtopic, hopes its alright] Which drawing program are you using now, and what kind of drawing program do you need this circle code for? I have been thinking about doing a DeluxePaint like windows version with fixed palette (256 colors and less) and geared towards pixel pushing, but I do not know if there is any need for such program. I have the basic framework for it coded, but still needs various tools coded.
Naw this is still on the topic I think. There is quite a need for this. MS Paint does everything I want except draw proper circles every time. If you really wanted to add some cool feaures you might look into making some pixel art isometric construction tecniques. Things like constructing an isometric cube or perhaps inscribing an isometric ellipse within the faces of said cube. The biggest complaint in isometric is the lack of good circles. Nobody quite knows how to construct them well. They just poke around and guess at what they might look like. I made a program that drew rotated ellipses but again they came out like my horrid polygonal and malformed circles. Some default dithering fills would be cool too. The biggest aspect of pixel art is visual correctness over mathmatical accuracy. The circles being a prime example. The isometric grid has lines that go up one pixel and over two the angle formed might repeat I don't know but it is best to just think in terms of rise and run rather than the angle formed.
Thoughts
Most images are saved as .png (lossless formats only)
Sometimes artists use hue shifts within light gradients (could be tinkered with in a color chooser)
Shape tools cannot produce clusters of three or more pixels except at intersections
Probably more little things too here is a simple (very) scene based on the pixel artist's isometric projection
The grid lines have a projected slope of 1/2. It would be really cool to have a tool that produced isometric circles, many times you might want to make a pipe coming out of a wall or other such things and it is very hard to freehand correctly. Imagine a cube drawin in this perspective with a circle on each face. I've solved the code myself but sadly the isometric circles always had clusters of pixels because I was using a polygon with center point algorithem. An isometric ellipse has an axis ratio of 2:1. Paint can do everything I need as a pixel artist except produce some isometric calculation and circles. Should you build such a pixel art program you may he hailed as some sort of a diety by thousands. So basically your paint program should be like MS Paint with some artist friendly features built in.
Annnnnnyyyyyywayyyyyy the scene:
-
The Christmas holiday is coming up, 11 days off from work :) I might look into getting back to that Dpaint program after all. Its something I had been thinking about doing years back, but never got around to do. And I have done other programs with pixel editing and effects. Perhaps you are right, perhaps there is a need for a specialized iso-pixel drawing tool. I am really amazed at what some of those pixel artists can produce. It must take forever to draw, especially those huge drawings with part of cities and such. I will give this some thought and I might end up taking some time out during the vacation to work on this. Its not like I have other plans anyways, only on christmas eve and new years, so I still have 9 days to kill.
One question to begin with would be: Do you think people would want a fixed palette (eg. containing 256 colors picked by themselves as an example via a color gradient tool), or should it be true color with all colors available at any time?
-
Well most people like their million color choices. I personally would like 256 color mode. Which brings me to another must have, savable color palettes. Paint never allows to save the palette which is very frustrating. I would advise that you have savable palettes that could be loaded independantly of images. Also it might be cool to have some palette options like converting an image into a palette and forcing a palette to an image. Many ideas here. :D I think you might start a new project thread where we can focus on features. This way there won't be walls of text to slog through.
-
Draw 90 degrees of the circle and then just mirror it.
-
Combine that with Bresenham's Circle Algorithm (http://www.google.com.au/search?hl=en&q=Bresenham%27s+Circle+Algorithm&meta=) and you will get perfect circles every time.
Jim