基于附属平行六面体空间的面心立方网格直线生成方法

摘要

本发明提供一种基于附属平行六面体空间的面心立方网格直线生成方法，以提高图形系统中直线的生成效率。本方法在三维方形网格Bresenham方法的基础上，利用附属平行六面体空间的平行六面体与面心立方网格空间的体素之间的一一对应关系生成直线。本方法应用简单的判断公式只涉及到整数运算；除了在一步生成三个体素的时候需要2次整数乘法运算外，其余的只用到整数加法、减法、移位、比较运算，因而没有累计误差，本方法的时间复杂度为O(N)。面心立方网格生成的直线与方形网格生成的直线比较，在相同质量的条件下，体素数量更少，生成的直线更平滑。该方法为基于面心立方网格的真实感显示，体绘制，光线追踪，消除隐藏线面及三维重建等技术提供。