轮廓体积的核心算法:完整指南深入解析spritefusion-sprite-normals的精确欧氏距离变换EDT实现

原创2026-11-01 16:58:101,990 阅读

轮廓体积的核心算法:完整指南深入解析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。

sprite normal map 法线贴图效果对比:左侧为精灵的法线贴图,右侧为响应光照的 2.5D 渲染效果

为什么"轮廓体积"需要距离变换?

法线贴图的本质,是把一张**高度图(relief)**求梯度后编码成 RGB。spritefusion-sprite-normals 的高度图由两部分叠加:

  • 轮廓体积(shape):根据不透明像素的轮廓,让精灵"鼓起来",边缘向内倾斜——这正是 EDT 的功劳;
  • 明暗细节(detail):根据手绘的明暗着色产生的浮雕,由 src/color.rs 把 sRGB 转成 Oklab 亮度后高斯模糊得到。

整个流程在 src/relief.rs 中串联:

  1. 按 alpha_threshold 构建不透明像素的布尔 mask;
  2. 对 mask 做 EDT,得到每个像素到"轮廓外最近点"的距离;
  3. 用对数压缩 ln_1p 把距离映射成高度,再经高斯平滑;
  4. 用 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)展示了可分离技巧:

  1. 逐行扫描:对每一行,"轮廓外"的行内像素 source = 0,"轮廓内"的 source = +∞。跑一遍 squared_line,得到每个像素到同一行轮廓外像素的平方距离;
  2. 逐列扫描:把上一行结果当作 source 数组,沿列方向再跑一遍 squared_line,此时得到的就是到任意方向最近轮廓外像素的精确平方距离;
  3. 开方: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 光影世界的核心所在。

登录后查看全文
spritefusion-sprite-normals