A General Multi-step Algorithm for Voxel Traversing Along a Line |
| |
Authors: | Y K Liu H Y Song B alik |
| |
Affiliation: | Computer Science Department, Dalian University for National Minorities, Dalian Development Zone 116600, China;Faculty of Electrical Enginerring and Computer Science, University of Maribor, Smetanova 17, SI-2000 Maribor, Slovenia |
| |
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. |
| |
Keywords: | I 3 3 [Computer Graphics] Picture/Image Generation Line and curve generation I 3 3 [Computer Graphics]: Line and Curve Generation |
|
|