如何画一条"直"线

如何在计算机上画一条直线

想必我们在小学二年级学函数的时候就已经背得滚瓜烂熟：直线公式 。但在屏幕上显示一条直线，却不能直接套用这个数学公式——因为数学世界和屏幕世界有着本质的不同。

从”连续”到”离散”

数学上的直线由无数个没有大小的点组成，拥有无限的分辨率，是连续的。但显示器本质上是一个由像素（Pixel）组成的巨大网格，是离散的——每个像素有固定的位置，要么亮，要么不亮，不存在”半个像素”。

如上图所示，我们在计算机上只能”逼近”一条直线，画出一个个离理想直线最近的像素点。所幸现代显示器的分辨率足够高，肉眼几乎看不出锯齿。

光栅化（Rasterization）：将矢量图形（点、线、面）转换为像素点阵的过程，是计算机图形学中最基础的操作之一。无论是游戏中的 3D 场景还是 GUI 界面上的一个按钮，最终都要经过光栅化才能显示在屏幕上。

直线算法

问题定义：给定直线两端点 和 ，在屏幕上画出该直线。

下面介绍两种经典算法：DDA 和 Bresenham。其中 Bresenham 算法尤其重要——几乎所有规则图形的绘制都离不开它的思想。

DDA 算法（Digital Differential Analyzer）

DDA 算法的核心思想很朴素：从起点出发，每一步沿直线前进一个微小增量，四舍五入取最近的像素点。

推导

设直线斜率为 ：

根据斜率大小，选择一个方向作为”主方向”，每次前进 1 个单位，另一方向前进 或 个单位：

• 当 时（ 方向变化更快）：以 为主方向。每次 前进 1， 前进 ：

• 当 时（ 方向变化更快）：以 为主方向。每次 前进 1， 前进 ：

由于像素坐标必须是整数，每步计算出的 需要四舍五入后再绘制。

算法步骤

以 且 为例：

1. 计算 ，初始点
2. 绘制
3. 更新
4. 重复步骤 2-3，直到

下面这张图直观展示了 DDA 的执行过程：

DDA 算法的特点

Bresenham 算法

DDA 的致命弱点是依赖浮点数运算。1962 年，IBM 的 Jack Bresenham 提出了一种仅用整数运算的直线算法，至今仍是图形学中最优雅的算法之一。

直线的一般方程

将直线方程 改写为隐式形式。代入 ：

两边乘 并移项：

对于直线上的点，。对于不在直线上的点：

• 直线上方的点：
• 直线下方的点：

平面被这条直线分成了三个区域：

的符号就像一个指南针，告诉我们当前点在直线的哪一侧。

核心思想：中点决策

以下推导假设 （即 ），其他情况可以通过对称变换归约。

假设当前已画出像素点 ，下一个要画的点是 这一列上的哪个像素？由于 ， 最多变化 1，所以只有两个候选：

• E（East）：——保持 不变
• NE（Northeast）：—— 加 1

如何选择？Bresenham 的巧妙之处在于：考察两个候选点之间的中点 ，判断它在直线的上方还是下方：

• 若 在直线上方（），说明理想直线从 下方穿过 → 更近 → 选 E
• 若 在直线下方（），说明理想直线从 上方穿过 → 更近 → 选 NE

将 代入 ，得到判别式：

递推公式

直接每一步都重新计算 太浪费了，我们可以利用增量关系递推。

• 当选 E 时：下一个中点为

• 当选 NE 时：下一个中点为

初始值

第一个中点取 ：

至此，算法每步只需要比较 的符号，然后做一次整数加法。但 中还有 这个浮点数——所以我们把所有 值乘以 2，符号判断不受影响：

这样一来，整个算法中只涉及整数加减法和位左移（乘 2），没有任何浮点数运算！

算法步骤（）

1. 输入端点 和
2. 计算 ，，，，
3. 绘制点
4. ；若 ，则 ；否则 ，
5. 若 ，重复步骤 3-4

推广到任意斜率

上面只讨论了第一象限 的情况。对于其他七种情况，可以利用对称性：

实现时可以根据 、 的符号和大小关系，归约到统一框架。这也是 Bresenham 算法的强大之处——同样的思想适用于所有八分圆（octant）。

DDA vs Bresenham 对比

下一篇我们还是会围绕Bresenham算法展开，简单讲解一下讲解圆和椭圆的绘制。

这次的插图来自画师luoyu

图片地址：https://www.pixiv.net/artworks/116826824