OpenGL实现Bresenham画圆算法

中点Bresenham算法

Bresenham画圆算法又称中点画圆算法，与Bresenham 直线算法一样，其基本的方法是利用判别变量来判断选择最近的像素点，判别变量的数值仅仅用一些加、减和移位运算就可以计算出来。为了简便起见，考虑一个圆 心在坐标原点的圆，而且只计算八分圆周上的点，其余圆周上的点利用对称性就可得到。

为什么只计算八分圆周上的点就可以了呢？和上面的直线算法类似，圆也有一个“八对称性”，如下图所示。

显然，我们只需要知道了圆上的一个点的坐标 (x, y) ，利用八对称性，我们马上就能得到另外七个对称点的坐标。

和直线算法类似，Bresenham画圆算法也是用一系列离散的点来近似描述一个圆，如下图。

考虑圆心在原点，半径为R的圆在第一象限内的八分之一圆弧，从点（0, R）到点（R’ , R’ ）顺时针方向确定这段圆弧。假定某点P_i(x_i, y_i)已经是该圆弧上最接近实际圆弧的点，那么Pi的下一个点只可能是正右方的P1或右下方的P2两者之一，如下图所示：

构造判别函数：

F(x, y）= x² + y² – R²

当F(x, y）= 0，表示点在圆上，当F(x, y）> 0，表示点在圆外，当F(x, y）< 0，表示点在圆内。如果M是P₁和P₂的中点，则M的坐标是（x_i + 1, y_i – 0.5），当F（x_i + 1, y_i – 0.5）< 0时，M点在圆内，说明P₁点离实际圆弧更近，应该取P₁作为圆的下一个点。同理分析，当F（x_i + 1, y_i – 0.5）> 0时，P₂离实际圆弧更近，应取P₂作为下一个点。当F（x_i + 1, y_i – 0.5）= 0时，P₁和P₂都可以作为圆的下一个点，算法约定取P₂作为下一个点。

现在将M点坐标（x_i + 1, y_i – 0.5）带入判别函数F(x, y），得到判别式d：

d = F（x_i + 1, y_i – 0.5）= (x_i + 1)² + (y_i – 0.5)² – R²

若d < 0，则取P₁为下一个点，此时P₁的下一个点的判别式为：

d’ = F（x_i + 2, y_i – 0.5）= (x_i + 2)² + (y_i – 0.5)² – R²

展开后将d带入可得到判别式的递推关系：

d’ = d + 2x_i + 3

若d > 0，则取P₂为下一个点，此时P₂的下一个点的判别式为：

d’ = F（x_i + 2, y_i – 1.5）= (x_i + 2)² + (y_i – 1.5)² – R²

展开后将d带入可得到判别式的递推关系：

d’ = d + 2(x_i – y_i) + 5

特别的，在第一个象限的第一个点（0, R）时，可以推倒出判别式d的初始值d₀：

d₀ = F(1, R – 0.5) = 1 – (R – 0.5)² – R² = 1.25 – R

改进的中点Bresenham算法

中点画圆法中，计算判别式d使用了浮点运算，影响了圆的生成效率。如果能将判别式规约到整数运算，则可以简化计算，提高效率。于是人们针对中点画圆法进行了多种改进，其中一种方式是将d的初始值由1.25 – R改成1 – R，考虑到圆的半径R总是大于2，因此这个修改不会影响d的初始值的符号，同时可以避免浮点运算。

代码

(未改进)

参考资料

https://blog.csdn.net/zhouzhouzf/article/details/39183265

https://blog.csdn.net/MMogega/article/details/53055625