基于Z-buffer算法优化的大型变电站场景模型快速线消隐方法

罗国亮，王 睿，吴 昊，赵 昕，黄晓生，曹义亲，廖成慧

基于Z-buffer算法优化的大型变电站场景模型快速线消隐方法

罗国亮1,2，王 睿2，吴 昊2，赵 昕2，黄晓生2，曹义亲2，廖成慧1

(1. 江西博微新技术有限公司，江西 南昌 330000；2. 华东交通大学软件学院，江西 南昌 330013)

针对现有三维模型消隐方法面向大规模三维场景模型应用中存在的计算复杂、耗时长等缺陷，本文提出了基于改进Z-buffer算法对大型变电站场景消隐的快速可视化方法。首先，为了简化计算，将场景模型数据整合并重构；其次，通过透视投影变换将变电场景模型像素化；进一步，基于Z-buffer算法高效的像素化计算特性提出了快速模型筛选方法，从而得到变电场景的子模型遮挡关系。最后，实验中将所得遮挡关系列表融合现有消隐算法，结果表明本文提出的方法能够大幅度提升消隐的运算性能。

大规模变电场景；消隐；Z-buffer算法；模型筛选；运算性能

当前，三维建模工具发展日新月异，包括基于深度学习方法的智能建模方法也随着人工智能进步得到了长足发展。在此背景下，大规模的三维模型已经开始逐步取代传统的二维或伪三维数据，成为工业设计、数字媒体娱乐、虚拟现实和增强现实等产业的主流数据载体。与此同时，由于三维模型同二维数据相比数据尺度极大，数据精度要求极高，相应的对三维模型显示技术也提出了新的挑战。

在计算机图形学和几何学领域，学者们自三维模型兴起之初就一直致力于实现方法及其性能提升方面的研究工作。其中，Z-Buffer算法是三维显示中最经典的方法之一。尽管三维模型的数据单元(包括空间点坐标与属性及拓扑结构等)在复杂模型中包含大量数据，但该算法仅考虑显示平面范围内每个像素点的坐标方向的深度信息，可有效优化了三维显示性能。然而，在当代兴起的虚拟现实产业及工业4.0产业浪潮中，逐渐形成海量大规模三维模型数据，对模型显示性能及对生产安全和用户体验要求极高，使得面向大规模三维模型的显示方法依旧是相应领域的研究重点之一。现有面向大规模三维场景模型应用中的三维模型消隐方法存在着计算复杂、耗时长等缺陷，因此本文在分析与研究的基础上对其进行改进，以做到大规模提升运算性能的效果。此外，本文基于OCC (Open CASCADE)库的消除隐藏线(hidden line removal，HLR)方法实现消隐，其消隐对象为各元器件的边界表示结构(boundary representation，BREP)，即各模型的线框线条。

本文提出优化方法适用于复杂的大规模场景模型的消隐可视化计算，其主要贡献包括：

(1) 对大规模三维变电站场景的模型与模型之间遮挡关系做出筛选，从而减少多余运算。

(2) 在OCC库的HLR功能的基础上进行性能优化，且对时间性能的提升是显著的，仅为原时间的近万分之一。

1 相关工作

在硬件性能提升和产业需求促进下，大规模三维模型数据在本世纪初逐渐兴起，学者们针对这类数据的显示问题开展了一系列研究工作[1-5]。文献[1]将届时主流的大规模三维模型的显示技术分为选择性可视、简化、缓存和数据压缩方法；文献[2]则提出约束带的概念，并用于实现高效的交互式显示方法；文献[3]提出了一个基于排序的流水线架构；文献[4]提出的空间提取方法均先后用于三维显示；文献[5]提出了“探索地图”概念，即通过构建复杂三维场景的全景式视图来实现高效的三维模型浏览。

基于大规模三维模型显示的方法，学者们在诸多领域进行了探索与应用研究。文献[6]介绍了考古基地的显示方法及其应用于虚拟现实展示方法的研究工作；CARTER等[7]研究了复杂PDM系统的模型显示方法；SÜß等[8]则研究了针对分布式三维场景的非同步障碍物异步计算集群的高性能显示方法；文献[9]提出构建三维模型间的连接和语义关系来优化三维模型检索、浏览、展示和标记，从而最终实现有效的大规模三维场景显示。同时，学者们针对大规模三维显示也在自然文化遗产保护[10]和复杂医学模型[11]开展了相应应用研究工作。

基于大规模模型的数据体量特性，三维模型显示方法性能是评估方法的重要指标之一。为此，诸多前期文献集中在实时显示方面开展研究工作[12-13]。其中，文献[12]通过集成数据放大和慵懒评估方法实现了渐进式建模，从而实现了大规模模型的渐进式显示；DU和LI[14]则提出下采样的金字塔型多层表示方法来表征三维模型；而RODRÍGUEZ等[15]则汇总了主流的GPU性能优化方法；冯浩和樊红[16]提出了一种针对单个模型的基于索引重排的部分消隐方法和技术，实现了模型的动态消隐和实时消隐；毛峡等[17]提出了一种基于点线关系的三维透视图消隐算法，为地形地物透视图的消隐提供了一种新的方法与支持手段；徐越月和林大钧[18]通过线段在投影过程中的深度比较，可区分可见线段和不可见线段，利用邻边几何关系补充部分可见线段来实现对立体图的消隐；李军民和袁青[19]提出剔除指定视点下明显不可见的面和线，获取可见线之后，对有线子段采用中点判断法正确地得到了三维物体的投影图，具有较好的消隐效率；HSU和HOCK[20]提出了从三维场景中删除隐藏线的通用解决方案，其可以准确地构造物体相互穿透时形成的连接线；BÆRENTZEN等[21]提出了2种新颖且鲁棒的线框制图技术，第1种方法是单程技术，非常适合于小N (特别是四边形或三角形)的凸N边形。结果表明，该方法比较有效，并且非常适合使用几何着色器实现。第2种方法是完全通用的，适用于非凸的任意N边形；CAPOWSKI和JOHNSON[22]提出了一种简单有效的算法，用于删除三维模型显示中的隐藏线，该算法针对由一系列堆叠平面轮廓组成的三维模型进行截面重建。部件的轮廓线框消隐方面；徐鑫等[23]针对传统线消隐算法的输出错误、图元缺失等问题，提出了一种容差可控的线消隐算法，该算法以三角网格为输入，用三角形求交的方法计算出所有的轮廓线和部分尖锐的棱；刘刚等[24]根据三维模型面片的方向对边进行分类，筛选出轮廓边即共享可见面与不可见面的边，最终得到外轮廓线。

Z-Buffer在图形学发展早期被提出用于基本三维模型的显示方法之一，由于其高效的计算特性，现已成为三维显示经典方法之一[25-26]。同时，为适应不同应用及当前三大规模三维模型应用场景，学者们始终致力于该算法优化研究。其中，文献[27]提出层级式深度缓冲以最小化三维显示时的内存带宽消耗；基于显示平面与三维模型的整体显示构造，截锥模型及阴影模型也同样在三维显示方法中广泛使用[28-30]。除此之外，Z-Buffer方法也在诸如自动建模仿真[31]、三维场景中模型间语义关系构建中起到了关键作用[32]；GREENE等[33]提出了一种可以快速剔除模型中的隐藏几何结构并利用生成图像的空间和时间的一致性的Z-buffer扫描转换算法，该方法使用非常适用于具有高深度复杂度的模型，与普通的Z-buffer扫描转换相比，在某种情况下可以实现指数级的加速。

2 数据预处理

大型变电站场景mesh模型是由数以万计的基本模型构成，且模型之间相互独立，若单个模型逐一运算不但耗时长且浪费运算资源，因此为了简化计算需要对模型数据进行预处理，具体地：主要是将数以万计的基本模型整合为一个大场景模型，并带有原始模型ID的标签(图1)。

图1 流程图

经过整合得到的mix和mix在3.1.3节的模型筛选方法中起到至关重要的作用。

3 三维消隐算法(优化Z-buffer算法)

3.1 透视投影变换

为了使显示的模型能以合适、准确的位置、大小及方向显示出来，则必须通过投影。同时，由于三维模型是在世界坐标系中所建立的，而计算机屏幕所显示的图形是在给定视点和视线方向下的二维屏幕上进行，所以透视投影变换是联系三维地形与屏幕二维图形的桥梁。

大型三维变电站场景的投影一般为简单的一点透视投影，由于在一点透视投影变换中，投影平面取坐标系中的一个坐标平面，因此用一个坐标系即可表示透视投影变换(图2)。在透视投影中往往要求物体不动，让视点在以形体为中心的球面上变化来观察各个方向上的图像，其方法为移入一个过渡坐标系，即视点坐标系。视点坐标系是三维直角坐标系，与一般物体所在的世界坐标系不同，其以人眼为坐标原点，坐标轴遵循左手法则。引入视点坐标系后，透视投影变换可看作是2个基本变换，即世界坐标系到视点坐标系的变换和视点坐标系到屏幕坐标系的变换。

世界坐标系到视点坐标系的变换过程如下。

设视平面(投影平面)在观察方向上离视点的距离为z，场景的顶点坐标为(x,y,z)，变换到视点坐标系下的坐标为(x,y,z)，场景坐标系至视点坐标系的变换矩阵为，则从视点坐标系到屏幕坐标系的变换为

带入到视点坐标系下一点透视投影的变换公式可得投影平面上的场景坐标(x,y)，见式(2)。为了简化计算，需统一将视点置于大型三维变电站场景的正上方，即顶视图。

图2 透视投影变化视景图

3.2 三维场景像素化方法

基于上述的三维变电站场景的透视投影变换得到的投影平面坐标(x,y)，本文进一步将大型三维变电站场景模型像素化，像素化的意义在于化繁为简，将三维空间内的空间模型的遮挡关系判断转化为二维像素下的空间模型遮挡关系的判断，并为随后的模型筛选做好铺垫。

已知大型三维变电站场景数据的表征形式为mesh，其由顶点和三角面片构成，同时依据三维变电场景经过透视投影变换得到的投影平面坐标(x,y)的整体范围跨度，本文定义了一个×的像素网格。

首先，对于场景中的三角面片mix，本文计算每个三角面片F的轴对齐包围盒(AABB式包围盒)，设三角面片3个顶点坐标为1，2，3。同时定义×的行像素索引矩阵和列像素索引矩阵，即

针对每个三角面片，设定其投影所占据的行像素集合为P，列像素集合为P。

求解上述方程得

图3 三角形重心

对应地，构建一个×的矩阵，用来存储上述三角面片所在的像素单元，每个像素所对应的三角面片在其世界坐标系下的深度值信息，即()=，则有

3.3 模型筛选方法

将大型三维变电站场景内个模型分标签筛选的前提是将三维场景进行像素化，该部分3.2节已介绍，前2节已将Z-buffer的核心部分涵盖，同时搭配每个像素对应的模型索引ID便可对模型进行分类筛选(图4)。每个像素单元对应的模型索引ID依附于每个模型的三角面片，由第2节得到的三角面片集合mix可针对性的解决该问题。以下伪代码将清晰地描绘整个过程，该算法的时间复杂度约为()。

算法：模型筛选

模型筛选流程(mix，，，，，P，，

值集合zbuffer，模型ID集合fbuffer)

图4 模型筛选方法流程图

Fig. 4 Flow chart of model selection method

具体地，遍历mix中的每一个三角面片，若三角面片的包围盒检测后包含了像素点，则将包含的像素坐标存储在对应数组中，而后遍历该三角面片的包围盒所包含的每个像素，将模型ID存入矩阵F_in_Pixel中；其次针对每个三角面片计算其，值，判断包围盒囊括的像素点是否在三角形内部，若像素点在三角形内部，则将深度值存入数组P中，再遍历存有深度值的像素点，选取深度值最大的像素单元，将其分别对应的深度值信息存入数组zbuffer中，模型ID信息存入数组fbuffer中。

最后本文在每个像素单元中得到存有模型ID信息的序列，每个投影至该像素的三角面片所对应的模型ID都会被存储，最靠前的ID对应的是深度值最大的模型ID，意味着其离屏幕越近，该单元中后面2～个模型ID便与第一个模型ID存在着前后遮挡关系，具体有以下3种关系：

(1) 模型遮挡模型。若该像素单元的模型ID数大于等于2，则存在相互遮挡关系，其第1个模型遮挡后面第2～个模型；

(2) 模型完全被遮挡。先将所有像素单元存储的第1个模型ID整合，在变电站所有模型中除去整合后模型，剩余模型即为完全被遮挡的模型；

(3) 模型独立。若在相当范围内的像素单元中只有该模型ID，没有出现第2个模型ID，则该模型独立。

4 实验和讨论

本文实验的硬件环境为：CPU Intel i7-8750H 2.20 GHZ，8 GB内存，GTX1050 Ti显卡(显存为4 GB)。测试软件环境为：MATLABR2018a，Visual Studio 2017。

4.1 优化Z-buffer算法

4.1.1 样本数据简介

本文使用的大型三维变电站场景的mesh信息是由13 813个基本模型构成，总计有9 947，892个顶点；3 255 510个三角面片；大型变电站场景模型的消隐是根据OCC库所提供的HLR方法实现，结合优化的Z-buffer算法，即可得到大型三维变电站场景的消隐可视化结果。

4.1.2 OCC消隐实验

OCC平台是由法国Matra Datavision公司开发的CAD/CAE/CAM软件平台，是几何造型基础软件平台之一，其主要用于开发二维和三维几何建模应用程序，包括通用或专业的计算机辅助设计(CAD)系统、制造或分析领域的应用程序、仿真应用程序或图形演示工具。

本文选取的是调用OCC库中针对三维实体的隐藏线算法功能：HLR基本算法思想是先将算法输入的三维mesh模型转化为边界表示法结构(boundary representation, Brep)以及对应的拓扑结构(TopoDS)来实现空间消隐。

步骤1.输入当前需要参与计算的2个三维模型的三维TopoDS_Shape ()结构；

步骤2.根据当前视点方向设置投影；

步骤3.计算这2个模型的前后遮挡关系，若无遮挡关系则直接分别计算2个模型轮廓线，若有遮挡关系则首先计算前后遮挡关系再根据遮挡关系计算当前2个模型的轮廓线；

步骤4.计算模型的可见与隐藏线；

步骤5.输出提取消隐后的二维TopoDS_Shape ()结构。具体的函数调用流程如下：通过使用HLRBRep_Algo::Add()函数来将需要被消隐的形状加入到消隐算法中去。对于HLRBRep_PolyAlgo对象，使用HLRBRep_PolyAlgo::Load() 函数来添加一个或多个需要处理的形状。通过函数HLRBRep_ PolyAlgo::Projector()来设置投影方向，其参数为一个HLRAlgo_Projector对象。一般会根据三维视图数据来得到这个投影数据，进而来设置需要消隐的投影参数。通过类HLRBRep_PolyAlgo中的函数HLRBRep_PolyAlgo::Update() 来计算模型的外轮廓。当用类HLRBRep_Algo时，使用HLRBRep_ Algo::Update()这个算法时，必须调用方法HLRBRep_Algo::Hide() 来计算模型可见与隐藏线。使用类HLRBRep_PolyAlgo时，可见与隐藏线是通过HLRBRep_PolyHLRToShape来计算。通过类HLRBRep_HLRToShape和HLRBRep_PolyHLR ToShape来提取消隐后的模型数据，提取数据来源分别对应HLRBRep_Algo和HLRBRep_PolyAlgo对象。图5为消隐实验算法流程图。可提取的模型元素类型有：

(1) Visible/hidden sharp edges；

(2) Visible/hidden smooth edges；

(3) Visible/hidden sewn edges；

(4) Visible/hidden outline edges。

提取所得到消隐结果的操作是由函数HLRBRep_ PolyHLRToShape::Update来实现。特别地，整个HLR功能可以被GPU实现。

在当前视点的消隐运算结束并改变视点后，需要重新光栅化，且光栅化的分辨率与最终绘制的分辨率一致。

图5中变电站场景模型集为已判断完遮挡关系的模型集，其可作为稀疏矩阵输入到HLR算法中，经OCC运算后得到消隐结果。

图5 消隐实验流程图

4.2 实验结果与比较

4.2.1 变电站局部实验结果

本文实验比较了变电站中的变压器器件在使用和未使用Z-buffer筛选算法(仅使用OCC平台的消隐功能)的2种情形，结果如图6所示。

由图6可以看出优化前、后其结果差异并不大，其模型消隐结果基本正确，但是其计算遮挡次数的算量大幅减少，消隐运算时间也得到相应减少(表1)，优化前、后的所需计算模型数量相应减少，计算遮挡次数缩小至原先的近千分之一，不难看出本文优化方法不仅剔除了大量的多余的遮挡运算也加快了运算时间，同时其本身Z-buffer算法的时间性能也较快，这在4.2.2节的结果中将更明显地体现。变压器的数据预处理时间为22 ms。

图6 优化前后结果图

4.2.2 变电站全局实验结果

使用本文优化方法之前和之后得到的消隐可视化结果并无多少区别，但是节省了相应的运算资源及时间成本，由于OCC强大的运算能力，对于小部件的运算目前体现不了优化方法的提升性能，因此本文用全局110 kV变电站场景来测试优化方法对运算性能的提升(表2)。

由于OCC的HLR功能的算法复杂度为(2)，其中，为模型数目，所以由表2可以看出，优化前后参与运算的模型数量减少至原来的近十分之一，而计算遮挡的次数减少至原来的近十万分之一，运算时间更是由原来的大于8 h缩短至10 s以内，由此可见本文优化方法对于整个消隐性能的提升是十分显著的，模型数目越庞大，优化性能的效果越明显；整个变电站场景的数据预处理时间为263 ms。图7为110 kV变电站的全局消隐结果图，从展现的结果来看，其消隐结果基本正确。

表1 变压器使用Z-buffer筛选算法优化前后耗时对比1

表2 变电站使用Z-buffer筛选算法优化前后耗时对比2

图7 全局消隐结果图((a)全局线框图(未对线框消隐)；(b)全局消隐图)

5 结束语

本文针对大规模三维变电站场景模型的消隐提出了基于优化Z-buffer筛选算法的消隐方法。首先通过数据预处理将变电站场景模型的数据进行整合，构造便于计算的数据结构，然后将场景模型经过透视投影将模型像素化，基于像素化后的模型进一步利用像素及本文设计数据结构的特点对模型进行筛选，定位出相互间的遮挡关系，最后调用OCC库HLR方法对整个场景模型完成消隐运算。本文提出的方法适用于任意一个大规模三维场景的消隐实现。

尽管本文提出的方法对消隐算法的性能提升具有一定的有效性，但是对于更大规模的变电站场景还无法达到工程上所需满足的时间，暂时还无法与bentley等软件的消隐算法的性能相媲美，但是相较国内与之相关的成熟算法匮乏的情况下为该算法的改进提供了新的方向和思路。因此，本文研究的下一步工作拟将三维场景中的模型的线框表示方法直接运用于本文提出的优化Z-buffer算法中，期望不调用OCC库HLR方法从而自主设计一个消隐方案来达到消隐功能的实现以及时间性能的提升。

[1] GOBBETTI E, KASIK D, YOON S E. Technical strategies for massive model visualization[C]//2008 ACM Symposium on Solid and Physical Modeling. New York: ACM Press, 2008: 405-415.

[2] DIAZ-GUTIERREZ P, BHUSHAN A, GOPI M, et al. Constrained strip generation and management for efficient interactive 3D rendering[C]//2005 International Computer Graphics. New York: IEEE Press, 2005: 115-121.

[3] FALCHETTO M, BARONE M, PAU D, et al. Sort middle pipeline architecture for efficient 3D rendering[C]//2007 Digest of Technical Papers International Conference on Consumer Electronics. New York: IEEE Press, 2007: 1-2.

[4] HUANG J B, ROETCISOENDER G, VENKATASUBRAMANIAM B. Massive model visualization with spatial retrieval: United States, EP20120808943[P]. 2012-09-07.

[5] DI BENEDETTO M, GANOVELLI F, BALSA RODRIGUEZ M, et al. ExploreMaps: efficient construction and ubiquitous exploration of panoramic view graphs of complex 3D environments[J]. Computer Graphics Forum, 2014, 33(2): 459-468.

[6] BORBA E Z, MONTES A, ALMEIDA M, et al. ArcheoVR: exploring itapeva’s archeological site[C]//2017 IEEE Virtual Reality (VR). New York: IEEE Press, 2017: 463-464.

[7] CARTER M B, BENNETT J S, HUANG J, et al. Massive model visualization in PDM systems: United States, 14703489[P]. 2015-05-04.

[8] SÜß T, KOCH C, JÄHN C, et al. Asynchronous occlusion culling on heterogeneous PC clusters for distributed 3D scenes[C]//Advances in Visual Computing. Heidelberg: Springer, 2012: 502-512.

[9] SERNA S, PENA R, SCOPIGNO M, et al. 3D-Centered media linking and semantic enrichment through integrated searching, browsing, viewing and annotating[C]//The 12th International Conference on Virtual Reality, Archaeology and Cultural Heritage. New York: ACM Press, 2011: 89-96.

[10] MARTON F, MARCOS B R, BETTIO F, et al. IsoCam: interactive visual exploration of massive cultural heritage models on large projection setups[C]//ACM Journal on Computing and Cultural Heritage. New York: ACM Press, 2014: 12.

[11] NOBORIO H, KUNII T, MIZUSHINO K. Comparison of GPU-based and CPU-based algorithms for determining the minimum distance between a CUSA scalper and blood vessels[EB/OL]. [2021-01-09]. https://xueshu.baidu.com/ usercenter/paper/show?paperid=0c74dd560265b05d200a2729e50de570&site=xueshu_se.

[12] CORDEIRO C S, CHAIMOWICZ L. Predictive lazy amplification: synthesis and rendering of massive procedural scenes in real time[C]//The 23rd SIBGRAPI Conference on Graphics, Patterns and Images. New York: IEEE Press, 2010: 263-270.

[13] RICHTER R, DÖLLNER J. Out-of-core real-time visualization of massive 3D point clouds[C]//The 7th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa-AFRIGRAPH’10. New York: ACM Press, 2010: 121-128.

[14] DU Z, LI Q. A new method of storage and visualization for massive point cloud dataset[EB/OL]. [2021-01-09]. https:// xueshu.baidu.com/usercenter/paper/show?paperid=f42a9713c93569ad299299284a6aeaf3&site=xueshu_se&hitarticle=1.

[15] RODRÍGUEZ M B, GOBBETTI E, IGLESIAS GUITIÁN J A, et al. A Survey of Compressed GPU-Based Direct Volume Rendering[EB/OL]. [2021-01-09].https://xueshu.baidu.com/ usercenter/paper/show?paperid=703e59e7f4bddb37348bc158635a158b.

[16] 冯浩, 樊红. 三维城市规划中的三维模型三角网格自动消隐和分割技术[J]. 武汉大学学报: 工学版, 2014, 47(3): 399-406.

FENG H, FAN H. Automatic blanking and segmentation of 3D model triangular mesh[J]. Engineering Journal of Wuhan University, 2014, 47(3): 399-406 (in Chinese).

[17] 毛峡, 沈巍, 赵兴圆. 基于点线关系的透视图消隐算法[J]. 北京航空航天大学学报, 2009, 35(8): 925-928, 937.

MAO X, SHEN W, ZHAO X Y. Hidden-removal method of perspective drawing based on constrains between lines and junctions[J]. Journal of Beijing University of Aeronautics and Astronautics, 2009, 35(8): 925-928, 937 (in Chinese).

[18] 徐越月, 林大钧. 用计算机实现线框模型的消隐技术[J]. 华东理工大学学报: 自然科学版, 2011, 37(2): 250-253.

XU Y Y, LIN D J. Technique of realizing hiding of stereogram drawing with computer[J]. Journal of East China University of Science and Technology: Natural Science Edition, 2011, 37(2): 250-253 (in Chinese).

[19] 李军民, 袁青. 三维线框模型物体的隐藏线消除算法与实现[J]. 西北大学学报: 自然科学版, 2012, 42(6): 931-934.

LI J M, YUAN Q. The hidden line removel algorithm and its implementation of 3D wireframe model[J]. Journal of Northwest University: Natural Science Edition, 2012, 42(6): 931-934 (in Chinese).

[20] HSU W I, HOCK J L. An algorithm for the general solution of hidden line removal for intersecting solids[J]. Computers & Graphics, 1991, 15(1): 67-86.

[21] BÆRENTZEN J A, NIELSEN S L, GJØL M, et al. Two methods for antialiased wireframe drawing with hidden line removal[C]//The 24th Spring Conference on Computer Graphics – SCCG’08. New York: ACM Press, 2008: 171-177.

[22] CAPOWSKI J J, JOHNSON E M. A simple hidden line removal algorithm for serial section reconstruction[J]. Journal of Neuroscience Methods, 1985, 13(2): 145-152.

[23] 徐鑫, 施侃乐, 雍俊海. 容差可控的线消隐算法[J]. 系统仿真学报, 2013, 25(9): 2079-2084.

XU X, SHI K L, YONG J H. Hidden-line elimination with tolerance[J]. Journal of System Simulation, 2013, 25(9): 2079-2084 (in Chinese).

[24] 刘刚, 何援军, 柳伟. 基于边分类的三维模型外轮廓线抽取算法[J]. 东华大学学报: 自然科学版, 2005, 31(4): 1-5.

LIU G, HE Y J, LIU W. Extracting contour from 3D model base d on edge classification[J]. Journal of Donghua University, Natural Science, 2005, 31(4): 1-5 (in Chinese).

[25] EL GINDY H, AVIS D. A linear algorithm for computing the visibility polygon from a point[J]. Journal of Algorithms, 1981, 2(2): 186-197.

[26] PIYAZA T A, SAMUSEN E C. Z-Buffer technology for figure heightenin: China, 1270278C[P]. 2004-01-04.

[27] YU C H, KIM L S. A hierarchical depth buffer for minimizing memory bandwidth in 3D rendering engine: depth filter[C]//Proceedings of the 2003 International Symposium on Circuits and Systems, 2003. ISCAS’03. New York: IEEE Press, 2003: II.

[28] RYAN WYMAN C, ELIOT LEFOHN A, PATNEY A. Frustum tests for sub-pixel shadows: United States, 20160203635[P]. 2016-01-06.

[29] LI S L, WANG Q H, XIONG Z L, et al. Multiple orthographic frustum combing for real-TimeComputer-generated integral imaging system[J]. Journal of Display Technology, 2014, 10(8): 704-709.

[30] GERHARDS J, MORA F, AVENEAU L, et al. Partitioned shadow volumes[J]. Computer Graphics Forum, 2015, 34(2): 549-559.

[31] ZHANGHX, LIU ZW. Z-Axis buffering device of automatic screwing machine: China, 203579159U[P]. 2014-01-04.

[32] ZHAO J Q, ZHU Q, DU Z Q, et al. Mathematical morphology- based generalization of complex 3D building models incorporating semantic relationships[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2012, 68: 95-111.

[33] GREENE N, KASS M, MILLER G. Hierarchical Z-buffer visibility[C]//Proceedings of the 20th annual conference on Computer graphics and interactive techniques–SIGGRAPH’93. New York: ACM Press, 1993: 231-238.

Fast hidden line removal method for large-scale 3D substation scene model based on Z-buffer algorithm optimization

LUO Guo-liang1,2, WANG Rui2, WU Hao2, ZHAO Xin2, HUANG Xiao-sheng2, CAO Yi-qin2, LIAO Cheng-hui1

(1. Jiangxi Bowei New Technology Co., Ltd, Nanchang Jiangxi 330000, China; 2. School of Software, East China Jiaotong University, Nanchang Jiangxi 330013, China)

In order to overcome the defects of the application of hidden lines elimination to large-scale 3D scene models, such as high complexity calculation and high time consumption, in this article, a time efficient visualization method was presented for the hidden-line elimination of large substation scenes based on the improved Z-buffer algorithm. First, the original scene model data was integrated and then restructured to simplify the calculation. Secondly, the substation scene model was pixelated through perspective projection transformation. Then a Z-buffer algorithmbased model selection method was proposed to obtain the occlusion relationship of the sub-model of the substation scene, which took the advantage of its pixilation property. Finally, the obtained occlusion relationship lists were merged to the existing hidden line elimination algorithm. Our experimental results prove that the proposed approach can greatly enhance the computing performance of the application of hidden lines elimination to large-scale 3D scene models. Finally, the sub-model occlusion relationship of the substation scene was obtained.

large-scale substation scene; hidden-line; Z-buffer algorithm; model selection; computing performance

TP 751.1

10.11996/JG.j.2095-302X.2021050775

A

2095-302X(2021)05-0775-09

2021-01-31；

2021-02-15

31 January，2021；

15 February，2021

国家自然科学基金地区基金项目(地区)(61962021，61763011)；江西省科技厅2018重点研发计划项目(20181BBE50024)；研究生创新资金项目(YC 2019-S258)；江西省自然科学基金重点项目(20202ACBL202008)；中国博士后科学基金第13批特别资助(2020T130264)；江西省高等学校教学改革研究省级课题(JXJG-20-5-20)；2020年度江西省博士后科研项目择优资助(一等)；江西省教育科学规划课题(20YB056)；中国博士后科学基金面上项目(二等资助，2019M662261)；江西省博士后研究人员日常经费资助(2019RC27)；浙江大学CAD&CG国家重点实验室开放课题经费(A2023)；江西省自然科学基金重点研发项目(20192BBE50079)

National Natural Science Foundation of China Regional Fund Project (Region) (61962021,61763011); Jiangxi Provincial Department of Science and Technology 2018 Key R&D Program Project (20181BBE50024); Graduate Innovation Fund Project (YC 2019-S258); The key project of the Natural Science Foundation of Jiangxi Province (20202ACBL202008); The 13th Batch of Special Funding From the China Postdoctoral Science Foundation (2020T130264); Jiangxi Province Higher Education Reform Research Provincial Project (JXJG-20-5-20); 2020 Jiangxi Province Postdoctoral Research Project Selected Funding (First Class); Jiangxi Province Educational Science Planning Project (20YB056); China Postdoctoral Science Foundation Project (Second-Class Grant, 2019M662261); Daily Funding for Postdoctoral Researchers in Jiangxi Province (2019RC27); Open Project Funding for the State Key Laboratory of CAD&CG of Zhejiang University (A2023); Key R&D Project of Jiangxi Natural Science Foundation (20192BBE50079)

罗国亮(1985–)，男，江西南昌人，副教授，博士。主要研究方向为计算机图形学。E-mail：luoguoliang@ecjtu.edu.cn

LUO Guo-liang (1985–), male, associate professor, Ph.D. His main research interest covers computer graphics. E-mail：luoguoliang@ecjtu.edu.cn

CAO Yi-qin (1964–), male, professor, Ph.D. His main research interests cover pattern recognition, image processing. E-mail：yqcao@ecjtu.jx.cn

曹义亲(1964–)，男，江西都昌人，教授，博士。主要研究方向为模式识别、图像处理。E-mail：yqcao@ecjtu.jx.cn