在上篇文章最后，我们提到希望在聚合后的圆形上标注出点的数量：

潘与其：使用 k-d tree 实现点聚合图?

zhuanlan.zhihu.com图标

本文会围绕「如何在 WebGL 中渲染文字「这个问题展开。

  • 首先我们会介绍 WebGL 中几种常见的渲染文字方式。
  • 然后我们将著重介绍基于有向距离场的实现思路、存在的问题（在线性时间生成、圆角问题）以及对应的解法。
  • 最后使用 Mapbox 的 tiny-sdf 实现文字标注效果，完善之前的点聚合图。

几种渲染文字的方式

在介绍这些方法之前，必须要推荐 StackOverflow 上的这个总结性的回答，其中对比了各种方式的适用场景、优缺点，十分详细。因此本文这部分就尽量精简了：

Better Quality Text in WebGL?

stackoverflow.com图标

使用 DOM API 添加 HTML 元素是最直接的方式，「WebGL Programing Guide」中也介绍了这种 HUD 方案，在展示静态文本、且数量不大的场景中是很适合的：

WebGL Text - HTML?

webglfundamentals.org图标

而 Bitmap Fonts 方案类似 Web 中的 Sprite，如果需要生成动态的文字，可以一次上传包含全部字元的纹理，并记录下每个字元的位置：

https://webglfundamentals.org/webgl/lessons/webgl-text-glyphs.html?

webglfundamentals.org
Bitmap Fonts Atlas

但是这种方式只需要适用有限字元的场景中，中文、日文这样的非拉丁文就不太适合了。另外，一张点阵图也不可能包含所有字型大小，在放大时必然出现人工痕迹，下图中左1、左2：

https://github.com/libgdx/libgdx/wiki/Distance-field-fonts

在 3D 文字展示场景中，可以使用 TextGeometry。但即使只有少量文本，生成顶点数量也很大。

在艺术字效果（glitch、扭曲、粒子等）展示场景中，blotter.js.org/ 是一个不错的选择：

Blotter 艺术字效果

最后，还有一些直接在 GPU 中渲染字体的探索性方案：

Font Rendering is Getting Interesting · Aras website?

aras-p.info图标
  • 矢量纹理：GPU text rendering with vector textures
  • GLyphy：不同于其他使用纹理存储 SDF 的方案
  • PathFinder：使用 Rust 编写，需要 OpenGL ES 3.0+

但是，在地理信息展示的场景中，文本量很大，并且也需要展示中文这样的字元，因此以上方案都不太适用。

有向距离场

@拳四郎 的这篇文章介绍了使用有向距离场绘制基础图形、对 Valve 的论文：「Improved Alpha-Tested Magnification for Vector Textures and Special Effects」?? 的解读和实践，强烈推荐阅读：

拳四郎：Signed Distance Field?

zhuanlan.zhihu.com图标

下面引用的图片来自「Shape Decomposition for Multi-channel Distance Fields」这篇论文，89 页但是干货满满，包含了 msdf 的巧妙思路，后面我们也会介绍。

距离场存储了矢量信息，例如下图 16 x 16 的网格中，每个格子都存储了到黑色边缘的距离，其中红色表示处于形状内部，蓝色表示处于外部：

有向距离场存储的信息

这样在使用距离场重建原始图形时，每个网格只需要以存储的距离为半径画圆，就能逼近原始图形（黑色部分）了：

根据距离场重建

即使在低解析度的距离场中，利用二次线性插值也能得到平滑的效果。例如下图中只有白色网格点处存储了原始的距离信息，其余都是通过插值得到的：

生成了距离场之后，在 Shader 中使用也十分简单，至于 Outlining、Glows 等效果可以参考上面那篇文章，这里就不介绍了：

// https://github.com/Jam3/three-bmfont-text/blob/master/shaders/sdf.js

// 反走样
float aastep(float value) {
float afwidth = length(vec2(dFdx(value), dFdy(value))) * 0.70710678118654757;
return smoothstep(0.5 - afwidth, 0.5 + afwidth, value);
}
vec4 texColor = texture2D(map, vUv);
float alpha = aastep(texColor.a);
gl_FragColor = vec4(color, opacity * alpha);

但是这种方法存在两个问题。首先在地理信息展示场景中，需要在运行时生成包含中文的文字，因此必须在线性时间内生成距离场。另外，在使用低解析度的距离场重建时，字元的拐角处过于平滑不能保持原有的尖锐效果。下面我们来看针对这两个问题的解决方案。

线性时间生成

最暴力的遍历方法 O(n^2) 肯定是不能接受的，一张 300K 的图片就意味著需要 900 亿次对距离的运算，我们需要高效的 O(n) 的演算法才能在运行时完成。

对于二维网格，距离场中的「距离」为欧式距离，因此 EDT（Euclidean Distance Transform）定义如下。其中 (x,y) 为构成形状的点集 P ，而 f(x, y) 为 sampled function。在网格中如果 (x, y) in P 则 f(x, y) = 0，否则为 infty ：

其中第一部分与 y『 无关，可以展开成两趟一维的 DT 计算，其中第一趟固定 x：

因此我们只需要考虑一维的距离平方：

如果从几何角度来理解上述一维距离平方场计算公式，其实是一组抛物线，每个抛物线最低点为 (q, f(q))：

因此这组抛物线的下界，即下图中的实线部分就代表了 EDT 的计算结果：

为了找出这个下界，我们需要计算任意两个抛物线的交点横坐标，例如对于（x=r, x=q）这两根抛物线，交点横坐标 s 为：

抛物线求交

现在我们有了计算 EDT 1D 的预备知识，按照从左往右的顺序，将下界最右侧的抛物线序号保存在 v[] 中。下界中每一段抛物线的边界保存在 z[] 中。这样计算下一段抛物线 x=q 时，只需要与 v[k] 抛物线求交，交点横坐标与 z[k] 的位置关系只有如下两种：

两个抛物线交点与当前最右交点的位置关系

完整演算法如下：

Mapbox 的 tiny-sdf 实现了上述演算法（EDT 1D），连变数名都是一致的。我们后续的 DEMO 将直接使用它在运行时生成 SDF 纹理。

mapbox/tiny-sdf?

github.com图标

对于 2D EDT 的计算正如我们本节开头介绍的，分解成两趟 1D 距离平方，最后开方得到结果。这里也能直接看出对于 height * width 尺寸的网格，复杂度为 O(n)：

function edt(data, width, height, f, d, v, z) {
// Pass 1
 for (var x = 0; x < width; x++) {
for (var y = 0; y < height; y++) {
f[y] = data[y * width + x];
}
// 固定 x 计算 1D 距离平方
 edt1d(f, d, v, z, height);
for (y = 0; y < height; y++) {
data[y * width + x] = d[y];
}
}
// Pass 2
 for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
f[x] = data[y * width + x];
}
edt1d(f, d, v, z, width);
for (x = 0; x < width; x++) {
// 开方得到欧式距离
 data[y * width + x] = Math.sqrt(d[x]);
}
}
}

最后，除了欧式距离( L_{2} )，如果要计算 city block( L_{1} ) 或者 Chessboard(L_{infty} ) ，同样也可以分解成两趟实现 O(n) 复杂度。详细演算法可以参考这份 Slide：「CS664 Computer Vision 7. Distance Transforms」??。

原始图、Euclidean distance(L2)、City block(L1) 和 Chessboard 距离场

圆角问题

虽然在地图场景中，对于放大字体时呈现的平滑转角是可以容忍的，但是对于这个问题的解法还是有必要了解一下。

左侧为 SDF 重建效果，右侧为 MSDF

距离场是可以进行集合运算的。例如下图中，我们将两个距离场分别存储在点阵图的两个分量（R、G）中，在重建时，虽然这两个距离场转角是平滑的，但是进行求交就能得到锐利的还原效果：

使用分解后的两个距离场求交重建

分解演算法可以参考原论文「Shape Decomposition for Multi-channel Distance Fields」?? 中4.4 节：Direct multi-channel distance field construction。

在实际使用时，作者提供了 MSDF 生成工具 github.com/Chlumsky/msd，可以看出 MSDF 在低解析度效果明显更好，甚至优于更高解析度的 SDF：

MSDF 与 SDF 效果对比

在重建时使用 median：

// https://github.com/Jam3/three-bmfont-text/blob/master/shaders/msdf.js

float median(float r, float g, float b) {
return max(min(r, g), min(max(r, g), b));
}
vec3 sample = texture2D(map, vUv).rgb;
float sigDist = median(sample.r, sample.g, sample.b) - 0.5;

DEMO 效果

为我们之前的点聚合图加上标注吧：

视频封面

00:09

使用 tiny-sdf 生成 SDF 十分简单，当然更好的改进方式是对当前出现的所有字元生成一张 atlas，每次有新字元出现再更新它：

import TinySDF from tiny-sdf;
const tinySDFGenerator = new TinySDF(fontsize, buffer, radius, cutoff, fontFamily, fontWeight);

const cache: {
[key: string]: {
width: number;
height: number;
data: Uint8ClampedArray;
};
} = {};

export function generateSDF(text: string) {
if (!cache[text]) {
cache[text] = tinySDFGenerator.draw(text);
}
return cache[text];
}

DEMO 地址：xiaoiver.github.io/cust

GitHub 地址：github.com/xiaoiver/cus

参考资料

  • 「Shape Decomposition for Multi-channel Distance Fields」??
  • 「Distance Transforms of Sampled Functions」??
  • 「A GENERAL ALGORITHM FOR COMPUTING DISTANCE TRANSFORMS IN LINEAR TIME」??
  • 「CS664 Computer Vision 7. Distance Transforms」??
  • Better Quality Text in WebGL
  • Font Rendering is Getting Interesting · Aras website

推荐阅读：

相关文章