Distance field transform with an adaptive iteration method

Fan Chen, Ye Zhao
Department of Computer Science, Kent State University, Kent, Ohio, USA
IEEE International Conference on Shape Modeling and Applications, 2009. SMI 2009


   title={Distance field transform with an adaptive iteration method},

   author={Fan, C.},



Download Download (PDF)   View View   Source Source   



We propose a novel distance field transform method based on an iterative method adaptively performed on an evolving active band. Our method utilizes a narrow band to store active grid points being computed. Unlike the conventional fast marching method, we do not maintain a priority queue, and instead, perform iterative computing inside the band. This new algorithm alleviates the programming complexity and the data-structure (e.g. a heap) maintenance overhead, and leads to a parallel amenable computational process. During the active band propagating from a starting boundary layer, each grid point stays in the band for a lifespan time, which is determined by analyzing the particular geometric property of the grid structure. In this way, we find the Face-Centered Cubic (FCC) grid is a good 3D structure for distance transform.We further develop a multiple-segment method for the band propagation, achieving the computational complexity of O(m middot N) with a segment-related constant m.
No votes yet.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: