基于曲率流的點模型編輯方法

摘 要：為了對點模型表面進行保細節的自由形狀編輯，提出了一種基于曲率流的點模型形狀編輯方法。該方法定義了基于平均曲率流的光順算子，通過此光順算子獲得點模型不同光滑程度的曲面表示。運用對應曲面上點之間的向量差進行相應幾何細節的抽取，在相鄰的曲面表示之間將幾何細節剝離出來。用戶可以在不同的曲面上進行自由形狀編輯，而無須關心幾何細節。在變形后的曲面上再將相應的幾何細節映射回去，實現對模型保細節的變形。實驗結果表明該方法是一種有效的點模型造型算法，在變形的同時，有效地保持了模型表面的細節特征。

關鍵詞：點模型； 形狀編輯； 幾何細節； 曲率流

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2008)09284502

(School of Computer Science Engineering， South China University of Technology， Guangzhou 510640， China)

Abstract:The paper presented a novel method for highlevel editing based on point samples. First developed curvature properties of unstructured point sets and defined the fairing operator based on mean curvature flow. The method computed a series of pointbased surface approximations at successively higher levels of smoothness using the fairing operator. The difference between two successive levels could be expressed as a set of detail coefficients that approximates for each point the distance between the two levels in normal direction; it made the separation of geometric detail from the overall shape of an object. This allows the user to manipulate a model in a flexible and intuitive way without having to pay close attention to whether or not the surface detail was properly affected. The surface detail was reconstructed using normal displacements. Experimental results show the efficiency and accuracy of the algorithm. It preserves the detail feature while perform freeform editing based on point samples.

Key words：point model; shape editing; geometric detail; curvature flow

0 引言

隨著三維數碼掃描儀的普及與應用，基于點的造型和繪制技術被科技人員廣泛研究^[1~5]。先進的三維數字照相機和三維掃描儀系統不僅能獲取現實世界中復雜物體的幾何信息，還能獲取外觀屬性，如表面顏色紋理信息等。通過這些技術生成巨大數量的曲面采樣點。猶如圖像中像素作為其基本的數字單元一樣，這些采樣點便構成了三維物體幾何和外觀屬性的基石?；邳c的圖形表示和繪制技術以離散的表面采樣點作為基本的繪制元素，相對于傳統的多邊形網格技術，其最大的優點是無須記錄頂點間的連接信息，避免了維護網格拓撲信息所需要的大量計算。因此，可以實現高度復雜場景快速有效的高品質繪制?；邳c的造型相比傳統的基于面的場景造型，其拓撲簡單，無須保存和維護復雜的拓撲信息。

在點模型編輯方面一項重要的工作是Zwicker等人^[6]的Pointshop3D點模型編輯操作系統。該系統采用類似于Photoshop圖像處理系統中的工具對采樣點表面進行操作，如帶紋理繪制、參數化、位移映射、雕刻等。將近年來多分辨率網格編輯的相關概念，如幾何光順、簡化、偏移計算等推廣到點模型上。Pauly等人^[7]提出了點模型的多分辨率造型操作。此后，結合點模型MLS隱式曲面表示和離散采樣點的參數化表示，Pauly等人^[3]于2003年又提出了一個自由形狀造型系統。由于該方法需要對點模型進行MLS隱式曲面重建，計算量大，效率不高。Guo等人^[8]采用基于體的隱式函數提出了基于物理的點模型局部造型方法，然后又將水平集用在點模型的基于純標量場驅動的自由變形。

雖然對點模型的編輯造型已經有了相當多的研究，但是仍然缺少一種有效、簡單、實用的點模型編輯造型系統。幾何細節是曲面的一種重要屬性，為了對點模型表面進行保細節的自由形狀編輯，筆者提出了一種基于曲率流的點模型形狀編輯方法。該方法直接在點模型上計算曲面的曲率及法向量，定義基于平均曲率流的光順算子，通過此光順算子獲得點模型不同光滑程度的曲面表示，然后計算對應曲面點在法向量方向的向量差，進行相應幾何細節的抽取，在相鄰的曲面表示之間將幾何細節剝離出來。用戶可以在不同的曲面上進行自由形狀編輯，而無須關心幾何細節，最后將幾何細節映射到變形后的曲面上，實現對模型保細節的變形。

1 基于曲率流的光順算子

1.1 曲率和法向量

曲面上某一點xi的平均曲率kH由式（1）決定：

2kHn=limdiam(A)→0 A/A(1)

其中：n是法向量；A是xi周圍一個無限小區域的面積；diam (A)是這個區域的直徑；表示梯度(對x，y，z求導)。記k(xi)=2kHn為平均曲率向量。Meyer等Voronoi區域如圖1所示。αij和βij是邊xixj對應的兩個角度，如圖2所示。當xi所在的某個三角形是鈍角三角形時，要對A作一些修正。

相對于三角形網格，點采樣之間沒有連接信息，無法自然確定某個點的鄰居，但可以通過采樣點的空間關系來定義局部鄰域。已知點p∈P，定義局部鄰域作為索引集Np，即對于每個點pi（i∈Np）滿足特定鄰域條件。該鄰域條件應該以Np的點充分地代表圍繞點P的小面積、局部曲面片來進行設置。局部鄰域僅僅依賴于空間采樣點的幾何位置，而不是某些與點云有關的額外連接結構。一種最簡單的確定鄰域的方法是采用Knearest鄰方法。Knearest鄰居對曲面采樣誤差很敏感，而筆者希望即使有一定的采樣誤差，也可以比較準確地得到鄰點集。這里采用類似M.S.Floater等人在文獻[10]中提到的方法。首先收集一個可能的鄰點集Ni(xi)={j∶‖xi-xj‖＜ri}，將Ni中的點投影到xi所在的切平面上，得到P(xj)；然后對P(xj)作Delaunay三角化，得到Ti；最后重新定義鄰點集Ni(xi)={j｜j在Ti中P(xi)與P(xj)是鄰居}。確定了鄰點之后，就可以將式（2）用于點集上，直接求其曲率。

原始的點采樣中沒有包含法向量，可以通過求協方差矩陣的特征向量來近似法向量。x

其中：x是以xi為中心的鄰域點集的重心。由于矩陣C是對稱半正定的矩陣，其三個特征值λi(i=0，1，2)為非負的實值，所對應的三個特征向量vi(i =1， 2， 3)組成一個正交基。假設λ0≤λ1≤λ2，平面(x-x)×v0=0使得x周圍的點到此平面的距離和為最小，此平面可以看成是點集的切平面，v0則可作為局部曲面xi在點的法向n0，見圖3。

1.2 光順算子

曲率流的基本思想是采樣點以該點的曲率為速度沿著其法向方向進行移動，如圖4所示。曲率流使得采樣點沿法向方向移動，因此避免了采樣點漂移的情況。為曲面上每個點獲取其法向n0和曲率km后，就可以為點模型構建基于曲率流的光順算子。點模型的曲率流定義如式(4)所示：

設點集曲面P=(p1，…，pn)R3。其中pi=(xi，yi，zi)，記其所逼近的曲面為S。通過式(4)對點模型進行多次光順處理，獲得一系列點集曲面P0，…，Pk。每一個點集曲面Pii∈(0…k)代表曲面S的不同光順程度表示；P0為曲面S最光滑的點集表示。

2 幾何細節表示

在點集曲面上進行幾何細節的抽取，需要獲得曲面S的一系列對應點集曲面X0，…，Xk，并且對于所有的xlm∈Xll∈{1，…，k}，都需要存在一個xl-1m∈

其中：nl-1m是曲面在點xl-1m處的法向量；dl-1m是對應的細節參數。這樣每一個樣本點xkm∈Xk都可以通過對應的點x0m∈X0加上一系列相應的法向偏移值d0m，…，dk-1m得到。令D={D0，…，Dk-1}。其中Dl={dl1，…，dln}為在第L層點集曲面的細節參數列。

在通過光順算子獲得了曲面S的不同光順曲面表示P0，…，Pk后，需要計算Pl-1與Pl之間的細節參數列Dl-1，以進行相應的幾何細節抽取。一般情況下，對應plm∈Pll∈{1，…，k}和pl-1m∈Pl-1之間的向量差不可能正好在法向方向，因此，Pl需要重采樣。筆者采用自底向上的方法，沿著每一個點樣本pl-1m∈Pl-1的法線方向發射一條光線，采用文獻[11]中的方法尋找光線與曲面Sl的交點rlm∈Sl，相應的細節參數可表示為

即點采樣Pl-1所代表的基曲面Sl-1不變，而點模型Pl所代表的基曲面Sl被重采樣，以獲得沿法向的偏移。因此，完整的點集曲面序列構造從X0=P0開始，依次根據P1，…，Pk重采樣得到X1，…，Xk，以及對應的幾何細節表示D={D

3 點模型編輯與實驗結果

點模型的形狀編輯中一個重要的問題是在變形中保持幾何細節特征，在抽取了曲面的幾何細節D之后，就可以在點模型的任意基曲面Xl上進行自由編輯，而無須關心幾何細節。假設Xl經過編輯變形得到新的曲面Xlnew，則通過式(5)能夠得到原始曲面X變形后的結果如式(8)所示：

這樣在任何基曲面上的任意區域的變形都會自動地傳遞到原始曲面。細節的線性重構的效果如圖5所示。

圖6給出了點模型編輯的兩個例子。（a）為原始曲面；（b）為直接在原始曲面上進行編輯變形，造成幾何細節的扭曲變形；（c）為在經過光滑的基曲面上變形，然后再將相應的幾何細節傳遞到原始曲面得到的效果，有效地保持了幾何細節。

4 結束語

本文提出的方法是一種有效的點模型造型算法，用戶可以在更光滑的表面進行整體變形，再通過細節映射進行細節的編輯，在變形的同時，有效地保持了模型表面的細節特征。文中的曲率流方法還可用于點模型的去噪處理。另外，本文方法也非常有利于拓展到點模型的幾何細節遷移、特征和細節粘貼等應用領域。

參考文獻：

［1］ALEXA M， BEHR J， COHENOR D，et al. Computing and rendering point set surfaces[J].IEEE Trans on Visaulization and Computer Graphics，2003，9(1):315.

[2]SCHAUFLER G， JENSEN W H. Ray tracing point sampled geometry[C]//Proc of the 11th Eurographics Workshop on Rendering， ACM International Conference Proceeding Series. Brno， C:Zech Republic， 2000:319328.

[3]PAULY M，KEISER R， KOBBELT P L，et al. Shape modeling with pointsampled geometry[C]//Proc of Annual Conference Series Computer Graphics， ACM SIGGRAPH. San Diego， California:[s.n.]， 2003:641650.

[4]OHTAKE Y， BELYAEV A， ALEXA M，et al. Multilevel partition of unity implicits[C]//Proc of Annual Conference Series Computer Graphics， ACM SIGGRAPH. San Diego， California:[s.n.]，2003:463470.

[5]ADAMS B， DUTR P. Interactive boolean operations on surfelbounded solids[C]//Proc ofAnnual Conference Series Computer Graphics， ACM SIGGRAPH. San Diego， California:[s.n.]， 2003:2631.

[6]ZWICKER M， PAULY M， KNOLL O， et al. Pointshop 3D:an interactive system for pointbased surface editing[C]//Proc of ACM SIGGRAPH. 2002:322329.

[7]PAULY M， KOBBELT L， GROSS M. Multiresolution modeling of pointsampled geometry[EB/OL].(2002). http://graphics.stanford.edu/mapauly/Pdfs/MultiresModeling.pd.

[8]GUO Xiaohu， QIN Hong. Dynamic sculpting and deformation of point set surfaces[C]//Proc of the 11th Pacific Computer Graphic and Application. 2003:123130.

[9]MEYER M， DESBRUN M， SCHRODER P，et al. Discrete differentialgeometry operators for triangulated 2manifolds[C]//Proc of VisMath’02. Berlin:[s.n.]，2002.

[10]FLOATER M S， REIMERS M. Meshless parameterization and surface reconstruction[J].CAGD，2001，18(2):7792.

[11]ADAMSON A， ALEXA M. Approximating and intersecting surfaces from points[C]//Proc of Eurographics ACM SIGGRAPH Symposium on Geometry Processing. 2003:230239.