三维带符号的欧氏距离变换及其应用

Three Dimensional Signed Euclidean Distance Transform and Its Applications

距离变换是图像处理中历史悠久的研究课题 .该文将二维带符号的欧氏距离变换推广到三维 ,对其进行了优化 ,分析了它的计算复杂度 ,并应用于解决计算机图形学中的两个重要问题 :第一 ,将图形对象的三角网格表示转换为它的距离场表示 .即首先将三角网格模型离散为体素表示 ,利用三维带符号的距离变换 ,将求空间一点到图形对象的最短距离的全局搜索过程 ,转化为求这一点到离它最近的特征体素所包含的图形对象部分的局部搜索过程 ;第二 ,利用类似的思想 ,求两张空间曲面之间的最短距离 .

The researches for distance transform have long history in image processing. In this paper, we extend two dimensional signed distance transform to three dimension, optimize it and analyze its computational complexity. Furthermore, we apply it to computer graphics. Firstly, it can be employed to transform the triangular mesh representation of graphics model into its distance field representation. By the three dimensional signed distance transform on the voxel representation of a graphics model, the global search for the point, which is closest to a given space point and on the graphical model, can be simplified to a local search. It greatly reduces the computational complexity. Secondly, and similarly, it can be employed to calculate the minimum distance between two pieces of surfaces in the space.