面向三維模型輕量化的自私羊群優(yōu)化算法研究

朱惠娟，王永利，陳琳琳

1.南京理工大學紫金學院 計算機學院，南京210046

2.南京理工大學 計算機科學與工程學院，南京210094

1 引言

20世紀70年代中期，虛擬仿真技術[1]開始逐漸擴展到民用領域[2]。從最初的靜態(tài)仿真模型展示，到如今人機交互、數(shù)據可視化于一體，仿真技術在各行業(yè)的應用越來越廣泛。航空類的仿真培訓系統(tǒng)、BIM建筑生命周期的管理平臺、制造智能仿真系統(tǒng)等，都在研究如何將仿真技術更好地與行業(yè)需求相結合[3]。這些仿真系統(tǒng)的三維場景結構復雜、數(shù)據量大，對真實性要求高，渲染時間長。目前大多數(shù)場景仍然是純手動生成階段，大量重復勞動、效率低，往往花了大量的人力與時間，也得不到滿意的效果，時常出現(xiàn)延時、丟幀、卡頓的現(xiàn)象，直接影響用戶體驗[4]。針對此問題，學者們紛紛提出模型輕量化的想法。

模型輕量化可以極大程度減少重復模型、多余的邊和面，縮短渲染時間，降低對處理器計算能力的要求，降低傳輸成本[5]。以BIM為例，BIM是“建筑信息模型”的簡稱，是在建筑行業(yè)的一項新技術。BIM的核心是通過建立虛擬的建筑工程三維模型，利用數(shù)字化技術，為用戶提供完整的數(shù)據模型[6]。由于模型鏈接模式比較復雜，中心模型擁有龐大的數(shù)據信息，對計算機硬件要求較高，因此進入BIM2.0階段以來，加大了對BIM輕量化的研究，以此提高系統(tǒng)的運行速度、降低使用成本[7]。

本文以3D模型點、面數(shù)量最小為優(yōu)化目標，采用自私羊群優(yōu)化算法對模型進行輕量化設計，通過隨機生成捕食者，為每個體分配生存值，得到羊群領袖和獵物的位置，從而刪減不必要的點和面，經過多次迭代，實現(xiàn)模型的最優(yōu)處理。為了驗證算法的優(yōu)化效果，在確保三維數(shù)據準確性的基礎上，根據模型冗余的類型，基于3DMax腳本語言MAXScript對三維模型進行輕量化處理，實驗證明，該算法收斂速度快，收斂精度高，穩(wěn)定性強，可以智能減少場景的數(shù)據量、加快模型的優(yōu)化速度、減少工作量，同時緩解計算機處理的壓力。

2 相關工作

文獻[8]通過點云降噪處理、逆向建模、構建合并和復雜構建減面的傳統(tǒng)方法處理碎片化點云模型，減少模型個數(shù)和面數(shù)，這樣做雖然模型體量變小，但是真實感也同時降低。文獻[9]通過對三維模型的非結構化幾何信息進行提取，采用壓縮簡化算法進行優(yōu)化處理，提取標準化的標注、屬性和檢測等各類信息，同時對曲線、曲面壓縮處理，最終得到數(shù)據量低的輕量化模型。文獻[10]以基于IFC的進度資源信息模型為基礎，通過分析IFC模型與離散時間仿真模型的異同，實現(xiàn)IFC模型向仿真模型的自動轉換。

目前，物體建模的常用方法有通過三維軟件建模、使用三維掃描儀器建模[11]。市場上有很多優(yōu)秀的建模軟件，較為知名常用的是3Dmax軟件。3DMax中有一些基本的幾何元素，比如立方體、圓柱體等，可以通過一系列幾何操作，比如平移、布爾運算等進行模型的構建。實際工程應用中，大多數(shù)的建模方法是手動減面，耗時耗力，本文提出采用3DMax內置的腳本語言MAXScript進行批量減面，可以有效減少優(yōu)化時間。

MAXScript[12]是3DMax內置編程語言，基于OpenGL和VC編制，可以調用3DMax的大多數(shù)功能，通過一個開放式界面自定義和編寫。文獻[13]在構建三維城市時，應用MAXScript對3DMAX對象進行開發(fā)，證明MAXScript在三維構建中有較好的適用性。文獻[14]運用MAXScript生成了一個立體構成插件用于立體構成課程教學中。利用MAXScript可以快速實現(xiàn)傳統(tǒng)模型優(yōu)化過程中的大量操作[15]。

由于基于群體智能優(yōu)化的方法可避免3D模型變量依賴于形狀參數(shù)信息，且具有優(yōu)化效率高，模型求解簡單易行，便于實際工程應用等優(yōu)點。眾所周知，國內外尚未有利用群體智能優(yōu)化算法解決3D模型輕量化問題的研究工作出現(xiàn)。Selfish Herd Optimizer（SHO）是一種新提出的群體智能優(yōu)化算法，該算法主要模擬羊群受到捕食者攻擊時的自私行為（盡量聚集到牧群中心遠離捕食者），它具有易于理解和實施的特點。

3 基于自私羊群優(yōu)化的大場景3D仿真模型輕量化方法

三維模型由網格和紋理構成。網格是通過物體中的點云而形成的，點云包括空間坐標信息、光線反射強度以及顏色信息，三維網格就是通過點到線、線到面、再由面構建成三維物體。越復雜的三維場景，需要點和面的數(shù)量就越多，當模型的精細復雜度達到一定程度，就會給CPU和顯卡帶來很大的負擔，造成系統(tǒng)嚴重的卡頓甚至渲染報錯現(xiàn)象。因此，在設計和規(guī)劃場景時，要充分考慮到現(xiàn)實的需求，刪除不需要的點和面，開展模型優(yōu)化工作。

3.1 三維仿真模型輕量化問題及自私羊群優(yōu)化形式化描述

本節(jié)首先形式化描述3D仿真模型輕量化問題，利用智能優(yōu)化的3D仿真模型輕量化問題或數(shù)學模型可描述為：以3D仿真生成的點、面?zhèn)€數(shù)最小為優(yōu)化目標，即：

3.2 基于自私羊群的3D仿真模型輕量化算法描述

自私羊群優(yōu)化SHO算法是由Fausto于2017年提出的元啟發(fā)式算法[16]，它主要基于漢密爾頓[17]提出的自私群理論來模擬獵物與捕食者之間的狩獵關系。當群體中的個體受到捕食者的攻擊時，為了增加生存機會，群體中的個體產生聚集行為，個體更有可能移動到相對安全的位置（群體的中心位置），并且群體的邊緣個體更容易受到攻擊，這也導致群體的邊緣個體逃離群體，以增加他們被捕食者攻擊時的生存機會。該方法假設整個平原是一個解空間，該算法包含兩個不同的搜索因子：被狩獵群和狩獵群。每個搜索因子通過一組不同的進化算子指導算法的計算，以便更好地模擬獵物與捕食者關系之間的關系。

（1）初始化種群個體

假設自私羊群體優(yōu)化算法的群體集合是S，它包含N個種群個體，本文中個體對應三維網絡中的面和點。種群中的每一個體被定義為Si=(si,1,si,2,…,si,n)，其代表個體在種群中的位置信息，n代表解決方案的大小（設計面總數(shù)）。整個種群組的初始化公式如下：

其中xlowj和xhighj 分別表示解空間的下限和上限。算法參數(shù)值的范圍：i=1,2,…,N和j=1,2,…,n。rand()表示隨機函數(shù)，生成值的范圍落在區(qū)間[0，1]內。

在自私羊群優(yōu)化算法中，整個種群S被分為兩個子群：H和P(S=H∪P)，H(H=h1,h2,…,hNh)代表一群獵物，P(P=p1,p2,…,pNp)代表一群捕食者。在自然界中，獵物的數(shù)量通常多于捕食者的數(shù)量。在SHO中，獵物(Nh)的數(shù)量占總個體的70%～90%(N)，其余的個體被認為是捕食者(Np)。Nh和Np按以下公式計算：

其中，rand()表示一個隨機數(shù)，其值范圍為0.7到0.9，而floor(·)表示將實數(shù)轉換為整數(shù)的函數(shù)。

整個過程都在不斷優(yōu)化點和面，任何形狀的圖形，捕食者都會遍歷所有獵物的信息，因此，三維網格不分模型形狀，將隨機生成獵物和捕食者。

（2）分配生存價值

在SHO中，為整個種群(S)的每個體(si)分配一個生存值(SVsi)，其代表個體的生存能力，有機會在攻擊中生存或成功殺死攻擊中的獵物。生存價值的數(shù)學公式定義如下：

其中，f(·)代表目標函數(shù)，fbest和fworst分別代表目標函數(shù)的最佳值和最差值。對70%～90%的獵物計算生存價值，生存價值最高的為獵物領袖，生存價值越低的為最容易被捕獲的獵物。

（3）算法的結構

基于SHO的3D模型輕量化算法的結構主要包括四個方面：①獵物（被捕食者）領袖的運動；②獵物追隨者的跟隨運動或逃脫運動；③捕食者的狩獵運動；④捕食階段和恢復階段。

①獵物領袖的運動

獵物的領導者被定義為獵物種群中最大的生存價值。

定義公式如下：

獵物領袖的位置更新如下：

α代表區(qū)間[0，1]之間的隨機數(shù)，α越大，位置更新越快，捕獲的獵物越多；α越小，捕獲的獵物越少。φ代表個體之間的吸引力，pM代表獵物的相對危險位置，φ與pM定義如下：

②獵物追隨者的跟隨運動或逃脫運動

在獵物種群中，獵物追隨者分為跟隨獵物(HF)和逃生獵物(HD)，跟隨獵物又分為優(yōu)勢獵物(Hd)和下屬獵物(Hs)。

HF，HD，Hd與Hs定義如下：

其中SVhu代表獵物生存價值的平均值，定義如下：

跟隨獵物的位置更新公式如下：

其中，β，γ和δ表示區(qū)間[0，1]內的隨機數(shù)形式，hci表示局部最優(yōu)個體，hM表示獵物的相對安全位置，其定義如下：

其中ri,j代表獵物個體之間的歐幾里德距離。逃生獵物的位置更新公式如下：

其中，xbest表示全局最優(yōu)位置，β和γ表示在區(qū)間[0，1]內的隨機數(shù)，β表示距離獵物領袖位置，β越小，表示距離越近；γ表示控制隨機偏移值的長短，γ越小，表示偏移值越小。ε表示空間解中的隨機方向。

③捕食者的狩獵運動

在捕食者種群中，捕食者的位置更新公式如下：

其中，ρ代表區(qū)間[0，1]之間的隨機數(shù)，ρ值越大，位置更新越遠，越容易忽略獵物。hr是基于捕食概率從獵物種群中隨機選擇的獵物，捕食概率(θpi,hj)定義如下：

ωpi,hj表示捕食者和獵物之間的吸引力，吸引力的數(shù)學公式定義如下：

其中||pi-hj||2代表pi和hj之間的歐幾里德距離。

④捕食階段和恢復階段

捕食階段：每個獵物都有一個危險的區(qū)域，如果它屬于這個領域，很可能被捕食者捕殺。危險域通常是一個圓，其半徑定義為：

危險區(qū)域的獵物收集定義如下：

獵物在危險區(qū)域被獵殺的概率定義如下：

恢復階段：在SHO中，被捕食者獵殺的所有獵物都將被新生的獵物所取代，新的獵物將通過交配操作產生，SHO通過交配概率選擇交配獵物，其定義如下：

其中M代表一群沒有被捕食者捕殺的獵物集，交配操作定義如下：

函數(shù)mix(·)用于從不同個體(s=r1,r2,…,rn)中選擇維度組件。基于SHO的模型輕量化算法3DL-SHO如算法1所示：

算法1基于SHO的模型輕量化算法

1.Input 3D模型網絡向量Si=(si,1,si,2,…,si,n)

2.Begin

3.利用公式（1）初始化所有個體S

4.定義羊群成員和捕食者的個數(shù)，利用公式（2）、（3）并將S分為兩組：H與P

5.For entire S do

6.利用公式（6）計算生存值

7.End For

8.While（t＜Max number of iterations）

9.執(zhí)行自私羊群移動操作

10. For each selfish herd

11. IF leader of the herd

12. 利用公式（8）為羊群領袖更新位置

13. Else

14. 利用公式（6）和（19）更新羊群跟隨或逃離運動

15. End IF

16. End For

17.捕食者移動操作

18. For each predators

19. For each selfish herd

20. 利用公式（21）計算追逐概率

21. End For

22. 利用公式（20）更新捕食者位置

23. End For

24.利用公式（6）重新計算H和P中每個成員的生存值

25.利用公式（23）計算危險域半徑R

26.利用公式（24）、（25）執(zhí)行捕食階段

27.利用公式（26）、（27）執(zhí)行恢復階段

28. t=t+1

29.End while

30.返回羊群領導者位置

31.Output點、面最優(yōu)值

32.End

表1 實驗中用到的測試函數(shù)

3DL-SHO運行中對模型優(yōu)化的幾個啟發(fā)式原則包括：

（1）采用Polygon多邊形建模方法，根據需要配合網格平滑生成曲面，制作出各種形狀的三維物體。

（2）運用單面建模與多邊形建模相配合，重點構建視覺范圍內看到的模型，不在視覺范圍內的模型可以適當減少模型面片。

（3）如果網格模型的面數(shù)減少對模型的輪廓沒有影響，這些面就可以刪除，或者用貼圖來代替。

（4）貼圖的大小直接影響顯卡的處理速度，在達到顯示效果的情況下，選用更少的材質、低分辨率的貼圖。對于規(guī)則的模型，可以通過分析建筑模型網格生成的特征，生成網格遍歷條件，利用MAXScript腳本語言，循環(huán)簡化場景表面的細節(jié)，從而使場景的模型面數(shù)大大精簡，最終實現(xiàn)輕量化的目標；對于不規(guī)則的模型，也就是包含了大量位置錯亂的點、面時，可以通過刪除錯誤的面，同時根據模型生成算法，在保持原有數(shù)據不變的情況下智能生成新模型，以替代舊模型的方式，從而達到優(yōu)化的目的。

4 仿真與性能測試

4.1 自私羊群優(yōu)化算法性能測試

為了驗證基于自私羊群優(yōu)化的3D模型輕量化方法性能，使用5個基準函數(shù)進行測試，該算法將與烏鴉搜索算法（記為3DL-CSA）[18]，粒子群優(yōu)化[19]（記為3DL-PSO）進行比較，所有基準函數(shù)和算法的具體參數(shù)均參考文獻[16]。所有算法的種群大小(N)設置為50個個體，最大迭代次數(shù)設置為1 000(T)[20]。實驗中，所用機器配置是CPU是i7 4710，主頻是2.5 GHz，970顯卡，16 GB內存。基準函數(shù)如表1所示，實驗數(shù)據如表2所示。

表2給出了實驗結果，其中“f”代表基準函數(shù)，“BV”、“MV”和“SD”分別代表最佳解決方案的最佳值、平均值和標準偏差。

從表2可以看出，對于函數(shù)f1，3DL-SHO的平均值的準確度分別比其他兩種算法的次優(yōu)解高16和14個數(shù)量級，對于函數(shù)f2、f3和f4，3DL-SHO的平均值的準確度分別比3DL-CSA的次優(yōu)解決方案高14、16和5個數(shù)量級。與3DL-PSO算法相比，平均值的準確度分別增加了7、8和1個數(shù)量級。

表2 算法優(yōu)化實驗結果

對于函數(shù)f5，3DL-SHO的平均值的準確度分別比3DL-CSA和3DL-PSO的次優(yōu)解高13個數(shù)量級。在功能上，3DL-CSA的平均值的準確度最好，平均值為-3.99E+03。3DL-SHO的平均值為-1.25E+03，與3DL-PSO相比，平均值的準確度增加了1個數(shù)量級。從上述實驗數(shù)據可以看出，所提出的算法與原算法和其他算法相比，對函數(shù)解的精度有很大的提高。

本文同時也測試了算法對應這幾個基準函數(shù)的收斂圖和標準方差圖，通過結構的分析來評估所提方法的性能。該算法的收斂速度最快，具有很強的穩(wěn)定性和最高的求解精度。可以看到所提算法的收斂速度和精度在第100次迭代后已經超過了其他算法。

PSO的收斂速度和精度稍微接近所提出的算法，但在迭代終止之前，其性能不超過所提出的算法。從上述實驗數(shù)據和圖片可以看出，與其他算法相比，3DLSHO該算法的性能在解決函數(shù)優(yōu)化問題上具有很大的優(yōu)勢。該算法收斂速度快，收斂精度高，穩(wěn)定性好。

為了驗證本文提出的3D模型輕量化方法在實際應用中的效果，本文構建了兩組3D模型仿真實驗，分別對應最常見的兩種3D模型冗余情況。

4.2 無規(guī)則的點、面冗余去除實驗

無規(guī)則的點、面冗余，指的是模型有大量位置錯亂的點和面，不但使模型體積變大，也影響了模型的UV展開和烘焙。如果直接把Revit模型導入交互引擎中，會出現(xiàn)不能貼圖等問題，因此要將模型先導入3Dmax或類似的三維建模軟件中優(yōu)化。但是當把Revit模型導入3DMax中時，又會出現(xiàn)大量位置錯誤的點和面。如圖1所示，尤其以圓柱體的模型，比如管線、彎頭出現(xiàn)這樣的現(xiàn)象最多。

圖1 BIM模型

本文使用3DL-SHO智能方法解決此問題，主要思想是遍歷待優(yōu)化的模型，獲得模型的位置等數(shù)據信息，根據模型生成的邏輯方式，調用3DL-SHO算法，自動在原位置上生成新的模型，并替代舊模型。

實驗模型如圖1所示，來自BIM房屋系統(tǒng)8層樓，用Revit建模，模型大小為10.7 MB，場景面數(shù)為122 224，頂點為70 576。每一層樓的內部空間如圖2所示。

圖2 內部模型

將場景導入3DMAX后，管線處生成了大量位置錯誤的點和面，如圖3和圖4所示，導入前是圓形，導入后，變成了正八邊形。

實驗操作如下：

圖3導入3DMAX前

圖4導入3DMAX后

（1）計算管線兩底面的高度；（2）獲取底面直徑；（3）設定分段數(shù)；（4）調用3DLSHO算法，生成新管線替代舊管線。

優(yōu)化之前，不規(guī)則的點、面，不適合展UV展開貼圖，如圖5所示；優(yōu)化后，方便展UV貼圖，在UV展開后輸入了“消防水管”貼圖，效果如圖6所示。

圖5優(yōu)化前的UV

圖6優(yōu)化后的UV

從實驗中看出，這種以機器建模替代舊模型的優(yōu)化方式是根據模型的特征計算機出新的模型，同時不會改變模型的坐標等信息，比較好地保留了主要數(shù)據。如果手動在原模型上修改，重復工作量巨大；如果手動完全重新構建，就很難保證模型坐標的正確。實驗前后對比數(shù)據如表3所示。

表3 優(yōu)化前后對比數(shù)據

4.3 有規(guī)則的點、面冗余去除實驗

有規(guī)則的點、面冗余，指的是多余的點、面有規(guī)律可循，但手動刪除，仍然要花費大量的人力，本實驗的主要思想是遍歷所有待優(yōu)化的模型，依次選擇所有的點，自動進行優(yōu)化操作。實驗模型如圖7所示，模型是一個水電廠的消防裝置，面數(shù)為14 660、點數(shù)為43 980，模型的頂點都是離散的，不但占內存，也不方便貼圖。如果手動焊接，工作量很大。

本實驗將通過自動焊接，完成每個模型點的焊接，有規(guī)則的點面冗余去除優(yōu)化步驟：

圖7 消防裝置

（1）根據條件遍歷模型，轉換成可編輯多邊形；（2）在點的模式下，選擇所有點；（3）調用3DLSHO算法，生成焊接的值，進行點的焊接；（4）進行平滑操作。

通過批量焊接點，頂點由43 980，優(yōu)化到了7 730，對貼圖效果有了大大的改進，如圖8和圖9所示。

圖8優(yōu)化前的UV

圖9 優(yōu)化后的UV

綜上所述，本文所提方法在不影響顯示效果的情況下，可以對模型有大量的優(yōu)化，同時計算過程簡單，占用內存空間較少。

5 結束語

綜上所述，為了降低計算機的硬件負荷，在不影響仿真模型真實感的前提下，應當對數(shù)字化模型進行優(yōu)化。針對當前優(yōu)化方法不多的情況，提出了一種基于自私羊群智能優(yōu)化的三維仿真模型輕量化方法，由于模型出現(xiàn)的問題都不相同，本文選用最有代表性的兩類問題，分別是大量重復的規(guī)則的點、面以及不規(guī)則的點、面，以智能化構建新模型以及修改原模型兩種解決方案，均實現(xiàn)了優(yōu)化效果。研究結果證明，只要根據模型的特點，所提出的方法能快速優(yōu)化模型，且實現(xiàn)過程較簡單。