An Integer One-Pass Algorithm for Voxel Traversal

Abstract

Voxel traversing along a line in a uniformly divided voxel space is frequently needed in different applications of computer graphics. The paper presents a new integer one-pass algorithm for this problem. In 2D, the proposed approach is based on a modification of the well-known Bresenham algorithm. The algorithm is then extended in 3D where a special case may occur. It is characterized by a simple discriminator. A derivation for this discriminator given in the paper confirms that all calculations can be realized using only integer arithmetic. In this way, the accumulation of rounding errors is completely eliminated, and a robust and compact implementation can be easily achieved. One of the main advantages of the proposed algorithm is that it visits 1-3 voxels during each iteration thus assuring its efficiency. The algorithm has been compared with other algorithms for voxel traversing by measuring spent CPU time. For comparison, Cleary and Wyvill's, Amanatides and Woo's, and Code-based algorithm have been used. The proposed algorithm is faster than the referenced algorithms.