中文摘要：

以菱形十二面体为体素构成的三维面心立方（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.