连续切片三维重构绘图过程的消隐技术
2008-06-10
作者:李华清1,陈百明2,谢水生1,李
摘 要:消隐技术是计算机三维模拟的关键。为实现对材料三维立体图形的快速绘制,本文利用连续切片截面之间相互平行的特性,通过寻找相邻截面中的关键点,分别从两边向中间绘制侧面并填色,从整体上采用自下而上的方法,实现了立体图形的消隐。该方法避免了常规消隐方法中需要建立构成物体几何元素的方程并求解诸元素之间相交、前后遮挡关系等复杂的运算过程。
关键词:连续切片 三维重构" title="重构">重构消隐 计算机模拟
在连续切片的三维重构过程中,最后得到的图形是实体的外表面,应该具有良好的立体效果" title="立体效果">立体效果。但是在最终绘制图形之前,需要经过坐标转换[1,2]和图形消隐处理[3,4]才能绘制出符合透视关系、具有真实立体感的图形。否则,比较复杂的立体图形将呈现为一幅杂乱无章的画面。
1 消隐的定义
消隐是指在计算机绘制立体图形时,只显示透视关系中能够看得见的部分,不显示被遮挡的线段或平面,从而使绘制的图形符合透视关系并具有立体感的绘图方法。
为了达到消隐的目的,需要把表示三维物体的每个几何元素(包括点、线、面)与每个构成物体的轮廓面进行遮蔽判断,即是否全部或部分被遮蔽。把被遮盖线段或部分被遮盖线段与可见线段或部分可见线段区分开来,最后画出可见线段和线段的可见部分,隐藏不可见线段和线段的不可见部分,就得到了经过消隐处理的立体图形。
各种消隐算法都涉及到排序,最常用的就是某种形式的几何排序,即将物体及物体各表面按照相对于某一观察点(注:视觉成像遵循透视投影的原理,透视投影的特点是,所有的投影线都从空间某一点出发,该点被称为投影中心或观察点,也称为视点)的距离远近依次排序。通过这种排序,可以找出位置上靠近视点的物体表面,最后确定各表面之间在透视关系上的遮挡关系。一般情况下,距离观察点远的物体总是被距离观察点近的物体部分或完全遮挡。
排序不仅在空间深度方向(如Z方向)进行,而且要在画面(如X、Y方向)平面内进行。实现排序要花费大量的时间进行相交计算、深度检测和关系判断。为了提高排序效率,各算法中需要频繁地利用点、边、面的相关性信息。相关性是指物体之间或一个物体的各部分之间引起隐藏现象改变的相互关系。消隐时,通过考虑这些关系,可以大幅度减少消隐搜索的计算量。
2 消隐算法分类及特点
按照所处空间位置的不同,消隐算法可以归纳为以下三类:(1)在描述物体的坐标系空间中进行,称为物体空间算法或用户空间算法。(2)在图像空间中进行,称为图像空间算法或屏幕空间算法。(3)同时在物体空间和图像空间中实现,如画家算法。
画家消隐算法与画家创作油画的过程类似,严格依照透视关系,先画背景,再画中间景物,最后画近景。按照这种顺序构造画面,即可解决画面的消隐问题。
消隐处理是计算机绘图中一个比较复杂的问题。目前的消隐方法过程涉及建立各个平面、线段的几何方程,并对它们的相交性、深度顺序进行计算,从而确定图形中各个几何元素的可见部分,最后画出立体图形。这些消隐方法的计算量大,程序设计" title="程序设计">程序设计复杂,占用存储空间多,数据结构复杂,非专业人员难于理解、编制和维护[5~7]。
3 本文设计的消隐方法
在绘制由切片截面构成的立体图形时,由于切片截面是相互平行的,因此,立体图形的可见性问题转变为位于上下截面之间一系列相邻侧面位置关系的判断问题。在把切片截面转变为立体图形的过程中,利用切片截面之间相互平行的特性,结合画家消隐方法,可以避免计算和判断几何元素的相交性、深度顺序等复杂过程,从而得到一种高效、简洁的消隐方法。该消隐方法主要由确定关键点位置以及确定侧面的绘图顺序两部分组成。
3.1 确定关键点位置
由一系列相互平行的截面构成的实体,其侧面的可见性与具有最小和最大" title="最大">最大x坐标值的点密切相关,凡是位于这两点之间并且距观察点较近一侧的侧面均是可见的面。
依据上述原则,先找出上截面中具有最小和最大x坐标值点的序号,再找出具有最大y坐标值的点的序号,然后分别从两边向具有最大y坐标值的点画出每个侧面并填充颜色[8],这样就使得不可见的面被隐藏,而可见的面被显示出来,实体的立体效果得以体现。
为了画出实体所有的可见部分,仅找出上截面的最小和最大x坐标值的序号是不够的。只有当上、下截面具有最大和最小x坐标值的点分别相互匹配时,才能保证依据上截面中具有最大和最小x坐标值的点的序号画出的侧面是实际可见的。因此要根据上下截面点的匹配情况,对上截面中两个特殊点的序号进行相应调整。
为便于区分,将上截面中具有最大和最小坐标值点的序号分别表示为MAX1和MIN1,与其相匹配并且位于下截面中点的序号表示为max2和min2;将下截面中具有最大和最小坐标值的点的序号表示为MAX2和MIN2,与其相匹配并且位于上截面的点的序号表示为max1和min1;具有最大y坐标值并且位于上截面中的点的序号表示为MAXY。
在分别找到上、下截面中具有最大和最小x坐标值点的序号后,如果min1点的y坐标值小于MIN1的点的y坐标值,则应把min1的值赋给MIN1;同样,如果max1点的y坐标值大于MAX1点的y坐标值,则把max1的值赋给MAX1。在对MAX1、MIN1的值作了以上调整后,就可以开始分别从两边向MAX1点绘制侧面并填色。各点及其匹配点的位置示意图如图1所示,图中MAX1、MIN1的序号数值将分别被赋予max1、min1的值。
3.2 确定侧面的绘图次序
在确定了绘图所需的关键点之后,需要确定各侧面的绘制顺序,这对于正确绘制具有立体感的图形非常重要。只有按照侧面与观察者之间的距离,由远而近地绘制侧面才能使图形的立体感显现出来。由于编号的原因,在确定了所需的关键点之后,还需确定绘制侧面的顺序。
为了解释绘图顺序,这里引入一个“图形的开口”概念:即图形的第一个点与最后一个点之间的边。不同开口位置的绘图次序示意图如图2所示。如果图形的开口背离观察者(如图2(a)),则MIN1点和MAX1点之间的序号是连续的,其绘图的顺序相对简单,绘图程序将分别从MIN1向MAXY、MAX1向MAXY绘图。如果图形的开口正好位于观察者一边(如图2(b)),则MIN1点和MAX1点之间的序号不连续,绘图顺序较前一种情况稍微复杂,绘图程序将先从MIN1点向序号为第一的点绘图,再从MAX1向最后一个序号的点绘图,最后绘制出第一序号与最后序号点之间的侧面,并将每一个绘制好的侧面填色。通过这种绘图次序,从观察点出发看不见的面均被可见平面覆盖,从而实现了图形的消隐。此流程图只说明了绘制侧面的算法,就整体绘图算法来说,采用的方法是从下往上绘制,边绘图,边填色,这样就解决了整体消隐的问题。
寻找关键点是此消隐方法的关键所在。确定了关键点之后就可以确定图形可见部分与被遮盖部分的分界线。其次是确定绘图顺序,正确的绘图顺序保证了图形可见部分的正确显示。此消隐方法利用了相邻截面互相平行的特性,简化了消隐计算量,提高了消隐效率。消隐问题是绘制连续切片立体图形的最后环节,消隐效果直接关系到图形的视觉效果。
消隐算法流程如图3所示。顺序处理连续截面的信息,逐层绘制出消隐后的图形并填充颜色,即可得到符合透视效果并具有真实立体感的三维实体图形。
与其他消隐方法(如径向分类法、平面方程法等)相比[9],本文提出的消隐方法通过确定相邻切片平面之间的关键点,画出物体的可见部分,并遮盖透视关系中不可见的图形部分,实现对图形不可见部分的消隐。该算法避免了用于建立组成物体各几何元素的方程,以及对这些元素之间展开相交、前后遮挡关系等大量的运算工作,较好地解决了立体图形的消隐问题。
参考文献
1 刘国权.体视" title="体视">体视学在材料科学研究中的进展与展望[J].中国体视学与图像分析,1996;1(2):96~101
2 夏小玲.三维消隐算法研究[J].东北大学学报,2002;4(2):138~141
3 陈百明,李华清,李旭东.计算机模拟材料组织结构的程序设计[J].兰州理工大学学报,2005;31(1):17~20
4 Herbert M J,Jones C B,Tudhope D S et al.There-dimen-sional reconstruction of geoscientific objects from serial sec-tions[J].Visual Computer,1995;11(7):343~359
5 辜晓川,张晋.一种简便消隐方法的实现[J].微型机与应用,1996;15(11):11~12
6 Hamlin G,Gear G.Raster-scan Hidden Surface Algorithm Techniques[J].Computer Graphics,1977;11(2):206~213
7 Griffiths J G.Bibliography of Hidden-line and Hidden-sur-face Algorithms[J].Compute Aided Des,1978;10(3):203~206
8 芮小平,付长晶,余志伟.多边形填充消隐算法[J].工程设计CAD与智能建筑,2000;(6):61~62
9 Berg M D.Generalized hidden surface removal[J].Computa-tional Geometry,1996;5(5):249~276