Bresenham画线算法 一种精确而有效的光栅线生产算法 如图01
需要确定的是取样像素位置 是（11,11）还是（11,12） 如图02
现在我已经拿到Xk 要取Xk+1的位置 那么Y要取 Yk还是Yk+1呢 我们使用Dlower 和 Dupper 来标识2个像素与数学上线路径的垂直偏移 在像素列位置Xk+1处的直线上的Y坐标 Y = m(Xk+1) + b 那么 Dlower = Y - Yk 那么 Dupper = (Yk+1) - Y 要确定2像素中哪一个更接近线路径 ， 需测试2个像素偏移差 Dlower - Dupper = 2m(Xk + 1) - 2Yk + 2b - 1 m:为线的斜率 Yk 这个表示的是整形坐标上的点 这个点与线无关 是在线的下方看图 如图03
那么通过变化上面的公式 可以得到一个决策参数Pk ,设定 X 和 Y 分别为2个端点的垂直和水平偏移量 m = y / x Pk = X*(Dlower - Dupper)--为什么要乘以 X 本人觉得是为了好计算 因为他们同时成X 他们的距离哪个大的还是那个大 = 2 Y Xk - 2 X Yk + c (2 Y + 2b X - X) -- 化简来的 参数c值为(2 Y + 2b X - X) 且会在循环计算Pk 时被消除 当Pk 为负数 Dlower < Dupper Yk处的像素点 比 Yk+1处的像素点更接近 因为直线上的坐标会沿x或y方向的单位步长而变化 ，可以利用递增整数运算得到后继的决策参数 Pk+1 - Pk = 2Y（Xk+1 - Xk） - 2X(Yk+1 - Yk) 因为是单位递整 （Xk+1 - Xk） = 1 Pk+1 - Pk = 2Y - 2X(Yk+1 - Yk) 那么 Pk+1 = 2Y - 2X(Yk+1 - Yk) +Pk (Yk+1 - Yk)的值是取 1 还是 0 是由 Pk的正负号决定的 为什么？ 这里需要广大朋友解析
我们代码的步骤： 1 输入线段的2个端点，并将左端点存储在(X0,Y0)中； 2 将(X0,Y0)装入帧缓存，画出第一个点； 3 计算常亮 X , Y 2X 和 2Y - 2X 这些用在 Pk+1 = 2Y - 2X(Yk+1 - Yk) +Pk 这个公式里面 并得到决策参数的第一个值 P0 = 2Y - X； -- 这个值怎么来的呢 Y0 = mX0 + b m 的斜率 = Y/X 求出 b 带入 Pk = 2 Y Xk - 2 X Yk + c (2 Y + 2b X - X) 化简得到 2Y - X 4 从K = 0 开始 在沿线路径的每个Xk处 进行下列检查： 如果 Pk < 0 位置点(Xk +1,Yk) 并且 Pk+1 = Pk + 2Y 如果 Pk > 0 位置点(Xk +1,Yk + 1) 并且 Pk+1 = Pk + 2Y - 2X 5 重复步骤4
代码演示
void lineBres(int x0,int y0,int xEnd,int yEnd) { int dx = fabs(xEnd - x0), dy = fabs(yEnd - y0); int p = 2 * dy - dx;//第一个策划参数 int twoDy = 2 * dy, twoDyMinusDx = 2 * (dy - dx); int x, y; if (x0 > xEnd) { x = xEnd; y = yEnd; xEnd = x0; } else { x = x0; y = y0; } //SetPixel(x, y); while (x < xEnd) { x++; if (p < 0 ) { p += twoDy; } else { y++; p += twoDyMinusDx; } //SetPixel(x, y); } }
