基于手繪的3D概念模型建模

鄧媛劼，王 倩

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

概念建模方法目的在于產(chǎn)生一個(gè)粗糙的概念模型，其方法應(yīng)該更加符合人的思考和設(shè)計(jì)習(xí)慣，而且更加簡單。概念設(shè)計(jì)的原則應(yīng)該是基于紙筆。在概念設(shè)計(jì)中，基于紙筆的設(shè)計(jì)過程，使得用戶的建模具有隨意性、模糊性。首先用戶習(xí)慣用筆繪制物體的2D輪廓，在繪制過程中，可以隨意繪制任何拓?fù)涞妮喞?其次，用戶的繪制過程只產(chǎn)生輪廓信息，而深度信息卻是模糊的。

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

1 概念模型建模設(shè)計(jì)與實(shí)現(xiàn)

1.1 程序框架和輪廓預(yù)處理

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

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

1.2 輸入點(diǎn)的采樣

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

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

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

該算法具體步驟如下:

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

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

(3)綜合x軸序列與y軸序列上的點(diǎn)，求pi上的特征點(diǎn)集。對(duì)于x軸序列上的任意特征點(diǎn)集px，對(duì)于y軸序列上的任意特征點(diǎn)py，設(shè)其序號(hào)分別為i，j，若≤3，則 px，py對(duì)應(yīng)同一個(gè)特征點(diǎn)，若＞3則px，py對(duì)應(yīng)不同特征點(diǎn)。

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

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

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

(2)調(diào)整標(biāo)準(zhǔn)三角化的結(jié)果。判斷用戶手繪的約束邊與標(biāo)準(zhǔn)三角化的邊是否相交，如果相交，則將其刪除，并同時(shí)連接另外的對(duì)邊，對(duì)標(biāo)準(zhǔn)三角化得到的圖進(jìn)行調(diào)整，使得多邊形的邊和標(biāo)準(zhǔn)三角化的結(jié)果不相交。

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

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

圖1 約束三角化(CDT)

1.4 求取骨骼點(diǎn)并過濾

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

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

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

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

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

圖2 計(jì)算骨骼的重要性

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

圖3 輪廓的骨骼

1.5 投影獲得骨骼點(diǎn)的深度信息

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

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

圖4 骨骼上點(diǎn)的深度信息

1.6 確定約束

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

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

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

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

圖5 約束的求取

1.7 構(gòu)造變分隱式曲面

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

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

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

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

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

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

其必須滿足條件一，即

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

1.8 可視化變分隱式曲面

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

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

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

三角網(wǎng)格繪制效果如圖6所示。

圖6 等值面

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

2 結(jié)束語

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

圖7 Gouraud－Shading繪制

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

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

［3］周曉云，劉慎權(quán).實(shí)現(xiàn)約束Delaunay三角剖分的健壯算法［J］.計(jì)算機(jī)學(xué)報(bào)，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.