An Efficient Code‐Based Voxel‐Traversing Algorithm

Abstract

The paper considers an efficient 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 first step, the so‐called Bresenham voxels are identified 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 find the missing voxels. In this way, the algorithm efficiently switches between face‐, edge‐ and vertex‐connectivity. Although the algorithm works with oating‐point precision, it is extremely computationally efficient, and tests of speed compared with the Müller, Cleary & Wyvill, Amanatides & Woo, and Zemčik algorithms are described.