文档介绍：第３３卷 第１２期 计 算 机 学 报 Ｖｏｌ．３３Ｎｏ．１２
２０１０年１２月 ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｄｅｃ．２０１０
三维面心立方网格下的直线生成算法
何丽君１），２） 刘勇奎２） 孙世昶２）
１）（大连理工大学数学科学学院 大连 １１６０２４）
２）（大连民族学院计算机科学与工程学院 大连 １１６６００）
摘 要 以菱形十二面体为体素构成的三维面心立方（ＦａｃｅＣｅｎｔｅｒｅｄＣｕｂｉｃ，ＦＣＣ）网格是六角网格在三维的一种
推广，直线生成算法在三维图形和图像应用中是一个非常重要和基础的算法．文中首先研究了二维六角网格下基
于附属菱形空间的直线生成算法，然后将其推广至三维ＦＣＣ网格，得到了一种ＦＣＣ网格下的直线生成算法，该算
法在三维方形网格下的Ｂｒｅｓｅｎｈａｍ算法的基础上，利用附属平行六面体空间的平行六面体与ＦＣＣ网格空间的体素
之间的一一对应关系生成直线．该算法应用简单的判断公式，一步最多可生成３个体素，且只涉及到整数运算，因
而没有累计误差．
关键词 菱形十二面体；面心立方网格；算法；体素；直线生成
中图法分类号ＴＰ３９１ 犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１０．０２４０７
犃犔犻狀犲犌犲狀犲狉犪狋犻狅狀犃犾犵狅狉犻狋犺犿狅狀３犇犉犪犮犲犆犲狀狋犲狉犲犱犆狌犫犻犮犌狉犻犱
ＨＥＬｉＪｕｎ１），２） ＬＩＵＹｏｎｇＫｕｉ２） ＳＵＮＳｈｉＣｈａｎｇ２）
１）（犛犮犺狅狅犾狅犳犕犪狋犺犲犿犪狋犻犮狊犛犮犻犲狀犮犲狊，犇犪犾犻犪狀犝狀犻狏犲狉狊犻狋狔狅犳犜犲犮犺狀狅犾狅犵狔，犇犪犾犻犪狀 １１６０２４）
２）（犆狅犾犾犲犵犲狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犈狀犵犻狀犲犲狉犻狀犵，犇犪犾犻犪狀犖犪狋犻狅狀犪犾犻狋犻犲狊犝狀犻狏犲狉狊犻狋狔，犇犪犾犻犪狀 １１６６００）
犃犫狊狋狉犪犮狋 ＴｈｒｅｅｄｉｍｅｎｓｉｏｎａｌｇｒｉｄｗｈｅｒｅｔｈｅｖｏｘｅｌｓａｒｅｒｈｏｍｂｉｃｄｏｄｅｃａｈｅｄｒａｉｓｃａｌｌｅｄＦＣＣ
（ｆａｃｅｃｅｎｔｅｒｅｄｃｕｂｉｃ）ｇｒｉｄｗｈｉｃｈｉｓｏｎｅｏｆｔｈｅｔｈｒｅｅｄｉｍｅｎｓｉｏｎａｌｅｑｕｉｖａｌｅｎｔｓｏｆｔｈｅｔｗｏｄｉｍｅｎ
ｓｉｏｎａｌｈｅｘａｇｏｎａｌｇｒｉｄ．３ＤＬｉｎｅｇｅｎｅｒａｔｉｏｎａｌｇｏｒｉｔｈｍｉｓａｎｉｍｐｏｒｔａｎｔａｎｄｆｕｎｄａｍｅｎｔａｌａｌｇｏｒｉｔｈｍｉｎ
ａｐｐｌｉｃａｔｉｏｎｓｆｏｒ３Ｄｇｒａｐｈｉｃｓａｎｄｉｍａｇｅｓ．ＡｎｉｎｔｅｇｅｒｌｉｎｅｇｅｎｅｒａｔｉｏｎａｌｇｏｒｉｔｈｍｏｎｔｈｅＦＣＣｇｒｉｄｉｓ
ｐｒｅｓｅｎｔｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｆｉｒｓｔｌｙ，ａｌｉｎｅｇｅｎｅｒａｔｉｏｎａｌｇｏｒｉｔｈｍｉｓｏｂｓｅｒｖｅｄｏｎｔｈｅ２Ｄｈｅｘａｇｏｎａｌｇｒｉｄ
ｂａｓｅｄｏｎｔｈｅａｄｊ