Chamfer distance transforms, proposed by Borgefors [Bor86],
issue from an assumption that the distance can be
computed only from values at neighboring positions plus a mask constant.
This approach enables precise computation the city-block ( metrics)
and chessboard (
metrics) distances,
but can only approximate
the Euclidean distance (
metrics). Therefore, more precise albeit
slower Vector distance transforms were introduced [Dan80],
propagating also position of the nearest surface point. To speed up
the computation, the multipass mask propagation was later replaced by
region growing [Cui97] and level-set [Set99,BMW98] approaches.
Traditionally, the distance computation issues from a segmented binary data, where the object surface voxel positions are confined to fixed grid point coordinates. However, mostly in volume graphics applications, this proved to be a precision limitation (for example, in offset surface computation [BMW98,SJ01]) and therefore techniques were developed, propagating distances to surfaces defined with subvoxel precision. To compute the field with even higher precision, for each voxel a corresponding nearest surface point is recomputed, utilizing information stored with its already processed neighbors.