阅读 239

WebGL 直线直吗?

前言📒

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

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

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

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

直线段的扫描转换算法📈

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

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

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

数值微分法

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

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

yi+1=kxi+1+b=k(xi+Δx)+b=kxi+b+kΔx=yi+kΔx=yi+ky_{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

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

// 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);
  }
}
复制代码

效果如图:

注意,该算法仅适用于 k1|k| \leq 1 的情况,当 k>1k > 1 时,需要将 xyx,y 互换,即 yy 增加1,xx 对应增加 1k\frac{1}{k}

中点画线法

假如当前绘制的点是 (xi,yi)(x_i, y_i),则当在绘制下一个点时我们实际上有两种选择:P0(xi+1,yi)P_0(x_i + 1, y_i)P1(xi+1,yi+1)P_1(x_i + 1, y_i + 1)。若 M=(xi+1,yi+0.5)M=(x_i+1,y_i+0.5)P0P1P_0,P_1 的中点,QQ 为理想直线与直线 x=xi+1x=x_i + 1 的交点。则当 MMQQ 下方时,P1P_1 应为下一个像素点;否则,P0P_0 应为下一个像素点。这就是 中点画线法 的原理,如下图:

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

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

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

Bresenham 算法

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

  • d0.5d \geq 0.5 时,直线与 xi+1x_i+1 相交的点最接近于当前像素 (xi,yi)(x_i, y_i) 的右上方像素 (xi+1,yi+1)(x_i + 1,y_i + 1)
  • d<0.5d < 0.5 时,交点更接近于当前像素右侧的像素 (xi+1,yi)(x_i+1, y_i)

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

结束语🎬

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

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

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

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

感谢阅读,欢迎关注公众号:Refactor!