基于八叉樹的大規模流程工廠模型細節裁剪算法

杜振林，唐衛清,，覃 力，李士才

(1.中國科學院 計算技術研究所，北京100190; 2.中國科學院大學 計算機與控制學院，北京101408;3.北京中科輔龍計算機技術股份有限公司，北京100085)(*通信作者電子郵箱tangweiqing@ict.ac.cn)

基于八叉樹的大規模流程工廠模型細節裁剪算法

杜振林1,2，唐衛清1,2,3*，覃 力1,2，李士才3

(1.中國科學院 計算技術研究所，北京100190; 2.中國科學院大學 計算機與控制學院，北京101408;3.北京中科輔龍計算機技術股份有限公司，北京100085)(*通信作者電子郵箱tangweiqing@ict.ac.cn)

針對傳統的細節裁剪算法，處理粒度為面片級，無法在規定時間內快速處理頂點、面片規模數以億計的流程工廠模型的問題，提出一種基于八叉樹的大規模流程工廠模型細節裁剪算法，用于解決傳統細節裁剪效率低下的問題，以保證較高的交互幀率。該方法依據組成流程工廠模型的構件體素特征以及空間特征，提出用于量化構件大小的占屏值，并結合建立的八叉場景樹，依據所述占屏值近似估算一系列構件投影至屏幕所占據的像素點數量上限，從而快速判斷是否裁剪。實驗結果表明，所提算法簡單有效，與現今主流的漫游軟件在加載具有10 000根管線的工廠模型后進行對比，其幀率至少提升50%，顯著提升了平臺的交互流暢度，對流程工廠行業以及圖形平臺整體的設計水平的提升有積極的意義。

流程工廠模型；細節裁剪；八叉樹；體素特征；幀率

0 引言

制造業是我國國民經濟的支柱產業，制造業發達與否也是衡量一國生產力水平高低的重要標準。而流程工業是制造業的一個重要分支，涵蓋了石油、化工、冶金等基礎性領域。隨著人類社會的不斷發展、經濟水平的不斷提高，人們對流程工業產能的需求也不斷增大。為了應對這種需求，人們不得不設計、建造更多、更大規模的流程工廠。正是在這種情況下，流程工廠設計平臺的模型處理能力及性能上限越來越受到設計人員和研究人員的關注。工廠模型數據規模增長而導致的圖形平臺交互幀率低下正是當前設計平臺最為突出的問題之一，而通過適當的裁剪算法以剔除不必要的渲染對象，加快渲染流程，從而提高交互幀率，是解決這一問題的重要方法。

圖形引擎繪制一幀的過程一般包括更新、裁剪以及繪制三個步驟，每個步驟的時長均對平臺最終的交互幀率有重要影響。在大規模復雜場景中，可見對象的數量通常遠遠小于場景數據集[1]。因此，在裁剪階段應用相關加速算法，對場景數據快速篩選，剔除不可見或投影至屏幕所占據的像素點數量小于一定閾值以致人眼無法捕獲的對象，可以減少大量不必要的繪制，大幅提升交互幀率。

可見集篩選產生的結果可歸為以下三類：1)精確可見集[2]，即精確包含所有可見對象的集合；2)近似可見集，即所得的可見集是精確可見集的真子集；3)保守可見集[3]，即所得的可見集可能包含部分不可見的對象。而上述三類可見集，統稱為潛在可視集(Potential Visibility Set, PVS)[4]。目前，存在大量獲取上述三類可見集的裁剪剔除算法，其中較為著名的有隱藏面剔除[5-7]、視域剔除[8]、背向面剔除、遮擋剔除[9]、層次遮擋圖[10-11]以及直接離散遮擋物[12]等方法。在這些算法中，也有學者繼續優化，以提升算法效率，比如視域剔除算法，文獻[13]提出一種基于軸對齊包圍盒和有向包圍盒的視錐體加速裁剪方法。

然而，在實際的流程工廠模型的設計過程中，當模型頂點、面片規模達到數以億計時，上述算法均無法很好地解決伴隨模型規模增長而導致交互幀率過低的問題。

由于流程工廠模型是由大量各類構件按相應的工藝及設計要求，有序連接而成。而在建模軟件中，各類構件均是由若干種體素組合而成。本文正是利用體素的幾何特征及模型整體的三維空間特征，提出一種基于八叉樹的大規模流程工廠模型細節裁剪算法。在本文提出的算法中，首先依據每一個構件體素的幾何特征以及設定的度量方法，快速度量構件的近似大小。并根據度量的構件大小，將構件集合劃分成大構件集合與小構件集合。其中大構件集合對應流程工廠模型的輪廓，小構件集合則對應流程工廠模型的細節。然后根據每個工廠模型的三維空間分布特征，采用兩棵八叉樹分別對大小構件集合進行層次組織，并將對應構件按包圍盒中心添加至對應的葉子節點。最后在渲染一幀的過程中，在裁剪階段依據大、小構件集合所對應的八叉樹的葉節點進行視錐體裁剪，并對小構件集合對應的八叉樹快速估算其葉子節點下所有構件投影至屏幕上所占的像素點數量上限，剔除小于設定閾值的構件，從而快速獲取可顯示工廠模型輪廓的保守可見集。實驗結果表明，與處理對象粒度為面片級的傳統細節裁剪算法相比，該方法在處理粒度為葉節點的級別上，能夠保證較高的交互幀率并較為完整地顯示工廠模型輪廓，達到交互過程流暢、顯示效果良好的目的。

1 基本理論

一個完整的流程工廠，由大量構件按照一定的工藝要求及工程約束有序連接而成。這里的構件泛指構成流程工廠的所有對象，包括：各類管道器材，如管件、法蘭、閥門、螺栓、螺母等；各類工藝設備：如泵、風機、鼓風機、壓縮機、真空設備、壓力容器、蒸汽透平、塔、儲罐、換熱器、加熱爐等。

而構件在建模的過程中，一般由網格體素、面片體素、多邊形體素以及18種基本體素(如圖1)組合構成。基本體素在流程工廠模型建模過程中均有相應的參數化表示，如：球，其參數化信息有半徑以及圓心坐標；而圓柱，其參數化信息有上頂面圓心坐標、下底面圓心坐標以及半徑等。

圖1 18種基本體素

體素的參數化信息對于構件而言有重要意義，它決定構件在一定的距離下投影至計算機屏幕顯示時所占據的像素點數量。圖2對這一過程進行了推導。

以圖2簡單表示視錐體。其中AB為近平面(其通常作為投影平面)，CD為遠平面。為了方便說明，以圓O表示位于視口中的構件，其半徑為|PO|，且AB的中垂線過圓心O(即EN⊥AB)。那么，圓O投影至AB上的長度為2|MN|，其中:

(1)

對此，圓O投影至AB上的長度占比k為：

(2)

其中，|AB|=2*|EN|*tanθ，θ為∠AEO(2∠AEO即為視場角，在程序運行時設置為常量，本文測試環境所采用的視場角為30°)，代入化簡，得:

(3)

由式(3)可得，構件的大小與構件至視點距離的關系為：

(4)

因此可以得出以下結論：構件投影至計算機屏幕顯示所占據的像素點數量，由構件自身的幾何尺寸及構件與視點之間的距離共同決定。觀察物至視點的距離|EO|越小，則投影至投影面AB的長度占比k越大，因而其投影至屏幕所占據的像素點數量就越多。

圖2 視錐體示意圖

結合上述分析，此處給出影響構件投影至屏幕最終占據像素點數量多少的關鍵因素“體素占屏值”“構件占屏值”以及“葉節點占屏值”的定義。

定義1 體素占屏值是指在已知和視點距離的情況下，體素自身最能影響其投影至屏幕所占據的像素點數量的幾何尺寸。

定義2 構件占屏值是指組成該構件所有體素的體素占屏值的最大值。

定義3 葉節點占屏值是指該葉節點所掛載的所有構件的構件占屏值的最大值。

針對以上定義，本文對各類基本體素的體素占屏值設定選取規則如表1所示。

由于工廠模型在設計時是以三維方式呈現，為了充分利用模型的空間結構特征，本文采用八叉樹[13]對模型構件進行層次組織，構建場景樹。

八叉樹的根節點，即組成流程工廠模型所有構件構成的軸對齊包圍盒(Axis-Aligned Bounding Box, AABB包圍盒)，其特征為盒體的每個面均和一條坐標軸垂直。八叉樹的中間節點和葉節點，均通過其父節點AABB包圍盒對應的空間區域進行遞歸層次劃分而獲得(如圖3)。構件依據構件自身的包圍盒中心所對應的空間區域范圍設為相應葉節點的孩子節點。

圖3 八叉樹

表1 體素占屏值設定，max-min表示取最大-最小值

2 算法原理與實現

2.1 算法原理

細節裁剪的思想，是通過估算處理對象投影至屏幕所占據的像素點數量來決定是否剔除繪制。傳統的細節裁剪方法，處理對象為構件剖分后的三角面片，其一幀裁剪處理的時間復雜度與模型三角面片規模成正比，因此，當模型面片規模達到上億時，裁剪效率低下。

本文所述的基于八叉樹的大規模流程工廠模型細節裁剪算法，其裁剪處理對象從三角面片轉化為一系列構件。

其具體原理如下：首先根據構件體素的參數信息進行剖分，獲取對應的頂點、法線以及顏色數組，并利用頂點數組信息計算構件的AABB包圍盒；同時，根據表1所述的規則，計算每個體素的體素占屏值，進而計算構件占屏值。其次，對構件按構件占屏值大小進行排序，將其劃分為大小構件集合，記為L與S；然后，分別對兩個構件集合依據其所掛載的構件的頂點信息獲取全局AABB包圍盒，并基于此按圖3遞歸創建八叉場景樹，記為octreeL與octreeS。

最后在一幀的裁剪繪制階段，首先對octreeL以及octreeS的中間節點與葉節點直接依據其AABB包圍盒進行視錐體裁剪測試。對通過視錐體裁剪測試的octreeS的葉子節點，計算葉節點占屏值pmax與視點至其包圍盒中心的距離的商，進而與預設的k′ tanθ的值作對比，從而判斷當前葉節點下所有構件投影至屏幕所占據的像素點數量上限，達到快速剔除與否的效果。而對于octreeL，依據其葉節點包圍盒進行視錐體裁剪獲得保守可見集，故即使在剔除octreeS所有構件的情形下，亦能通過octreeL的可見集，來最大限度地展示流程工廠模型的輪廓外觀。

所述的k′ tanθ，其獲取借助式(4)，模擬計算一定大小的構件，在一定的距離上，其投影至屏幕占用像素點數量為1×1時ktanθ的大小。并在1×1的基礎上對ktanθ進行比例縮放至k′ tanθ，即得裁剪閾值(本文k′ tanθ的取值為0.002，在屏幕分辨率為1 920×1 080的情況下，其代表的像素點數量大約為14×14，其中k′取值為0.007 5)。

2.2 算法實現

本文所述的一種基于八叉樹的大規模工廠模型細節裁剪算法，其流程包括模型讀取與構件信息初始化，場景樹建立以及一幀繪制與裁剪渲染，實現流程如圖4所示。

圖4 基本算法實現流程

2.2.1 模型讀取與構件信息初始化

模型讀取的過程，即創建構件的過程。正如前文所述，構件一般由網格體素、面片體素、多邊形體素或18種基本體素組合構成。通過讀取每個構件對應體素的參數信息，并進行相應的剖分，最終獲取渲染構件節點所需的頂點、法線以及顏色數組。

算法1 構件包圍盒初始化。

輸入：構件剖分后的頂點數組；

輸出：構件的AABB包圍盒。

1)初始化該構件的AABB包圍盒(由[(xMin, yMin, zMin) ～ (xMax, yMax, zMax)]所對應的空間區域組成，其中xMin表示x的最小值，xMax表示x的最大值，其余以此類推。minVal、maxVal表示程序可取的最小值和最大值)

(xMin, yMin, zMin) = (maxVal, maxVal, maxVal)

(xMax, yMax, zMax) = (minVal, minVal, minVal)

2)取出構件的頂點數組，對每個頂點v = (x, y, z)，計算xMin = min(x, xMin); yMin = min(y, yMin);

zMin = min(z, zMin); xMax = max(x, xMax);

yMax = max(y, yMax); zMax = max(z, zMax)

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。

圖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。

圖6 測試模型

測試模型采用管線規模達9 710根管線的某化工工廠模型以及5 736根管線的某液臘工廠模型(其形態與數據分別見圖6與表2 )，分別與主流漫游軟件PDSOFT Review，Navisworks Manage進行測試對比，其結果見表3。

表3 幾種算法的幀率對比

同時，對表3所述平臺分別采用1 942、3 884、5 826、7 768以及9 710根管線的流程工廠模型進行測試，幀率變化與管線關系如圖7所示。結果表明，該算法和現今主流漫游軟件相比幀率提升顯著，且其幀率大大高于傳統的細節裁剪算法。

再以某化工工廠模型為例，當對其進行交互與靜態操作時進行對比，結果如圖8所示。結果表明，該算法在交互過程中進行快速剔除與繪制的同時，也可完整顯示工廠模型的輪廓。

圖7 幀率與管線規模關系

綜上所述，本文所述方法，與傳統細節裁剪算法相比，其時間復雜度從O(N)降低至O(8h-1)，交互幀率可提升至少200%。其中所述N為三角面片的數量，h為八叉場景樹的高度，8h-1表示八叉樹葉節點的數量(h通常取4或5)。在幀率提升的同時，該方法可最大限度顯示流程工廠模型的整體輪廓。本文所述方法已集成至擁有自主知識產權的三維協同設計圖形平臺PDSOFT Open5D，對圖形平臺的市場競爭力與流程工廠行業的整體設計產能的提升有極大的促進作用。

圖8 某化工工廠模型繪制效果

4 結語

本文根據流程工廠模型的特征，提出一種基于八叉樹的大規模流程工廠模型細節裁剪算法。該算法充分應用模型構件體素的幾何特征以及模型整體的三維空間特征，快速估算出模型構件投影至屏幕所占據的像素點數量，進而剔除小于預設像素點數量閾值的構件，提升裁剪效率，降低后續繪制階段的負擔，從而提升繪制幀率。與傳統采用計算三角面片對應像素數量的細節裁剪算法相比，本文所述的算法直接借助空間建模的八叉樹葉子節點，對于面片規模上千萬的模型，數據處理規模可降低至原來的1/100。在提升幀率的同時，也可呈現出流程工廠模型的整體輪廓。

更進一步地，本文所述的像素點數量的度量方法，亦可應用為細節層次變化的度量準則。并且，通過設定前文所述的構件劃分權重x%的取值，可以依據現實情況，自適應調整可達到顯示控制幀率的效果。

在后續的研究中，所述的網格體素、面片體素以及多邊形體素仍需進一步考慮與選取合適的占屏值度量方法，使得該方法對所有的流程工廠模型而言，具有更高的普適性與通用性。

References)

[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.

[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.

[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.

[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.

Improvedsmallfeaturecullingforlargescaleprocessplantmodelbasedonoctree

DU Zhenlin1,2, TANG Weiqing1,2,3*, QIN Li1,2, LI Shicai3

(1.InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100190,China;2.SchoolofComputerandControlEngineering,UniversityofChineseAcademyofSciences,Beijing101408,China;3.BeijingZhongkeFulongComputerTechnologyCompanyLimited,Beijing100085,China)

To eliminate the drawbacks of traditional small feature culling algorithm which processing granularity are triangles and can’t efficiently cope with the number of vertexes and triangles up to hundreds of millions in a certain time period, an improved small feature culling algorithm for large scale process plant based on octree was proposed. Based on the component primitive characteristics and spatial characteristics of the process plant model, the value of screen for quantizing the size of component was proposed, and the established octree and the value of screen were combined to estimate the upper limit of the number of pixels, so as to quickly determine whether the component would be culled or not. The experimental results show that the proposed algorithm is simple and effective. Compared with the current popular review software after loading the factory model with 10 000 pipelines, the frame rate is increased by at least 50%, which greatly improves the platform’s fluency. Process factory industry and graphics platform as a whole to enhance the level of design has a positive meaning.

process plant model; small feature culling; octree; primitive characteristic; frame rate

2017- 03- 15;

2017- 05- 19。

杜振林(1992—)，男，福建泉州人，碩士研究生，CCF會員，主要研究方向：計算機輔助設計與圖形學； 唐衛清(1956—)，男，江蘇太倉人，研究員，博士，CCF杰出會員，主要研究方向：制造業信息化、計算機輔助設計與圖形學、計算機支持的協同計算、工業大數據及其可視化； 覃力(1987—)，男，湖北宜昌人，博士研究生，CCF會員，主要研究方向：大型軟件設計、機器學習； 李士才(1971—)，男，河北易縣人，高級工程師，博士，主要研究方向：計算機輔助設計與圖形學、軟件建模及協同設計。

1001- 9081(2017)09- 2626- 05

10.11772/j.issn.1001- 9081.2017.09.2626

TP391.41

A

DUZhenlin, born in 1992, M. S. candidate. His research interests include computer aided design, computer graphics.

TANGWeiqing, born in 1956, Ph. D. candidate, researcher. His research interests include manufacturing informatization, CAD&CG, computer aided collaborative design, visualization of industrial data.

QINLi, born in 1987, Ph. D.. His research interests include large software design, machine learning.

LIShicai, born in 1971, Ph. D., senior engineer. His research interests include CAD&CG, software modeling and collaborative design.