積木3D模型智能搭建系統主要算法的研究與設計

蔡 浩 姚肖豪 高展鵬 張承鈿

(汕頭大學工學院計算機科學與技術系 廣東 汕頭 515000)

積木3D模型智能搭建系統主要算法的研究與設計

蔡 浩 姚肖豪 高展鵬 張承鈿

(汕頭大學工學院計算機科學與技術系 廣東 汕頭 515000)

由于人工使用插座式積木搭建大型場景模型時會出現無法提前計算用料、單憑經驗搭建費時費力等難題，應企業需求而開發的積木智能搭建系統解決了從模型的3D文件導入、模型調整、切片分層、柵格化，到輸出積木搭建方案的全智能化。其中對該系統開發所涉及的矢量圖柵格化、積木鋪設、模型粘連性檢驗等問題，提出了相應的算法，并探討了設計的細節。這些算法是整個系統的核心，系統的實際應用表明，這些算法在保證模型正確搭建的前提下，能有效地提高系統的運算速度。

積木 智能搭建 矢量柵格化 積木鋪設 粘連性檢驗

0 引 言

積木智能搭建系統的用戶是一家生產類似樂高插座形式積木玩具的企業，除了銷售小型積木玩具，還負責為客戶搭建所定制的用于布設場景的大型積木模型，如會展的大型吉祥物、建筑群的微景觀。以往大型積木模型的搭建過程一般要經過以下四個步驟：1)創建欲搭建模型的3D文件；2)進行分層并得到各層切片；3)各分層切片的柵格化；4)依靠員工的經驗一層層的搭建。由于在上述的前三個步驟中需借助多個來源不一的軟件，這不僅加大了員工的培訓難度，也造成管理上的不統一。而步驟4的用時長短更是影響整個工作的關鍵因素。人工搭建大型積木模型時無法提前計算出所需的積木類型及數量，而且面對越來越大的模型，純粹依靠工作經驗來搭建已經變得越來越難以實現，對于經驗豐富的員工，每層的搭建工作都經常是一個搭了拆、拆了又搭的過程。所以一個模型的搭建用時通常需要一到兩個星期，甚至一個多月，這不僅影響工期、增加人工成本，也必將影響企業與國外同行的競爭優勢。

目前，國內外關于積木模型智能自動搭建的研究幾乎是一片空白，既缺少相關的理論研究，也無現成軟件可供企業直接使用。因此，積木智能搭建系統正是應企業需求所開發，實現了從模型數據導入、模型調整、切片分層、柵格化，到輸出積木搭建方案的全自動化。本文敘述了系統開發過程中核心算法的研究與實現。

1 邏輯流程

積木智能搭建系統的功能是自動選取積木，完成模型的搭建(如圖1所示)，解決從模型的3D文件導入到輸出積木搭建方案等一系列問題。其流程如圖2所示，其中主要涉及到矢量圖柵格化、積木智能鋪設及模型粘連性檢驗等算法。

圖1 插座式積木及模型樣例

圖2 搭建流程圖

步驟1 導入被搭建物體的原始模型3D數據，本系統采用3ds格式文件，主要獲取其形狀、色彩等數據。

步驟2 生成一個原始模型副本，并在此副本上進行編輯操作，如按一定比例放大、縮小、修改表面顏色等。

步驟3 將此副本等距地分為若干層(每層高度等于積木的高度)并進行切片操作，得到各層的矢量多邊形數據。

步驟4 對所有層的矢量多邊形進行柵格化，并提供基礎性的鏤空及編輯功能(因考慮到省料及減重，大型積木模型通常是非實心的)。

步驟5 在步驟4的基礎上，從下往上逐層鋪設積木，每鋪設完一層就進行上下層粘連性檢驗，以確保搭建至末層(最高層)時積木模型具有整體性即不散架。如若檢驗不通過，則在給出修改方案或由人工調整后再循環步驟5，直至鋪設至末層。

步驟6 將搭建方案數據保存至文件，以供重復使用。

2 模型的顆粒化

整個模型的顆粒化需要對模型副本所有分層的矢量多邊形進行柵格化。矢量數據與柵格數據之間的轉換方法前人已有很多的研究，并應用在很多方面，如在地理信息系統(GIS)中，矢量數據與柵格數據間的轉換就是其基本功能之一。現今，矢量數據的柵格化，對點、線而言，并不存在什么難題，如線的柵格化常用算法有DDA法(數字微分分析法)、Bresenham算法等。而面的柵格化算法也有多種，如常見的有內部點擴散法、邊界代數法(BAF-Boundary Algebra Filling)、邊界點跟蹤算法、射線法、掃描法等，再如近年提出的一些方法，武廣臣等提出的環繞數法[4]、張毅等提出的基于邊界跟蹤的填充算法[8]等。上述現有的柵格化算法都有各自的優缺點，并非都能很好地適用于此項目的模型顆粒化問題。在GIS中矢量數據轉換成柵格數據之前需要根據數據精度和數據量等來確定柵格尺寸的大小，然而在本系統中，積木的最小顆粒度即1×1的積木的大小是固定的。固定的柵格尺寸及可能出現的局部高精度密集矢量數據，是選擇柵格化算法時首先必須考慮的問題。

模型的各層切片數據是由若干個多邊形組成，這些多邊形有可能出現交叉或重疊。每個多邊形都是封閉的，各條邊的數據中除了兩端點坐標，還帶有該邊的顏色信息。因此，在考慮單個多邊形的柵格化之外，還要考慮多個多邊形交叉疊加的處理，以及染色問題。

本搭建系統在應用現有邊線柵格化算法的基礎上，設計出完整的處理多個多邊形交叉疊加并染色的柵格化算法。

首先，采用Bresenham算法將每一個多邊形的邊線柵格化并染色。邊線柵格化，在這可以理解為將邊線經過的柵格填充染色。讀出一個多邊形的數據，對于該多邊形的每一條邊，先將起點(x0，y0)所在的柵格填充，然后依次遞推計算下一個要填充的柵格的坐標。Bresenham算法的核心是根據由直線斜率構成的誤差項的符號來確定下一個柵格坐標的遞增值。

設斜率k=Δy/Δx，根據直線的斜率分8個象限，如圖3所示。

圖3 根據斜率劃分的8個象限

在第1象限時，線段更貼近x軸，x值每次步進1，再根據誤差項符號確定y值是否加1。令起始誤差項e=-1/2，推斷出下一個坐標后，e=e+Δy/Δx，若e≥0時，y值加1；若e<0時，y值不變。若e≥0，y定值后e=e-1。

其他象限依此類推。在填充直線經過的每個柵格時，同時將該線段的顏色信息記錄到每個柵格中。

完成邊線的柵格化后，采用floodfill算法對該多邊形進行內部染色。這是本算法一個巧妙的設計。這里不用常用的種子填充法，而是使用洪水算法(floodfill)先填充多邊形之外的區域，然后再反填內部點。這樣避免了尋找多邊形的內部點并進行各種檢驗的復雜過程。在本項目中，各個多邊形都是簡單封閉多邊形，不會出現如圖4中的情形(柵格化后出現“洞”，這種情況會在切片時檢查并分隔為若干個多邊形)。

圖4 多邊形柵格化后出現“洞”的情形

每次使用洪水算法填充的對象不是整個分層，而是該層中的某一多邊形，將其映射到一個臨時二維數組中，并確保邊上所有柵格都不與數組邊界重合。在數組中任選一個邊界點開始著色，只要著色點周圍的格子還未染色(邊線格子已染色)，則將該格子著色，然后依次漫開。當這區域全染色后，剩下的未染色區域則為多邊形的內部，反填即可，如圖5所示。

R:紅色;E:多邊形外部;A:任意色圖5 多邊形內部染色過程

每次填充后，需將此多邊形柵格數據疊加回該層平面的柵格數據總表。由于前述的單個多邊形柵格化操作是將各個多邊形抽象獨立出來，各自開辟臨時表格，并進行了坐標平移的操作，所以疊加的時候需對坐標進行復位計算，并按以下規則著色填入總表：設臨時表中某柵格s1[x1][y1]非空，且顏色為C1，其對應總表中的位置S[x][y]。若S[x][y]的顏色為‘E’(多邊形外)，或者為‘A’(多邊形內且非邊)，則將C1填入S[x][y]；若S[x][y]的顏色信息為邊線顏色，則不作改變。

3 單層積木鋪設

每一層積木的鋪設是個難題，模型的截面直徑、高度可達5米，1×1的積木邊長還不到1厘米，也就是說，一個平面層最多能布上500×500個積木。若只考慮“基本件”，即矩形的“磚”和“L型拐”，積木的形狀種類也有數十種。假設一個平面布上n個積木，積木的種類有m種，那么搜索的復雜度是m的n次方，若再考慮積木的擺放方向，問題將更復雜。

這種情況下是不能單純采用搜索算法的，剪枝、A*等搜索優化均不適用，也不能用動態規劃去解決，遺傳算法之類的隨機調整算法也不能有效地提高運算效率。除此之外，曾試采用分治法將多邊形劃分為多個區域，每個區域采用搜索或動態規劃來鋪設積木。實際測試后證明，這種方法也是不可取的，運算速度遠遠無法達到要求。

其實，上述的幾種方法不可取之處在于每一步的考慮范圍過大，且其具有的隨機性及無序性，無形中一步步地破壞了欲填充區域內部的結構，這必將導致運算時間的居高不下。觀察這幾種方法給出的鋪設結果會發現積木的擺放十分雜亂，毫無規律可言，這一點與由經驗豐富的員工搭建的結果截然不同。人工搭建的每一層十分具有規律性。在每個多邊形的腹部區域一般會呈現積木類型及擺放方向的統一性，猶如一同向而游的同類魚群。這一規律隨多邊形面積的增大而愈發明顯。雖然人工搭建也需在局部如多邊形邊界上做出細微調整，但總體上的規律性還是給予我們很好的啟發。

因此，本系統提出一種算法，主要分為三個部分：

(1) 采用貪心加局部搜索的算法鋪設。矩形“磚”的形狀種類有1×1、1×2、1×3、1×4、1×6、1×8、…、2×2、2×3、2×4、2×8、2×16、…等。“L型拐”積木也有多種類型，圖6列舉了其中幾種。

圖6 “L型拐”積木樣例

首先，從這些“基本件”中選取1×1、1×2、1×3、2×2、2×3的磚和2×2“L型拐”這6種積木為基本鋪設顆粒，其他基本件可由這幾種積木拼合而成。由于有1×1的顆粒，可知平面任意多邊形均能用這六種積木鋪滿。再根據這6種積木的幾何特性得到以下優先級，如表1所示，表中優先級數越小，優先級越高。其中同種積木由于擺放方向的差異、正在鋪設層層號的奇偶性，其優先級也將不同。

表1 積木基本顆粒鋪設優先級

這六種積木按優先級高低進行鋪設，如正在鋪設奇數層時，先用2×3的積木先橫后豎填充多邊形，再用2×2的積木填充剩余空間，然后再用“拐”，以此類推，……直到最后用1×1的積木將多邊形填滿。注意，2×3、1×3、1×2這三種積木各自要分豎放和橫放兩種情況(或各自視為兩種積木)，L型拐則要同時搜索四個方向進行擺放。因為搭建的模型是有顏色的，在鋪設的同時還要注意，同個積木所覆蓋的區域是否為同一種顏色。

(2) 就近調整“單粒”。為了減少零碎顆粒，檢查所有鋪設了1×1積木的地方，根據其四周相鄰的積木種類，以及相接的位置，分多種情況進行調整。例如，與1×1積木相鄰的是2×3的積木，有三種相接位置的可能，與其對應調整方案如圖7所示。

圖7 “單粒”與2×3積木相接的3種調整方案

與“L型拐”相鄰時則有4種情況，其中一種情況在調整后會出現新的“單粒”，具體如圖8所示。圖8(c)這種情況下，邊緣或懸空點應優先調整。若再考慮顏色因素，處理情況會更加復雜，但原理相同，便不再贅述。

(a)

(b)

(c)

(d)

圖8 “單粒”與“L型拐”相接的4種調整方案

由于上下層粘連檢驗的需要，平面中每個柵格的信息除了顏色還需包含鋪設積木的編號和類型。調整“單粒”時，這些信息都應做出相應的改變。

(3) “并小為大”拼合積木。將基本鋪設顆粒拼合成大的積木，以方便實際的搭建操作。各種積木的大小和形狀數據都存于數據庫中，除了上述六種基本鋪設顆粒，其他積木的數據可以由廠家根據需要自行調整。拼合的過程需要用到搜索和枚舉算法。相鄰兩個積木若符合拼合條件，并且拼合后的積木與數據庫中某積木的數據相同，則進行拼合。這樣逐漸從小到大拼合，直到全圖找不到可以拼合的積木。

實驗證明，此算法可以很好地完成積木鋪設問題。在不考慮上下層粘連性(即結合的牢固程度)條件下，此算法給出的鋪設方案與由員工自行思考后搭建的結果十分相似，而且在速度上更是完美地滿足了需求，例如鋪設一個2平方米的平面一般只需要幾百毫秒。

4 上下層粘連性檢驗

圖9 上下層積木交叉相扣

最終輸出的積木搭建方案除了外觀需要符合要求，還得保證這個積木模型是“整體”的，通俗點說就是通過上下層積木之間的相互搭扣來確保模型不散架，如圖9所示。在本系統中，通過兩個方面的配合來達到這一點。

一方面，盡量使搭建每一層的積木鋪設算法有利于上下層積木之間的相互搭扣。這也是本文前述的單層積木鋪設算法中將自身長寬不同的積木視為兩種積木的原因，如將2×3的磚視為3×2與2×3兩種積木，相鄰層對這兩種積木采用不同的優先級。如某層的積木優先順序為“橫向優先”時，則相鄰層為“豎向優先”，圖10所示為這兩種優先級順序的鋪設結果。顯然，相鄰層采用不同的積木擺放優先級有利于上下層積木交叉相扣，增強相鄰層的粘連性，使積木模型更加牢固。

圖10 兩種優先級鋪設結果對比

另一方面，設計了一種上下層粘連性檢驗算法，逐層檢驗并及時調整。在系統設計之初，為了確保模型的“整體”性，曾試用了幾種數據結構來記錄同層相鄰積木間的關系，并在鋪設積木時不斷地考慮扣緊哪些相鄰的積木。但是，實驗證明這種做法不僅提高了單層積木鋪設算法的設計難度，還大大增加了運算時間。而且基于本系統最后采用的單層積木鋪設算法本身有利于上下層積木之間交叉相扣的特性，完全可以采用一種比較寬松的標準來檢驗模型的粘連性。因此，我們參照并查集的算法思想，把每塊積木映射為圖論模型中的一個結點，把相互搭扣在一起的積木視為一個集合，從而將如何檢驗積木的粘連性轉化為一個圖論問題，并提出了這樣一種算法，具體描述如下。

在每一層的鋪設積木算法完成后掃描該層所有積木，并執行以下操作：

1) 賦予每塊積木唯一的標識并在圖論模型中建立相應的結點，其標識由單層積木鋪設算法賦予的編號及此積木所在層號組成。

2) 建立此積木結點與其他結點的關系。若此積木與下層某個積木相扣，則在圖論模型中相應的兩個結點間生成一條邊，將它們連通起來。經此操作，圖中會形成一個個連通分量，每個連通分量作為一個集合，若相連的這兩個結點分屬于不同的集合，則要進行合并集合的操作，其中壓縮路徑等并查集的算法細節不在此贅述。

3) 在掃描完該層所有積木后，將圖中的連通分量數與積木模型此層的最小集合數setNum[k]作比較。若兩者相等即滿足粘連性要求，若前者大于后者，則需做出局部調整，并輸出局部調整的參考方案以供員工實際搭建時分析。setNum[k]表示一個積木模型在搭建到第k層時所能達到的最小分塊數亦稱最小集合數。即搭建到第k層時，若已搭建部分已具有“整體”性，可形成一個塊時，則setNum[k]值為1；若在第k層還不可能形成一個塊，如搭建一個四條腿支撐的桌子，在未搭建到桌面時，最少也存在四個獨立的積木塊，此時setNum[k]值為4。如圖11所示，圖11是一原始模型的分層效果圖，在圖中顯示了對應層號的最小集合數。

通過積木鋪設與粘連性檢驗兩個算法相互配合，在速度上很好地滿足了要求的同時，也較好地保證了積木模型的整體性。

圖11 模型各層的最小集合數示意圖

5 結 語

積木智能搭建系統的成功使用不僅在一定程度上證明了上述算法的可行性，還較大地縮短了大型模型的搭建時間，降低了人工成本，讓員工可以把更多的精力放到大型模型的內部支架、美觀等其他方面。當然，本系統還有很多有待發展的地方，比如在整個積木模型的內部鏤空、局部及整體的受力分析(如積木倒吊部分是否會影響模型的平衡、懸空部分是否會脫落)等方面還是比較欠缺的。由于這方面專業知識的缺乏，及實際搭建中經常需要在鏤空的大型模型中搭建支架(這些支架可能是一個不銹鋼骨架，也可能是積木)，本系統在這些方面只是給出一個比較粗糙的參考方案，具體還需有經驗的員工自行判斷和修改。對此，可以初步設想，若能賦予每塊積木具體的物理特性，并結合力學、建筑學等方面的知識，則有望推出一個更完美且可運用到其他工程項目的系統。

[1] Gaol F L．Bresenham algorithm:implementation and analysis in raster shape[J]．Journal of Computers,2013,8(1):69-78．

[2] Skala V．An interesting modification to the Bresenham algorithm for hidden-line solution[J]．Computer Graphics Forum,1987,6(4):343-347．

[3] 賈銀亮，張煥春，經亞枝．Bresenham直線生成算法的改進[J]．中國圖象圖形學報,2008,13(1):158-161.

[4] 武廣臣，左建章，劉艷，等．矢量數據柵格化的一種有效方法--環繞數法[J]．測繪科學,2009,34(1):50-51,89.

[5] Wang Y,Li M,Zhang S,et al．Research research on on parallel algorithm for polygon rasterization[C]//Proceedings of the 2012 20th International Conference on Geoinformatics．IEEE Computer Society,2012:1-4．

[6] 陽波，王衛星，魏許青．基于曲線積分的任意多邊形填充算法[J]．計算機工程與應用,2002,38(24):81-85.

[7] 王培珍，許睿．任意多邊形填充新算法[J]．安徽工業大學學報(自然科學版),2009,26(4):405-408.

[8] 王建，杜道生．矢量數據向柵格數據轉換的一種改進算法[J]．地理與地理信息科學,2004,20(1):31-34.

[9] 張毅，李昌華．基于邊界跟蹤的任意形狀區域填充算法[J]．計算機工程與設計,2015,36(3):725-728.

[10] 徐勝攀，劉正軍，左志權，等．一種改進的活性邊表區域填充算法[J]．計算機工程與應用,2014,50(17):178-181.

[11] 周琛，陳振杰，張帥．基于邊界代數法的矢量柵格化并行算法設計與實現[J]．計算機工程與科學,2013,35(4):37-41.

THE RESEARCH AND DESIGN OF THE MAIN ALGORITHMS OF THE INTELLIGENT BUILDING SYSTEM FOR 3D BUILDING BLOCKS MODEL

Cai Hao Yao Xiaohao Gao Zhanpeng Zhang Chengdian

(DepartmentofComputerScienceandTechnology,InstituteofTechnology,ShantouUniversity,Shantou515000,Guangdong,China)

Meeting the need of enterprises,an intelligent building system of building blocks is developed to solve the problems of failing to compute the material in advance and wasting time and energy building by rules of thumb when using building blocks to build large-scale scene model,which solves the whole intelligentialize of importing 3D files,adjusting model,slicing and hierarchy,rasterization and outputting the building scheme of building blocks.Besides,algorithms for the referred problems such as vector diagram rasterization,building blocks laying and the model adhesion checking are proposed and discussed in detail.These algorithms are the kernel of the whole system;experiments show that these algorithms are able to improve the calculating speed of the system,ensuring the model is built correctly.

Building blocks Intelligent building Vector diagram rasterization Building blocks laying Adhesion cheching

2015-11-19。廣東省“揚帆計劃”人才項目(140-14600202)。蔡浩，教授，主研領域：實時系統，軟件工程。姚肖豪，碩士生。高展鵬，碩士生。張承鈿,副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.02.041