基于工程圖紙的三維形體重建技術

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