转载

Bresenham算法画填充圆及SDL代码实现

画圆是计算机图形操作中一个非常重要的需求。普通的画圆算法需要大量的浮点数参与运算，而众所周知，浮点数的运算速度远低于整形数。而最终屏幕上影射的像素的坐标均为整形，不可能是连续的线，所以浮点数运算其实纯属浪费。下面介绍的Bresenham算法就是根据上文的原理设计。该算法原应用于直线的绘制，但由于圆的八分对称性，该算法也适用与圆（曲线图形）的绘制。

该算法主要是这样的原理：找出一个1/8的圆弧，用快速的增量计算找出下一个点。同时利用圆的八分对称性，找出８个点（包括该点），进行绘制。

这里给出示例的SDL代码实现DrewDemo.zip（Ubuntu 12.04LTS下编译，Win用户需要自行在连接时加库libmingw32）。下面是程序运行时的截图。程序运行有效时间（即绘制SDL_Texture的时间）在E3 V1230+HD6770的PC上为18ms。

Bresenham实在是一个很快的算法，尤其是在没有硬件乘法（乘以２为底数的数均可用位运算代替）及除法器的单片机（MPU）上，效率将比浮点模拟画图法快上一个数量级。所以这是一个极容易硬件实现的算法。但是该算法也不是万能的。如上图可以看出，画出的圆比较粗糙，不符合人类挑剔的审美。而且在日益强大的性能面前，算法的优化似乎有了些累赘（需要更多的精力查BUG，想代码），所以没有特殊需求（密集形绘图或上文提到的嵌入式绘图）的同学也没必要写这算法了。

正文到此结束