【计算机图形学】Bresenham算法改进——MATLAB实现「建议收藏」

这是我参与11月更文挑战的第1天，活动详情查看：2021最后一次更文挑战

1 引言

直线的扫描转换算法比较著名的有DDA算法和Bresenham算法，后者相较于前者虽过程稍复杂，但效率较高。本文将在Bresenham算法的基础上加以改进，主要有以下几点：

• 将所有判别式的浮点型化为整型
• 将直线上所有点存储后再一次性绘制
• 输出直线上所有点的坐标

2 思路

算法推到均只考虑直线斜率在0~1之间，其他斜率可通过对称性转化为基本情况。

中点算法的核心在于比较待选点中点与直线的位置关系，如果直线在中点上方，则取偏上方的点；反之取偏下方的点

改进算法的大致步骤如下：

1. 首先绘制起点

2. 将直线表示为隐式方程，
   $d_{0}=F\left(x_{0}+1, y_{0}+0.5\right)=0.5-k$

3. 将浮点型化为整型只需乘以
   $2\Delta x$，即
   $d_{0}=2\Delta x-\Delta y$（
   $\Delta x,\Delta y$为直线起终点坐标差）

4. 接下来递归判断
   $d$的符号：

   • 若
     $d<0$，则
     $(x,y)$更新为
     $(x+1,y+1)$，
     $d$更新为
     $d+2\Delta x-2\Delta y$
   • 否则
     $(x,y)$更新为
     $(x+1,y)$,
     $d$更新为
     $d-2\Delta y$

5. 计算判别式的同时存储点，直到绘制完最后一个点；

3 过程

首先求得直线斜率，将所有情况转化为k>=0&&k<=1

k=(y1-y0)/(x1-x0);
if k>=-1&&k<0 %-1<=k<0,y轴对称
    x0=-x0;
    x1=-x1;
end
if k>1 %k>1,交换xy
    temp0=x0;temp1=x1;
    x0=y0;x1=y1;
    y0=temp0;y1=temp1;
end
if k<-1 %k<-1
    temp0=x0;temp1=x1;
    x0=-y0;x1=-y1;
    y0=temp0;y1=temp1;
end
% 保证起始点y坐标较小
if y1-y0<0
    tempX=x0;tempY=y0;
    x0=x1;y0=y1;
    x1=tempX;y1=tempY;
end

接下来构造判别式，首先构造初始表达式，再递归为下一个表达式赋值，并循环保存点

deltaX=x1-x0;
deltaY=y1-y0;
d=deltaX-2*deltaY; %(0.5-k)*2*(x1-x0)
% 保存点,当x>x1时退出循环
while(x<x1) 
    if d<0 %取上方点
        x(end+1)=x(end)+1;
        y(end+1)=y(end)+1;
        d=d+2*(deltaX-deltaY);
    else %取下方点
        x(end+1)=x(end)+1;
        y(end+1)=y(end);
        d=d-2*deltaY;
    end
end

为了得到所绘制直线上的每一个点，需将存储的各坐标转换回其对应的坐标系。

简而言之，我们在第一步将所有直线斜率均转化为0~1时，其实已经改变了直线起终点的坐标，现在我们需输出正确的坐标，需将它们转化回去。

% 转为正确的坐标
if k>=-1&&k<0
    x=-x;
elseif k>1
    temp=x;
    x=y;
    y=temp;
elseif k<-1
    temp=-x;
    x=y;
    y=temp;
end

最后执行一次绘制即可plot(x,y,'r.');

4 运行结果

在命令行输入几条执行语句，可将不同直线组合起来绘制自定义的形状

完整代码请见 Bresenham(gitee.com)