Bresenham布雷森曼算法

【计算机图形学】画线算法——Bresenham算法(任意斜率)_bresenham算法原理-CSDN博客

一个朴素的观点：直线穿过两个像素点，哪个像素点离直线比较近，就用哪个像素点来表示这个直线的点。

为什么不直接用直线公式计算点的位置，然后取整呢？y=round(m*x+c)

因为这会涉及到三个问题：

• 斜率m的计算使用了除法，这回引入额外风险和计算量
• m是浮点数，浮点数的乘法的计算量会比整数高
• 需要使用round()函数取整，涉及到大小比较

而Bresenham算法可以避免上诉三个问题

定义：

• m：斜率
• $p_k$：算法第k步的决策参数

$m=\frac{x_2-x_1}{y_2-y_1}=\frac{\Delta x}{\Delta y}\\ p_k=\Delta x(d_1 - d_2)$

推导：

f(x) & = & m(x_k+1)+b &\\ d_1 & = & f(x_k+1)-y_k & = &m(x_k+1)+b-y_k\\ d_2 & = & (y_k + 1) - f(x_k+1) & = &y_k+1-m(x_k+1)-b\\ d_1-d_2 & = & 2m(x_k+1)-2y_k-2b+1

$p_k=\Delta x(d_1-d_2)=2x_k\Delta y - 2y_k\Delta x + c$

其中$c=2\Delta y+\Delta x(2b-1)$

通过$p_k$来判断像素点的取值：

\text{if }p_k<0,\text{ i.e. }d_1<d_2,\text{then }y_{k+1}=&y_k\\ \text{if }p_k\geqslant 0,\text{ i.e. }d_1\geqslant d_2,\text{then }y_{k+1}=&y_k+1\\

同理：

$p_{k+1}-p_k=(x_{k+1}-x_k)2\Delta y-2(y_{k+1}-y_k)\Delta x$

当$0<m<1$时，$x_{k+1}=x_k+1$，则：

$p_{k+1}-p_k=2\Delta y-2(y_{k+1}-y_k)\Delta x$

其中$y_{k+1}-y_k$的值取决于$p_k$：

$p_{k+1}= \begin{cases} p_k+2\Delta y , &\text{when }p_k <0,\text{i.e. }y_{k+1}=y_k\\ p_k+2\Delta y - 2\Delta x, &\text{when }p_k \geqslant 0,\text{i.e. }y_{k+1}=y_k+1 \end{cases}$

初始化：

其实端点$(x_0,y_0)$处的决策参数$p_0$为：

\begin{flalign} d_1=&y-y_0=m(x_0+1)+b-y_0=m\\ d_2=&(y_0+1)-y=y_0+1-m(x_0+1)-b=1-m\\ d_1-d_2=&2m-1\\ p_0=&\Delta x(d_1-d_2)=(2m-1)\Delta x=2\Delta y-\Delta x \end{flalign}

为什么$p_k$不这么算？因为$p_k$这样算会使用斜率m，这就和最开始提出的问题没有太大差别了。

以上都是基于$0<m<1$讨论的，在整个二维平面则需要讨论四种情况

• $0<m<1$
• $1<m$
• $-1<m<0$
• $m<-1$

// Bresenham's line drawing algorithm
// Code taken from a stack overflow answer: https://stackoverflow.com/a/16405254
void rst::rasterizer::draw_line(Eigen::Vector3f begin, Eigen::Vector3f end)
{
    auto x1 = begin.x();
    auto y1 = begin.y();
    auto x2 = end.x();
    auto y2 = end.y();

    Eigen::Vector3f line_color = {255, 255, 255};

    int x,y,dx,dy,dx1,dy1,px,py,xe,ye,i;

    dx=x2-x1;
    dy=y2-y1;
    dx1=fabs(dx);
    dy1=fabs(dy);
    px=2*dy1-dx1; //p0初始化
    py=2*dx1-dy1;

    if(dy1<=dx1)
    {
        if(dx>=0)
        {
            x=x1;
            y=y1;
            xe=x2; // xe:x_end
        }
        else
        {
            x=x2;
            y=y2;
            xe=x1;
        }
        Eigen::Vector3f point = Eigen::Vector3f(x, y, 1.0f);
        set_pixel(point,line_color); // 初始点赋值
        for(i=0;x<xe;i++)
        {
            x=x+1;
            if(px<0) // pk<0: d1<d2
            {
                px=px+2*dy1;
            }
            else
            {
                if((dx<0 && dy<0) || (dx>0 && dy>0)) // 斜率是正的
                {
                    y=y+1;
                }
                else
                {
                    y=y-1;
                }
                px=px+2*(dy1-dx1);
            }
//            delay(0);
            Eigen::Vector3f point = Eigen::Vector3f(x, y, 1.0f);
            set_pixel(point,line_color); // 画线
        }
    }
    else
    {
        if(dy>=0)
        {
            x=x1;
            y=y1;
            ye=y2;
        }
        else
        {
            x=x2;
            y=y2;
            ye=y1;
        }
        Eigen::Vector3f point = Eigen::Vector3f(x, y, 1.0f);
        set_pixel(point,line_color);  // 初始点pixel赋值
        for(i=0;y<ye;i++)
        {
            y=y+1;
            if(py<=0)
            {
                py=py+2*dx1;
            }
            else
            {
                if((dx<0 && dy<0) || (dx>0 && dy>0))
                {
                    x=x+1;
                }
                else
                {
                    x=x-1;
                }
                py=py+2*(dx1-dy1);
            }
//            delay(0);
            Eigen::Vector3f point = Eigen::Vector3f(x, y, 1.0f);
            set_pixel(point,line_color);
        }
    }
}