轮廓体积的核心算法:完整指南深入解析spritefusion-sprite-normals的精确欧氏距离变换EDT实现
轮廓体积的核心算法:完整指南深入解析spritefusion-sprite-normals的精确欧氏距离变换EDT实现
spritefusion-sprite-normals 是一款用 Rust 编写的 normal map(法线贴图)生成工具,能从任意 2D 像素风精灵(sprite)、sprite sheet 以及 GIF/APNG 动画中生成可响应动态光照的法线贴图,让 2D 素材获得 2.5D 的立体感。本文面向新手,深入解析它生成"轮廓体积"的核心——**精确欧氏距离变换(Exact Euclidean Distance Transform, EDT)**的实现原理,并带你走读源码 src/distance.rs。
为什么"轮廓体积"需要距离变换?
法线贴图的本质,是把一张**高度图(relief)**求梯度后编码成 RGB。spritefusion-sprite-normals 的高度图由两部分叠加:
- 轮廓体积(shape):根据不透明像素的轮廓,让精灵"鼓起来",边缘向内倾斜——这正是 EDT 的功劳;
- 明暗细节(detail):根据手绘的明暗着色产生的浮雕,由 src/color.rs 把 sRGB 转成 Oklab 亮度后高斯模糊得到。
整个流程在 src/relief.rs 中串联:
- 按
alpha_threshold构建不透明像素的布尔 mask; - 对 mask 做 EDT,得到每个像素到"轮廓外最近点"的距离;
- 用对数压缩
ln_1p把距离映射成高度,再经高斯平滑; - 用 3×3 Sobel 算子求梯度,归一化后写入法线贴图的 RGB 通道(透明像素保持中性的
[128, 128, 255])。
let mut shape = distance::edt(&mask, width, height);
let reach = settings.shape_radius;
for value in &mut shape.data {
let inset = (*value - 0.5).max(0.0);
*value = settings.shape_strength * reach * (inset / reach).ln_1p();
}
💡 对数压缩(
ln_1p)是关键的一笔:距离本身离边缘越远增长越快,直接取用会导致精灵"中间平顶、边缘陡崖";对数让高度在轮廓附近最陡、向内逐渐变缓,形成自然的"鼓包"。
什么是精确欧氏距离变换?
给定一张二值 mask,EDT 要求对每个不透明像素,计算它到最近的"非不透明像素"的欧氏距离:
d(x, y) = √( (x−x′)² + (y−y′)² ) 的最小值,(x′, y′) 为轮廓外像素
如果用最朴素的双重循环逐像素比较(brute force),复杂度是 O(n × m²),对一张 200×200 的精灵就要上亿次运算。
而 spritefusion-sprite-normals 采用的是经典的 Felzenszwalb–Huttenlocher 算法:把距离场表示为一系列抛物线(二次函数)的下包络(lower envelope),使得每一维的变换都是 O(n) 线性的。它有两个重要性质:
- 精确:结果与暴力法在数学上完全一致(只存在浮点误差),不是八邻域 chamfer 之类的近似;
- 可分离:二维变换可以拆成"先逐行、再逐列"两次一维变换,代码极其简洁。
逐行走读 1D 变换:squared_line 函数
核心代码在 src/distance.rs 的 squared_line 函数中,它把一维的"到最近源点距离"问题转化为"抛物线下包络"问题。
把每个候选源点 q(高度为 source[q])看成一个抛物线:
f_q(x) = (x − q)² + source[q]
所有抛物线的下包络,在每个 x 位置的值就是"到最近源点"的平方距离。算法分两步:
1. 求包络:维护站点表 sites 与切换点 starts
遍历每个候选源点 q,把它对应的抛物线加入下包络:
-
计算新抛物线与"上一个站点 p"的交点
intersection,公式直接来自两式相减:intersection = (h_q + q² − h_p − p²) / (2(q − p))
-
若交点落在上一个站点的生效区间之前,说明上一个站点被完全压制,弹出它(
sites.pop()),再和前一个比较; -
否则该交点就是新站点的生效起点,记入
starts。
这个过程类似单调栈:每个站点最多入栈、出栈各一次,整段是 O(n)。注意 !height.is_finite() 的跳过逻辑——"无穷远"的源点直接不参与包络。
2. 求值:指针单次扫描
包络建成后,用指针 active 从左到右扫描输出位置 q:只要下一个切换点 starts[active+1] < q,就把指针右移一位。由于指针只前进、不后退,扫描同样是 O(n)。最后用 delta.mul_add(delta, ...) 算出 (q − site)² + height,一次 FMA 指令完成平方距离。
从 1D 到 2D:可分离两趟扫描
edt 入口函数(src/distance.rs)展示了可分离技巧:
- 逐行扫描:对每一行,"轮廓外"的行内像素 source = 0,"轮廓内"的 source = +∞。跑一遍
squared_line,得到每个像素到同一行轮廓外像素的平方距离; - 逐列扫描:把上一行结果当作 source 数组,沿列方向再跑一遍
squared_line,此时得到的就是到任意方向最近轮廓外像素的精确平方距离; - 开方:
result.data[...] = value.sqrt(),恢复成真实欧氏距离。
为什么这样是精确的?因为欧氏距离的平方可以分解:d² = dx² + dy²。第一趟在 x 方向枚举了所有 x 候选,把 dx² + h(x) 求了下包络;第二趟把这个"合成高度" h(x) 当作新源点在 y 方向再求一次下包络,恰好完成 min(dx² + dy²) 的全局搜索。
🎯 工程细节:两趟共用同一个
source/destination缓冲(width.max(height)大小),零重复分配;所有中间值都保持"平方距离"形态,直到最后一步才统一开方,避免反复 sqrt。
用暴力法做"对表":内置的精确性测试
精确算法最怕"看起来对"。src/distance.rs 里自带了一个严格的回归测试:
- 对 1×1 到 16×12 的全部尺寸、用 LCG 伪随机生成的 mask;
- 对每个像素,用双重循环暴力枚举所有轮廓外像素,取
dx.hypot(dy)的最小值作为期望值; - 断言 EDT 结果与暴力值误差小于 1e-5(无穷远情况要求同为无穷)。
也就是说,每次 cargo test --locked 都会自动验证"精确性"这一承诺。上层还有一组端到端测试(tests/generation.rs)验证法线贴图的性质:圆盘精灵的法线应当朝外指向、中心保持 <a href="https://link.gitcode.com/i/4d62eb03a62452f69d3880ac8a807131" target="_blank">128, 128, 255] 中性、解码后的法线是单位向量、sprite sheet 中邻近的小岛互不干扰(见 [src/components.rs 的八连通岛屿拆分,保证每块轮廓独立做 EDT)。
调优轮廓体积:三个关键参数
EDT 输出的原始距离只是"原料",最终观感由 src/settings.rs 中的三个默认参数控制,CLI 也提供对应开关:
| CLI 参数 | 默认值 | 作用 |
|---|---|---|
--shape-radius |
4 |
轮廓坡度衰减的作用半径(像素),决定"鼓包"影响多深 |
--shape-strength |
1.15 |
轮廓体积的整体高度 |
--shape-softness |
1.15 |
高度图的高斯平滑强度,数值越大边缘越柔和 |
例如想做出更强的"浮雕体积":
spritefusion-sprite-normals sprite.png -o sprite_n.png --shape-strength 2 --shape-radius 6
⚠️ 法线 PNG 是数据纹理:在游戏引擎中记得关闭 sRGB 采样,否则会破坏法线方向。
小结:这套 EDT 实现好在哪?
- ✅ 精确而非近似:抛物线下包络给出与暴力法一致的数学结果,并经全尺寸暴力对表测试背书;
- ✅ 线性复杂度:行 + 列两趟 O(n) 扫描,对 4,194,304 像素的上限(见 src/lib.rs)轻松胜任,且内循环对 SIMD 友好;
- ✅ 代码极简:核心仅一个 ~40 行的
squared_line+ 一个 25 行的edt入口,无 unsafe(Cargo.toml 中unsafe_code = "forbid"); - ✅ 纯 Rust 全栈:同一套代码既编译成 CLI(src/main.rs),也编译成 WebAssembly 在浏览器本地运行(src/wasm.rs),处理数据不出机器。
理解了这个"抛物线包络 + 可分离两趟扫描"的模式,你就掌握了图像处理中距离场、轮廓膨胀、骨架提取等一系列算法的通用钥匙——这正是 spritefusion-sprite-normals 把 2D 像素画变成 2.5D 光影世界的核心所在。