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

时间:2021-09-02 03:08:25

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

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

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

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

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