基于八叉樹的大規(guī)模流程工廠模型細節(jié)裁剪算法

杜振林，唐衛(wèi)清,，覃 力，李士才

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

基于八叉樹的大規(guī)模流程工廠模型細節(jié)裁剪算法

杜振林1,2，唐衛(wèi)清1,2,3*，覃 力1,2，李士才3

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

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

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

0 引言

制造業(yè)是我國國民經(jīng)濟的支柱產(chǎn)業(yè)，制造業(yè)發(fā)達與否也是衡量一國生產(chǎn)力水平高低的重要標準。而流程工業(yè)是制造業(yè)的一個重要分支，涵蓋了石油、化工、冶金等基礎(chǔ)性領(lǐng)域。隨著人類社會的不斷發(fā)展、經(jīng)濟水平的不斷提高，人們對流程工業(yè)產(chǎn)能的需求也不斷增大。為了應(yīng)對這種需求，人們不得不設(shè)計、建造更多、更大規(guī)模的流程工廠。正是在這種情況下，流程工廠設(shè)計平臺的模型處理能力及性能上限越來越受到設(shè)計人員和研究人員的關(guān)注。工廠模型數(shù)據(jù)規(guī)模增長而導(dǎo)致的圖形平臺交互幀率低下正是當(dāng)前設(shè)計平臺最為突出的問題之一，而通過適當(dāng)?shù)牟眉羲惴ㄒ蕴蕹槐匾匿秩緦ο螅涌熹秩玖鞒?，從而提高交互幀率，是解決這一問題的重要方法。

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

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

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

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

1 基本理論

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

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

圖1 18種基本體素

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

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

(1)

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

(2)

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

(3)

由式(3)可得，構(gòu)件的大小與構(gòu)件至視點距離的關(guān)系為：

(4)

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

圖2 視錐體示意圖

結(jié)合上述分析，此處給出影響構(gòu)件投影至屏幕最終占據(jù)像素點數(shù)量多少的關(guān)鍵因素“體素占屏值”“構(gòu)件占屏值”以及“葉節(jié)點占屏值”的定義。

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

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

定義3 葉節(jié)點占屏值是指該葉節(jié)點所掛載的所有構(gòu)件的構(gòu)件占屏值的最大值。

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

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

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

圖3 八叉樹

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

2 算法原理與實現(xiàn)

2.1 算法原理

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

本文所述的基于八叉樹的大規(guī)模流程工廠模型細節(jié)裁剪算法，其裁剪處理對象從三角面片轉(zhuǎn)化為一系列構(gòu)件。

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

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

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

2.2 算法實現(xiàn)

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

圖4 基本算法實現(xiàn)流程

2.2.1 模型讀取與構(gòu)件信息初始化

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

算法1 構(gòu)件包圍盒初始化。

輸入：構(gòu)件剖分后的頂點數(shù)組；

輸出：構(gòu)件的AABB包圍盒。

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

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

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

2)取出構(gòu)件的頂點數(shù)組，對每個頂點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)]。

通過剖分后的頂點數(shù)組，對構(gòu)件求取AABB包圍盒，具體見算法1。同時，按照表1所述的體素占屏值的選取規(guī)則，計算每個體素的體素占屏值，進而計算構(gòu)件的構(gòu)件占屏值pi。

獲得已初始化相關(guān)信息的構(gòu)件集合A。

2.2.2 場景樹建立

為了獲取流程工廠模型中能夠顯示工廠模型輪廓的大構(gòu)件信息，本文在2.2.1節(jié)所獲取的構(gòu)件集合A的基礎(chǔ)之上，將構(gòu)件集合依據(jù)預(yù)設(shè)的劃分占屏值再次劃分成構(gòu)件集合L與S(L表示構(gòu)件占屏值大于劃分占屏值的構(gòu)件集合，S則相反)，具體見算法2。

算法2 構(gòu)件集合L與S獲取。

輸入：構(gòu)件集合A；

輸出：構(gòu)件集合L與S。

1)對構(gòu)件集合A依據(jù)構(gòu)件占屏值pi從大到小排序；

2)設(shè)定劃分權(quán)重x%，獲取在構(gòu)件集合A中x%處的構(gòu)件對應(yīng)的構(gòu)件占屏值p(記為劃分占屏值)；

3)將構(gòu)件占屏值大于p的構(gòu)件劃分至構(gòu)件集合L，否則劃分至集合S。

對構(gòu)件集合L和S，按照算法1步驟，分別求取其對應(yīng)的AABB包圍盒l(wèi)AABBBox及sAABBBox。并依據(jù)lAABBBox以及sAABBBox，分別按預(yù)設(shè)深度hl、hs從上至下層次遞歸建立八叉樹octreeL與octreeS，見算法3。并將其根節(jié)點設(shè)為模型根節(jié)點的孩子節(jié)點，場景圖見圖5。

圖5 場景樹

算法3 場景樹建立。

輸入：構(gòu)件集合L與S；

輸出：場景樹。

1)預(yù)設(shè)octreeL、octreeS的八叉樹深度hl、hs。

2)層次遞歸創(chuàng)建八叉樹octreeL。

①對lAABBBox按圖3進行遞歸層次創(chuàng)建八叉樹，深度為hl。

②將構(gòu)件集合L中的構(gòu)件依據(jù)包圍盒中心設(shè)置為octreeL對應(yīng)葉節(jié)點的孩子節(jié)點。

3)層次遞歸創(chuàng)建八叉樹octreeS。

①對sAABBBox按圖3進行遞歸層次創(chuàng)建八叉樹，深度為hs。

②將構(gòu)件集合S中的構(gòu)件依據(jù)包圍盒中心設(shè)置為octreeS對應(yīng)葉節(jié)點的孩子節(jié)點。

③計算octreeS每個葉節(jié)點的葉節(jié)點占屏值pmax。

4)將octreeL與octreeS的根節(jié)點設(shè)置為場景節(jié)點的孩子節(jié)點。

2.2.3 一幀繪制與裁剪渲染

一幀繪制與裁剪渲染，包括對octreeL與octreeS葉節(jié)點進行相應(yīng)的視錐體裁剪與細節(jié)裁剪操作，其實現(xiàn)流程見算法4。

算法4 一幀繪制與裁剪渲染。

輸入：場景樹；

輸出：模型的一幀渲染及其交互。

1)一幀渲染開始。

2)若遍歷的節(jié)點為八叉樹的中間節(jié)點或葉節(jié)點，則直接進行視錐體與包圍盒測試，不在視錐體內(nèi)則直接剔除，否則遞歸遍歷或繪制。

3)若遍歷的節(jié)點為octreeS的葉節(jié)點，且通過視錐體裁剪測試，則：

①計算當(dāng)前葉節(jié)點的葉節(jié)點占屏值pmax與視點至其包圍盒中心距離的商t；

②比較預(yù)設(shè)的k′ tanθ與t的大小關(guān)系：若k′ tanθ>t，表示該葉節(jié)點下最大構(gòu)件投影至屏幕像素點數(shù)量足夠少，直接剔除；否則，進行繪制，并遍歷下一節(jié)點。

4)可選的，也可采用3)①～3)②所述的方法，將其作為細節(jié)層次變化的度量方式，對構(gòu)件實施細節(jié)層次(Level of Detail, LOD)繪制。

5)若節(jié)點遍歷完畢，則跳轉(zhuǎn)至1)開始下一幀的渲染；若程序關(guān)閉，則渲染結(jié)束。

3 實驗結(jié)果與分析

本文所采用的測試機器配置為Windows 7 64 b操作系統(tǒng)，處理器為Intel Core i5-3470 CPU @ 3.20 GHz (4CPU),～3.60 GHz，內(nèi)存為16 GB，顯卡為Nvidia GeForce GT 520，屏幕分辨率為1 920×1 080。算法集成測試平臺為PDSOFT Open5D，幀率采集軟件使用fraps(Version 3.4.7)。同時，對于octreeL以及octreeS的八叉樹深度，hl，hs均設(shè)為4。

圖6 測試模型

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

表3 幾種算法的幀率對比

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

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

圖7 幀率與管線規(guī)模關(guān)系

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

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

4 結(jié)語

本文根據(jù)流程工廠模型的特征，提出一種基于八叉樹的大規(guī)模流程工廠模型細節(jié)裁剪算法。該算法充分應(yīng)用模型構(gòu)件體素的幾何特征以及模型整體的三維空間特征，快速估算出模型構(gòu)件投影至屏幕所占據(jù)的像素點數(shù)量，進而剔除小于預(yù)設(shè)像素點數(shù)量閾值的構(gòu)件，提升裁剪效率，降低后續(xù)繪制階段的負擔(dān)，從而提升繪制幀率。與傳統(tǒng)采用計算三角面片對應(yīng)像素數(shù)量的細節(jié)裁剪算法相比，本文所述的算法直接借助空間建模的八叉樹葉子節(jié)點，對于面片規(guī)模上千萬的模型，數(shù)據(jù)處理規(guī)?？山档椭猎瓉淼?/100。在提升幀率的同時，也可呈現(xiàn)出流程工廠模型的整體輪廓。

更進一步地，本文所述的像素點數(shù)量的度量方法，亦可應(yīng)用為細節(jié)層次變化的度量準則。并且，通過設(shè)定前文所述的構(gòu)件劃分權(quán)重x%的取值，可以依據(jù)現(xiàn)實情況，自適應(yīng)調(diào)整可達到顯示控制幀率的效果。

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

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.交互式計算機圖形學(xué):基于OpenGL的自頂向下方法[M].張榮華,姜小磊,宋雨，譯.北京：電子工業(yè)出版社,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] 許云杰,胡事民.基于層次細節(jié)模型的遮擋裁剪算法[J].中國圖象圖形學(xué)報,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會員，主要研究方向：計算機輔助設(shè)計與圖形學(xué)； 唐衛(wèi)清(1956—)，男，江蘇太倉人，研究員，博士，CCF杰出會員，主要研究方向：制造業(yè)信息化、計算機輔助設(shè)計與圖形學(xué)、計算機支持的協(xié)同計算、工業(yè)大數(shù)據(jù)及其可視化； 覃力(1987—)，男，湖北宜昌人，博士研究生，CCF會員，主要研究方向：大型軟件設(shè)計、機器學(xué)習(xí)； 李士才(1971—)，男，河北易縣人，高級工程師，博士，主要研究方向：計算機輔助設(shè)計與圖形學(xué)、軟件建模及協(xié)同設(shè)計。

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.