光栅化算法-中点画圆算法

光栅化算法-中点画圆算法

中点画圆算法

对圆形光栅化时,只需考虑在极坐标下 \(\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 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);
    }
}
/**
 * 画出所有对称的点
 */
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);
}

热门相关:地球第一剑   无法隐瞒的本能:偷拍   姐妹们的丑闻   别那么骄傲   仗剑高歌