基于Delaunay三角剖分的測頭半徑補償算法

趙小軍

ZHAO Xiao-jun

（九江學院 數控技術與應用實驗室，九江 332005）

0 引言

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

1 常用的半徑補償算法

1.1 二維補償法

二維補償法的操作方法比較簡單，使用范圍需也相對較廣，該方法在測量時會把測量點與測頭半徑之間的關系轉化為二維情況，現階段比較常用的二維測量法有三點共圓法和測量方向補償法。

1.2 三維補償法

在對一些形狀規則的表面（如二次曲面、平面等）進行測量時，二維補償是比較精確的，而在對一些形狀較為復雜的曲面（如增加器葉輪葉面）進行測量時，測點位置的曲面法向適量則往往與上述補償方向分別位于不同的平面內，如果繼續使用二維補償勢必會出現誤差，所以，在這種情況下就需要采用三維補償法來進行有關計算。

從本質上看，三維補償法的原理就是將探頭與被測曲面的法矢計算出來，而補償方法的選擇則應根據被測曲面的實際情況來決定，現階段實際工作中常用的計算方法有以下幾種：微平面法、迭代修正法、規則網格均值計算法、B樣條曲面補償法、參數曲面法、三角網格法。

1.3 三維半徑補償方法的比較

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

2 Delaunay三角剖分

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

2.1 Delaunay三角剖分的定義

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

三角剖分中如果點集V的一個三角剖分T只包含一條邊e，其兩個端點為a,b，存在一個圓經過a,b兩點，圓內不含點集V中任何其他的點，稱之為Delaunay三角剖分。

2.2 Delaunay三角剖分的特性

1）空圓特性：Delaunay三角網是唯一的，任意四點不能共圓。在Delaunay三角形網中任一三角形的外接圓范圍內不會有其它點存在。如圖1所示：

圖1 Delaunay三角剖分的空圓特性示意圖

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

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

此外Delaunay三角剖分剖分還具有，最接近、唯一性、最優性、區域性等顯著的點。

3 對基于Delaunay三角剖分的測頭半徑補償法的分析和探討

Delaunay三角剖分能夠通過CMM對已經獲得的有序數據的點列進行測量，使多邊形輪廓的構造變得更加簡單易行，在實際工作中也更容易實現。下面就以某次測量作為實例，對該方法的計算過程進行簡要介紹：

3.1 在單一多邊形中的應用

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

圖3 數據鏈表建立示意圖

需要注意的是，在剛開始進行鏈表的建立時（即選取第一、二行時）必須要首先明確鏈表的旋轉方向，以便使生成的法矢量與補償方向相同。我們假設數據屬于內向補償，那么整個鏈表就是按照順時針的方向進行旋轉，因此，我們取的是鏈表ABCD。去掉鏈表中的i+2行數據，我們就可以建立鏈表EF，然后對i+1行數據進行反向重構，從而建立鏈表CD，確保了補償方向的一致性。

然后對新鏈表中D與EF的距離進行計算，將距離最小的端點連接到一起，形成鏈表CDFE。對有關數據進行循環取行，最終形成一個完整的鏈表結構。

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

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

圖4 三角剖分的鏈表處理

之后，把所生成的三角形放入相應的鏈表中，如果鏈表非空，則重新進行遍歷；如果為空，則輸出全部的三角形，并將i加1后去鏈表結構中的第i個鏈表環。執行結果詳見如圖5所示。

圖5 Delaunay三角剖分結果。

3.2 對于任意點補償矢量的計算

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

圖6 補償矢量計算圖

公式中的n所代表的是有多少個三角形圍繞點P。

3.3 對于邊界點補償矢量的計算

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

圖7 邊界點補償矢量計算圖示

符號的標注方法應該按照下面的方式進行：P點的前后分別為點O和點Q，根據PQ、OP所構成三角形對應的點S、R增設點S′、R′，這樣一來，就可以形成3個三角形。不過，要注意確保所形成的3個三角形的旋轉方向與剖分后的三角形旋轉方向的一致性。

根據上述內容，點S′、R′就要滿足下列條件：

在上面的公式中，θab所表示的是ab邊所對應的兩個三角形的平面法矢所形成的夾角， 則代表著ab邊的總長，在求出R′、S′之后，就可以通過（1）來對點P處的補償法矢進行計算了。

3.4 半徑補償的實現

在計算出補償矢量np之后，就可以對有關數據點進行求值。設測頭的半徑為r，那么半徑補償公式就可以寫成下面的形式：

4 實例分析

按照前面所講述的內容，我們首先對需要測量的曲面中的有序點進行Delaunay三角剖分,結果如圖8所示（實線部分）。然后，利用公式（3）對經過半徑補償的點的Delaunay三角剖分和點云進行計算（虛線部分），通過對比我們可以發現，在補償前后，點云所構成的兩個曲面實際上就是兩個等距面，其距離就是我們所要求的三坐標測量機球形測頭的半徑。

圖8 半徑補償結果

5 結束語

本文通過對基于Delaunay三角剖分的半徑補償法的研究，對這一方法在半徑補償中的良好效果進行了分析和說明，證明該方法能夠有效改善三角網格的質量，提高了邊界點法向矢量的估算精度以及邊界點半徑補償的準確性，具有非常好的應用前景。

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

[2] 楊欽. 限定Delaunay 三角網格剖分技術[M]. 北京： 電子工業出版社,2005.

[3] 孫科,田懷文. 三坐標測量機測頭半徑補償實用算法[J].機械,2009,36(2)： 6-8.

[4] 王紅敏,石沛林. 三坐標測量機測頭的測球半徑補償誤差的計算[J]. 工具技術,2003,37 (7)： 63-65.