WebGL 直线直吗？

前言📒

如题，”直线直吗“？当思考这个问题时，我们回过头想想之前的文章所讲的直线是由什么组成的：WebGL 中图元有点、线和三角形，虽然三者都被定义为最基础的图形，但它们之间也有着密不可分的联系，正如《酒干倘卖无》中唱到的：”没有点哪有线“😉直线段便是由许多像素点组成的图形。

我们知道像素点其实是正方形的，那么如果展示的直线是水平或者垂直于水平方向的，那么像素点的排列也必然是沿水平或垂直于水平方向的，那么此时直线必然是直的。以俄罗斯方块距离，此时的直线应该是对应俄罗斯方块中的这个图形：

但大多数情况下直线并不是严格水平或竖直的，那么这种情况下，我们看到的直线更像是下面这些图形的排列组合：

那这些像素点是以何规则排布的呢？就此引出我们今天的主题——直线段的扫描转换算法👏

直线段的扫描转换算法📈

在之前将 WebGL 工作流程时我们提到过一个环节叫做 光栅化，比较标准地解释是确定最佳逼近图形的像素集合，并用指定属性写像素的过程称为光栅化或图形的扫描转换。

听懂没？没？说白了就是把图像转化为像素点的过程。

本篇主要介绍三种直线段光栅化的算法：数值微分法、中点画线法和 Bresenham算法。

数值微分法

数值微分法（DDA） 也称为 离散插值分析法 （本文统称为数值分析法）。

大家都知道在坐标系中可以用 $y = kx + b$ 来表示一条直线，那么当我们知道了我们要绘制线段的端点 $P_0(x_0, y_0)，P_1(x_1, y_1)$ 后，即可通过 两点式 求出其所在直线的表达式： $\frac{y-y_0}{y_1-y_0}=\frac{x-x_0}{x_1-x_0}$ ，从而再转换成 $y = kx + b$ 的形式。 $x，y$ 分别就是点在屏幕上的坐标，假设 $x$ 从 $P_0$ 开始，每次绘制向 $P_1$ 端点移动距离为1像素，那么我们要求的下一个点 $y_{i+1}$ ：

y_{i+1}=kx_{i+1}+b=k(x_i+\Delta{x})+b=kx_i+b+k\Delta{x} \\ =y_i + k\Delta{x}=y_i+k

这样我们就把求要绘制点的算法简化成了一个加法。同时，对屏幕而言，像素点的坐标值并没有小数一说所以需要对所求得的 $y$ 值进行四舍五入处理。代码如下：

// vertex shader
attribute vec4 a_Position;
void main() {
  // 为了更明显，特将点的大小设置为10px
  gl_PointSize = 10.0;
  gl_Position = a_Position;
}
// fragment shader
void main() {
  gl_FragColor = vec4(1.0, 1.0, 0.0, 1.0);
}

let current = 0; // 当前顶点索引
let handle = -1;
let a_Position;
const POINTS = []; // 要绘制的顶点数组
const P0 = [-300, -200]; // 起始端点
const P1 = [500, 200]; // 终止端点
const k = (P1[1] - P0[1]) / (P1[0] - P0[0]); // 斜率

// 主函数
// 与之前的基础文章内容大致相同，不再赘述
function main() {
  const canvas = document.querySelector('#canvas');
  const gl = canvas.getContext('webgl');

  initShaders(gl, VS, FS);

  a_Position = gl.getAttribLocation(gl.program, 'a_Position');

  gl.clearColor(0.0, 0.0, 0.0, 1.0);
  gl.clear(gl.COLOR_BUFFER_BIT);

  animation(gl);
}

function animation(gl) {
  if (current === P1[0] - P0[0]) { // 退出animation
    cancelAnimationFrame(handle);
    return;
  }
  DDA(gl);
  handle = requestAnimationFrame(() => animation(gl));
}

// DDA算法
function DDA(gl) {
  // 将下一个要绘制的点存入顶点数组，将px转为webgl系统使用的[-1.0, 1.0]
  POINTS.push([
    (current+P0[0])/1200, // x
    (Math.round(current*k+P0[1]))/800, // y
  ]);
  current++;

  gl.clear(gl.COLOR_BUFFER_BIT);

  // 循环绘制
  for(let i = 0; i < current; i++) {
    gl.vertexAttrib3f(a_Position, POINTS[i][0], POINTS[i][1], 0.0);
    gl.drawArrays(gl.POINTS, 0, 1);
  }
}

效果如图：

注意，该算法仅适用于 $|k| \leq 1$ 的情况，当 $k > 1$ 时，需要将 $x，y$ 互换，即 $y$ 增加1， $x$ 对应增加 $\frac{1}{k}$ 。

中点画线法

假如当前绘制的点是 $(x_i, y_i)$ ，则当在绘制下一个点时我们实际上有两种选择： $P_0(x_i + 1, y_i)$ 和 $P_1(x_i + 1, y_i + 1)$ 。若 $M=(x_i+1,y_i+0.5)$ 为 $P_0，P_1$ 的中点， $Q$ 为理想直线与直线 $x=x_i + 1$ 的交点。则当 $M$ 在 $Q$ 下方时， $P_1$ 应为下一个像素点；否则， $P_0$ 应为下一个像素点。这就是 中点画线法 的原理，如下图：

我们将直线方程标准化后可以得到： $F(x,y)=ax+by+c$ 的形式，其中 $a=y_0-y_1,b=x_1-x_0,c=x_0y_1-x_1y_0$ ，同时点与直线的有如下关系：

\begin{cases} 上方：F(x,y)>0 \\ 线上：F(x,y)=0 \\ 下方：F(x,y)<0 \end{cases}

因此，只需将点 $M$ 带入 $F(x,y)$ 即可判断中点 $M$ 与直线的关系。后续绘制就没什么两样了。

Bresenham 算法

该算法与中点画线法类似，只不过在此算法中定义了一个 误差项 $d$ ， $d$ 并不是一个固定值，而是随着顶点的改变而变化的。误差项初始值为0， $x$ 下标每增加1， $d$ 的值相应增加直线的斜率值 $k$ ，即 $d=d+k$ 。而要绘制顶点的位置与误差项 $d$ 关系如下：

$d \geq 0.5$ 时，直线与 $x_i+1$ 相交的点最接近于当前像素 $(x_i, y_i)$ 的右上方像素 $(x_i + 1,y_i + 1)$ ；
$d < 0.5$ 时，交点更接近于当前像素右侧的像素 $(x_i+1, y_i)$ ；

注意，假如下一个要绘制的点为右上方的像素时，因为我们选取了新的 $y$ 方向的基准点，故 $d$ 要减1。

结束语🎬

总结一下三种直线段扫描算法的原理：

数值微分法：使用 $y=kx+b$ ，求 $y$ ，并四舍五入得到下一个要绘制的像素；
中点画线法：如果中点在理想直线与 $x=x_i+1$ 交点的上方，则绘制右侧像素，反之绘制右上方像素；
Bresenham 算法：如果误差项 $d \ge 0.5$ ，则绘制右上方像素，反之绘制右侧像素。

这就是计算机如何绘制的直线，简简单单，不知和你想象中是否一致？我们在反过头看文章开篇的问题 “直线是直的吗”，或许你自己心中也有了答案！🤫

大家可以看到上面图片中的直线有锯齿，这是因为像素逼近有误差，会使图形发生畸变，这种现象称为走样。当然也有解决这种问题的技术方法，而这些技术则就称为 反走样，比如最粗暴的方法就是提高分辨率，同时还有 区域采样、加权区域采样 等方式。感兴趣的小伙伴可以自行了解😉

感谢阅读，欢迎关注公众号：Refactor！