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

2023-04-12 06:13:13 来源：博客园

(相关资料图)

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

中点画圆算法

对圆形光栅化时，只需考虑在极坐标下 \(\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);}

关键词：