【计算机图形学】 圆的两种生成算法（角度微分法 Bresenham算法）

圆的两种生成算法（角度微分法、Bresenham算法）

文章目录

1.角度微分法的原理2.角度微分法的实现（基于matlab）3.Bresenham 算法的原理4.Bresenham 算法的实现（基于matlab）

1.角度微分法的原理

圆的角度微分法是用圆的内接正多边形来逼近该圆。

若我们设圆的参数方程为：

其中𝜑为旋转角，0° ≤ φ ≤ 360° 现把该圆 n 等分，用 n 条直线来逐次逼近该圆，则各直线的端点坐标计算如下：

设旋转角𝜑的起始角、终止角分别为α、β，且满足关系式0° ≤ α ≤ β ≤ 360°

把圆进行 n 等分，其对应的角度增量为：𝛥𝜑 = 2𝜋 ∕ 𝑛

则可以得到第 i 点所对应的角度与端点坐标为（其中 i = 0 , 1 , 2 , …… , n）：

上式即为生成圆的基本公式之一。我们不难看出，n 越大，精度越高，但计算也越 复杂。下一步是如何确定 R 和 n 的关系？

可以这样认为：如果圆的内接多边形的边线与理想圆弧之间的距离在一个刻度单位之内时，其近似显示效果是能接受的。如下图所示：

即：如果线段 ab 的距离在一个刻度单位内都是能被接受的，即要求 ab < 1

那 ab 的距离等于多少呢？显然 𝑎𝑏 = 𝑅 − 𝑅 ⋅ 𝑐𝑜𝑠𝛥𝜑 < 1

对于𝑐𝑜𝑠𝛥𝜑，可按泰勒级数展开取前两项，得到𝑐𝑜𝑠𝛥𝜑 = 1 − 𝛥𝜑2 / 2

将其带入 ab 中即得到 𝑅 − 𝑅 ⋅ (1 − 𝛥𝜑2 / 2 ) < 1，解之可得𝛥𝜑 < √(2 / 𝑅)

将𝛥𝜑 = 2𝜋 / 𝑛带入上式可得𝑛 > 𝜋 ⋅ √(2𝑅)

用经验公式取代得到 𝑛 = 0.1𝑅 + 15

这就是圆的半径与其内接正多边形边数之间的关系

2.角度微分法的实现（基于matlab）

下面给出利用matlab实现该算法的完整代码：

function main %测试主函数clcclear;DifferentiationOfCircle(100,'r')%调用角度微分法function DifferentiationOfCircle(R,color) %圆的角度微分算法n = 0.1*R+15; %计算出需要微分的次数delta = 2*pi/n;%从而得到每次需要增加的角度alpha = delta;%初始化alphax0 = R,y0 = 0;%初始化x0,y0hold onwhile(n>0)x = R*cos(alpha);y = R*sin(alpha);plot([x0,x],[y0,y]);%绘制点(x0,y0)和(x,y)之间的线段alpha = alpha + delta; %更新alphax0 = x , y0 = y;%更新x0、y0n = n-1; %n减1endgrid minorhold off

在matlab中运行上述代码，实验结果如下：

可以看出，角度微分法在绘圆时具有明显的分段现象。当然，我们可以通过加大 n 的值来适当减轻分段效果。不过这样的代价是会使得程序需花费更多的时间来进行微分。 所以这才有了𝑛 = 0.1𝑅 + 15 这一公式的出现。

3.Bresenham 算法的原理

圆可被定义为到给定中心位置 O（圆心）距离为 r 的点集。圆心位于原点的圆有四条对称轴 x=0,y=0, x=y 和 x=-y。若已知圆弧上一点(x,y),可以得到其关于四条对称轴的其它 7 个点，这种性质称为八分对称性（如下图所示）。因此，只要扫描转换八分之一圆弧，就可以求出整个圆弧的象素集。

所以接下来我们的重心就放在：如何将某段圆弧尽可能描绘清楚

对于上图中，点(y,x)所在那一段圆弧而言，其特征是 x 坐标变化率大于 y 坐标变化 率，且随着 x 的增加，y 在减小。因此逼近该圆弧的绘点步进规律是：每推算一次，其 x 坐标都加 1，而 y 坐标根据相应误差决定是否减 1。我们易知该圆中最上方的那个点的 坐标为(0,R)，将其设为(𝑥0,𝑦0)，则有ⅆ(𝑥0,𝑦0) = 0）。对于下一点而言，有两种可能：

① (𝑥0+1,𝑦0)

② (𝑥0+1,𝑦0−1)

现在我们的任务就是确定到底取谁。

在高中时，我们对于圆的定义式为：ⅆ(𝑥,𝑦) = 𝑥2 + 𝑦2 − 𝑅2。

这样定义的意义在于：对于某个给定点(𝑥0,𝑦0)，其值的正负能反应该点位于圆内 还是圆外。具体的规则如下：

若ⅆ(𝑥0,𝑦0) < 0，则表示该点位于圆内；

若ⅆ(𝑥0,𝑦0) > 0，则表示该点位于圆外；

若ⅆ(𝑥0,𝑦0) = 0，则表示该点位于圆内；

在确定到底取①还是②时，我们实际上并不关心它们到底在圆内还是圆外，我们只 关心它们到底谁距离圆的那一段圆弧更近。因此，我们可以将这两个点带入圆的定义式 中，即得到ⅆ(𝑥0+1,𝑦0)、ⅆ(𝑥0+1,𝑦0−1)，通过加绝对值的方式来获得这两点距离圆弧的绝对距离，最后取其中的较小值作为下一个点的位置即可。

因此，如果我们设：

ⅆ(𝑈𝑖) = (𝑥𝑖−1 + 1)2 + (𝑦𝑖)2 − 𝑅2

ⅆ(𝐷𝑖) = (𝑥𝑖−1 + 1)2 + (𝑦𝑖 − 1)2 − 𝑅2

则可以将圆的 Bresenham 算法的偏差判别式定义为：

ⅆ𝑖 = |ⅆ(𝑈𝑖)| − |ⅆ(𝐷𝑖)|

其原则是：

① 当 ⅆ𝑖 < 0 时，选 𝑈𝑖 作为下一个绘制的像素点

② 当 ⅆ𝑖 ≥ 0 时，选 𝐷𝑖 作为下一个绘制的像素点

将上面偏差判别式的绝对值去掉，得到:

ⅆ𝑖 = ⅆ(𝑈𝑖) + ⅆ(𝐷𝑖)

根据这个判别式，我们可通过一个循环来将八分之一圆弧绘制出，同时通过坐标变 换以将整个圆画出。但是，这个式子里的运算偏多，我们需要对其进行优化，以使整个 绘制过程中，尽量是以迭代运算为主，从而减少复杂的乘幂运算次数。

首先是将𝑈𝑖(𝑥𝑖−1 + 1, 𝑦𝑖−1)，𝐷𝑖(𝑥𝑖−1 + 1,𝑦𝑖−1 − 1)的坐标带入得到：

ⅆ𝑖 = 2(𝑥𝑖−1 + 1)2 + (𝑦𝑖−1 − 1)2 + (𝑦𝑖−1)2 − 2𝑅2

然后增加下标值可得到：

ⅆ𝑖+1 = 2(𝑥𝑖 + 1)2 + (𝑦𝑖 − 1)2 + 𝑦𝑖2 − 2𝑅2

将其作差（ⅆ𝑖+1 − ⅆ𝑖），得到：

𝛥ⅆ = 2((𝑥𝑖 + 1)2 − (𝑥𝑖−1 + 1)2) + ((𝑦𝑖 − 1)2 − (𝑦𝑖−1 − 1)2) + (𝑦𝑖2 − (𝑦𝑖−1)2)

① 当ⅆ𝑖 < 0时，选择的下一点是𝑈𝑖，此时𝑥𝑖 = 𝑥𝑖−1 + 1， 𝑦𝑖 = 𝑦𝑖−1，带入上式可得： 𝛥ⅆ = 4𝑥𝑖−1 + 6；

② 当ⅆ𝑖 ≥ 0时，选择的下一点是𝐷𝑖，此时𝑥𝑖 = 𝑥𝑖−1 + 1，𝑦𝑖 = 𝑦𝑖−1 − 1，带入上式 可得： 𝛥ⅆ = 4(𝑥𝑖−1 − 𝑦𝑖−1) + 10 。

这样一来，对于 ⅆ𝑖 的求解就由之前的算术求值变为了迭代求值，大大减少了程序的 运算时间。

4.Bresenham 算法的实现（基于matlab）

下面给出利用matlab实现该算法的完整代码：

function main %测试函数clcclear;Bresenham(100)%调用Bresenham算法function Plot(x,y)%此函数会将某个点集在对应的8个区域中所构成的弧线绘制出，从而构成一个圆plot(x,y,'r') %用红色的线绘制第一象限的圆弧plot(y,x,'r')plot(-x,y,'b')%用蓝色的线绘制第二象限的圆弧plot(-y,x,'b')plot(-x,-y','y') %用黄色的线绘制第三象限的圆弧plot(-y,-x,'y')plot(x,-y,'g')%用绿色的线绘制第四象限的圆弧plot(y,-x','g')function Bresenham(R) %Bresenham算法d = 0 , n = 1; %初始情况下d=0x(1) = 0 , y(1) = R;while(x < y)if(d < 0)d = d + 4*x(n) + 6;y(n+1) = y(n);elsed = d + 4*(x(n)-y(n)) + 10;y(n+1) = y(n) - 1;endx(n+1) = x(n) + 1;n = n + 1;endhold on;Plot(x,y);grid minor;hold off;

在matlab中运行上述代码，实验结果如下：

可以看出，Bresenham 算法在绘圆时不会出现明显的分段现象，但是却存在“抖动”弧。出现这一现象的原因是由于 plot 函数是对像素点进行连结绘制，这个函数并不具有平滑拟合的效果。但如果仅对此算法在描绘圆弧的点上进行评估的话，该算法的效果明显是优于微分算法的。