A General Multi-step Algorithm for Voxel Traversing Along a Line
No Thumbnail Available
Date
2008
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association and Blackwell Publishing Ltd
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.
Description
@article{10.1111:j.1467-8659.2007.01097.x,
journal = {Computer Graphics Forum},
title = {{A General Multi-step Algorithm for Voxel Traversing Along a Line}},
author = {Liu, Y. K. and Song, H. Y. and Zalik, B.},
year = {2008},
publisher = {The Eurographics Association and Blackwell Publishing Ltd},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.2007.01097.x}
}