摘要：隨着計算機輔助設計(Computer Aided Design，CAD)技術和三維圖形硬件的不斷髮展，專業化CAD軟件在工業中得到了廣泛使用。三維工程模型已成爲工程分析和生產製造的基礎，是現代工程企業產品數據事實上的標準，爲工程信息的構建、分析和重用提供了新的手段，大大提高了設計和製造的效率。由於產品結構越來越複雜，產品類型不斷增加，需要設計的模型越來越多，造成工程三維模型爆炸式的增長。統計顯示，在產品設計中只有20%的零部件是需要全新設計的，40%可以從現有設計中直接得到，剩下的40%可以從現有設計中修改得到;75%的新設計都需要參考已有的設計和知識口]。
現今許多企業正在建立企業內部的三維工程模型數據庫，方便了產品開發人員及時有效地獲得所需的三維模型，加快了產品開發的步伐。在客戶需求多樣化的今天，有效檢索並重用已有的三維模型及相關設計知識已成爲實現產品快速研發、提高企業競爭力的重要手段。
傳統的檢索方式是將CAD模型中附帶的文件名、零部件數量或內容等信息作爲關鍵詞進行檢索，這種方法相對簡單易行，但已不能滿足日益增長的檢索需求 [z]。許多學者採用基於圖(graph)的方法對模型進行檢索[3q]，並將其應用於基於實例的產品設計中。他們將零件本身的結構特徵(如幾何、加工精度特徵等)、工藝特徵(如外圓、內孔、平面、槽等)及其相互間的關係提取出來用有向圖表示，進而通過子圖同構來檢索需要的模型。這種方法有效地利用了零件自身的信息，與領域知識關聯緊密。但前提是必須對模型進行特徵識別，才能準確提取出模型的特徵信息。由於不同商業CAD系統內部三維模型表示方法以及建模方式不同，阻礙了CAD系統問的產品數據交換和模型共享。目前的通用加工特徵識別算法不穩定，特徵識別只能針對某種CAD系統單獨進行二次開發，工作量大，且缺乏通用性和一般性。況且子圖同構算法是NP難問題，一旦零件複雜，對應的有向圖急劇膨脹，檢索效率將大大降低。
爲此，本文提出一種與CAD系統無關的基於網格特徵臨界點的三維工程模型檢索算法。該算法以三維模型的網格化表示作爲檢索輸入，通過對網格模型的分析，找出表徵網格形狀的關鍵點，即特徵臨界點，以這些點爲基礎計算三維模型的形狀度量，通過相似性比較，從模型數據庫中檢索出與輸入模型相似的模型。
1、原理與方法
1.1 Morse理論和網格特徵臨界點
1934年，美國數學家e提出用分析方法研究空間拓撲性質，即Morse理論[5]，成爲微分拓撲學的一個重要分支。空間是幾何研究的對象，而函數是分析研究的對象。因此，定義於空間上的函數與空間的形狀有着緊密的聯繫。Morse理論正是研究空間上的函數與空間關係的，它特別關注的是函數的臨界點，並從臨界點的信息中獲取空間形狀的信息，即研究流形上光滑函數的臨界點與流形本身拓撲結構之間的關係。本文以Morse理論作爲理論基礎，將網格模型映射爲Morse臨界點的集合。
設MCR“爲行維空間下的緊緻流形，函數，：
M—R爲作用在M上的一個光滑實值函數，在點P(越)∈M處建立局部座標系，“=(U。，?，U。)，則：①如果函數廠在點P的梯度爲零，即 3f/aU。一0，i∈[1，咒]，則P是函數，的臨界點。②如果P是函數，的臨界點，且，在P點處的Hessian矩陣日(，)(P;32，越)5(蠢女)非奇異，則P是Morse。$i界-A。
本文只考慮M是三角網格、函數廠是分段線性實值函數、且作用在網格M的頂點上的情況，三角面片內部的函數值可由頂點處的函數值插值得到。
假設對任意的邊<夕，Pz>∈M，均有廠(P，)≠廠(Pz)，可推知在任意三角面片內部，梯度都是恆定的非零實數，且I臨界點只出現在網格的頂點上[5]。
對於二維流形，Morse臨界點分爲極大值點、極小值點和鞍點三類。若P爲極小值點，則廠在P的/J,lI臺i域的各個方向均上升;若P爲鞍點，則P 爲廠在P的小臨域內上升下降轉換的過渡點;若P爲極大值點，則廠在P的小臨域的各個方向均下降。圖1表示了網格頂點P的分類情況，其中圓圈表示與P相連的頂點可i，0表示f(v。)>廠(p)，e表示廠(讓)<廠(夕)。
1.2網格特徵區域
Chang Ha Lee等人於2005年提出了網格特徵區域(mesh saliency)的概念[6]。網格特徵區域是對網格模型局部區域重要性的一種度量，即該網格模型局部區域能否體現網格形狀特點，其基本思想是函數，將模型表示爲採樣點處函數值的概率分佈。
計算網格頂點的平均曲率，並對其進行高斯加權平該方法易於理解，實現簡單，計算效率高，對網格退均(Gaussian-weighted average)，然後計算頂點的化的情況魯棒性好，但存在以下不足：
特徵因子，以此對頂點進行濾波，找出能體現網格模(1)由於該方法中採樣點的數量是一定的，不能型外形特點的區域。根據模型的形狀與複雜程度自適應地產生採樣點，本文結合網格特徵區域和Morse理論，找出網特別針對工程模型，一些很重要的局部幾何特徵(如格上表徵網格局部形狀的特徵臨界點，並以基於這槽、凸臺)很難被充分採樣，而對於平面特徵往往被些臨界點之間的距離和角度值的統計規律作爲形狀過採樣，因此採樣點不能很好地體現工程模型的形描述子，對網格進行形狀比較。狀特點。
1.3基於形狀分佈的圖形檢索算法
普林斯頓大學Robert Osada等人提出的基於形狀分佈的方法(D2)E73是圖形檢索領域中十分重要的算法，其基本思想是：首先對模型進行採樣，生成一系列的採樣點，然後通過作用在模型上的形狀(2)此算法採用單一形狀分佈函數，即任意兩採樣點間的歐氏距離，雖然計算簡單，但沒有充分利用模型的其他幾何信息，如三角面片和網格頂點處的法矢和曲率信息，所以單一的形狀分佈函數很難充分反映出模型的外形特點，檢索結果差強人意。圖2所示爲三個模型的比較結果，可以看出，雖然三個模型的外形差異很大，但通過此算法得到的形狀分佈曲線是相似的。可見該方法並不能很好地區分這三種模型，此算法有待改進和增強。
等人根據任意兩點的連線與模型的位置關係，將距離分爲In distances，Out distances和Mixed distances，改進了D2算法，並用於比較CAD模型[8]，改進方法較傳統的形狀分佈算法有效，但計算過程複雜，計算量過大，實時性有待加強，且不能避免傳統形狀分佈算法不足對檢索結果的影響。