[發明專利]產品逆向工程數據動態索引多目標自適應構建方法

無效

• 申請號: 201210332537.9
• 申請日: 2012-09-11
• 公開（公告）號: CN102831241A
• 公開（公告）日: 2012-12-19
• 發明（設計）人: 孫殿柱;史陽;劉華東;李延瑞
• 申請（專利權）人: 山東理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明提供一種產品逆向工程數據動態索引多目標自適應構建方法，屬于產品逆向工程技術領域。

背景技術

在產品逆向工程技術領域，所處理的原始數據通常是來自實物表面采樣而獲得的散亂點云、多邊形網格模型等數據格式，基于該類原始數據進行曲面重建生成分片連續曲面是產品逆向工程的核心技術。由于散亂點云、多邊形網格以及分片連續曲面這些數據格式均表現為大規模甚至海量空間幾何對象的復合結構，為這些數據類型構建一種通用且高效的索引技術，對于提高產品逆向工程數據處理效率具有重要意義。

對現有文獻檢索發現，現有產品逆向工程數據的索引技術通常僅適用于某種特定的數據類型。在散亂點云處理中，空間八叉樹與K-D樹分別是應用最為廣泛的靜態索引與動態索引。周海在其博士學位論文“細分曲面造型技術研究”（南京航空航天大學，2005）中采用空間八叉樹作為三角網格模型的空間索引結構，依據三角面片包圍盒中心的位置將三角面片插入到空間八叉樹中，建立三角網格模型索引結構，組織三角面片間的近鄰關系，該方法以三角面片包圍盒中心表示三角面片，不能準確反映三角面片所在位置及所占空間區域大小，準確性差，降低了索引結構的質量及基于該結構的空間查詢效率。王占禮在其博士學位論文“面向虛擬制造的數控加工仿真技術研究”（吉林大學，2007）中采用一個大包圍盒包圍三角網格模型，將該包圍盒作為根索引結點，然后將其中的三角面片分割成兩部分，每一部分用一個包圍盒包圍，再對每一個包圍盒遞推進行分割，直到一個包圍盒只包含一個三角面片，建立三角網格模型的非平衡二叉樹索引結構，該結構提高了三角網格模型的空間查詢效率，但由于該結構為非平衡二叉樹，故只適用于分布較為均勻的三角網格模型，當三角網格模型分布疏密不均時，容易出現樹的某一分支層數過多現象，導致數據結構急劇惡化，嚴重降低索引查詢效率。孫殿柱等人在其學術論文“基于四維聚類的R*-樹結點分裂算法”（機械工程學報，2009,45（10）：180-184）中對R*-樹進行了改進，使之可統一索引散亂點云、多邊形網格等數據類型，繼而在其學術論文“三角Bézier曲面快速求交算法”（機械工程學報，2011，47（3）：89-94）中將改進的R*-樹作為分片連續曲面的索引結構以提高相交三角Bézier曲面片查詢效率，但是由于改進的R-樹在索引結點分裂過程中采用了k-均值聚類算法，需要用戶交互設定聚類簇數，聚類簇數的不同會導致差別很大的索引結點分裂結果，導致索引結構與性能不穩定，此外k-均值聚類算法是一種局部搜索算法，對初始值過于敏感，采用爬山法迭代搜索最優的索引結點分裂結果，容易陷入局部極值，難以獲得全局最優的索引結點分裂結果，導致未能充分發揮R*-樹的優勢。

綜上所述，目前的產品逆向工程數據的動態索引結構已經具備了一定的通用性，可基于統一的索引機制處理各種類型的空間幾何對象的復合結構，但是依然存在數據適應性較差、索引性能較低并且系統資源消耗較高等問題，為產品逆向工程數據構建穩定、高效的索引機制已成為本領域技術人員亟待解決的技術問題。

發明內容

為克服現有產品逆向工程數據的索引機制的不足，本發明目的在于提供一種產品逆向工程數據動態索引多目標自適應構建方法，使之能索引各種類型的逆向工程數據，具有穩定性強、數據查詢效率高的特點，技術方案如下：

?一種產品逆向工程數據動態索引多目標自適應構建方法，其特征在于包含以下步驟：一、讀取產品逆向工程數據，建立各空間對象的軸向包圍盒，依據軸向包圍盒的中心以及外接球半徑建立其對應的數據結點，并存入數據結點序列；二、將數據結點插入到索引結構中，結點插入到索引結構的具體步驟是：1）為結點選擇插入位置；2）將結點插入到步驟1）中得到的位置；3）令結點插入到結點node下，判斷結點node的子結點數是否大于結點的最大子結點數，如果大于則對結點node進行溢出處理，若結點node為非根索引結點且在插入一個空間對象過程中該結點所在層第一次進行溢出處理，則在結點node中有選擇地取出一部分結點，將它們重新插入索引結構的該層中，否則進行結點分裂；4）調整各結點的軸向包圍盒；三、將體積過大的軸向包圍盒重新插入到索引結構中，實現索引結構的優化；四、基于產品逆向工程數據動態索引結構，實現散亂點云、多邊形網格以及分片連續曲面的拓撲近鄰查詢。