基于曲率球的參數(shù)曲面自適應(yīng)三角化方法研究

1、 PAGE 9基于曲率球的參數(shù)曲面自適應(yīng)三角化方法研究楊偉民1,2，樓天良1，林志偉2，沈洪垚21.義烏工商職業(yè)技術(shù)學(xué)院機(jī)電信息分院，義烏，322000 2.浙江大學(xué)現(xiàn)代制造工程研究所，杭州，310027摘要：參數(shù)曲面的三角化算法是有限元分析和數(shù)控機(jī)床路徑規(guī)劃的基礎(chǔ)。文中提出了一種新的基于分層遞推思想的三角化算法，直接在曲面上生成三角網(wǎng)格。根據(jù)曲面微分幾何定義相對(duì)保守的曲率球概念，將局部曲面近似成曲率球面，在球面上建立三角形邊和面片的誤差模型和遞推關(guān)系，計(jì)算三角形各個(gè)頂點(diǎn)在歐式空間以及參數(shù)空間的坐標(biāo)。然后采用逐層遞推的方法，從曲線(xiàn)邊界開(kāi)始，逐層生成三角形網(wǎng)格，直至滿(mǎn)足收斂準(zhǔn)則。文章最后將此算法

2、用C+程序語(yǔ)言編程并通過(guò)NURBS曲面進(jìn)行實(shí)例驗(yàn)證，結(jié)果表明該算法能夠較好的對(duì)參數(shù)曲面進(jìn)行三角網(wǎng)格劃分。關(guān)鍵詞：參數(shù)曲面；三角化；曲率球；誤差控制中圖分類(lèi)號(hào)：TP391.73Parametric surface triangulation based on curvature sphereWeimin Yang1,2，Tianliang Lou1，Zhiwei Lin2，Hongyao Shen21.Yiwu Industrial & Commercial College，Yiwu，322000 2.Zhejiang University，Hangzhou，310027Abstract：Par

3、ametric surface triangulation algorithm is the basis of both the finite element method and the tool path generation in CNC machining. In this paper, a new method is proposed to directly generate triangular meshes on the surface through a layered recursive method. The concept of curvature sphere is d

4、efined. The local surface is approximated to be the spherical surface of the curvature sphere. On the curvature surface, the error models of the triangular mesh and the original surface are established and the coordinates of the triangular vertexes, both in the parametric domain and the Euclidean sp

5、ace, are calculated. Then the layered recursive method is applied to generate the triangular meshes layer by layer from the boundary of the surface until the convergent condition is met. The proposed method is implemented in C+ programing language and is tested by a NURBS surface example. Results sh

6、ow that the proposed method can deal well with the parametric surface triangulation problem.Keywords：Parametric surface; triangulation; curvature sphere; error control0 引言三角化是指對(duì)已知曲面方程的參數(shù)曲面進(jìn)行三角形離散劃分。它是有限元分析和數(shù)控機(jī)床路徑規(guī)劃的基礎(chǔ)。三角化算法的優(yōu)劣直接關(guān)系到這些計(jì)算的計(jì)算量和準(zhǔn)確度。首先要求保證三角化離散的精度，即保證自由曲面離散后的三角面片能夠逼近原始曲面；其次要求離散具有自適應(yīng)性，即生成的

7、三角面片的疏密程度能夠隨著曲面曲率變化而變化，在曲面曲率大的地方生成的三角面片致密一些，而在曲面曲率小的地方生成的三角面片相對(duì)稀疏一些。由于路徑規(guī)劃中干涉檢測(cè)算法需要遍歷曲面中所有三角面片，所以在保證精度的前提下，曲面三角面片數(shù)量越少越好。對(duì)參數(shù)曲面而言，最簡(jiǎn)單、最直觀(guān)的三角化方法是映射法。這種方法先在參數(shù)空間實(shí)現(xiàn)平面三角化，如Delaunay平面三角剖分 ADDIN EN.CITE ADDIN EN.CITE.DATA HYPERLINK l _ENREF_1 o Cignoni, 1998 #252 1, HYPERLINK l _ENREF_2 o 余杰, 2010 #9 2，然后將得到

8、的三角形映射到歐式空間。這種方法由于參數(shù)空間和歐式空間的映射沒(méi)有空間形態(tài)的必然聯(lián)系，得到的三角面片沒(méi)有自適應(yīng)性，難以評(píng)價(jià)三角化精度 ADDIN EN.CITE 王青2003131117王青程艷旗林海鮑虎軍浙江大學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,浙江大學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,浙江大學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,浙江大學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室 浙江杭州310027 ,浙江杭州310027 ,浙江杭州310027 ,浙江杭州310027隱函數(shù)曲面的實(shí)時(shí)采樣與三角化技術(shù)浙江大學(xué)學(xué)報(bào)(理學(xué)版)浙江大學(xué)學(xué)報(bào)(理學(xué)版)621-62706隱函數(shù)曲面多邊形化曲面離散20031008-949733-1246/NCnki HYPERLINK l _ENRE

9、F_3 o 王青, 2003 #1 3。徐松等在傳統(tǒng)映射法的基礎(chǔ)上，在平面三角化算法中環(huán)邊統(tǒng)一處理，采用自適應(yīng)三角網(wǎng)格加密法，有效地處理帶有特征約束條件的任意曲面三角剖分問(wèn)題 ADDIN EN.CITE 徐松2000242217徐松王劍英中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系!合肥230027,中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系!合肥230027曲面的自適應(yīng)三角網(wǎng)格剖分計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)267-27104三角剖分特征約束自適應(yīng)網(wǎng)格加密曲面200011-2925/TP11-2925/TPCnki HYPERLINK l _ENREF_4 o 徐松, 2000 #2 4。關(guān)振群等提出一種

10、基于映射法的復(fù)雜三維組合曲面的有限元網(wǎng)格全自動(dòng)生成方法，通過(guò)引入虛邊界解決了閉合曲面在參數(shù)域中邊界不完整的問(wèn)題，并通過(guò)調(diào)節(jié)虛邊界提高了復(fù)雜組合曲面網(wǎng)格生成的質(zhì)量 ADDIN EN.CITE 關(guān)振群2003353317關(guān)振群隋曉峰顧元憲李云鵬大連理工大學(xué)工業(yè)裝備結(jié)構(gòu)分析國(guó)家重點(diǎn)實(shí)驗(yàn)室,大連理工大學(xué)工業(yè)裝備結(jié)構(gòu)分析國(guó)家重點(diǎn)實(shí)驗(yàn)室,大連理工大學(xué)工業(yè)裝備結(jié)構(gòu)分析國(guó)家重點(diǎn)實(shí)驗(yàn)室,大連理工大學(xué)工業(yè)裝備結(jié)構(gòu)分析國(guó)家重點(diǎn)實(shí)驗(yàn)室 大連116024 ,大連116024 ,大連116024 ,大連116024復(fù)雜三維組合曲面的有限元網(wǎng)格生成方法計(jì)算力學(xué)學(xué)報(bào)計(jì)算力學(xué)學(xué)報(bào)409-41604網(wǎng)格剖分閉合曲面虛邊界組合曲面

11、20031007-470821-1373/O3Cnki HYPERLINK l _ENREF_5 o 關(guān)振群, 2003 #3 5。吳寶海等采用改進(jìn)波前法對(duì)曲面進(jìn)行三角化細(xì)分，從曲面兩條邊界向曲面中心同時(shí)推進(jìn)，避免了常規(guī)波前法中由于曲面角點(diǎn)的不良形態(tài)導(dǎo)致網(wǎng)格規(guī)劃的失敗以及生成低質(zhì)量的網(wǎng)格 ADDIN EN.CITE 吳寶海2005464417吳寶海王尚錦西安交通大學(xué)能源與動(dòng)力工程學(xué)院,西安交通大學(xué)能源與動(dòng)力工程學(xué)院 西安710049 ,西安710049參數(shù)曲面網(wǎng)格生成的改進(jìn)波前法計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)1686-169008參數(shù)曲面三角剖分波前法20051003-9

12、77511-2925/TPCnki HYPERLINK l _ENREF_6 o 吳寶海, 2005 #4 6。梁義等結(jié)合映射法和前沿推進(jìn)技術(shù)，通過(guò)曲率計(jì)算自動(dòng)識(shí)別曲率特征并創(chuàng)建密度場(chǎng)，對(duì)組合參數(shù)曲面生成幾何自適應(yīng)的網(wǎng)格 ADDIN EN.CITE 梁義2010676617梁義,陳建軍,陳立崗,鄭耀,幾何自適應(yīng)參數(shù)曲面網(wǎng)格生成計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)327-33520102曲面網(wǎng)格生成 自適應(yīng) Delaunay三角化 黎曼度量 中軸20101003-977597390XVIP HYPERLINK l _ENREF_7 o 梁義, 2010 #6 7。李李等利用均勻采

13、樣點(diǎn)來(lái)估算曲面曲率，針對(duì)裁剪曲面進(jìn)行三角剖分，提高剖分效率和精度 ADDIN EN.CITE 李李2006585517李李 王亞平 裁剪曲面自適應(yīng)三角化剖分計(jì)算機(jī)應(yīng)用計(jì)算機(jī)應(yīng)用2006年S1期TP391.41針對(duì)CAD/CAM領(lǐng)域中裁剪曲面的三角剖分問(wèn)題,從提高效率和滿(mǎn)足剖分精度的角度出發(fā),提出了一種較為實(shí)用的自適應(yīng)離散方法,與傳統(tǒng)的自適應(yīng)方法相比,三角片數(shù)量有所減少,速度有明顯的提高。2006 HYPERLINK l _ENREF_8 o 李李, 2006 #5 8。王飛等基于B樣條曲面的適應(yīng)性分割，將背齊爾曲面片的三角化處理擴(kuò)展到整張曲面，消除相鄰面間邊界處可能出現(xiàn)的裂縫 ADDIN EN

14、.CITE 王飛1997797717王飛,董國(guó)輝,基于b樣條曲面適應(yīng)性分割的三角化算法北京郵電大學(xué)學(xué)報(bào)北京郵電大學(xué)學(xué)報(bào)95-98202計(jì)算機(jī)圖形學(xué) B樣條曲面 三角化算法19971007-532191520AVIP HYPERLINK l _ENREF_9 o 王飛, 1997 #7 9。Shimada等則提出用BMG（Bubbul Mesh Generation）對(duì)曲面進(jìn)行三角化 ADDIN EN.CITE Shimada19988108817Shimada, KenjiGossard, David C.Automatic triangular mesh generation of trim

15、med parametric surfaces for finite element analysisComputer Aided Geometric DesignComputer Aided Geometric Design199-222153TriangulationDelaunay triangulationVoronoi polygonsSphere packingPhysically based modelBubble meshingDynamic simulationFinite element analysis19980167-8396/science/article/pii/S

16、016783969700037X/10.1016/S0167-8396(97)00037-X HYPERLINK l _ENREF_10 o Shimada, 1998 #8 10。在本文中，我們結(jié)合曲面的局部微分幾何，提出曲率球概念，在局部范圍內(nèi)，用曲率球近似曲面，在曲率圓上直接近似生成三角面片，并利用分層遞推思想，將生成的的三角片面覆蓋至整張曲面。1 參數(shù)曲面的微分幾何對(duì)于給定的參數(shù)曲面，只要知道參數(shù)域內(nèi)的任意一點(diǎn)坐標(biāo)值，就可以根據(jù)相應(yīng)的公式計(jì)算出曲面在歐式空間內(nèi)對(duì)應(yīng)的點(diǎn)，以及曲面在該點(diǎn)的一階、二階偏導(dǎo)、和單位法向量。曲面在點(diǎn)處的法曲率可以表示為： （1）其中：，為曲面第一基本型；，為曲面

17、第二基本型。根據(jù)式(1)可以得到曲面在該點(diǎn)的主曲率： （2）其中：；。圖1 曲面的微觀(guān)幾何特性不妨設(shè)，根據(jù)、在數(shù)軸上取值正負(fù)不同，可以把曲面的微觀(guān)幾何特性分成5種情況，如圖1所示。圖1b所示為橢圓拋物面，對(duì)應(yīng)圖1a中的第1和第5兩種情況，即、同時(shí)為正或同時(shí)為負(fù)。當(dāng)、同時(shí)為正時(shí)，橢圓拋物面開(kāi)口朝上；當(dāng)、同時(shí)為負(fù)時(shí)，橢圓拋物面開(kāi)口朝下。圖1c所示為拋物面，對(duì)應(yīng)圖1a中的第2和第4兩種情況，即、兩者中其中有一個(gè)為零。當(dāng)為零時(shí)，拋物面開(kāi)口朝下；當(dāng)為零時(shí)，拋物面開(kāi)口朝下。圖1d所示為猴鞍面，對(duì)應(yīng)圖1a中的第3中情況，即為正，為負(fù)。為了簡(jiǎn)化討論和計(jì)算，引入曲率球的概念。曲率球的定義如下：設(shè)、為曲面上處的兩

18、個(gè)主曲率，取，把球心在過(guò)的法線(xiàn)上，半徑為的球稱(chēng)為曲面在點(diǎn)的曲率球。由曲率球的定義可知，曲率球是以曲面上某點(diǎn)的極大曲率為半徑建立的球面，因此在將曲面附近的點(diǎn)轉(zhuǎn)移到曲率球上考慮，從誤差角度上講，是偏安全的。2 單個(gè)三角面片生成及誤差控制上節(jié)定義了曲率球的概念，本文涉及到的誤差都是將曲面局部近似到曲率球面上分析的。本節(jié)詳述在給定的精度條件下曲面上單個(gè)三角面片的生成。2.1 曲線(xiàn)上弦生成在考慮在曲面上獲得一條符合精度要求的三角形邊之前，先考慮在曲線(xiàn)上獲得一條符合精度要求的弦。對(duì)空間參數(shù)曲線(xiàn)及其曲線(xiàn)上的一個(gè)已知點(diǎn)，在曲線(xiàn)上點(diǎn)附近求點(diǎn)，使得弦和原始曲線(xiàn)段之間的弓高誤差為不大于給定的弦容差。近似地，本文在點(diǎn)

19、的曲率圓上考慮問(wèn)題。如圖2所示，設(shè)曲線(xiàn)上弦長(zhǎng)度為，近似用圓上的弦代替。在圓中，為中點(diǎn)，連接交圓于點(diǎn)，則線(xiàn)段就是弦的弓高，也即原始曲線(xiàn)上弦的弓高。設(shè)曲線(xiàn)上點(diǎn)曲率圓半徑為，在中，易得：圖2 在曲線(xiàn)上得到一條符合精度要求的弦 （3）對(duì)式（3）忽略2次小量，得：。由上可知，只要保證，就能保證弦的精度。臨界情況下，弦的長(zhǎng)度可以表示為： （4）下面根據(jù)式（4）中得到的值反向近似求解點(diǎn)參數(shù)值。設(shè)一質(zhì)點(diǎn)沿著曲線(xiàn)運(yùn)動(dòng)，在某點(diǎn)速率為，方向?yàn)榍€(xiàn)切線(xiàn)方向。曲線(xiàn)的參數(shù)是時(shí)間的變量，寫(xiě)成，隨著時(shí)間遞增，因此。由于： （5）所以： （6）令，它們分別代表，點(diǎn)參數(shù)值。對(duì)在處一階泰勒展開(kāi)并將（6）式代入得： （7）為質(zhì)點(diǎn)走過(guò)

20、的路程，近似認(rèn)為該路程等于弦長(zhǎng)度，即：。將式（4）代入（7）式，得： （8）根據(jù)式（8）即可求出點(diǎn)的參數(shù)值，在曲線(xiàn)上的位置可完全確定。運(yùn)用上述方法可以求得任意曲線(xiàn)上一條符合精度要求的弦。2.2 曲面上弦生成下面考慮在曲面上獲得一條符合精度要求的弦，即三角形的一條邊。設(shè)是曲面上一點(diǎn)，其參數(shù)坐標(biāo)為；球?yàn)辄c(diǎn)處的曲率球；是曲面上領(lǐng)域內(nèi)的任意一點(diǎn)。當(dāng)趨近，即時(shí)，近似認(rèn)為點(diǎn)落在球的球面上；那么曲面上弦的弓高就是弦的兩個(gè)端點(diǎn)都落在球上時(shí)的最大弓高，即在球最大圓上的弓高。圖3 在曲面上得到一條符合精度要求的弦如圖3所示，考慮過(guò)點(diǎn)的、向曲線(xiàn)，由式（8）可在、向曲線(xiàn)上分別找到符合弓高誤差的弦和弦： （9） （10

21、）式（9）、（10）中為曲率球的半徑，為弦、容許誤差，、分別為曲面對(duì)、的一階偏導(dǎo)。式（9）、（10）中用曲率球半徑求出的、值是偏安全的。如圖3所示，分析點(diǎn)的誤差，點(diǎn)坐標(biāo)可以表示為。令為，的夾角，記弦長(zhǎng)度為，、長(zhǎng)度分別為、，則由圖3可知： （11）式（11）中， 長(zhǎng)度隨著變化而變化。顯然，在曲率球面上，當(dāng)最長(zhǎng)時(shí)，弓高誤差最大。因此在最壞的情況下，即時(shí)，此時(shí)。而由式（4）可知，因此可得曲面上弦的最大弓高誤差為： （12）要保證弦的弓高誤差小于給定弦容差，即，只需保證： （13）即在計(jì)算式（9）、（10）中的、時(shí)的容許誤差要小于給定弦容差的四分之一。2.3 曲面上三角形生成本文中提出的生成三角形面片

22、的算法是遞推的，因此認(rèn)為的一條邊的兩個(gè)端點(diǎn)在三維空間的坐標(biāo)以及在參數(shù)域內(nèi)值已經(jīng)在前一步中計(jì)算出來(lái)。這里要考慮的問(wèn)題是如何根據(jù)這條已知邊在曲面上找到第三個(gè)點(diǎn)，使得點(diǎn)分別和，連起來(lái)之后得到的盡量能夠符合精度要求。 如圖4所示，用2.1中的方法，對(duì)點(diǎn)進(jìn)行一次運(yùn)算，在參數(shù)域內(nèi)得到點(diǎn)坐標(biāo)；同理對(duì)點(diǎn)進(jìn)行運(yùn)算，在參數(shù)域內(nèi)得到點(diǎn)坐標(biāo)，這里用是讓盡量靠近，從而提高精度。取中點(diǎn)，其在參數(shù)域內(nèi)坐標(biāo)為：由此得到的就是所要求的三角形，如圖4。下面對(duì)進(jìn)行誤差分析。在微觀(guān)情況下，由于三邊是在同一點(diǎn)鄰域內(nèi)產(chǎn)生的弦，在這點(diǎn)鄰域內(nèi)曲面的曲率變化很小，近似認(rèn)為這三邊所在的曲率球的半徑相同。由于三邊弓高一樣，所以的三條邊長(zhǎng)相同，認(rèn)為

23、是等邊三角形。圖4 在曲面上得到一個(gè)符合精度要求的三角形的三個(gè)頂點(diǎn)都落在曲面上，近似情況下以三角形其中一個(gè)頂點(diǎn)的曲率球代替附近曲面。如圖5所示，垂直于所在平面交球面于，則所在平面到曲面的弓高就近似為長(zhǎng)度。圖5三角面片在曲率球上的近似弓高圖6 三角形面片弓高和三角形邊弓高的關(guān)系如圖6所示，圓弧為球大圓上的圓弧，球半徑為，即為在2.2中弦最大弓高誤差。則在直角中： （14）在直角中，： （15）在直角中： （16）令，則： （17）忽略平方項(xiàng)，得： （18）所以要想把的弓高誤差限定在，只要在2.2中保證： （19）綜合式（13）、（19），若要保證三角面片生成精度，只需在計(jì)算式（9）、（10）中的

24、、時(shí)的容許誤差要小于給定弦容差的四分之一。3 三角網(wǎng)格生成第2節(jié)中介紹了曲面上單個(gè)三角面片的生成以及誤差控制方法，下面闡述曲面三角網(wǎng)格生成。三角網(wǎng)格生成時(shí)遵循“點(diǎn)對(duì)點(diǎn)，邊對(duì)邊”原則，即每個(gè)三角形的頂點(diǎn)必須對(duì)應(yīng)另外三角形的頂點(diǎn)，每個(gè)三角形的邊對(duì)應(yīng)另外三角形的邊；不允許出現(xiàn)某個(gè)三角形的頂點(diǎn)對(duì)應(yīng)另外三角形的邊，否則生成的三角網(wǎng)格會(huì)出現(xiàn)裂縫。本文提出一種分層遞推生成三角面片的方法，直接在參數(shù)曲面上生成三角網(wǎng)格，生成的三角網(wǎng)格無(wú)裂縫而且符合精度要求。對(duì)一張參數(shù)曲面，其中，如圖7所示，其邊界線(xiàn)分別是線(xiàn)，線(xiàn)，線(xiàn)，線(xiàn)。按照本文提出的分層遞推方法對(duì)曲面逐層進(jìn)行三角網(wǎng)格劃分，假設(shè)第層劃分結(jié)束后形成的的圖形如圖7所

25、示，其中左邊有三角網(wǎng)格的是已經(jīng)進(jìn)行三角劃分過(guò)的曲面，右邊的是沒(méi)有進(jìn)行三角劃分的曲面，它們之間的分界折線(xiàn)是由當(dāng)前一層三角形的邊首尾依次連接得到的，記這一層折線(xiàn)為第層折線(xiàn)。下面對(duì)第層折線(xiàn)進(jìn)行輪廓更行，同時(shí)在曲面上生成三角形，得到第層三角形面片。圖7 第k層三角面片生成圖8 折線(xiàn)段輪廓更新分析第層折線(xiàn)段、，首先考慮，夾角。當(dāng)時(shí)，則直接連接得到，同時(shí)刪除、，成為新的，成為，下面的線(xiàn)段序號(hào)依次減1。下一個(gè)分析對(duì)象為。當(dāng)時(shí)，則對(duì)線(xiàn)段和夾角考慮。當(dāng)時(shí)，則直接連接得到，同時(shí)刪除、，成為新的，下面的線(xiàn)段序號(hào)都不變。下一個(gè)分析對(duì)象為。當(dāng)，那么對(duì)根據(jù)兩端點(diǎn)，按照2.3節(jié)中方法計(jì)算出曲面上一點(diǎn)，得到的，同時(shí)刪除，成為

26、新的，成為新的，成為新的。下一個(gè)分析對(duì)象是。圖8所示的情況由于得到的新三角形面片都在折線(xiàn)右側(cè)，即在曲面未三角化區(qū)域，此時(shí)不存在問(wèn)題。但當(dāng)?shù)玫降男氯切蚊嫫谡劬€(xiàn)左側(cè)，也就是在曲面已經(jīng)三角化的區(qū)域，此時(shí)新三角形會(huì)和原來(lái)的三角形重疊起來(lái)，這種情況應(yīng)該避免。事實(shí)上，圖8中的夾角是根據(jù)向量，得到的： （20）式（8）無(wú)法計(jì)算當(dāng)線(xiàn)段和的夾角大于180時(shí)的情況。而新三角形出現(xiàn)在左邊正是因?yàn)闆](méi)有檢測(cè)到和夾角大于180的情況。為此引入凹角以及凸角，直觀(guān)的，相對(duì)于右邊還沒(méi)有三角化了的區(qū)域，當(dāng)角是圖8中的情況時(shí)，認(rèn)為是凹角，它是凹向未三角化區(qū)域的；當(dāng)是圖9的情況時(shí)，認(rèn)為是凸角，它是凸向未三角化區(qū)域的。圖9 凸角定

27、義以上根據(jù)觀(guān)察給出了凹凸角的簡(jiǎn)單定義，下面給出凹凸角精確的數(shù)學(xué)定義。點(diǎn)位于曲面上，如圖8所示，點(diǎn)法向量可由得到。令向量，理論上當(dāng)生成的三角面片無(wú)窮小的時(shí)候，都是位于的切平面上的，此時(shí)有和方向完全一致。而實(shí)際上因?yàn)樯傻娜切尾豢赡軣o(wú)窮小，和方向不可能真正完全一致。人為規(guī)定一個(gè)，向量方向一致的判據(jù)。設(shè)向量和向量的夾角，人為規(guī)定當(dāng)時(shí)，和同向；當(dāng)時(shí)，和反向。而當(dāng)和同向時(shí)，是凸角；當(dāng)和反向時(shí)，是凹角。所以在前述的算法中，加上對(duì)的判斷，如果是凸角，則跳出直接去判斷和的夾角是凹角還是凸角。如果是凹角，則進(jìn)入判斷的情況。3.1 邊界處理以上討論中沒(méi)有涉及到曲面邊界，下面針對(duì)邊界進(jìn)行討論。對(duì)第層折線(xiàn)的第一條線(xiàn)

28、段，它的起點(diǎn)所在的曲面邊界可能有3種情況。如圖10所示，分別是在線(xiàn)上，在線(xiàn)上，在線(xiàn)上。這三種情況可以簡(jiǎn)單地從點(diǎn)的參數(shù)坐標(biāo)判斷出來(lái)。分析在線(xiàn)上這種情況，其他也是類(lèi)似的。在圖10中，為線(xiàn)和線(xiàn)在的切線(xiàn)的夾角。當(dāng)時(shí)，按照2.1節(jié)中方法在線(xiàn)上得到一段符合精度要求的弦,得到的三角形作為一個(gè)新的三角形，同時(shí)刪除，將變?yōu)?，其他都保持不變。而?dāng)時(shí)，則在考慮和的所成角的凹凸情況。如果是凸角則直接根據(jù)兩端點(diǎn)、按2.3節(jié)中方法形成新三角形，同時(shí)處理；如果和的所成角是凹角，計(jì)算和的角度：如果該角度大于90則按照2.3方法根據(jù)、形成新三角形，同時(shí)處理，否則連接、以及端點(diǎn)得到新的三角形，同時(shí)處理。對(duì)層折線(xiàn)段的最后一條線(xiàn)處理

29、和第一條線(xiàn)是類(lèi)似的。也分為三種情況，的終點(diǎn)分別和線(xiàn)，線(xiàn)，線(xiàn)相交；處理也和類(lèi)似，都是遵循先和前一條線(xiàn)段求角，然后再考慮分別和曲面界面的切線(xiàn)求角，這里不再贅述。圖10 網(wǎng)格生成邊界處理 圖11 網(wǎng)格生成的收斂條件3.2 網(wǎng)格的起始和收斂遞推法對(duì)曲面進(jìn)行三角化處理依賴(lài)于第一層折線(xiàn)段的生成。本文中第一層折線(xiàn)段取自曲面邊界，用2.1節(jié)中方法在邊界曲線(xiàn)上連續(xù)取出一系列折線(xiàn)段。下面分析網(wǎng)格生成的收斂條件?？梢韵胂螽?dāng)網(wǎng)格生成快要結(jié)束的時(shí)候，對(duì)應(yīng)的那一層折線(xiàn)段會(huì)碰到曲面的邊界，如圖11所示。每一層折線(xiàn)段的起點(diǎn)和終點(diǎn)都落在曲面的邊界上，在每一層折線(xiàn)段對(duì)每條線(xiàn)段生成三角形之前，先對(duì)這條的終點(diǎn)進(jìn)行判斷，如果的終點(diǎn)在邊

30、界上，那么的起點(diǎn)也必然在曲面邊界上，跳過(guò)和，下一個(gè)要分析的是；如果的終點(diǎn)不在邊界上，則照常處理。對(duì)這樣一層處理結(jié)束之后對(duì)新得到逐個(gè)掃描，判斷終點(diǎn)是否落在邊界上，并記錄終點(diǎn)落在邊界上的個(gè)數(shù)，記為。當(dāng)滿(mǎn)足： （21）則可以判斷曲面三角網(wǎng)格生成結(jié)束。最后再針對(duì)生成最后一層三角形，結(jié)束網(wǎng)格生成。4 實(shí)例演示本文提出的算法用C+語(yǔ)言編程，以下用一張NURBS曲面驗(yàn)證本文算法。該曲面的控制頂點(diǎn)信息如下：節(jié)點(diǎn)矢量分別為：權(quán)值系數(shù)為： 。三角化結(jié)果如圖12所示。由圖12可知，本文算法能夠較好地對(duì)參數(shù)曲面進(jìn)行三角化，在曲面曲率小的地方，能夠生成較疏的三角網(wǎng)格；而在曲率大的地方，生成相對(duì)密的三角網(wǎng)格。圖12 NURBS曲面三角化實(shí)例5 總結(jié)三角化算法是有限元分析和數(shù)控機(jī)床路徑規(guī)劃的基礎(chǔ)。本文提出了一種新的針對(duì)自由曲面三角化的算法。定義了曲率球的概念，將復(fù)雜的曲面誤差模型轉(zhuǎn)化到曲率球上考慮，大大簡(jiǎn)化了誤差計(jì)算。先后在曲面上獲得符合精度要求的弦和三角形面片。在此基礎(chǔ)上，利用遞推算法，從曲面邊界開(kāi)始，逐層遞推生成三角網(wǎng)格，并確定了三角網(wǎng)格生成的收斂條件。本文算法經(jīng)過(guò)實(shí)例驗(yàn)證，表明算法確實(shí)有效。參考文獻(xiàn) ADDIN EN.REFLIST 1.Cignoni P, Montani C, Scopigno R (1998) DeWall: A fast divide and c