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·
.792. 北京科技大学学报 第29卷 Refining process analysis of clean pipe steel LIU Jianhua,BAO Yanping,LI Taiquan,HAN Lina,DONG Xian,YANG Lingli Metallurgical and Ecological Engineering School.University of Science and Technology Beijing.Beijing 100083.China ABSTRACT Serious sampling and integrated analysis were carried out in the production of pipe steel with LF- VD.RH LF and LF-RH refining processes.It is shown that high grade pipe steel can be produced with the three refining processes,but the purity and cleanness of the steel produced with LF-RH process are higher:the functions of different refining instruments are distinct,but they are affected effected by up and dow n working procedures because of the conjunction and restriction of the quantity and composition of refining slag and other factors. KEY WORDS pipe steel;refining:purity;cleanliness (上接第765页) An algorithm of disappearing figure based on 3D visualization of ore deposit SU Haiyun,LI Zhongxue Key Laboratory of Chinese Ministry of Education for High-Efficient Mining and Safety of Metal Mines,University of Science and Technology Beijing Beijing 100083,China ABSTRACI A painter algorithm was proposed to better solve the disappearing problem of ore body when ore body was displayed in a graphics equipment.After taking four steps of merging plane polygon,decomposing polygon graphics into triangle graphics,sorting triangular surface treatment and building up triangle graphics for depth,ore body was disposed by the painter algorithm,and hidden line or body warded off by opaque body or other entities in original entities would be not output.When ore body was showed and printed by the graphics e- quipment,underground mining engineering body would be more realistic. KEY WORDS underground mining engineering:disappearing figure:painter algorithm;3D visualization
Refining process analysis of clean pipe steel LIU JianhuaBAO Y anpingLI T aiquanHA N L inaDONG XianY A NG L ingli Metallurgical and Ecological Engineering SchoolUniversity of Science and Technology BeijingBeijing100083China ABSTRACT Serious sampling and integrated analysis were carried out in the production of pipe steel with LF－ VDRH－LF and LF－RH refining processes．It is shown that high grade pipe steel can be produced with the three refining processesbut the purity and cleanness of the steel produced with LF－RH process are higher；the functions of different refining instruments are distinctbut they are affected effected by up and down working procedures because of the conjunction and restriction of the quantity and composition of refining slag and other factors． KEY WORDS pipe steel；refining；purity；cleanliness （上接第765页） An algorithm of disappearing figure based on3D visualization of ore deposit SU HaiyunLI Zhongxue Key Laboratory of Chinese Ministry of Education for High-Efficient Mining and Safety of Metal MinesUniversity of Science and Technology Beijing Beijing100083China ABSTRACT A painter algorithm was proposed to better solve the disappearing problem of ore body when ore body was displayed in a graphics equipment．After taking four steps of merging plane polygondecomposing polygon graphics into triangle graphicssorting triangular surface treatment and building up triangle graphics for depthore body was disposed by the painter algorithmand hidden line or body warded off by opaque body or other entities in original entities would be not output．When ore body was showed and printed by the graphics equipmentunderground mining engineering body would be more realistic． KEY WORDS underground mining engineering；disappearing figure；painter algorithm；3D visualization ·792· 北 京 科 技 大 学 学 报 第29卷
