一、相關(guān)理論

測(cè)地極坐標(biāo)參數(shù)化的paper是我研究生學(xué)習(xí)階段，寫的第二篇沒(méi)有源碼的外文文獻(xiàn)，年少無(wú)知，看文獻(xiàn)的也是沒(méi)有完全看懂，就開(kāi)始寫代碼，然后通過(guò)代碼不斷的根據(jù)文獻(xiàn)算法，進(jìn)行調(diào)整，終于把paper的代碼實(shí)現(xiàn)了。在此把paper的算法詳細(xì)解讀一下，以供正在苦逼的搞三維圖形算法的同道中人學(xué)習(xí)。

三維的算法比較難，網(wǎng)上資料也比較少，國(guó)內(nèi)除了到知網(wǎng)、萬(wàn)方等數(shù)據(jù)庫(kù)可以有文獻(xiàn)看，代碼方面可以說(shuō)沒(méi)有，國(guó)外要找到提高源碼的paper也很不容易，所以要把三維CAGD的一些算法學(xué)懂實(shí)屬不易，在此祭奠曾經(jīng)走過(guò)的三維苦逼算法學(xué)習(xí)之路。本篇博文主要講解文獻(xiàn)：《Geodesic?polar?coordinates?on?polygonal》，這里中文我又把它翻譯為：測(cè)地極坐標(biāo)參數(shù)化，離散冪映射算法中每個(gè)頂點(diǎn)參數(shù)值取決于該頂點(diǎn)的法矢，因此網(wǎng)格曲率變化較大時(shí)經(jīng)常使得參數(shù)化結(jié)果發(fā)生較大扭曲。相比于離散指數(shù)映射算法，Eivind等提出的測(cè)地極坐標(biāo)參數(shù)化方法具有更好的穩(wěn)定性和魯棒性。

給定具有n個(gè)頂點(diǎn)的三角網(wǎng)格模型M=(V,E,T),V為頂點(diǎn)集，E為邊集，T為三角面片集合。設(shè)Tijk=[vi,vj,vk],設(shè)s為網(wǎng)格曲面上的任意點(diǎn)，切向量X為基方向，如圖。

二、算法講解

在網(wǎng)格曲面上，對(duì)于給定的參數(shù)化種子點(diǎn)S，我們把網(wǎng)格曲面上的頂點(diǎn)分為兩類：1-ring、k-ring(k>=2)，其中1-ring表示與s直接相連的頂點(diǎn)，k-ring表示不與s相鄰的頂點(diǎn)。對(duì)于測(cè)地極坐標(biāo)參數(shù)化方法來(lái)說(shuō)，我們需要根據(jù)這兩種頂點(diǎn)，使用不同的計(jì)算公式。

1、1-ring參數(shù)化方法

對(duì)于網(wǎng)格曲面上的任意點(diǎn)s，根據(jù)s點(diǎn)位于網(wǎng)格三角面片的位置可分為三角面片內(nèi)點(diǎn)、邊點(diǎn)、頂點(diǎn)三種情況：

①s為三角面片T0內(nèi)的點(diǎn)，如圖?s1點(diǎn)，此時(shí)只需以T0作為參數(shù)化平面，以s點(diǎn)為原點(diǎn)，即可求取T0三個(gè)頂點(diǎn)的極坐標(biāo)

②s位于網(wǎng)格邊上E0，如圖s2點(diǎn)，此時(shí)只需以E0作為鉸鏈，固定其中的一個(gè)平面，以E0作為鉸鏈，把另一個(gè)鄰接三角面片旋轉(zhuǎn)到同一個(gè)平面上，

③s為網(wǎng)格曲面的頂點(diǎn)，使用:《Free-form?shape?design?using?triangulated?surfaces》提出的極坐標(biāo)映射：即保證s點(diǎn)鄰接邊的長(zhǎng)度不變，鄰接角度為的縮放比例為，其中θi為頂點(diǎn)的鄰接角，即對(duì)于s點(diǎn)鄰接頂點(diǎn)的局部參數(shù)化滿足：

其中v和w為s點(diǎn)的鄰接頂點(diǎn)，根據(jù)公式可對(duì)s點(diǎn)的鄰接三角面片作局部展平參數(shù)化。

?

?2、k-ring參數(shù)化

如圖所示，設(shè)網(wǎng)格曲面上有4點(diǎn)，分別為s、vi、vj、vk，s點(diǎn)為源點(diǎn)，vi、vj、vk為同一個(gè)三角面片的三個(gè)頂點(diǎn)，且vi測(cè)地極坐標(biāo)未知，vj、vk為極坐標(biāo)已知的點(diǎn)，分別為(Rj,θj)、(Rk,θk)，目標(biāo)是求取vi的極坐標(biāo)，即vi在參數(shù)空間Tp上的映射點(diǎn)。

測(cè)地極坐標(biāo)參數(shù)化方法的基本思想是：以vi'(0,0)為原點(diǎn)，對(duì)vi的一環(huán)鄰域點(diǎn)作局部參數(shù)化，接著分別以vk'、vj'為圓點(diǎn)，以Rk、Rj為半徑作圓，則可以獲得兩圓的交點(diǎn)s'。以s'作為偽源點(diǎn)，通過(guò)該偽源點(diǎn)計(jì)算vi的極坐標(biāo)。

設(shè)ek=vk'-vi'，ej=vj'-vi'，ekj=vk'-vj'，則偽源點(diǎn)s'可以表示為：

s'=xjej+xkek

式中，

，

根據(jù)(8)式可計(jì)算s'在vi局部參數(shù)空間的坐標(biāo)。由此可得vi映射至Tp的極徑：

極角計(jì)算公式：

θi=(1-α)θj+αθk

式中，α=?ij/?kj，?kj是向量vk's'與向量vj's'之間的夾角，?ij是向量vi's'與向量vj's'之間的夾角。

測(cè)地極坐標(biāo)方法：首先對(duì)源點(diǎn)的一環(huán)鄰域點(diǎn)作局部參數(shù)化，接著用極徑作為Dijkstra算法往外擴(kuò)散的依據(jù)。Dijkstra算法擴(kuò)散過(guò)程中，用公式(9)(10)不斷更新活動(dòng)頂點(diǎn)的極坐標(biāo)。

三、算法實(shí)現(xiàn)

下面是paper中的偽代碼：

[cpp]?view plaincopy

<span?style="font-size:18px;">Algorithm?1:?Pseudo?code?for?computing?DGPC?on?a?mesh??

1:?for?i?=?1,?·?·?·?,n?do??

2:?U[i]?=∞??

3:?end?for??

4:?initializeNeighbourhood(s)??

5:?candidates.push(?neighbourhood(?s?)?)??

6:?while?candidates.notEmpty()?do??

7:?j?=?candidates.getSmallestNode()??

8:?for?i?∈?neighbours(j)?do??

9:?newUi?=?computeDistance(i)??

10:?if?U[i]?/?newUi?>?1?+?eps?then??

11:?U[i]?=?newUi??

12:?theta[i]?=?computeAngle(i)??

13:?if?newUi?<?Umax?then??

14:?candidates.push(i)??

15:?end?if??

16:?end?if??

17:?end?for??

18:?end?while</span>??

參考文獻(xiàn)：

1、《Differential?coordinates?for?interactive?mesh?editing》

2、《Interactive?decal?compositing?with?discrete?exponential?maps》

3、《Part-based?representation?and?editing?of?3D?surface?models》

4、《Geodesic?polar?coordinates?on?polygonal》

**********************作者：hjimce ? 時(shí)間：2015.5.10 ?聯(lián)系QQ：1393852684 ? 地址：http://blog.csdn.net/hjimce?原創(chuàng)文章，版權(quán)所有，轉(zhuǎn)載請(qǐng)保留本行信息********************

總結(jié)

以上是生活随笔為你收集整理的图形处理（十）测地极坐标参数化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。