画圈，OpenGL风格

Question

我有一个13 x 13的像素阵列，我正在使用一个函数在它们上面画一个圆圈。（屏幕是13*13，这可能看起来很奇怪，但它是一个LED阵列，所以这就解释了它。）

unsigned char matrix[13][13];
const unsigned char ON = 0x01;
const unsigned char OFF = 0x00;

这是我想到的第一个实现。（它效率低下，这是一个特殊的问题，因为这是一个嵌入式系统项目，80 MHz处理器。）

// Draw a circle
// mode is 'ON' or 'OFF'
inline void drawCircle(float rad, unsigned char mode)
{
    for(int ix = 0; ix < 13; ++ ix)
    {
        for(int jx = 0; jx < 13; ++ jx)
        {
            float r; // Radial
            float s; // Angular ("theta")
            matrix_to_polar(ix, jx, &r, &s); // Converts polar coordinates
                                             // specified by r and s, where
                                             // s is the angle, to index coordinates
                                             // specified by ix and jx.
                                             // This function just converts to
                                             // cartesian and then translates by 6.0.
            if(r < rad)
            {
                matrix[ix][jx] = mode; // Turn pixel in matrix 'ON' or 'OFF'
            }
        }
    }
}

我希望这很清楚。这很简单，但是后来我对它进行了编程，所以我知道它应该如何工作。如果您想要更多信息/解释，那么我可以添加更多代码/注释。

可以认为画几个圆（如4到6）非常慢。。。因此，我正在寻求一种更有效的算法来画圆圈。

编辑：通过进行以下修改，将性能提高了一倍：

调用绘图的函数通常如下所示：

for(;;)
{
    clearAll(); // Clear matrix

    for(int ix = 0; ix < 6; ++ ix)
    {
        rad[ix] += rad_incr_step;
        drawRing(rad[ix], rad[ix] - rad_width);
    }

    if(rad[5] >= 7.0)
    {
        for(int ix = 0; ix < 6; ++ ix)
        {
            rad[ix] = rad_space_step * (float)(-ix);
        }

    }

    writeAll(); // Write 
}

我添加了以下检查：

if(rad[ix] - rad_width < 7.0)
    drawRing(rad[ix], rad[ix] - rad_width);

这将性能提高了大约2倍，但理想情况下，我希望使圆圈绘制更有效以进一步提高它。这将检查环是否完全在屏幕之外。

编辑2：类似地，添加反向检查进一步提高了性能。

if(rad[ix] >= 0.0)
    drawRing(rad[ix], rad[ix] - rad_width);

性能现在相当不错，但我再次没有对圆的实际绘图代码进行任何修改，这就是我打算在这个问题上关注的。

编辑3：矩阵到极坐标：

inline void matrix_to_polar(int i, int j, float* r, float* s)
{
    float x, y;
    matrix_to_cartesian(i, j, &x, &y);
    calcPolar(x, y, r, s);
}

inline void matrix_to_cartesian(int i, int j, float* x, float* y)
{
    *x = getX(i);
    *y = getY(j);  
}

inline void calcPolar(float x, float y, float* r, float* s)
{
    *r = sqrt(x * x + y * y);
    *s = atan2(y, x);
}

inline float getX(int xc)
{
    return (float(xc) - 6.0);
}

inline float getY(int yc)
{
    return (float(yc) - 6.0); 
}

作为对Clifford的回应，如果函数调用不是内联的，那么实际上有很多函数调用。

编辑4：drawRing只画了两个圆，首先是一个模式打开的外圆，然后是一个模式关闭的内圆。我相当有信心，有一种更有效的方法来绘制这样的形状，但这分散了问题的注意力。

Answer 1

对于一个只有13x13元素显示屏的慢速嵌入式设备，你真的应该做一个查找表。例如：

struct ComputedCircle
{
    float rMax;
    char col[13][2];
};

其中，绘图例程使用rMax确定要使用的LUT元素。例如，如果有两个元素，一个rMax=1.4f，另一个=1.7f，那么1.4f和1.7f之间的任何半径都将使用该条目。

列元素将为每行指定零、一或两个线段，这些线段可以在每个字符的下4位和上4位进行编码-1可以用作此行的哨兵值。要使用多少查找表条目取决于您，但使用13x13网格，您应该能够对100个条目以下的像素的所有可能结果进行编码，并且只使用10个左右的条目就可以得到合理的近似值。您还可以在压缩和绘图速度之间进行权衡，例如，将列[13][2]矩阵放在一个平面列表中，并对定义的行数进行编码。

Answer 2

不要低估在没有FPU的处理器上使用浮点运算的基本算法的成本。浮点似乎不太可能是必需的，但它的使用细节隐藏在matrix_to_polar（）实现中。

您当前的实现将每个像素都视为候选像素——这也是不必要的。

使用方程y=cy±√[rad²-（x-cx）²]其中cx，cy是中心（在本例中为7，7），并采用合适的整数平方根实现，可以这样绘制圆：

void drawCircle( int rad, unsigned char mode )
{
    int r2 = rad * rad ;
    for( int x = 7 - rad; x <= 7 + rad; x++ )
    {
        int dx = x - 7 ;
        int dy = isqrt( r2 - dx * dx ) ;

        matrix[x][7 - dy] = mode ;
        matrix[x][7 + dy] = mode ;
    }
}

在我的测试中，我使用了下面基于此处代码的isqrt（），但考虑到所需的最大r²为169（13²，如果需要，您可以实现16位甚至8位优化版本。如果您的处理器是32位，这可能很好。

uint32_t isqrt(uint32_t n)
{
   uint32_t root = 0, bit, trial;
   bit = (n >= 0x10000) ? 1<<30 : 1<<14;
   do
   {
      trial = root+bit;
      if (n >= trial)
      {
         n -= trial;
         root = trial+bit;
      }
      root >>= 1;
      bit >>= 2;
   } while (bit);

   return root;
}

尽管如此，在如此低分辨率的设备上，您可能会通过为所需的每个半径手动生成位图查找表来获得更高质量的圆圈和更快的性能。如果内存是个问题，那么单个圆圈只需要7个字节来描述您可以反映到所有三个象限的7 x 7象限，或者为了获得更高的性能，您可以使用7 x 16位词来描述半圆（因为颠倒位序比颠倒数组访问更昂贵——除非您使用带有位带的ARM Cortex-M）。使用半圆查找，13个圆需要13 x 7 x 2字节（182字节），象限查找将是7 x 8 x 13（91字节）-您可能会发现计算圆所需的代码空间的字节更少。

Answer 3

你在做很多不需要的计算。例如，您正在计算极坐标的角度，但从不使用它。通过比较值的平方，也可以很容易地避免平方根。

不做任何花哨的事情，这样的事情应该是一个好的开始：

int intRad = (int)rad;
int intRadSqr = (int)(rad * rad);

for (int ix = 0; ix <= intRad; ++ix)
{
    for (int jx = 0; jx <= intRad; ++jx)
    {
        if (ix * ix + jx * jx <= radSqr)
        {
            matrix[6 - ix][6 - jx] = mode;
            matrix[6 - ix][6 + jx] = mode;
            matrix[6 + ix][6 - jx] = mode;
            matrix[6 + ix][6 + jx] = mode;
        }
    }
}

这将以整数格式完成所有数学运算，并利用圆对称性。

根据评论中的反馈，上述变化：

int intRad = (int)rad;
int intRadSqr = (int)(rad * rad);

for (int ix = 0; ix <= intRad; ++ix)
{
    for (int jx = 0; ix * ix + jx * jx <= radSqr; ++jx)
    {
        matrix[6 - ix][6 - jx] = mode;
        matrix[6 - ix][6 + jx] = mode;
        matrix[6 + ix][6 - jx] = mode;
        matrix[6 + ix][6 + jx] = mode;
    }
}