Premium
An Efficient Code‐Based Voxel‐Traversing Algorithm
Author(s) -
Žalik Borut,
Clapworthy Gordon,
Oblonšek Črtomir
Publication year - 1997
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.00128
Subject(s) - voxel , traverse , computer science , algorithm , cube (algebra) , vertex (graph theory) , point (geometry) , code (set theory) , enhanced data rates for gsm evolution , position (finance) , theoretical computer science , artificial intelligence , mathematics , geometry , set (abstract data type) , graph , geodesy , finance , economics , programming language , geography
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.