基于OpenGL的邦寶模型積木分析系統(tǒng)設計與實現(xiàn)

張承鈿 趙靜

摘 要：由于傳統(tǒng)單憑經驗使用插座式積木搭建大型場景模型時會出現(xiàn)費時費力，無法提前統(tǒng)計成本等難題，所以急需開發(fā)出一個積木智能搭建系統(tǒng)。邦寶模型積木分析系統(tǒng)正是應企業(yè)需求開發(fā)，涉及到智能選擇不同形狀的積木來完成每一層的鋪設、上下層交叉鋪設、模型不同位置不同染色、減少零碎顆粒等要求，針對這種情況，提出了基于OpenGL技術，設計出相應的算法。本文從工程應用的角度出發(fā)，簡要介紹了3DS文件格式，系統(tǒng)用到的開發(fā)平臺及OpenGL技術，整個系統(tǒng)的結構總框架及功能，基于掃描法的柵格化算法、單層積木鋪設算法及上下層粘連性檢驗算法。在此基礎上實現(xiàn)了從3D模型文件導入、模型調整、切片分層、顆粒化到輸出積木搭建方案的全自動化。

關鍵詞：積木;3D模型;OpenGL

0 引言

隨著當今時代計算機技術的突飛猛進，三維圖形技術在建筑虛擬、場景漫游、虛擬教育、3D游戲等各方面的應用越來越廣泛。同時各種3D模擬積木軟件也得到迅猛的發(fā)展，目前國內外應用較多的軟件有Lego Digital Designer、MLCad、LDView、LPub等，雖然這些都是非常優(yōu)秀的3D模擬積木軟件，但它們并沒有一個軟件能徹底解決從三維模型導入、模型調整、切片分層、顆?；捷敵龇e木搭建方案的全自動化。

OpenGL是一個功能強大的三維圖形開發(fā)接口，由于它方便而強大的三維圖形的繪制功能，并具有可靠性高、可擴展性、可伸縮性、容易使用、靈活性和可移植性等優(yōu)點，因此應用OpenGL開發(fā)技術能夠極大地提高開發(fā)效率。盡管很多文獻[1-4]介紹了利用OpenGL技術對3DS模型數(shù)據(jù)進行讀取、顯示和控制的方法，但大多數(shù)只涉及到基本的靜態(tài)3DS模型數(shù)據(jù)的使用，并沒有對動態(tài)數(shù)據(jù)進行處理。本文基于OpenGL技術對邦寶模型積木分析系統(tǒng)進行了研究，通過這個系統(tǒng)，我們可以讀取出3DS模型文件并對其進行顯示控制，然后通過切片、顆?；纫幌盗胁僮饔嬎愠鲈谑褂冒顚毣静考罱ㄒ粋€模型時所需要的部件種類、個數(shù)及每層的積木搭建排列，進一步計算出整個模型所用積木的總重量及總價格。

1 3DS文件格式簡介

3DS是Autodesk公司存儲3D模型數(shù)據(jù)的一種文件格式。

3DS文件結構由許多塊組成，每個塊由信息類別和下一個塊的相對位置兩部分組成，其中塊的信息類別用ID來標識。由于每個塊指出了下一個塊的相對于該塊起始位置的偏移字節(jié)數(shù)，這樣即使你不明白這個塊的含義，也可以很容易地忽略它。與許多文件格式一樣，3DS二進制文件中的數(shù)據(jù)也是按低位在前、高位在后的方式組織的。例如，兩個十六進制字節(jié)0x4A5C組成的整型數(shù)，表明5C是高位字節(jié)，4A是低位字節(jié)[5]。

3DS文件中塊的前兩項信息分別是塊的ID和塊的長度，其中塊的ID是一個整型數(shù)，而塊的長度是一個塊相對于該塊的字節(jié)偏移量，是一個長整型數(shù)。3DS文件中每個塊是一個層次結構，不同類型的塊具有不同的層次結構。每一個3DS文件的開頭都是由一個根塊構成，它包含了整個文件，其ID是0x4D4D。根塊內的塊稱為主塊，主塊有3D編輯程序塊和關鍵幀塊兩種類型。主塊后面是該主塊所包括的子塊，而3D編輯程序塊是物體的形體數(shù)據(jù)定義的開始。3D編輯程序塊的子塊包括材質列表塊、物體塊等，而物體塊又包含了網格塊、亮度信息塊、相機參數(shù)塊等。其中網格塊包括位置信息塊、頂點列表塊、面信息塊等;關鍵幀塊定義關鍵幀的信息。3DS文件這種復雜的塊層次結構的優(yōu)勢在于即使我們并不知道每一個塊的具體含義，在程序中讀取3DS文件類型的模型時，完全可以忽略掉那些不感興趣或不需要的塊信息，僅讀取所需要的塊。

2 開發(fā)平臺和技術

2.1 使用C#編程語言

C#是一種完全建立在Microsoft.NET框架平臺上的高級編程語言，它幾乎集中了所有關于軟件開發(fā)和軟件工程研究的最新成果，如面向對象、類型安全等。C#充分利用了.NET框架的優(yōu)點，是開發(fā).NET框架應用程序最好的語言之一。與VC++相比，C#的程序調試更加容易，語法更加簡潔，且可以更加快速地開發(fā)應用程序。把C#和OpenGL結合起來開發(fā)3D圖形程序和軟件，將顯著提高開發(fā)效率[6]。

2.2 使用OpenGL技術

OpenGL的英文全稱是“Open Graphics Library”，即“開放性圖形庫”，它是計算機工業(yè)標準3D應用程序接口，是一個功能強大，調用方便的底層3D圖形庫。作為圖形硬件的軟件接口，OpenGL由幾百個指令或函數(shù)組成，這些指令允許用戶說明二維幾何對象或三維幾何對象，允許用戶對對象實施操作以便把這些對象著色到幀存上。OpenGL作為一個性能優(yōu)越的圖形應用程序設計界面（API），適用于廣泛的計算機環(huán)境。OpenGL是一套底層三維圖形API，之所以稱之為底層API，是因為它沒有提供幾何實體圖元，不能直接用以描述場景。但通過一些轉換程序，可以很方便的將AutoCAD、3DS等圖形設計軟件制作的3DS模型文件轉換成OpenGL的頂點數(shù)據(jù)。由于OpenGL提供了清晰明了的圖形函數(shù)，所以不要求開發(fā)者把三維物體模型的數(shù)據(jù)寫成固定的數(shù)據(jù)格式，開發(fā)者不但可以直接使用自己的數(shù)據(jù)，而且可以利用其它不同格式的數(shù)據(jù)源，這種靈活性極大地節(jié)省了開發(fā)時間，提高了開發(fā)效率。因此我們選擇使用OpenGL技術進行開發(fā)。

2.3 在C#中使用Tao框架實現(xiàn)OpenGL建模技術

由于OpenGL的廣泛應用，它已經成為了一個工業(yè)標準。

目前雖然有很多軟件開發(fā)商提供的程序設計語言都提供了對開發(fā)基于OpenGL應用軟件的支持，如Visual C++，C++builder等。但是并沒有提供在C#中開發(fā)OpenGL的標準和規(guī)范的方法，而且，在.NET框架中也沒有提供0penGL API的接口。目前在C#中可以通過CsGL等第三方軟件進行OpenGL建模的技術，也可以基于Tao技術，因為Tao Framework提供了許多基于.NET和Mono的庫，它是由美國華盛頓大學分布式對象計算組織開發(fā)的開放源碼的CORBA（通用對象請求代理體系結構）產品，它實現(xiàn)了C0RBA2.6規(guī)范中的說明。因此，我們利用Tao框架實現(xiàn)在C#中進行OpenGL建模的方法[7]。

2.4 使用SharpGL擴展庫

SharpGL是C#對OpenGL庫的封裝，是一個方便我們在Windows窗體中和WPF中使用OpenGL的擴展庫，它能夠設置一個強大的場景圖和Visual Studio模板。SharpGL擴展庫包裝了所有當前的OpenGL函數(shù)，所有主要的擴展和一套豐富的先進功能的對象，并且能夠將代碼移植到其它的平臺中，所以我們使用它很容易開發(fā)出3D圖形程序。它的命名空間包括：

①SharpGL：包含OpenGL的主要對象，這個對象封裝了所有的OpenGL函數(shù)、枚舉和擴展。

②SharpGL.SceneGraph：包含所有包裝OpenGL的對象和場景中的元素-燈光、材料、紋理、材質等。

③SharpGL.WinForms：為我們的應用程序包含Windows窗體控件。

④SharpGL.WPF：為我們的應用程序包含WPF控件。

⑤SharpGL.Serialization：包含用于裝載幾何和來自于3D Studio Max文件的數(shù)據(jù)，不引人注意的obj文件和truespace文件的類。

3 邦寶模型積木分析系統(tǒng)設計與實現(xiàn)

3.1 系統(tǒng)概述

積木是公認能培養(yǎng)兒童創(chuàng)造力、學習能力以及訓練手眼協(xié)調的最佳工具，積木中的排列，接合，環(huán)形，對稱等都對開發(fā)孩子的智力有好處。積木的生產是個很有發(fā)展前景的項目，但是由于組成實物的小積木塊，一般都由幾百、幾千甚至上萬個小積木組成，零件的數(shù)據(jù)量龐大，目前大部分玩具廠商都是先通過先人手動地拼成我們需要的積木實體形狀，再統(tǒng)計所需的積木小零件的種類和總個數(shù)，最后交由工廠生產，顯然這過程的任務很繁重，拼裝設計時稍微的改動對整體的影響很大，效率也很低。如果積木的拼裝和統(tǒng)計能用計算機模擬，那將極大地節(jié)約人力、物力和成本。因此，我們急需開發(fā)出一個系統(tǒng)，能夠用計算機來實現(xiàn)從三維模型導入、模型調整、切片分層、顆?；捷敵龇e木搭建方案的全自動化，這樣既能節(jié)約生產成本和生產周期，又能提供實踐指導。

本系統(tǒng)的目標就是建立一個3D圖形應用程序，用于計算在使用邦寶基本部件搭建一個模型時所需要的部件種類、個數(shù)及輸出每層的積木搭建排列方案，進一步計算出搭建這樣的模型時的初步報價。不同形狀的積木可以由不同的顆粒狀的積木塊（積木磚）組成，積木的拼裝過程整體上可以看出是從下到上（或從上到下）。對于給定實物模型的3D外觀數(shù)據(jù)，用計算機模擬分層切割過程，計算出每層的排列情況并顯示，且滿足以下條件：

①所用的積木塊數(shù)量總數(shù)盡量少，即中心部分是骨架連接或鏤空的。

②拼成后積木盡可能的牢固。

③拼成后盡可能的逼近原始形狀的物體。

3.2 系統(tǒng)結構總框架設計

邦寶模型積木分析系統(tǒng)主要包括八大功能模塊，即數(shù)據(jù)導入、數(shù)據(jù)管理、模型副本管理、模型副本分層、分層顆?；?、積木搭建、查看三維圖、數(shù)據(jù)導出，這些模塊又是由若干個子模塊構成的，系統(tǒng)結構總框架如下圖所示：

圖一 ?系統(tǒng)結構總框架圖

3.3 系統(tǒng)的主要功能介紹

系統(tǒng)的主要功能如下：

①數(shù)據(jù)導入

基本部件：導入邦寶基本部件的3DS文件。

三維模型：導入模型的3DS文件。

②數(shù)據(jù)管理

數(shù)據(jù)修改：修改部件及模型的基本數(shù)據(jù)并保存在數(shù)據(jù)庫。

數(shù)據(jù)計算：計算部件及模型的長、寬、高等數(shù)據(jù)并保存在Access數(shù)據(jù)庫。

數(shù)據(jù)增刪：添加或刪除部件或模型的相關數(shù)據(jù)。

③模型副本管理

副本增刪：按某個比例放大或縮小原始模型來添加其副本或刪除模型副本及其相關數(shù)據(jù)。

副本編輯：修改模型副本的相關數(shù)據(jù)，設置鏤空壁厚、分層方式等參數(shù)并保存在Access數(shù)據(jù)庫。

④模型副本分層

部件選擇：可以選擇不同類型的部件，如小顆粒塊（磚）等， 按所選部件的高度將模型等距地分為若干層并進行切片操作。

最優(yōu)分層：將各層分層后所得矢量多邊形進行柵格化，并提供基礎性的鏤空及編輯功能（一般大型積木模型不會是實心的）。

⑤分層顆粒化

顆?；簩⒎謱拥玫降钠矫娑噙呅斡貌煌伾男》綁K最佳覆蓋，對模型的所有層進行顆?；?。

鏤空設定：用戶可以調整鏤空時的厚度參數(shù)。

⑥積木搭建

底層排列：第一層是底層，在此層的部件排列方式與其它層不同。

逐層排列：每層在它下層排列的基礎上進行積木排列，準許用戶調整鏤空時的厚度參數(shù)，并提供上下層粘連性檢驗，但要保證搭建的模型牢固。

⑦查看三維圖

三維顯示及編輯：查看部件和模型的三維圖，能夠用鼠標進行三維圖的旋轉、縮放和平移等交互操作，并提供對積木模型的編輯功能，如對某塊積木的增刪、著色、移動等。

單層顯示：查看整個模型每一層的三維圖。

雙層顯示：查看整個模型每兩層疊加在一起的三維圖。

三層顯示：查看整個模型每三層疊加在一起的三維圖。

所有層顯示：查看整個模型所有層的三維圖。

⑧數(shù)據(jù)導出

積木統(tǒng)計：系統(tǒng)可以計算出模型中總共使用的部件種類及其數(shù)量，進而計算出其總重量及總價格。

數(shù)據(jù)導出：系統(tǒng)可以導出3DS和bmp格式的文件。

3.4 系統(tǒng)的核心算法簡介

3.4.1 3DS文件導入算法

在數(shù)據(jù)讀取之前，首先要建立存儲點、面、材質、對象等信息的數(shù)據(jù)結構，以用來保存3DS模型數(shù)據(jù)。OpenGL讀取3DS的算法思路是：首先根據(jù)偏移量和長度找到一個塊的ID標識符，再根據(jù)這個來判斷它是什么塊，遇到我們需要的塊，就進一步讀取，如果不需要，直接忽略這一塊，讀取下面的塊，最后循環(huán)遍歷所有的塊，即讀出各個數(shù)據(jù)塊[9]。

讀取出3DS文件后，需要在OpenGL環(huán)境下將讀出來并存在數(shù)據(jù)結構中的3DS文件信息繪制出來。在繪制場景時，首先計算法向量，它直接影響到光線從不同的角度入射到模型表面，產生不同的顯示結果，如果法向量不確定，三維效果的圖形是顯示不出來的。再通過模型的各種變換來實現(xiàn)法向量的計算，本系統(tǒng)首先遍歷對象的面和頂點的所有信息，從而計算出這些信息的法向量，并將法向量添加到法向量列表中。然后根據(jù)存儲在自定義的數(shù)據(jù)結構的信息，這樣OpenGL就能將模型繪制出來。

3.4.2 基于掃描法的柵格化算法

整個模型的顆?；枰獙δＰ透北舅蟹謱拥玫降氖噶慷噙呅芜M行柵格化。目前雖然已存在多種柵格化算法[10]，如常見的有內部點擴散法、邊界代數(shù)法、邊界點跟蹤算法、射線法、掃描法等，但每種算法都有自己的缺陷。本系統(tǒng)采用了各方面性能比較平衡的掃描法，雖然避免了上述的內部填充過程，但模型的顆?；K在設計的過程中還遇到了一些特殊問題。因此本系統(tǒng)的算法設計在掃描法的基礎上，添加了橫邊表并制定了更加詳細的規(guī)則，使其能正確處理各種特殊情況。

3.4.3 單層積木鋪設算法

根據(jù)現(xiàn)實中經驗豐富的員工搭建的每一層積木大體上是十分規(guī)律的，只是在局部上作出某些調整。因此在本系統(tǒng)提出這樣一種算法，這種算法可分三個部分，一是利用“基本件”的特點，選取了1×1、1×2、1×3、2×2、2×3和“L型拐”這6種積木為基本鋪設顆粒，采用貪心加局部搜索的算法鋪設;二是為了減少零碎顆粒，就近調整“單?！?三是“并小為大”，將基本鋪設顆粒拼合成大的積木。結果證明，此算法可以很好地完成積木鋪設問題。

3.4.4 上下層粘連性檢驗算法

一個合格的積木模型搭建方案必須確保這個積木模型不散架，在本系統(tǒng)中，通過上下層粘連性檢驗算法來達到這一效果。這個算法可分為兩個方面，一是相鄰層采用不同的優(yōu)先順序可以巧妙地使相鄰層的積木盡量多的交叉相扣，增強上下層的粘連性;二是結合并查集算法，將每塊積木視為圖中的一個結點，為積木粘連問題建立圖論模型。通過這兩個方面的相互配合，不僅在一定程度上提高了運算速率，而且較好地保證了模型的粘連性。

4 結束語

邦寶模型積木分析系統(tǒng)的成功使用，能夠用計算機實現(xiàn)從三維模型導入、模型調整、切片分層、顆?；捷敵龇e木搭建方案的全自動化。這不僅在一定程度上節(jié)約了大型模型的搭建時間和生產成本，而且為員工提供了實踐指導，有效地提高了工作效率。本文基于OpenGL技術對邦寶模型積木分析系統(tǒng)進行了研究，簡要介紹了實現(xiàn)這一系統(tǒng)所需的開發(fā)平臺、技術及算法。由于時間和知識水平的限制，本系統(tǒng)還存在著很多的不足之處，比如在整個積木模型的內部鏤空、積木模型的受力分析（如積木懸空部分、倒吊部分）等方面還是比較不足的。對此，我們可以進一步研究，將本系統(tǒng)的相關知識運用到其他工程項目中。

參考文獻：

[1]施瑞奈爾（DaveShreiner）.OpenGL編程指南[M].北京：機械工業(yè)出版社，2010.

[2]賴特（RichardS.Wright.Jr）.OpenGL超級寶典[M].北京：人民郵電出版社，2010.

[3]Donald Hearn，M.Pauline Baker.計算機圖形學（第四版）[M].北京：電子工業(yè)出版社，2012.

[4]呂希奎，周小平.實戰(zhàn)OpenGL三維可視化系統(tǒng)與源碼精解[M].北京：電子工業(yè)出版社，2009.

[5]劉芳，劉賢梅.3DS文件讀取、繪制與控制方法的研究與應用[J].計算機工程與設計，2009，30（19）：4575-4578.

[6]高明向，陳定方.OpenGL建模技術在C#中的實現(xiàn)[J].武漢理工大學學報，2005，27（1）：65-68.

[7]門光福，田芳.基于Tao框架的C#中OpenGL建模技術的實現(xiàn)[J].新余高專學報，2006，11（6）：73-74.

[8]殷素峰，高雪強，楊勝強.在OpenGL環(huán)境下開發(fā)3DS 文件瀏覽器[J].工程圖學學報，2005，26（6）：22-25.

[9]陳雪梅，謝清鐘.淺析一種運用OpenGL導入顯示3DS三維模型的方法[J].吉林省教育學院學報，2012，28（299）：86-87.

[10]周琛，陳振杰，張帥.基于邊界代數(shù)法的矢量柵格化并行算法設計與實現(xiàn)[J].計算機工程與科學，2013，35（4）：37-41.

作者簡介：

張承鈿，男，1961.02.24，籍貫：德國，副教授，研究方向：軟件工程及項目管理、云計算技術在科學計算中的應用、流體力學計算。

趙靜，女，1991.01.01，湖北崇陽人，漢族，碩士研究生，研究方向：軟件工程。