一種採用草圖創建三維模型的方法

2023-06-22 07:25:51

專利名稱：一種採用草圖創建三維模型的方法
技術領域：
本發明涉及一種圖形分析與解釋的方法，屬於計算機軟體和計算機圖形學技術領域，具體地說，是一種運用草圖解析、深度恢復和三維重建等過程將自由繪製的草圖直接轉 換成三維數字模型的一種採用草圖創建三維模型的方法。
背景技術：
計算機技術的發展給工程設計領域帶來了一系列革命性變化，三維模型已成為當 前工程應用領域的主流，它不僅拓展了設計過創意的作用空間，而且超越了傳統設計技術 的表現局限，還縮短了產品設計與建模欣賞間的空間間隔。然而，三維模型給設計帶來巨大 便利的同時也帶來模型創建的諸多不便。現行的三維模型創建方法主要有兩種一種是利 用諸如Maya和AutoCAD等三維造型商業系統提供的諸如參數化或變量模型等建模工具來 構造三維模型，但這些系統的功能基本上是以大量預定義對象和指令按鈕的WIMP方式為 用戶提供構思細節定型後的結果表達，其複雜而又專業化的操作流程對大多數非計算機專 業的設計師而言是巨大的挑戰；另一種則是利用三維掃描設備或測量設備來直接獲取實物 的三維模型，但這種方式不僅代價昂貴又依賴於已存物體，而且其龐大的信息量需要進行 複雜的後期處理，獲取的三維模型也往往無法直接為設計所利用。事實上，計算機技術並未 改變設計師對傳統紙筆環境或對等數字環境下草圖繪製這一模型設計方式的偏愛，繪製草 圖依然是人類一種直接而快速的思想表達和交流方式，也是設計師進行形體設計最方便的 平臺，因此，理想的三維模型創建方式是手繪草圖交互，這樣既能支持設計創意的「頭腦風 暴式」流暢表達，又能捕捉設計師心中的三維模型信息，還能實現設計創作過程「創意平面 化表達」與「內容三維化呈現」有效連接。基於手繪草圖的三維模型生成技術的核心問題是「從圖畫中獲取三維形狀 (ShapeFrom Drawings) 」，S卩如何從二維平面草圖中恢復物體的三維信息。這個問題面臨 的主要困難在於與給定二維圖畫相匹配的三維模型信息具有不唯一性(一對多映射)。由 於圖像和視頻等數字媒體中對象或場景的三維信息是通過投影以二維形式呈現的，因此， 「從二維平面中獲得(三維)深度信息」也是計算機視覺領域的一個基本問題，這一領域解 決這個問題的典型方法是從X生成形狀技術(shape from X :X代表視頻、陰影、紋理、聚焦 和光流等視覺特徵)，一些以圖像導引的草繪系統採用此原理來支持用戶通過在多個標準 正交構造平面上的草圖像輪廓來生成三維線架模型。但是，手繪草圖是以粗略形狀來創建 三維模型，而不強調形體構成的細節信息，且多視角手繪草圖方式不符合用戶的日常繪製 習慣。已有採用單幅草圖創建三維模型的方法主要有如下幾類第一類方法是如文 獻 lZeleznik，Robert C.，Herndon，Kenneth P.，Hughes，John F.，1996. SKETCH :an interfacefor sketching 3D scenes. In Rushmeier, Holly (Ed.), SIGGRAPH' 96.Addison Wesley, pp. 163-170所述的符號系統，這種方法建立在在線手勢識別技術基礎上，將三維 幾何體用典型視角投影的二維形狀特徵(相當於形狀符號)表示，用戶手繪草圖與這些形狀特徵對應即可獲得對應的幾何體。第二種方法是如文獻4 Ymg C，Sharon D，vmde Panne Μ. Sketch-based modeling of parameterized objects. In !Proceedings of eurographics workshopon sketch-based interfaces and modeling(SBIM^ 05),2005. 所述的基於模板方法，它將用戶繪製草圖的各線條與模板進行匹配計算，根據匹配結果有 模板信息指導各部分組件的三維生成，並從草圖筆畫獲取重建的相關參數。這種方法將用 戶的繪製方式限制在系統內部定義的模板下，無法有效支持用戶的自由繪製，模板所定義 的繪製方式有時也不符合用戶的繪製習慣，且模板的定義和添加十分困難。第三類方法是 如文獻 2 LipsonH, Shpitalni M. Optimization-based reconstruction of a 3d object from a single freehand linedrawing. In :ACM SIGGRAPH 2007 courses, 2007.所述的 優化方法，這種方法將手繪草圖上的邊解釋為幾何體在相應投影下的邊界輪廓，然後利用 諸如平行、垂直等潛在幾何約束條件建立各頂點深度數據目標方程，再應用最優化技術對 目標方程進行優化以得到各頂點的深度數據，最終給出幾何體的最可接受的解釋。這種方 法要求用戶繪製包括被遮擋的隱線在內的所有輪廓線。第四類方法是如文獻3 Varley, P.A. C. , Martin, R. R. , Suzuki, H. 2004. Can machines interpret line drawings ？ In Hughes, John F. , Jorge, JoaquimA. (Eds. ), EUROGRAPHICS Workshop on Sketch-Based Interfaces and Modeling.所述的線標註方法，與第二類方法相比，它無需用戶繪製遮擋 輪廓，而將草圖中的邊分凹邊、凸邊和遮擋邊，再應用計算機視覺中的線標記算法給出草圖 各頂點和輪廓邊界的一個合理解釋，從而恢復各頂點的深度數據，但線標記算法將三維模 型限定在「三面角」結構(即所有面元均為平面，所有角都由三個面相交形成)。概括起來，手繪草圖是三維模型創建的有效方式，但已有基於單幅草圖的三維模 型創建方法主要採用表達形體輪廓線的手繪草圖，且要麼對用戶繪製的限制過多，如符號 系統和基於模板方法限制在系統定義的圖形中；要麼需用戶在複雜優化過程中提供多種結 果進行選擇，如優化方法或線標註方法由系統內部定義的選擇標準提供多個結果，這些由 純輪廓線產生的結果可能與用戶期望存在很大差異。顯然，這些方式不能支持用戶較自由 地進行形體設計。實際應用中，用戶在利用單幅手繪草圖表達三維物體時，往往會繪製一些 陰影線等輔助線索來表明其三維效果，而現有的基於手繪草圖的三維創建方法並沒有充分 利用這些線索，因此，如何將這些線索與形體輪廓線有機結合併為用戶提供自由的草圖繪 制方式是手繪草圖交互創建三維模型面臨的重要課題。

發明內容
發明目的本發明所要解決的技術問題是針對現有技術的不足，提供一種採用草 圖創建三維模型的方法，該方法支持用戶以繪製的單幅草圖的方式直接創建三維模型。技術方案本發明公開了一種採用草圖創建三維模型的方法，其特徵在於，包括以 下步驟步驟一，草圖解析將待處理的草圖的筆畫分為作為對象輪廓的圖元筆畫和作為 三維效果的線索筆畫，並分別進行圖元識別和線索識別；步驟二，深度信息恢復利用圖元鄰接關係檢測實現對象單元的識別，從而構建對 象單元集恢復各對象單元的深度信息；步驟三，隱藏線判別並補全在繪製線索指導下判別並補全各對象構成單元的隱藏線，生成完整的三維對象單元；步驟四，三維模型重建使用幾何拓撲關係拼接對象單元重建目標對象模型。本發明步驟一中包括以下步驟採用基於幾何屬性的草圖識別方法，將草圖筆畫集S分為圖元筆畫集Sm和線索筆畫集S。，其中，幾何屬性包括筆畫閉包矩形面積A和筆畫密度P，所述矩形面積A = aXb, 所述筆畫密度P = 1/A，a為閉包矩形的長、b為閉包矩形的寬，1為筆畫長度，筆畫密度大 於設定閾值的筆畫識別為線索筆畫，構成線索筆畫集Sc ；對圖元筆畫集Sm中的筆畫進行筆畫分割；對筆畫分割後的各部分進行圖元筆畫類型識別，將各部分筆畫分為直線段、橢圓 和圓弧三類，並略去橢圓筆畫，將圓弧連接首尾端點做直線段處理，從而將圖元筆畫集Sm中 的筆畫分為一組線段集；構建圖元筆畫圖結構Gn= {V, E}，其中V為線段的頂點集，包含頂點的坐標值，E 為線段集，包含各邊的長度值和方向值，修正頂點的坐標值使圖元筆畫集Sm中的線段滿足 相鄰、T型交、平行、等長或共線關係。所述筆畫分割的策略是選擇筆畫中相對曲率較大的採樣點作為分割點，第i個採
樣點的相對曲率計算公式為
formula see original document page 6formula see original document page 6其中，Pi表示筆畫中第i個採樣點，k表示計算相對曲率的窗口大小(一般取值範 圍為3-10，本發明中取4)，j為求和變量，L^m表示以點Pi_k和點pi+k為端點的直線段， Dis (Pj，Li-k，i+k)
表示點Pj到直線L^i+k的距離，Len(Li^itk)表示直線段L^pk的長度。本發明步驟二中採用條件規則生成方法表示對象的幾何構成，並在線索筆畫指導 下利用圖元筆畫集Sm中線段之間的相鄰、平行、等長或者共線關係實現對象單元識別，包括 以下步驟對圖元筆畫圖結構Gn中的線段集進行組合，構建對象單元圖結構G。= (Μ，Ω)， 其中，M表示對象單元集，該集合中每一個對象由圖元筆畫圖結構Gn線段集中的線段組合構 成，Ω表示兩兩對象單元之間的拓撲關係；所述條件規則生成方法包括以下步驟將目標模型分為一組對象單元幾何體，每 一幾何體均有一元屬性值，包括各邊尺寸和三維中心位置，兩兩幾何體之間帶有二元屬性 值，表示幾何體之間的拓撲位置關係；對象單元幾何體在草圖中分線元、面元和體元三種表 示，其中，線元在二維表現為一條線段，表示三維空間中的一個細長長方體；面元在二維表 現為平行四邊形，表示三維空間中的一個矩形薄板；塊元在二維表現為共享同一頂點的三 個不同方向的面元，表示三維空間中的一個長方體；對象識別過程包含如下三條形狀構成 規則包圍線索筆畫的最小平行四邊形為面元；未被面元引用的圖元筆畫為線元；共享同 一頂點的三個面元組合為塊元。本發明步驟三中在線索筆畫的形狀構成規則指導下，根據對象單元的幾何屬性自 動判別和補全對象單元的隱藏線，生成完整的三維對象單元，即使對象單元圖結構G。中的 不完整的對象單元通過補齊隱藏線完整化，在補齊隱藏線時，首先閉合不封閉的面元，通過 延長不閉合的頂點和平移已有邊生成完整的平行四邊形，以補齊面元的隱藏線，然後補齊塊元，通過平移已有邊生成完整的三個面元，並添加塊元自身被遮擋的頂點以構建完整的塊元信息。本發明步驟四中根據各對象單元之間的拓撲關係，採用幾何拼接方法完成對象三 維模型的重建，包括以下步驟從圖元筆畫圖結構6,中提取對象單元圖結構G。中每一線元、 面元與塊元所對應幾何體的各邊尺寸屬性值，完成對象單元三維參數計算；設定任意一幾 何體的三維中心位置為原點，迭代搜索對象單元圖結構Gc中與已知三維中心位置的幾何體 有拓撲關係的對象單元幾何體，通過拓撲關係屬性計算各幾何體的三維中心位置，完成對 象單元幾何拼接。有益效果本發明具有以下優點1、允許利用手繪草圖繪製對象透視投影輪廓的 同時使用某些陰影線等輔助線索表達三維效果，提高了繪製方式的自然性和自由度；2、採 用條件規則生成方法表示對象的幾何構成，將對象模型看成是由線、面和塊等基本圖元構 成，提高了對象表示的通用性，避免了符號系統或模板定義對圖形構成的限制；3、本發明中 隱藏線判別和補全方法的引入，既可作為對對象單元識別結果的優化和檢驗，也簡化了後 續三維重建過程。


下面結合附圖和具體實施方式
對本發明做更進一步的具體說明，本發明的上述和 /或其他方面的優點將會變得更加清楚。圖Ia和圖Ib為本發明的一個應用實施例示意圖。圖2是本發明的處理流程示意圖。
具體實施例方式本發明公開了一種採用草圖創建三維模型的方法，包括以下步驟步驟一，草圖解析將待處理的草圖的筆畫分為作為對象輪廓的圖元筆畫和作為 三維效果的線索筆畫，並分別進行圖元識別和線索識別；步驟二，深度信息恢復利用圖元鄰接關係檢測實現對象單元的識別，從而構建對 象單元集恢復各對象單元的深度信息；步驟三，隱藏線判別並補全在繪製線索指導下判別並補全各對象構成單元的隱 藏線，生成完整的三維對象單元；步驟四，三維模型重建使用幾何拓撲關係拼接對象單元重建目標對象模型。更具體地說，本發明讓用戶採用數字圖形輸入環境提交的手繪草圖，其實施主要 涉及草圖解析、深度恢復和三維重建三大關鍵技術，其處理流程如圖2所示。手繪草圖解析 是將用戶提交的手繪草圖筆畫分為作為對象輪廓的圖元筆畫和作為三維效果的線索筆畫， 並分別識別處理；深度信息恢復這是利用圖元鄰接關係並在繪製線索筆畫的指導下完成對 象單元的識別並恢復各對象單元的深度信息；隱藏線判別和補全則是在繪製線索筆畫的指 導下判別並補全各對象構成單元的隱藏線，生成完整的三維對象單元；三維模型重構是用 幾何拓撲關係拼接對象單元以重建目標對象模型。下面分別介紹各實施例部分的主要流 程1、草圖解析
草圖解析模塊首先需要對草圖上的筆畫進行分類處理，本發明將草圖筆畫分為圖 元筆畫和線索筆畫兩類，然後分別對圖元筆畫和圖元筆畫進行處理。1. 1筆畫處理/分類 用戶繪製草圖時，除了繪製必須的模型輪廓線條，還可能繪製一定成分的線索筆 畫，這些線索不僅有助於體現三維效果，而且經有效識別之後，能輔助對整張草圖進行解 析，以消除建模過程的歧義性。用戶提交的草圖是一張矢量圖S(矢量圖，在數學上定義為 一系列由線連接的點，它與位像相對應)，表現為基本筆劃的序列，可表示為(SiIi = 1，...，η)，其中Si為用戶繪製的一筆，即每次起筆和抬筆之間所繪的一筆，筆畫所含的點採 樣連續，表示為(P」j = 1，...，m)，其中，Pi表示筆畫中第i個採樣點。由於用戶在同一筆 中不會同時繪製線索和模型輪廓線，因此本發明可對用戶所繪的每一筆進行分類，本發明 將用戶所繪的筆畫分為如下兩類1).圖元筆畫表示實際三維模型上存在的線條；2).線 索筆畫輔助表達用戶設計意圖的筆畫，實際的三維空間不存在這些線條，筆畫分類過程如 下輸入原始草圖S輸出圖元筆畫集SM，線索筆畫集S。，初始均為空。具體包括以下步驟步驟1 取原始草圖S中一個筆畫Si ；步驟2 對該筆進行筆畫分割；步驟3 若該筆無拐點，判斷其為直線，則將筆畫Si壓入圖元筆畫集SM，跳至步驟1 判斷下一筆；步驟4 計算筆畫密度P = 1/A，其中1為筆畫長度，A為筆畫矩形凸包面積；步驟5 若筆畫密度P大於某一閾值P ！(所述閾值P ！ 一般設為0. 018-0. 022，本 實施例取0. 02)，則將筆畫Si壓入線索筆畫集S。，否則將筆畫Si壓入圖元筆畫集Sm ；步驟6 跳至步驟1判斷下一筆。1. 2圖元識別對圖元筆畫集Sm的處理類似於其他現有的草圖處理方法，該模塊的處理目標是 對圖元筆畫集Sm中的每一筆進行濾噪、筆畫分割和擬合等處理，最後將圖元筆畫集Sm轉換 為一個規整化的圖結構G= (V，E)，其中，V= {Vi|i = 1，...，NV}為頂點集，E= IeiIi = 1，...，Ne}為線段集，其中(1)每一頂點Vi = (C，λ )為一個二元組，其中，c = (x, y)表示其二維坐標，χ表 示X軸坐標，y表示Y軸坐標，λ表示頂點類型屬性，其值由與其相連邊的數目與所呈形狀 確定。(2)每一線段力=(vi; V2, a, 1) 一個四元組，其中，V1為起始端點，V2為末端端點， a為該線段的傾角，1為該線段的長度。為了給用戶的繪製提供一定程度的自由性，本發明允許將相鄰的線段一筆繪製。 為了進行有效的解析，本發明需要尋找該相鄰兩線段的斷點。根據相鄰線段的方向關係的 不同，分為線段平行和兩線段不平行兩種情況處理。對於不平行的情況，本發明通過計算用 戶連續繪製一筆每一點的相對曲率，將相對曲率大於某一固定閾值的點(所述閾值一般取 值範圍為0. 5-0. 7，本實施例中取0. 6)作為拐點，實現對筆畫的分割；對於平行的情況，由於此時前後兩線段構成了一條線段，因此無法僅根據該線段尋找斷點，本發明根據全局線段的相互位置關係(T型交關係)的檢測結果計算其斷點。首先，本發明對圖元筆畫集Sm進行預處理，主要包括冗餘點消除、聚點消除和曲線 閉合誤差校正，並利用相對曲率計算進行筆畫分割，從而將圖元筆畫集Sm的圖元筆畫分割為若干部分，從而建立相應的筆畫集L = (Ii I i = 1，. . .，NJ，其中Ii為一筆畫，可由兩個端點Vil和vi2確定。筆畫集L中所有筆畫的端點構成筆畫集L的端點集P= {vn,vi2|i = 1，...，NJ，由此可得到草圖的一個初始草結構G。= {P，L}。本發明識別筆畫集L中每一筆筆畫的類型。圖元筆畫分類識別過程如下輸入初始草結構G。= {P，L}；輸出初始草結構G。. L每一筆畫的基本類型(線段、弧、橢圓的一種)具體包括以下步驟步驟1 計算包含筆畫的最小外接矩形，如果該矩形的高寬比小於某一預設閾值 (如0. 1)，則判斷筆畫為線段，轉步驟6 ；步驟2 根據筆畫首尾相鄰情況判斷筆畫是否為封閉性筆畫，若閉合，則判斷筆畫為橢圓，轉步驟6;步驟3 將筆畫進行橢圓弧擬合，計算長短軸長度、弧的起始和終止角度；步驟4:如果筆畫的橢圓弧擬合結果中起始角度和終止角度差值小於某一閾值 (如0. 35* π )，且長軸較大，則判斷筆畫為線段，轉步驟6 ；步驟5 如果筆畫的弧段擬合結果中起始角度和終止角度差值在一定某預設閾值區間內(如區間
)，判斷筆畫為弧段，步驟6 ；步驟6 返回結果，算法退出。由於本發明所建模型為多面體模型，只包含直線段，因此根據識別結果，本發明略 去初始草結構G。. L中的橢圓筆畫，並將識別為弧段的筆畫取首尾兩端點作為線段的兩 個端點，由此將初始草結構G。轉化為所需的圖元筆畫圖結構Gn= {V，Ε}，由於用戶繪 制的草圖含有許多模糊信息，本發明通過草圖規整化處理優化頂點坐標，從而將一張粗糙的草圖轉化為一張與所建目標模型投影一致的線畫圖，由此，本發明可計算圖元筆畫圖結構Gn. E中各線段的幾何屬性值，包括傾角和長度，此外，本發明可計算圖元筆畫圖結構Gn. V 中各個頂點的λ屬性值，該屬性描述了連接該頂點的邊的形狀信息，不同的λ屬性在三維 空間中有不同的解釋，本發明使用了六種結點類型。其中，I型結點僅有一條邊與之相連；L 型結點有兩條邊與之相連，為面的一角；T型結點在三維空間中反映出邊包含的關係，或者來自於面遮擋現象；Y型結點連接三個面，可作為一個立方體的標記；E結點連接兩個面；X 型結點是多個面的公共頂點。1. 3線索判別用戶繪製的線索筆畫種類繁多，如陰影、塗鴉、波浪線等等，各類有著不同的語義解釋。本發明根據筆畫自身的形狀特徵去判別線索的種類，用以輔助之後的對象單元識別。 本發明根據線索筆畫的凸包面積和筆畫密度對線索筆畫分類，線索筆畫類型分類過程如 下輸入線索筆畫集Sc;輸出線索筆畫集Sc每一筆畫的線索類型；
具體包括以下步驟步驟1 計算每一筆畫的矩形凸包及其面積A ；步驟2 計算筆畫密度P = 1/A，其中1為筆畫長度，A為筆畫矩形凸包面積；步驟3 根據筆畫矩形凸包面積A和筆畫密度P判別線索類型。2、深度恢復在對草圖的基本圖元和線索進行基本處理之後，本發明需要將二維基本圖元的線段映射到三維空間，即發現其深度信息，本發明首先檢測二維基本圖元線段之間的相鄰位 置關係，然後利用線索輔助對對象單元的識別，最後由於用戶未添加被遮擋的線段，本發明 根據幾何屬性識別並補齊隱藏的線段。2. 1圖元鄰接關係檢測圖元之間的關係計算是實現從二維空間到三維空間映射的基礎，本發明根據圖元 線段的頂點的坐標屬性，判斷線段兩兩之間的位置關係。本發明包含如下五種位置關係屬 性(1)相鄰如果兩線段存在某一對端點(不屬於同一線段)的距離小於某一閾值 (所述閾值一般取值範圍為10-15個像素距離，本實施例中取14個像素距離)，則兩線段為 相鄰關係。(2) T型交如果某一直線的端點位於另一條線段上，則兩線段為T型交關係，當兩 線段I1, I2滿足該關係時，不失一般性，設線段I1的端點P1位於線段I2上，則以端點P1為 斷點將線段I2分割為兩部分。(3)平行如果兩線段傾角差小於某一閾值(所述閾值一般取值範圍為10-15度， 本實施例中取13度)，則兩線段為平行關係，平行關係為一個等價關係，假定最終草圖共 有Np組平行線，則筆畫集L可根據平行關係給出其一個劃分，表示為平行關係劃分集Lp = {LPi I i = 1, · · · , Np}。(4)共線兩線段I1, I2為共線關係若且唯若該兩條線段平行且相鄰或者存在另 一條線段I3與該兩條線段I1和I2均為共線關係，共線關係為一等價關係，可利用傳遞閉包 計算方法得到全局的線段共線關係。根據共線關係，可將筆畫集L劃分為共線關係劃分集 Ls = {LSi i = 1，· · ·，Ns}，其中，Ns為共線關係劃分集合總數，因為共線關係是一種特殊的 平行關係，因此平行關係劃分集Lp和共線關係劃分集Ls之間有如下關係
Z57 c LPj ο(5)等長和以往草圖處理方法不同，本發明不檢測線段的長度，因為用戶繪製的 草圖是十分粗糙的，所提取的尺寸信息的偏差很大，因此，本發明利用「平行線所夾的平行 線段長度相等」這一幾何法則，確定線段之間是否滿足等長關係，本發明中等長關係只可能 存在於平行且不相鄰的線段之間，為一個等價關係。兩線段是否等長可根據建立各個方向 下的等高點集C= ICiIi = 1，...，NP}進行判斷，其中Np為整張草圖的平行線組數，相對於 每一組平行線LPi，Ci定義如下 Ι7 = 1，···， }為頂點集P關於關係Ri的商集，其中，關係Ri定義為(PvP2)SRi ^lllBl2, (I1 e Lpi Λ I2 e Lpi) Λ (I1, I2 共線)Λ (Pl，P2 各為 I1, I2 的端點)本發明根據計算得到的等高點集C判斷線段之間的等長關係，線段等長關係判斷如下輸入初始草結構G。= {P，L}，平行關係劃分集Lp= {LPi|i = 1，...，NP}，共 線關係劃分集 Ls= {LSi|i = 1，...，NS}輸出等長關係劃分集Ll= {Lu|i = 1，...，NJ，其中，隊為等長關係劃分集合總 數步驟1，計算頂點劃分Ci,構成等高點集C ；步驟11，取共線關係劃分集Ls中某一元素Lsj，若、，取下一元素；步驟12，若劃分Lsj只有一條直線1，其端點為Pl，p2，則新建一划分Pn= (Pl，P2) 加入頂點劃分Ci,轉步驟11 ；步驟13，取劃分Lsj所有直線對I1, I2，其端點為Pl，p2, p3, P4，在頂點劃分Ci中已 有元素搜索該四個端點，若存在於不同的頂點劃分集中，則合併該頂點集，並將不存在的頂 點併入該集合；若均不存在，新建一划分Pn = (Pl, P2, P3, P4)加入頂點劃分Ci ；步驟14，取共線關係劃分集Ls下一元素，轉步驟11繼續判斷；步驟2 取平行關係劃分集Lp中一個劃分LPi，若其中只含一條線段，則取下一划 分；步驟3 取劃分Lpi —組不共線的直線對I1, 12，其端點分別為pn，P12和P21，P22，若 3j φ i3k3l, ((Al' Pn} C Cj .Pk λ {ρη ,p22}cz Cj ({ρη,ρ22} cz Cj .Pk a{Pu, p2i} ^Cj-Pl),則直
線對I1, I2等長，在等長關係劃分集k已有元素中搜索直線對I1, 12，若存在於不同的劃分 集，則合併劃分集；若僅有一個存在，設直線I1存在，將直線I2加入直線I1所屬的劃分集； 否則新建一個劃分Lu = (I1, I2)加入等長關係劃分集k ；步驟4 轉步驟2判斷下一個劃分。
最後，為了使線段與線段之間的位置關係精確化，系統需要對草圖進行規整化操 作，即修正頂點的坐標值使圖元筆畫集Sm中的線段滿足相鄰、T型交、平行、等長或共線關 系，其過程詳細描述如下輸入初始草結構G。= {P，L}，平行關係劃分集LP，共線關係劃分集Ls，等長 關係劃分集k輸出圖元筆畫圖結構Gn = {V, E}步驟1 利用T型交關係分割邊步驟2 統一平行關係劃分集Lp中每一划分中的邊的傾角步驟3 統一等長關係劃分集k中每一划分中的邊的長度步驟4 重新計算所有頂點的二維坐標步驟41 從圖元筆畫圖結構Gn. E中取出一邊1，令1. V1. c = (0,0)；步驟42計算 1. V2. c = l. V1. c+α X (1. lXcos(l. a)，1. lXsin(l. a))，其中 α 為 起始點標誌，由起點計算末點α = 1，否則α = -1 ；步驟43 深度優先順序搜索圖元筆畫圖結構Gn. E的所有線段，已知相鄰線段的端 點坐標和邊的傾角與長度，使用步驟42中的公式計算新端點的坐標，並得到所有端點的坐 標；步驟44 計算初始草結構重心點 。= Σ G。. P. Pi. c/IG。. P I和圖元筆畫圖結構 重心點 ν=Σ Gn. V. Vi. C/|Gn.V
步驟45 圖元筆畫圖結構Gn. V中每一點ν的坐標偏移 。_ Ν ；步驟46 ；將圖元筆畫圖結構Gn. V坐標相同的點設為同一點，修改相應的邊端點信 息；2. 2對象單元識別在對圖元關係進行檢測後，本發明對圖元線段進行組合以構成基本的構造元素， 所述元素在三維空間中對應著一個獨立的實體模型，即計算對象的基本構成單元，本發明 定義了如下三種基本元素1、線元二維表現為一條線段，表示三維空間中的一個細長長方體；2、面元二維表現為平行四邊形，表示三維空間中的一個矩形薄板；3、塊元二維表現為共享同一頂點的三個不同方向的面元，表示三維空間中的一 個長方體，此時，該長方體有三個面被遮擋。該模塊的目標是配合線索筆畫集Sc將圖元筆畫圖結構Gn. E中的線段進行組合，每 一個組合部分為上述三種基元之一，從而識別出最終模型的構成要素及各要素之間的位置 關係，即給出一種對象單元圖結構Gc = (Μ，Ω )，該圖結構定義如下1). M = Imi I i = 1，...，
M| }，其中，Hii = {lji = 1, ... , ImiI, Ii e Gn. Ε} ；2) · Ω = Iri | i = 1，· · ·，| Ω |}，其中， ri = {relation}，本發明定義了 18種關係屬性，這些關係基本涵蓋了多面體模型基元拼接 的常見情況。在對象單元識別中，面元的識別最為重要，這是因為1)塊元由三個面元構成，其 識別依賴於面元的識別；2)草圖繪製中，線元的線段不屬於任何一個面元，因此未構成面 元的線段均為線元，代表獨立的實體。因此，面的提取是這一部分的核心問題。針對這一問 題，以往方法通過檢測草圖中的閉合區域，以此作為面，但是本發明處理的草圖含有獨立的 線元，並且不繪製被遮擋的線段，這兩種情況均不滿足閉合區域條件，因此，通過閉合檢測 無法有效解析本發明處理的草圖對象。而在實際的繪製圖中，用戶為了表現模型的三維效果，常在面上使用了線索線對其進行標識，本發明可利用線索筆畫集S。識別面元，進而識別 線元和塊元。線索筆畫集Sc中的每一筆線索筆畫sCi均對應一個面元m，並且線索筆畫sCi 的每一採樣點均在面元m的內部，因此，尋找線索筆畫sCi對應的面元等價於尋找包含該筆 畫的最小閉合區域，且該閉合區域滿足如下兩個條件1)閉合區域為一平行四邊形；2)區域邊界上的邊只可能為兩種情況之一模型線或者目標模型上的遮擋邊，即若該區域邊界存在某一邊未被繪製，同時該邊不被其他面所遮擋，則該區域不是該筆線索 筆畫Sci對應的面元。本發明使用獨特設計的貪心算法提取構成草圖中的某一面元的線段集，即每次從候選邊集中依所定規則選擇最優邊作為下一邊界線段，直到面閉合或無候選邊為止，面元 識別算法如下輸入圖元筆畫圖結構Gn= {V，E}，平行關係劃分集LP，線索筆畫集S。；輸出面元序列MFace = {mFi I i = 1，...，NF}，其中 mFi = (IjIj = 1，· · ·，|mFi|， Ij e Gn. Ε}；具體包括步驟1，取線索筆畫集S。中某一筆畫Sc= {Pi = (xi; Yi) |i = 1, ... , I sc| }，計算線索筆畫平均點F = Σ SC. Pi/1 Sc ι ； 步驟2，計算圖元筆畫圖結構Gn. E中各邊與線索筆畫平均點F的距離，並按距離升 序排序；步驟3，使用貪心算法提取面元mF，所述貪心算法包括步驟31 步驟39 步驟31，按升序取邊1= (Vl，V2，a，l)，壓入面元％，記初始邊Is = 1 ；步驟32，建立候選邊集，搜索與邊1相鄰於頂點V2的邊，設候選邊集為 {V，——，In' }，另一端端點集為 Iv1' , ... ,Vn' }；步驟33，以初始邊首端點1. V1為原點，初始邊1為χ軸，線索筆畫平均點i所在半 面為y正半平面，計算候選邊集中的邊傾角，結果記為{a/ , . . . , an' }，同樣的計算線段 1. V1F的傾角記為S ；步驟34，選擇滿足如下條件的邊(a/ > a) Λ (min fabs(aj' 5))，為1/，若面 元％中含有兩個方向的邊，而邊1/不與該兩方向平行，則從候選邊集中去除該邊，繼續選 擇，直到選出與該兩方向的平行邊1/為止，將邊1/壓入面元％，若候選邊集空，轉步驟 37 ；步驟35，若所選邊和初始邊Is相鄰於頂點V1，則面閉合，轉步驟38 ；步驟36，記1 = 1/，轉步驟32繼續跟蹤邊界；步驟37依照平行四邊形規則，補邊使該區域閉合，判斷所補邊是否被已提取的面 元遮擋，若無遮擋，則清空面元mF，轉步驟31按序取下一邊開始跟蹤；步驟38，判斷線索筆畫S。中每一點是否均在區域內，若有一點在區域外，則清空面 元％，轉步驟31按序取下一邊開始跟蹤；步驟39，將面元mF壓入面元序列MFace ；步驟4，取線索筆畫集S。下一筆轉1提取面元。在得到面元序列Mf_之後，搜索圖元筆畫圖結構Gn. E未被引用的線段，這些線段 各自構成線元序列Mlim。由於每一個塊元由三個面元構成，因此需要從面元序列MFace提取可構成塊元的面 元，並補齊塊元所對應長方體中被遮擋的三個面。由於組成塊元的三個面元共享同一個頂 點，則該頂點至少連接三條線段，其形呈Y型，因此，該種頂點和塊元是一一對應的關係，本 發明首先識別草圖潛在的Y型點，該類頂點的λ值為Υ、Χ或T之一；然後由此組合面元成 塊元，塊元識別算法如下輸入圖元筆畫圖結構Gn = {V, Ε}，平行關係劃分集LP，面元序列Mf_ ；輸出塊元序列Mbox = {mBi I i = 1，· · ·，Nb}，其中 mBi = {mFJ | 1 彡 j 彡 3，mFJ e MFacJ ；步驟1，識別塊元Y型點，結果存入塊元Y型點序列Yust ；步驟11，計算圖元筆畫圖結構Gn. V中各個頂點在面元序列Mf_被引用的次數；步驟12，取被引用次數大於2且λ屬性為Y的頂點，將該類型頂點壓入塊元Y型 點序列Yust ；步驟13，取被引用次數大於2且λ屬性為X或T的頂點ν，依照以識別的Y型點 的形狀，給頂點ν加線段連接，判斷所加線段是否被引用頂點ν的面元遮擋，如果該線段被 遮擋，且可見邊已構成面元，則將頂點V壓入塊元Y型點序列Yust ；步驟2，組合已識別面元，將面元關聯到每一個Y型點上；
步驟21，取塊元Y型點序列Yust中一點V，計算與其相鄰的呈Y型的三條線段，將 其中的可見線集記為L。b;步驟22，計算引用塊元Y型點ν的面元序列Mfv，從中選取引用可見線集L。b中兩條 線段的面元mFv壓入塊元mBv，並從面元序列MFa。e中去除面元mFv ； 步驟23，將塊元mBv加入塊元序列MB。X。由此，本發明得到了各單元序列MF_，Mline, Mbm，構成對象單元集Gc. M0最後，本發 明計算對象單元圖結構邊集G。. Ω，即對象單元之間的拓撲關係，根據基元之間頂點與邊連 接關係和基元自身屬性的不同，本發明定義了 18種拓撲關係屬性，包括1)線元與線元之間同向相鄰，異向相鄰；2)線元與面元之間角點重合(線在面元平面內)，角點重合(線位於面元法方 向)，邊T型交(線在面元平面內)，邊T型交(線位於面元法方向)；3)線元與塊元之間角點重合，邊T型交；4)面元與面元之間邊重合，邊包含(同向)，邊包含(異向)，點相鄰(同向)，點 相鄰(異向)；5)面元與塊元之間邊T型交，邊重合，點相鄰；6)塊元與塊元之間邊重合，點相鄰。2. 3隱藏線判別/補全由於實際繪製時，用戶不繪製被遮擋的線段或部分線段，為了能夠進行有效的三 維重建，本發明需要計算模型被遮擋的部分。在繪製中，被遮擋的部分源於T型點，該類節 點導致如下三種情況1)面元不閉合該種情況可利用平行四邊形生成規則，通過平移對邊補齊被遮擋 的邊；2)塊元的某些面不完整或者某些面完全沒有繪製該種情況下先補齊不閉合的 面，然後利用Y型點對應的三條線段補齊三個面元，最後通過面的平移補齊餘下的三個面；3)線元的連接關係錯誤這種情況可嘗試延長線元的T型端點，直到與某基元的 隱線相交為止。隱線重建算法首先處理面元不閉合的情況，然後補齊塊元，最後處理線元的連接 關係錯誤情況，隱線重建過程如下輸入圖元筆畫圖結構Gn，對象單元圖結構Gc輸出重建隱線的圖元筆畫圖結構Gn'和重建隱線的對象單元圖結構(V步驟1，初始化 Gn' = Gn, Gc' = Gc；步驟2，閉合不完整的面元。步驟21，從重建隱線的對象單元圖結構中的面元集(V .MF_和塊元中的面元集 Gc' .MB。x.mB 中搜索不閉合的面元 m' = {1/ j = 1, . . . , |m' }；步驟22，檢測面元m'的角點(1/和lj+1 『方向不同，其公共頂點為角點)；步驟23，根據角點數目的不同應用平行四邊形生成規則補齊面元的不完整部分；步驟24，轉步驟21判斷下一個面元；步驟3，補齊塊元步驟31，取重建隱線的對象單元圖結構中的塊元集(V .Mbm中一塊元mB'；
步驟32，若塊元mB'中所含面元數少於3，則步驟321，取該塊的Y型點，並計算相對應的三條線段，記為線段組I1, I2, I3;步驟322，取線段組I1, 12，I3—組線段對I1 『，I2'，若塊元mB'中無面元同時包 含線段對1/，I2'，則以線段對1/，I2'為邊，該Y型點為頂點，建立平行四邊形區域，記 該區域為mM加入塊元mB'；步驟323，轉步驟322取下一線段對判斷；步驟33取塊元 < 的Y型點Vy，並計算相對應的三條線段，記為線段組I1,12,13, 除Y型點Vy的另一端的端點集為端點組Vl，V2，V3，計算塊元mB'中三個面元上Y型點Vy的 對角點為角點組ν/ ,V2' ,V3'；步驟34，新建頂點ν= (ν/ ^+V1-C-VrC, 『 Y')為塊元被遮擋的頂點加入重 建隱線的圖元筆畫圖結構G/ .V；步驟 35，新建邊 1/ = (ν/ , ν, slopeAngle (ν/ ν), |ν/ ν|)加入重建隱線的 圖元筆畫圖結構G/ .E，其中，slopeAngle (ν/ ν)表示線段ν/ ν的傾角；步驟36，由頂點ν和邊1/新建三面元加入塊元mB'；步驟4，識別T型交節點，延長判斷和隱線的相交，改變該T型交節點位置，補齊線 段的隱藏部分。3、三維重建經過深度恢復模塊的處理，本發明得到了重建隱線的對象單元圖結構(V，該結 構提供了目標模型所構成的基本要素及其兩兩之間的位置關係，因此，三維重建只需從草 圖中提取相應的尺寸等信息構建各個基本元素，最後根據各個元素之間的位置關係拼接各 個元素以構成目標模型。整個三維重建過程如下輸入重建隱線的圖元筆畫圖結構Gn'，重建隱線的對象單元圖結構(V輸出目標模型步驟1，對象單元三維信息計算從重建隱線的圖元筆畫圖結構Gn'提取線段的長 度參數以定義重建隱線的對象單元圖結構(V各元素的尺寸信息；步驟2，對象單元幾何拼接根據重建隱線的對象單元圖結構(V . Ω的屬性拼接 相鄰元素，實現對模型的重建。本發明中，如圖Ia所示的輸入的手繪草圖平面透視圖，通過本發明所述的創建三 維模型的方法，處理成如圖Ib所述的三維模型空間立體圖。本發明提供了一種採用草圖創建三維模型的方法的思路及方法，具體實現該技術 方案的方法和途徑很多，以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域 的普通技術人員來說，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改 進和潤飾也應視為本發明的保護範圍。本實施例中未明確的各組成部分均可用現有技術加 以實現。
權利要求
一種採用草圖創建三維模型的方法，其特徵在於，包括以下步驟步驟一，草圖解析將待處理的草圖的筆畫分為作為對象輪廓的圖元筆畫和作為三維效果的線索筆畫，並分別進行圖元識別和線索識別；步驟二，深度信息恢復根據圖元識別進行圖元鄰接關係檢測，並根據圖元鄰接關係檢測和線索判別實現對象單元的識別，從而構建對象單元集恢復各對象單元的深度信息；步驟三，隱藏線判別並補全在繪製線索指導下判別並補全各對象構成單元的隱藏線，生成完整的三維對象單元；步驟四，三維模型重建根據幾何拓撲關係進行對象單元幾何拼接重建目標對象模型。
2.根據權利要求1所述的一種採用草圖創建三維模型的方法，其特徵在於，步驟一中， 包括以下步驟採用基於幾何屬性的草圖識別方法，將草圖筆畫集S分為圖元筆畫集Sm和線索筆畫集 Sc，其中，幾何屬性包括筆畫閉包矩形面積A和筆畫密度P，所述矩形面積A = aXb，所述 筆畫密度P = 1/A，a為閉包矩形的長、b為閉包矩形的寬，1為筆畫長度，筆畫密度大於設 定閾值的筆畫識別為線索筆畫，構成線索筆畫集Sc;對圖元筆畫集Sm中的筆畫進行筆畫分割；對筆畫分割後的各部分進行圖元筆畫類型識別，將各部分筆畫分為直線段、橢圓和圓 弧三類，並略去橢圓筆畫，將圓弧連接首尾端點做直線段處理，從而將圖元筆畫集Sm中的筆 畫分為一組線段集；構建圖元筆畫圖結構Gn= {V, E}，其中V為線段的頂點集，包含頂點的坐標值，E為線 段集，包含各邊的長度值和方向值，修正頂點的坐標值使圖元筆畫集Sm中的線段滿足相鄰、 T型交、平行、等長或共線關係。
3.根據權利要求2所述的一種採用草圖創建三維模型的方法，其特徵在於，步驟二中， 採用條件規則生成方法表示對象的幾何構成，並根據圖元鄰接關係檢測和線索判別實現對 象單元的識別，包括以下步驟對圖元筆畫圖結構Gn中的線段集進行組合，構建對象單元圖 結構ge= (μ, Ω)，其中，m表示對象單元集，該集合中每一個對象由圖元筆畫圖結構6,線 段集中的線段組合構成，Ω表示兩兩對象單元之間的拓撲關係；所述條件規則生成方法包括以下步驟將目標模型分為一組對象單元幾何體，每一幾 何體均有一元屬性值，包括各邊尺寸和三維中心位置，兩兩幾何體之間帶有二元屬性值，表 示幾何體之間的拓撲位置關係；對象單元幾何體在草圖中分線元、面元和體元三種表示， 其中，線元在二維表現為一條線段，表示三維空間中的一個細長長方體；面元在二維表現為 平行四邊形，表示三維空間中的一個矩形薄板；塊元在二維表現為共享同一頂點的三個不 同方向的面元，表示三維空間中的一個長方體；對象識別過程包含如下三條形狀構成規則 包圍線索筆畫的最小平行四邊形為面元；未被面元引用的圖元筆畫為線元；共享同一頂點 的三個面元組合為塊元。
4.根據權利要求3所述的一種採用草圖創建三維模型的方法，其特徵在於，步驟三中， 根據對象單元的幾何屬性判別和補全對象單元的隱藏線，生成完整的三維對象單元，即使 對象單元圖結構G。中的不完整的對象單元通過補齊隱藏線完整化，在補齊隱藏線時，首先 閉合不封閉的面元，通過延長不閉合的頂點和平移已有邊生成完整的平行四邊形，以補齊 面元的隱藏線，然後補齊塊元，通過平移已有邊生成完整的三個面元，並添加塊元自身被遮擋的頂點以構建完整的塊元信息。
5.根據權利要求4所述的一種採用草圖創建三維模型的方法，其特徵在於，步驟四中， 根據幾何拓撲關係進行對象單元幾何拼接重建目標對象模型，包括以下步驟從圖元筆畫 圖結構Gn中提取對象單元圖結構G。中每一線元、面元與塊元所對應幾何體的各邊尺寸屬性 值，完成對象單元三維參數計算；設定任意一幾何體的三維中心位置為原點，迭代搜索對象 單元圖結構G。中與已知三維中心位置的幾何體有拓撲關係的對象單元幾何體，通過拓撲關 系屬性計算各幾何體的三維中心位置，完成對象單元幾何拼接。
6.根據權利要求2所述的一種採用草圖創建三維模型的方法，其特徵在於，所述筆畫 分割的策略是選擇筆畫中相對曲率較大的採樣點作為分割點，第i個採樣點的相對曲率計 算公式為formula see original document page 3其中，Pi表示筆畫中第i個採樣點，k表示計算相對曲率的窗口大小，j為求和變量， Li-k, i+k表示以點Pi-k和點Pi+k為端點的直線段，DiS (Pj, Li_k, i+k)表示點Pj到直線Li_k, i+k的 距離，Len (Li_k, i+k)表示直線段Li^pk的長度。
全文摘要
本發明公開了一種採用草圖創建三維模型的方法，包括以下步驟將手繪草圖筆畫分為作為對象輪廓的圖元筆畫和作為三維效果的線索筆畫，並分別識別處理，並對圖元筆畫進行規整化處理；採用條件規則生成方法表示對象的幾何構成，並在繪製線索指導下利用圖元鄰接關係實現規則驅動推理，完成對象單元識別並恢復各對象單元的深度信息；在繪製線索規則指導下，根據對象單元的幾何屬性自動判別和補全對象單元的隱藏線，生成完整的三維對象單元；根據各對象單元之間的拓撲關係，採用幾何拼接方法完成對象三維模型的重建。本發明利用手繪草圖繪製對象透視投影輪廓的同時使用陰影線等輔助線索表達三維效果，提高了繪製自由度。
文檔編號G06T17/00GK101799937SQ20101013067
公開日2010年8月11日 申請日期2010年3月23日 優先權日2010年3月23日
發明者孫正興, 宋沫飛, 張巖 申請人:南京大學