沿三维直线的非单位体素遍历的多步整数算法

提出一种只用整数运算的沿三维直线的体素遍历算法,适用的体素空间可以分割成非单位的和非正方体的.首先研究了二维平面中的体素直线遍历算法,然后提出一种以二维平面中的遍历算法为基础的沿三维直线的体素遍历算法.该算法是一个多步整数遍历算法,每一步可以遍历最多3个体素,且所用的判断公式非常精炼,不仅计算量很小而且没有累计误差.与现有的体素遍历算法进行比较的结果表明,该算法不仅没有累计误差,而且执行速度也是最快的.

A Multi-step Integer Algorithm for Non-unit Voxel Traversing along a 3D Line

An algorithm for traversing voxels along a 3D line using only integer arithmetic is presented. Two kinds of subdivision, namely non-unit space subdivision and non-square space subdivision, could be used. A 2D algorithm is first developed to find out the pixels a line passes through. Then based on it, an algorithm for traversing voxels along a 3D line in uniformly divided voxel space is proposed. Up to 3 voxels may be processed in one step and no accumulated error is made. The discriminator used in this algorithm is well refined, so that few calculations are required and the algorithm is simple and compact in form. Comparison with existing voxel traversal algorithms shows that the new algorithm is not only free from accumulated error but also is the fastest.