2. 中国科学院大学 计算机与控制学院, 北京 101408;
3. 北京中科辅龙计算机技术股份有限公司, 北京 100085
2. School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 101408, China;
3. Beijing Zhongke Fulong Computer Technology Company Limited, Beijing 100085, China
制造业是我国国民经济的支柱产业,制造业发达与否也是衡量一国生产力水平高低的重要标准。而流程工业是制造业的一个重要分支,涵盖了石油、化工、冶金等基础性领域。随着人类社会的不断发展、经济水平的不断提高,人们对流程工业产能的需求也不断增大。为了应对这种需求,人们不得不设计、建造更多、更大规模的流程工厂。正是在这种情况下,流程工厂设计平台的模型处理能力及性能上限越来越受到设计人员和研究人员的关注。工厂模型数据规模增长而导致的图形平台交互帧率低下正是当前设计平台最为突出的问题之一,而通过适当的裁剪算法以剔除不必要的渲染对象,加快渲染流程,从而提高交互帧率,是解决这一问题的重要方法。
图形引擎绘制一帧的过程一般包括更新、裁剪以及绘制三个步骤,每个步骤的时长均对平台最终的交互帧率有重要影响。在大规模复杂场景中,可见对象的数量通常远远小于场景数据集[1]。因此,在裁剪阶段应用相关加速算法,对场景数据快速筛选,剔除不可见或投影至屏幕所占据的像素点数量小于一定阈值以致人眼无法捕获的对象,可以减少大量不必要的绘制,大幅提升交互帧率。
可见集筛选产生的结果可归为以下三类:1) 精确可见集[2],即精确包含所有可见对象的集合;2) 近似可见集,即所得的可见集是精确可见集的真子集;3) 保守可见集[3],即所得的可见集可能包含部分不可见的对象。而上述三类可见集,统称为潜在可视集(Potential Visibility Set, PVS)[4]。目前,存在大量获取上述三类可见集的裁剪剔除算法,其中较为著名的有隐藏面剔除[5-7]、视域剔除[8]、背向面剔除、遮挡剔除[9]、层次遮挡图[10-11]以及直接离散遮挡物[12]等方法。在这些算法中,也有学者继续优化,以提升算法效率,比如视域剔除算法,文献[13]提出一种基于轴对齐包围盒和有向包围盒的视锥体加速裁剪方法。
然而,在实际的流程工厂模型的设计过程中,当模型顶点、面片规模达到数以亿计时,上述算法均无法很好地解决伴随模型规模增长而导致交互帧率过低的问题。
由于流程工厂模型是由大量各类构件按相应的工艺及设计要求,有序连接而成。而在建模软件中,各类构件均是由若干种体素组合而成。本文正是利用体素的几何特征及模型整体的三维空间特征,提出一种基于八叉树的大规模流程工厂模型细节裁剪算法。在本文提出的算法中,首先依据每一个构件体素的几何特征以及设定的度量方法,快速度量构件的近似大小。并根据度量的构件大小,将构件集合划分成大构件集合与小构件集合。其中大构件集合对应流程工厂模型的轮廓,小构件集合则对应流程工厂模型的细节。然后根据每个工厂模型的三维空间分布特征,采用两棵八叉树分别对大小构件集合进行层次组织,并将对应构件按包围盒中心添加至对应的叶子节点。最后在渲染一帧的过程中,在裁剪阶段依据大、小构件集合所对应的八叉树的叶节点进行视锥体裁剪,并对小构件集合对应的八叉树快速估算其叶子节点下所有构件投影至屏幕上所占的像素点数量上限,剔除小于设定阈值的构件,从而快速获取可显示工厂模型轮廓的保守可见集。实验结果表明,与处理对象粒度为面片级的传统细节裁剪算法相比,该方法在处理粒度为叶节点的级别上,能够保证较高的交互帧率并较为完整地显示工厂模型轮廓,达到交互过程流畅、显示效果良好的目的。
1 基本理论一个完整的流程工厂,由大量构件按照一定的工艺要求及工程约束有序连接而成。这里的构件泛指构成流程工厂的所有对象,包括:各类管道器材,如管件、法兰、阀门、螺栓、螺母等;各类工艺设备:如泵、风机、鼓风机、压缩机、真空设备、压力容器、蒸汽透平、塔、储罐、换热器、加热炉等。
而构件在建模的过程中,一般由网格体素、面片体素、多边形体素以及18种基本体素(如图 1)组合构成。基本体素在流程工厂模型建模过程中均有相应的参数化表示,如:球,其参数化信息有半径以及圆心坐标;而圆柱,其参数化信息有上顶面圆心坐标、下底面圆心坐标以及半径等。
体素的参数化信息对于构件而言有重要意义,它决定构件在一定的距离下投影至计算机屏幕显示时所占据的像素点数量。图 2对这一过程进行了推导。
以图 2简单表示视锥体。其中AB为近平面(其通常作为投影平面),CD为远平面。为了方便说明,以圆O表示位于视口中的构件,其半径为|PO|,且AB的中垂线过圆心O(即EN⊥AB)。那么,圆O投影至AB上的长度为2|MN|,其中:
$ \left| {MN} \right| = \left| {PO} \right| * \frac{{\left| {EN} \right|}}{{\left| {EO} \right|}} $ | (1) |
对此,圆O投影至AB上的长度占比k为:
$ k = \frac{{2\left| {MN} \right|}}{{\left| {AB} \right|}} = \frac{{2*\left| {PO} \right| * \left| {EN} \right|}}{{\left| {EO} \right| * \left| {AB} \right|}} $ | (2) |
其中,|AB|=2*|EN|*tan θ,θ为∠AEO(2∠AEO即为视场角,在程序运行时设置为常量,本文测试环境所采用的视场角为30°),代入化简,得:
$ k = \frac{{\left| {PO} \right|}}{{\left| {EO} \right|{\rm{tan}}\theta }} $ | (3) |
由式(3) 可得,构件的大小与构件至视点距离的关系为:
$ \frac{{\left| {PO} \right|}}{{\left| {EO} \right|}} = k * {\rm{tan}}\theta $ | (4) |
因此可以得出以下结论:构件投影至计算机屏幕显示所占据的像素点数量,由构件自身的几何尺寸及构件与视点之间的距离共同决定。观察物至视点的距离|EO|越小,则投影至投影面AB的长度占比k越大,因而其投影至屏幕所占据的像素点数量就越多。
结合上述分析,此处给出影响构件投影至屏幕最终占据像素点数量多少的关键因素“体素占屏值”“构件占屏值”以及“叶节点占屏值”的定义。
定义1 体素占屏值是指在已知和视点距离的情况下,体素自身最能影响其投影至屏幕所占据的像素点数量的几何尺寸。
定义2 构件占屏值是指组成该构件所有体素的体素占屏值的最大值。
定义3 叶节点占屏值是指该叶节点所挂载的所有构件的构件占屏值的最大值。
针对以上定义,本文对各类基本体素的体素占屏值设定选取规则如表 1所示。
由于工厂模型在设计时是以三维方式呈现,为了充分利用模型的空间结构特征,本文采用八叉树[13]对模型构件进行层次组织,构建场景树。
八叉树的根节点,即组成流程工厂模型所有构件构成的轴对齐包围盒(Axis-Aligned Bounding Box, AABB包围盒),其特征为盒体的每个面均和一条坐标轴垂直。八叉树的中间节点和叶节点,均通过其父节点AABB包围盒对应的空间区域进行递归层次划分而获得(如图 3)。构件依据构件自身的包围盒中心所对应的空间区域范围设为相应叶节点的孩子节点。
细节裁剪的思想,是通过估算处理对象投影至屏幕所占据的像素点数量来决定是否剔除绘制。传统的细节裁剪方法,处理对象为构件剖分后的三角面片,其一帧裁剪处理的时间复杂度与模型三角面片规模成正比,因此,当模型面片规模达到上亿时,裁剪效率低下。
本文所述的基于八叉树的大规模流程工厂模型细节裁剪算法,其裁剪处理对象从三角面片转化为一系列构件。
其具体原理如下:首先根据构件体素的参数信息进行剖分,获取对应的顶点、法线以及颜色数组,并利用顶点数组信息计算构件的AABB包围盒;同时,根据表 1所述的规则,计算每个体素的体素占屏值,进而计算构件占屏值。其次,对构件按构件占屏值大小进行排序,将其划分为大小构件集合,记为L与S;然后,分别对两个构件集合依据其所挂载的构件的顶点信息获取全局AABB包围盒,并基于此按图 3递归创建八叉场景树,记为octreeL与octreeS。
最后在一帧的裁剪绘制阶段,首先对octreeL以及octreeS的中间节点与叶节点直接依据其AABB包围盒进行视锥体裁剪测试。对通过视锥体裁剪测试的octreeS的叶子节点,计算叶节点占屏值pmax与视点至其包围盒中心的距离的商,进而与预设的k′ tan θ的值作对比,从而判断当前叶节点下所有构件投影至屏幕所占据的像素点数量上限,达到快速剔除与否的效果。而对于octreeL,依据其叶节点包围盒进行视锥体裁剪获得保守可见集,故即使在剔除octreeS所有构件的情形下,亦能通过octreeL的可见集,来最大限度地展示流程工厂模型的轮廓外观。
所述的k′ tan θ,其获取借助式(4),模拟计算一定大小的构件,在一定的距离上,其投影至屏幕占用像素点数量为1×1时k tan θ的大小。并在1×1的基础上对k tan θ进行比例缩放至k′ tan θ,即得裁剪阈值(本文k′ tan θ的取值为0.002,在屏幕分辨率为1 920×1 080的情况下,其代表的像素点数量大约为14×14,其中k′取值为0.007 5)。
2.2 算法实现本文所述的一种基于八叉树的大规模工厂模型细节裁剪算法,其流程包括模型读取与构件信息初始化,场景树建立以及一帧绘制与裁剪渲染,实现流程如图 4所示。
模型读取的过程,即创建构件的过程。正如前文所述,构件一般由网格体素、面片体素、多边形体素或18种基本体素组合构成。通过读取每个构件对应体素的参数信息,并进行相应的剖分,最终获取渲染构件节点所需的顶点、法线以及颜色数组。
算法1 构件包围盒初始化。
输入:构件剖分后的顶点数组;
输出:构件的AABB包围盒。
1) 初始化该构件的AABB包围盒(由[(xMin, yMin, zMin) ~ (xMax, yMax, zMax)]所对应的空间区域组成,其中xMin表示x的最小值,xMax表示x的最大值,其余以此类推。minVal、maxVal表示程序可取的最小值和最大值)
$ \begin{array}{l} {\rm{(xMin,\ yMin,\ zMin) = (maxVal,\ maxVal,\ maxVal)}}\\ {\rm{(xMax,\ yMax,\ zMax) = (minVal,\ minVal,\ minVal)}} \end{array} $ |
2) 取出构件的顶点数组,对每个顶点v = (x, y, z),计算xMin = min(x, xMin); yMin = min(y, yMin);
$ \begin{array}{l} {\rm{zMin = min(z,\ zMin); \ xMax = max(x,\ xMax);}}\\ {\rm{yMax = max(y,\ yMax); \ zMax = max(z,\ zMax) }} \end{array} $ |
3) 得到AABB包围盒[(xMin, yMin, zMin) ~ (xMax, yMax, zMax)]。
通过剖分后的顶点数组,对构件求取AABB包围盒,具体见算法1。同时,按照表 1所述的体素占屏值的选取规则,计算每个体素的体素占屏值,进而计算构件的构件占屏值pi。
获得已初始化相关信息的构件集合A。
2.2.2 场景树建立为了获取流程工厂模型中能够显示工厂模型轮廓的大构件信息,本文在2.2.1节所获取的构件集合A的基础之上,将构件集合依据预设的划分占屏值再次划分成构件集合L与S(L表示构件占屏值大于划分占屏值的构件集合,S则相反),具体见算法2。
算法2 构件集合L与S获取。
输入:构件集合A;
输出:构件集合L与S。
1) 对构件集合A依据构件占屏值pi从大到小排序;
2) 设定划分权重x%,获取在构件集合A中x%处的构件对应的构件占屏值p(记为划分占屏值);
3) 将构件占屏值大于p的构件划分至构件集合L,否则划分至集合S。
对构件集合L和S,按照算法1步骤,分别求取其对应的AABB包围盒lAABBBox及sAABBBox。并依据lAABBBox以及sAABBBox,分别按预设深度hl、hs从上至下层次递归建立八叉树octreeL与octreeS,见算法3。并将其根节点设为模型根节点的孩子节点,场景图见图 5。
算法3 场景树建立。
输入:构件集合L与S;
输出:场景树。
1) 预设octreeL、octreeS的八叉树深度hl、hs。
2) 层次递归创建八叉树octreeL。
① 对lAABBBox按图 3进行递归层次创建八叉树,深度为hl。
② 将构件集合L中的构件依据包围盒中心设置为octreeL对应叶节点的孩子节点。
3) 层次递归创建八叉树octreeS。
① 对sAABBBox按图 3进行递归层次创建八叉树,深度为hs。
② 将构件集合S中的构件依据包围盒中心设置为octreeS对应叶节点的孩子节点。
③ 计算octreeS每个叶节点的叶节点占屏值pmax。
4) 将octreeL与octreeS的根节点设置为场景节点的孩子节点。
2.2.3 一帧绘制与裁剪渲染一帧绘制与裁剪渲染,包括对octreeL与octreeS叶节点进行相应的视锥体裁剪与细节裁剪操作,其实现流程见算法4。
算法4 一帧绘制与裁剪渲染。
输入:场景树;
输出:模型的一帧渲染及其交互。
1) 一帧渲染开始。
2) 若遍历的节点为八叉树的中间节点或叶节点,则直接进行视锥体与包围盒测试,不在视锥体内则直接剔除,否则递归遍历或绘制。
3) 若遍历的节点为octreeS的叶节点,且通过视锥体裁剪测试,则:
① 计算当前叶节点的叶节点占屏值pmax与视点至其包围盒中心距离的商t;
② 比较预设的k′ tan θ与t的大小关系:若k′ tan θ > t,表示该叶节点下最大构件投影至屏幕像素点数量足够少,直接剔除;否则,进行绘制,并遍历下一节点。
4) 可选的,也可采用3)①~3)② 所述的方法,将其作为细节层次变化的度量方式,对构件实施细节层次(Level of Detail, LOD)绘制。
5) 若节点遍历完毕,则跳转至1) 开始下一帧的渲染;若程序关闭,则渲染结束。
3 实验结果与分析本文所采用的测试机器配置为Windows 7 64 b操作系统,处理器为Intel Core i5-3470 CPU @ 3.20 GHz (4CPU), ~3.60 GHz,内存为16 GB,显卡为Nvidia GeForce GT 520,屏幕分辨率为1 920×1 080。算法集成测试平台为PDSOFT Open5D,帧率采集软件使用fraps(Version 3.4.7)。同时,对于octreeL以及octreeS的八叉树深度,hl,hs均设为4。
测试模型采用管线规模达9 710根管线的某化工工厂模型以及5 736根管线的某液腊工厂模型(其形态与数据分别见图 6与表 2),分别与主流漫游软件PDSOFT Review,Navisworks Manage进行测试对比,其结果见表 3。
同时,对表 3所述平台分别采用1 942、3 884、5 826、7 768以及9 710根管线的流程工厂模型进行测试,帧率变化与管线关系如图 7所示。结果表明,该算法和现今主流漫游软件相比帧率提升显著,且其帧率大大高于传统的细节裁剪算法。
再以某化工工厂模型为例,当对其进行交互与静态操作时进行对比,结果如图 8所示。结果表明,该算法在交互过程中进行快速剔除与绘制的同时,也可完整显示工厂模型的轮廓。
综上所述,本文所述方法,与传统细节裁剪算法相比,其时间复杂度从O(N)降低至O(8h-1),交互帧率可提升至少200%。其中所述N为三角面片的数量,h为八叉场景树的高度,8h-1表示八叉树叶节点的数量(h通常取4或5)。在帧率提升的同时,该方法可最大限度显示流程工厂模型的整体轮廓。本文所述方法已集成至拥有自主知识产权的三维协同设计图形平台PDSOFT Open5D,对图形平台的市场竞争力与流程工厂行业的整体设计产能的提升有极大的促进作用。
4 结语本文根据流程工厂模型的特征,提出一种基于八叉树的大规模流程工厂模型细节裁剪算法。该算法充分应用模型构件体素的几何特征以及模型整体的三维空间特征,快速估算出模型构件投影至屏幕所占据的像素点数量,进而剔除小于预设像素点数量阈值的构件,提升裁剪效率,降低后续绘制阶段的负担,从而提升绘制帧率。与传统采用计算三角面片对应像素数量的细节裁剪算法相比,本文所述的算法直接借助空间建模的八叉树叶子节点,对于面片规模上千万的模型,数据处理规模可降低至原来的1/100。在提升帧率的同时,也可呈现出流程工厂模型的整体轮廓。
更进一步地,本文所述的像素点数量的度量方法,亦可应用为细节层次变化的度量准则。并且,通过设定前文所述的构件划分权重x%的取值,可以依据现实情况,自适应调整可达到显示控制帧率的效果。
在后续的研究中,所述的网格体素、面片体素以及多边形体素仍需进一步考虑与选取合适的占屏值度量方法,使得该方法对所有的流程工厂模型而言,具有更高的普适性与通用性。
[1] | COHEN-OR D, CHRYSANTHOU Y L, SILVA C T, et al. A survey of visibility for walkthrough applications[J]. IEEE Transactions on Visualization and Computer Graphics, 2003, 9(3): 412-431. DOI:10.1109/TVCG.2003.1207447 |
[2] | LUEBKE D, GEORGES C. Portals and mirrors:simple, fast evaluation of potentially visible sets[C]//Proceedings of the 1995 Symposium on Interactive 3D Graphics. New York:ACM, 1995:105-106. |
[3] | TELLER S J, SÉQUIN C H. Visibility preprocessing for interactive walkthroughs[EB/OL].[2016-11-06]. https://static.aminer.org/pdf/PDF/000/594/056/visibility_preprocessing_for_interactive_walkthroughs.pdf. |
[4] | AIREY J M, ROHLF J H, BROOKS, Jr. F P. Towards image real-ism with interactive update rates in complex virtual building environments[C]//Proceedings of the 1990 Symposium on Interactive 3D Graphics. New York:ACM, 1990:41-50. |
[5] | HUGHES J F, VAN DAM A, FOLEY J D, et al. Computer Graphics:Principles and Practice[M]. Upper Saddle River, NJ: Pearson Education, 2013: 1047-1048. |
[6] | WEILER K, ATHERTON P. Hidden surface removal using polygon area sorting[C]//Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques. New York:ACM, 1977:214-222. |
[7] | EDWARD A. 交互式计算机图形学: 基于OpenGL的自顶向下方法[M]. 张荣华, 姜小磊, 宋雨, 译. 北京: 电子工业出版社, 2009: 196-198. (EDWARD A. Interactive Computer Graphics:a Top-down Approach using OpenGL[M]. ZHANG R H, JIANG X L, SONG Y, translated. Beijing:Publishing House of Electronics Industry, 2009:196-198.) |
[8] | CLARK J H. Hierarchical geometric models for visible surface algorithms[J]. Communications of the ACM, 1976, 19(10): 547-554. DOI:10.1145/360349.360354 |
[9] | 许云杰, 胡事民. 基于层次细节模型的遮挡裁剪算法[J]. 中国图象图形学报, 2002, 7(9): 962-967. (XU Y J, HU S M. An occlusion grid culling algorithm based on LOD models[J]. Journal of Image and Graphics, 2002, 7(9): 962-967.) |
[10] | ZHANG H. Effective occlusion culling for the interactive display of arbitrary models[D]. Chapel Hill, NC:University of North Carolina, 1998. http://dl.acm.org/citation.cfm?id=336054 |
[11] | ZHANG H, MANOCHA D, HUDSON T, et al. Visibility culling using hierarchical occlusion maps[C]//Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York:ACM/Addison-Wesley, 1997:77-88. |
[12] | BERNARDINI F, KLOSOWSKI J T. Directional discretized occluders for accelerated occlusion culling[J]. Computer Graphics Forum, 2010, 19(3): 507-516. |
[13] | ASSARSSON U, MÖLLER T. Optimized view frustum culling algorithms for bounding boxes[J]. Journal of Graphics Tools, 2000, 5(1): 9-22. DOI:10.1080/10867651.2000.10487517 |