  This paper presents a fundamental algorithm, called VDB-EDT, for Euclidean
distance transform (EDT) based on the VDB data structure. The algorithm
executes on grid maps and generates the corresponding distance field for
recording distance information against obstacles, which forms the basis of
numerous motion planning algorithms. The contributions of this work mainly lie
in three folds. Firstly, we propose a novel algorithm that can facilitate
distance transform procedures by optimizing the scheduling priorities of
transform functions, which significantly improves the running speed of
conventional EDT algorithms. Secondly, we for the first time introduce the
memory-efficient VDB data structure, a customed B+ tree, to represent the
distance field hierarchically. Benefiting from the special index and caching
mechanism, VDB shows a fast (average \textit{O}(1)) random access speed, and
thus is very suitable for the frequent neighbor-searching operations in EDT.
Moreover, regarding the small scale of existing datasets, we release a
large-scale dataset captured from subterranean environments to benchmark EDT
algorithms. Extensive experiments on the released dataset and publicly
available datasets show that VDB-EDT can reduce memory consumption by about
30%-85%, depending on the sparsity of the environment, while maintaining a
competitive running speed with the fastest array-based implementation. The
experiments also show that VDB-EDT can significantly outperform the
state-of-the-art EDT algorithm in both runtime and memory efficiency, which
strongly demonstrates the advantages of our proposed method. The released
dataset and source code are available on https://github.com/zhudelong/VDB-EDT.

Robotics