A Line Generation Algorithm over 3D Body- centered Cubic Lattice

Abstract—New line generation algorithm is proposed for generating lines over 3D body-centered cubic lattice, a kind of optimal lattice in 3D space. The main contribution in this paper is employing the 3D Bresenham algorithm, a popular algorithm for generating 3D lines on a cubic lattice, to produce the BCC lattice occupied by 3D lines, with the help of the adjunct parallelepiped space, having the same center and basis vectors with the BCC lattice. The adjunct parallelepiped line is easy to generate by employing the existed 3D cubic Bresenhan algorithm. Due to the one-to-one correspondence between the parallelogram cells of parallelepiped space and the voxels of the BCC space, the 3D BCC line generation algorithm is gained. The whole procedure is characterized by a simple discriminator and a derivation for this discriminator given in the paper confirms that all calculations can be realized using only integer arithmetic which is to implement on computer. Index Terms—body-centered cubic, lattice, voxel, line generation I