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

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

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