昨晚去图书馆看了《计算机图形学——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
豪 阅读(1117)
评论(0) 编辑 收藏 引用 所属分类:
计算机图形学