Jump to content
  • Advertisement
Sign in to follow this  
Wardyahh

[Solved]Scalable Circle Algorithms

This topic is 3826 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 ++;

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!