当前位置:首页 >> 机械/仪表 >>

快速3D 图像曲面摊平至2D 平面演算法之研究


快速 3D 圖像曲面攤平至 2D 平面演算法之研究
林易泉 李國龍 高國峰 國立虎尾技術學院資訊工程系 樹德科技大學資訊工程系 樹德科技大學資管所 lyc@nhit.edu.tw s89113247@mail.student.stu.edu.tw kuofeng@msn.com 摘要
本論文主要探討如何將複雜的 3D 三角形網 格曲面攤平至

2D 平面上之研究。對許多製造業 如 製鞋 成衣 或製管而言往往會透過 CAD/CAM : 、 、 系統幫助於立體產品之設計 透過此類系統之輔助 , 設計業者可以輕易設計出產品之立體式樣 而設計 , 完之後之產品立體樣本可透過攤平演算法根據其 3D 立體資訊攤平至其對應之 2D 平面,使製造商 能快速獲得其產品之平面材料資訊 由於製造業所 。 設計出之立體曲面是非常複雜的 而這些曲面常包 , 含一些如橢圓或者雙曲曲率之類的不可攤曲面 這 , 些不可攤曲面於攤平時是非常耗時且攤平完之後 可能會造成失真情況 為了求更精確之平面資訊往 。 往就必須減少於攤平時之失真 如此一來便會造成 , 需要更大之計算量來減少失真情況 而本論文為了 。 解決攤平時之費時以及減少攤平後之失真所以設 計出一套新的加速攤平演算法 從實驗數據顯示經 。 由此攤平演算法可以大大的加快攤平時間以及降 低攤平後之失真。 關鍵字:3D 攤平、3D 曲面、3D 電腦輔助設計

圖一、可展曲面。

一、前言
隨著資訊科技之快速發展,許多產業之 3D 產品 設計與製造過程 皆可藉由電腦輔助設計與製造系 , 統(CAD/CAM)的幫助,能克服人工的費時及精確 度之不穩定性。要達到全自動電腦輔助設計之目 標,首先需要設計開發出一套有效率的攤平演算 法,能夠將 3D 曲面攤平至 2D 平面樣版,進而獲 取產品材料的平面資訊 方便進一步的設計或製造 , 程序,提昇整體效率。3D 曲面攤平的工作在許多 的領域經常被使用到,如製鞋、造船、製管、繪製 地圖、醫療診斷、和服裝設計等。 從微分幾何學的觀點[1],三度空間的任意曲 面可分為兩類,根據高斯曲率(Gaussian curvature) 的定義,3D 曲面可分成:可展曲面(developable surface)與不可展曲面兩種。曲面上某一點的全曲 率為兩個主曲率(principle curvature)的乘積。可展 曲面上的全曲率等於零,如圓柱、圖錐等,攤平時 可以與平面貼合 (圖一),曲面幾何距離不會因攤 平而有改變 而不可展曲面上的全曲率可分為橢圖 。 曲率(elliptical curvature)與雙曲點曲率(hyperbolic curvature)兩種(圖二)。

圖二、不可展曲面:(a)橢圓曲率曲面;(b) 雙曲點 曲率曲面 3D 曲面展開至 2D 平面之工作,雖然方法多 樣化,但是將 3D 曲面切割成規則或不規則之三角 形或四角形之連續網格後,再進行處理,似乎是目 前的主流方式。由於 3D 曲面形狀複雜,經常是由 不同形狀的不可展曲面混合組成 故展開後皆會有 , 失真或變形發生;立體形狀愈複雜,產生的失真就 愈大。至於如何表示這種失真,各研究者的論述皆 有其獨到之創見。如何能控制失真程度,且讓執行 速度能加快,則是在這系統發展上所該努力的目 標。目前有許多學者皆提出其獨特之攤平演算法 如: 一、日本學者 Shimada 及 Tada 兩位所提出之 有限元素法[7](Finite Element Method)。 二、國內學者謝孟達等人[8]提出之旋轉正交 矩陣法(Orthogonal Property of Rotation Matrices)。 三 英國學者 McCartney 等人所提出之疊代應 、 變能量釋放法[2-5](Iterative Strain Energy Relaxation Method)。 有限元素法於攤平時可以獲得精確的結果 但 , 是其攤平計算需花費可觀之計算時間 旋轉正交矩 。

陣法簡單快速但是攤平後的樣版會有斷裂 重疊之 、 現象隨著曲面愈複雜情況愈嚴重 疊代應變能量釋 。 放法最直接且不複雜但是愈接近最後攤平完成階 段,其能量釋放次數更為頻繁。 所以本論文針對英國學者所提出之疊代應變能 量釋放法提出一改良疊代應變能量釋放法 (Improve Iterative Strain Energy Relaxation Method, IISERM),此一 IISERM 利用一最大堆積樹(Max Heap Tree)來累積攤平過程中每一網點之能量,並 於特定時間點根據此最大堆積樹取其最大之能量 值之網點給予能量釋放,此 IISERM 所需之能量釋 放之時間複雜度為 O(logN),且釋放完之能量累積 也跟未改善前差異不大。 而本論文架構描述如下 第二章我們針對上述 : 所提之攤平演算法做一簡單描述 第三章詳細描述 。 本論文所提之 IISERM 之演算法, 並詳細說明此演 算法如何達到快速能量釋放又不嚴重失真 第四章 。 我們針對未改良前之疊代應變能量釋放演算法做 一些實驗,並且將其實驗數據與本論文所提之 IISERM 做個比較。第五章針對本論文之研究做個 結論以及本論文未來之研究方向。

若對複雜曲面適度分割成若干個較簡單之小 曲面,並加入適當尖摺或鬆份,應可獲得不 少改良。 二 、 旋 轉 正 交 矩 陣 法 [8](Orthogonal Property of Rotation Matrices) 若考慮攤平演算法之複雜度,則發展高效率 之攤平演算法是無法避免的。國內謝孟達等人 [8],應用電腦圖學中之旋轉矩陣正交特性,將 3D 曲面之三角網格展開至 2D 平面上,並嘗試應用在 服裝基本原型上。 旋轉矩陣正交特性,空間中任意三個正交的 單位向量,皆可以旋轉至卡式座標系統的,x,y,z 三個軸上 方法是將這三個向量分別置於旋轉矩陣 , 的第一行、第二行、及第三行,如圖三所示。此特 性提供一非常方便之工具 經過二至三次矩陣相乘 , 運算 便可以將空間中一三角形平面轉換至 XY 平 , 面上,面朝向 Z 軸方向,一邊與 X 軸或 Y 軸對齊, 及對齊 X 軸或 Y 軸之邊的任一頂點與原點重合。
v2 v1 u x y
x v3

二、文獻探討
在本章中我們就所搜集較代表性之攤平演算法相 關研究歸納如下: 一、有限元素法[6](Finite Element Method) 日本學者 Shimada 及 Tada 兩位,採用 2D 有 限元素法則(FEM)及平板熱應力模型[7],求出 3D 鞋面之對應 2D 平面樣版。此方法之展開失真指標 為平板之熱應變能量(strain energy),失真修正方式 乃是反覆地使用 2D 有限元素法則修正連續之展開 結果 直到熱應變能量小於某一預先指定之門閥值 , (threshold value)。 此有限元素法則演算法有一特色,它並不直 接進行 3D 對 2D 映射(mapping)轉換,而是先想像 一粗估之平面,此平面具有與 3D 曲面相同之網點 數量,且三角形數量也相同,差別只是各個相對應 三角形間之形狀及方位不同而已 根據這些三角形 。 之形狀差異,藉由 2D 有限元素法則可以推導出, 在粗估平面上之網點 2D 修正位移量,及其所對應 之應變能量。經修正後之 2D 平面形狀更趨精確, 因此,若欲獲得較佳精確結果,則此動作應反覆連 續執行若干次。 由初步的實驗觀察中,發現有限元素方法之 特點,並歸納如下: 此法可以獲得精確的結果。 需花費可觀的計算時間,求解大型聯立方程 組。 當曲面較複雜且網點個數眾多時,可能需要 較高等級的大型電腦輔助。

z

v
轉換矩陣

z v1 v2 y

圖三、轉換矩陣示意圖。 第一個 3D 曲面上轉換至 XY 平面之三角 形,只需經過兩次矩陣相乘運算即可。第二個三角 形,則需從與已轉換至 XY 平面之三角形共邊開 始,逐一轉換至 XY 平面上,且具下列條件:(1) 一 頂點與原點重合,(2) 一邊與 X 軸對齊,(3) 三角 形平面朝向 Z 軸方向。然而,這還不是此三角形 的位置,它仍需經過一矩陣相乘,使其繞 Z 軸旋 轉 同時平移至平面上與之共邊之三角形的適當邊 , 對齊。 由初步的實驗觀察中,發現旋轉正交矩陣方 法之特點,並歸納如下: 此法簡單快速,曲面上之每一三角形只需經 過四次以內之矩陣相乘計算。 若是可展曲面的話,則此法可得到正確攤平 無失真的樣版。 若是不可展曲面,則攤平後的樣版會有斷 裂、重疊的現象,曲面愈複雜情形愈嚴重。 需有後處理程序,縫補這些斷裂、重疊的現 象,並控制在可接受的失真範圍內。

三 、 疊 代 應 變 能 量 釋 放 法 [2-5](Iterative Strain Energy Relaxation Method) 英國學者 McCartney 等人,發展了一類似於 上述利用旋轉矩陣正交特性演算法之平面展開方 案 此方法可以有效地針對非可展曲面進行平面展 。 開,因為此法於攤平每一三角形的過程中,若發生 失真現象,隨即進行能量釋放,擴散至目前已攤平 之每一網點 因此它的時間複雜度比前述之第二個 , 方法高,但攤平效果良好。在討論此演算法細節之 前,先定義一些符號: T (Triangle Set):輸入三角形集合(亦即欲處 理之 3D 曲面三角形網格)。 V(Available Set):包含所有尚未攤平之 3D 曲 面上之三角形集合。 A (Active Set) (ordered):稱為有序活動集 合,即從集合 V 中,特別挑出來所成的三角 形集合,每個成員具有與已攤平之三角形至 少一個以上的邊共邊之特性。這樣的三角形 會很多,將依照被加入的順序,逐一地攤平 至 2D 平面上。 F(Flattened Set):所有已經攤平至 2D 平面之 三角形皆屬於此展開集合。 在 McCartney 的方法中 3D 曲面三角形,從 V 中挑選一最接近曲面平均位置之三角形 攤平至集 , 合 F 中,再將集合 V 中所有與 F 集合中之三角形 有共邊之三角形移至集合 A 中。判斷集合 A 是否 為空集合(有無三角形),若有即結束此三角形坦 平。若 A 集合中有三角形等待攤平,則從 A 集合 中取出一三角形,並判斷該三角形是否已攤平,若 沒有難平則計算第三點的平面座標並將其攤平 若 , 此三角第三點與其他三角形共邊為束縛三角形 即 , 進行誤差式攤平進行能量擴散動做程序 如下圖四 , McCartney 之演算法流程所示。

由初步的實驗觀察中,發現疊代應變量釋放 方法之特點,並歸納如下: 此法也是一種直接且不複雜的方法。 能量釋放過程算是最耗時的部份,且愈接近 完成階段,每次釋能所需的時間愈多。 此法的執行時間與輸入的 3D 曲面複雜度有 關,愈複雜所需時間愈多;這是因為釋能的 頻率遍高。 此法所攤平的樣版,不會產生斷裂、或重疊 的現象。 疊代應變能量釋放演算法中,有關攤平應變 能量(Strain Energy)的釋放方式說明如下: 1、 假設某一曲面三角形上一邊為 AB ,攤平後則 變成 A' B' ,其能量定義如下:

f energy ( A ' , B ' , A, B) = 0.5 ×

( A ' B ' ? AB) 2 AB

2、 如圖十一中 P’i, P’p, P’q, P’r, P’s, 分別為 立體網格中 3D 頂點 Pi, Pp, Pq, Pr, Ps, 攤平 以後對應之 2D 頂點 今定義位於 P’i 頂點處之 。 能量值為
' Ei = f energy( pi' , p'p , pi , p p ) + fenergy( pi' , pq , pi , pq )

+ fenergy( pi' , pr' , pi , pr ) + fenergy( pi' , ps' , pi , ps )
……………….…(1) 若 P’i 頂點將往 a 方向移動至 P’ia 頂點後的能量之 定義為:
' ' ' Eia = fenergy( pia , p'p , pi , pp ) + fenergy( pia , pq , pi , pq ) ' ' + fenergy( pia , pr' , pi , pr ) + fenergy( pia , ps' , pi , ps )

3、 如圖五所示,P’i 頂點可往 a, b, c, d 四個方 向移動點後, 求得 E ia , E ib , Eic , E id 四個能 量值,與原來移動前之能量值比較後,P’i 頂 點將往能獲得最大釋能的方向移動。其最大釋 能定義如下:
?E i = max{( E i ? E ia ), ( E i ? E ib ), ( E i ? E ic ), ( E i ? E id )}

P'p
p'ia

' Pq

p'id
p'ic

p'ib

' Pr
' Ps

圖四、McCartney 演算法流程

圖五、於 2D 平面能量釋放時之四個嘗試位移。

三、IISERM Algorithm
在本論文中我們以 ISERM 為基礎提出一改 良式疊代應變能量釋放法(Improve Iterative Strain Energy Relaxation Method, IISERM) 此 IISERM 是 , 利用一最大堆積樹(Heap Tree)之資料結構,根據 3D 曲面上相連區域中各頂點,計算其能量值,並 將這些頂點之能量生成一最大堆積樹(Max Heap Tree),根據此堆積樹我們即可得知已攤平的頂點 之最大能量累積 然後選擇該最大堆積樹裡面數個 , 最大能量值頂量來做能量釋放 此種方式可以減少 , 能量釋放之次數加快其攤平速度。 最大能量堆積樹表示法: 假設有一 3D 立體網格由十八片三角網格及十 六個頂點所組成如圖六所示

階時,即第四階有八個節點時,在第三階度往下訪 之原為兩條釋能路徑 在第四階再比較非路徑之節 , 點大小,為新增路徑之起點,如圖中假設 E8>E9、 E14>E15 時,E8 和 E14 即為第四階之能量釋放路 線之新增起點。到第六階時(第五階已有十六個節 點),至此第五階則新增四個路徑之起點,依此類 推。換句話說在第四階之開始往後每多一階,即新 增加該階度節點數/2條路徑。

圖八、快速能量釋放路徑示意圖 此快速攤平演算法之步驟如下: Step1:從未攤平之曲面集中選取位於中間之曲面 來攤平 然後計算其能量並加入到最大能量 , 堆積樹中。 Step2:其找其共邊三角形並置入待攤平三角形之 佇列(Queue)中。 Step3:假設佇列中無攤平三角形則攤平結束,否 則再從佇列中取出一三角形至 Step4。 Step4:判斷此三角形是否為束縛三角形,如果是 至 Step5 否則至 Step6。 Step5:直接攤平此三角形之第三點,並計算其能 量值並將該能量值加入至最大能量堆積 樹,調整最大能量堆積樹並至 Step7。 Step6:計算該曲面之新決定點的第三點攤平位置 與原先位置之點距離 判斷此距離是否大於 , 設定之最大容許差距 如果大於的話則進行 , 誤差式攤平並計算其能量後進入 Step7,否 則的話則決定攤平面新第三點座標並記錄 所計算之能量值並回 Step2。 Step7:如果樹之階度小於 4,樹根開始往第二階 兩個子節點進行釋能動作 依此分別尋找下 , 一階子節點中能量最大者為能量釋放路 徑,直到路徑之末節點並至 Step8。否則就 從樹根開始往第二階兩個子節點進行釋能 動作,至第四階以後,找出非路徑子樹中之 最大能量節點並新增為新能量釋放路徑 往 。 下每一階段皆新增能量釋放路徑節點直到 末階並至 Step8。 Step8:能量釋放完之後,被釋放之頂點能量值已 改變且釋放頂點之相鄰點能量也因釋放點 之位移而改變 依據這些點再調整最大堆積 , 樹,使其待合最大堆積樹之標準。至 Step2。

圖六、十六個頂點形成之 3D 曲面 上例十六個頂點所構成之曲面 若曲面已攤平 , 之平面頂點 根據 McCarteny 攤平演算法能量計算 , 式中,攤平時分別計算每一頂點,與其它頂點之能 量值為 E1,E2…..E16。舉例說明,假設此一曲面攤 平後所計算出之能量關係分別為 E1>E2…..>E16 則我們可以生成一最大能量之堆積樹如圖七所示 。

圖七、已攤平之頂點所生成之最大堆積樹 快速能量釋放攤平演算法: 如圖八所示為 33 個頂點所建構出之最大能量 堆積樹之能量釋放方式,即從樹根開始,第一階度 後第二個階度行進時 將兩個子節點全部歸為須走 , 之路徑節點 第二階產生之兩條路徑即根據讓子節 , 點最大者繼續往下訪至最後點階 節點增加至第五 ;

四、實驗結果
在本章節中主要將本研究之結果及測試數據之 呈現。首先,將 3D 曲面之可展與不可展曲面利用 本論文所提出之加速演算法 取不同樣本之攤平測 , 試,並呈現攤平之結果,及與英國學者 McCarteny 所提出之演算法進行實驗比較 兩方法比較主要實 。 驗方向為資料量(曲面點數)對於攤平時間長短之 影響、資料量對能量釋放頻率之影響。 曲面上全曲率為兩個主曲的乘積 可攤曲面即 , 是曲面上的全曲率等於零 如錐形和圓柱及圓錐形 , 等曲面較不複雜,在攤平時可減少失真情形發生, 且可以與平面貼合 圖九即是圓柱部份曲面攤平樣 。 版,而圖十即是攤平後之結果。

圖十二、球體攤平後之結果 圖十三則是 IISERM 與 ISERM 兩攤平演算法 針對不同曲面點數所測得攤平花費時間之實驗結 果,由此張測試數據圖我們可以看到 IISERM 演算 法隨著曲面點數的增加其攤平所花費的時間成長 速度相當的有限,而 ISERM 在曲面點數愈大時, 其攤平所花費之時間是呈現指數型成長。

圖九、圓柱部份曲面攤平樣版

圖十三、攤平時間比較圖 本論文所提出之 IISERM 演算法之所以能夠 加快曲面攤平的原因在於本演算法減少了攤平時 能量釋放之次數 這意味著能量釋放次數少相對的 , 所累積的能量就會變得比較大 而剩餘能量愈大代 , 表著其失真情形會愈重,但是根據 IISERM 演算法 的特性,能量愈大的攤平點其被釋放之頻率會愈 高 所以其累積之能量亦會隨著最大能量點被釋放 , 之頻繁而降低整體之能量累積,圖十四即是針對 ISERM 及 IISERM 兩演算法攤平完後之剩餘能量 比較圖,我們可以看到 ISERM 之剩餘能量會趨近 於零,因為 ISERM 是疊代式的能量釋放,無論其 曲面點是否有無能量累積皆會被釋放,跟 IISERM 之剩餘能量比較起來我們可以看到 IISERM 之剩 餘能量值比 ISERM 之剩餘能量值高,但是對於曲 面之失真度而言這樣差距是被允許的。

圖十、攤平後之結果 球體與彎管均為不可攤曲面 在允許失真可接受 , 範圍內,可攤平近似樣版。圖十一為球體未攤平時 之立體樣式而圖十二則是攤平後之結果。

圖十一、球體未攤平時之立體樣式

圖十四、新舊方式之剩餘能量比較圖

五、結論
3D 曲面攤平至 2D 平面技術是製造業應用資訊 科技非常重要的技術之一 而許多的攤平演算法皆 , 能夠提供非常好的攤平結果 但是其攤平所消耗的 , 時間也是非常驚人的,所以本論文所提出之 IISERM 演算法能夠快速的將 3D 曲面攤平至 2D 平面 由實驗結果數據顯示經過本論文所提之攤平 。 演算法可以提高其攤平速度以及精確之攤平能量 。 在未來預計會將本論文所提之 IISERM 演算 法運用於分散式環境下 利用分散式環境下之平行 , 運算來進行平行攤平計算 預計將會得到比現在更 , 快速之攤平速度。

3.

B. K. Hinds and J. McCartney, “Interactive Garment Design,” The Visual Computer, pp. 53-61, 1990. B. K. Hinds, J. McCartney, C. Hadden, and J. Diamond, “3D CAD for Garment Design,” International Journal of Clothing Science and Technology, Vol. 4, No. 4, pp. 6-14, 1992. J. McCartney, B. K. Hinds, and B. L. Seow, “The Flattening of Triangulated Surfaces Incorporating Darts and Gussets,” Computer-Aided Design, Vol. 31, pp. 249-260, 1999. J. N. Reddy, An Introduction to Finite Element Method, 2d edition, McGraw-Hill 1993. T. Shimada and Y. Tada, “Development of a Curved Surface using a Finite Element Method,” in Brebbia, C. A. and Hernandez, S. (eds) proc. 1st Int. Conf. Computer-Aided Optimum Design of Structures, Recent Advances Springer-Verlag, pp. 23-30, 1989. M. D. Shieh, C. C. Yang, K. Z. Sun, M. J. Tsai, and J. J. Fang, “Computer Aided System for 2D Flatting of 3D Apparel – Non-developable Surfaces,” 經濟部所屬事業單位協助中小企業 推動研究發展計畫︰合約編號︰P188048

4.

5.

誌謝
本研究之經費承蒙國科會工程處贊助 計劃編號:NSC 91-2213-366-003 。

6. 7.

參考文獻
1. E. D. Bloch, A First Course in Geometric Topology and Differential Geometry, Birkh?user Boston 1997. B. K. Hinds, J. McCartney, and G. Woods, “Pattern Development for 3D Surfaces,” Computer-Aided Design, Vol. 23, No. 8, pp. 583-592, 1991. 8.

2.


相关文章:
三种2D-3D定位算法(摄像机定标)
三种2D-3D定位算法(摄像机定标)_理学_高等教育_教育专区。三种2D-3D定位算法(...点正交投影到图像平面上同一个 2D 点这种情 况,具体的解法看的还不是太明白...
更多相关标签: