面向移動終端的三維CAD模型面片生成方法*

蔡 強，許 杰，李海生，李 楠，曹 健

1.北京工商大學 食品安全大數據技術北京市重點實驗室，北京 100048 2.北京工商大學 材料與機械工程學院，北京 100048

面向移動終端的三維CAD模型面片生成方法*

蔡 強1+，許 杰1，李海生1，李 楠2，曹 健1

1.北京工商大學 食品安全大數據技術北京市重點實驗室，北京 100048 2.北京工商大學 材料與機械工程學院，北京 100048

CAI Qiang,XU Jie,LI Haisheng,et al.3D CAD model patch generation method in mobile terminal.Journal of Frontiers of Computer Science and Technology,2017,11(6)：972-979.

移動終端；三維CAD模型；面片生成；分類樹；規模系數

1 引言

隨著計算機技術的快速發展，智能手機、平板電腦和可穿戴設備等移動終端成為一種重要的計算載體，其便于攜帶和適于多種工作環境的優點在很多行業得到了應用。同時，人們對移動終端的圖形交互體驗有了更多的需求，三維場景的廣泛應用由PC端開始轉向移動終端設備。尤其在工業設計領域，一個復雜的三維場景包含的對象體不僅范圍廣泛，種類繁多，大部分還具有復雜的幾何結構和形態描述，因此構建的模型數據量不但巨大，而且還占用很多的內存空間，這就影響了視覺效果和計算機處理速度[1]。而且與高端的圖形工作站和桌面PC相比，移動終端的各種資源極為有限，如CPU的主頻低且大多數浮點計算能力差，存儲小等，三維模型的高效繪制在移動終端上的研究面臨更多的難點[2]。因此基于移動終端的三維模型面片生成技術用于提高移動終端三維模型顯示效率，已成為近年來計算機輔助設計與制造領域一個新的研究熱點。

表示三維模型的最基本單位稱為頂點，它代表三維空間中的一個點。兩個頂點連接成線段，3個不在同一條直線的頂點構成一個三角形，也就能表示一個面。因此，通過頂點數組定義點、線段、三角形或四邊形，可以構建簡單的二維圖形，而不同的二維圖形則可以構成復雜的三維立體模型[3]。在圖形顯示系統中一般采用三角面片[4]表示圖形，通過面片的集合來表示物體表面，能夠簡單有效地用于顯示系統。因此本文使用基于三角面片的模型生成方法。

基于此，本文針對移動終端的特點，在利用CAD模型中的層次類型和圖形表達信息[5]的基礎上，提出了基于規模估算的三維模型面片生成方法。該方法以CAD模型的層次類型和圖形表達的關系數據為信息輸入源，首先根據數據中的圖形、拓撲和分類信息構建包含整個模型圖形信息的圖形分類樹[6]，葉子節點就是表示模型最小單元的體元，每個體元包含生成三角面片所需的參數信息；其次，在移動終端實現交互方法，以便選取所要顯示的模型節點，計算出模型規模系數；最后，根據規模系數，生成所要顯示模型的三角面片集來實現三維模型的面片構建。

2 基本概念和思路

2.1 基本概念

本文充分利用三維CAD模型對象的層次類型和圖形表達數據來進行三維面片的生成，模型對象按其工程意義可分為若干大類，每個大類又可細分為若干子類，子類還可以繼續劃分子類，從而形成一個樹形層次分類結構。

定義1類型層次關系RC。類型層次關系為三元關系，屬性CID是其唯一ID，屬性Name是該分類的名稱，屬性ParentCID是其父分類的ID。表示如下：

定義2模型對象關系RO。模型對象關系為二元關系，屬性OID表示其唯一ID，屬性CID表示其所屬的分類ID。表示如下：

定義3圖形描述關系RG。圖形描述關系為二元關系，屬性OID是對象ID，屬性Data是對象包含的所有體元信息。表示如下：

一個模型對象的三維圖形由若干體元組成，體元之間沒有布爾運算，只是簡單堆積。定義G為基本體元集[7]，G={Cylinder（圓柱），Scylinder（斜截圓柱），Prism（多棱柱），Econe（偏心圓臺），Concone（同心圓臺），Squcir（天圓地方），Squcone（矩形斷面臺），Box（長方體），Torus（圓形斷面圓環），Squtorus（矩形斷面圓環），Sphere（球），Wedge（直角楔形體），Saddle（馬鞍形），Oval（橢球封頭）}；每個體元包含生成三角面片所需的參數信息[7-8]，以Sphere為例，該體元圖形描述為Sphere:〈Center(圓心)〉，〈Radius(半徑)〉。

2.2 方法概述

針對移動終端的三維模型顯示存在的問題，首先以CAD模型的3種關系數據RC、RO和RG為信息輸入源，根據數據中的圖形、拓撲和分類信息[9]構建包含整個模型圖形信息的圖形分類樹，葉子節點就是表示模型最小單元的體元，每個體元包含生成三角面片所需的參數信息；在移動終端實現交互方法，以便選取所要顯示的模型節點，計算出模型規模系數；然后，根據規模系數，生成所要顯示模型的三角面片集來實現三維模型面片的生成。具體步驟如下。

步驟1解析CAD模型文件，構建模型圖形信息分類樹。依據類型層次關系RC建立類型層次結構；依據模型對象關系RO將對象分類；依據圖形描述關系RG將體元信息作為葉子結構。

步驟2在移動終端構建良好的交互界面，交互地選取所要瀏覽的模型節點，估算所要顯示的模型節點的規模系數。

步驟3根據模型規模系數，選擇不同體元的三角面片生成策略，生成頂點數組。

3 圖形分類樹的構建

3.1 類型層次結構

CAD模型通常包含多種類型信息，具有層次結構。以CAD模型的3種關系數據RC、RO和RG為輸入源，通過對其中類型層次關系RC的解析能夠建立一種樹形結構來表示這種層次結構。根據RC的定義，按如下步驟生成一些中間關系來體現類型層次結構。

步驟1求根節點關系。在類型層次關系RC中，父類型編號等于類型編號的元組變量，即為圖形分類樹的根節點。

式中，Rroot為根節點關系；t[1]表示元組變量t的屬性CID；t[3]表示元組變量t的屬性ParentCID。因為根節點的唯一性，所以Rroot度數為1。

步驟2求一級類型節點關系。在RC中，父類型編號等于根節點類型編號的元組變量為根節點的子節點，即一級類型節點。

步驟3求二級類型節點關系。在RC中，父類型編號等于一級類型節點編號的元組變量為一級類型節點的子節點，即二級類型節點。

式中，RC2i為ti一級類型節點的二級類型關系。

基于上述步驟，可以構建圖形分類樹的類型層次節點。其中，根節點root為Rroot唯一的元組變量；一級類型節點的所有元組變量；一級類型節點Ci對應的二級類型節點的所有元組變量。

表1中的示例數據采取上述算法構建的樹如圖1所示。

Table 1 Type hierarchy sample data表1 類型層次示例數據

Fig.1 Type hierarchy structure tree of sample data圖1 示例數據類型層級結構樹

3.2 模型對象分類

CAD模型中各類型節點又包含了若干模型對象[10]，本文基于上面構建的樹來將模型對象分類，進一步構建圖形分類樹。根據模型對象關系RO的定義，依次對二級類型層次關系值為的度）進行對象分類：

式中，ROi,j表示中每一個元組變量tj的對象關系。t[2]為RO的元組變量t的屬性CID。

基于此，就可以構建圖形分類樹的對象節點，即二級類型節點Ci,j的對象節點Oi,j,k為ROi,j的所有元組變量。

3.3 圖形信息解析

對象為在CAD模型設計中，對于工程而言有意義的最小單位[11]，如一段管子、一個設備、一個元件等。一個模型對象的三維圖形由若干體元組成，體元之間沒有布爾運算，只是簡單堆積。

根據圖形描述關系RG的定義，依次對模型對象關系

根據上述算法，構建了如圖2所示的圖形分類樹。

Fig.2 Structure of shape classification tree圖2 圖形分類樹結構圖

4 模型節點規模的估算

4.1 交互選取模型節點

為了解決大規模三維模型在移動終端顯示存在的難點，本文特地對CAD模型構建了圖形分類樹，在移動終端可視化該圖形分類樹，可視化方式是實現4個列表，分別是一級層次類型列表、二級層次類型列表、模型對象列表和體元列表。其中，一級層次類型列表列舉圖形分類樹的一級層次類型節點Ci；構建了良好的交互方式[12]來選取任意節點，當選取任意Ci之后，二級層次類型列表列舉所選取的Ci節點的所有子節點Ci,j；當選取任意Ci,j之后,模型對象列表列舉所選取的Ci,j節點的所有子節點Oi,j,k；當選取任意Oi,j,k之后，最后的體元列表列舉所選取的Oi,j,k節點的所有體元信息。

根據上述的移動終端模型節點選取方式，能夠高效地選取需要顯示的局部三維模型（細節），并從圖形分類樹中獲取該節點所有子節點的圖形信息，這樣便能構建表示三維模型所需的三角面片，使注意力集中在模型的細節上。

4.2 規模系數計算

不同體元在相同顯示精度的情況下，構成體元的三角面片數量差別很大，如長方體體元在任意顯示精度下都可以使用12個三角面片來表示；在圓顯示精度為圓周16等分時，圓柱體元需要64個三角面片，球體元需要240個三角面片。而且，當顯示精度越高，不同體元的三角面片數量差異會越來越大。因此，根據構建體元面片的實際情況，使用對不同體元加權的方式來計算出模型的體元總量：

其中，k表示不同體元，如設k=1表示圓柱，k=2表示斜截圓柱，以此類推，n=14；num(Ok)表示所選對象節點Ok所包含的體元k的數量；wk為體元k的體元權重。

至此，可以用N來表示所選模型節點的體元總量。對于在移動終端三角面片顯示存在的效率問題，并不能隨意地對任意體元總量實現高精度的顯示，因此引入模型規模系數來衡量模型節點的面片規模，從而判斷實際顯示所需的精度級別。面片規模越大，顯示精度越低；面片規模越小，顯示精度越高。采用如下公式計算規模系數：

其中，N是所選取模型節點的體元總量，在交互選擇需要瀏覽的對象時計算出N；nMin為可以顯示的模型最少體元總量，這里取1；nMax為整個模型包含的體元總量，在構建圖形分類樹時得到；λ為調整指數，因為通過前面的標準化可以得到一個區間在(0,1)之間的實數，但是當面片數很小時，面片的緩慢增加對顯示性能影響不大，而當面片數很大時，面片的增加對顯示性能的影響就明顯增大，因此引入λ調整規模系數，使它滿足這種特性。

這樣，規模系數的范圍在(0,1)之間，用來度量模型節點的規模，規模系數越大，模型規模越大。

5 模型面片的生成策略

三維模型的主流表示方法就是用三角面片來表示三維空間的面，三角面片用3個三維空間的點依據規定好的順序（逆時針或順時針）來表示的。前文在移動終端中選取了所要顯示的模型節點，并依上述算法得到了模型規模系數，據此動態地計算所需顯示的三角面片。本文使用頂點數組[13]的方式來構建三角面片，每3個頂點以逆時針的方式表示一個三角面片。

如圖3所示，圓周上分為8個頂點，其中頂點V1、V2、V3和V4組成了面片F1和F2。PX、PY、PZ、NX、NY、NZ、R、G、B、A分別表示頂點三維空間坐標、頂點法向量和頂點顏色，坐標用來確定三維空間位置，法向量和顏色用來添加環境光照，這樣顯示的效果會接近自然環境。

Fig.3 Structure of triangular patch vertex array圖3 三角面片頂點數組結構

得到所選模型節點的體元信息后，據此還需要判斷顯示精度來計算如圖3的頂點數組。不同體元在不同顯示精度的情況下構建面片的策略都略有不同，其中最主要的是包含圓的情況，如圓柱、斜截圓柱、偏心圓臺、同心圓臺、天圓地方、圓形斷面圓環、矩形斷面圓環、球、橢球封頭這幾種體元都包含圓形。因此，以圓為例，不同的顯示精度本質就是圓周需要用多少面片來表示，圓周需要的面片數計算如下：

其中，s為規模系數；cMax為顯示最細致的情況圓上頂點數，根據實際情況，取值36（即將圓36等分）。

在根據規模系數計算出模型的頂點數組之后，需要在移動終端借助三維圖形接口顯示出模型，并添加交互方式實現模型的旋轉、縮放和平移，將模型進行實用。

Table 2 Patches number of some model nodes表2 部分模型節點面片數

6 實驗及結果分析

上述基于分類樹的三維模型面片生成方法，用于提高在移動終端顯示三維模型的效率，能夠有效地將注意力集中在關注的模型細節上。根據某公司對旗下三維模型產品移動化的需求，筆者自主設計并開發了“基于分類樹的三維模型顯示系統”。開發所用移動設備是Apple的iPad mini2，A7 CPU，1 GB內存；使用的3D引擎是OpenGL ES[14]。因為在PC領域專業的圖形程序接口有兩種標準的3D API：OpenGL和DirectX。一般主流的游戲和顯卡都支持這兩種渲染方式，DirectX在Windows平臺上有很大的優勢，但是OpenGL具有更好的跨平臺性。為了滿足嵌入式設備對3D繪圖的要求，Khronos公司對標準的OpenGL系統進行了維護和改動，形成一套為手持和嵌入式系統設計的3D引擎API，即OpenGL ES。

以文獻[2]中的某流程工廠模型（本質是關系型數據庫文件[15]，三維CAD模型所包含的圖形、拓撲和分類信息以數據表的形式儲存）為例，對本文基于分類樹的三維CAD模型面片生成方法在上訴系統進行實驗。為了進行比較，選取不同模型節點，采用上訴算法進行繪制，得到的三角面片數量如表2所示，其中原面片數指模型以普通精度構建所需面片數。

從表2中可以看出，對于模型規模較大時，本文方法大大降低了模型面片數量，以實現其在移動終端的高效顯示；當模型規模較小時，對移動終端的渲染壓力較少，因此增加面片的數量以提高顯示精度。

同時，在相同的漫游路徑下，采用不同方法對該模型進行繪制，得到的繪制幀速如圖4所示。可以從圖中看出，本文方法雖然在模型規模較小時，繪制幀速低于文獻[7]，但在規模較大時，繪制的幀速滿足瀏覽的實時性。重要的是，本文方法占用內存空間較其他方法少很多，充分考慮了移動終端內存小的特性，而文獻[7]是使用多分辨率的繪制方法，極大地增加了內存的占用。

Fig.4 Drawing frame of different methods圖4 不同方法的繪制幀速

在該系統中，用戶可以輕松地選取如圖5所示的圖形分類樹的模型節點，并查看模型的圖形信息和工程信息，同時可以進行交互瀏覽。其中，圖5（a）所示的運行界面是本文集加載解析文件和可視化圖形分類樹功能的主界面，用戶可清楚明了地查看模型組成結構，包括一級類型節點、二級類型節點、對象節點和體元節點；圖5（b）所示為模型二級類型節點“管線-13S-9003-H”的顯示界面。

7 結束語

Fig.5 Screenshots of running system圖5 系統運行截圖

本文提出了一種基于分類樹的移動終端三維CAD模型面片生成方法。依據模型包含的層次類型和圖形表達信息，根據數據中的圖形、拓撲和分類信息構建包含整個模型圖形信息的圖形分類樹。圖形分類樹能夠較好地體現CAD模型的層次結構以及構成層次結構的圖形對象信息，這些圖形信息存儲在作為葉子節點的體元中；在移動終端實現三維模型顯示時，通過友好的交互方式選取所要顯示的模型節點，計算出模型規模系數；最后，通過規模系數，選擇不同體元三角面片生成策略來實現三維模型面片的生成。實現的顯示效果表明，本文方法較好地解決了由于三維模型信息量巨大，信息結構復雜的特點導致的移動終端三維模型瀏覽效果不理想的問題，使用戶關注于模型的具體細節。

下一步工作將針對模型二義性進行模型結構的優化。二義性是指某個模型可由多種方法堆積而成，比如長方體，可由一個長方體體元構造，也可由兩個小的長方體體元構造。以此達到減少圖元數目的目的，從另一個角度實現對模型顯示精度的控制。

[1]Olatunji O A,Sher W.Estimating in geometric 3D CAD[J]. Journal of Financial Management of Property and Construction,2015,20(1):24-49.

[2]Su Zhiyong,Tang Weiqing,Li Weiqing,et al.A fast approach for constructing hierarchical levels of details of dy-namic process plant model[J].Journal of Computer-Aided Design &Computer Graphics,2008,20(8):1038-1046.

[3]Huang Xiaofeng,Song Jinyu,Yu Chenghai.Three-dimensional model drawing in mobile platform based on OpenGL ES[J]. Industrial Control Computer,2013,26(1):60-62.

[4]Yue Liting,Yu Ming,Yu Yang,et al.3D reconstruction algorithm based on facet[J].Computer Engineering,2012,38 (14):199-202.

[5]Su Zhiyong,Xia Ming,Li Weiqing,et al.Design review oriented model simplification for collaborative process plant CAD[C]//Proceedings of the 7th International Conference on Virtual-Reality Continuum and Its Applications in Industry,Singapore,Dec 8-9,2008.New York:ACM,2008:1-6.

[6]Minne L,Eslami S,Keizer N D,et al.Statistical process control for validating a classification tree model for predicting mortality—a novel approach towards temporal validation[J].Journal of Biomedical Informatics,2012,45(1): 37-44.

[7]Zhou Jian,Tang Weiqing,Zhu Yaoqin,et al.Multi-resolution rendering approach of large-scale process plant models based on programmable graphics pipeline[J].Journal of Image and Graphics,2012,17(3):426-434.

[8]Wen Rui,Tang Weiqing,Su Zhiyong,et al.Edit distance based partial retrieval algorithm for large scale process plant models[J].Computer Integrated Manufacturing Systems,2015,21(12):3349-3355.

[9]Nyamsuren P,Lee S H,Kim S.A Web-based revision control framework for 3D CAD model data[J].International Journal of Precision Engineering&Manufacturing,2013, 14(10):1797-1803.

[10]Nie Weizhi,Li Xixi,Liu Anan,et al.3D object retrieval based on Spatial+LDA model[J].Multimedia Tools&Applications,2015:1-14.

[11]Bosché F.Automated recognition of 3D CAD model objects in laser scans and calculation of as-built dimensions for dimensional compliance control in construction[J].Advanced Engineering Informatics,2010,24(1):107-118.

[12]Lee J,Kim T,Lee T,et al.Bouncing animation of a lock mode screen in a mobile communication terminal:US,US20110028186[P].2011.

[13]Shreiner D.OpenGL?programming guide:the official guide to learning OpenGL?,Versions 3.0 and 3.1[M].[S.l.]: Addison-Wesley Professional,2009.

[14]Sellers G,Wright R S,Haemel N.OpenGL SuperBible[M]. Amsterdam:Addison-Wesley Longman,2013.

[15]Zhu Longxian.The analysis and design of SQLite database encryption[J].Electronic Design Engineering,2014,22 (16):191-193.

附中文參考文獻：

[2]蘇智勇,唐衛清,李蔚清,等.面向動態流程工廠模型的快速分層層次細節法[J].計算機輔助設計與圖形學報,2008, 20(8):1038-1046.

[3]黃小鳳,宋瑾鈺,俞成海.基于OpenGL ES的移動平臺的三維模型繪制[J].工業控制計算機,2013,26(1):60-62.

[4]岳立廷,于明,于洋,等.一種基于面片的三維重建算法[J].計算機工程,2012,38(14):199-202.

[7]周劍,唐衛清,朱耀琴,等.基于可編程圖形管線的大規模流程工廠模型多分辨率繪制方法[J].中國圖象圖形學報, 2012,17(3):426-434.

[8]溫蕊,唐衛清,蘇智勇.基于編輯距離的大規模流程工廠模型局部檢索算法[J].計算機集成制造系統,2015,21(12): 3349-3355.

[15]褚龍現.SQLite數據庫加密的分析與設計[J].電子設計工程,2014,22(16):191-193.

蔡強（1969—），男，重慶永川人，2003年于北京航空航天大學計算機圖形學專業獲得博士學位，現為北京工商大學計算機與信息工程學院教授、碩士生導師，CCF高級會員，主要研究領域為計算幾何，可視化等。

XU Jie was born in 1991.He is an M.S.candidate at Beijing Technology and Business University.His research interest is computer graphics.

許杰（1991—），男，四川汶川人，北京工商大學碩士研究生，主要研究領域為計算機圖形學。

LI Haisheng was born in 1974.He received the Ph.D.degree in computer graphics from Beihang University in 2002.Now he is a professor and M.S.supervisor at Beijing Technology and Business University,and the senior member of CCF.His research interests include computer graphics and scientific visualization,etc.

李海生（1974—），男，山東寧津人，2002年于北京航空航天大學計算機圖形學專業獲得博士學位，現為北京工商大學計算機與信息工程學院教授、碩士生導師，CCF高級會員，主要研究領域為計算機圖形學，可視化等。

LI Nan was born in 1979.He received the Ph.D.degree in mechanical design and theory from Beijing Jiaotong University in 2010.Now he is an associate professor at School of Materials Science and Mechanical Engineering,Beijing Technology and Business University.His research interests include design methodology,digital design and manufacturing,etc.

李楠（1979—），男，北京人，2010年于北京交通大學獲得博士學位，現為北京工商大學材料與機械工程學院副教授，主要研究領域為設計方法學，數字化設計與制造等。

CAO Jian was born in 1982.He received the Ph.D.degree from Beijing Institute of Technology in 2010.Now he is an associate professor at School of Computer and Information Engineering,Beijing Technology and Business University,and the member of CCF.His research interests include image processing and pattern recognition,etc.

曹健（1982—），男，山東臨沂人，2010年于北京理工大學獲得博士學位，現為北京工商大學計算機與信息工程學院副教授，CCF會員，主要研究領域為圖像處理，模式識別等。

3D CAD Model Patch Generation Method in Mobile Terminal*

CAI Qiang1+,XU Jie1,LI Haisheng1,LI Nan2,CAO Jian1
1.Beijing Key Laboratory of Big Data Technology for Food Safety,Beijing Technology and Business University, Beijing 100048,China
2.School of Materials Science and Mechanical Engineering,Beijing Technology and Business University,Beijing 100048,China
+Corresponding author:E-mail:caiq@th.btbu.edu.cn

To improve the display efficiency in the mobile terminal and the display accuracy of model detail,this paper proposes a novel algorithm for 3D CAD model patch generation based on type hierarchy and object graph element. By extracting the database information such as the type and shape attributes of models,3D CAD models are represented by shape classification tree.The scale coefficient is estimated by 0-1 normalization method for classification tree node of interactive selection.After estimating the scale coefficient,the display accuracy of the model is confirmed and 3D CAD model patch is generated.Finally,this paper proposes a 3D CAD model display system in mobile terminal,and carries out the experiments on 3D CAD model patch generation.The experimental results prove the feasibility and effectiveness of this 3D CAD model patch generation method.

mobile terminal;3D CAD model;patch generation;classification tree;scale coefficient

was born in 1969.He

the Ph.D.degree in computer graphics from Beihang University in 2003. Now he is a professor and M.S.supervisor at Beijing Technology and Business University,and the senior member of CCF.His research interests include computational geometry and scientific visualization,etc.

A

TP391

*The National Natural Science Foundation of China under Grant No.51405005(國家自然科學基金);the Natural Science Foundation of Beijing under Grant No.4162019(北京市自然科學基金);the General Project of Science and Technology Development Plans of Beijing Municipal Education Commission under Grant No.SQKM201610011010(北京市教委科研計劃一般項目).

Received 2016-04,Accepted 2016-06.

CNKI網絡優先出版:2016-06-02,http://www.cnki.net/kcms/detail/11.5602.TP.20160602.1144.008.html

摘要：為提高三維CAD模型在移動終端的顯示效率，提高模型細節的顯示精度，提出了一種基于類型層次結構及對象體元的三維CAD模型面片生成方法。依據模型的數據庫表示形式，抽取其必要的類型和圖形信息，將三維CAD模型用圖形分類樹表示；對交互選擇的分類樹節點，使用基于離差標準化的方法估算所選節點的模型規模系數；依據規模系數確定模型的顯示精度，以此進行三維CAD模型面片的生成。在移動終端開發了三維CAD顯示系統并進行了三維CAD模型面片生成實驗，通過實驗證明了所提三維CAD模型面片生成方法的可行性和有效性。