蔡 浩 姚肖豪 高展鵬 張承鈿

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

積木3D模型智能搭建系統(tǒng)主要算法的研究與設(shè)計

蔡 浩 姚肖豪 高展鵬 張承鈿

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

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

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

0 引 言

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

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

1 邏輯流程

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

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

圖2 搭建流程圖

步驟1 導(dǎo)入被搭建物體的原始模型3D數(shù)據(jù)，本系統(tǒng)采用3ds格式文件，主要獲取其形狀、色彩等數(shù)據(jù)。

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

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

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

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

步驟6 將搭建方案數(shù)據(jù)保存至文件，以供重復(fù)使用。

2 模型的顆粒化

整個模型的顆?；枰獙δＰ透北舅蟹謱拥氖噶慷噙呅芜M行柵格化。矢量數(shù)據(jù)與柵格數(shù)據(jù)之間的轉(zhuǎn)換方法前人已有很多的研究，并應(yīng)用在很多方面，如在地理信息系統(tǒng)(GIS)中，矢量數(shù)據(jù)與柵格數(shù)據(jù)間的轉(zhuǎn)換就是其基本功能之一?，F(xiàn)今，矢量數(shù)據(jù)的柵格化，對點、線而言，并不存在什么難題，如線的柵格化常用算法有DDA法(數(shù)字微分分析法)、Bresenham算法等。而面的柵格化算法也有多種，如常見的有內(nèi)部點擴散法、邊界代數(shù)法(BAF-Boundary Algebra Filling)、邊界點跟蹤算法、射線法、掃描法等，再如近年提出的一些方法，武廣臣等提出的環(huán)繞數(shù)法[4]、張毅等提出的基于邊界跟蹤的填充算法[8]等。上述現(xiàn)有的柵格化算法都有各自的優(yōu)缺點，并非都能很好地適用于此項目的模型顆?；瘑栴}。在GIS中矢量數(shù)據(jù)轉(zhuǎn)換成柵格數(shù)據(jù)之前需要根據(jù)數(shù)據(jù)精度和數(shù)據(jù)量等來確定柵格尺寸的大小，然而在本系統(tǒng)中，積木的最小顆粒度即1×1的積木的大小是固定的。固定的柵格尺寸及可能出現(xiàn)的局部高精度密集矢量數(shù)據(jù)，是選擇柵格化算法時首先必須考慮的問題。

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

本搭建系統(tǒng)在應(yīng)用現(xiàn)有邊線柵格化算法的基礎(chǔ)上，設(shè)計出完整的處理多個多邊形交叉疊加并染色的柵格化算法。

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

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

圖3 根據(jù)斜率劃分的8個象限

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

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

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

圖4 多邊形柵格化后出現(xiàn)“洞”的情形

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

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

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

3 單層積木鋪設(shè)

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

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

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

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

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

圖6 “L型拐”積木樣例

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

表1 積木基本顆粒鋪設(shè)優(yōu)先級

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

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

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

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

(a)

(b)

(c)

(d)

圖8 “單粒”與“L型拐”相接的4種調(diào)整方案

由于上下層粘連檢驗的需要，平面中每個柵格的信息除了顏色還需包含鋪設(shè)積木的編號和類型。調(diào)整“單?！睍r，這些信息都應(yīng)做出相應(yīng)的改變。

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

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

4 上下層粘連性檢驗

圖9 上下層積木交叉相扣

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

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

圖10 兩種優(yōu)先級鋪設(shè)結(jié)果對比

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

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

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

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

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

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

圖11 模型各層的最小集合數(shù)示意圖

5 結(jié) 語

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

[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] 賈銀亮，張煥春，經(jīng)亞枝．Bresenham直線生成算法的改進[J]．中國圖象圖形學(xué)報,2008,13(1):158-161.

[4] 武廣臣，左建章，劉艷，等．矢量數(shù)據(jù)柵格化的一種有效方法--環(huán)繞數(shù)法[J]．測繪科學(xué),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] 陽波，王衛(wèi)星，魏許青．基于曲線積分的任意多邊形填充算法[J]．計算機工程與應(yīng)用,2002,38(24):81-85.

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

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

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

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

[11] 周琛，陳振杰，張帥．基于邊界代數(shù)法的矢量柵格化并行算法設(shè)計與實現(xiàn)[J]．計算機工程與科學(xué),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)。蔡浩，教授，主研領(lǐng)域：實時系統(tǒng)，軟件工程。姚肖豪，碩士生。高展鵬，碩士生。張承鈿,副教授。

TP3

A

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