An Efficient Code-Based Voxel-Traversing Algorithm

The paper considers an e cient approach to traversing a uniformly-subdivided space pierced by a line segment. A voxel, as the basic constituent element of the uniformly subdivided space, is restricted to having the form of a cube. The algorithm works in two steps. In the rst step, the so-called Bresenham voxels are identi ed and, by comparing their position codes, their type of connectivity is determined. To achieve the required connectivity between neighbouring voxels, the second step of the algorithm is applied to nd the missing voxels. In this way, the algorithm e ciently switches between face-, edge- and vertex-connectivity. Although the algorithm works with floating-point precision, it is extremely computationally e cient, and tests of speed compared with the M¨uller, Cleary & Wyvill, Amanatides & Woo, and Zem cik algorithms are described.