三角網(wǎng)格模型的動態(tài)空間索引結(jié)構(gòu)

三角網(wǎng)格模型的動態(tài)空間索引結(jié)構(gòu)

三角網(wǎng)格模型可以快速準確地重建基于產(chǎn)品形狀采樣數(shù)據(jù)的云平面模型?，F(xiàn)在，它被廣泛應(yīng)用于產(chǎn)品的逆向工程中。利用反向工程系統(tǒng)生成的三角網(wǎng)格模型進行統(tǒng)計，可以切割和連接網(wǎng)格曲線的模型，并構(gòu)建復雜的網(wǎng)格模型。文獻提出一種可靠的多面體布爾運算算法,采用多面體一致關(guān)系的判斷和推理方法,根據(jù)頂點坐標判斷多面體位置關(guān)系,實現(xiàn)網(wǎng)格模型的布爾運算.該算法雖然保證了形狀規(guī)則、數(shù)據(jù)量少的網(wǎng)格模型布爾運算的可靠性,但對形狀復雜、數(shù)據(jù)量大的網(wǎng)格模型其幾何推理過程將耗費大量時間.文獻采用鄰接表作為網(wǎng)格模型數(shù)據(jù)結(jié)構(gòu),建立曲面模型中三角面片的包圍盒,遍歷包圍盒獲取相交的三角面片并計算其交線段,將所有交線段排序獲取2個模型交線,根據(jù)交線剖分網(wǎng)格模型,實現(xiàn)網(wǎng)格模型的布爾運算.但該算法三角面片鄰接表的建立及維護過程煩瑣,需重復遍歷鄰接表計算交線段,算法運行效率低.文獻采用非正則精確模型作為幾何對象數(shù)據(jù)結(jié)構(gòu),基于該模型進行數(shù)據(jù)對象的層次求交,實現(xiàn)網(wǎng)格模型的布爾運算.該算法雖然避免了由于計算誤差引起的裂紋以及拓撲生成的不一致,但非正則精確模型結(jié)構(gòu)復雜,獲取網(wǎng)格模型交線過程煩瑣,求交速度慢.本文針對以上算法存在的不足,建立了三角網(wǎng)格模型的動態(tài)空間索引結(jié)構(gòu),并基于該結(jié)構(gòu)快速獲取2個三角網(wǎng)格模型的相交區(qū)域;求解相交區(qū)域內(nèi)網(wǎng)格模型的離散交線段,并對其進行排序獲取交線;根據(jù)交線細分相交三角面片,將三角網(wǎng)格模型沿交線分割成2個子網(wǎng)格模型,通過合并不同子網(wǎng)格模型實現(xiàn)三角網(wǎng)格模型的布爾運算.實例結(jié)果證明,本文算法可準確地定位三角網(wǎng)格模型中相交的三角面片,能夠快速、準確地求解2個三角網(wǎng)格模型交線,可實現(xiàn)數(shù)據(jù)密集、形狀復雜三角網(wǎng)格模型的布爾運算,有效地提高了網(wǎng)格模型的布爾運算效率.1基于r#-東北部的動態(tài)空間索引為了精確地表示復雜拓撲曲面,三角網(wǎng)格模型通常由大規(guī)模密集三角面片組成,為其建立合理的數(shù)據(jù)結(jié)構(gòu)是高效實現(xiàn)網(wǎng)格模型中三角面片查找、求交、分割,以及合并等運算的先決條件.本文采用R*-tree動態(tài)空間索引結(jié)構(gòu)并對其進行改進,建立三角網(wǎng)格模型的動態(tài)空間索引結(jié)構(gòu),有效地解決了三角網(wǎng)格模型數(shù)據(jù)結(jié)構(gòu)的創(chuàng)建及動態(tài)維護等問題.1.1基于r#-to-b的結(jié)論聚類分簇算法R*-tree結(jié)點插入算法采用結(jié)點(minimumboundingrectangle,MBR)增量作為結(jié)點聚類分簇的判定條件.該算法應(yīng)用于三角面片集合的空間聚類分簇時,若三角面片平行于坐標平面,結(jié)點MBR將由三維退化為二維,導致R*-tree結(jié)點插入失效,破壞了R*-tree結(jié)點的聚合性.為解決該問題,本文將三角面片及索引結(jié)點MBR統(tǒng)一表示為四維點對象(x,y,z,r),其中x,y,z為MBR中心坐標,r為MBR外接球半徑值.1.2基于r#-toh-n-n-r#-zi,ri分簇中心本文采用k-means算法實現(xiàn)三角面片集合的空間聚類分簇.在選取初始分簇中心時,為減少k-means迭代次數(shù),將結(jié)點中心距離最遠的一對結(jié)點MBR中心作為初始分簇中心.確定初始分簇中心后,將數(shù)據(jù)對象添加到中心距其最近的分簇中.為使結(jié)點MBR均勻,避免出現(xiàn)結(jié)點MBR奇異,根據(jù)R*-tree定義,當分裂所得結(jié)點的子結(jié)點數(shù)k小于R*-tree最小子結(jié)點數(shù)m時,將另一簇中距離當前簇較近的m-k個結(jié)點插入到當前簇中,并調(diào)整分裂結(jié)果.采用k-means對R*-tree索引結(jié)點進行聚類分簇時,需要迭代定位最終的分簇中心.對于同簇結(jié)點中的N個索引結(jié)點,其四維標準化坐標為pi(xi,yi,zi,ri),i=1,…,N,分簇中心坐標(xˉ,yˉ,zˉ,rˉ)(xˉ,yˉ,zˉ,rˉ)由???????????????????????????????????????????????????????xˉ=∑i=1Nxi?ri∑i=1Nriyˉ=∑i=1Nyi?ri∑i=1Nrizˉ=∑i=1Nzi?ri∑i=1Nrirˉ=∑i=1NriN(1){xˉ=∑i=1Νxi?ri∑i=1Νriyˉ=∑i=1Νyi?ri∑i=1Νrizˉ=∑i=1Νzi?ri∑i=1Νrirˉ=∑i=1ΝriΝ(1)計算.各索引結(jié)點至聚類分簇中心的距離d=[(xi?xˉ)2+(yi?yˉ)2+(zi?zˉ)2+(ri?rˉ)2]12(2)d=[(xi-xˉ)2+(yi-yˉ)2+(zi-zˉ)2+(ri-rˉ)2]12(2)圖1所示為基于四維點表示的三角網(wǎng)格模型空間聚類分簇效果.2獲得三角形網(wǎng)格模型的交線數(shù)據(jù)2.1交通流量不對稱設(shè)參與布爾運算的2個三角網(wǎng)格模型為S1和S2,根據(jù)S1動態(tài)空間索引結(jié)構(gòu)判斷S2動態(tài)空間索引結(jié)構(gòu)中結(jié)點MBR與S1的相交關(guān)系,若不相交,則不對S1和S2進行布爾運算;否則,繼續(xù)比較S2子結(jié)點MBR與S1的相交關(guān)系,直至獲取與S1相交的數(shù)據(jù)結(jié)點,該數(shù)據(jù)結(jié)點中存儲的三角面片即為與目標三角網(wǎng)格模型相交的三角面片.圖2所示為2個三角網(wǎng)格模型獲取相交三角面片的過程.圖2b～2d中實體顯示部分分別為2個三角網(wǎng)格模型動態(tài)空間索引結(jié)構(gòu)相交的第一層結(jié)點、葉結(jié)點和數(shù)據(jù)結(jié)點MBR.2.22個三角形所在平面的交線獲取2個三角網(wǎng)格模型動態(tài)空間索引結(jié)構(gòu)相交數(shù)據(jù)結(jié)點中存儲的三角面片,將其求交獲取交線段.為提高三角面片交線求解速度,將空間三角面片位置關(guān)系劃分為以下3種情況.情況1.三角面片的3個頂點均在另一三角面片所在平面的同側(cè).情況2.2個三角面片共面.情況3.2個三角面片均與另一三角面片所在平面相交.若為情況1,表示2個三角形不相交,不進行求交運算;若為情況2,利用三角面片的3條邊與另一三角面片求交獲取2個三角面片交線段,將各交點平均值作為交點;若為情況3,計算2個三角形所在平面的交線l,通過l和2個三角面片求交獲取交線段,確定交線段的端點對應(yīng)于l上的參數(shù)值為t00,t01,t10和t11,其位置關(guān)系如圖3所示.若t01≤t10或t11≤t00,則表示2個三角面片沒有交線,如圖3a所示;若t01>t10或t11>t00,則表示2個三角面片相交,如圖3b所示.根據(jù)參數(shù)值分布求解2個三角面片交線段,令交線段的起點和終點對應(yīng)直線l上的參數(shù)值分別為t0和t1,即t0={t10,t00≤t10t00,t00>t10(3)t1={t01,t01≤t11t11,t01>t11(4)t0={t10,t00≤t10t00,t00>t10(3)t1={t01,t01≤t11t11,t01>t11(4)2.32到起始段某終點距離為0的數(shù)據(jù)基點相交三角面片求交所獲取的交線數(shù)據(jù)是一組雜亂無序的線段,需對其進行排序以形成完整的交線.本文采用改進后的R*-tree建立所獲取的離散交線數(shù)據(jù)動態(tài)空間索引結(jié)構(gòu),并基于該索引結(jié)構(gòu)各層結(jié)點的空間鄰近關(guān)系實現(xiàn)交線數(shù)據(jù)鄰近排序.步驟如下:Step1.以任一交線段為起始線段,查詢離散交線數(shù)據(jù)動態(tài)空間索引結(jié)構(gòu)中到起始線段某端點距離為0的數(shù)據(jù)結(jié)點.Step2.獲取該數(shù)據(jù)結(jié)點中存儲的交線段,連接該交線段與起始線段組成新的起始線段.Step3.查詢離散交線數(shù)據(jù)動態(tài)空間索引結(jié)構(gòu)中到新起始線段某端點距離為0的數(shù)據(jù)結(jié)點.若存在距離為0的數(shù)據(jù)結(jié)點,轉(zhuǎn)Step2;否則,執(zhí)行下一步.Step4.對當前交線數(shù)據(jù)排序完成后,輸出2個三角網(wǎng)格模型一條交線.由于2個復雜三角網(wǎng)格模型交線不止一條,需重復執(zhí)行上述步驟獲取多條交線,最終生成2個網(wǎng)格模型交線.圖4所示為2個三角網(wǎng)格模型交線的求解過程.步驟如下:Step1.線段E0為起始線段,查詢R*-tree索引結(jié)構(gòu)中到E0端點P0距離為0的數(shù)據(jù)結(jié)點MBR1,獲取MBR1中存儲交線段E1.Step2.連接E0與E1,并查詢R*-tree索引結(jié)構(gòu)中到E1端點P1距離為0的數(shù)據(jù)結(jié)點MBR2,獲取MBR2中存儲交線段E2.Step3.連接E1與E2,迭代查詢R*-tree索引結(jié)構(gòu)中數(shù)據(jù)結(jié)點,直至查詢到所有交線段,最終生成2個網(wǎng)格模型一條交線.3角網(wǎng)格模型的建立基于交線將相交三角面片進行三角網(wǎng)格劃分,可保證三角網(wǎng)格模型沿交線分成2個子網(wǎng)格模型,通過合并2個三角網(wǎng)格模型的指定子網(wǎng)格模型,實現(xiàn)兩者的布爾運算.3.1角網(wǎng)格劃分將交線段在三角面片內(nèi)部的端點作為細分點,對三角面片進行三角細分.由于相交三角面片的空間位置是任意的,進行三維三角網(wǎng)格劃分比較復雜.本文采用文獻算法將三維三角網(wǎng)格劃分問題轉(zhuǎn)化到二維,對所有相交三角面片進行約束Delaunay細分,約束邊界為交線段和三角面片的3條邊.圖5所示為相交三角面片的三角網(wǎng)格劃分.3.2角網(wǎng)格模型的分割將細分后的三角面片添加到三角網(wǎng)格模型動態(tài)空間索引結(jié)構(gòu)中,重新建立三角網(wǎng)格模型動態(tài)空間索引結(jié)構(gòu).以交線為公共邊界的三角面片位于交線的兩側(cè),遍歷三角網(wǎng)格模型動態(tài)空間索引結(jié)構(gòu),自適應(yīng)地擴張查找位于交線兩側(cè)的三角面片;以交線為分界線將網(wǎng)格模型分成2個子網(wǎng)格模型,實現(xiàn)三角網(wǎng)格模型的分割.三角網(wǎng)格模型分割步驟如下:Step1.以三角網(wǎng)格模型中位于交線上的任一三角面片為初始迭代面片.Step2.查找三角網(wǎng)格模型中包含初始迭代面片非交線邊的三角面片.Step3.判斷查找到的三角面片是否以交線為邊界,若存在交線邊界,則停止查找交線邊方向上的三角面片;若三角網(wǎng)格模型查找完畢,執(zhí)行下一步;否則,查找三角網(wǎng)格模型中包含其他邊界的三角面片,重復Step3.Step4.若2個網(wǎng)格模型只有一條交線,執(zhí)行下一步;若2個網(wǎng)格模型存在多條交線,提取下一條交線,轉(zhuǎn)Step1.Step5.將查找到的三角面片從三角網(wǎng)格模型中分割出來,實現(xiàn)沿交線將網(wǎng)格模型分成2個子網(wǎng)格模型.如圖6a所示,三角面片T1為初始迭代面片,由T1查找到三角面片T2和T3,由T2查找到三角面片T4和T5,由T3查找到三角面片T6,由T4查找到三角面片T7和T8;圖6b所示為網(wǎng)格模型的分割結(jié)果.3.3s1e-s13.3設(shè)2個三角網(wǎng)格模型為S1和S2,交線將S1分成2個子網(wǎng)格模型,分別為位于S2內(nèi)部的網(wǎng)格模型和位于S2外部的網(wǎng)格模型,交線同樣將S2分成2個子網(wǎng)格模型,則S1和S2布爾運算公式為S1∩S2=S1inS2+S2inS1?S1∪S2=S1outS2+S2outS1?S1?S2=S1outS2+S2inS1?S2?S1=S2outS1+S1inS2.S1∩S2=S1inS2+S2inS1?S1∪S2=S1outS2+S2outS1?S1-S2=S1outS2+S2inS1?S2-S1=S2outS1+S1inS2.其中,S1inS2和S1outS2分別表示S1位于S2內(nèi)部和外部的子網(wǎng)格模型,S2inS1和S2outS1分別表示S2位于S1內(nèi)部和外部的子網(wǎng)格模型.三角網(wǎng)格模型的交運算是將S1中的S1inS2與S2中的S2inS1合并組成一張曲面;并運算是將S1中的S1outS2與S2中的S2outS1合并組成一張曲面;差運算是將S1中的S1outS2與S2中的S2inS1合并組成一張曲面,或?qū)2中的S2outS1與S1中的S1inS2合并組成一張曲面.4實際模型測試采用本文算法和文獻算法對圖7a,7b所示的網(wǎng)格模型進行布爾運算,圖7c～7f所示分別為通過網(wǎng)格交線分割出的4個子網(wǎng)格模型,對所生成的子網(wǎng)格模型進行布爾交、并、差運算的結(jié)果如圖7g～7j所示.表1所示為采用本文算法和文獻算法對圖7a,7b模型進行布爾運算的算法時間比較,可以看出,本文算法交線求解效率比文獻算法提高1～6倍,布爾運算效率提高約11倍.圖8所示為采用本文算法和文獻算法對數(shù)據(jù)量依次遞增的多組網(wǎng)格模型的布爾運算效率進行對比分析,可以看出,隨著三角網(wǎng)格模型數(shù)據(jù)量的遞增,本文算法效率明顯優(yōu)于文