設計曲面上測量數據點最近點的計算研究

佘抒萌

摘 要： 在曲面匹配過程中，需要大量計算測量點到設計曲面的最近點及其距離，這一過程需要大量時間。而求解測量點到設計曲面距離的快速算法是解決曲面匹配問題的關鍵所在。如果采用測量數據點沿曲面法向投影到設計曲面，通過求解與曲面的交點得到最近點解，由于需要計算曲面上各位置處的法向，這樣計算量較大。為簡化算法，本文提出了一種近似的設計曲面上測量數據點最近點的計算方法。

關鍵詞： 曲面匹配 測量點 設計曲面 距離 快速算法

引言

以汽車覆蓋件模具型面為例，由于汽車覆蓋件模具型面設計大多采用自由曲面，但對于某一汽車覆蓋件模具曲面，其曲面形狀往往不是由單一的曲面組成的，而是由多個曲面（其中含規則曲面和不規則曲面）經過拉伸、裁減等處理拼合而成的。因此本文將設計曲面離散成小三角面片接近曲面形狀。計算測量點到設計曲面的最近點時，對于復雜曲面來說，通常所用的方法是Newton法和快速迭代算法[1]，[2]，但是這些迭代算法的成功在很大程度上取決于給定的初始點，初值選取不當，會導致計算發散，同時由于其計算耗時，不是理想的計算方法。

1.快速算法理論

為簡化計算，本文采用一種近似的方法：首先將設計曲面離散成較高密度的三角網格面片，將毛坯曲面測量數據點沿設計曲面三角面片所在法向投影到三角面片上尋求測量點到曲面的近似最近點，以測量數據點到設計曲面微小三角片的距離，（該測量數據點的投影點必須在小三角面片內或其邊界上）代替該點到設計曲面的距離以實現匹配點對的搜尋。如圖1所示為曲面測量數據點沿設計曲面離散三角網格面片法向投影的示意圖。

要縮短計算測量點到設計曲面三角面片的最近距離的時間，關鍵在于如何搜索測量點在設計曲面上投影點的最鄰近三角面片，以及減少該測量點在設計曲面上投影點的最鄰近三角面片的候選數量。因為一旦確定了測量點在設計曲面上投影點的最鄰近三角面網格頂點，則距離的計算就變成了一個相對簡單的問題。目前，對這類問題的求解主要有兩類算法：第一類是基于Gilbert算法[3]的多面體分解算法，Gilbert算法給出了計算復雜度為O（n）的求點到任意凸體最近距離的方法，因此這類算法的共同點就是首先通過各種方法將任意非凸面多面體分解為一系列凸體，然后再利用Gilbert算法求解。但這種方法不能保證正確處理任意復雜的情況，其應用受到一定的限制；另一類是利用八叉樹剖分技術[4]搜索最近三角面片，該方法在利用八叉樹剖分物體模型后，在測量點周圍的臨近三角面片數目可能會很多，需要計算從測量點到每一個臨近三角面片的距離，這樣將使效率有所下降，因此要與其他方法相結合，減少測量點的臨近三角面片數目。

2.曲面上測量數據點最近點計算步驟

本文在計算測量點到曲面投影點的最近點的距離采用了三個步驟：首先搜索測量點到設計曲面投影點鄰近的三角網格頂點；然后是計算測量點到設計曲面三角形網格頂點的距離或三角形所在平面的距離并判斷測量點在三角形所在平面的投影點是否在三角形內；最后比較二者的距離值，距離較小者即為所求。

步驟一：距離待匹配測量點鄰近的（設計曲面上）候選匹配點集的確定。

如果求設計曲面上所有離散數據點與測量點的距離，然后確定設計曲面上離測量點的最近點，這樣會導致計算量太大。為此，以測量點為圓心，以定長R為半徑作一個球，在球面內包含的點求與測量點的最近網格點。定長R可以根據實際情況確定，一般可以取離散三角形的最大邊長，如不合適，可以取離散三角形邊長的兩倍及數倍等。

步驟二：計算測量點到三角形所在平面的距離。

步驟三：對同一測量點，比較該測量點到最近網格頂點的距離與到三角面片的距離的大小，距離小者即為所求。

3.結語

曲面匹配是數字化加工與檢測的基礎，在自由曲面產品的加工制造和檢測中有著非常重要的應用（如定位安裝等）。本文研究了離散三角網格曲面的精確配準算法，計算中將“點一點”對齊法和“點一面”對齊法結合使用進行精匹配，對同一待匹配點，“點一點"對齊法和“點一面”對齊法求出的配對點中距離較小者即為所求。在搜尋待匹配測量點的最近點時提出了直接以待匹配測量點為中心的動態球搜索算法，可在設計曲面離散數據點中快速搜尋到距離測量點的最近點，使算法效率顯著提高。

參考文獻：

[1]Peng Q S.An algorithm for dingding the intersection lines between two B—spline surfaces.Computer-aided design，1984，16（4）：191-196.

[2]Bamhill R E，Farin G，Jordon Metal.Surface/surface intersection.Computer aided geometric design，1987，4（2）：277-289.

[3]Gilbert B G，Johnson D W，Keerthi S S.A Fast Procedure for Computing the Distance Between Complex Objects in Three—dimensional Space.IEEE Journal of Robotics and Automation，1988，4（2）：193-203.

[4]Zachmann G.Rapid collision detection by dynamically aligned DOP-trees.In：IEEE Proceedings Virtual Reality Annual International Symposium，Atlanta，Georgia，1998：90-97.