[Solved]Scalable Circle Algorithms
Author
Hello
I'm looking at circle drawing algorithms for a parser i'm doing,the first one i notice is the midpoint(bresenham's) algorithm.
this (as far as i can tell) plots the points in each of the 8 octants simultaneously which would mean i'd have to figure out the order of the points afterwards so i could draw the circle.
alternatively i could calculate the points using trigonometry for the full 365 degrees(or 90 and mirror).
i'm using it to produce circles for an svg implementation so i need them to scale well.
The problem is i'm not sure how well these methods would hold up under scaling of the circle(both display and efficiency wise), i would imagine that with circles with large radii(is that the plural of multiple radius(es) lol) the methods would start to produce noticable corners.
any thoughts or suggestions on how this is normally done would be greatly appreciated.
Wardyahh
[Edited by - Wardyahh on June 19, 2008 3:17:13 PM]
You could use the plain old circle equation to calculate the x extents for each scanline:
x=sqrt(r*r-y*y)
For filled circles, all you have to do is draw a horizontal span all the way across (xCenter-x to xCenter+x). For non-filled, you'll have to keep track of the x for the previous line and draw short spans, since near the top and bottom the x changes more than 1 pixel per scanline, so plotting single pixels doesn't work.
Square root per scanline is a little slow, but maybe still faster than iterating over degrees and calling sin/cos, since that usually involves a lot of overdraw to avoid missing any pixels.
x=sqrt(r*r-y*y)
For filled circles, all you have to do is draw a horizontal span all the way across (xCenter-x to xCenter+x). For non-filled, you'll have to keep track of the x for the previous line and draw short spans, since near the top and bottom the x changes more than 1 pixel per scanline, so plotting single pixels doesn't work.
Square root per scanline is a little slow, but maybe still faster than iterating over degrees and calling sin/cos, since that usually involves a lot of overdraw to avoid missing any pixels.
Author
Thanks for the reply,
i think calculating per scanline would sort out the scaling problem.
i'm pretty sure i wont have to deal with the filling manually(at least not for the closed shapes).
rather than calling the sqrt for all of the scanlines i could probably call it for 90 degrees and use the inverse y for the flipside vertically and the inverse x for the flip horizontally.
do you think there would be any placement issues with using the inverse y?
i think calculating per scanline would sort out the scaling problem.
i'm pretty sure i wont have to deal with the filling manually(at least not for the closed shapes).
rather than calling the sqrt for all of the scanlines i could probably call it for 90 degrees and use the inverse y for the flipside vertically and the inverse x for the flip horizontally.
do you think there would be any placement issues with using the inverse y?
Short answer: Only if the center y is not an integer.
Long answer: Since calculating the x extents uses the current y scanline (naturally an integer) relative to the y center (maybe not an integer), if the y center is say 100.2, then the calculated x would be slightly different above and below the center.
The same doesn't apply to x mirroring though. Since the x extent and x center could both be floating point, adding for one side and subtracting for the other would retain the fractional portion properly. The problem with y is that you're "sampling" the x at an integer y coordinate, so it doesn't retain symmetry around the potentially fractional center.
The whole algorithm could be done entirely in integer math though, in which case nothing can go wrong with mirroring.
Long answer: Since calculating the x extents uses the current y scanline (naturally an integer) relative to the y center (maybe not an integer), if the y center is say 100.2, then the calculated x would be slightly different above and below the center.
The same doesn't apply to x mirroring though. Since the x extent and x center could both be floating point, adding for one side and subtracting for the other would retain the fractional portion properly. The problem with y is that you're "sampling" the x at an integer y coordinate, so it doesn't retain symmetry around the potentially fractional center.
The whole algorithm could be done entirely in integer math though, in which case nothing can go wrong with mirroring.
Author
Thanks for all the help,
i hopefully know enough now, just to clarify, i cant restrict it to integer points only as the centre value(and indeed the radius as well) must allow floating point values to conform to the spec.
Ratings ++;
i hopefully know enough now, just to clarify, i cant restrict it to integer points only as the centre value(and indeed the radius as well) must allow floating point values to conform to the spec.
Ratings ++;
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
