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

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

作　　者：刘勇奎[1] 云健[1] 王晓强[1] 宋海玉[1] 

机构地区：[1]大连民族学院计算机图形图像研究所,大连116600

出　　处：《计算机辅助设计与图形学学报》2006年第6期812-818,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(60473108)

摘　　要：提出一种只用整数运算的沿三维直线的体素遍历算法,适用的体素空间可以分割成非单位的和非正方体的·首先研究了二维平面中的体素直线遍历算法,然后提出一种以二维平面中的遍历算法为基础的沿三维直线的体素遍历算法·该算法是一个多步整数遍历算法,每一步可以遍历最多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.

关 键 词：体素 三维直线生成 遍历 算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP312[自动化与计算机技术—计算机科学与技术]