xoxosvst

dsp blog for xoxos.net

c++ antialiased circle algorithm

with one comment

i released a very minimal c++ win32 graphics&audio source on the software page at xoxos.net a few days ago with an antialiased line algorithm. i’d read about the wu line and seen the results and decided to do it my way first.. i use more than 2 pixels and a nonlinearity for the edge which is smoother than wu. it looks keen and it’s homemade.. only “feature” is a slight shift when switching from NWN to NWW directions, likely because i didn’t add 0.5 when converting to INT, which is a task for another day as it looks nice otherwise.

got to circles, my method inherits some of the methods i used for lines. this is pretty much a/the brute force algorithm as a sqrt() is performed for every pixel, and an additional sqrt() for every row. the benefit of this is that subpixel centers may be assigned so it can’t be optimised by symmetry.

my antialiasing uses a margin scaling coefficient, eg. once the distance between a pixel and a circle/line is resolved, this distance is then scaled before antialiasing is conducted.. which softens the boundary, or makes it more steppy if the coefficient increases the relative distance… 0.75 looks real nice to me along with the nonlinearity. the distance this affects in pixels is of course the inverse 1/margin, or 1.33 pixels if using 0.75.

circle basics:
radius = sqrt(x*x + y*y)   and so   y = sqrt(radius*radius – x*x) 

my technique is pretty simple – compute an outside circle and an inside circle which are larger/smaller by the inverse margin coefficient (eg. radius +/- 1.33), thereby reducing the amount of pixels that need to be run.

much of the length of this script is actually reading the preexistent pixel colour. once you get the idea, it’s probably easier to write it yourself than untangle my code.

as you may guess, reducing margin to 0.25 fades/blurs graphics by 4 pixels.. 0.001 by 1000 pixels and so forth.. and, once you get the idea, you can easily modify this technique to give the circle thickness. like the line algorithm, i am suggesting that this method be known as the pothead antialiased circle algorithm.

soz for the mess, i am not 1337 wordpresser, code tags put the whole lot on one line..

void circleaa(point2 param, float radius, int bgrr, int bgrg, int bgrb) {
 if (radius <= 0.f) return;
 short int bgb, bgg, bgr;
 float radiuso = radius + margini; // outside radius
 float radiusi = radius – margini;
 float radiusi2 = radiusi * radiusi;
 float radiuso2 = radiuso * radiuso;
 int cxi = floor(param.x); // center int
 int cyi = floor(param.y);
 float cxd = param.x – cxi;
 float cyd = param.y – cyi;
 o = radiuso + margini;
 int lowm = floor(-o); int highm = o;
 for (int dox = lowm; dox <= highm; dox++) {
  int pixx = cxi + dox;
  if (pixx > -1 && pixx < dispx) {
   float dx = dox – cxd; dx *= dx;
   float boy = radiuso2 – dx;
   if (boy > 0) {
    boy = sqrt(boy);
    int lowy = floor(-boy); int highy = boy; highy += 2;
    float biy = radiusi2 – dx;
    if (biy > 0) {
     biy = sqrt(biy);
     int lowi = floor(-biy); int highi = biy; lowi += 2;
     for (int doy = lowy; doy < lowi; doy++) {
      int pixy = cyi + doy;
      if (pixy > -1 && pixy < dispy) {
       float dy = doy – cyd;
       dy = sqrt(dx + dy * dy);
       dy -= radius; if (dy < 0) dy = -dy; dy = 1.f – dy * margin;
       if (dy > 0) {
        dy *= pih; dy = dy – dy * dy * dy * 0.1472725f; float dy0 = 1.f – dy;
        int dopix = (doy + cyi) * dispx + dox + cxi;
        bgb = (byte)framebuf[dopix];
        bgg = (byte)(framebuf[dopix]>>8);
        bgr = (byte)(framebuf[dopix]>>16);
        o = bgrb * dy + bgb * dy0; o < 255.f ? bgb = (int)o : bgb = 255;
        o = bgrg * dy + bgg * dy0; o < 255.f ? bgg = (int)o : bgg = 255;
        o = bgrr * dy + bgr * dy0; o < 255.f ? bgr = (int)o : bgr = 255;
        *(framebuf + dopix) = RGB(bgb,bgg,bgr);
     } } }
     for (int doy = highi; doy < highy; doy++) {
      int pixy = cyi + doy;
      if (pixy > -1 && pixy < dispy) {
       float dy = doy – cyd;
       dy = sqrt(dx + dy * dy);
       dy -= radius; if (dy < 0) dy = -dy; dy = 1.f – dy * margin;
       if (dy > 0) {
        dy *= pih; dy = dy – dy * dy * dy * 0.1472725f; float dy0 = 1.f – dy;
        int dopix = (doy + cyi) * dispx + dox + cxi;
        bgb = (byte)framebuf[dopix];
        bgg = (byte)(framebuf[dopix]>>8);
        bgr = (byte)(framebuf[dopix]>>16);
        o = bgrb * dy + bgb * dy0; o < 255.f ? bgb = (int)o : bgb = 255;
        o = bgrg * dy + bgg * dy0; o < 255.f ? bgg = (int)o : bgg = 255;
        o = bgrr * dy + bgr * dy0; o < 255.f ? bgr = (int)o : bgr = 255;
        *(framebuf + dopix) = RGB(bgb,bgg,bgr);
    } } } }
    else {
     for (int doy = lowy; doy < highy; doy++) {
      int pixy = cyi + doy;
      if (pixy > -1 && pixy < dispy) {
       float dy = doy – cyd;
       dy = sqrt(dx + dy * dy);
       dy -= radius; if (dy < 0) dy = -dy; dy = 1.f – dy * margin;
       if (dy > 0) {
        dy *= pih; dy = dy – dy * dy * dy * 0.1472725f; float dy0 = 1.f – dy;
        int dopix = (doy + cyi) * dispx + dox + cxi;
        bgb = (byte)framebuf[dopix];
        bgg = (byte)(framebuf[dopix]>>8);
        bgr = (byte)(framebuf[dopix]>>16);
        o = bgrb * dy + bgb * dy0; o < 255.f ? bgb = (int)o : bgb = 255;
        o = bgrg * dy + bgg * dy0; o < 255.f ? bgg = (int)o : bgg = 255;
        o = bgrr * dy + bgr * dy0; o < 255.f ? bgr = (int)o : bgr = 255;
        *(framebuf + dopix) = RGB(bgb,bgg,bgr);
} } } } } } } }

 

Advertisements

Written by xoxosvst

October 8, 2013 at 6:06 am

Posted in Uncategorized

Tagged with

One Response

Subscribe to comments with RSS.

  1. lol so much for proofreading, about the 12th line in there.. o = radiuso + margini.. then used to set two integers.. this is an artifact from developing as it should read radius + margini… both ints only need to be set using radiuso (which is already radius + margini). i don’t think the extra margin is necessary…

    also like to say “sorry for variable names” as i’m new to OO and haven’t developed a convention for naming variables in objects (i’m used to c style programming with minimal variable names).

    xoxosvst

    October 8, 2013 at 6:19 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: