三维面心立方网格下的直线生成算法  

A Line Generation Algorithm on 3D Face-Centered Cubic Grid

作　　者：何丽君[1,2] 刘勇奎[2] 孙世昶[2] 

机构地区：[1]大连理工大学数学科学学院,大连116024 [2]大连民族学院计算机科学与工程学院,大连116600

出　　处：《计算机学报》2010年第12期2407-2416,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(60675008);辽宁省教育厅科学技术研究项目(L2010096);中央高校基本科研业务费专项资金(DC10010114);大连民族学院青年基金(2007A204)资助~~

摘　　要：以菱形十二面体为体素构成的三维面心立方(Face-Centered Cubic,FCC)网格是六角网格在三维的一种推广,直线生成算法在三维图形和图像应用中是一个非常重要和基础的算法.文中首先研究了二维六角网格下基于附属菱形空间的直线生成算法,然后将其推广至三维FCC网格,得到了一种FCC网格下的直线生成算法,该算法在三维方形网格下的Bresenham算法的基础上,利用附属平行六面体空间的平行六面体与FCC网格空间的体素之间的一一对应关系生成直线.该算法应用简单的判断公式,一步最多可生成3个体素,且只涉及到整数运算,因而没有累计误差.Three-dimensional grid where the voxels are rhombic dodecahedra is called FCC（face-centered cubic）grid which is one of the three-dimensional equivalents of the two-dimensional hexagonal grid.3D Line generation algorithm is an important and fundamental algorithm in applications for 3D graphics and images.An integer line generation algorithm on the FCC grid is presented in this paper.Firstly,a line generation algorithm is observed on the 2D hexagonal grid based on the adjunct rhomb space,and then is extended to the 3D FCC grid.The method is a modification of the 3D cubic Bresenham algorithm based on an adjunct parallelepiped space with the same center and basis vectors.The 3D FCC line is generated employing the one-to-one correspondence between the parallelogram cells of parallelepiped space and the voxels of the FCC space.The procedure is characterized by a simple discriminator with up to 3 voxels being processed in one step and is implemented in integer form without accumulated error.In this way,the accumulation of rounding errors is eliminated completely.

关 键 词：菱形十二面体 面心立方网格 算法 体素 直线生成 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]