昨晚去圖書館看了《計算機圖形學——OpenGL實現》關于Bresenham算法的另一種推導方式。
Bresenham最精妙之處在于通過方程變換，然后得到迭代方程，從而消除了浮點運算。
下面簡單寫寫自己對中點法推導的理解：
記：W = bx - ax, H = by - ay
所以 （ax, ay）和（bx, by）的理想直線為：
-W*(y-ay) + H*(x-ax) = 0
記：函數 f(x, y) = -2*W*(y-ay) + 2*H*(x-ax);
f(x,y)有如下性質：
f(x, y) < 0, 那么(x, y)在直線上方
f(x, y) > 0, 那么(x, y)在直線下方
現考慮 點L(Px+1, Py), 點U(Px+1, Py+1), 則LU中點M(Px+1, Py+1/2) 有：
如果f(Mx, My) < 0, 則M在理想直線上方， 所以選擇L
如果f(Mx, My) > 0, 則M在理想直線下方， 所以選擇U
則：
f(Mx,My) = -2*w*(Py+1/2-ay) + 2*H*(Px+1-ax)
當 x從Px+1移動到Px+2時， 考慮f變化M'和M'':
M'：在前一步沒有增加y, M' = (Px+2, Py+1/2)
M''：在前一步增加了y, M' = (Px+2, Py+3/2)
對于 M'：
f(M'x, M'y) = -2*w*(Py+1/2-ay) + 2*H*(Px+2-ax) = f(Mx, My) + 2 * H
對于 M''：
f(M''x, M''y) = -2*w*(Py+3/2-ay) + 2*H*(Px+2-ax) = f(Mx, My) - 2 * (W-H)
所以
對于下一個“測試量”都有一個常數增量：前一次沒有增加y，增量為2*H，如果增加了y，則增量為-2*(W-H)
對于初始條件：x = ax, y = ay
M = (ax+1, ay+1/2);
f(Mx, My) = -2*W*(ay+1/2-ay) + 2*H(ax+1-ax) = 2*H-W
Code:
#include <stdlib.h>
#include <math.h>
#include <GL/glut.h>
void myInit() 
{
glClearColor(1.0, 1.0, 1.0, 0.0);
glColor3f(0.0, 0.0, 0.0);
//glPointSize(2.0);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0.0, 640.0, 0.0, 480.0);
}
void setPixel(int x, int y) {
glBegin(GL_POINTS);
glVertex2i(x, y);
glEnd();
}
void lineBres(int xs, int ys, int xe, int ye) {
int W = xe - xs, H = ye - ys, f = 2 * H - W, tH = 2 * H, tHW = 2 * (H - W);
int x, y;
if (xs > xe) {
x = xe;
y = ye;
xe = xs;
} else {
x = xs;
y = ys;
}
while (x <= xe) {
setPixel(x, y);
x++;
if (f<0) {
f += tH;
} else {
y++;
f += tHW;
}
}
}
void myDisplay() {
glClear(GL_COLOR_BUFFER_BIT);
lineBres(20, 10, 300, 180);
glFlush();
}
int main(int argc, char **argv) {
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
glutInitWindowSize(640, 480);
glutInitWindowPosition (100, 150);
glutCreateWindow("Bresenham畫線");
glutDisplayFunc(myDisplay);
myInit();
glutMainLoop();
return 0;
}posted on 2007-10-11 11:57
豪 閱讀(1155)
評論(0) 編輯 收藏 引用 所屬分類:
計算機圖形學