目录问题描述Bresenham算法基本思想算法推演特殊斜率：0 Bresenham算法是图形学非常经典的光栅线生成算法，可用于显示直线、圆以及其他曲线。这里通过算法画直线过程，了解其工作原理。 问题描述 已知线段2端点\((x_0, y_0) (x_e, y_e)\)，屏幕上画出该直线段。 由于屏幕是通过像素点显示的，只能通过像素点所在的整数坐标近似代表直线上点的位置。那么，该用什么点画出直线呢？这就是Bresenham算法要解决的问题。 Bresenham算法 基本思想 根据当前点，决定下一个（像素）点画在哪儿。要么在相邻点，要么在对角点。相邻点是指x坐标+1、y坐标不变，或者x不变、y+1；对角点是指x+1，同时y+1。 要确定2个备选点中的哪一个，可根据它们到直线的距离远近决定：如果相邻点更近，下一点选相邻点；如果对角点更近，下一点就选对角点。 为减少误差，用光栅直线逼近理论直线，Bresenham算法按变化大的轴（x轴或y轴）逐像素绘制线段。 算法推演 假设直线方程：\(y = mx + b\) 因为线段2端点在直线上，所以，\(y_0=mx_0+b, y_e=mx_e+b\) 线段x、y坐标变化：\(∆x=x_e-x_0, ∆y=y_e-y_0\) 斜率m、截距b： \[m=∆y/∆x=(y_e-y_0)/(x_e-x_0 ), b=y_0-mx_0=y_0-x_0∆y/∆x \tag{1} \] 如果现在画到了第k个像素点，位置\((x_k,y_k)\)，那么第k+1个点\((x_{k+1},y_{k+1})\)在哪？ 由于斜率影响算法的过程，可以分情况讨论： 特殊斜率：0 ∵0 < m < 1 ∴Δx>Δy ∴可按x轴递增绘制像素点，即\(x_{k+1}=x_k+1\)； ∵m > 0且线段连续 ∴y递增，\(y_{k+1}\)取值只能是\(y_k\)或\(y_k+1\)。 => 第k+1点\((x_{k+1}, y_{k+1})\)有2个选择：\((x_k+1,y_k ) or (x_k+1,y_k+1)\) tips: 哪个像素点距离直线更近，Bresenham算法就选择那个点作为下一个要绘制的点。然而，计算点到直线的距离方法复杂，而且涉及(斜率)浮点数运算。为了简化运算，Bresenham算法并没有用点到线的垂直距离，而是利用y轴或x轴方向的偏移替代。 根据\((1)\)，直线在\(x_{k+1}\)位置的y值（理论值）： \[ y=mx_{k+1}+b=m(x_k+1)+b \tag{2} \] 记2个备选点\(y_k, y_k+1\)到直线的竖直偏移分别为\(d_{1}, d_{2}\)，有： \[\tag{3} \begin{aligned} d_{1} & = y-y_k \\\\ & = m(x_k+1)+b-y_k \end{aligned} \] \[\tag{4} \begin{aligned} d_{2} & = (y_k+1)-y \\\\ & = y_k+1-m(x_k+1)-b \end{aligned} \] 这里利用了m范围：0 < m < 1，有\(d_{1} > 0, d_{2} > 0\)，可知， \[y_{x+1}=\begin{cases} y_k & d_{1} < d_{2}, y_k更近 \\\\ y_{k+1} & d_{1} ≥ d_{2}, y_{k+1}更近 \end{cases} \] 要判断哪个点距离更近，将\((3)(4)\)做差值： \[d_{1}-d_{2} = 2m(x_k+1)-2y_k+2b-1 \tag{5} \] 其中，斜率m、截距b都是常数。 将\(m=∆y/∆x\)代入\((5)\)，两边同时乘∆x，可得， \[ ∆x(d_{1}-d_{2}) = 2∆y(x_k+1)-2∆xy_k+∆x(2b-1) \] 令常数c：\(c=∆x(2b-1)\)，可得第k步决策参数： \[\tag{6} \begin{aligned} p_k & = ∆x(d_{1}-d_{2}) \\\\ & = 2∆y(x_k+1) - 2∆xy_k+c \end{aligned} \] ∵m > 0 ∴∆x>0 ∴\(p_k, d_{1}-d_{2}\)同号 问题转化为求\(p_k\)。 1)求\(p_k\)递推公式 根据\((6)\)，当k取值k+1时，有 \[ p_{k+1} = 2∆y(x_{k+1}+1)-2∆xy_{k+1}+c \tag{7} \] \((7)-(6)\)可得递推公式， \[ p_{k+1} - p_k = 2∆y(x_{k+1}-x_k)-2∆x(y_{k+1}-y_k) \tag{8} \] ∵\(x_{k+1}=x_k+1\), \(y_{k+1}-y_k\)取值（0或1）取决于\(p_k\)的符号。 ∴ \[p_{k+1}=\begin{cases} p_k+2∆y-2∆x & p_k ≥ 0 \\\\ p_k+2∆y & p_k < 0 \end{cases} \] 2)求初值\(p_0\) ∵起始点\((x_0, y_0)\)在直线上 ∴ \[ \begin{aligned} p_0 & = 2∆y(x_0+1)-2∆xy_0 + c \\\\ & = 2∆y(x_0+1)-2∆xy_0 + ∆x(2b-1) \end{aligned} \] 又\(b=y_0-mx_0=y_0-x_0∆y/∆x\) => \(∆xb=∆xy_0-x_0∆y\) ∴ \[p_0=2∆y-∆x \tag{9} \] 综上，可将0 输入线段2端点，左端点存储在\((x_0, y_0)\)； 将\((x_0, y_0)\)装入帧缓存，画出第一个点； 计算常量\(∆x, ∆y, 2∆y, 2∆y-2∆x\)，得到决策参数初值：\(p_0=2∆y-∆x\) 从k=0开始，沿着线段路径，每个\(x_k\)处，计算下一个要绘制的点位置： 如果\(p_k<0\)，下一个要绘制点\((x_k+1, y_k)\)，且\(p_{k+1}=p_k+2∆y\)； 否则，下一个要绘制点\((x_k+1, y_k+1)\)，且\(p_{k+1}=p_k+2∆y-2∆x\)； 重复步骤4)，共计∆x-1次。 可写出0 void setPixel(int x, int y) { glBegin(GL_POINTS); glVertex2i(x, y); glEnd(); } // case 0 < m < 1 void lineBresenham(int x0, int y0, int xe, int ye) { int dx = abs(xe - x0), dy = abs(ye - y0); int p = 2 * dy - dx; int twoDy = 2 * dy, twoDx = 2 * dx, twoDyMinusDx = 2 * (dy - dx); int x, y; /* determine which endpoint to use as a start point */ if (x0 > xe) { x = xe; y = ye; xe = x0; } else { x = x0; y = y0; } setPixel(x, y); // draw pixel while (x < xe) { x++; if (p < 0) { p += twoDy; } else { y++; p += twoDyMinusDx; } setPixel(x, y); } } 其他斜率 简化一下推理过程。 当0 从像素点角度看，整个过程： x: x0 -> xe, 递增(↑), x每次+1 y: y0 -> ye, 非递减(↑), y是否+1取决于p符号, 而p可由递推公式计算 有\(Δx > Δy\)，可按x轴逐像素绘制，x每次+1 => \(x_{k+1} = x_k + 1\) ∵y=f(x): y = mx + b连续且递增 ∴\((x_k, y_k)\)下一像素点\((x_{k+1}, y_{k+1})\)选择：\((x_{k+1}, y_{k})\) or \((x_{k+1}, y_{k}+1)\) => \[y_{k+1}=\begin{cases} y_k & , y_k 更近 \\\\ y_k + 1 & , y_k + 1更近 \end{cases} \] \(x_{k+1}\)处垂直偏移\(d_{1}\), \(d_{2}\)分别用来（近似）代表点\((x_k+1, y_k)\), \((x_k+1, y_k+1)\)到直线的距离（均>=0）。 \[\begin{aligned} d_{1} & = y(x_{k+1}) - y_k \\\\ & = (mx_{k+1} + b) - y_k \\\\ & = [m(x_k + 1) + b] - y_k \end{aligned} \] \[\begin{aligned} d_{2} & = y_{k+1} - y(x_{k+1}) \\\\ & = (y_k + 1) - (mx_{k+1} + b) \\\\ & = (y_k + 1) - [m(x_k + 1) + b] \end{aligned} \] \(d_{1}, d_{2}\)做差值， \[d_{1} - d_{2} = 2m(x_k+1) - 2y_k + 2b - 1 \] 两边乘以\(Δx\)，可得决策参数\(p_k\)： \[\begin{aligned} p_k & = Δx(d_{1} - d_{2}) = Δx[2m(x_k+1) - 2y_k + 2b - 1] \\\\ & = 2Δy(x_k+1) - 2Δxy_k + Δx(2b-1) \end{aligned} \] k取k + 1，可得 \[\begin{aligned} p_{k+1}-p_k &= 2Δy(x_{k+1} - x_k) - 2Δx(y_{k+1} - y_k) +0, \because b为常数 \therefore2b-1项做差值为0 \\\\ & = 2Δy - 2Δx(y_{k+1} - y_k) \end{aligned} \] 根据\(y_{k+1}\)与\(y_k\)关系，可得， \[p_{k+1} - p_k = \begin{cases} 2Δy & , y_k更近, d_{low} < d_{upper}<=>p_k<0 \\\\ 2Δy - 2Δx & , y_k+1更近, d_{low} > d_{upper}<=>p_k>0 \end{cases} \] 注：Δx>0, Δy>0 而初值\(p_0\)， \[\begin{aligned} p_0 &= [2Δy(x_0+1) - 2Δxy_0]+Δx(2b-1) \\\\ & = ... + 2Δxb - Δx , \because b = y - xΔy/Δx \therefore Δxb = Δxy - Δyx\\\\ & = ... + 2(Δxy_0 - Δyx_0) - Δx \\\\ & = 2Δy-Δx \end{aligned} \] 当-1 从像素点角度看，整个过程： x: x0 -> xe, 递增(↑), x每次+1 y: y0 -> ye, 非递增(↓), y是否-1取决于p符号，p由递推公式计算 \((x_k, y_k)\)下一像素点：\((x_k + 1, y_k)\) or \((x_k + 1, y_k - 1)\) \[\begin{aligned} d_{1} &= y_k - y(x_k+1) \\\\ & = y_k - [m(x_k+1)+b] \end{aligned} \] \[\begin{aligned} d_{2} &= y(x_k+1)-(y_k-1) \\\\ & = m(x_k+1)+b - (y_k-1) \end{aligned} \] 做差值可得， \[d_{1} - d_{2} = 2y_k - 2m(x_k+1) - 2b - 1 \] 发现与0 \[\begin{aligned} p_k &= Δx(d_{1} - d_{2}) \\\\ & = 2Δxy_k-2Δy(x_k+1)-2Δxb-Δx \end{aligned} \] 将\(p_{k+1}\)与\(p_k\)做差值，求递推公式： \[\begin{aligned} p_{k+1} - p_k &= 2Δx(y_{k+1}-y_k) - 2Δy(x_{k+1}-x_k) + 0 \\\\ &=2Δx(y_{k+1}-y_k) - 2Δy, \because x_{k+1}-x_k=1 \\\\ &=\begin{cases} -2Δy & , y_k更近<=>d_{1} -2Δx-2Δy & , y_k-1更近<=>d_{1}>d_{2}<=>p_k<0 \end{cases} \end{aligned} \] 注: Δx>0, Δy<0 ∵Δx>0 ∴\(p_k\)与\(d_{1}-d_{2}\)同号 初值\(p_0\)：\(p_0=-2Δy-Δx\) 综合 0 \[p_{k+1}-p_k=\begin{cases} 2|Δy| & , p_k < 0 \\\\ 2|Δy|-2|Δx| & , p_k > 0 \end{cases} \] 当m>1时，只需要将0 当m<-1时，只需要将-1 可以写出下面程序，适用于所有斜率的Bresenham算法： // 在(x,y)位置绘制像素点 void set_pixel(int x, int y) { glBegin(GL_POINTS); glVertex2i(x, y); glEnd(); } // 适用所有斜率的通用Bresenham画线算法 // (x1,y1) (x2, y2)是线段两端点 void bresenham_line(int x1, int y1, int x2, int y2) { int dx = x2 - x1; int dy = y2 - y1; int stepX = dx >= 0 ? 1 : -1; int stepY = dy >= 0 ? 1 : -1; dx = abs(dx); dy = abs(dy); if (dx > dy) { // |m| < 1 int p = 2 * dy - dx; int y = y1; for (int x = x1; x != x2; x += stepX) { set_pixel(x, y); if (p > 0) { y += stepY; p -= 2 * dx; } p += 2 * dy; } } else { // |m| >= 1 int p = 2 * dx - dy; int x = x1; for (int y = y1; y != y2; y += stepY) { set_pixel(x, y); if (p > 0) { x += stepX; p -= 2 * dy; } p += 2 * dx; } } } 参考 [1]DonaldHearn,M.PaulineBaker,赫恩,等.计算机图形学(第四版)[M].电子工业出版社,2014. [2]KATEX公式编辑器符号大全-CSDN的Mardown公式支持 | CSDN
Bresenham画直线算法（所有斜率）
