佘抒萌

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

關(guān)鍵詞： 曲面匹配 測(cè)量點(diǎn) 設(shè)計(jì)曲面 距離 快速算法

引言

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

1.快速算法理論

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

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

2.曲面上測(cè)量數(shù)據(jù)點(diǎn)最近點(diǎn)計(jì)算步驟

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

步驟一：距離待匹配測(cè)量點(diǎn)鄰近的（設(shè)計(jì)曲面上）候選匹配點(diǎn)集的確定。

如果求設(shè)計(jì)曲面上所有離散數(shù)據(jù)點(diǎn)與測(cè)量點(diǎn)的距離，然后確定設(shè)計(jì)曲面上離測(cè)量點(diǎn)的最近點(diǎn)，這樣會(huì)導(dǎo)致計(jì)算量太大。為此，以測(cè)量點(diǎn)為圓心，以定長(zhǎng)R為半徑作一個(gè)球，在球面內(nèi)包含的點(diǎn)求與測(cè)量點(diǎn)的最近網(wǎng)格點(diǎn)。定長(zhǎng)R可以根據(jù)實(shí)際情況確定，一般可以取離散三角形的最大邊長(zhǎng)，如不合適，可以取離散三角形邊長(zhǎng)的兩倍及數(shù)倍等。

步驟二：計(jì)算測(cè)量點(diǎn)到三角形所在平面的距離。

步驟三：對(duì)同一測(cè)量點(diǎn)，比較該測(cè)量點(diǎn)到最近網(wǎng)格頂點(diǎn)的距離與到三角面片的距離的大小，距離小者即為所求。

3.結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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，F(xiàn)arin 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.