一種用於實時分割三維網格模型的筆劃式交互方法
2023-05-02 20:53:01 1
專利名稱：：一種用於實時分割三維網格模型的筆劃式交互方法
技術領域：
：本發明涉及計算機圖形
技術領域：
，提出了一種用於實時分割3D模型的筆劃式交互框架。
背景技術：
：在計算機圖形學領域，網格模型分割是一個非常有用的工具，可用於建模，紋理貼圖，交叉參數化，形狀漸變，形狀檢索和碰撞檢測等。當前，因為表現能力和速度上的優勢，三角形網格成為3D數據的通用表示形式。然而，三角形網格本身只表徵了低層數據結構，無法反映出高層結構，比如語義特徵。為了獲得一個有意義的目標分割，從這些底層數據表示中來提取出語義特徵非常關鍵。然而，"有意義"的分割這個概念非常依賴於具體的應用背景，並且隨著用戶主觀意願的不同而不同。因此，在圖形學領域這仍然是個極具挑戰性的問題。目前大多數網格分割方法都希望自動地將一個表面形狀分割成有意義的特徵。這些方法的一個重要目標是儘可能避免過度分割，儘可能獲得少數目的分割部件，最後的輸出結果通常少於10個分割部件。然而，在這些自動分割方法中，為了適應不同的場景，一些控制參數仍然需要用戶調節和設定。因此，由於問題本身的不適定性，要做到嚴格意義上的自動分割仍然很困難。
發明內容為了解決現有技術的問題，本發明的目的是通過簡單直觀的交互方法來進行模型分割，而無需抽象繁瑣的參數調節，為此，本發明提供一種用於實時分割三維網格模型的筆劃式交互方法。為達到上述目的，本發明用於實時分割三維網格模型的筆劃式交互方法的技術方案如下所述首先，在這個基於筆劃的網格分割系統中，用戶通過簡單直觀的交互接口對三維網格模型3D有效地執行分割操作；其次，用基於角度的特徵感知尺度獲得離散微分幾何特徵，並採用擴散算法對三維網格模型3D進行分割操作;提出了兩種基於角度的特徵感知尺度。這些尺度清晰地揭示了離散微分幾何特徵，比如曲率張量和高斯像的曲線長度；最後，我們分別基於凸包特徵和視在角度特徵，提出了兩種快速的拓撲不變且幾何不變的調整算法，生成自然的網格分割邊界。值得注意的是，本發明不僅提高了用戶的操作體驗，而且可以僅在--個交互中實現多級分割。這種靈活性使得本發明所提出的方法可以滿足大多數應用的需要。所述的方法中的頂點、面片特徵距離尺度分別為頂點特徵距離尺度y;(w)為//(W)=(1+COS(。))(1+1sin(。)I)=(l+^")(l+ll",x",||)'II^II式中，源頂點標識為義.，它的法線為"、；目標頂點標識為v,，對應法線為n,;^,為連接、和v,的有向邊；過程角。為源法線",和有向邊e,,之間的夾角；狀態角為源法線和目標法線之間的夾角；面片特徵距離尺度//(^)為//(A0=-cos(la加I)=-"f.《；式中《，《分別為源和目標面片的法線，c^為狀態角。所述基於頂點的分割步驟為步驟ll:對於三維網格模型中的每一個頂點，我們用一個四元組{v,,,/—"om^，W,//}來定義它的屬性，其中v,是索引號為/的頂點，z'=l,2，...,『|;,/一hown是一個布爾值，其決定這個頂點的部件id是否己知(即是否被索引標記)；W是這個頂點的部件id(W=l,2,.』；0保留用於初始的未知狀態)；《是這個頂點到l-鄰某個已標識點的特徵距離；步驟12:初始時，遍歷3D網格找出1-鄰有已標識點的頂點，把它們插入到一個候選鍊表中；步驟13:然後使用擴散方法進行迭代求解，其中，在每一步，尋找具有最小/J值的頂點，改變它的狀態從未知到已知，將其從候選鍊表中刪除，並將它的1-鄰未知頂點插入到候選鍊表，迭代過程直到候選鍊表為空為止。所述基於面片的分割策略為對於其三個頂點id都相同的面片/:，該面片的id等於頂點的id;否則，面片/、.的id等於和它具有最近面片特徵距離//(w)的面片y;的id，其中面片特徵距離尺度//(^)定義為//(")=-cos(K』=-《.《。本發明提出了一個基於筆劃的交互框架，通過這種易於使用的交互方式，根據用戶的意圖輕鬆地分割網格模型，而無須很多時間或者技巧。為了有意義地分割一個模型，我們提出了兩個獨立於模型的大小和尺寸的特徵感知尺度。這些尺度具有清晰的物理意義且反映了離散微分幾何特徵，比如曲率張量和高斯像的曲線長度。此外，基於凸包屬性和角度屬性，提出了兩種快速的拓撲不變且幾何不變的邊界調整算法取得了視覺滿意的分割邊界。實驗顯示本發明的方法不僅能生成用戶希望的有意義分割，也極大地提高了用戶的體驗。此外，本發明的分割系統還可以僅在一個交互中實現多級分割，而這對於現有技術的自動分割算法是非常困難的，本發明的這種靈活性使得的系統可以滿足大多數應用的需要。通過使用本發明這種易於使用的交互方式，用戶可以輕易地分割一個3D模型而無須很多時間或者技巧。圖l示出本發明方法的一個示例；圖2示出本發明方法的另一個例子；圖3示出本發明方法的三個步驟；圖4a示出用於頂點擴散的特徵感知尺度示意圖4b示出用於面片擴散的特徵感知尺度示意圖5示出為本發明邊界調整策略的效果；圖6示出本發明基於筆劃的交互系統界面。圖7示出是利用本發明對於動物模型的分割結果；圖8示出對於CAD模型的分割結果；圖9示出更多模型的分割結果。具體實施例方式下面將結合附圖對本發明加以詳細說明，應指出的是，所描述的實施例僅旨在便於對本發明的理解，而對其不起任何限定作用。本發明方法的主要動機是基於如下事實在真實的應用中，最後輸出通常只有數目很少的分割部件，一般58個，通常小於10個。因此，用戶更傾向於通過簡單直觀的方法來自己決定輸出結果，而不是通過抽象繁瑣的參數調節。而且，對於網格分割的許多重要應用，比如紋理貼圖和交叉參數化，如果要取得高質量和視覺滿意的結果，一個好的面向用戶的調整接口是非常必要的。因此，一個直觀簡單的工具在這項任務中擔負著重要角色。然而，己有的自動方法不能提供這麼一個直觀的接口。而我們注意到應用面越來越廣泛的基於筆劃的交互技術正好可以填補用戶的主觀性和複雜三維模型之間的語義鴻溝。使用這種便利的交互方式，只需隨意地畫上幾筆來粗略標識出感興趣的區域或者部件，本發明所提供的方法就可以給出用戶想要的分割結果。對於本發明的使用，即使是非專業用戶，也無須進行特別地培訓。圖1示出本發明方法的一個示例；圖l(a)示出用戶隨意畫一些筆劃在3D模型上，例如在3D模型的手指上、胸前、臉部等部位畫筆劃；圖1(C)示出本發明的系統給出用戶所希望的分割結果；基於筆劃的交互模式能輕鬆地在一個操作過程中取得多級分割，比如細小的拇指相比於龐大的身軀，見圖l(b)中的放大圖。圖2本發明方法的另一個例子；由圖2(a)為主視圖和圖2(b)側視圖可以看出，本發明所提供的方法對駱駝Camd模型生成了一個自然的分割結果。圖3是本發明方法的三個步驟圖3(a)在頂點擴散後的結果，注意其中白色部分是尚未最終確定所屬id的區域；圖3(b)應用所有面部件分割策略後的結果；圖3(c)邊界調整之後的結果。1.生成基於頂點的網格分割在本發明系統的交互步驟中，用戶只需在2D屏幕上隨手畫幾筆筆劃。這些筆劃然後投影到3D模型上產生一些初始的種子頂點。每一個這樣的頂點分配到一個和所屬筆劃相同的索引號。然後，本發明對這些初始的種子進行擴散，以完成對整個網格的分割。最自然的方式是考慮l-鄰擴散，這需要特定的尺度來決定兩個相鄰頂點的特徵距離。本發明提出了一種基於角度的擴散特徵感知尺度，其獨立於模型的大小和尺寸。下面，我們對這個尺度作一個詳細的描述。用於頂點擴散的特徵感知尺度示意圖如圖4a所示。將一個頂點標識為v,.，它的法線為；而標記它的某一個l-鄰點為v,，對應法線為n,。因為法線(或a)是通過平均1-鄰面片的法線而得到的，可將其視為一個狀態，因為它反映了一個頂點1-鄰鄰居的局部狀態。相似地，將連接v、.和v,的有向邊e、.,視為一個過程，其表徵了從源頂點到目標頂點的傳遞過程。為了計算v,和v,的特徵感知距離，需要考慮兩個方面過程量的大小和狀態改變量的大小。具體而言，將源法線和有向邊^之間的夾角apro視為過程量，而將源法線和目標法線a之間的夾角視為狀態改變量。從圖4a的輪廓圖可以看出，由於凹形的趨勢，應將圖4a(l)到圖4a(3)(不含)中源點、和目標點v,分到兩個不同的凸部件中(換句話說，此時源點v,和目標點v,具有更遠的特徵距離)；而因為圖4a(4)到圖4a(6)的凸形趨勢，應將其中的源點v,和目標點v,分到兩個相同的凸部件中(換句話說，更近的特徵距離)。此外，為了完成分割過程，需更多關注前面的情況(將兩個頂點分到不同的部件中)。從圖4a(l)到圖4a(6)，角度。"從0。到180。逐漸增加，角度"。從-90。到90°逐漸增加。也即對於第一種情況，特徵距離的趨勢隨著過程量角度s,。增加而減小，這類似於cw/"e函數在這個角度範圍的曲線趨勢。對於第二種情況，由於3D空間中正負角度的不確定性(如果缺少額外參考系的話)，應集中考慮相對重要的角度區域-9(T到(T。在這個角度區域中，距離趨勢也隨著狀態改變量角度^的增加而減小，這類似於的曲線趨勢(1sin(x)|)。根據上面的分析，現在我們來定義過程量角度。，令人感興趣的，該項和離散方向曲率相似，因為後者的表徵形式為:其中《和《為兩個主曲率。)2IIII接著，我們定義狀態改變量角度。,,。Isin(a加)HIx",II也令人感興趣的是，我們的第二個龜度和法線高斯像的曲線長度相、，因為後者在-9(T到90。時和狀態改變量角度。有相同的趨勢曲線。其中&'是高斯像c'上的弧長元素。這樣，我們用過程量角度^。和狀態改變量角度^。一起來定義全局特徵距離尺度/J(W)://(5,/)=(1+C0S"prJ)(l+Isin(a."。)I)=(i+g;:)0+ii",x",ii)這個尺度是一個獨立於模型大小尺寸的特徵感知尺度。在以上定義中，有兩個額外的1:第一個1用於避免負值；第二個1用於當該項(li"、w,11)趨近於0時，避免左邊的項(l+^^)因為乘以0而被消掉。II,I！我們用這個尺度來完成初始的頂點擴散，如圖3(a)所示。此外，額外的增強函數也可應用到不同的角度區域以實現各種濾波效果。接下來，我們介紹本發明的擴散算法。對於每一個頂點，本發明用一個四元組K,f/—來定義它的屬性，其中v,是索引號為/的頂點，/=1,2,...,|K|;//—是一個布爾值，其決定這個頂點的部件id是否己知(即是否被索引標記)；/"是這個頂點的部件id(W=l,2,...";O保留用於初始的未知狀態)；//是這個頂點到1-鄰某個已標識點的特徵距離。初始時，我們找出1-鄰有己標識點的頂點，把它們插入到一個候選鍊表中。在每一步，我們尋找具有最小/J值的頂點，改變它的狀態從未知到己知，將其從候選鍊表中刪除，並將它的l-鄰未知頂點插入到候選鍊表。重複以上操作，直到候選鍊表被清空為止。這時，所有頂點都被標記一個索引id，基於頂點的網格分割至此完成。2.生成基於面片的網格分割在初始的基於點的擴散之後，我們已經對每一個頂點標識了一個部件id。但因為通常要輸出基於面片的分割部件，所以我們需要將點部件轉換成面部件。為了標記每一個面片，我們採用如下的策略今對於其三個頂點id都相同的面片乂，該面片的id等於頂點的id。今否則，面片/、的id等於和它具有最近特徵距離的面片,的id。與定義基於點的特徵距離相類似，我們也定義基於面的特徵距離//(W)。這裡我們僅需考慮狀態量。如圖4b用於面片擴散的特徵感知尺度示意圖所示，//(W)隨著角度",.,。從-180。到(T(或者從180。到0。)而減小，這類似於-cos(l;cl)的曲線趨勢。//(,m)=-cos(i"加ix"r式中《，",分別為源和目標面片的法線，狀態角",,。為源面片法線Ko/(c//(《""gU/A))+K。/(c//(《"'"g—y;")同理，類似的操作被應用於部件屍6。圖5(c)和圖5(d)為應用雙邊動態凸包調整策略之前和之後的效果對比。3.2基於視在角度屬性的面部件調整在這一步中，我們直接按照人類對一個規則邊界的視在感知來調整邊界，即最小化鄰接邊界角的差異。給定位於部件《邊界上一條邊e,和它的兩個頂點v，，V_，我們得到e,的屬於部件S的鄰接面片"和屬於部件P。的鄰接面片r。我們分別計算v，，v^的覆蓋部件^的邊界角"，和"_。然後我們應用如下的調整策略今如果>1S(T同時I-ev|>《，則添加面片"到部件屍。。今如果"_4，則添加面片/r到部件^。這裡，我們採用閾值4=120°。因為該步驟非常快速，我們執行A^3個迭代步驟為了更好的效果。圖5(e)和圖5(f)為應用視在角度屬性調整策略之前和之後的效果對比。下面結合附圖詳細說明整個系統的操作過程。圖6顯示了本發明筆劃交互系統的界面實例。用戶用滑鼠簡單地在3D模型上畫一些2D筆劃，無須參數調節，然後本發明的系統就可給出所希望的分割結果。在圖7(a)和(b)中是貓面獸Feline模型的分割效果，龍Dragon模型的分割效果見圖7(c)，圖7(d)。用戶只需幾秒鐘的時間就可以在同一個視圖中完成筆劃的勾勒，並快速獲得分割結果。我們實驗所測試的模型不僅包含人和動物模型，還包括CAD模型圖8，錘子Hammer模型的分割效果見圖8(a)，圖8(b);螺絲起子Screwdriver模型的分割效果見圖8(c),圖8(d)，更多的結果見圖1，2和9。圖9示出更多模型的分割結果。恐龍Dinosaur,寵物龍Dinopet，大象Elephant禾n辦公椅Officechair模型的分割效果分別見圖9(a)，圖9(b)，圖9(c)和圖9(d)。無論是對有經驗還是無經驗的用戶，使用起來都非常簡單快捷。由於我們的特徵感知尺度是獨立於尺寸的，因此我們的系統適用於各種不同大小的模型。相對於自動方法，我們基於筆劃的分割系統有一個顯著優點在於可以輕鬆地在一個交互過程中實現多級分割，比如無論是圖1中纖細的右手指相比於龐大的身軀，還是圖7(a)、圖7(b)中細小的右角相比於健壯的四肢，都可同時被分割出來。此外，我們的邊界調整算法為網格分割生成了自然的邊界。實驗是在奔騰1.8GCPU/1G內存的計算機上進行的。從表1的運行時間總計(包括邊界調整時間)可以看到，我們的方法足夠快捷，適於實時應用。如9996個面片的模型只需0.2秒就可分割完成。表1是本發明方法的運行時間統計表1tableseeoriginaldocumentpage14我們也同時在非常大的模型上作了極限測試，比如龍Dmgon模型有871414個面片，1300K條邊，66.8MB，如圖7(c)所示，其只用72.562秒即可被準確地分割出來。綜上所述，本發明所提供的方法可以有效、快捷、便利地對3D模型進行分割操作。以上所述，僅為本發明中的具體實施方式，但本發明的保護範圍並不局限於此，任何熟悉該技術的人在本發明所揭露的技術範圍內，可理解想到的變換或替換，都應涵蓋在本發明的包含範圍之內，因此，本發明的保護範圍應該以權利要求書的保護範圍為準。權利要求1、一種用於實時分割三維網格模型的筆劃式交互方法，其特徵在於，首先，基於筆劃的網格分割系統，用戶通過直觀的交互接口對三維網格模型3D執行分割操作；其次，用基於角度的特徵感知尺度獲得離散微分幾何特徵，並採用擴散算法對三維網格模型3D進行分割操作；最後，分別基於凸包特徵和視在角度特徵，用兩種快速的拓撲不變且幾何不變的邊界調整算法生成自然的網格分割邊界。2、如權利要求1所述的方法，其特徵在於，所述特徵感知尺度的頂點特徵、面片特徵距離尺度，其中頂點特徵距離尺度//(^)為formulaseeoriginaldocumentpage2式中，源頂點標識為、，它的法線為n、；目標頂點標識為v,，對應法線為n,;^,為連接、和v,的有向邊；過程角^。為源法線",和有向邊^,之間的夾角；狀態角、為源法線",和目標法線",之間的夾角；面片特徵距離尺度y;(w)為-formulaseeoriginaldocumentpage2式中《，^分別為源和目標面片的法線，",,。為狀態角。3、如權利要求2所述的方法，其特徵在於，所述基於頂點的分割步驟為步驟11:對於三維網格模型中的每一個頂點，用一個四元組formulaseeoriginaldocumentpage2來定義它的屬性，其中v,是索引號為/的頂點formulaseeoriginaldocumentpage2是一個布爾值，其決定這個頂點的部件id是否已知即是否被索引標記；W是這個頂點的部件id，W=l，2,.j;0保留用於初始的未知狀態；/J是這個頂點到1-鄰某個已標識點的特徵距離；步驟12:初始時，遍歷3D網格找出1-鄰有已標識點的頂點，把它們插入到一個候選鍊表中；步驟13:然後使用擴散方法進行迭代求解，其中，在迭代的每一步，尋找具有最小y;值的頂點，改變它的狀態從未知到已知，將其從候選鍊表中刪除，並將它的1-鄰未知頂點插入到候選鍊表，迭代過程直到候選鍊表為空為止。4、如權利要求2所述的方法，其特徵在於，所述基於面片特徵的分割策略為對於其三個頂點id都相同的面片,.，該面片的id等於頂點的id，否則，面片乂.的1(1等於和它具有最近特徵距離//(^)的面片/;的1(1，其中面片特徵距離尺度//定義為formulaseeoriginaldocumentpage3全文摘要本發明為用於實時分割三維網格模型的筆劃式交互方法。用戶通過直觀的筆劃交互接口對三維網格模型執行分割操作；首先用基於角度的特徵感知尺度獲得離散微分幾何特徵，並採用擴散算法對三維網格模型進行分割操作；然後分別基於凸包特徵和視在角度特徵，用兩種快速的拓撲不變且幾何不變的邊界調整算法生成自然的網格分割邊界。用戶可輕易地分割3D模型，而無須很多時間或者技巧。本發明提出兩個特徵感知尺度分割模型，這些尺度具有清晰的物理意義且反映了離散微分幾何特徵，此外，分別基於凸包特徵和視在角度特徵，提出兩種快速的拓撲不變且幾何不變的邊界調整算法。與現有技術分割方法相比，本發明可輕鬆地在一個交互中實現多級分割。文檔編號G06T5/00GK101470894SQ20071030422公開日2009年7月1日申請日期2007年12月26日優先權日2007年12月26日發明者吳懷宇,青楊,潘春洪,馬頌德申請人:中國科學院自動化研究所