黃 茹，李亞娟，鄧重陽

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

1827 年，M?BIUS[1]首次提出2D 重心坐標(biāo)的概念：平面三角形內(nèi)任意一點(diǎn)可由三角形的頂點(diǎn)線性表示，該線性組合的系數(shù)就是三角形內(nèi)該點(diǎn)的重心坐標(biāo)。1975 年，WACHSPRESS[2]首次提出多邊形頂點(diǎn)數(shù)量大于 3 的重心坐標(biāo)(wachspress coordinates，WC)，但該重心坐標(biāo)僅對凸多邊形有明確的定義。2003 年，F(xiàn)LOATER[3]提出2D 的均值坐標(biāo)(mean value coordinates，MVC)，該坐標(biāo)對任意多邊形有明確的定義，且在多邊形內(nèi)部光滑。2005 年，F(xiàn)LOATER 等[4]提出3D 的均值坐標(biāo)，該坐標(biāo)可表示四面體內(nèi)部的一點(diǎn)關(guān)于四面體頂點(diǎn)的凸組合。2006 年，LANGER 等[5]提出球重心坐標(biāo)(spherical barycentric coordinates)，在球體上定義平面重心坐標(biāo)系中的任意重心坐標(biāo)，并給出球體上一點(diǎn)相對于給定球面三角形頂點(diǎn)的重心坐標(biāo)。2007 年，JOSHI 等[6]利用調(diào)和坐標(biāo)(harmonic coordinates，HC)，將重心坐標(biāo)的定義擴(kuò)展到任意維度，且即使在強(qiáng)凹的情況下重心坐標(biāo)仍然具有非負(fù)性。調(diào)和坐標(biāo)沒有具體的表達(dá)式，而是通過求解Laplace方程得到。2008 年，HORMANN 和SUKUMAR[7]提出最大熵坐標(biāo)(maximum entropy coordinates，MEC)，通過牛頓法求解凸優(yōu)化問題計算得到。最大熵坐標(biāo)可應(yīng)用于平面內(nèi)任意多邊形，且具有非負(fù)性。2008 年，LIPMAN 等[8]提出格林坐標(biāo)(Green coordinates，GC)，利用cage 的頂點(diǎn)與面的法向信息，通過格林第三等式推導(dǎo)得到，在空間變形中具有良好的保形性。2011 年，MANSON 等[9]提出正Gordon-Wixom 坐標(biāo)(positive Gordon-Wixom coordinates，PGWC)，在任意多邊形內(nèi)具有非負(fù)性，但其光滑性會受到多邊形邊界光滑性的限制。2014 年，ZHANG 等[10]提出局部重心坐標(biāo)(local barycentric coordinates，LBC)。LBC僅依賴于一部分控制頂點(diǎn)，且通過基于全變分的凸約束優(yōu)化計算得到。2016 年，ANISIMOV 等[11]提出細(xì)分重心坐標(biāo)(subdividing barycentric coordinates，SBC)，將被廣泛使用于構(gòu)造曲面的細(xì)分算法應(yīng)用于構(gòu)造重心坐標(biāo)。2017 年，ANISIMOV等[12]利用混合重心坐標(biāo)(blended barycentric coordinates，BBC)，對任意多邊形先進(jìn)行約束Delaunay 三角剖分，在剖分得到的三角形上計算均值坐標(biāo)，再通過合適的混合函數(shù)計算得到。2019，TAO 等[13]提出新的數(shù)值計算方法計算局部坐標(biāo)，與之前的局部坐標(biāo)[10]相比提高了計算效率，但未滿足非負(fù)性。2020 年，DENG 等[14]提出迭代坐標(biāo)(iterative coordinates，IC)，將初始多邊形投影至單位圓，并通過迭代圓上的多邊形，直至計算均值心坐標(biāo)為非負(fù)，最后通過回代得到關(guān)于初始多邊形的重心坐標(biāo)。

本文在三角網(wǎng)格的內(nèi)部將三角形衍生得到點(diǎn)多邊形、邊多邊形和面多邊形，提出基于衍生多邊形的混合坐標(biāo)，繼承了HC，LBC 和IC 的局部性和非負(fù)性，通過實(shí)例還表明在多邊形內(nèi)部光滑。

1 衍生多邊形

1.1 點(diǎn)多邊形

圖1 點(diǎn)多邊形示意圖((a)邊界點(diǎn)的點(diǎn)多邊形；(b)內(nèi)部點(diǎn)的點(diǎn)多邊形) Fig.1 Diagram of the point polygon ((a) The point polygon of the boundary point;(b) The point polygon of the inner point)

1.2 邊多邊形

1.3 面多邊形

圖2 邊多邊形示意圖((a)邊界邊的邊多邊形；(b)內(nèi)部邊的邊多邊形) Fig.2 Diagram of the edge polygon ((a) The edge polygon of the boundary edge;(b) The edge polygon of the inner edge)

2 基于衍生多邊形的混合坐標(biāo)算法

HC，LBC 和IC 均滿足上述性質(zhì)，本文提出的基于衍生多邊形的混合坐標(biāo)繼承了其局部性和非負(fù)性，并且在選取合適的混合系數(shù)后還滿足光滑性。

2.1 混合系數(shù)的選取

2.2 基于衍生多邊形的混合坐標(biāo)

3 實(shí)例分析

由文獻(xiàn)[6,10,14]可知HC，LBC 和IC 滿足非負(fù)性，則Ak和均滿足非負(fù)性，故Bk也滿足非負(fù)性。又因?yàn)榛旌舷禂?shù)為非負(fù)的，因此由式(4)可知基于衍生多邊形的混合坐標(biāo)具有非負(fù)性。

因?yàn)檠苌佣噙呅蔚捻旤c(diǎn)關(guān)于初始多邊形的重心坐標(biāo)僅與部分初始多邊形的頂點(diǎn)相關(guān)，即存在λi=0。又因?yàn)辄c(diǎn)p關(guān)于衍生子多邊形頂點(diǎn)的重心坐標(biāo)僅與部分衍生子多邊形的頂點(diǎn)相關(guān)，即存在可知點(diǎn)p通過第k個衍生子多邊形得到關(guān)于初始多邊形的初始混合坐標(biāo)具有局部性，故基于衍生多邊形的混合坐標(biāo)具有局部性。

圖3 比較了同一多邊形的同一頂點(diǎn)處不同重心坐標(biāo)的等高線與偽彩圖，其中圖3(d)～(f)分別為使用IC，HC 和LBC 計算衍生多邊形的頂點(diǎn)關(guān)于初始多邊形頂點(diǎn)的重心坐標(biāo)，再使用IC 計算點(diǎn)關(guān)于衍生多邊形頂點(diǎn)的重心坐標(biāo)。如圖3 所示，與均值坐標(biāo)、迭代坐標(biāo)、調(diào)和坐標(biāo)相比，基于衍生多邊形的混合坐標(biāo)具有更好的光滑性。

圖3 不同重心坐標(biāo)的等高線與偽彩圖((a)均值坐標(biāo)；(b)迭代坐標(biāo)；(c)調(diào)和坐標(biāo)；(d) IC_IC 混合坐標(biāo)；(e) HC_IC 混合坐標(biāo)；(f) LBC_IC 混合坐標(biāo)) Fig.3 Iso-high lines and pseudo-color drawings of different center of gravity coordinates ((a) Mean value coordinates; (b) Iterative coordinates;(c) Harmonic coordinates;(d) IC_IC Blended coordinates; (e) HC_IC Blended coordinates;(f) LBC_IC Blended coordinates)

圖4(a)～(f)分別展示了六邊形、七邊形、八邊形、九邊形、十邊形和Woody 的同一頂點(diǎn)處的等高線與偽彩圖。圖4 中從上到下分別使用IC，HC 和LBC計算衍生多邊形的頂點(diǎn)關(guān)于初始多邊形頂點(diǎn)的重心坐標(biāo)，再使用IC 計算點(diǎn)關(guān)于衍生多邊形頂點(diǎn)的重心坐標(biāo)，繪制對同一個多邊形的同一頂點(diǎn)的等高線與偽彩圖，并將其簡稱為 IC_IC，HC_IC，LBC_IC。其中IC_IC，HC_IC 使用MATLAB 的PDE工具箱進(jìn)行三角化，LBC_IC 使用LBC 使用的Triangle 進(jìn)行三角化。

圖4 不同多邊形的等高線與偽彩圖((a)六邊形；(b)七邊形；(c)八邊形；(d)九邊形；(e)十邊形；(f) Woody) Fig.4 Iso-high lines and pseudo-color drawings of different polygons ((a) Hexagon;(b) Heptagon;(c) Octagon; (d) Enneagon;(e) Decagon;(f) Woody)

將同一多邊形的初始化三角形網(wǎng)格的數(shù)量取相近數(shù)量，每個面取100 個采樣點(diǎn)，最終計算這些采樣點(diǎn)的時間，見表1。實(shí)例表明本文提出的基于衍生多邊形的混合坐標(biāo)具有好的局部性、非負(fù)性和光滑性。由圖4(a)～(d)可觀察到LBC_IC 的局部性比HC_IC 和IC_IC 的更好，對于相同的點(diǎn)處的等高線LBC_IC 顯然與更少的頂點(diǎn)相關(guān)。由圖4(c)～(f)可觀察到HC_IC 的光滑性比LBC_IC，IC_IC 的更好。由表1 可觀察到IC_IC 的計算時間最短。

表1 不同多邊形的計算坐標(biāo)的時間(s) Table 1 The time of calculate barycentric coordinates for different polygons (s)

4 結(jié)束語

本文首先給出衍生多邊形的定義，利用三角網(wǎng)格定義點(diǎn)多邊形、邊多邊形和面多邊形?；谘苌噙呅卫肏C，LBC 和IC 計算點(diǎn)關(guān)于初始多邊形的初始混合坐標(biāo)。再使用合適的混合系數(shù)，得到基于衍生多邊形的混合坐標(biāo)。其中，點(diǎn)多邊形PP?對應(yīng)的混合系數(shù)為邊多邊形EP?對應(yīng)的混合系數(shù)為(λ0+λ1)2，(λ1+λ2)2，(λ2+λ0)2；面多邊形EP?對應(yīng)的混合系數(shù)為

因?yàn)檠苌噙呅蔚慕Y(jié)構(gòu)簡單且可經(jīng)過少許迭代次數(shù)便可使均值重心坐標(biāo)為正，因此對于相同的多邊形，基于衍生多邊形的混合坐標(biāo)在計算過程中需要迭代的次數(shù)少于IC，減少了計算量。今后工作的重點(diǎn)是將二維的基于衍生多邊形的混合坐標(biāo)推廣到三維，并尋找更合適的混合系數(shù)，使得在不改變光滑性的前提下達(dá)到更高的連續(xù)性。