光柵化演算法-中點畫圓演算法
中點畫圓演算法
對圓形光柵化時，只需考慮在極坐標下 \(\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);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549756.html
標籤：其他
上一篇：記憶體對齊的規則