基于矿床真三维显示的图形消隐处理算法.pdf_大学文库

D0I:10.13374/i.issnl00113.2007.08.022 第29卷第8期北京科技大学学报 Vol.29 No.8 2007年8月 Journal of University of Science and Technology Beijing Aug.2007 基于矿床真三维显示的图形消隐处理算法苏海云李仲学北京科技大学金属矿山高效开采与安全教育部重点实验室，北京100083 摘要为了更好地解决地矿广实体在平面图形设备上显示时凹面矿体及多矿床实体之间的消隐问题，提出了画家消隐处理的算法·通过采取汇集前平面多边形、分解多边形图形面成三角形的图形面、排序处理三角形面、建立三角形图形面深度次序四步骤，对地矿工程三维实体消隐处理，使得原实体中那些被不透明的体素或其他实体挡住的线素或体素不再被输出，当地矿实体在平面图形设备上显示或打印时将使地矿工程三维实体更具真实感关键词地矿工程：图形消隐：画家算法；三维可视化分类号TD178 近年来，三维可视化技术以其优越的仿真效果再把各个多边形分解成三角形面，使得问题简单化；引起业内人士广泛的关注，地矿实体的真三维显示最后，将比较所有的三角形面的位置前后关系，按照是地矿工程可视化技术中最后一道工序山.由于三其前后关系顺序地将它们存放到显示文件中，该文维实体中的矿体元素有前后之分，当地矿实体要在件中图形的顺序就是体素体输出的顺序，平面图形设备上显示时，必然要判断其前后关系，不 1.1汇集要输出图形的全部前平面多边形输出后的图形.这种去掉实体中该隐藏的矿体元素如果实现消隐处理，三维实体对象在输出时要的处理称为图形消隐处理] 加上背面移去和画家算法处理，使三维图形处理流目前，使用比较普遍的消隐处理方法为背面移程发生变化，增加消隐处理后，三维实体处理流程去法，背面移去法是一种消去三维实体中的隐面的按图1顺序进行方法)，背面移去法可以很好得解决每个都是凸面背面家窗口/视口显示实体对象的消隐问题，但它对于凹面实体及多实体移去处理变换文件之间的消隐问题仍无能为力，三维实体经过背面移图1三维实体处理流程示意图去处理后保留了应该显示的可见体素面（即实体前 Fig-1 3D solid disposal flow chart 面)，但实际上并不是所有的前面体素都应该完全被显示出来，对于多个矿体面，由于它们仍存在不同图2为画家算法处理框图，图中，收集多边形前后位置，前面的体素面会完全挡住或部分挡住后操作是集中要输出的所有实体对象的全部多边形图面的体素面，所以还需要继续消隐处理，针对该问题形面，这些多边形图形面是由经过背面移去后的前提出画家算法，平面经过投影变换后得出的，它们使用图形体数据和填充属性表示 1画家消隐处理算法的分析画家算法将地矿实体面位置的前后关系转换为输出时间的先后关系，把后输出的实体面作为上层图2画家算法处理框图图形体覆盖先输出的图形体（下层图形体），以实现 Fig.2 Painter algorithm disposal flow chart 地矿实体消隐，地矿体素体消隐的画家算法的基 1.2将多边形图形面分解成三角形的图形面本思路是：首先将要输出的三维体素体对象用多个尽管多边形的边及角关系很复杂，但它们都可多边形的图形面表示（包括几何参数和填充属性）；以分解为一个个三角形，利用三角形可以使消隐算收稿日期：2006-02-23修回日期：2006-10-07 法简单统一，多边形分解为三角形分凸多边形和凹基金项目：教育部高等学校博士学科点专项科研基金项目(N。.2002 多边形两种情况，如图3所示， -0008006) (1)凸多边形分解三角形的方法，凸多边形分作者简介：苏海云(1976一)，男，博士研究生；李仲学(1957一)，男，教授，博士生导师解三角形时取多边形的第一个点为公共顶点，依次

基于矿床真三维显示的图形消隐处理算法苏海云李仲学北京科技大学金属矿山高效开采与安全教育部重点实验室北京100083 摘要为了更好地解决地矿实体在平面图形设备上显示时凹面矿体及多矿床实体之间的消隐问题提出了画家消隐处理的算法．通过采取汇集前平面多边形、分解多边形图形面成三角形的图形面、排序处理三角形面、建立三角形图形面深度次序四步骤对地矿工程三维实体消隐处理使得原实体中那些被不透明的体素或其他实体挡住的线素或体素不再被输出当地矿实体在平面图形设备上显示或打印时将使地矿工程三维实体更具真实感．关键词地矿工程；图形消隐；画家算法；三维可视化分类号 TD178 收稿日期：2006-02-23 修回日期：2006-10-07 基金项目：教育部高等学校博士学科点专项科研基金项目（No．2002 －0008006）作者简介：苏海云（1976－）男博士研究生；李仲学（1957－）男教授博士生导师近年来三维可视化技术以其优越的仿真效果引起业内人士广泛的关注．地矿实体的真三维显示是地矿工程可视化技术中最后一道工序［1］．由于三维实体中的矿体元素有前后之分当地矿实体要在平面图形设备上显示时必然要判断其前后关系不输出后的图形．这种去掉实体中该隐藏的矿体元素的处理称为图形消隐处理［2］．目前使用比较普遍的消隐处理方法为背面移去法．背面移去法是一种消去三维实体中的隐面的方法［3］．背面移去法可以很好得解决每个都是凸面实体对象的消隐问题但它对于凹面实体及多实体之间的消隐问题仍无能为力．三维实体经过背面移去处理后保留了应该显示的可见体素面（即实体前面）但实际上并不是所有的前面体素都应该完全被显示出来．对于多个矿体面由于它们仍存在不同前后位置前面的体素面会完全挡住或部分挡住后面的体素面所以还需要继续消隐处理针对该问题提出画家算法． 1 画家消隐处理算法的分析画家算法将地矿实体面位置的前后关系转换为输出时间的先后关系把后输出的实体面作为上层图形体覆盖先输出的图形体（下层图形体）以实现地矿实体消隐［4］．地矿体素体消隐的画家算法的基本思路是：首先将要输出的三维体素体对象用多个多边形的图形面表示（包括几何参数和填充属性）；再把各个多边形分解成三角形面使得问题简单化；最后将比较所有的三角形面的位置前后关系按照其前后关系顺序地将它们存放到显示文件中该文件中图形的顺序就是体素体输出的顺序． 1∙1 汇集要输出图形的全部前平面多边形如果实现消隐处理三维实体对象在输出时要加上背面移去和画家算法处理使三维图形处理流程发生变化．增加消隐处理后三维实体处理流程按图1顺序进行．图1 三维实体处理流程示意图 Fig．1 3D solid disposal flow chart 图2为画家算法处理框图．图中收集多边形操作是集中要输出的所有实体对象的全部多边形图形面这些多边形图形面是由经过背面移去后的前平面经过投影变换后得出的它们使用图形体数据和填充属性表示．图2 画家算法处理框图 Fig．2 Painter algorithm disposal flow chart 1∙2 将多边形图形面分解成三角形的图形面尽管多边形的边及角关系很复杂但它们都可以分解为一个个三角形利用三角形可以使消隐算法简单统一．多边形分解为三角形分凸多边形和凹多边形两种情况如图3所示．（1）凸多边形分解三角形的方法．凸多边形分解三角形时取多边形的第一个点为公共顶点依次第29卷第8期 2007年 8月北京科技大学学报 Journal of University of Science and Technology Beijing Vol．29No．8 Aug．2007 DOI:10．13374／j．issn1001－053x．2007．08．022

.764 北京科技大学学报第29卷 1.3对三角形面进行的排序处理对三角形进行的排序处理即确定三角形的前后位置顺序，并按其顺序对三角形排序.设两个三角形面为A、B,它们之间的前后位置关系只可能有三 (a)凸多边形 (b)凹多边形种：A遮挡了全部或部分B;互不重叠；B遮挡了全图3多边形分解为三角形部或部分A,通过极大极小可检测出两三角形的 Fig-3 Separating polygon into triangles 关系，取三个顶点组成三角形，分解时应注意，如果三角极大极小检查法步骤为：先按三角形的三个顶形的顶点几乎在一条直线上，应取消该三角形，因为点的最小X坐标和Y坐标构成框的左下点，最大它的面积太小，挡不住后面的物体 X坐标和Y坐标构成的右上点，在两个三角形外部由于分解三角形的过程中会增加一些辅助边，形成两个围绕它们的最小矩形框，如图4所示，再这些辅助边应为不可见边，而原多边形为可见边，使检查两个三角形矩形框，如果两个框不重叠，则三角在记录这些三角形时要注意边的可见性] 形必然不重叠，就可以比较它们中心Z坐标的大 (2)凹边形分解三角形的方法.凹边形在分解小，确定三角形的先后关系：检查结果如果两个框重为三角形时，应该取最左（或最上）点与内部的最左叠，说明这两个三角形可能重叠，还需要作进一步检 (或最上)点连线，分割凹边形为两个多边形.分割查才能确定其真实关系].进一步检查需要以下后的多边形要继续分解，直到全部为三角形为止· 两步，图4三角形最小矩形 Fig.4 The smallest triangular rectangle (1)求两个三角形的相交边，对两三角形的两的大小决定，Z值大的在前面两边都要检查是否有相交边，如果结果为无交点，综上所述，三角形图形面的前后顺序测试流程则说明两三角形完全包含或完全不包含，求相交边如图5所示. 的具体过程如下 (a)用极大极小法检查两三角形边是否相交，图像轴入以被检查的两个边为对角形成两个边的最小矩形，看它们是否重叠，如果不重叠则排除这两边相交的极大极小测试不重可能性；否则要进行下一步检查，重变 ()求出两边所在直线的交点，如果两直线无交点在边的外部，则也可以排除两边相交的可能性：、投影边相交否无否则两边有交点且交点在边内，要进行下一步检查，三角形包含香否 <交点处Z相同 (c)通过交点处的Z值大小比较两三角形的深度] 是是 (2)确定两三角形之间是全部包含或不包含， Z值比较 Z值比较如果上面检查确定两个三角形之间无相交点，则可为以下两种情况：如果两个三角形框是全部包含的，用像输出则这两个三角形属于全部包含情况；反之，属于完全不重叠情况，对于完全包含的两三角形，它们的深图5两个三角形批较流程图度关系由在共同区域（小三角形中）的一点处Z值 Fig.5 Flow chart for comparing two triangles

图3 多边形分解为三角形 Fig．3 Separating polygon into triangles 取三个顶点组成三角形．分解时应注意如果三角形的顶点几乎在一条直线上应取消该三角形因为它的面积太小挡不住后面的物体．由于分解三角形的过程中会增加一些辅助边这些辅助边应为不可见边而原多边形为可见边使在记录这些三角形时要注意边的可见性［5］．（2）凹边形分解三角形的方法．凹边形在分解为三角形时应该取最左（或最上）点与内部的最左（或最上）点连线分割凹边形为两个多边形．分割后的多边形要继续分解直到全部为三角形为止． 1∙3 对三角形面进行的排序处理对三角形进行的排序处理即确定三角形的前后位置顺序并按其顺序对三角形排序．设两个三角形面为 A、B它们之间的前后位置关系只可能有三种：A 遮挡了全部或部分 B；互不重叠；B 遮挡了全部或部分 A．通过极大极小可检测出两三角形的关系．极大极小检查法步骤为：先按三角形的三个顶点的最小 X 坐标和 Y 坐标构成框的左下点最大 X 坐标和 Y 坐标构成的右上点在两个三角形外部形成两个围绕它们的最小矩形框如图4所示．再检查两个三角形矩形框如果两个框不重叠则三角形必然不重叠就可以比较它们中心 Z 坐标的大小确定三角形的先后关系；检查结果如果两个框重叠说明这两个三角形可能重叠还需要作进一步检查才能确定其真实关系［6］．进一步检查需要以下两步．图4 三角形最小矩形 Fig．4 The smallest triangular rectangle （1）求两个三角形的相交边．对两三角形的两两边都要检查是否有相交边．如果结果为无交点则说明两三角形完全包含或完全不包含．求相交边的具体过程如下．（a）用极大极小法检查两三角形边是否相交．以被检查的两个边为对角形成两个边的最小矩形看它们是否重叠．如果不重叠则排除这两边相交的可能性；否则要进行下一步检查．（b）求出两边所在直线的交点．如果两直线无交点在边的外部则也可以排除两边相交的可能性；否则两边有交点且交点在边内要进行下一步检查．（c）通过交点处的 Z 值大小比较两三角形的深度［7］．（2）确定两三角形之间是全部包含或不包含．如果上面检查确定两个三角形之间无相交点则可为以下两种情况：如果两个三角形框是全部包含的则这两个三角形属于全部包含情况；反之属于完全不重叠情况．对于完全包含的两三角形它们的深度关系由在共同区域（小三角形中）的一点处 Z值的大小决定Z 值大的在前面．综上所述三角形图形面的前后顺序测试流程如图5所示．图5 两个三角形比较流程图 Fig．5 Flow chart for comparing two triangles ·764· 北京科技大学学报第29卷

第8期苏海云等：基于矿床真三维显示的图形消隐处理算法 .765 1.4对三角形图形面建立深度次序计中采用的消隐处理的画家算法的一个消隐过程，对三角形编码，比较全部三角形，建立深度顺序图(a)是水平采准切割图，图(b)是采准与矿体结合链表[8].如果输出的图形较多，要将排序后的三角图，图(c)是矿体、采准和网格交互图，其三者位置形按从后到前的顺序送入显示文件暂存，图形显示的前后关系可以用输出的先后次序表示，图（©）中矿时按文件中三角形顺序输出，体部分遮盖了最先输出的采准面，而后输出的网格 2消隐处理画家算法的实例应用线又将矿体和采准面的部分体素消去，因而使得打印出的井巷工程图像更加逼真[9. 图6所示为在地矿工程三维可视化仿真系统设 (a)采准图示 b)矿体、采准图 (©)矿体、采准、网格图图6消隐处理的画家算法 Fig.6 Disappearing disposal of the painter algorithm 1998,215 3结论 [3]Foiey JD.交互式计算机图形学基础.北京：清华大学出版社， 2000.66 消隐处理的画家算法可以将地矿实体面位置的 [4]袁绪龙.基于OpenGL的弹道视景仿真系统设计.电脑与信息前后关系转换为输出时间的先后关系，把后输出的技术，2001(4)：7 实体面作为上层图形体覆盖先输出的图形体，以实 [5]李翠平，李仲学.矿床体视化的一种空间规则体数据生成方现地矿实体消隐，在地矿工程三维可视化设计过程法.北京科技大学学报，2002,24(6)：589 中，经过对三维实体的消隐处理，原实体中那些被不 [6]陈光富，井巷工程透视投影图的计算机绘制，金属矿山，1996， 242(8):88 透明的体素体或其他实体挡住的线素或体素不再被 [7]Ivanov NS,Juan P GG.Jrgen A J.Real time 3D visualization of 输出，其结果符合三维实体前后关系的视觉特征， ultrasonic data using a standard PC.Ultrasonics.2003,41(6): 当地矿实体要在平面图形设备上显示或打印时，运用消隐处理的画家算法将使地矿工程三维实体更具 [8]Anshuman R.Kamal P.Farin G E.Volume visualization of mul- 有真实感，为工程技术人员能够更直观地分析和优 ticolor laser confocal microscope data-Comput Graphics.2001.25 化地下采矿工程布置提供手段 (3):371 [9]汪家琪.井巷三维立体图自动绘制系统山西煤炭，1997,17 参考文献 (4):12 [IO]李春民，李仲学.OpenGL在矿山井巷工程三维可视化仿真系 [1]罗振东。计算机图形学原理和方法·上海：复旦大学出版社，统中的应用.北京科技大学学报，2004,26(5)：457 1998,122 (下转第792页) [2]Hearn D,Baker M P.计算机图形学.北京：电子工业出版社

1∙4 对三角形图形面建立深度次序对三角形编码比较全部三角形建立深度顺序链表［8］．如果输出的图形较多要将排序后的三角形按从后到前的顺序送入显示文件暂存．图形显示时按文件中三角形顺序输出． 2 消隐处理画家算法的实例应用图6所示为在地矿工程三维可视化仿真系统设计中采用的消隐处理的画家算法的一个消隐过程图（a）是水平采准切割图图（b）是采准与矿体结合图图（c）是矿体、采准和网格交互图．其三者位置的前后关系可以用输出的先后次序表示图（c）中矿体部分遮盖了最先输出的采准面而后输出的网格线又将矿体和采准面的部分体素消去因而使得打印出的井巷工程图像更加逼真［9］．图6 消隐处理的画家算法 Fig．6 Disappearing disposal of the painter algorithm 3 结论消隐处理的画家算法可以将地矿实体面位置的前后关系转换为输出时间的先后关系把后输出的实体面作为上层图形体覆盖先输出的图形体以实现地矿实体消隐．在地矿工程三维可视化设计过程中经过对三维实体的消隐处理原实体中那些被不透明的体素体或其他实体挡住的线素或体素不再被输出其结果符合三维实体前后关系的视觉特征．当地矿实体要在平面图形设备上显示或打印时运用消隐处理的画家算法将使地矿工程三维实体更具有真实感为工程技术人员能够更直观地分析和优化地下采矿工程布置提供手段．参考文献［1］罗振东．计算机图形学原理和方法．上海：复旦大学出版社 1998：122 ［2］ Hearn DBaker M P．计算机图形学．北京：电子工业出版社 1998：215 ［3］ Foiey J D．交互式计算机图形学基础．北京：清华大学出版社 2000：66 ［4］袁绪龙．基于 OpenGL 的弹道视景仿真系统设计．电脑与信息技术2001（4）：7 ［5］李翠平李仲学．矿床体视化的一种空间规则体数据生成方法．北京科技大学学报200224（6）：589 ［6］陈光富．井巷工程透视投影图的计算机绘制．金属矿山1996 242（8）：88 ［7］ Ivanov N SJuan P G GJrgen A J．Real time3D visualization of ultrasonic data using a standard PC．Ultrasonics200341（6）： 42 ［8］ Anshuman RKamal PFarin G E．Volume visualization of multicolor laser confocal microscope data．Comput Graphics200125 （3）：371 ［9］汪家琪．井巷三维立体图自动绘制系统．山西煤炭199717 （4）：12 ［10］李春民李仲学．OpenGL 在矿山井巷工程三维可视化仿真系统中的应用．北京科技大学学报200426（5）：457 （下转第792页）第8期苏海云等：基于矿床真三维显示的图形消隐处理算法 ·765·