鄧媛劼，王 倩

(黃河科技學院現(xiàn)代教育技術中心，河南 鄭州 450063)

概念建模方法目的在于產生一個粗糙的概念模型，其方法應該更加符合人的思考和設計習慣，而且更加簡單。概念設計的原則應該是基于紙筆。在概念設計中，基于紙筆的設計過程，使得用戶的建模具有隨意性、模糊性。首先用戶習慣用筆繪制物體的2D輪廓，在繪制過程中，可以隨意繪制任何拓撲的輪廓;其次，用戶的繪制過程只產生輪廓信息，而深度信息卻是模糊的。

文中采用變分隱式曲面對物體進行建模，充分利用變分隱式函數(shù)閉合，光滑的特性，繪制具有任何拓撲輪廓的物體;采用基于輪廓推測物體深度信息的方法，根據(jù)輪廓的寬度信息推測物體的深度信息。

1 概念模型建模設計與實現(xiàn)

1.1 程序框架和輪廓預處理

程序采用MFC框架，使用基于對話框的結構，在對話框中添加static text控件用于圖形顯示，并添加繼承CSTATIC的類SWVIEW，類中使用Windows的消息機制，完成圖形的左鍵繪制，左鍵拾取、右鍵旋轉、滾輪放縮功能。

程序支持多筆繪制，用戶可以繪制一個開放、未封閉的筆畫，然后逐步添加開放的筆畫，直到形成一個封閉輪廓。程序通過設定兩個筆畫之間的最小距離MIN_STORKE_DISTANCE來完成這個功能。如果兩個筆畫的端點小于此距離，則被認為是一個筆畫，進行合并，否則認為是兩個筆畫。程序支持交叉識別、包含識別。通過判斷一個筆畫的點是否在另一個筆畫所形成的多邊形中判斷兩個筆畫是否相交，如果一個筆畫的點完全落在另一個筆畫所形成的多邊形中，則判斷兩個筆畫包含。對于相交，則將兩個筆畫交叉部分的點除去，然后將兩個筆畫合并成一個筆畫。對于包含，則將包含的筆畫除去。

1.2 輸入點的采樣

用戶使用鼠標進行筆畫的輸入，鼠標以固定的頻率對屏幕上的移動軌跡進行采樣。一般采用基于曲率的［1］采樣算法，但效率較差，文中提出了一種間接提取算法［2］。

假設鼠標所采樣到的點{pi，i=0，1，2，…，n}，則將其分解為 x 軸上的序列{xi，i=0，1，2，…，n}和 y 軸上的序列{yi，i=0，1，2，…，n}，分別對 x 軸上的序列和 y 軸上的序列求特征值集合。最后根據(jù)特征值進行合并。

以x軸上的序列為例，求其特征點集，y軸上的序列同樣如此。x軸序列中任意xi的特征點取為其曲率的h2倍。其推導過程如下

該算法具體步驟如下:

(1)求曲線x軸序列的特征點集。計算x(i)每一點的q值并按照一下規(guī)則進行判斷，若在某一區(qū)間內，對于區(qū)間內的所有點都有q≤2，則該區(qū)間內不存在特征點，這是存在兩種情況，一是區(qū)間內大部分點的q值都等于零，只有少量q≤2，則可認為是噪音點，該區(qū)間對應一條存在噪聲的直線段;二是區(qū)間內大部分點的q值不為0且＜2，該區(qū)間對應一條彎曲程度較小的直線，所以可以假設這兩種情況都不存在特征點，若在某一區(qū)間內，對所有的點都由q＞2，則該區(qū)間對應一條變化程度較大的直線，為更好地逼近曲線，設定適當?shù)牟介L，找出每個步長內q值最大的點作為特征點。

(2)求曲線y軸序列的特征點集。

(3)綜合x軸序列與y軸序列上的點，求pi上的特征點集。對于x軸序列上的任意特征點集px，對于y軸序列上的任意特征點py，設其序號分別為i，j，若≤3，則 px，py對應同一個特征點，若＞3則px，py對應不同特征點。

1.3 簡單多邊形的約束Delaunay三角化

用戶通過鼠標輸入的輪廓，在計算機中表示的是一個點序列，這些點連接起來后形成一個簡單多邊形，在程序中，為尋找輪廓的形態(tài)信息，必須將其進行Delaunay三角化，文中采用的算法［3］將Delaunay三角化分為3個步驟進行:

(1)對輸入點進行標準 Delaunay三角化，標準Delaunay三角化又分為兩個步驟，首先，將輸入點按照X軸進行排序，逐點插入，尋找每個點的可見點，其次，對于新插入的邊進行優(yōu)化，判斷對角是否＞180°，當所有的輸入點插入完畢，則標準Delaunay三角化完成。

(2)調整標準三角化的結果。判斷用戶手繪的約束邊與標準三角化的邊是否相交，如果相交，則將其刪除，并同時連接另外的對邊，對標準三角化得到的圖進行調整，使得多邊形的邊和標準三角化的結果不相交。

(3)過濾調整后的圖。判斷每個邊是否在輸入多邊形的外部，如果是，則說明其為多邊形凸出的邊，予以刪除。

三角化的效果如圖1所示。

圖1 約束三角化(CDT)

1.4 求取骨骼點并過濾

一般采用中線軸變換(Medial Axis Transform)或弦軸變換(Cordal Axis Transform)的方法從輪廓中提取骨骼，MAT相對于CAT，計算時間較長，產生的骨架不理想，可逆性較差。文中使用 CAT［4］(Chordal Axis Transform)方法，其步驟如下:

(1)首先對多邊形進行帶約束的Delaunay三角化，將多邊形分解成3類三角形，分別為T三角形，S三角形，J三角形，T三角形有兩個外邊，S三角形有一個外邊，J三角形沒有外邊。

(2)從CDT中獲取離散的CAT骨架。首先任選一條邊界邊，從該邊開始沿順時針或者逆時針遍歷并將邊界邊編號，將S三角形內邊的中點連接起來，對于J三角形，如果是銳角三角形就取其外心，如果是鈍角三角形，就取其最長邊的中點。

(3)獲取整體CAT骨架。遍歷每個J三角形，如果J三角形是銳角三角形，則連接其各邊中點到外心，如果J三角形是鈍角三角形，則連接兩邊中點到其最長邊中點上。

需要注意，當對邊界點的采樣密集時，會包含噪聲或者是小的波動，這會產生非重要形態(tài)的骨架分支，而從形態(tài)學的意義來說，其并不具有骨骼的意義，所以必須將其過濾掉。首先將每個骨骼分支的重要性予以量化，如圖2所示，d代表分支中T三角形頂點到J三角形邊的距離，圖2中黑色代表分支的T三角形;斜線陰影部分代表J三角形;P代表T三角形一頂點;AB代表J三角形的一條邊;d代表p到AB的距離，則這一分支的重要性可以定量表示為λ=d/AB。

圖2 計算骨骼的重要性

然后遍歷每個分支，求出每個分支的重要性，設置一個閾值，如果這個分支的重要性小于閾值，則予以刪除。至此分支過濾完畢，其所求骨骼效果如圖3所示。

圖3 輪廓的骨骼

1.5 投影獲得骨骼點的深度信息

在此之前，所有點的坐標都是視口坐標，必須將其轉化到空間視域體中。程序中使用正交投影，根據(jù)視口與視域體的比例關系，進行坐標轉化，將點投影到視域體z=0的平面內。

前期得到的手繪信息僅是物體的輪廓，沒有其深度信息，如果欲構建模型，則必須推斷物體的深度信息。文中采用基于輪廓的寬度推測深度信息的推斷方法。對于骨骼上的每一個點，根據(jù)其CDT的結果，如果骨骼點所在邊的三角形是S三角形，則可以找到其所在邊所在的四邊形;如果是J三角形，且是銳角三角形，則找到骨骼點所在的三角形，然后找到骨骼上點到四邊形4個端點，或者三角形3個端點的平均距離，這個距離稱為深度信息。由于這個深度信息是模糊的，推測的結果可能并不符合用戶的要求，因此，通過增加一系數(shù)，并允許用戶通過控制這個系數(shù)，控制高度的變化，其效果如圖4所示。

圖4 骨骼上點的深度信息

1.6 確定約束

文中使用兩種約束來構造變分隱式函數(shù)。

(1)0值約束，即曲面一定經過的點。對輪廓上的輸入點進行過濾后得到的特征點，以及CDT后所求的骨骼點，都可以作為0值約束，即f(c)=0。

(2)法線約束，即0值約束點在其法線方向移動若干個單位后得到的點。對于輪廓上的特征點和骨骼點，分別求其法線方向上的約束點。輪廓上的每個特征點都相連兩條線段，用這兩個線段法線的和作為點的法線，這樣線段的長度自然成為權重，單位化后即得。骨骼上點的結構其實是一個圖結構，骨骼上每一個點可能連接多個骨骼分支，因此對每一個骨骼段求法線，相加后單位化即可，即f(c)=1。

根據(jù)以上所描述的兩種約束，求出并可視化，其如下圖5所示。

圖5 約束的求取

1.7 構造變分隱式曲面

文中使用的變分隱式曲面類似于薄板插值(Thinplate Interpolation)，需要滿足兩個條件:

(1)滿足約束，給定i個約束點ci，且每個約束點有一個取值hi，必須使每一個點滿足f(ci)=hi。

(2)光滑，用一個能量函數(shù)來量化光滑的概念，即其所有點的曲率和最小，能量函數(shù)如下

上式中，fxx，fxy，fyy為 f(x)的二階偏導數(shù)，能量函數(shù)表示在區(qū)域Ω上所有點的曲率和。

Turk［5］在其文章中推薦使用一組徑向基函數(shù)的線性組合來構造變分隱式函數(shù)，這樣的函數(shù)可以自動滿足兩個條件，因此使用這種隱函數(shù)只需滿足第一個條件即可。文中徑向基函數(shù)使用Φ(x)=，則其線性組合為

論文使用一組以約束點為中心的徑向基函數(shù)，其表示形式可以變形為

其必須滿足條件一，即

其用矩陣形式可以表示為M*D=H。式中，M為系數(shù)矩陣;D為權重向量;H為約束點函數(shù)值向量，因為系數(shù)矩陣M對稱和半正定，則這個方程有惟一解，程序通過LU分解來求解方程，得到權重向量，將權重向量回代函數(shù)中，即可構造變分隱式函數(shù)。需要注意的是，當約束點較多，方程較大時，則解方程則相當耗時，可以采用迭代法求解。

1.8 可視化變分隱式曲面

通過以上步驟可求得滿足約束條件的變分隱式函數(shù)，然而為了顯示曲面，必須將隱式函數(shù)的0值等值面顯示出來，隱式函數(shù)可視化的傳統(tǒng)方法是Marching Cube［6］算法，在程序中，用C++ 實現(xiàn)了經典的Marching Cube算法，其步驟如下:

(1)首先定義曲面與立方體相交的各種情況，曲面與立方體相交有256種情況，但可通過對稱性和旋轉對稱性簡化為14種情況，這14種情況可通過對稱性和旋轉對稱性再現(xiàn)為256中情況，并構造出一查詢表。

(2)在視域體中劃分體素，對于每個體素，計算出與曲面相交的情況，然后查詢構造出的查詢表，通過三線性插值得到三角網格及每個頂點的法線向量。

三角網格繪制效果如圖6所示。

圖6 等值面

圖6(a)圖為 MC算法繪制 f(x，y，z)=x2+y2+z2－1=0的等值面，圖6(b)為手繪的手掌所得的等值面。得到三角形網格和所有頂點的法向量后，通過Gouraud－Shading方法進行繪制，得到幾何模型的效果如圖7所示。

2 結束語

通過建模仿真，實驗結果表明，使用變分隱式曲面繪制的模型具有光滑、封閉的特性，而且可以方便地進行融合和其他后續(xù)的編輯操作。

圖7 Gouraud－Shading繪制

［1］張文景，許曉鳴.一種基于曲率提取輪廓特征點的方法［J］.上海交通大學學報，1999，33(5):592 －595.

［2］劉玉蘭.一種間接提取輪廓特征點的算法［J］.計算機工程與應用，2004，40(10):51 －52.

［3］周曉云，劉慎權.實現(xiàn)約束Delaunay三角剖分的健壯算法［J］.計算機學報，1996，19(8):615 －624.

［4］PRASAD L.Morphological analysis of shapes［J］.CNLS Newsletter，1997，139(1):1997 －2007.

［5］TURK G，BRIEN J O.Variational implicit surfaces［EB/OL］.(2009－11－19)［2011－06－19］http://smartech.gatech.edu.

［6］LORENSEN W，CLINE H.Marching cubes:A high resolution 3D surface construction algorithm ［J］.ACM Computer Graphics，1987，21(4):163－172.