一種任意拓撲的多邊形網格模型融合方法

2023-10-05 13:13:04 1

專利名稱：：一種任意拓撲的多邊形網格模型融合方法
技術領域：
：本發明涉及計算機才莫型處理技術，特別是涉及一種任意拓樸情況的多邊形網格模型融合方法。
背景技術：
：三維物體融合通過將已有物體的部件無縫地拼接在一起以構造出兼有它們特徵的新模型，提供了一種操作簡潔、功能強大的造型工具。在早期，一些研究人員提出運用參數化技術建立待融合物體邊界處影響區域之間的映射關係，然後對影響區域進行混合處理以達到光滑拼接，參見T.Kanai.H.Suzuki,J.MitaniandF.Kimura.Interactivemeshflisionbasedonlocal3Dmetamorphosis.InProceedingsofGraphicsInterface,1999，pp148-156。近年來，微分域多邊形網格處理技術的發展為實現融合操作提供了新思路。在建立邊界之間的對應關係後，將對應邊界變換到一致的形狀並將變換擴散到對應邊界的影響區域產生一個漸變的過渡，由於僅需建立邊界之間的對應關係，這種方法可以4艮好地適用於虧^f各不為0的物體間的融合，參見Y.Yu.K.Zhou,D.Xu.X.Shi.H.Bao，B.GuoandH.Shum.MesheditingwithPoisson-basedgradientfieldmanipulation.ACMTransactionsonGraphics23(3):664-651.2004以及O.Sorkine，Y.Lipman，D.Cohen-Or,M.Alexa,C.RossiandH.P.Seidel.Laplaciansurfaceediting.InProceedingsofEUROGRAPHICS/ACMSIGGRAPHSymposiumonGeometryProcessing,pp179-188.2004。但無論是基於參數化技術的方法還是基於微分域多邊形網格處理的方法，都採取將待融合物體的邊界直接拼接在一起，然後對邊界附近定義的影響區域進行特定操作以實現光滑拼接的策略，因而這些策略只能處理兩個對應邊界之間的融合，而無法處理多個邊界的同時融合。
發明內容本發明提供一種任意拓樸的多邊形網格模型融合方法，在於解決現有多邊形網格模型融合方法存在的拓樸限制問題。一種任意拓樸的多邊形網格模型融合方法，包括以下步驟1)從已有模型上截取感興趣的部件；2)基於過渡基元的物體定位用戶在已有多邊形網格模型上截取感興趣部件，在過渡基元的輔助下將它們變換到用戶滿意的方位。所述的過渡基元是一個大致表示中間過渡物體形狀的簡單幾何體如球、圓柱、圓臺等，待融合物體圍繞過渡基元放置；3)基於草圖的輪廓勾勒提供基於草圖的接口以方便用戶指定中間過渡物體的輪廓形狀，用戶在屏幕空間用滑鼠大致勾勒出過渡物體的輪廓，系統自動確定出輪廓線的深度信息，並變換到世界坐標系，隨後這些輪廓被轉化為位置約束和法向約束並添加到變分隱式曲面構造中；4)基於變分隱式曲面的過渡物體描述採用變分隱式曲面定義中間過渡物體，將待融合的部件連接在一起以處理各種拓樸情況下的融合問題，在融合邊界處引入位置約束和法向約束以實現邊界的光滑過渡；5)局部化移動立方體等值面抽取將指定空間剖分為立方體，並根據定義的隱函數進行採樣；根據立方體的採樣信息以及待融合物體的信息對立方體分類；在有效立方體上應用保拓樸的移動立方體算法抽取等值面；採用最優橋接三角化實現過渡網格與待融合物體的無縫連接；對過渡區域進行重新網格化改善網格質量。對於每個^寺融合物體，我們定義一個方向n=nAowW+wxnw,式中ntam/和n"分別表示邊界和整個待融合物體的方向，分別通過對邊界的所有頂點和整個待融合物體的所有頂點進行主元分析得到。用戶在過渡基元上指定物體將要移到的位置G，由^可以確定一個目標方向i1,^,,接著系統將自動計算得到一個剛性變換，物體通過變換後，C,變換到G位置，n變換到n,^,。採用變分隱式曲面定義中間過渡物體將待融合的部件連接在一起以方便處理各種拓樸情況下的融合問題，在融合邊界處引入位置約束和法向約束以實現邊界的光滑過渡。我們首先為所有邊界點及邊界的"-環點(記這些點的集合為F"按列出方程，函數值取/>0,這樣可^U呆證過渡曲面精確插值給定的邊界。此外，為了保證過渡光滑，我們還必須引入法向約束，對於7*中的每個點v,我們沿其法向n,偏移一定距離得到一個新點^+zn,,將該點加入線性系統中，賦予函數值/;-r。r為一個很小的實數，我們取r-0.U^，Zmin為所有邊界上最短的邊長。提供基於草圖的接口以方便用戶指定中間過渡物體的輪廓形狀用戶在屏幕空間用滑鼠大致勾勒出過渡物體的輪廓，系統自動找到兩個離該輪廓線端點最近的開口j和B,並在兩個開口上分別確定離輪廓線端點最近的點p、Q;然後引入兩個平面投影平面Q和深度平面n:深度平面n經過點P、Q和^L點，記其法向為n。，用於進一步調整輪廓線的深度變化。投影平面Q經過點P、Q,其法向為n。i^x帀，描述當前角度下輪廓線的形狀；接著，用戶所繪輪廓線被投影到由深度平面上的貝賽兒曲線沿nn掃略得到的曲面上。系統自動確定出輪廓線的深度信息，並變換到世界坐標系；隨後用戶勾勒的過渡物體輪廓被轉化為位置約束和法向約束並添加到變分隱式曲面構造中，對於輪廓線上的點，它們的法向可以通過對確定輪廓線的開口上的兩個點P和Q的法向通過沿輪廓線進行弧長插值得到。採用一個局部化移動立方體算法將變分隱式曲面轉化為三角網格表示在算法上，要求只多邊形化隱式曲面上感興趣的部分，為此必須對剖分後的立方體進行歸類，然後對每種立方體〗吏用不同的處理方法。由於只對VS-Cube進行多邊形化，在給定模型和生成的網格間那些BS-Cube所佔據的區域會存在一個空白帶，必須對這個條帶進行三角化從而將所有網格曲面連成一個整體。本發明針對現有的多邊形網格模型融合方法存在的拓樸限制，以及邊界形狀不能差異太大等缺點，採用了一種通過構造中間過渡物體來融合給定的多個部件的技術方案，本發明算法明確，界面友好，結果魯棒，該方法可以用於遊戲、影視中的角色設計。圖1為本發明的技術方案流程圖；圖2圖1中基於過渡基元的物體定位處理過程圖；圖3圖1中基於草圖的輪廓線勾勒的處理過程圖；圖4圖1中局部化移動立方體算法具體組成圖；圖5圖1中立方體分類的組成圖。具體實施方式一種適合於任意拓樸的多邊形網格模型融合方法，用戶從已有模型上分割出感興趣的部件，接著在過渡基元的輔助下將各個部件變換到合適的方位，然後用戶用滑鼠在屏幕上勾勒出中間過渡物體的輪廓，隨後算法生成一個變分隱式曲面表示的、精確插值邊界位置和法向約束、符合用戶所描繪輪廓的中間過渡物體，最後通過一個局部化移動立方體方法自動抽取出過渡曲面上所需保留的部分並實現與待融合物體的無縫連接，具體流程參見圖1。本發明實施的關鍵有四點基於過渡基元的物體定位、基於變分隱式曲面的過渡物體描述、基於草圖的輪廓勾勒、局部化移動立方體等值面抽取。下面具體介紹關^fc的實現細節1.基於過渡基元的物體定位對於每個待融合物體，我們定義一個方向式中和n"分別表示邊界和整個待融合物體的方向，分別通過對邊界的所有頂點和整個待融合物體的所有頂點進行主元分析得到，首先我們按下式構造協方差矩陣CVM:formulaseeoriginaldocumentpage7記4$;122義3為CVM的特徵值，7,^,5為對應的單位特徵向量，則i^"和定義如下formulaseeoriginaldocumentpage7formulaseeoriginaldocumentpage7。*v,式中C,，Cp分別是邊界和物體的重心。w'g"(x)為符號函數formulaseeoriginaldocumentpage7用戶在過渡基元上指定物體將要移到的位置cr，由cr可以確定一個目標方向n,^,，接著系統將自動計算得到一個剛性變換，物體通過變換後，Cfl變換到CV位置，n變換到n,唚,。物體定位的示意圖見2。2.基於草圖的輪廓勾勒我們設計了一個草圖接口來描述待生成過渡曲面的輪廓形狀，並將這些輪廓線轉化為變分曲面的位置約束和法向約束。在一般的基於草圖的自由造型系統中，用戶所繪製的線條都在同一個深度平面上，同時也不需要太多地考慮上下文環境(這裡，上下文環境指的是造型系統中已存在的一些會對解析新繪製的線條所反映用戶意圖產生影響的物體)，而在網格融合框架下，繪製的線條往往不會僅簡單的處於一個深度平面上，即必須考慮深度變化的連續性問題。我們設計了一個比較新穎的構造方法，如圖3所示。首先用戶在屏幕上繪製出一條2維輪廓線，系統自動找到兩個離該輪廓線端點最近的開口^和5，並在兩個開口上分別確定離^"廓線端點最近的點P、Q;然後我們引入兩個平面投影平面Q和深度平面n:深度平面n經過點P、Q和一見點，記其法向為iin，用於進一步調整輪廓線的深度變化。投影平面Q經過點P、Q,其法向為n。-i^x巧，描述當前角度下輪廓線的形狀；接著，用戶所繪輪廓線被投影到由深度平面上的貝賽兒曲線沿nn掃略得到的曲面上。然後可以在兩個平面上分別對投影后的輪廓線進行調整，對於投影平面，我們設計了一個光順工具讓方便用戶對輪廓線進行光順直到滿意，對於深度平面，用戶可以通過調整貝賽兒曲線的兩個控制頂點來改變形狀，從而改變輪廓線的深度變化，而固定其餘控制點從而保證深度變化與邊界處光滑連續。3.基於變分隱式曲面的過渡物體描述在用戶指定了滿意的輪廓線約束後，我們就可以構造一個光滑連接所有待融合物體並符合給定輪廓的變分曲面。過渡曲面的形狀由邊界約束和用戶指定的輪廓約束所決定，我們首先為所有邊界點及邊界的w-環點(記這些點的集合為")按列出方程，函數值取O,這樣可以保證過渡曲面精確插值給定的邊界。此外，為了保證過渡光滑，我們還必須引入法向約束，對於*中的每個點v,我們沿其法向n,.偏移一定距離得到一個新點v,+w,將該點加入線性系統中，賦予函數值/;-r。r為一個很小的實數，我們取r=0.1Am，A^為所有邊界上最短的邊長。對於輪廓線上的點，它們的法向可以通過對確定輪廓線的開口上的兩個點P和Q的法向通過沿輪,卩線進行弧長插值得到。才艮據給定的插值約束/(c,)",，我們可以列出如下的方程由於這個方程只'是未知數(A,和函數/7的係數)的線性方程，所以可以用一個線性系統來求出未知數來。設c,表示點，A表示一c,-c」)，則線性方程可以用矩陣表示tableseeoriginaldocumentpage9從上可以看出該線性系統是對稱和半正定的，所以總存在一個唯一的解。需要注意的是上面矩陣的條件數隨著約束點的增加而增加，這樣就會增加系統的不穩定性，但是我們的應用中約束點只是待融合物體邊界上的點，數目不會^f艮大，所以沒有給我們的過渡曲面帶來影響。4.局部化移動立方體等值面抽取局部化移動立方體算法的整個過程見圖4。我們的方法是在原始移動立方體方法上進一步擴展得到的。移動立方體算法的核心思想是首先將隱式曲面所處的特定空間剖分成立方體子空間，對於每個立方體，根據其八個頂點的內外標誌進行多邊形化。不同於傳統的移動立方體方法，我們的算法要求只多邊形化隱式曲面上感興趣的部分，為此我們必須對剖分後的立方體進行歸類，然後對每種立方體使用不同的處理方法。如圖5所示我們的算法將立方體分為4類*E-Cube:如果一個立方體的八個節點全部位於曲面的內/外部，則該立方體將不會包含任何三角片，稱之為E-Cube,其餘的立方體則稱為S-Cube,S-Cube又可以進一步分為下面的三類BS-Cube、VS-Cube和IS誦Cube。-CI\T…zcwoooo\T%2…\fooooHIJ2oooo11…1oooo^A…入1d42"uu:wII1少lz1BS-Cube:如果一個S-Cube與給定的邊界相交，則稱為邊界相交立方體；如果S-Cube的26個鄰居中有一個是邊界相交立方體,則稱該S-Cube為邊界鄰居立方體。這兩類立方體都歸為BS-Cube。*VS-Cube和IS-Cube:在確定了BS-Cube後，其他剩下的S-Cube分為兩種有效曲面立方體(VS-Cube)和無效曲面立方體(IS-Cube)。位於感興趣曲面片上的即為VS-Cube，反之則是IS-Cube。我們採用了一個種子填充算法來區分IS-Cube和VS-Cube:首先我們在BS-Cube的鄰居中尋找種子IS-Cube,考察每一個BS-Cube的為確定類型的鄰居，如果它與任一個邊界的周圍一圈三角片相交則為種子IS-Cube(對於每一個邊界，我們取其環繞3圈的三角片參與求交，若某邊界不存在對應的種子IS-Cube，那麼我們則將環繞邊界的更多3角片加入，直到每個邊界都存在至少一個對應的種子IS-Cube。)；在為每個邊界都找到種子IS-Cube後，我們以種子IS-Cube出發進行一個種子填充過程以得到所有的IS-Cubes,對於任意一個種子IS-Cube，考察其26個鄰居，若存在未確定類型的S-Cube,則將該立方體置為IS-Cube並作為新的種子點，重複該過程直到沒有新的種子IS-Cube出現為止。種子IS-Cube搜索算法-Function&^/(^&5^^/2(0的偽代碼如下FunctionSeeifC^&S^c《。aseedXff-Cu&s1)forai^rcfc's26nei^iborS"ctf2)ifcsisCuteORCu6eORW-Cu3)ifcwinterssetaboundarythenreturnc及；4)foranyofc，s26nei^iborS"c#5)5-null;6)ifc#isaBS-Cube，then5=5^Ci^e沒。r5);7)ifsisNOTnull^thenreturns;8)returnnull;IS-Cube種子填充算法-FunctionCM&F/oo^7g("的偽代碼如下formulaseeoriginaldocumentpage11兩種算法都以遞歸函數形式給出。我們從每一組BS-Cubes中隨機選取一個BS-Cubec作為輸入調用Function5"eaiCwZ^&arc/2(c)，得到種子IS-Cube然後調用FunctionCw6eF/ocxi/"g("進^亍IS-Cube的4專4番。長口果FunctionSeei/Cw6&Sean^(c)返回null,我們從另一組BS-Cubes中再選取一個BS-Cubec進行搜索。我們迭代的進行搜索及傳播過程直到沒有找到新的種子IS-Cube。由於兩個函數中的搜索過程都是局部的，因此整個立方體分類的過程是比較快的。在完成了立方體分類後，我們就可以在VS-Cubes上抽取等值面，本文採用了Lewiner等人提出的移動立方體算法的一個高效而魯棒的實現(參見T.Lewiner，H.Lopes，A.W.Vieira,andG.Tavares.Efficientimplementationofmarchingcubescaseswithtopologicalguarantees.JournalofGraphicsTools,2003,8:1-15)。由於我們只對VS-Cube進行多邊形化，在給定模型和生成的網格間那些BS-Cube所佔據的區域會存在一個空白帶，我們必須對這個條帶進行三角化從而將所有網格曲面連成一個整體。我們將之定義為一個組合優化問題並進一步轉化成有向圖上的最短路徑問題進行求解。我們定義有向圖上的邊權重為一個衡量三角片r規則性的式子formulaseeoriginaldocumentpage11式子中r是內切圓的半徑，/為三角片r的最長邊。度量值j越小表示三角片越規整，這樣求得的是一個三角片最規整的結果。權利要求1.一種任意拓撲的多邊形網格模型融合方法，包括以下步驟1)從已有模型上截取感興趣的部件；2)在過渡基元的輔助下將部件放置在合適的位置；3)在屏幕上用滑鼠繪製線條以指定連接已有模型的中間過渡物體的大致輪廓；算法自動構造出深度平面和投影平面以確定輪廓線初始深度信息，用戶分別在兩個平面上對輪廓線進行再編輯直到滿意；4)採用變分隱式曲面定義光滑插值邊界並符合指定輪廓的過渡曲面；5)採用局部化的移動立方體算法，對過渡曲面進行多邊形化並與已有模型進行無縫連接。2.根據權利要求1所述的多邊形網格模型融合方法，其特徵在於所述的步驟(2)中將部件放置在合適的位置是指在過渡基元上指定目標位置，並據此確定物體目標方向；應用主元分析方法對每個待融合物體定義個方向；將待融合物體由當前定義方位變換到過渡基元上指定方位；最後在鎖定模式下調整物體，物體將限制在過渡基元表面上運動。3.根據權利要求1所述的多邊形網格模型融合方法，其特徵在於所述的步驟(3)中算法是指系統自動找到兩個離該輪廓線端點最近的開口^4和S，並在兩個開口上分別確定離^"廓線端點最近的點P、Q;然後引入兩個平面投影平面Q和深度平面n:深度平面n經過點P、Q和視點，記其法向為i^,用於進一步調整輪廓線的深度變化；投影平面Q經過點P、Q,其法向為n。-i^x兩，描述當前角度下輪廓線的形狀；接著，用戶所繪輪廓線被投影到由深度平面上的貝賽兒曲線沿nn掃略得到的曲面上；系統自動確定出輪廓線的深度信息，並變換到世界坐標系；隨後用戶勾勒的過渡物體輪廓被轉化為位置約束和法向約束並添加到變分隱式曲面構造中，對於輪廓線上的點，它們的法向通過對確定輪廓線的開口上的兩個點p和Q的法向通過沿，侖廓線進行弧長插值得到。4.根據權利要求1所述的多邊形網格模型融合方法，其特徵在於所述的步驟(5)中所述的局部化的移動立方體算法為將指定空間剖分為立方體，並根據定義的隱函數進行採樣；根據立方體的採樣信息以及待融合物體的信息對立方體分類；在有效立方體上應用保拓樸的移動立方體算:抽===用，橋接三角化實現過渡網格與^^^縫連接，對過渡區域進行重新網格化改善網格質量。^全文摘要本發明公開了一種任意拓撲的多邊形網格模型融合方法，包括以下步驟1)從已有模型上截取感興趣的部件；2)在過渡基元的輔助下將部件放置在合適的位置；3)在屏幕上用滑鼠繪製線條以指定連接已有模型的中間過渡物體的大致輪廓；4)採用變分隱式曲面定義光滑插值邊界並符合指定輪廓的過渡曲面；5)採用局部化的移動立方體算法，對過渡曲面進行多邊形化並與已有模型進行無縫連接。本發明通過將已有的多邊形網格模型以自然、光滑的方式融合在一起，得到新的複雜多邊形網格模型，從而為非專業人員提供了一種簡便直觀的造型方法。文檔編號G06T15/00GK101266691SQ20081006065公開日2008年9月17日申請日期2008年4月24日優先權日2008年4月24日發明者林俊聰,王昌凌,許健泉,金小剛申請人:浙江大學