摘要
提出一种只用整数运算的沿三维直线的体素遍历算法,适用的体素空间可以分割成非单位的和非正方体的·首先研究了二维平面中的体素直线遍历算法,然后提出一种以二维平面中的遍历算法为基础的沿三维直线的体素遍历算法·该算法是一个多步整数遍历算法,每一步可以遍历最多3个体素,且所用的判断公式非常精炼,不仅计算量很小而且没有累计误差·与现有的体素遍历算法进行比较的结果表明,该算法不仅没有累计误差,而且执行速度也是最快的·
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.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2006年第6期812-818,共7页
Journal of Computer-Aided Design & Computer Graphics
基金
国家自然科学基金(60473108)
关键词
体素
三维直线生成
遍历
算法
voxel
3D line generation
traversal
algorithm
