產品stl模型快速求交方法
2023-06-29 02:25:16
專利名稱：產品stl模型快速求交方法
技術領域：
本發明提供一種產品STL模型快速求交方法，屬於產品逆向工程技術領域。
背景技術：
產品STLGtereo Lithography)模型因其對複雜外形產品具有造型快速靈活、拓撲適應性強等特點，廣泛應用於產品數位化模型重建、曲面細分造型、快速成型製造及數控加工仿真等領域。為精確表示模型外形，產品STL模型通常由海量數據組成，有效提高STL 模型求交效率對於逆向工程系統中的曲面裁剪、拼接及數控刀軌生成等問題的研究具有重要意義。對現有技術文獻檢索發現，郭開波等在其學術論文「STL模型布爾運算的實現」(華中科技大學學報，2006，34 (7) :96-99)中基於鄰接表建立三角網格曲面模型索引結構，採用三角面片包圍盒相交檢測算法求解三角網格曲面模型交線數據，並根據交線數據鄰接表實現交線段鄰接排序，由於鄰接表的建立及維護過程過於繁瑣，且需反覆線性遍歷鄰接表以查詢相交面片，嚴重影響了曲面求交效率。花衛華等在其學術論文「一種改進的不規則三角網格曲面切割算法」(地球科學-中國地質大學學報，2006,31(5) =619-623)中採用0BB(0riented Bounding Box)樹建立三角網格曲面模型索引結構，通過包圍盒求交獲取相交區域，求解模型間交點，通過對交點排序提取交線，可有效提高數據量較小網格曲面求交效率，但該算法所採用的索引結構為非平衡二叉樹，容易出現層數過多現象，嚴重影響網格曲面相交區域查詢效率，難以實現海量數據網格曲面模型快速求交。周海在其博士學位論文「細分曲面造型技術研究」中以八叉樹作為三角網格曲面索引結構，通過包圍盒相交查詢相交區域，由於包圍盒僅包含三角面片重心，不能包含整個三角面片，通過包圍盒求交檢索相交區域容易產生漏交。孫殿柱在其專利「產品STL模型布爾運算方法」(Publication No. CN 101510225,Application No. CN200910019897. 1)中基於R*_樹動態空間索引結構定位網格模型的相交區域，通過交線數據索引結構各層結點的空間鄰近關係實現交線數據鄰近排序，該算法需要對交線數據建立索引結構，影響了網格曲面模型求交效率。
發明內容
本發明針對現有技術存在的求交過程繁瑣，效率低，難以實現逆向工程中海量網格數據的快速求交等技術問題，提供一種適用於任意STL網格數據，數據適用性強，運行效率高的產品STL模型快速求交方法。本發明解決其技術問題所採用的技術方案是該產品STL模型快速求交方法，其特徵在於步驟依次為1)假設參與求交的兩個STL模型為S1和S2，分別基於Rt樹對S1和 &構建網格數據動態索引結構；2)採用深度優先遍歷算法，判斷31動態索引結構與&動態索引結構索引結點包圍盒的相交關係，獲取相交葉結點包圍盒，將其包含的三角面片添加到相交三角面片包圍盒集合Ut ；3)基於索引結點空間鄰近關係對Ut中索引結點包圍盒進行拓撲近鄰排序，獲取有序的索引結點包圍盒序列；4)將空間三角面片位置關係劃分為相交(一個三角面片的頂點在另一三角面片所在平面的兩側)、共面(兩三角面片共面)及相離 (一個三角面片三個頂點在另一個三角面片所在平面的同側)三種情況，獲取Ut中各包圍盒內三角面片交線段具體步驟為若兩三角面片相交，計算兩三角形所在平面的交線L，通過L與兩三角面片求交獲取L與兩三角面片之間的交線段，確定兩交線段端點對應於直線 L上的參數值t00, t01、t00和tn，若t01彡t10或tn彡t00無交線；對於相交情況可根據參數值分布情況求出交線段，令交線段的起點和終點對應直線L上的參數值分別為、和、，則 to和、可由下式求得，
權利要求
1.一種產品STL模型快速求交方法，其特徵在於，步驟依次為1)設參與求交的兩STL 模型為S1和&，分別基於Rt樹對S1和&構建網格數據動態索引結構，並對動態索引結構中的索引結點進行聚類分簇；2)採用深度優先遍歷算法，判斷S1的動態索引結構與&的動態索引結構索引結點包圍盒的相交關係，獲取相交葉結點包圍盒，將其包含的三角面片添加到相交三角面片包圍盒集合Ut中；3)基於索引結點空間鄰近關係對Ut中索引結點包圍盒進行拓撲近鄰排序，獲取有序的索引結點包圍盒序列；4)將三角面片位置關係劃分為相交、共面及相離三種情況，獲取仏中各包圍盒內三角面片的交線段，具體步驟為若兩三角面片相交，計算兩三角面片所在平面的交線L，通過交線L與兩三角面片求交獲取交線L與兩三角面片之間的交線段，確定兩交線段端點對應於直線L上的參數值t, t01, t10和tn， 令交線段的起點和終點對應直線L上的參數值分別為、和、，則、和、可由下式求得，, ,10，Ooo — ^io), ^oi 『 (^oi《,U)Z0 = SZ1 = Sl/oo，(^00 >義10) l/ll，Ooi >義11)交線段端點V1, V2的坐標即分別為C (t0)、C (ti)，當tQ1 < t10或tn彡t00時無交線；若兩三角面片共面，利用三角面片三條邊與另一三角面片求交獲取兩三角面片交線段，將各交點平均值作為交點；若兩三角面片相離，則表示兩三角形不相交，不進行求交運算；5)對步驟4)中得到的各交線段進行首尾連接得到STL模型交線。
2.根據權利要求1所述的產品STL模型快速求交方法，其特徵在於步驟1)中所述對 STL模型動態索引結構中的索引結點進行聚類分簇是指採用基於間隙統計算法獲取索引結點最佳聚類簇數，並採用k-均值算法對索引結點進行最佳聚類簇數下的聚類分簇。
3.根據權利要求1或2所述的產品STL模型快速求交方法，其特徵在於所述對STL模型動態索引結構中的索引結點進行聚類分簇的具體步驟為①初始化聚類簇數為k= 1，在索引結點範圍內選擇F組均勻分布的參考點集，採用k-均值算法對F組參考點集進行聚類分簇，將每一組參考點集都分為k簇；②計算其聚類相似度之和W(k)k-\ ηα-\ηα-\ γ \ γ α=0 ζ=0 ；=0 αTi, rj(i Φ j)分別為索引結點Ni, Nj包圍盒的外接球半徑，d為索引結點Ni, Nj包圍盒中心間距，採用公式d = ^jix1 -Xj)2 + {y-yjf + (zt -Zj)2計算，(Xi, Ii, Zi)、(Xj, Yj, Zj)分別為N」 Nj的包圍盒中心坐標，na為經k-均值分裂後第a簇的索引結點數；③採用公式伢lnfFre/㈨]= 『Σ:1η^τ，#)計算參考點集聚類相似Γ J度期望值，公式中下標ref表示數據為參考點集，Wref, j(k)表示第j組參考點集進行k-均值聚類的聚類相似度之和；④採用公式Wit =指Z;JlnWreij(/c)_E[lnWrei(/c)]}2計算參考點集標準差，並採用公式\計算由參考點集標準差導致的聚類結果誤差；⑤若步驟②中索引結點分簇結果滿足條件￡{111[^10]}-111[1(10] ^E{ln[ffref(k+l)}-ln[ff(k+l)-sk+1]，則索引結點最佳簇數為k，索引結點最佳聚類簇數獲取過程結束，否則令k = k+1，返回步驟②。
4.根據權利要求3所述的產品STL模型快速求交方法，其特徵在於步驟①中所述F組均勻分布的參考點集中F的取值與索引結點數量成正比。
5.根據權利要求3或4所述的產品STL模型快速求交方法，其特徵在於所述F組均勻分布的參考點集中F的取值為3 8。
6.根據權利要求3所述的產品STL模型快速求交方法，其特徵在於步驟①中所述每一組參考點集的獲取步驟為將索引結點統一表示為四維點對象(X，1，Z, r)，組成nXp的矩陣A，A中每一行對應一個索引結點的四維點坐標，其中η為索引結點數，ρ為索引結點維度；對矩陣A進行奇異值分解:A = UDVt ；定義矩陣B = AV,在矩陣B列值範圍內產生均勻分布的矩陣C ；定義矩陣Z = CVt，矩陣Z即為參考點集。
7.根據權利要求1所述的產品STL模型快速求交方法，其特徵在於步驟幻所述獲取有序的索引結點包圍盒序列的具體步驟為①任取序列Ut中一元素M作為初始點，將M添加到輔助序列\中，並將M從序列Ut中刪除，構造向量P1並初始化P1 = 0 ；②採用擴展空心球算法遍歷S1的動態索引結構，獲取MWk-近鄰索引結點，若存在索引結點屬於Ut，則執行③，否則執行⑥；③取距離M最近且屬於Ut的索引結點N，設M的包圍盒中心點為0Μ， N的包圍盒中心點為0Ν，令向量P1 = OmOn，將索引結點N添加到輔助序列Vi中並將NW Ut 中刪除；④遍歷M的k-近鄰索引結點，若存在索引結點Ntl屬於序列Ut且中心點Onci滿足 P1 · OmOno ( 0，則執行⑤，否則令N為M，返回②；⑤將N0從Ut中刪除並添加到輔助序列Vi 中M索引結點的前面，分別令N和Ntl為M，返回②；⑥若Ut為空，則輔助序列Vi中元素即為有序的包圍盒序列，索引結點包圍盒拓撲近鄰排序過程結束，否則令i = i+Ι，返回①繼續執行。
8.根據權利要求7所述的產品STL模型快速求交方法，其特徵在於所述輔助序列Vi 中，i的初始值為0，最大取值不超過索引結點數。
全文摘要
本發明提供一種產品STL模型快速求交方法，屬於產品逆向工程技術領域。其特徵在於基於R*-樹構建STL模型動態索引結構，通過索引結點包圍盒相交檢測快速縮小求交範圍，準確定位相交三角面片包圍盒集合併對該集合進行拓撲近鄰排序，依次連接各包圍盒內三角網格曲面模型交線段，實現曲面模型交線快速提取，實例證明該方法可有效提高數據密集、形狀複雜的STL曲面模型求交效率，對逆向工程中三角網格曲面模型的裁剪、拼接及數控加工刀軌生成具有重要意義。
文檔編號G06F17/50GK102508973SQ201110355099
公開日2012年6月20日 申請日期2011年11月10日 優先權日2011年11月10日
發明者孫殿柱, 孫永偉, 宋洋, 李延瑞 申請人:山東理工大學