CODEWITHSUNDEEP
c++openglpixelantialiasing
Lyndon Alcock
Lyndon Alcock

Reputation: 139

why does my circle anti aliasing algorithm in C++ give asymmetrical results?

Some background:

So my plan is to create a stippling algorithm in C++ and I basically just plan on storing a whole bunch of data for each radius of a circle to write onto a texture map in OpenGL I'm not sure if this is the right thing to do but I feel like it

would be quicker than the computer dynamically calculating the radius for each circle especially if lots of circles are the same size, my plan is to create a function that just writes a whole text document full of radiuses up to a certain size and this data will be stored bitwise inside an array of long's std::array <long> bit = {0x21, 0x0A ect... } so that I can encode 4X4 arrays of values with 2 bits assigned to the antialiasing value of each pixel however to create this database of ant-aliased circles I need to write a function that I keep getting wrong;

The actual question:

So this may seem lazy but I can promise I have tried everything to wrap my head around what I am getting wrong here basically i have written this code to anti=alias by dividing up the pixels into sub pixels however it seems to be returning values greater than 1 which shouldn't be possible as i have divided each pixel into 100 pixels of size 0.01

float CircleConst::PixelAA(int I, int J)
{
    float aaValue = 0;

    for (float i = (float) I; i < I + 1; i += 0.1f)
    {
        for (float j = (float) J; j < J + 1; j += 0.1f)
        {
            if ((pow((i - center), 2) + pow((j - center), 2) < pow(rad, 2)))
                aaValue += 0.01f;
        }
    }
    return aaValue;
}

also here is the code that writes the actual circle

CircleConst::CircleConst(float Rad)
{
    rad = Rad;
    dataSize = (unsigned int) ceil(2 * rad);


    center = (float) dataSize/2;

    arrData.reserve((int) pow(dataSize, 2));

    for (int i = 0; i < dataSize; i++)
    {
        for (int j = 0; j < dataSize; j++)
        {
            if ( CircleBounds(i, j, rad-1) )
                arrData.push_back(1);
            else if (!CircleBounds(i, j, rad - 1) && CircleBounds(i, j, rad + 1))
            {
                arrData.push_back(PixelAA(i,j));
            }
            else
                arrData.push_back(0);
        }
    }
}

so I noticed without the antialiasing that the way the circle is written is shifted over by one line, but this could be fixed by changing the value of the centre of the circle todataSize/2 - 0.5f but this causes problems later on when the circle is asymmetrical with the antialiasing, here is an example of radius 3.5

0.4 1.0 1.1 1.1 1.1 0.4 0.0
1.0 1.0 1.0 1.0 1.0 1.1 0.2
1.1 1.0 1.0 1.0 1.0 1.0 0.5
1.1 1.0 1.0 1.0 1.0 1.0 0.5
1.1 1.0 1.0 1.0 1.0 1.0 0.2
0.4 1.1 1.0 1.0 1.0 0.5 0.0
0.0 0.2 0.5 0.5 0.2 0.0 0.0

as you can see some of the values are over 1.0 which should not be possible, I'm sure there is an obvious answer to why this is but I'm completely missing it.

Upvotes: 2

Views: 418

Answers (2)

Marco Sacchi
Marco Sacchi

Reputation: 982

In addition to what @Yun (the round-off error of floating point numbers) indicates, you must also pay attention to the sampling point (which must be at the pixel center).

Here your code, with some modification and addition:

#include <iostream>
#include <vector>
#include <iomanip>

#include <math.h>

float rad, radSquared, center;

const int filterSize = 8;
const float invFilterSize = 1.0f / filterSize;

// Sample the circle returning 1 when inside, 0 otherwise.
int SampleCircle(int i, int j) {
   float di = (i + 0.5f) * invFilterSize - center;
   float dj = (j + 0.5f) * invFilterSize - center;
   return ((di * di + dj * dj) < radSquared) ? 1 : 0;
}

// NOTE: This sampling method works with any filter size.
float PixelAA(int I, int J)
{
   int aaValue = 0;

   for (int i = 0; i < filterSize; ++i)
      for (int j = 0; j < filterSize; ++j)
         aaValue += SampleCircle(I + i, J + j);

   return (float)aaValue / (float)(filterSize * filterSize);
}

// NOTE: This sampling method works only with filter sizes that are power of two.
float PixelAAQuadTree(int i, int j, int filterSize)
{
   if (filterSize == 1)
      return (float)SampleCircle(i, j);

   // We sample the four corners of the filter. Note that on left and bottom corners
   // 1 is subtracted to avoid sampling overlap.
   int topLeft = SampleCircle(i, j);
   int topRight = SampleCircle(i + filterSize - 1, j);
   int bottomLeft = SampleCircle(i, j + filterSize - 1);
   int bottomRight = SampleCircle(i + filterSize - 1, j + filterSize - 1);

   // If all samples have same value we can stop here. All samples lies outside or inside the circle.
   if (topLeft == topRight && topLeft == bottomLeft && topLeft == bottomRight)
      return (float)topLeft;

   // Half the filter dimension.
   filterSize /= 2;

   // Recurse.
   return (PixelAAQuadTree(i, j, filterSize) +
      PixelAAQuadTree(i + filterSize, j, filterSize) +
      PixelAAQuadTree(i, j + filterSize, filterSize) +
      PixelAAQuadTree(i + filterSize, j + filterSize, filterSize)) / 4.0f;
}

void CircleConst(float Rad, bool useQuadTree)
{
   rad = Rad;
   radSquared = rad * rad;
   center = Rad;

   int dataSize = (int)ceil(rad * 2);
   std::vector<float> arrData;
   arrData.reserve(dataSize * dataSize);

   if (useQuadTree) 
   {
      for (int i = 0; i < dataSize; i++)
         for (int j = 0; j < dataSize; j++)
            arrData.push_back(PixelAAQuadTree(i * filterSize, j * filterSize, filterSize));
   }
   else 
   {
      for (int i = 0; i < dataSize; i++)
         for (int j = 0; j < dataSize; j++)
            arrData.push_back(PixelAA(i * filterSize, j * filterSize));
   }

   for (int i = 0; i < dataSize; i++)
   {
      for (int j = 0; j < dataSize; j++)
         std::cout << std::fixed << std::setw(2) << std::setprecision(2) 
            << std::setfill('0') << arrData[i + j * dataSize] << " ";

      std::cout << std::endl;
   }
}

int main() {
   CircleConst(3.5f, false);

   std::cout << std::endl;
   CircleConst(4.0f, false);

   std::cout << std::endl;

   std::cout << std::endl;
   CircleConst(3.5f, true);

   std::cout << std::endl;
   CircleConst(4.0f, true);

   return 0;
}

Which gives these results (the second ones with use of quad-tree to optimize number of samples required to compute the AA value):

0.00 0.36 0.84 1.00 0.84 0.36 0.00 
0.36 1.00 1.00 1.00 1.00 1.00 0.36 
0.84 1.00 1.00 1.00 1.00 1.00 0.84 
1.00 1.00 1.00 1.00 1.00 1.00 1.00 
0.84 1.00 1.00 1.00 1.00 1.00 0.84 
0.36 1.00 1.00 1.00 1.00 1.00 0.36 
0.00 0.36 0.84 1.00 0.84 0.36 0.00 

0.00 0.16 0.70 0.97 0.97 0.70 0.16 0.00 
0.16 0.95 1.00 1.00 1.00 1.00 0.95 0.16 
0.70 1.00 1.00 1.00 1.00 1.00 1.00 0.70 
0.97 1.00 1.00 1.00 1.00 1.00 1.00 0.97 
0.97 1.00 1.00 1.00 1.00 1.00 1.00 0.97 
0.70 1.00 1.00 1.00 1.00 1.00 1.00 0.70 
0.16 0.95 1.00 1.00 1.00 1.00 0.95 0.16 
0.00 0.16 0.70 0.97 0.97 0.70 0.16 0.00 


0.00 0.36 0.84 1.00 0.84 0.36 0.00 
0.36 1.00 1.00 1.00 1.00 1.00 0.36 
0.84 1.00 1.00 1.00 1.00 1.00 0.84 
1.00 1.00 1.00 1.00 1.00 1.00 1.00 
0.84 1.00 1.00 1.00 1.00 1.00 0.84 
0.36 1.00 1.00 1.00 1.00 1.00 0.36 
0.00 0.36 0.84 1.00 0.84 0.36 0.00 

0.00 0.16 0.70 0.97 0.97 0.70 0.16 0.00 
0.16 0.95 1.00 1.00 1.00 1.00 0.95 0.16 
0.70 1.00 1.00 1.00 1.00 1.00 1.00 0.70 
0.97 1.00 1.00 1.00 1.00 1.00 1.00 0.97 
0.97 1.00 1.00 1.00 1.00 1.00 1.00 0.97 
0.70 1.00 1.00 1.00 1.00 1.00 1.00 0.70 
0.16 0.95 1.00 1.00 1.00 1.00 0.95 0.16 
0.00 0.16 0.70 0.97 0.97 0.70 0.16 0.00

As further notes:

Upvotes: 2

Yun
Yun

Reputation: 3812

The problem lies with lines such as this one:

for (float i = (float) I; i < I + 1; i += 0.1f)

Floating point numbers cannot be stored or manipulated with infinite precision. By repeatedly adding one floating point number to another, the inaccuracies accumulate. This is why you're seeing values higher than 1.0.

The solution is to iterate using an integer type and compute the desired floating point numbers. For example:

for (unsigned i = 0U; i < 10U; ++i)
{
    float x = 0.1F * static_cast<float>(i);
    printf("%f\n", x);
}

Upvotes: 3

Related Questions