直線光柵化-Bresenham演算法
Bresenham演算法
設兩個頂點為 \(P_{1}(x_{1},y_{1})\) 和 \(P_{2}(x_{2},y_{2})\) ，且滿足 \(\Delta x =x_{2}-x_{1}>0\) 且 \(\Delta y=y_{2}-y_{1}>0\) ，則兩點確定的直線方程的斜率為 \(k=\frac{\Delta y}{\Delta x}\) ，當 \(0<k<1\) 時，從 \(x\) 軸開始取樣，演算法的決策引數遞推方程為：
\[p_{1}=2\Delta y-\Delta x \]\[p_{k+1}=\left\{\begin{matrix} p_{k}+2\Delta y-2\Delta x,p_{k}\ge0 \\ p_{k}+2\Delta y,p_{k}<0 \end{matrix}\right. \]當 \(p_{k}\ge0\) 時 \(y_{k+1}=y_{k}+1\) ，當 \(p_{k}<0\) 時 \(y_{k+1}=y_{k}\) ，
當 \(k>1\) 時，則交換 \(x\) 和 \(y\) 變數，則變換后的直線方程斜率 \(k'=\frac{1}{k}\in(0,1)\)，此時歸結為上述情況，
對于一般的直線光柵化演算法，只需根據坐標系象限的對稱性修改上述引數即可，
C++/OpenGL實作
下述代碼為Bresenham演算法繪制任意直線的C++/OpenGL代碼實作：
void drawLineBresenham(GLint x1, GLint y1, GLint x2, GLint y2) {
int deltaX = x2 - x1, deltaY = y2 - y1;
double k = 1.0 * deltaY / deltaX;
deltaX = abs(deltaX), deltaY = abs(deltaY);
if (k < -1 || 1 < k) { // 斜率小于-1或大于1則交換x和y變數
int tt = abs(deltaX); deltaX = abs(deltaY); deltaY = tt;
}
int p = (deltaY << 1) - deltaX; // 決策引數
int dp1 = (deltaY << 1) - (deltaX << 1), dp2 = (deltaY << 1); // 快取遞推時常量
int dx = (x1 < x2) ? 1 : -1, dy = (y1 < y2) ? 1 : -1; // 繪制方向
int count = deltaX; // 繪制次數
glVertex2i(x1, y1);
if (-1 < k && k < 1) {
for (int i = 1; i < count; i++) {
x1 += dx; y1 += (p >= 0) ? dy : 0; // 計算下一個坐標
glVertex2i(x1, y1);
p += (p >= 0) ? dp1 : dp2; // 計算下一個決策引數
}
} else {
for (int i = 1; i < count; i++) {
x1 += (p >= 0) ? dx : 0; y1 += dy; // 計算下一個坐標
glVertex2i(x1, y1);
p += (p >= 0) ? dp1 : dp2; // 計算下一個決策引數
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549672.html
標籤：其他
上一篇：自己動手從零寫桌面作業系統GrapeOS系列教程——4.1 在VirtualBox中安裝CentOS
下一篇：三重境