光栅化算法-中点画圆算法
中点画圆算法
对圆形光栅化时，只需考虑在极坐标下 \(\theta\in[\pi/4,\pi/2]\) 的点即可，其他的点可通过对称法绘制。
将圆形光栅化的算法类似于Bresenham算法。设当前绘制的点的坐标为 \(P_{k}(x_{k},y_{k})\) ，那么下一个点的坐标为 \(P_{k+1}(x_{k+1},y_{k+1})\) 。从 \(x\) 轴开始取样，那么 \(x_{k+1}=x_{k}+1\) ，而 \(y_{k+1}\) 的值可能为 \(y_{k}\) 或 \(y_{k}-1\) 。为确定具体绘制的点，需引入一个决策参数 \(p\) 。
设圆函数为 \(f(x,y)=x^2+y^2-r^2\) ，其中 \(r\) 表示圆的半径。取两个可能的点的中点 \((x_{k}+1,y_{k}-\frac{1}{2})\) ，将其带入圆函数，定义决策参数为：
\[p_{k}=f(x_{k}+1,y_{k}-\frac{1}{2})=(x_{k}+1)^2+(y_{k}-\frac{1}{2})^2-r^2
\]
将初始顶点 \(P_{1}(0, r)\) 代入决策参数方程可得初始决策参数 \(p_{1}=\frac{5}{4}-r\) 。再通过 \(p_{k+1}-p_{k}\) 的方式即可得到决策参数 \(p_{k}\) 的递推方程：
\[p_{1}=\frac{5}{4}-r
\]
\[p_{k+1}=\left\{\begin{matrix}p_{k}+2x_{k+1}-2y_{k+1}+1,p_{k}\ge0\\p_{k}+2x_{k+1}+1,p_{k}<0\end{matrix}\right.
\]
如果程序输入时的半径 \(r\) 恒为整数，则可将初始决策参数设置为 \(p_{1}=1-r\) 。由于递推方程中的计算均为整数计算，因此修改后不影响结果。
C++/OpenGL实现
下述代码为中点画圆算法绘制任意圆形的C++/OpenGL实现：
/**
* 画出所有对称的点
*/
void circlePlotPoints(GLint ox, GLint oy, GLint dx, GLint dy) {
glVertex2i(ox + dx, oy + dy);
glVertex2i(ox + dx, oy - dy);
glVertex2i(ox + dy, oy + dx);
glVertex2i(ox + dy, oy - dx);
glVertex2i(ox - dx, oy + dy);
glVertex2i(ox - dx, oy - dy);
glVertex2i(ox - dy, oy + dx);
glVertex2i(ox - dy, oy - dx);
}
/**
* 中点画圆算法
*/
void midPointCircle(GLint ox, GLint oy, GLint r) {
int dx = 0, dy = r; // 当前绘制的点与圆心的横纵坐标差值
int p = 1 - r; // 决策参数
circlePlotPoints(ox, oy, dx, dy);
while (dx < dy) {
dx++;
if (p >= 0) {
dy--;
p += ((dx - dy) << 1) + 1;
} else {
p += (dx << 1) + 1;
}
circlePlotPoints(ox, oy, dx, dy);
}
}