Sparse grid distance transforms
We present a Sparse Grid Distance Transform (SGDT), an algorithm for computing and storing large distance fields. Although SGDT is based on a divide-and-conquer algorithm for distance transforms, its data structure is quite simplified. Our observations revealed that distance fields can be recovered from distance fields of sub-block cluster boundaries and the binary information of the cluster through a one-time distance transform. This means that it is sufficient to consider only the cluster boundaries and to represent clusters as binary volumes. As a result, memory usage is less than 0.5% the size of raw files, and it works in-core.
distance fields divide-and-conquer algorithm volume graphics