关于图形学:Dead-Reckoning算法生成有向距离场

有向间隔场（signed distance field，SDF）是一张标注了每个像素到最近几何体边缘间隔的位图。因为在几何轮廓之外提供了额定的信息，SDF 能为二维渲染减少很多灵活性，比方渲染文字时任意调整笔画粗细、放大形态时没有显著锯齿、通过穿插淡化两张 SDF 来穿插淡化几何轮廓等等。

这里介绍一种通用的有向间隔场生成办法：Dead Reckoning（原始文献），它可能从二维位图形容的几何轮廓计算 SDF。不同于之前的一些近似算法会失去有“棱角”的后果，Dead Reckoning 得出的后果简直是精确的，靠近于全局遍历失去的参考后果。

Dead Reckoning 这个名字来源于船舶导航办法，名字中的“dead”可能来源于“deduced”简称之后的语音流变。这种导航办法通过观察一个指标之外的固定标志物来推算与导航指标之间的方位和间隔，这与算法中通过观察街坊像素来寻找最近边界有些类似，故而得名。

Dead Reckoning 与生物信息学畛域的 Needleman-Wunsch 序列比对算法相似，都是一种动静布局算法。在处理过程中，它岂但记录每个像素的边界间隔，而且记录对应边界的像素地位，或者说以后的间隔是“从哪来的”。

整个计算过程会遍历两遍矩阵，第一次从上向下、从左向右逐行遍历所有像素，第二次反过来从下向上、从右向左。

假如输出几何形态存在位图 I 上，外部像素值为 1，内部像素值为 0；位图 d 用来存储间隔，位图 p 用来存储每个像素的最近边界地位的坐标。

位图d：将位于边际的地位设为零，所有其它地位设为无穷大。

位图p：将位于边际的地位设为指向本身，所有其它地位设为某个非法值。

这里有个细节问题：如何定义边际地位。原论文认为该当既蕴含那些位于几何形态外部的像素，也蕴含位于内部的像素。也就是说，边界的宽度为 2 像素。这样的起因是为了数学对称性：将内外部的定义颠倒，对应的 SDF 也是原 SDF 求正数。但实际上咱们通常并不关怀这个对称性，只计入外部的那条边界就能够了。所以边际的条件是：

I[x,y] == 1 and (I[x,y]!= I[x-1,y] or 
    I[x,y]!= I[x+1,y] or 
    I[x,y]!= I[x,y-1] or 
    I[x,y]!= I[x,y+1] )

遍历每个像素的时候，将它的以后距边界间隔与曾经解决过的四个街坊比拟，如果街坊的以后距边界间隔 + 像素间隔比它本人的要小，阐明街坊对应的边界更近，就应用街坊的边界信息，并依此更新本人的间隔。

假如左上角是(0,0)，那么正向遍历的四个街坊就是它的左、左上、上、右上像素，反向遍历的四个街坊是它的右、右下、下、左下像素。

图中正在进行正向遍历的过程。绿色像素是曾经解决过的。蓝色像素是以后要解决的像素，它会从四个相邻的已解决像素（标为深绿色）中获取最近的那个边界地位。

伪代码如下：

// 正向遍历
for y in 1 to height {
    for x in 1 to width {curr_d = d[x,y];
        curr_p = p[x,y];
        // 查看左上像素
        if d[x-1,y-1] + 1.414 < curr_d {curr_p = p[x-1,y-1];
            curr_d = distance((x,y), curr_p);
        }
        // 查看正上方像素
        if d[x,y-1] + 1 < curr_d {curr_p = p[x,y-1];
            curr_d = distance((x,y), curr_p);
        }
        // 查看右上像素
        if d[x+1,y-1] + 1.414 < curr_d {curr_p = p[x+1,y-1];
            curr_d = distance((x,y), curr_p);
        }
        // 查看正左方像素
        if d[x-1,y] + 1 < curr_d {curr_p = p[x-1,y];
            curr_d = distance((x,y), curr_p);
        }
        d[x,y] = curr_d;
        p[x,y] = curr_p;
    }
}

// 反向遍历
for y in height to 1 {
    for x in width to 1 {curr_d = d[x,y];
        curr_p = p[x,y];
        // 查看左下像素
        if d[x-1,y+1] + 1.414 < curr_d {curr_p = p[x-1,y+1];
            curr_d = distance((x,y), curr_p);
        }
        // 查看正下方像素
        if d[x,y+1] + 1 < curr_d {curr_p = p[x,y+1];
            curr_d = distance((x,y), curr_p);
        }
        // 查看右下像素
        if d[x+1,y+1] + 1.414 < curr_d {curr_p = p[x+1,y+1];
            curr_d = distance((x,y), curr_p);
        }
        // 查看正右方像素
        if d[x+1,y] + 1 < curr_d {curr_p = p[x+1,y];
            curr_d = distance((x,y), curr_p);
        }
        d[x,y] = curr_d;
        p[x,y] = curr_p;
    }
}

在正反两次遍历之后，间隔 d 曾经填充实现，然而没有辨别几何体内外。如果须要这个辨别，只须要再遍历依此图像，将位于外部的像素的间隔变成负的。

当解决位于位图边缘的像素时，逻辑上须要拜访不存在的越界像素。无妨令 I[越界] 为 0（里面不属于几何体外部，这很正当），d[越界]为无穷大（于是永远不会指向里面的像素坐标），p[越界]为非法值。

Dead Reckoning 算法应用每个像素街坊的部分信息代替了全局搜寻，为什么依然能够失去比拟精确的后果呢？这可能是因为 Voronoi 域自身就是比拟邻域性的：在引入一些小的地位变动之后，其 Voronoi 域要么放弃不变，就算变动也通常是以后 Voronoi 域的某个街坊域，简直不可能跑到齐全不相干的老远的一个域上，所以遍历像素的街坊就足够了。

就算几何形态很简单，然而像素形容的几何形态有精度极限：就是像素大小。那么在同样的精度级别上做遍历解决，大抵上仍然是足够的。

关于图形学:Dead-Reckoning算法生成有向距离场

简介

算法

数据初始化

两次遍历

越界解决

一点思考