iT邦幫忙

2018 iT 邦幫忙鐵人賽
DAY 27
0
Modern Web

在Three.js探索CAD的奧秘系列 第 27

Day 27 : 三角網格邊翻轉

前言

邊翻轉(Flip edge),是指某邊AB相鄰三角形所圍成的四邊形ABCD中,將邊翻轉為CD而改變網格原有的結構,這種網格操作行為可用於處理狹長形三角網格問題,如下圖所示。

https://ithelp.ithome.com.tw/upload/images/20180115/201071754wqX26Sadw.png
邊翻轉示意圖

狹長形網格問題

在CAD領域中一般來說,理想的三角網格會是正三角形,而狹長形網格是指三角網格的內角中有角度過大的情形,這時就會造成三角網格品質不佳,下圖是狹長形網格情形。

https://lh3.googleusercontent.com/_4ZC1nOzdgyRuU8CVD8dmq0wrDsV1IbzmTn_Zo5y9CVzBdc0BdFpR-WQ4lJNtQ8m4CKvBy2vsCcIh5LqcA=s0-tmp.gif
因網格細分造成的狹長形網格

價數計算

為了解決這個問題需要將邊進行翻轉,本文採用計算點的價數(Valence)來進行修正,價數是指某一點鄰近共有多少點的數量,如下圖中的紅色的點A,鄰近共有6個藍色的點,因此價數為6
https://ithelp.ithome.com.tw/upload/images/20180115/20107175XQ4iJvbcCn.png

價數平方和

價數平方和是用來判斷邊翻轉後是否需提升網格質量的依據,而在開始之前必須建立一個理想的價數作為目標,在本文中將 目標價數 設定為6,用來將價數盡量逼近此數量,接著假設四個點的價數為V_A、V_B、V_C、V_D,目標價數為V target,最後計算四個點與目標價數之差值,再取所有差值的平方和即可,公式如下:

https://ithelp.ithome.com.tw/upload/images/20180116/20107175jEOjXvR3ap.png
價數平方和公式: https://goo.gl/qoBL8q

邊翻轉前

https://ithelp.ithome.com.tw/upload/images/20180116/20107175Yn9BYKxQXx.png
以上圖的範例來解說,邊翻轉前的價數,點 A 的價數為 7 ,點 B 的價數為 7 ,點 C 的價數為 5 ,點 D 的價數為 5 ,套入公式後得到價數。

https://ithelp.ithome.com.tw/upload/images/20180116/20107175riQk0V4TRR.png
計算結果: https://goo.gl/AawHFU

邊翻轉後

https://ithelp.ithome.com.tw/upload/images/20180116/20107175emG4v5ftVM.png
以上圖的範例來解說,邊翻轉後的價數,點 A 的價數為 6 ,點 B 的價數為 6 ,點 C 的價數為 6 ,點 D 的價數為 6 ,套入公式後得到價數。

https://ithelp.ithome.com.tw/upload/images/20180116/20107175zHdw6zfNVa.png
計算結果: https://goo.gl/Y2wjaX

邊翻轉判定

最後透過價數平方和來決定是否要翻轉該邊線,若翻轉後產生 較小的值 ,則判定需要進行邊翻轉,反之則不需要翻轉。本範例中翻轉前為 6 而翻轉後為 0 因此判定需要進行邊翻轉。

後記

本次不撰寫程式碼,先解說邊翻轉的原理以及如何實作,邊翻轉是建立理想的三角網格其重要的步驟之一,大家務必清楚的理解其原理。最近圖解部分較多,由於筆者所有的圖都是自己繪製或是程式截圖,沒有一張是從網路上下載的,有時候可能草草放上導致排版或文章順暢度不佳,但還是會把文章排版得比較美觀漂亮給大家,不便之處敬請見諒。


上一篇
Day 26 : 三角網格平滑變形
下一篇
Day 28 : 網格邊翻轉實作
系列文
在Three.js探索CAD的奧秘30

尚未有邦友留言

立即登入留言