基于工程圖紙的三維形體重建技術(shù)

基于工程圖紙的三維形體重建技術(shù)

1多三維形體重建算法基于工程圖紙的三維重建技術(shù)是計(jì)算機(jī)設(shè)計(jì)和計(jì)算機(jī)繪圖的一個(gè)重要研究領(lǐng)域。國內(nèi)外研究人員先后提出了幾種重建算法。idesaw首先提供了三維重建方法的數(shù)學(xué)推理模型。該方法僅研究了非常有限的3d重建算法，但它提出的自函數(shù)法已成為許多3d重建算法的基礎(chǔ)。marrowsky和wesley提出了一種適合任何多面體的重建算法。該算法可以生成符合輸入三個(gè)場景的多個(gè)解決方案，以適應(yīng)3d圖像。gu部分解決了平面體和柱面體重建的問題，并將柱面體軸的自由度延長到與特定坐標(biāo)平面平行的平面上。yan提出了適合平面體重建的算法。該算法使用決策樹技術(shù)加速了三維邊緣的生成速度。陰影利用每個(gè)圖像中的二維信息和重建過程中產(chǎn)生的三維信息之間的關(guān)系，減少檢測和評估的數(shù)量，在一定程度上提高了算法的操作效率。以前的重建算法由于反復(fù)執(zhí)行投影匹配操作和復(fù)雜的幾何運(yùn)算,需要較長的處理時(shí)間.本文工作的主要目的是減少重建過程的處理時(shí)間.在重建過程中,我們利用幾何基元之間的幾何性質(zhì)和拓?fù)潢P(guān)系,減少了投影匹配的次數(shù),避免了復(fù)雜的幾何運(yùn)算.在決策求解過程中,我們根據(jù)Moebius規(guī)則和工程圖的性質(zhì),省去了候選塊生成這一步驟,簡化了傳統(tǒng)的決策求解.2概念和結(jié)論1.定義12.定義2定義3(1)環(huán)L內(nèi)沒有與其共邊的其它環(huán);(2)環(huán)L的方向與有界面F的法向滿足右手螺旋定則.定義4維點(diǎn)與二維點(diǎn)性質(zhì)1(空間點(diǎn)的投影特性).設(shè)空間點(diǎn)P(x,y,z)在主視圖投影面上的投影為(xf,zf),在俯視圖投影面上的投影為(xt,yt),在側(cè)視圖投影面上的投影為(ys,zs),則有:xf=xt=x,yt=ys=y,zf=zs=z.性質(zhì)2(對應(yīng)原理).若主視圖、俯視圖、側(cè)視圖3個(gè)視圖中的二維點(diǎn)(xf,zf),(xt,yt)和(ys,zs)滿足那么它們對應(yīng)于三維空間中的唯一點(diǎn)(xf,yt,zs).3維形體算法本節(jié)主要討論基于三視圖的平面體的重建算法,與傳統(tǒng)的自底向上的重建算法相比較,該算法省去了候選塊的生成這一步驟.在重建過程中,我們首先根據(jù)對應(yīng)原理,從三視圖生成形體的三維頂點(diǎn)和三維邊,初步構(gòu)造出形體的線框模型.然后利用線框模型生成形體的面環(huán),最后根據(jù)Moebius規(guī)則和投影性質(zhì)進(jìn)行決策求解,獲得最終的三維形體.算法的主要步驟為:檢查整理輸入數(shù)據(jù);生成三維候選頂點(diǎn);生成候選邊;生成切割點(diǎn);構(gòu)造面環(huán);決策求解.在形體重建過程中,所產(chǎn)生的頂點(diǎn)、邊、面等未必都是最終形體的成分,有的可能是非法的,在重建過程中將被消除.為此,我們把這個(gè)過程中的頂點(diǎn)、邊和面稱為候選頂點(diǎn)、候選邊和候選面,分別記為C＿Vertex,C＿Edge和C＿Face.3.1建立階段及其數(shù)據(jù)的選取過程本算法的輸入數(shù)據(jù)是屏幕坐標(biāo)系下的三視圖.為了獲得重建算法所需的數(shù)據(jù),首先需要找出3個(gè)視圖的公共原點(diǎn),然后分離3個(gè)視圖.對于每一個(gè)視圖,我們建立相應(yīng)的二維頂點(diǎn)表CnodeList和二維邊表CsegmentList,并檢查輸入數(shù)據(jù)的合法性.3.2共享軸接合點(diǎn)的構(gòu)成為了生成所有的三維候選頂點(diǎn),我們首先從兩個(gè)不同視圖的二維頂點(diǎn)表中各取一點(diǎn),如果兩點(diǎn)在共享軸上的坐標(biāo)值相等,那么繼續(xù)在第3個(gè)視圖的二維頂點(diǎn)表中查找與上述兩點(diǎn)除相同坐標(biāo)值之外的其它兩個(gè)坐標(biāo)值完全相同的頂點(diǎn).如果第3個(gè)視圖的二維頂點(diǎn)表中存在這樣的二維點(diǎn),那么這3個(gè)二維頂點(diǎn)生成了一個(gè)C＿Vertex.3.3假設(shè)假設(shè)不成立為了降低處理時(shí)間,我們利用二維點(diǎn)、邊和三維點(diǎn)、邊之間的幾何關(guān)系和生成規(guī)則,來減少投影匹配的次數(shù).性質(zhì)3.垂直于某投影平面的直線段在該投影面上的投影是二重點(diǎn)(二維頂點(diǎn)).性質(zhì)4.設(shè)e是由兩個(gè)C＿Vertex構(gòu)成的線段,如果e僅在一個(gè)視圖中的投影包含在二維視圖的邊表中,則e不是一條C＿Edge.證明.假設(shè)命題不成立,則出現(xiàn)下面兩種情況.1)e僅在一個(gè)視圖中的投影為二維邊,在其它兩個(gè)視圖中的投影為二維頂點(diǎn);2)e在3個(gè)視圖中的投影均為二維頂點(diǎn).以1)為例證明.由性質(zhì)3可知僅當(dāng)某條線段垂直于某一個(gè)投影平面時(shí),它在該平面上的投影為二維頂點(diǎn).為了滿足條件1),e應(yīng)該同時(shí)垂直于兩個(gè)投影平面.然而,一條直線段不可能同時(shí)垂直于兩個(gè)非平行平面,出現(xiàn)矛盾.同理可證假設(shè)2)也不成立.因而一條屬于三維形體的邊至少在兩個(gè)投影平面的投影為二維邊.證畢.新的三維邊生成方法主要是利用上述性質(zhì)來加快C＿Edge的生成.為了充分利用上述性質(zhì),我們采用如圖2所示的數(shù)據(jù)結(jié)構(gòu).新三維候選邊的生成方法為:對于每一視圖的二維邊,從二維邊兩個(gè)端點(diǎn)的C＿Vertex表中各取一點(diǎn),連接這兩點(diǎn)形成的三維邊為e,將e投影到另外兩個(gè)視圖中進(jìn)行匹配判斷.在匹配過程中,利用圖2的數(shù)據(jù)結(jié)構(gòu),我們僅需查找與該三維邊某一端點(diǎn)的投影點(diǎn)相關(guān)聯(lián)的二維邊,減少了匹配判斷次數(shù),降低了運(yùn)行時(shí)間.我們將在第4節(jié)分析算法的效率.3.4切割點(diǎn)的生成在第3.2節(jié),我們給出了一般頂點(diǎn)的生成方法,然而形體中可能存在切割點(diǎn)(如圖3中的點(diǎn)P),不能通過前述方法生成.為了得到合法的線框圖,我們在線框模型中引入切割點(diǎn).由切割點(diǎn)的定義和投影的性質(zhì)可知,切割點(diǎn)至少在一個(gè)視圖中的投影為兩條非共線二維邊的交點(diǎn),并且這一交點(diǎn)不是該視圖中二維邊的端點(diǎn),而是二維邊的內(nèi)點(diǎn).按照慣例,這類二維點(diǎn)是不出現(xiàn)在二維視圖中的.然而為了能夠生成相應(yīng)的線框圖,我們需要求出該二維點(diǎn)及與其相關(guān)聯(lián)的二維邊.利用這一性質(zhì),在三視圖的預(yù)處理中,對兩個(gè)非共線的二維邊求交獲得此二維點(diǎn)的同時(shí),我們將這樣的二維頂點(diǎn)放入到一個(gè)臨時(shí)的二維點(diǎn)表中,并記錄與其相關(guān)聯(lián)的兩條二維邊.此處我們僅檢測這些二維頂點(diǎn),由通過該二維頂點(diǎn)的兩條二維邊找到其生成的三維邊,對兩個(gè)三維邊進(jìn)行求交獲取切割點(diǎn).3.5以vivi,vi為起點(diǎn)的環(huán)本節(jié)將討論從線框模型中提取表面信息的算法.目前常用的表面信息自動識別方法為幾何方法.該方法的基本思想是:根據(jù)相鄰兩條邊的類型來確定一個(gè)三維面及其方程,然后應(yīng)用深度優(yōu)先方法搜索該面中的所有邊,生成所有可能的面環(huán),最后應(yīng)用一定的準(zhǔn)則刪除非極小環(huán).由上面的討論可知,幾何方法的幾何運(yùn)算復(fù)雜,需要較多的存儲空間和較長的處理時(shí)間.針對這一不足,我們提出了左鄰邊序列法,這一方法僅需生成構(gòu)造形體的面所需要的環(huán),避免了非極小環(huán)的生成,節(jié)省了算法的處理時(shí)間和存儲空間.算法主要包含6步:1.選擇未處理過的凸頂點(diǎn)vi作為跟蹤起點(diǎn);2.選擇未組合過的共點(diǎn)于vi且不共線的邊對el(vl,vi),em(vi,vm),假設(shè)由這兩條邊所組成的面F的法向?yàn)閚=(vi-vl)×(vm-vi),找出屬于該面的所有邊E(F),確定該平面頂點(diǎn)和邊的連接關(guān)系.對于度大于2的頂點(diǎn),求出該頂點(diǎn)的左鄰邊序列;3.從E(F)中選擇一條未被引用過的邊ei(vi,vj)作為初始邊;4.根據(jù)已知條件,選擇一遍歷方向,假設(shè)vi→vj是目前的遍歷方向;5.如果vj的度為2,則將與該點(diǎn)相關(guān)聯(lián)的另外一條邊加入到環(huán)中,否則根據(jù)該點(diǎn)的左鄰邊序列確定環(huán)中的下一條邊,假設(shè)這條邊為el(vj,vl);6.若vl=vi,生成環(huán)并返回到步驟2,否則令vj=vl,轉(zhuǎn)步驟4;注:在尋找一個(gè)面的所有邊時(shí),我們僅檢測與該面上已知頂點(diǎn)相關(guān)聯(lián)的邊,并且屬于該面的共點(diǎn)邊對均認(rèn)為已經(jīng)組合過,不再用于求解新的面方程,這樣就減少了面及面環(huán)生成過程的判斷次數(shù).另外,確定左鄰邊序列時(shí),我們并不求出兩邊的夾角,而通過下述方法來簡化計(jì)算.設(shè)共點(diǎn)于vi的邊為e1,e2,…,ek,將e1作為x軸,將該平面的法向量看作是z軸,那么y=z×x.設(shè)《n》x,《n》y為x軸和y軸的單位向量,e1和ei夾角的正、余弦為:通過比較cosθi和sinθi(i=2,…,k),可以確定相應(yīng)夾角的大小關(guān)系,進(jìn)而可以求出該點(diǎn)的左鄰邊序列.這樣就避免了反余弦求角計(jì)算,降低了運(yùn)算復(fù)雜度.3.6結(jié)果顯著性處理從前面的討論可知,三維形體的點(diǎn)和邊是重建過程中生成的三維線框模型的子集.即,三維線框模型中可能包含假元.因而重建的關(guān)鍵技術(shù)是檢測并刪除線框模型中的假元.Wesley和Markowsky首先給出與候選塊(Candidateblock)有關(guān)的決策求解方法,目前許多B-rep重建使用這種方法.該方法生成許多臨時(shí)候選塊,然后組合這些候選塊,構(gòu)造所有可能的形體,并檢查每個(gè)合法形體的三視圖是否與輸入數(shù)據(jù)完全匹配.然而,算法中臨時(shí)生成的某些候選塊可能會相交,在其邊界上產(chǎn)生非法的交線.為了避免兩個(gè)候選塊之間存在非法交線,傳統(tǒng)方法引入了原三維形體中并不存在的臨時(shí)的“切割邊”.切割邊將剛生成的候選面分割成較小的候選面.然后交替引用每一面,組合出所有的候選塊.從上面的討論可知,傳統(tǒng)決策求解方法不僅搜索復(fù)雜度是指數(shù)級的,而且切割邊的引入也是十分費(fèi)時(shí)和浪費(fèi)存儲空間的,特別是當(dāng)形體中包含曲面時(shí)為了避免這種窮舉搜索策略和切割邊的引入我們給出與面有關(guān)的決策求解方法.該方法利用一些決策規(guī)則搜索求解最終的三維形體.本節(jié)使用的決策規(guī)則主要是基于Moebius規(guī)則和工程圖的性質(zhì).我們首先介紹組成形體的邊應(yīng)滿足的兩個(gè)條件.(1)局部條件(Moebius規(guī)則):2-流形體中的每一條邊屬于兩個(gè)面,三維邊在每個(gè)面中的方向不同,即屬于兩個(gè)面的邊在兩個(gè)面環(huán)中的方向相反;(2)全局條件:組成形體的任意兩個(gè)面除了構(gòu)成它們的邊之外,不能再有任何交線.決策求解算法的基本思想是根據(jù)形體的局部條件和全局條件刪除線框模型中的非流形邊,并使生成的形體滿足輸入的三視圖.為了確保生成的三維形體與輸入的視圖匹配,我們采取下述方法.對于二維視圖中的每一條二維邊si,我們計(jì)算出該二維邊所對應(yīng)的三維邊總數(shù)ni.在構(gòu)造三維形體的過程中,我們可能會刪去線框模型中的一部分邊,這時(shí)二維視圖中一部分二維邊的ni值將會減少.決策方法的目標(biāo)是在保證每一個(gè)ni為正數(shù)的前提下,生成有效的三維形體.圖4給出決策求解方法中所用的數(shù)據(jù)結(jié)構(gòu).下面給出決策求解算法.1.在生成的線框模型中尋找非流形邊,設(shè)為ei.2.在與ei相關(guān)聯(lián)的面中選出任意兩個(gè)未組合的面,設(shè)這兩個(gè)面為合法面,將兩個(gè)面的所有邊均標(biāo)識為TRUE,刪除與ei相關(guān)聯(lián)的其它面,并檢查刪除邊所對應(yīng)二維邊的ni值是否為0,若為0,返回2,否則轉(zhuǎn)3;3.檢查線框模型中是否存在僅與一個(gè)面相關(guān)聯(lián)的邊,若不存在,轉(zhuǎn)向5,否則,轉(zhuǎn)向4;4.刪除該面和該邊,檢查刪除邊所對應(yīng)二維邊的ni值是否為0,若為0,返回2,否則轉(zhuǎn)5;5.檢測是否存在與現(xiàn)有合法面相交于內(nèi)部的面,若存在,則該面為非法面,刪除該面,轉(zhuǎn)向3,若不存在,轉(zhuǎn)向6;6.對于線框模型中投影線為虛線的邊,檢測是否有面遮擋它,若有,轉(zhuǎn)向7,否則,轉(zhuǎn)向2;7.檢測是否所有邊的表示均為TRUE,若是,生成形體,否則轉(zhuǎn)向1.基于以上算法步驟,我們使用VisualC++實(shí)現(xiàn)了一個(gè)原型實(shí)驗(yàn)系統(tǒng),圖5給出了應(yīng)用新方法進(jìn)行重建的機(jī)械零件.4算法運(yùn)行時(shí)間的比較本節(jié)詳細(xì)分析了重建主要階段的算法復(fù)雜性,并以實(shí)際物體為例,比較了本文所提出的算法與傳統(tǒng)的以Gujar和Shin為代表的重建方法的運(yùn)行效率.圖6、圖7給出了應(yīng)用本文的算法進(jìn)行重建的例子,實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)算法相比較,該算法在保持存儲空間不變的情況下,運(yùn)行速度提高了10倍左右.(1)候選邊生成階段的算法效率分析:傳統(tǒng)的三維邊的生成方法為:在生成的C＿Vertex表中任取兩點(diǎn),為了檢測這兩點(diǎn)的連線是否為一條C＿Edge,需要將這條新生成的C＿Edge重新投影到三視圖中,并與三視圖的二維點(diǎn)表和邊表進(jìn)行匹配.如果該線段的投影包含在3個(gè)視圖的二維點(diǎn)表或邊表中,則該邊是一條C＿Edge.該方法再投影的次數(shù)為n(n-1)/2,其中n=card(C＿Vertexs).每一C＿Edge的匹配時(shí)間復(fù)雜度為O(m),m為三視圖中二維線段與頂點(diǎn)之和.對于復(fù)雜的形體,這一過程勢必導(dǎo)致處理時(shí)間的迅速增加.而新算法的再投影次數(shù)為msn-2.ms為二維邊數(shù),n-是每一個(gè)二維點(diǎn)所生成的C＿Vertex平均數(shù),且n-滿足1≤n-≤3n,即msn-2<<n2.每一C＿Edge的匹配時(shí)間復(fù)雜度為O(1).表1給出了候選邊生成過程的運(yùn)行時(shí)間的比較,由表1可知,本文所提出的算法顯著減少了處理時(shí)間(2)切割點(diǎn)生成階段的算法效率分析:傳統(tǒng)的方法從生成的三維候選邊表中任取兩條邊,通過求交獲取切割點(diǎn),因而傳統(tǒng)切割點(diǎn)生成方法的求交次數(shù)為ne(ne-1)/2,其中ne為C＿Edge總數(shù).我們方法的求交次數(shù)為nsne2,其中ns是度≥4的二維頂點(diǎn)數(shù),ne是投影通過這些二維頂點(diǎn)的C＿Edge平均數(shù).由于2nsne<ne,ne<<ne,所以nsns2<<ne2.(3)面及面環(huán)生成階段的算法效率分析:表3給出了提取表面信息階段算法運(yùn)行時(shí)間的比較,由表3可知本文所提出的方法需要較少的處理時(shí)間.(4)決策求解階段的算法效率分析:表4給出了決策求解階段運(yùn)行時(shí)間的比較,表4表明本文所提出的方法需要較少的處理時(shí)間,這是因?yàn)槲覀兊姆椒ㄊ∪チ撕蜻x塊的生成這一步驟,避免傳統(tǒng)窮舉搜索策略和切割邊的引入,從而降低了運(yùn)行時(shí)間.上面列出了重建主要階段的算法運(yùn)行時(shí)間,加上其它一些必要處理過程的運(yùn)行時(shí)間,我們給出了整個(gè)重建過程的處理時(shí)間比較(見表5),實(shí)驗(yàn)結(jié)果表明我們的重建算法提高