隱式曲面形狀交互調整的新方法

1、一種隱式曲面交互調整的新方法本課題得到國家“九七三”重點基礎研究發(fā)展規(guī)劃項目基金(2006CB303102)和國家自然科學基金(60673003，60573180)資助.周元峰1 伯彭波3 張彩明1，21. 山東大學 計算機科學與技術學院，濟南，2501012. 山東經濟學院 計算機科學與技術學院，濟南，2500143. 香港大學 計算機科學系，香港摘 要：提出了一種對隱式曲面形狀進行交互調整的新方法, 為隱式曲面的調整提供了兩種交互工具, 分別是對曲面上點的位置調整和法向調整. 該方法以調整后的位置和法向為新曲面的插值條件建立目標函數, 極小化該目標函數求解曲面參數的變化量, 從而確定新的隱

2、式曲面. 從優(yōu)化角度對極小化問題進行研究, 分別采用牛頓法和SQP（Sequential Quadratic Programming）方法求解該非線性優(yōu)化問題. 在調整過程中用粒子的方法對隱式曲面進行繪制, 實現了對隱式曲面形狀進行實時交互調整. 最后用實例說明了新方法的有效性.關鍵詞：隱式曲面；交互調整；優(yōu)化; 粒子系統(tǒng); 目標函數1 引 言隨著計算機圖形學、輔助幾何設計、計算機建模技術的發(fā)展，隱式曲面得到了更為廣泛的關注和應用。在曲面建模中，隱式曲面的優(yōu)勢在于表達形式簡單，用戶可方便地判定空間點與隱式曲面的相對位置，而且其光滑性非常高。隱式曲面能夠容易的表示復雜拓撲的曲面，并且可以很容易的

3、改變曲面拓撲結構。相對于參數曲面建模來說，隱式曲面的系數對于曲面形狀的影響往往是不直觀的，例如，對于代數曲面，給定代數曲面的系數之后很難預計它的形狀。因此，隱式曲面模型的一個主要缺點是難以直觀地控制和調整曲面的形狀1。近年來對于隱式曲面建模和控制的研究有很多2-10。目前使用較多隱式曲面類型主要包括代數曲面4和blobby曲面5。后者提供了一種方便的隱式曲面的交互設計方法。用戶可通過交互修改各個blobby元素來局部修改隱式曲面，進而生成復雜形狀的光滑曲面。blobby曲面是一張由一些blobby基本元素所定義的標量場的等值面。但由于blobby元素的單一性，由blobby系統(tǒng)構造一張曲面需要

4、大量基本元素，且用戶對此難以有效控制，這給交互設計帶來了極大的困難。對于隱式曲面形狀的交互調整一直是曲面建模繪制研究中一個比較難的問題。Witkin5提出了一種基于粒子化的方法對隱式曲面進行采樣和控制。該方法約束一組粒子在曲面上，這些粒子自動對曲面進行采樣。粒子之間的排斥力使粒子均勻地分布在曲面上。而且，該方法能夠允許用戶交互調整指定粒子的位置，從而改變曲面的形狀。但是該方法所用的參數太多難以控制，且文章中僅實現了對于曲面上點的位置的調整。Turk10提出了一種利用變分曲面進行插值建模的造型方法，該方法簡單有效，得到的曲面插值為線性插值，構造出來的曲面形狀較好，易于調整，但是該方法僅適用于變分

5、曲面造型，對于一般的隱式曲面并不適用。Hart6改進了文獻5中的方法, 給出了一種自動確定參數的方法，能夠對較為復雜的隱式曲面的形狀進行調整。但這種調整方式也僅實現了對頂點位置的調整，交互調整方式過于單一。如何實時調整隱式曲面形狀是隱式曲面應用中的難點問題。對于隱式曲面形狀的調整問題實質上是如何基于約束條件確定新的隱式曲面表達式的系數?；谏鲜鰡栴}，本文提出了一種隱式曲面形狀交互調整的新方法。該方法實現了對于隱式曲面上指定點進行位置調整和法向調整兩種曲面形狀調整方式?；诹Ｗ酉到y(tǒng)對曲面進行實時繪制。根據用戶希望的位置和法向建立目標函數和約束，利用優(yōu)化方法極小化目標函數求解出調整后的隱式曲面系數

6、。本文余下部分安排如下：第二節(jié)介紹曲率自適應的隱式曲面粒子采樣方法；交互調整方法的基本思想將在第三節(jié)中給出；目標函數建立和優(yōu)化方法求解在第四節(jié)中進行了詳細討論；實驗結果與數據說明在第五節(jié)給出；結論和進一步的工作在第六節(jié)中討論。2 基于粒子的隱式曲面顯示圖1 Blobby曲面上的點位置和法向控制手柄本文提出了交互調整曲面形狀的方法，在顯示的時候用Witkin5的粒子表示方法（如圖1所示），這里先簡短介紹Witkin的粒子方法。Witkin的隱式曲面建模方法是基于粒子采樣系統(tǒng)來顯示和控制一個隱式曲面。在隱式曲面上約束一個圓點使得：此處可以看作是浮動于隱式曲面上的一個粒子（particle），利用粒

7、子之間的互斥力將粒子均勻的分布于曲面表面，簡單的互斥能夠使得靜態(tài)曲面得到很好的粒子分布，但是需要一個較好的采樣作為前提條件。Witkin采樣方法采用粒子動態(tài)分裂/死亡機制將粒子約束在曲面上，初始給定一個隨機粒子和一個比較大的互斥半徑，用迭代方法對粒子進行分裂或者死亡，若粒子的互斥半徑大于設定的半徑閾值或者粒子能量大于設定的能量閾值，則將該粒子一分為二，并減少粒子之間的互斥半徑；反之，若粒子的互斥半徑過小，則該粒子死亡。迭代重復上述步驟，直至所有粒子滿足能量和互斥半徑約束條件。該方法可以很好的達到收斂效果，這樣隱式曲面的調整可以通過調整粒子來實現，達到了交互的目的。隱式曲面的形變根據隱式曲面系數

8、的變化速度確定：其中表示隱式曲面系數的變化速度，為約束粒子的個數，為要得到的無約束系數變化速度。3 算法基本思想 定義隱式曲面表達式為： （1）其中定義為曲面上的點坐標，為隱式曲面表達式系數向量。本文提出兩種對于任意隱式曲面的形狀進行調整的工具，分別是對曲面上指定點的位置調整和法向的調整。在調整過程中，為了實時顯示調整結果，我們采用Witkin的粒子方法對隱式曲面進行實時繪制。隱式曲面表達式（1）可以看作函數的零值面。當用戶改變了隱式曲面上的某一個頂點的位置或者法向之后，曲面形狀就會隨之變化，新的隱式曲面插值由新頂點的位置或法向來指定。本文的方法以新頂點的位置或法向作為曲面形狀改變的目標插值，

9、建立新的目標函數，極小化目標函數求解新的隱式曲面系數變化量，從而得到形狀改變后的新的隱式曲面。這里，該求解過程看作一個優(yōu)化過程，以插值條件建立目標函數，進行優(yōu)化。第3節(jié)詳細給出了插值目標函數的建立和求解方法。4 隱式曲面交互調整新方法 首先介紹曲面交互調整的工具，如圖1所示，圖中是采用粒子系統(tǒng)繪制的兩個blobby球體組成的blobby曲面。圖中橢圓區(qū)域所標識的藍色圓盤為曲面上點的位置調整手柄，藍色圓錐為曲面上點的法向調整手柄。用戶選中要調整的圓盤或圓錐，調整到希望的位置或方向。隱式曲面自動調整形狀，插值于用戶的設定位置或法向。4.1 基于頂點位置的調整任意指定隱式曲面上某一頂點，通過交互方式

10、將的位置移動至新位置，這時發(fā)生形變后的隱式曲面方程為：其中為隱式曲面方程系數的變化量。利用隱式曲面是曲面表達式的零值面的性質，我們定義目標函數如下： （2）其中為方程未知量。目標函數（2）的幾何意義可以看作是調整后的頂點到新曲面的代數距離平方。通過極小化尋找通過新頂點的零值面。即求解: （3）4.2 基于頂點法向的調整基于頂點位置的調整對于曲面形狀設計來說比較直觀，但是調整方法過于單一。本文還給出了基于曲面頂點法向的調整方法。用戶指定曲面上的一點，交互地將該點處法向的方向調整到一個新的位置。（1）無約束法向調整：假設對的法向調整之后的新法向為，以調整后的曲面在處的法向與用戶給定法向同向為目標，

11、建立以下目標函數： （4）其中表示在處的梯度，為隱式曲面系數變化量。極小化目標函數（4）得到未知量的值,即求解: （5）（2）帶約束法向調整：一般來說，改變了曲面一點的法向之后，曲面發(fā)生形變，這時曲面不會再插值于被修改法向的調整點。為了約束新的曲面插值于調整點，可以將頂點位置作為約束條件。約束條件定義為：用帶約束的極值求解方法極小化目標函數得到未知量的值，即求解帶約束的優(yōu)化問題： （6）4.3 問題的求解我們用優(yōu)化方法求解（3），（5）和（6）三個目標函數11,12，確定隱式曲面系數的變化量。對于非線形優(yōu)化問題的求解，本文采用牛頓法和序列二次規(guī)劃方法（SQP）。（1）牛頓法是求解非線性優(yōu)化問題

12、的一種迭代方法。將非線性函數在初始值點處進行二次Taylor展開，求解該二次優(yōu)化問題的解，作為下一次求解的初始值。該方法在局部具有平方收斂速度。（2）SQP （Sequential Quadratic Programming）方法是求解帶約束的非線性問題的一種迭代方法，在每次迭代中求解一個二次規(guī)劃子問題（QP問題）。該子問題對目標函數進行二次逼近，對約束條件進行線性逼近。牛頓法和SQP方法都是局部優(yōu)化方法，在局部均具有收斂速度。在交互調整過程中，由于用戶的調整是逐步的，所求解的未知量是，在此每次求解設定的初始值是0，因為曲面的變化總是從系數的變化量開始，所以采用牛頓法或者SQP方法所得到的解一

13、定是局部極小解中的一個值。這樣做也保證了牛頓法和SQP方法在求解過程中的收斂性，從而得到正確的結果。在程序實現中本文使用了IMSL優(yōu)化函數庫13，用于提高目標函數求解速度和穩(wěn)定性。4.4 算法描述我們將基于頂點位置的調整和基于頂點法向的調整歸結為兩個交互算法如下：算法 1：輸入：隱式曲面；Step 1：用戶選定曲面上一點，得到位置控制手柄；Step 2：將指定的點進行拖拽到一個新的位置；Step 3：根據新位置建立目標函數（3）；Step 4：設定隱式曲面系數的變化量初始值為，極小化目標函數。用牛頓法求解的值；Step 5：將代入隱式曲面表達式得到調整后的曲面，繼續(xù)調用Step 2直至得到用戶

14、滿意的形狀。算法 2：輸入：隱式曲面；Step 1：用戶選定曲面上一點，得到其法向控制手柄；Step 2：將指定的點的法向圓錐拖拽到一個新的位置；Step 3：根據新位置建立目標函數（5）或者帶約束的優(yōu)化目標函數（6）；Step 4：設定隱式曲面系數的變化量初始值為，求解優(yōu)化問題極小化目標函數。用牛頓法求解無約束下法向調整的值，用SQP方法求解帶約束的法向調整的值；Step 5：將代入隱式曲面表達式得到調整后的曲面，繼續(xù)調用Step 2直至得到用戶滿意的形狀。5 實驗結果本節(jié)給出了基于頂點位置調整、無約束的法向調整和帶約束的法向調整的曲面實例。本節(jié)所實現的例子均是基于blobby surfac

15、e，在2.8GHz Pentium(R) 4 CPU、1GB 內存PC上用Visual Studio 2005實現。Blobby曲面是將基本體素：blobby圓柱、blobby橢球和blobby球體加在一起構成復雜曲面的一種表示。Blobby圓柱定義為圍繞一條給定線段的區(qū)域，其表達式為：。其中表示點到直線段的最近點位置，該直線段用兩個點坐標表示。其系數向量為7個參數：。直線段兩個端點坐標分別為：，為。Blobby橢球定義為對于一個中心點，三個坐標軸有不同的區(qū)域。其表達式為：。其中為中心點位置，為三個坐標軸上的不同軸長。其系數向量為6個參數：。中心點的坐標為：，三個軸長分別為。Blobby球體定

16、義為圍繞一個中心點的區(qū)域。其表達式為：。其中為中心點位置。其系數向量為4個參數：。中心點的坐標為：，為。如圖2中給出了兩個blobby曲面模型，其中圖2是blobby曲面的粒子繪制，圖3是blobby基本體素的網格繪制，圖4是blobby曲面的實體模型繪制。其中（a）為peanut曲面模型，為兩個blobby球體的和，（b）為doll曲面模型，為兩個blobby球體，一個橢球和四個圓柱體的和。圖2和圖3中曲面的表達式及其系數向量分別為：Peanut模型表達式為： （7）其中系數向量。Doll模型中包含兩個球體，一個橢球和四個圓柱，其表達式和系數向量分別為：(a) peanut模型(b) dol

17、l模型圖3 blobby曲面基本體素的網格表示(a) peanut模型(b) doll模型圖2 blobby曲面模型粒子表示(a) peanut模型(b) doll模型圖4 blobby曲面實體模型表示圖5給出了對于peanut模型曲面上一個頂點位置和法向進行調整的實例，其中（a）、（b）分別為初始blobby曲面的粒子模型和網格模型，藍色的圓盤表示選定的頂點。（c）、（d）分別為進行頂點調整之后得到的新曲面的粒子繪制和曲面繪制。（e）、（f）分別為進行法向調整之后得到的新曲面的粒子繪制和曲面繪制結果。從圖中可以看出，通過調整頂點的位置，可以將兩個blobby球體相加的曲面分離，這顯示了隱式曲

18、面容易改變其拓撲形狀的優(yōu)點。優(yōu)化目標函數為。圖6給出了對于peanut模型曲面進行無約束法向調整的結果，其優(yōu)化目標函數為：。牛頓法和SQP局部均具有收斂速度，并且粒子系統(tǒng)能夠實時地對曲面進行繪制，因此本文的方法可以達到對隱式曲面實時交互調整的效果。圖7中給出了對于doll曲面模型的交互調整實例，其中（a）為原始曲面的粒子表示；（b）為對曲面上某一頂點進行位置調整的結果；（c）為對指定頂點的法向進行無約束調整的結果；（d）為對指定頂點的法向進行帶約束調整的結果，約束條件為指定頂點的位置，優(yōu)化目標函數為，。(a) 初始模型(b) 調整結果I(c) 調整結果II(d) 初始實體模型圖5 對于pean

19、ut模型曲面頂點位置調整結果(e) 調整后實體模型I(f) 調整后實體模型II圖6 對于peanut模型曲面無約束法向調整結果(a) 初始模型及法向(b) 初始實體模型(c) 調整后曲面及法向(d) 調整后實體模型表1 圖5中調整結果的數據比較比較結果初始模型（a）頂點調整后I（b）頂點調整后II（c）所選頂點位置(0.108433,2.5004,0.199201)(0.749607,2.92466,1.22876)(0.833066,3.44722,1.15075)所花費時間(ms)06292曲面系數(0.1, 0, 1, 0, 1, 0, -1, 0, 1)(0.0948017, 0.03

20、3812, 2.13287, -0.0784693, 1.01861, -5.40194e-005, -1.00008, 9.42229e-005, 0.999906)(0.0929125, 0.0342821, 2.67257, -0.146967, 1.02698, -0.000188889, -1.00021, 0.000229093, 0.999771)表2 圖6中調整結果的數據比較(a) 初始模型及法向(c) 無約束法向調整(d) 帶約束法向調整圖 7 對于doll曲面模型的頂點位置和法向調整(b) 頂點位置調整比較結果初始模型（a）無約束法向調整后I（c）所選頂點法向(0.7406

21、5,0.576329,-0.345373)(-0.586766,-0.114165,-0.801668)所花費時間(ms)0105曲面系數(0.1, 0, 1, 0, 1, 0, -1, 0, 1)( 0.0995085, -0.228863, 2.1971, -0.252157, 1.00581, -0.00459666, -1.00906, 0.000906126, 0.969618)表1 圖5中調整結果的數據比較表2 圖6中調整結果的數據比較表3 圖7中調整結果的數據比較比較結果初始模型（a）頂點位置調整后（b）頂點位置(0.698444,2.54288,0.132953)(1.0260

22、6,-1.31355,-0.0610136)頂點法向(0.582545,0.812232,-0.0303365)(0.52527,-0.186199,-0.830314)所花費時間(ms)038曲面系數比較結果無約束法向調整后（c）帶約束法向調整后（d）頂點位置(-0.50773,4.15044,0.659245)(1.02606,-1.31355,-0.0610136)頂點法向(0.754179,-0.469746,-0.458861)(-0.394431,0.599146,0.696741)所花費時間(ms)4662曲面系數其中表示如下：在圖8的例子中，在doll模型曲面上指定五個控制點，

23、然后分別拖拽五個點將doll模型的四肢拉長，并將頭部拖拽至脫離軀干，從而改變原始模型的形狀，可以看出新的交互調整方法也可以很容易改變原始曲面的拓撲結構。(a) 初始模型及被調整頂點(b) 初始實體模型(c) 調整后模型及頂點(d) 調整后實體模型圖 8 對于doll模型曲面多個頂點位置的調整結果6 結論本文提出了一種新的隱式曲面交互調整方法，新方法利用了隱式曲面表達式的為零值面的特性，對于頂點位置調整、無約束的頂點法向調整和帶約束的頂點法向調整三種曲面調整方式分別建立目標函數約束，用優(yōu)化方法極小化目標函數得到隱式曲面系數的變化量。新方法可以在用戶進行交互調節(jié)的同時得到調整之后的隱式曲面，從而達

24、到實時調整的目的。本文的主要工作可以概括為：1）曲面交互調整方法適用于一般隱式曲面；2）可以指定在隱式曲面上的任意一點進行位置或者法向的交互調整；3）交互調整能夠達到實時效果。為了更好的從整體上控制曲面的形狀,我們在以后的工作中會嘗試引入能量約束，以得到更好的控制效果。參考文獻1 Chandrajit Bajaj, Insung Ihm, and Joe Warren. Higher-order interpolation and least-squares approximation using implicit algebraic surfaces. ACM Trans. on Graph

25、ics, 12(4):327347, 1993.2 David Baraff. Analytical methods for dynamic simulation of non-penetrating rigid bodies. Computer Graphics, 23(3):223232, 1989.3 Jules Bloomenthal. Polygonization of implicit surfaces. Computer Aided Geometric Design, 5:341355, 1988.4 J. F. Blinn. A generalization of algebr

26、aic surface drawing. ACM Transactions on Graphics, 1(3):235256, 1982.5 A. P. Witkin and P. S. Heckbert. Using particles to sample and control implicit surfaces. In Computer Graphics (Annual Conference Series): 269277, 1994.6 J. C. Hart, E. Bachta, W. Jarosz, and T. Fleury. Using particles to sample

27、and control more complex implicit surfaces. In Proceedings of Shape Modeling International, 2002.7 W. Schroeder, W. Lorensen, and S. Linthicum. Implicit modeling of swept surfaces and volumes. Proc. Visualization 94, 4045, 1994.8 WAN Hua-Gen , JIN Xiao-Gang , LIU Gang , FENG Jie-Qing , PENG Qun-Shen

28、g. Mesh Fusion Based on Variational Implicit Surfaces. Journal of software, 16(11):2000-2007, 2005.(in Chinese)(萬華根,金小剛,劉剛,馮結青,彭群生, 基于變分隱式曲面的網格融合, 軟件學報, 16(11):2000-2007, 2005)9 B. T. Stander and J. C. Hart. Guaranteeing the topology of an implicit surface polygonization for interactive modeling. In

29、 Computer Graphics (Annual Conference Series): 279286, Aug. 1997.10 Greg Turk, James F. OBrien, Modelling with Implicit Surfaces that Interpolate. ACM Transactions on Graphics, Vol 21(4), 2002.11 Poul Erik Frandsen, Kristian Jonasson, UNCONSTRAINED OPTIMIZATION, 3. Edition, Informatics and Mathemati

30、cal Modelling Technical University of Denmark, 2004.12 K. Madsen, H.B. Nielsen, O. Tingleff, OPTIMIZATION WITH CONSTRAINTS, 2nd Edition, Informatics and Mathematical Modelling Technical University of Denmark, 2004.13 IMSL C Library, Users Guide. Visual Numerics, Inc.A New Interactive Method for Cont

31、rolling Implicit SurfacesZhou Yuan-Feng1 Bo Peng-Bo3 Zhang Cai-Ming1，21. School of Computer Science and Technology, Shandong University, Jinan, 2501012. School of Computer Science and Technology, Shandong Economic University, Jinan, 2500143. Department of Computer Science, The University of Hong Kon

32、gAbstract: This paper proposes a new interactive method for controlling implicit surfaces. Two interactive controlling tools are introduced: position controlling handle and normal controlling handle. The new implicit surfaces are required to interpolate the adjusted position and normal vector at des

33、ired vertices on surfaces, which are appointed by user interaction. This problem can be treated as an optimization one. Newton and SQP methods are applied to solve it respectively. Particle system is used for real-time rendering of implicit surface. This provides a real-time and interactive method f

34、or controlling the shape of implicit surfaces. Experiences are included in the end to demonstrate the efficiency of the new method.Keywords: Implicit surface; Interactive control; Optimization; Blobby surface; Particle systemBackgroundAs the developments of computer graphics and computer aided desig

35、n, implicit surfaces have been increasingly used for modeling, visualizing and animation. In geometric modeling, comparing with parametric surfaces, implicit surface has three obvious advantages: one is implicit surface's simple expression form which can be described in the form of , another is

36、it is easy to judge the relative position to a special point, and the third is implicit surface has high smoothness. Implicit surfaces are useful for describing continuous and smoothly blend surfaces with complex topology, and can change the topology of surfaces easily. However, effect of coefficien

37、ts of an implicit surface is not intuitive. So the main drawback of implicit surfaces is difficult to control and model implicit surfaces interactively. Based on above problems, a new interactive controlling method for implicit surfaces is presented. For general implicit surfaces, shape controlling is essential on how to determine the coefficients of the new implicit surfaces. Position and normal of a selected vertex on surface controlling are used as two