A Line Generation Algorithm on 3D Face-Centered Cubic Grid
He Li · Chinese Journal of Computers · 2010
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.