基于Delaunay三角剖分的測(cè)頭半徑補(bǔ)償算法

趙小軍

ZHAO Xiao-jun

（九江學(xué)院 數(shù)控技術(shù)與應(yīng)用實(shí)驗(yàn)室，九江 332005）

0 引言

三坐標(biāo)測(cè)量機(jī)以其優(yōu)異的智能化程度和測(cè)量精確度被廣泛的應(yīng)用于制造業(yè)的質(zhì)量控制、產(chǎn)品檢測(cè)和計(jì)算機(jī)輔助設(shè)計(jì)當(dāng)中。在對(duì)自由曲面進(jìn)行測(cè)量時(shí)，需要用到三坐標(biāo)測(cè)量機(jī)的球形測(cè)頭，但是測(cè)頭自身也是有一定的體積的，因此測(cè)量結(jié)果實(shí)際上是與被測(cè)量曲面距離為r（測(cè)頭半徑）的包絡(luò)面，所以，為了得到所需要的測(cè)量數(shù)據(jù)，就必須求出由測(cè)頭圓心部位軌面所形成的包絡(luò)面，也就是所謂的測(cè)頭半徑補(bǔ)償。在一些對(duì)精度要求較高的測(cè)量工作中，無法忽略測(cè)頭半徑對(duì)測(cè)量數(shù)據(jù)所造成的影響，這樣，就需要一個(gè)科學(xué)的半徑補(bǔ)償算法來對(duì)測(cè)頭半徑所產(chǎn)生的誤差進(jìn)行消除。

1 常用的半徑補(bǔ)償算法

1.1 二維補(bǔ)償法

二維補(bǔ)償法的操作方法比較簡(jiǎn)單，使用范圍需也相對(duì)較廣，該方法在測(cè)量時(shí)會(huì)把測(cè)量點(diǎn)與測(cè)頭半徑之間的關(guān)系轉(zhuǎn)化為二維情況，現(xiàn)階段比較常用的二維測(cè)量法有三點(diǎn)共圓法和測(cè)量方向補(bǔ)償法。

1.2 三維補(bǔ)償法

在對(duì)一些形狀規(guī)則的表面（如二次曲面、平面等）進(jìn)行測(cè)量時(shí)，二維補(bǔ)償是比較精確的，而在對(duì)一些形狀較為復(fù)雜的曲面（如增加器葉輪葉面）進(jìn)行測(cè)量時(shí)，測(cè)點(diǎn)位置的曲面法向適量則往往與上述補(bǔ)償方向分別位于不同的平面內(nèi)，如果繼續(xù)使用二維補(bǔ)償勢(shì)必會(huì)出現(xiàn)誤差，所以，在這種情況下就需要采用三維補(bǔ)償法來進(jìn)行有關(guān)計(jì)算。

從本質(zhì)上看，三維補(bǔ)償法的原理就是將探頭與被測(cè)曲面的法矢計(jì)算出來，而補(bǔ)償方法的選擇則應(yīng)根據(jù)被測(cè)曲面的實(shí)際情況來決定，現(xiàn)階段實(shí)際工作中常用的計(jì)算方法有以下幾種：微平面法、迭代修正法、規(guī)則網(wǎng)格均值計(jì)算法、B樣條曲面補(bǔ)償法、參數(shù)曲面法、三角網(wǎng)格法。

1.3 三維半徑補(bǔ)償方法的比較

微平面法能夠模擬出某一點(diǎn)的法向量，但是該方法對(duì)于α的距離要求較高，因此不僅效率低下，且難以實(shí)現(xiàn)。規(guī)則網(wǎng)絡(luò)均值計(jì)算法是一種效率較高的補(bǔ)償算法，但是它對(duì)測(cè)量點(diǎn)的排列要求比較嚴(yán)格。迭代修正法和參數(shù)曲面法的計(jì)算原理非常復(fù)雜，并且效率較低。從理論上來看，B樣條曲面補(bǔ)償法是最為精確的計(jì)算方法，但是使用該方法的前提條件是要重新構(gòu)建曲面，由此而導(dǎo)致的大量偏微分計(jì)算非常耗時(shí)。三角網(wǎng)絡(luò)法是一種高校、簡(jiǎn)便的半徑補(bǔ)償方法，但是在三角網(wǎng)格化過程的計(jì)算方面則有待進(jìn)一步的完善。相對(duì)于其他方法來說，Delaunay三角剖分在技術(shù)和方法上都顯得更加成熟，其特點(diǎn)就是在剖分過程中引入了優(yōu)化原則，賦予了三角剖分更強(qiáng)的適應(yīng)性，不僅降低了操作難度，還讓測(cè)量結(jié)果變得更加準(zhǔn)確。同時(shí)，該方法能夠適用于任意多邊形輪廓，應(yīng)用范圍極廣。

2 Delaunay三角剖分

三角剖分在實(shí)際中運(yùn)用的最多也是Delaunay三角剖分，它是一種特殊的三角剖分。1934年,俄國數(shù)學(xué)家Delaunay提出三角形最小內(nèi)角最大的三角化準(zhǔn)則,并證明在四點(diǎn)或四點(diǎn)以上共圓條件下的平面散亂點(diǎn)存在的三角化方式。

2.1 Delaunay三角剖分的定義

三角剖分是：假設(shè)V是二維實(shí)數(shù)域上的有限點(diǎn)集，邊e是由點(diǎn)集中的點(diǎn)作為端點(diǎn)構(gòu)成的封閉線段,E為e的集合。那么該點(diǎn)集V的一個(gè)三角剖分除了端點(diǎn)，平面圖中的邊不包含點(diǎn)集中的任何點(diǎn)，且沒有相交邊；平面圖中所有的面都是三角面，且所有三角面的合集是散點(diǎn)集V的凸包。

三角剖分中如果點(diǎn)集V的一個(gè)三角剖分T只包含一條邊e，其兩個(gè)端點(diǎn)為a,b，存在一個(gè)圓經(jīng)過a,b兩點(diǎn)，圓內(nèi)不含點(diǎn)集V中任何其他的點(diǎn)，稱之為Delaunay三角剖分。

2.2 Delaunay三角剖分的特性

1）空?qǐng)A特性：Delaunay三角網(wǎng)是唯一的，任意四點(diǎn)不能共圓。在Delaunay三角形網(wǎng)中任一三角形的外接圓范圍內(nèi)不會(huì)有其它點(diǎn)存在。如圖1所示：

圖1 Delaunay三角剖分的空?qǐng)A特性示意圖

2）最大化最小角特性：在散點(diǎn)集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。從這個(gè)意義上講，Delaunay 三角網(wǎng)是“最接近于規(guī)則化的“的三角網(wǎng)。具體的說是指在兩個(gè)相鄰的三角形構(gòu)成凸四邊形的對(duì)角線，在相互交換后，六個(gè)內(nèi)角的最小角不再增大。如圖2所示：

圖2 Delaunay三角剖分最大化最小角特性示意圖

此外Delaunay三角剖分剖分還具有，最接近、唯一性、最優(yōu)性、區(qū)域性等顯著的點(diǎn)。

3 對(duì)基于Delaunay三角剖分的測(cè)頭半徑補(bǔ)償法的分析和探討

Delaunay三角剖分能夠通過CMM對(duì)已經(jīng)獲得的有序數(shù)據(jù)的點(diǎn)列進(jìn)行測(cè)量，使多邊形輪廓的構(gòu)造變得更加簡(jiǎn)單易行，在實(shí)際工作中也更容易實(shí)現(xiàn)。下面就以某次測(cè)量作為實(shí)例，對(duì)該方法的計(jì)算過程進(jìn)行簡(jiǎn)要介紹：

3.1 在單一多邊形中的應(yīng)用

第一步就是要建立數(shù)據(jù)鏈表。該方法對(duì)于數(shù)據(jù)的測(cè)量是有一定規(guī)律的，所得到的每一行數(shù)據(jù)都有其規(guī)律可循。我們首先取相鄰的兩行數(shù)據(jù)構(gòu)建鏈表AB和鏈表CD。對(duì)距離‖AC‖和‖AD‖進(jìn)行計(jì)算，如果‖AC‖＜‖AD‖，那么就將A、C連接在一起，否則的話就連接A、D。根據(jù)圖3可建立鏈表ABDC和ACDB。

圖3 數(shù)據(jù)鏈表建立示意圖

需要注意的是，在剛開始進(jìn)行鏈表的建立時(shí)（即選取第一、二行時(shí)）必須要首先明確鏈表的旋轉(zhuǎn)方向，以便使生成的法矢量與補(bǔ)償方向相同。我們假設(shè)數(shù)據(jù)屬于內(nèi)向補(bǔ)償，那么整個(gè)鏈表就是按照順時(shí)針的方向進(jìn)行旋轉(zhuǎn)，因此，我們?nèi)〉氖擎湵鞟BCD。去掉鏈表中的i+2行數(shù)據(jù)，我們就可以建立鏈表EF，然后對(duì)i+1行數(shù)據(jù)進(jìn)行反向重構(gòu)，從而建立鏈表CD，確保了補(bǔ)償方向的一致性。

然后對(duì)新鏈表中D與EF的距離進(jìn)行計(jì)算，將距離最小的端點(diǎn)連接到一起，形成鏈表CDFE。對(duì)有關(guān)數(shù)據(jù)進(jìn)行循環(huán)取行，最終形成一個(gè)完整的鏈表結(jié)構(gòu)。

隨后，我們就要開始利用基于Delaunay三角剖分的測(cè)頭半徑補(bǔ)償法。首先去鏈表結(jié)構(gòu)中的第i個(gè)鏈表環(huán)，如果沒有符合要求的鏈表環(huán)，則終止該程序。然后，對(duì)任意一邊V1、V2，遍歷全部的節(jié)點(diǎn)Vj。由于符合要求的三角形可能存在很多歌，因此本次研究主要根據(jù)以下四條原則對(duì)其進(jìn)行判斷：1）三角形共存原則，即節(jié)點(diǎn)Vj與V1、V2不共線。2）三角形獨(dú)立原則，即線段V1V2、V1Vj與任何一個(gè)多邊形的輪廓都不相交。3）可見原則，就是指有向線段V1V2與節(jié)點(diǎn)Vj所構(gòu)成的三角形，必須與鏈表自身的旋轉(zhuǎn)方向一致。4）最大內(nèi)角最小原則，即在全部符合要求的節(jié)點(diǎn)中，應(yīng)選擇能使∠V1VjV2的值最大的節(jié)點(diǎn)。上述原則的應(yīng)用能夠有效保證三角形的勻稱度。

在將節(jié)點(diǎn)Vj確定下來后，根據(jù)其與線段V1V2 的關(guān)系形成新的三角形與多邊形輪廓。在這一過程中，主要應(yīng)注意以下問題：1）如果節(jié)點(diǎn)Vj與V1和V2均不相鄰，那么就將節(jié)點(diǎn)V2用Vj代替，并在鏈表中插入有向線段VjV2；2）如果Vj是有向線段V1V2的后一節(jié)點(diǎn)，那么就要用Vj替代V2，并將有向線段V2Vj刪除；3）如果Vj是有向線段V1V2的前一節(jié)點(diǎn)，那么就要用Vj替代V1，并將有向線段V1Vj刪除；4）如果Vj與V1、V2都相連，那么應(yīng)在鏈表中同時(shí)刪除這三條邊。前面所述四種情況詳如圖4所示。

圖4 三角剖分的鏈表處理

之后，把所生成的三角形放入相應(yīng)的鏈表中，如果鏈表非空，則重新進(jìn)行遍歷；如果為空，則輸出全部的三角形，并將i加1后去鏈表結(jié)構(gòu)中的第i個(gè)鏈表環(huán)。執(zhí)行結(jié)果詳見如圖5所示。

圖5 Delaunay三角剖分結(jié)果。

3.2 對(duì)于任意點(diǎn)補(bǔ)償矢量的計(jì)算

鏈表和三角形的旋轉(zhuǎn)方向以及法向矢量都是相同的，如果以補(bǔ)償矢量相反的視角去看圖3中的P點(diǎn)，就是圖6的樣子，具體算法如下。對(duì)于補(bǔ)償矢量的計(jì)算從本質(zhì)上看是一個(gè)加權(quán)平均的過程，本文采用下面的計(jì)算公式：

圖6 補(bǔ)償矢量計(jì)算圖

公式中的n所代表的是有多少個(gè)三角形圍繞點(diǎn)P。

3.3 對(duì)于邊界點(diǎn)補(bǔ)償矢量的計(jì)算

對(duì)于邊界點(diǎn)來說，由于圍繞點(diǎn)p的三角形并不完整，因此繼續(xù)采用公式（1）的話勢(shì)必會(huì)帶來誤差過大的問題，針對(duì)此種情況，可以采用增加點(diǎn)數(shù)的方式來完成邊界點(diǎn)補(bǔ)償矢量的計(jì)算。由三角形分析結(jié)果可知，將會(huì)出現(xiàn)3中P1和P2兩種情況，具體情況如圖7所示。

圖7 邊界點(diǎn)補(bǔ)償矢量計(jì)算圖示

符號(hào)的標(biāo)注方法應(yīng)該按照下面的方式進(jìn)行：P點(diǎn)的前后分別為點(diǎn)O和點(diǎn)Q，根據(jù)PQ、OP所構(gòu)成三角形對(duì)應(yīng)的點(diǎn)S、R增設(shè)點(diǎn)S′、R′，這樣一來，就可以形成3個(gè)三角形。不過，要注意確保所形成的3個(gè)三角形的旋轉(zhuǎn)方向與剖分后的三角形旋轉(zhuǎn)方向的一致性。

根據(jù)上述內(nèi)容，點(diǎn)S′、R′就要滿足下列條件：

在上面的公式中，θab所表示的是ab邊所對(duì)應(yīng)的兩個(gè)三角形的平面法矢所形成的夾角， 則代表著ab邊的總長(zhǎng)，在求出R′、S′之后，就可以通過（1）來對(duì)點(diǎn)P處的補(bǔ)償法矢進(jìn)行計(jì)算了。

3.4 半徑補(bǔ)償?shù)膶?shí)現(xiàn)

在計(jì)算出補(bǔ)償矢量np之后，就可以對(duì)有關(guān)數(shù)據(jù)點(diǎn)進(jìn)行求值。設(shè)測(cè)頭的半徑為r，那么半徑補(bǔ)償公式就可以寫成下面的形式：

4 實(shí)例分析

按照前面所講述的內(nèi)容，我們首先對(duì)需要測(cè)量的曲面中的有序點(diǎn)進(jìn)行Delaunay三角剖分,結(jié)果如圖8所示（實(shí)線部分）。然后，利用公式（3）對(duì)經(jīng)過半徑補(bǔ)償?shù)狞c(diǎn)的Delaunay三角剖分和點(diǎn)云進(jìn)行計(jì)算（虛線部分），通過對(duì)比我們可以發(fā)現(xiàn)，在補(bǔ)償前后，點(diǎn)云所構(gòu)成的兩個(gè)曲面實(shí)際上就是兩個(gè)等距面，其距離就是我們所要求的三坐標(biāo)測(cè)量機(jī)球形測(cè)頭的半徑。

圖8 半徑補(bǔ)償結(jié)果

5 結(jié)束語

本文通過對(duì)基于Delaunay三角剖分的半徑補(bǔ)償法的研究，對(duì)這一方法在半徑補(bǔ)償中的良好效果進(jìn)行了分析和說明，證明該方法能夠有效改善三角網(wǎng)格的質(zhì)量，提高了邊界點(diǎn)法向矢量的估算精度以及邊界點(diǎn)半徑補(bǔ)償?shù)臏?zhǔn)確性，具有非常好的應(yīng)用前景。

[1] 李海生. Delaunay三角剖分理論及可視化應(yīng)用研究[M].哈爾濱： 哈爾濱工業(yè)大學(xué)出版社,2010.

[2] 楊欽. 限定Delaunay 三角網(wǎng)格剖分技術(shù)[M]. 北京： 電子工業(yè)出版社,2005.

[3] 孫科,田懷文. 三坐標(biāo)測(cè)量機(jī)測(cè)頭半徑補(bǔ)償實(shí)用算法[J].機(jī)械,2009,36(2)： 6-8.

[4] 王紅敏,石沛林. 三坐標(biāo)測(cè)量機(jī)測(cè)頭的測(cè)球半徑補(bǔ)償誤差的計(jì)算[J]. 工具技術(shù),2003,37 (7)： 63-65.