A General Multi-step Algorithm for Voxel Traversing Along a Line

Abstract

Traversing voxels along a three dimensional (3D) line is one of the most fundamental algorithms for voxel-based applications. This paper presents a new 6-connectivity integer algorithm for this task. The proposed algorithm accepts voxels having different sizes in x, y and z directions. To explain the idea of the proposed approach, a 2D algorithm is firstly considered and then extended in 3D. This algorithm is a multi-step as up to three voxels may be added in one iteration. It accepts both integer and floating-point input.The new algorithm was compared to other popular voxel traversing algorithms. Counting the number of arithmetic operations showed that the proposed algorithm requires the least amount of operations per traversed voxel. A comparison of spent CPU time using either integer or floating-point arithmetic confirms that the proposed algorithm is the most efficient. This algorithm is simple, and in compact form which also makes it attractive for hardware implementation.