Creator_Chen's Dream Island

中点圆扫描转换算法跟中点直线扫描转换算法使用相同的像素选择策略。即对于圆周上一点，要从两个候选像素中选择一个作为其光栅化结果，而选择的依据是这两个候选像素连线的中点跟圆的位置关系。可以像分析中点直线扫描转换算法那样来分析中点圆扫描转换算法的执行过程。由于圆的对称性，可以只对圆周的1/8进行光栅化，其他部分的光栅化结果可以利用其对称性简单的求出。对于宽度为1，圆心在原点的1/8圆弧的光栅化，假设现在正处于算法的执行过程中，并假设算法的当前步选中了像素P（如下图所示），那么算法的下一步将从像素E和像素SE中选择一个作为光栅化结果。

像素E和像素SE的选择依据是他们连线的中点M跟圆的位置关系。如果M在圆外，显然像素SE离圆弧更近，选择像素SE.否则，就选择像素E.利用圆的隐式方程可以容易的判断一个点跟圆的位置关系。对于圆心在原点，半径为r的圆，其隐式方程为x² + y² = r².设d = F(x, y) = x² + y² - r²则：

• d > 0时，点在圆外。
• d < 0时，点在圆内。
• d = 0时，点在圆上。

对于上图中的M，d = F(x_p + 1, y_p - 1/2).

• d > 0时，M在圆外，选择SE作为光栅化结果。算法下一步将使用M_SE计算新的d值，此时Δd = d_new - d = F(x_p + 2, y_p - 3/2) - F(x_p + 1, y_p - 1/2) = 2x_p - 2y_p + 5.
• d < 0时，M在圆内，选择E作为光栅化结果。算法下一步将使用M_E计算新的d值，此时Δd = d_new - d = F(x_p + 2, y_p - 1/2) - F(x_p + 1, y_p - 1/2) = 2x_p + 3.
• d = 0时，M在圆上，处理过程同d < 0时的情况。

现在已经可以总结出圆心位于原点，宽度为1，半径为r的圆的光栅化算法了。如下：

以上代码中有三个需要注意的问题：

1. 代码假设光栅化过程中x ≠ y.事实上，x是否等于y取决于半径r的值。在下面两种情况下，算法的下一步x是等于y的，要进行特殊处理，否则x = y的像素不会被绘制。
   • 假设当前步选中了像素P(x_p, y_p)（其中x_p + 1 = y_p - 1），并且下一步中d > 0.
   • 假设当前步选中了像素P(x_p, y_p)（其中x_p + 1 = y_p），并且下一步中d ≤ 0.
2. 这段代码假设待光栅化的圆的圆心位于原点，将其扩展为适合任意位置圆心也非常容易。计算出一个像素坐标后，将圆心坐标加在像素坐标上做偏移量即可。
3. 上面代码每一步在计算nDeltaE和nDeltaSE时都要求解一个多项式的值，其实有更高效的方法来计算它们。由于n次多项式的差分是n - 1次多项式，所以只需要计算出nDeltaE和nDeltaSE的差分就可以在每一步中简单的累加一个常量来求出它们的值。nDeltaE和nDeltaSE的差分计算如下：
还是假设算法当前选中了像素P(x_p, y_p)，此时nDeltaE = 2 * x_p + 3，nDeltaSE = 2 * (x_p - y_p) + 5.
• 如果下一步选中了E(x_p + 1, y_p)，那么下一步的nDeltaENew = 2 * (x_p + 1) + 3，nDeltaSENew = 2 * (x_p + 1 - y_p) + 5，则ΔnDeltaE = nDeltaENew - nDeltaE = 2，ΔnDeltaSE = nDeltaSENew - nDeltaSE = 2.
• 如果下一步选中了SE(x_p + 1, y_p - 1)，那么下一步的nDeltaENew = 2 * (x_p + 1) + 3，nDeltaSENew = 2 * (x_p + 1 - y_p + 1) + 5，则ΔnDeltaE = nDeltaENew - nDeltaE = 2，ΔnDeltaSE = nDeltaSENew - nDeltaSE = 4.

修改后的算法代码如下：