李雪艷+華順剛

摘要：對給定的兩個三維模型進行層次構(gòu)建與部件替換，生成一系列新穎的模型。首先對模型進行接觸分析、對稱檢測和層次結(jié)構(gòu)生成；然后通過形狀匹配確保兩個模型生成的層次節(jié)點一對一匹配，進而通過部件替換生成若干模型，最后進行部件連接確保模型的接觸合理性。實驗表明，該方法可以快速生成一系列與原模型在外觀上有所不同，但具有類似的對稱和鄰接結(jié)構(gòu)的新模型。

關(guān)鍵詞：層次結(jié)構(gòu)；形狀匹配；部件替換；部件連接

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）25-0184-04

Abstract： A series of novel 3D models are generated based on given two models by constructing their hierarchy structures and replacing parts. First the shape analysis is implemented ，which involves contact analysis， symmetry detection and hierarchy structure generation. Then a one-to-one node mapping is established by shape matching，and new models could be generated by part replacement. Finally， parts is connected to ensure the contact reasonability of the generated model. Experiment results show that the method is competent to quickly generate varies of novel models which are similar to the original model in symmetry and adjacent structure， but different in appearance.

Key words： hierarchy structure； shape matching； part replacement； part connection

隨著3D建模技術(shù)、模型分割技術(shù)及在線3D模型庫的發(fā)展，三維模型創(chuàng)新設(shè)計已成為一個熱門研究領(lǐng)域，如何管理、重用現(xiàn)有網(wǎng)格模型，如何根據(jù)新的設(shè)計目標修改已有模型，現(xiàn)已成為三維建模的研究熱點，三維模型的設(shè)計思路將從傳統(tǒng)的軟件建模，發(fā)展為快速尋找并重用現(xiàn)有模型進行模型生成。

由于傳統(tǒng)的3D建模比較繁瑣，近年來，一些利用已有模型進行模型生成的方法已被提出。Thomas等[1]提出了一種數(shù)據(jù)驅(qū)動合成方法，來構(gòu)建三維幾何表面模型，基于部件的幾何相似性，通過交換將模型的部件進行融合與匹配，利用智能剪裁分割出所需部件的網(wǎng)格模型，并按照相應(yīng)的方式將他們組合在一起生成新的三維模型。此方法只允許沿著現(xiàn)有網(wǎng)格的頂點和邊緣進行分割與連接，不能自適應(yīng)地分割三角形。Karevoy等[2]設(shè)計的一個模型生成系統(tǒng)（The Shuffler System），考慮部件的幾何相似性和部件的接觸信息，允許用戶加載一組人工選定的兼容的三維模型，并快速交換模型之間的相似部分。該系統(tǒng)依賴于一種所有模型都兼容的分割方法，只能用于用戶的當前模型不能用于其他模型，需要用戶控制生成模型的形狀以確保其合理性。Siddhartha等[3]提出了一種利用統(tǒng)計幾何處理技術(shù)來進行數(shù)據(jù)驅(qū)動建模的方法，該方法支持開放階段的建模過程，利用形狀檢索和形狀對應(yīng)，從簡單的三維模型中獲取一些組件，這些組件能被添加到設(shè)計者的當前模型中，激發(fā)設(shè)計者的創(chuàng)作靈感，但算法只考慮了幾何屬性，沒有考慮部件的語義功能。Talton等[4]的探索性建模系統(tǒng)適用于數(shù)據(jù)驅(qū)動的方法來支持開放式三維建模。它依賴于一個參數(shù)化空間，在這個空間中設(shè)計新的三維模型。Bokeloh等[5] 對三維模型進行分析，提取潛在的對接部位，使有意義的逆過程建模變的可能。徐凱等人[6]提出通過使用圖像輪廓線約束變形零件，利用圖像激發(fā)3D模型創(chuàng)作。形狀生成的另一種方法[7]是基于統(tǒng)計模型創(chuàng)建實例，這是一種常用的紋理生成方法，將模型分解為多個紋理元素，然后重新組合這些元素生成新的模型。當生成的模型有一個復雜的層次結(jié)構(gòu)時，基于局部相似性的統(tǒng)計模型是無效的。

本文通過計算已分割模型部件間的對稱和接觸關(guān)系，由粗糙到精細構(gòu)建模型層次結(jié)構(gòu)；然后根據(jù)位置信息對層次中的節(jié)點進行匹配以及層次結(jié)構(gòu)的再生成；接著進行部件替換，生成新的模型；最后通過部件連接確保部件間合理接觸。本文方法進一步簡化了建模接口，不用直接操縱幾何形狀，能夠在已有模型庫的基礎(chǔ)上自動、有效地生成一系列新模型。

1 形狀分析

要實現(xiàn)模型的重組，首先對單個模型進行形狀分析，包括接觸分析、對稱檢測和層次結(jié)構(gòu)生成。整個形狀分析過程如圖1所示。

由于模型分割技術(shù)的不斷發(fā)展，現(xiàn)已存在大量的已分割模型庫。為便于分析，首先對模型進行規(guī)則化處理，使其具有一致的主軸方向；進而采用將模型包圍盒的最長邊縮放為1的方法對模型進行歸一化處理，使模型縮放的一個立方體內(nèi)，采用的包圍盒是Axis-aligned bounding box （AABB）包圍盒，該包圍盒是與坐標軸對齊的包圍盒， 構(gòu)造簡單，存儲空間小，且能達到本文所需要求，故采用此包圍盒。

1.1 接觸分析

部件間的接觸點描述一個模型的連接關(guān)系，找到模型中各部件的接觸關(guān)系，并保存接觸點，為后續(xù)分層和形狀匹配做準備。接觸分析過程如下所述。

由于每個三維網(wǎng)格模型都包含大量的三角面片，若直接計算兩部件間三角面片是否有接觸，計算量較大。為了提高程序運行效率，首先判斷兩部件的AABB包圍盒是否接觸，由于該包圍盒包圍物體時不緊致，即便兩包圍盒有重疊，還不能直接斷定兩部件有接觸，需要進一步判斷兩部件的三角面片是否有接觸。判斷兩三角面片T1（來自部件1）和T2（來自部件2）是否接觸的流程圖如圖2所示：

其中判斷交點是否在T2內(nèi)采用的是同向法。假設(shè)三角面片的三個頂點為ABC，當沿著ABCA的方向在三條邊上行走時，若點P始終位于邊AB，BC和CA的同側(cè)，則點P就在三角形內(nèi)。利用叉積來判斷P是否位于三個邊同側(cè)，連接PA，將PA和AB做叉積，再將CA和AB做叉積，若兩個叉積的結(jié)果方向一致，那么兩個點在同一側(cè)。用點積判斷兩個向量是否同向，若點積結(jié)果同為1，則兩向量同向，否則，兩向量不同向。

按照上述過程遍歷兩部件的所有面片，將T1中與T2相交線段的兩個端點中距離T2較近的端點作為接觸點保存起來。遍歷模型的所有部件，保存所有的接觸部件和相應(yīng)的接觸點。

1.2 對稱檢測

對稱檢測是計算機圖形學領(lǐng)域的熱點問題，其廣泛應(yīng)用于三維幾何模型的形狀匹配、檢索、對準、重網(wǎng)格化、模型分割等領(lǐng)域。對稱性通常被視作連接三維形狀低層幾何屬性和高層語義信息的橋梁，對稱作為一種幾何屬性，其定義和檢測可以完全基于幾何信息，同時對稱性對于模型結(jié)構(gòu)和語義分析具有重要作用[8]。本文利用對稱性對模型進行分層細化，并利用層次節(jié)點的對稱來簡化部件替換過程，提高程序的運行效率。

由于已將模型主軸方向處理一致，把x=0面作為對稱面，只需計算x=0面的兩側(cè)是否存在對稱部件?？筛鶕?jù)兩部件的AABB包圍盒是否對稱來判斷兩個部件是否對稱。對稱檢測步驟如下：

1）判斷兩部件的AABB包圍盒的中心距離是否小于某個閾值，若小于閾值則進行步驟（2），否則，可判定兩部件不對稱。

2）判斷兩部件AABB包圍盒的對角線向量的夾角和長度是否分別小于某個閾值，若均小于各自的閾值，則兩部件對稱，否則兩部件不對稱。

經(jīng)過實驗驗證分析，將兩部件AABB包圍盒中心距離的閾值threshold1設(shè)定為0.01，包圍盒對角線夾角的閾值threshold2設(shè)定為5?，包圍盒對角線長度的閾值threshold3設(shè)定為0.01，可正確檢測出模型中存在的對稱部件。

1.3 層次結(jié)構(gòu)生成

此過程為模型生成由粗糙到精細的層次結(jié)構(gòu)，每一個層次包括若干個層次節(jié)點N，該節(jié)點由若干個相互連接的部件組成，并利用對稱檢測找到節(jié)點N的對稱節(jié)點，記錄節(jié)點N的各種信息，如節(jié)點中心、節(jié)點大小、父節(jié)點等，用于形狀匹配。層次結(jié)構(gòu)生成的流程圖如圖3所示：

用k表示層次結(jié)構(gòu)的層號（k=0，1，2…n）。當k=0時，表示第0層，包含一個節(jié)點，這個節(jié)點包括模型的所有部件。當由較粗糙層k生成較精細的層次k+1時，將k層上的每個父節(jié)點分割成兩個子節(jié)點，并把生成的子節(jié)點分配到k層上。若節(jié)點中存在對稱的部件，分割時將把對稱信息考慮在內(nèi)，把對稱的部件分別分配給兩個子節(jié)點。若某些部件的中心距離分割平面非常近，則認為這些部件的中心位于分割平面上，并將這些部件添加到第三個節(jié)點中去。分割操作后，若父節(jié)點至少生成了兩個子節(jié)點，并且每個子節(jié)點至少包含一個部件，則認為分割操作是成功的。若父節(jié)點中不存在對稱的部件，或父節(jié)點中存在對稱的部件，但基于對稱面的分割操作不成功，則將父節(jié)點坐標系中的x=0面作為分割面，若此分割操作仍然不成功，則依次將y=0面、z=0面作為分割面進行分割。如果按任何一個分割面分割都不成功，則這個父節(jié)點只生成一個子節(jié)點，且包含父節(jié)點的所有部件。若分割成功，計算并保存每個子節(jié)點對應(yīng)的節(jié)點信息。對稱檢測也將在每個子節(jié)點中進行，并記錄節(jié)點中對稱的部件。

由于在層次生成的過程中沒有考慮部件間的接觸信息，一個子節(jié)點中包含的部件可能是分離的。例如子節(jié)點中的一個或多個部件與其他部件不連接，這就需要重新調(diào)整層次k的節(jié)點，確保每個節(jié)點所包含的部件都是接觸的。這一過程的步驟如下：

1）根據(jù)記錄的部件間接觸信息，重新調(diào)整k層的節(jié)點，原節(jié)點中如果存在分離的部件，則將原節(jié)點分成兩個或多個節(jié)點。

2）為保證新生成的節(jié)點與原來的節(jié)點數(shù)目相同，需要對節(jié)點進行合并。將節(jié)點按體積大小排序，把體積最小的節(jié)點與其接觸的體積也較小的節(jié)點進行合并。

通過以上分離和合并步驟，再次生成的每個節(jié)點所包含的部件都是一個整體，不再存在部件與部件間分離的情況。迭代進行以上分層過程，直至某個層次的每個節(jié)點都不能再進行分割，則層次構(gòu)建結(jié)束。至此，形狀分析過程完成，其結(jié)果將用于形狀匹配。

2 形狀合成

單個模型的形狀分析完成后，對兩個模型之間的形狀進行合成，形狀合成包括形狀匹配、部件替換和部件連接三個部分。

2.1 形狀匹配

一般情況下，兩個模型所含的部件個數(shù)是不同的，所以部件間很難形成一對一的匹配。顯然，由不同部件個數(shù)構(gòu)成的模型生成的層次結(jié)構(gòu)也不能實現(xiàn)一對一匹配，這就需要調(diào)整兩個模型層次結(jié)構(gòu)中每層的節(jié)點個數(shù)，以便形成節(jié)點間一對一匹配。如圖4（a）所示，S1汽車模型作為原模型，S2卡車模型作為目標模型、每個模型的節(jié)點個數(shù)是相同的，但是為了形成一對一匹配，汽車車身將與卡車的兩個部件卡車車身和尾部的一個輪胎相匹配，這樣就會造成不合理的匹配。圖4（b）是在匹配的過程中，為了適應(yīng)S1的層次節(jié)點為S2生成的新的層次節(jié)點。

形狀匹配算法實現(xiàn)過程如下所述：

1）構(gòu)造一個與原形狀S1完全相同的層次結(jié)構(gòu)LS，使其每個節(jié)點都為空節(jié)點，得到一個與S1的層次結(jié)構(gòu)完全對應(yīng)的空層次結(jié)構(gòu)，使其在形狀匹配過程中起到紐帶作用。

2）根據(jù)最鄰近匹配原則，將目標形狀S2在各層節(jié)點所包含的部件分配到與其對應(yīng)層的對應(yīng)節(jié)點，即將與原層次節(jié)點中心距離最近的目標層次節(jié)點的部件分配到新構(gòu)造的層次結(jié)構(gòu)的對應(yīng)層的對應(yīng)節(jié)點。如果在原節(jié)點中有兩個節(jié)點距離同一個目標節(jié)點都最近，則判斷目標節(jié)點距離哪一個原節(jié)點最近，將目標節(jié)點與其距離最近的原節(jié)點相匹配，并將目標節(jié)點所包含的部件添加到與原節(jié)點相對應(yīng)的LS的節(jié)點中，這樣與未被匹配的原節(jié)點相對應(yīng)的LS節(jié)點就是空節(jié)點了。

3）新生成的層次結(jié)構(gòu)中有空節(jié)點存在，將空節(jié)點移除，并將對應(yīng)的原層次和目標層次節(jié)點合并到具有共同父節(jié)點且接觸的節(jié)點里。如果對應(yīng)的原層次或目標層次節(jié)點沒有與其共享父節(jié)點的節(jié)點，則將其合并到當前層體積最小且與其接觸的節(jié)點里。

對各個層次進行迭代，使S1和S2層次結(jié)構(gòu)完全相同，每層的節(jié)點一一對應(yīng)。模型的形狀匹配過程如圖5所示：

2.2 部件替換

形狀匹配后，在層次結(jié)構(gòu)的最精細層（最后一層）進行部件替換，，通過替換兩個模型層次結(jié)構(gòu)中最后一層相匹配的節(jié)點來生成新的形狀。部件替換時要控制替換順序，進而有規(guī)律的生成若干模型。具體的部件替換控制方法如下所述：

通過設(shè)置一個權(quán)重[0，1]來生成新的模型 S（），其中新生成的模型S（0）=S1，S（1）=S2，。在形狀生成的過程中，S1的部件只能被S2的部件替換一次，并且不再進行逆替換。這個過程通過以下方法來完成，用表示一個層次結(jié)構(gòu)的第k層有n個節(jié)點，實例化一個新模型時令個節(jié)點來自S2，剩余的節(jié)點來自S1，這樣就能控制哪個模型的哪個節(jié)點被替換，有規(guī)律的生成若干模型。如果兩個節(jié)點是對稱的，則其同時被實例化或不被實例化。

在替換的過程中，隨著的增大，索引小的節(jié)點將首先被實例化，為了使實例化時按照一定的規(guī)律生成新模型，將原模型S1最后一層的節(jié)點按照節(jié)點體積由大到小排序，同時將目標模型S2的最后一層也作相應(yīng)的調(diào)整，以保證節(jié)點索引一一對應(yīng)。這樣體積大的節(jié)點將首先被實例化，新生成的模型將逐漸由S1向S2過渡。

2.3 部件連接

通過部件替換生成的新模型，由于不同部件的尺寸，坐標位置不同，替換的部件放置的位置可能不合理，這就需要重新調(diào)整部件放置的位置。用代表兩個部件間一系列接觸點的集合，如果部件j在當前節(jié)點中，部件k在另一個節(jié)點中，則每個節(jié)點與其連接的節(jié)點的接觸點P通過以下公式求得：

其中為求得的部件j和部件k的接觸點。如果原模型S1的部件j被目標模型S2的部件h替換，則將h所在節(jié)點對應(yīng)的接觸點平移到接觸點，并將h所在的節(jié)點作相同的平移，實現(xiàn)部件h和部件k良好接觸。

3 實例驗證

在Visual Studio2010開發(fā)平臺下，采用C#編程對本文算法進行實例驗證。下面以兩個飛機模型為例詳細講解

本方法的實現(xiàn)過程， fighter1、fighter2的層次構(gòu)建結(jié)果分別如圖6、圖7所示：

由圖6 fighter1層次結(jié)構(gòu)的第1層（即k=0）包括一個節(jié)點，這個節(jié)點包含模型的所有部件。節(jié)點中存在三對對稱的部件，按對稱平面將模型分割，得到k=1層上的三個節(jié)點，第1個節(jié)點包含右上、下羽翼和右引擎三個部件；第2個節(jié)點包含一個軀干部件，第3個節(jié)點包含左上、下羽翼和左引擎三個部件，利用對稱檢測得出節(jié)點1與節(jié)點3是對稱的。接著再分割k=1層的節(jié)點，由于三個節(jié)點中不存在對稱的部件，則先按x=0面分割，由于節(jié)點1包含的三個部件的中心位置都在x=0面的右側(cè)所以導致分割不成功，再按照z=0面分割，由于右上羽翼與右引擎的中心都在z=0面的上方，這兩個部件被分配到同一個節(jié)點中，右下羽翼的中心在z=0面的下方，被單獨分配到另一個節(jié)點中去。同理，節(jié)點3也被分割成了兩個節(jié)點。第2個節(jié)點只包含一個部件，因此不必再被分割。隨著k=1層的節(jié)點被分割完畢，k=2層的節(jié)點完全生成了。按照以上過程依次生成第3、第4層的節(jié)點。圖6中第4層中的每個節(jié)點都只包含一個部件，模型fighter1的層次結(jié)構(gòu)構(gòu)建完畢。

Fighter2層次結(jié)構(gòu)生成過程與fighter1類似，不同之處在于對其層次結(jié)構(gòu)的第2層進行了節(jié)點的再生成。第1層的節(jié)點中存在四對對稱的部件，按照對稱軸進行分割，得到圖7中a、b、c三個節(jié)點，由于節(jié)點a和c中包含的部件存在分離現(xiàn)象，所以要重新劃分節(jié)點，確保節(jié)點中包含的部件都接觸。重新劃分后，由節(jié)點a得到節(jié)點d和e，由節(jié)點c得到節(jié)點f和g。為了使節(jié)點個數(shù)與剛分割時的節(jié)點個數(shù)相同，需要對有接觸部件的某些節(jié)點進行合并。將節(jié)點d、e、f、g、b按體積大小排序，使節(jié)點體積小的節(jié)點和與其有接觸部件的節(jié)點合并，如果其與多個節(jié)點都有接觸的部件，則將其合并到體積較小的節(jié)點中。由于節(jié)點e的體積最小，并且其只與b有接觸，所以將節(jié)點e合并到節(jié)點b中；由于節(jié)點f與節(jié)點e對稱，節(jié)點f也同時被合并到節(jié)點b中，合并之后得到三個節(jié)點，與剛分割時的節(jié)點個數(shù)相同，停止合并。通過節(jié)點的重劃分和再合并生成了圖7中k=1層的三個節(jié)點，它們包含的部件都是相互接觸的，說明節(jié)點再生成完畢。

fighter1與fighter2層次結(jié)構(gòu)中最后一層的匹配結(jié)果如圖8所示：

圖8中節(jié)點索引按照體積大小得到，當索引為0時，代表節(jié)點體積最大，替換時將首先被替換。圖中1 和2，3和4，5和6分別對稱，節(jié)點替換時對稱的節(jié)點將被同時替換。fighter1與fighter2模型重組的結(jié)果如圖9所示：

fighter1與fighter2模型重組之后得到的部分新模型接觸不合理，如圖9所示的shape1，左、右下羽翼與軀干沒有接觸。對模型進行部件連接后得到的結(jié)果如圖10所示，可以看出模型部件間接觸良好。

圖11為若干模型重組結(jié)果實例，重組結(jié)果顯示本文方法可以較好地實現(xiàn)兩個來自同類模型集中模型間的重組，生成的新模型較為合理。

4 結(jié)論

本文實現(xiàn)了一種基于部件替換的三維模型生成方法。在形狀分析階段中考慮了單個模型部件間的接觸和對稱關(guān)系，并為每個模型生成一個由粗糙到精細的層次結(jié)構(gòu)；形狀匹配過程通過節(jié)點中心的位置關(guān)系實現(xiàn)節(jié)點一對一匹配；部件替換時通過節(jié)點體積大小和權(quán)重來控制新生成的模型形狀；對新模型進行部件連接以實現(xiàn)節(jié)點間合理接觸。由于匹配時僅考慮位置信息，所以本文方法對部分同模型集的模型適用，對一些比較復雜或不同模型集中的模型難以適用，可能會導致重組生成的新模型在結(jié)構(gòu)上不合理。下一步研究將通過增加一些約束條件優(yōu)化本文算法，使其適用于更多更復雜的模型，使重組后生成的新模型更加合理且更加多樣化。

參考文獻：

[1] Funkhouser T， Kazhdan M， Shilane P， et al. Modeling by example[J]. In Proc. SIGGRAPH ，2004，23（3）：652–663.

[2] Kraevoy V， Julius D， Sheffer A. Shuffler： Model composition from interchangeable components[J]. In Proc. Pacific Graphics ，2007， 129–138.

[3] Chaudhuri S， Koltun V. Data-driven suggestions for creativity support in 3d modeling[J] ACM Trans. Graph. ，2010，29（6）：183–183.

[4] Talton， J.O，Gibson， Yang， L， et al. Exploratory modeling with collaborative design spaces[Z]. ACM Trans. Graph. 2009.

[5] Bokeloh M， Wang M， Seidel H. A connection between partial symmetry and inverse procedural modeling[J]. In ACM （Siggraph） ，2010， 29（4） ：104：1–104：10.

[6] Xu K， Zheng H， Zhang H， et al. Photo-inspired model-driven 3d object modeling[J].ACM Siggraph，2011，30（4）：80：1-80：10.

[7] Efros A， Leung T. Texture synthesis by nonparametric sampling[J]. In Proc. ICCV ，2002， 2： 1033–1038.

[8] Mitra N， Pauly M， Wand M， et al. Symmetry in 3D geometry： Extraction and applications[R]. In Proceedings of Euro graphics STAR Report 2012.