• 即将更新图形学,编译原理,机器学习等文章,谢谢关注~
  • 由于算法限制,搜索时注意简化关键字,谢谢支持~
  • 网站不兼容IE5.0及以下,请使用主流浏览器访问.
  • OpenGL实现Bresenham画圆算法

    中点Bresenham算法

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

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

     

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

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

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

    构造判别函数:

    F(x, y)= x+ y– R2

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

    现在将M点坐标(xi + 1, yi – 0.5)带入判别函数F(x, y),得到判别式d:

    d = F(xi + 1, yi – 0.5)= (xi + 1)2 + (yi – 0.5)2 – R2

    若d < 0,则取P1为下一个点,此时P1的下一个点的判别式为:

    d’ = F(xi + 2, yi – 0.5)= (xi + 2)2 + (yi – 0.5)2 – R2

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

    d’ = d + 2xi + 3

    若d > 0,则取P2为下一个点,此时P2的下一个点的判别式为:

    d’ = F(xi + 2, yi – 1.5)= (xi + 2)2 + (yi – 1.5)2 – R2

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

    d’ = d + 2(xi – yi) + 5

    特别的,在第一个象限的第一个点(0, R)时,可以推倒出判别式d的初始值d0

    d0 = F(1, R – 0.5) = 1 – (R – 0.5)2 – R2 = 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

    读者评分
    [评分人数: 1 平均分: 5]

    评论

    OmegaXYZ