何科雨，陳中貴

基于圓堆砌的紋理生成方法

何科雨，陳中貴

(廈門大學(xué)信息學(xué)院，福建 廈門 361005)

人造的裝飾性紋理在人們的生活中得到了廣泛地應(yīng)用。傳統(tǒng)的基于實(shí)例的紋理生成方法首先會(huì)在目標(biāo)區(qū)域放置一些很小的圖元，然后通過迭代的方式讓這些圖元增長，最后填充整個(gè)目標(biāo)區(qū)域。在迭代的過程中相鄰的圖元之間會(huì)發(fā)生交叉與覆蓋，因此需要對圖元做變形、裁剪或其他處理，然而這種處理方式往往會(huì)花費(fèi)大量的時(shí)間?；谶^程化的方法通過設(shè)計(jì)很多結(jié)構(gòu)復(fù)雜的規(guī)則，在二維平面生成具有豐富層次的紋理，但這種方法比較難拓展到三維空間。本文提出了一種基于圓堆砌的紋理生成方法，可以生成二維或三維的紋理。圓堆砌問題屬于NP-hard問題，本文將該問題轉(zhuǎn)換成一個(gè)最優(yōu)化問題，從而能夠快速近似求解，求解出圓堆砌后就可以在圓上定義規(guī)則來對圓形進(jìn)行填充或替換以生成紋理。由于采用的是設(shè)計(jì)規(guī)則的方式生成紋理，該方法可以避免圖元之間發(fā)生的交叉覆蓋的問題。

圓堆砌；球堆砌；非線性優(yōu)化；紋理生成；重新網(wǎng)格化

裝飾性的紋理是由大量簡單的基本圖元構(gòu)成的復(fù)雜圖案，在人們的日常生活中有廣泛地應(yīng)用，然而由人工手動(dòng)生成的紋理通常是費(fèi)時(shí)又費(fèi)力。目前的紋理生成方法主要分為2類：①基于實(shí)例的方法，實(shí)例是一些簡單的幾何圖元，其可以是圖片、幾條相交的曲線或多邊形等等，通常由用戶輸入，然后算法將這些實(shí)例填充到目標(biāo)表面，目標(biāo)表面可以是二維平面或三維網(wǎng)格表面。算法首先會(huì)在目標(biāo)表面進(jìn)行均勻采樣并在采樣的位置放置一個(gè)比較小的實(shí)例，然后采取各種方法讓這些實(shí)例不斷地增長，最后得到一個(gè)實(shí)例緊密填充的目標(biāo)表面。在實(shí)例增長的過程中相鄰的實(shí)例可能會(huì)發(fā)生交叉，因此就需要對相鄰實(shí)例做適當(dāng)?shù)淖冃?、裁剪等處理，有時(shí)為了讓實(shí)例填充更緊密又需要對實(shí)例進(jìn)行拉伸處理。然而現(xiàn)有的處理方法都非常費(fèi)時(shí)。②過程化的紋理生成方法，該方法在計(jì)算機(jī)發(fā)展的早期就得到了很多的關(guān)注。這種方法通過算法上的設(shè)計(jì)及少量參數(shù)就能夠生成帶有豐富層次的、復(fù)雜的紋理圖案，但設(shè)計(jì)過程的算法并不容易，參數(shù)的微小變化會(huì)對最終結(jié)果產(chǎn)生很大的影響。大多生成的紋理達(dá)不到人們的預(yù)期，由于生成這種紋理的算法結(jié)構(gòu)復(fù)雜，很難有通用的方法將其推廣到三維網(wǎng)格表面。本文提出一個(gè)基于圓堆砌的紋理生成方法，能夠克服上述方法的缺點(diǎn)。圓堆砌指用圓形盡可能對目標(biāo)區(qū)域進(jìn)行填充，目標(biāo)區(qū)域通常是二維平面中的閉合圖形。相鄰的圓形不能出現(xiàn)重疊，圓堆砌問題屬于NP-hard問題。因此本文采用了啟發(fā)式的方法，將圓與圓之間的幾何約束轉(zhuǎn)換成了數(shù)學(xué)形式，從而將圓堆砌問題轉(zhuǎn)化成一個(gè)最優(yōu)化問題，并利用最優(yōu)化庫進(jìn)行快速近似求解，使二維平面上的圓堆砌方法可以很容易拓展到三維網(wǎng)格表面。圓堆砌的最終結(jié)果通過三角網(wǎng)格的形式來表示。本文提出了基于圓堆砌生成紋理的方法，即圓堆砌的結(jié)果可作為一個(gè)框架用于生成紋理，并在圓中放置基本圖元，或根據(jù)圓與圓之間的幾何，拓?fù)涞汝P(guān)系定義各種規(guī)則來生成紋理。由于本文的方法不需要處理相鄰圖元之間的重疊問題，因此具有較高的時(shí)間效率。

1 相關(guān)工作

本文主要涉及到圓堆砌和紋理生成2個(gè)問題，下面將介紹這2方面的相關(guān)工作。

1.1 圓堆砌

圓堆砌指用不重疊的圓形對給定的目標(biāo)區(qū)域進(jìn)行填充，目標(biāo)區(qū)域通常是二維平面上的閉合圖形，根據(jù)圓的半徑是否相等來區(qū)分等圓堆砌和不等圓堆砌。SCHIFTNER等[1]通過對三角網(wǎng)格進(jìn)行優(yōu)化來得到一個(gè)等圓堆砌。本文主要關(guān)注不等圓填充，用非線性優(yōu)化庫來求解圓堆砌問題。盡可能對目標(biāo)區(qū)域進(jìn)行填充，因?yàn)楸疚淖罱K的目標(biāo)是在圓堆砌的基礎(chǔ)上生成紋理，所以對圓的半徑和數(shù)量沒有要求。

1.2 紋理生成

生成紋理的方法主要分為2大類，一類是基于實(shí)例的紋理生成方法，另一類是過程化的紋理生成方法。

1.2.1 基于實(shí)例的紋理生成方法

基于實(shí)例的紋理生成方法通常需要用戶提供一個(gè)實(shí)例，然后通過一系列方法將實(shí)例排列到目標(biāo)區(qū)域以獲得最終的紋理。實(shí)例可以是圖片、帶有拓?fù)溥B接關(guān)系的曲線、幾何圖形等等，根據(jù)不同的實(shí)例以及不同的目標(biāo)區(qū)域可選擇不同的方法。首先是WEI等[2]提出的基于像素圖片的方法，輸入一張比較小的紋理圖片，然后在給定目標(biāo)區(qū)域平面或三維網(wǎng)格表面生成更大范圍的紋理，該類方法通常都會(huì)用到塊匹配[3]算法。塊匹配算法能夠快速找到圖像塊之間的對應(yīng)關(guān)系，可以被用來對圖像紋理進(jìn)行拓展。DUMAS等[4]將基于實(shí)例的方法拓展到了三維空間且不再局限于對網(wǎng)格表面進(jìn)行著色，而是生成具有空間結(jié)構(gòu)的鏤空網(wǎng)格。其輸入是一張二值化的黑白紋理圖片，然后將紋理圖片緊密排布到三維網(wǎng)格表面，其中黑色的部分最終會(huì)生成孔洞，白色的部分會(huì)生成網(wǎng)格。ZHOU等[5]用具有網(wǎng)狀結(jié)構(gòu)的幾何元素替代了二值化的紋理圖片，可以生成類似編制物的紋理，并考慮到了相鄰幾何元素之間的拓?fù)溥B接關(guān)系而不是相鄰圖像塊之間像素的相似性。

SENDIK和COHEN-OR[6]和ZHOU等[7]通過深度學(xué)習(xí)的方法學(xué)習(xí)圖片紋理的深度特征，能夠?qū)⒁恍K紋理生成更大的紋理，傳統(tǒng)的基于塊匹配的方法無法生成一些具有全局結(jié)構(gòu)的紋理如樹樁，分形圖案等。另外一部分文獻(xiàn)是基于幾何元素排布的，如BARLA等[8]需要用戶輸入一個(gè)矢量化的圖案，然后分析圖案的結(jié)構(gòu)并進(jìn)行各個(gè)方向上的拓展；IJIRI等[9]采用了類似的方法，通過分析一個(gè)給定元素的分布與周圍元素的比較來生成新的元素；TU等[10]輸入一系列曲線和離散的點(diǎn)，其不僅考慮了元素的位置還考慮了元素與元素之間的拓?fù)溥B接；SAPUTRA等[11]在給定目標(biāo)區(qū)域生成了一個(gè)流線型向量場，其部分參數(shù)可以由用戶指定，然后通過對用戶輸入的實(shí)例圖元做一些變形來填充到目標(biāo)空間；HU等[12]通過排布各種形狀的閉合多邊形到目標(biāo)空區(qū)域，這些多邊形可以進(jìn)行縮放、平移、旋轉(zhuǎn)，但相鄰多邊形不能出現(xiàn)交叉，其將紋理生成的問題轉(zhuǎn)換成了一個(gè)多邊形的堆砌問題；CHEN 等[13-14]介紹了生成裝飾物紋理的方法，能夠自動(dòng)將一系列圖案元素緊密地排列到目標(biāo)區(qū)域，這種紋理生成方法將圖案元素的排布轉(zhuǎn)換成了一個(gè)關(guān)于堆砌的最優(yōu)化問題，并通過對圖案元素進(jìn)行增長，處理相鄰圖案重疊的部分以及后續(xù)的優(yōu)化來獲得最終的結(jié)果。本文參考了文獻(xiàn)[13]方法，但是不同的地方在于本文并不直接排布圖案元素，而是首先生成一個(gè)目標(biāo)區(qū)域的圓堆砌，然后在圓堆砌上生成紋理。ZEHNDER等[15]給用戶提供了一個(gè)能直接在網(wǎng)格表面操作的曲線網(wǎng)格工具，輸入是一些由曲線構(gòu)成的基本曲線圖案，即用戶可以自由地在網(wǎng)格表面放置預(yù)定義的曲線圖案，然后逐漸讓這些圖案進(jìn)行增長，不同圖案的曲線在增長過程中會(huì)出現(xiàn)碰撞，這時(shí)圖元會(huì)發(fā)生相應(yīng)的局部變形，用戶也能夠在網(wǎng)格模型表面對這些曲線進(jìn)行編輯；FANNI等[16]采用了體素化的方法，在目標(biāo)表面采樣后放置三角網(wǎng)格實(shí)例，然后對這些實(shí)例體素化后利用SETHIAN[17]的快速行進(jìn)算法讓實(shí)例增長并變形以填充目標(biāo)表面，該方法最終能夠生成與藝術(shù)家手工制作出的工藝品類似的結(jié)果。

1.2.2 過程化的紋理生成方法

相較于基于實(shí)例的方法，過程化的紋理生成方法更加復(fù)雜，生成的紋理會(huì)有更多的細(xì)節(jié)，但過程化的方法往往不直觀。參數(shù)變化會(huì)對最終結(jié)果產(chǎn)生非常大的影響。EBERT[18]介紹了很多過程化的建模的方法，主要利用各種噪聲函數(shù)進(jìn)行不同層次的疊加，通過很少量的代碼就能夠控制很復(fù)雜的紋理細(xì)節(jié)，該方法能夠?qū)淠镜募y路、石頭紋理、水面、煙霧等自然現(xiàn)象進(jìn)行模擬。SANTONI和PELLACINI[19]將文法作用于紋理生成，給用戶提供了3種不同的操作符用于處理紋理，可以對目標(biāo)區(qū)域做分割，填充不同的圖形以及對目標(biāo)區(qū)域進(jìn)行變形。不同operator的組合作用于目標(biāo)區(qū)域后就能夠得到各種不同的紋理圖案，該方法只能作用于二維平面，NAZZARO等[20]提出了一個(gè)在網(wǎng)格上快速計(jì)算測地距離的方法，將文獻(xiàn)[19]方法拓展到了三維網(wǎng)格上。LOI等[21]將文法的作用對象進(jìn)行了拓展，不再局限于對目標(biāo)區(qū)域的劃分，紋理中的點(diǎn)線面都可以被視為文法的作用對象。因此能生成結(jié)構(gòu)更加復(fù)雜的紋理。文獻(xiàn)[19]方法側(cè)重于對目標(biāo)區(qū)域的分割和填充，而文獻(xiàn)[21]方法側(cè)重于對具有規(guī)律的圖案進(jìn)行程序化的變形和替換。本文對圓形進(jìn)行替換生成紋理時(shí)采用了與文獻(xiàn)[21]類似的方法。

GUO等[22]提出了一個(gè)能根據(jù)圖片推測出L系統(tǒng)文法的方法，該首先根據(jù)預(yù)定義的基本圖元和L系統(tǒng)規(guī)則生成各種各樣的圖案，然后訓(xùn)練出一個(gè)能夠識別圖案中基本圖元的深度神經(jīng)網(wǎng)絡(luò)，最后利用啟發(fā)式算法推測出原有的L系統(tǒng)文法。WONG等[23]發(fā)現(xiàn)很多紋理圖案中具有豐富的S型曲線，而這種曲線可以通過相切的圓形得到，于是提出了一個(gè)可編程的過程化方法。其能夠生成類似植物的裝飾性紋，并定義了很多基于圓形的可編程的生長規(guī)則，生長規(guī)則作用在裝飾性元素并根據(jù)一系列限制條件決定生成元素的類型及位置。在每次迭代中試探性的選擇可能的、最大的位置來放置元素。最終生成一個(gè)填滿目標(biāo)區(qū)域的紋理圖案。

本文主要參考了文獻(xiàn)[12-13,23]的方法，首先利用非線性優(yōu)化快速得到一個(gè)目標(biāo)區(qū)域的圓堆砌，然后將圓堆砌的結(jié)果作為一個(gè)生成紋理的框架?？梢詷?gòu)造出S型曲線，也可以放置一些圓形的圖元。本文方法既可生成基于實(shí)例的紋理，也能夠生成過程化的紋理。

2 圓堆砌問題的求解

在介紹生成紋理之前，首先介紹本文對圓堆砌問題的求解過程。圓堆砌問題中有很多約束，本文方法將圓堆砌中的幾何約束轉(zhuǎn)換成不等式形式，并設(shè)置圓的初始位置及半徑，然后利用非線性優(yōu)化庫近似求解出滿足約束條件的最大的圓形。

2.1 問題描述

對于二維要在一個(gè)給定封閉區(qū)域內(nèi)做圓堆砌，該區(qū)域由閉合多邊形表示，圓與圓之間不能相交，圓與閉合多邊形的邊界也不能相交，在滿足這些約束的前提下盡可能用圓填充該區(qū)域。輸入閉合多邊形的頂點(diǎn)，輸出圓形的半徑以及二維坐標(biāo)。對于三維圓堆砌就變成了球堆砌，所以希望用球盡可能覆蓋網(wǎng)格表面，輸入是三角網(wǎng)格，輸出每一個(gè)球的半徑以及三維坐標(biāo)。

2.2 非線性優(yōu)化求解圓堆砌問題

非線性優(yōu)化是由一系列約束函數(shù)和一個(gè)目標(biāo)函數(shù)構(gòu)成的優(yōu)化問題。約束函數(shù)可以是等式約束也可以是不等式約束，該問題的目標(biāo)就是求解出滿足所有約束函數(shù)的目標(biāo)函數(shù)的最大值或最小值。非線性優(yōu)化問題通常為

其中，為目標(biāo)函數(shù)；為個(gè)最優(yōu)化參數(shù)，目標(biāo)函數(shù)在個(gè)參數(shù)下取得最大或最小值；fc()為不等式約束，其中=1,···,；h()為等式約束。非線性優(yōu)化問題是一個(gè)比較成熟的問題，目前已經(jīng)有很多用于求解這類問題的方法，本文采用Knitro[24]優(yōu)化庫來求解，并通過嘗試去求解一個(gè)局部或全局最優(yōu)解。在圓堆砌問題中主要有2種類型的約束，一種是圓形與圓形之間的約束，即2個(gè)圓之間不能相交；另一種是圓形與邊界的約束，即圓與邊界也不能相交，圓與圓之間的約束可以看做2個(gè)圓心之間的歐氏距離必須大于或等于2個(gè)圓形半徑之和，圓與邊界的約束則是圓心到邊線的距離必須大于或等于半徑，圖1給出約束的具體例子。圖1(a)展示了圓-圓約束，紅色圓是約束圓，黑色圓是目標(biāo)圓，數(shù)學(xué)不等式為

其中，為1指向的單位方向向量；和1和分別為2個(gè)圓圓心坐標(biāo)；與1分別為2個(gè)圓半徑。

圖1(b)展示了圓-邊界約束，紅色的邊為約束邊，數(shù)學(xué)形式為

其中，為指向的單位向量；為過圓心做垂直于邊的垂線的垂足。Knitro優(yōu)化庫采用基于梯度的優(yōu)化方法，因此還需要給出對應(yīng)約束函數(shù)的梯度。本文的問題一共有3個(gè)需要優(yōu)化的參數(shù)，分別是點(diǎn)的2個(gè)坐標(biāo)分量以及半徑，將約束函數(shù)對這3個(gè)變量求偏導(dǎo)，即

其中，n，n分別為向量的2個(gè)坐標(biāo)分量。三維情形下的約束與二維情形類似，依然是3個(gè)參數(shù)，點(diǎn)依然在一個(gè)平面進(jìn)行移動(dòng)，不同的地方在于從原來在二維平面移動(dòng)變成了在三維空間中的平面進(jìn)行移動(dòng)。首先通過每一個(gè)三角網(wǎng)格中的頂點(diǎn)計(jì)算出一個(gè)切平面，頂點(diǎn)只能夠在這個(gè)平面上進(jìn)行移動(dòng)，二維平面的點(diǎn)需要乘一個(gè)矩陣從二維平面變換到切平面上，即

其中，?為變換后的坐標(biāo)；為切平面上的一個(gè)點(diǎn)；為一個(gè)3×3的矩陣，其3個(gè)行向量分別對應(yīng)網(wǎng)格頂點(diǎn)所在平面的切向量，副切向量和法向量，即

三維情形對應(yīng)的約束函數(shù)的梯度表示為

設(shè)置約束后，還需要對優(yōu)化庫設(shè)置變量的初始值，即需要設(shè)置圓的初始位置以及半徑。由于優(yōu)化庫依賴梯度求解，因此不同的初始值最終會(huì)收斂于不同的局部最小值，即初始頂點(diǎn)位置的不同對最終算法得到的結(jié)果會(huì)有很大的影響，如圖2所示，其中圖2(a)紅色矩形與圓為約束，共有4條邊與一個(gè)圓約束，本文目標(biāo)是在滿足這幾個(gè)約束的條件下找到一個(gè)最大的圓。圖2(a)中放置了4個(gè)較小的初始圓，圖2(b)是利用優(yōu)化庫得到的結(jié)果，其中紫色的圓最大，是本文希望得到的結(jié)果?？梢钥闯鲆话闱闆r下優(yōu)化庫只能求解出一個(gè)局部最優(yōu)解，本文采取的策略是從這幾個(gè)局部最優(yōu)解中選擇最好的結(jié)果，即最大的那個(gè)圓。

圖2 不同初始位置得到的結(jié)果((a)初始化；(a)優(yōu)化結(jié)果)

3 基于圓堆砌的紋理生成方法

基于圓堆砌算法的紋理生成方法的核心思想是，基于實(shí)例在目標(biāo)區(qū)域放置基本圖元，并讓這些圖元進(jìn)行增長，然后對相鄰圖元產(chǎn)生重疊交叉的部分做優(yōu)化處理。而本文采用的思路是首先對目標(biāo)區(qū)域做圓堆砌以獲得一個(gè)放置圖元的框架，然后在生成的圓內(nèi)放置基本圖元或利用圓與圓之間的關(guān)系定義出各種規(guī)則并生成不同的紋理圖案。這樣做就回避了處理相鄰圖元的階段。圖3(a)為本文算法的總流程圖，對于二維平面，輸入是閉合多邊形，對于三維輸入則是三角網(wǎng)格，然后對輸入進(jìn)行重新網(wǎng)格化后執(zhí)行圓堆砌算法，最后生成紋理，圖3(b)為本文圓堆砌算法的流程圖。

圖3 算法概覽((a)算法總流程；(b)圓堆砌流程)

3.1 二維平面的圓堆砌

本文采用三角網(wǎng)格來表示圓堆砌，二維平面的目標(biāo)表面用閉合多邊形來表示且允許存在孔洞。首先利用CGAL庫的二維網(wǎng)格優(yōu)化方法[22-23]，根據(jù)目標(biāo)多邊形生成一個(gè)頂點(diǎn)分布均勻的三角網(wǎng)格={,,}，其中是三角形集合，是邊集合，是頂點(diǎn)集合，三角網(wǎng)格中的邊界以及內(nèi)部的孔洞都被視為邊界邊。除邊界上的頂點(diǎn)外，三角網(wǎng)格中的每一個(gè)頂點(diǎn)都表示一個(gè)圓，頂點(diǎn)的坐標(biāo)就是圓的圓心坐標(biāo)，每一個(gè)頂點(diǎn)都有一個(gè)屬性來表示圓的半徑。圓的初始半徑設(shè)為0，在計(jì)算出三角網(wǎng)格后利用算法2對三角網(wǎng)格中的每一個(gè)圓進(jìn)行優(yōu)化，本文采用逐頂點(diǎn)迭代優(yōu)化，對圓進(jìn)行增長需要設(shè)置相應(yīng)的約束，并選擇一環(huán)鄰域內(nèi)的頂點(diǎn)及邊界邊作為約束。如圖4所示，當(dāng)優(yōu)化頂點(diǎn)為時(shí)，頂點(diǎn)約束集合為={1,2,3,4,5,6}，邊約束集合為={1,2,3,4,5,6}，然后利用優(yōu)化庫求解出最大圓的位置以及半徑。在優(yōu)化結(jié)束后會(huì)存在一些空間未被圓填充，因此需要在這些區(qū)域插入圓形來讓目標(biāo)區(qū)域獲得一個(gè)更高的覆蓋率。但是本文在具體的實(shí)驗(yàn)過程中發(fā)現(xiàn)隨著插入的圓形半徑越來越小，Delaunay三角網(wǎng)格的質(zhì)量尤其是邊界部分網(wǎng)格質(zhì)量變得非常差，一環(huán)鄰域約束無法正確的約束圓的位置，導(dǎo)致無法繼續(xù)插入圓。圖5(a)展示了插入圓的結(jié)果，對于這個(gè)問題本文的解決方案是固定相切邊。當(dāng)一個(gè)圓形和一環(huán)鄰域內(nèi)的圓形相切或與某一個(gè)邊界相切時(shí)，可定義這條邊為相切邊，對于與邊界相切的圓可在圓與邊界相切的部分插入一個(gè)新的點(diǎn)以避免形成狹長的三角形。固定這條邊后即使以這條邊為公共邊的2個(gè)三角形不滿足Delaunay結(jié)構(gòu)也不執(zhí)行翻邊操作。執(zhí)行這一步后，三角網(wǎng)格不再保持Delaunay三角網(wǎng)格的性質(zhì)，但是從視覺上更加合理，如圖5(b)所示。圖5(a)中的三角網(wǎng)格維持Delaunay結(jié)構(gòu)且不處理邊界，存在很多穿過圓但不穿過圓心的邊，邊界網(wǎng)格的質(zhì)量變得非常差，圖5(b)固定了三角網(wǎng)格的部分邊，同時(shí)對邊界做了處理，當(dāng)某個(gè)圓與邊界相切時(shí)，就在相切的位置插入一個(gè)頂點(diǎn)。這樣就得到了比圖5(a)更加緊湊的結(jié)果。圖6展示了圖5(b)中圓堆砌的生成過程，初始網(wǎng)格為一個(gè)矩形，內(nèi)部有2個(gè)三角形，邊界邊固定，在圖中顯示為藍(lán)色，圖6(b)中放置了第一個(gè)圓形，如果不指定的話就會(huì)在矩形的正中央生成一個(gè)與矩形4條邊相切的圓形，圖6(c)插入了第一個(gè)圓形，新增的這個(gè)圓形與矩形的2條邊相切，在相切的位置增加了2個(gè)頂點(diǎn)并與新增的圓形有一條邊相連。

本文通過更進(jìn)一步的實(shí)驗(yàn)發(fā)現(xiàn)被固定的相切邊和三角網(wǎng)格中原有的邊界可以將三角網(wǎng)格分割成多個(gè)更小的多邊形，小多邊形邊界全部由相切邊或三角網(wǎng)格中原有邊界構(gòu)成，如圖7(a)所示，其中藍(lán)色的邊為相切邊，綠色的邊為非相切邊。只看相切邊，則原來的網(wǎng)格被分割成了2個(gè)較小的多邊形和一個(gè)三角形，由相切邊分割出來的多邊形相互獨(dú)立。因此插入圓就可以從原來在整個(gè)多邊形內(nèi)插入圓轉(zhuǎn)化成為在多個(gè)比較小的多邊形內(nèi)插入圓，并且新插入的圓與原有的圓形會(huì)產(chǎn)生新的相切邊，新的相切邊又能夠繼續(xù)對這些多邊形進(jìn)行分割。本文采用基于三角形的插入策略，對于三角網(wǎng)格中的每一個(gè)三角形，首先找到這個(gè)三角形所屬的多邊形的所有圓約束和邊界約束，如圖7(b)所示，其中邊界約束集合={1,2,3,4}，頂點(diǎn)約束集合={1,2,3,4}，插入圓不同于算法2優(yōu)化圓的大小，插入圓需要設(shè)置一個(gè)初始位置，在本文中初始位置一般設(shè)置為三角形的重心坐標(biāo)，如果三角形的重心在某個(gè)圓內(nèi)部，就將坐標(biāo)做一個(gè)偏移移動(dòng)到該圓的邊界上以保證初始位置不會(huì)被某個(gè)圓形覆蓋。然后利用優(yōu)化庫求解出基于當(dāng)前三角形的最大圓，并將這個(gè)圓定義為候選圓。如果一開始插入比較小的圓形，后面插入的圓就只會(huì)越來越小，這將不利于后面的紋理生成，為了避免最后插入的圓太小，所以希望每一次都能插入一個(gè)比較大的圓。因此需對每一個(gè)三角形都計(jì)算出一個(gè)候選圓，然后選擇最大的候選圓插入。新插入的圓會(huì)與原有的圓相切，形成新的相切邊，這些邊需要被固定，由于插入圓是在當(dāng)前三角形所屬的多邊形內(nèi)部進(jìn)行的，并不會(huì)對外部的多邊形產(chǎn)生任何影響。因此每一次插入圓都是一個(gè)局部優(yōu)化問題，并不需要再次重新計(jì)算每一個(gè)三角形的候選圓，只需要對閉合多邊形內(nèi)部的三角形進(jìn)行重新計(jì)算。

圖4 三角網(wǎng)格約束示例

圖5 不固定邊與固定邊的結(jié)果對比((a)不固定邊；(b)固定邊))

圖6 初始網(wǎng)格以及插入部分圓形的過程((a)初始網(wǎng)格；(b)放置一個(gè)初始的圓；(c)插入一個(gè)圓；(d)插入2個(gè)圓；(e)插入3個(gè)圓形；(f)最終結(jié)果)

圖7 分割多邊形示例((a)多邊形分割；(b)最小多邊形約束)

算法1.圓堆砌算法。

輸入：平面區(qū)域(由閉合多邊形表示Ω)，半徑閾值。

輸出：三角網(wǎng)格。

步驟1.在閉合多邊形上生成頂點(diǎn)均勻分布的Delaunay三角網(wǎng)格；

步驟2.用算法2對每一個(gè)圓進(jìn)行優(yōu)化；

步驟3.固定邊界；

步驟4.對于三角網(wǎng)格中的每一個(gè)三角形利用算法3計(jì)算出最大圓位置以及半徑并插入最大的一個(gè)圓，當(dāng)找到的最大圓半徑小于閾值時(shí)結(jié)束。

算法2.圓優(yōu)化算法。

輸入：三角網(wǎng)格和需要被優(yōu)化的圓形對應(yīng)的頂點(diǎn)。

輸出：優(yōu)化后的圓坐標(biāo)和半徑。

步驟1.找到頂點(diǎn)的一環(huán)鄰域的頂點(diǎn)以及一環(huán)鄰域邊界邊；

步驟2.將和寫成約束形式；

步驟3.利用優(yōu)化庫求解出優(yōu)化后圓形的半徑以及坐標(biāo)；

步驟4.翻邊以維持Delaunay結(jié)構(gòu)。

算法3.插入圓算法。

輸入：三角網(wǎng)格和的三角形。

輸出：優(yōu)化后的圓坐標(biāo)和半徑。

步驟1.找到三角形所屬的最小閉合多邊形的邊界集合以及頂點(diǎn)集合；

步驟2.將和寫成約束形式；

步驟3.設(shè)置初始位置；

步驟4.根據(jù)約束利用優(yōu)化庫求解出最大圓；

步驟5.固定新的相切邊。

在實(shí)際求解圓堆砌的過程中，目標(biāo)區(qū)域的邊界約束中往往存在內(nèi)部凹陷或孔洞結(jié)構(gòu)，如圖8(a)所示，考慮到本文的邊界約束，凹多邊形中邊界約束會(huì)壓縮實(shí)際的可行空間。圖中目標(biāo)區(qū)域是一個(gè)閉合的凹多邊形，一共有6個(gè)邊界約束，其中3，4這2條邊內(nèi)凹。在本文提出的邊界約束下整個(gè)目標(biāo)區(qū)域?qū)嶋H上會(huì)被劃分成3個(gè)更小的區(qū)域，如圖8(c)所示，在這種情況下只能生成3個(gè)較小的圓，不能有效利用多邊形的空間。本文的解決方法為，首先將邊界約束邊按照逆時(shí)針方向排列，如圖8(d)所示，箭頭表示該邊，然后依次計(jì)算每一條邊的方向向量結(jié)果，如果方向向量由屏幕外指向屏幕內(nèi)，則這2條邊屬于凹邊，對于凹邊的約束只需約束圓心的位置，即只保證圓心的位置不會(huì)穿過這個(gè)邊界約束，如圖8(b)所示，數(shù)學(xué)形式為

同時(shí)增加一個(gè)點(diǎn)約束，點(diǎn)約束可以看作半徑為0的圓約束，其圓心位于2條凹邊的交點(diǎn)，即圖8(e)中3，4這2條邊的交點(diǎn)1。通過設(shè)置約束后，就能夠在有凹結(jié)構(gòu)的目標(biāo)區(qū)域中求解出最大的圓，即圖8(e)中黑色的圓。

圖8 凹多邊形的處理((a)凹邊界約束；(b)不約束半徑的邊界約束；(c)不處理凹結(jié)構(gòu)；(d)找出凹結(jié)構(gòu)；(e)處理凹結(jié)構(gòu))

Fig. 8 Processing of concave polygons ((a) Concave boundary constraints; (b) Boundary constraints without radius constraints; (c) Without handling concave structures; (d) Finding concave structures; (e) Dealing with concave structures)

圖9展示了包含孔洞的閉合多邊形的圓堆砌過程。其中圖9(a)為初始網(wǎng)格，由2個(gè)閉合多邊形構(gòu)成，內(nèi)部的閉合多邊形為孔洞，圖9(b)為將初始網(wǎng)格重新網(wǎng)格化后的結(jié)果，利用算法2對圖9(b)網(wǎng)格中的每一個(gè)非邊界頂點(diǎn)進(jìn)行優(yōu)化后就得到了圖9(c)，圖9(d)展示了在空白部分插入圓(紅色)后得到的結(jié)果，圖9(e)展示了部分凹結(jié)構(gòu)的細(xì)節(jié)。

3.2 三維網(wǎng)格表面的球堆砌

球堆砌是對二維平面的圓堆砌的拓展，相較于二維的圓與圓的約束與圓與邊界約束，到了三維空間就變成了球與球的約束和球與邊界的約束，算法與二維平面的圓堆砌基本一致，在算法2圓優(yōu)化這一步需要為三角網(wǎng)格中每一個(gè)球計(jì)算一個(gè)切平面，將球心的坐標(biāo)限制在這個(gè)切面內(nèi)進(jìn)行優(yōu)化。一個(gè)平面可以通過一個(gè)法向量和一個(gè)三維空間中過平面的坐標(biāo)確定，坐標(biāo)即球心的坐標(biāo)，法向量由該球?qū)?yīng)網(wǎng)格頂點(diǎn)一環(huán)鄰域內(nèi)部三角形所在平面的法向量取平均值得到。算法3采用基于三角形的插入圓策略，被插入的圓只能限制在三角形所在平面內(nèi)進(jìn)行移動(dòng)。圖10給出了球堆砌的例子，首先輸入一個(gè)三角網(wǎng)格，然后對這個(gè)網(wǎng)格進(jìn)行重新網(wǎng)格化讓頂點(diǎn)均勻分布，使球堆砌的結(jié)果中球的分布較均勻，然后執(zhí)行球堆砌算法。圖10(b)和(c)展示了球堆砌的結(jié)果。

圖9 帶有孔洞的圓堆砌結(jié)果((a)初始網(wǎng)格；(b)重新網(wǎng)格化；(c)初始圓堆砌；(d)插入圓后的圓堆砌；(e)凹結(jié)構(gòu)細(xì)節(jié))

圖10 三維網(wǎng)格球堆砌上的幾何紋理生成((a)輸入網(wǎng)格；(b)重新網(wǎng)格化；(c)球堆砌；(d)生成紋理)

3.3 二維平面的紋理生成

在得到二維圓堆砌的結(jié)果后，就可按上述定義規(guī)則來生成紋理，本文主要參考了文獻(xiàn)[21,23]的方法，如圖11所示。在圓堆砌上生成紋理的規(guī)則如下，首先定義由2個(gè)圓構(gòu)成的圓對，圓對中的一個(gè)圓必須是另一個(gè)圓一環(huán)鄰域中的圓，且一個(gè)圓只能出現(xiàn)在一個(gè)圓對中。用貪心策略找到圓堆砌中的所有圓對，然后開始繪制，首先將所有的圓按一定比例縮小后繪制邊框，并在2個(gè)圓之間繪制一條線段，線的方向由2個(gè)圓的圓心坐標(biāo)決定，長度為2個(gè)圓的圓心距離減去其半徑。

圖11 二維紋理生成示例((a)圓堆砌結(jié)果；(b)紋理生成)

3.4 三維網(wǎng)格表面的紋理生成

三維網(wǎng)格表面的紋理生成與二維情形類似，圖10(d)展示了三維網(wǎng)格模型球堆砌后生成的紋理，之前已計(jì)算出了每一個(gè)球?qū)?yīng)三角網(wǎng)格中頂點(diǎn)的法向量，然后利用法向量和球生成圓環(huán)模型，其中圓環(huán)的朝向由法向量確定，圓環(huán)的半徑與圓心位置與球的半徑和球心位置一致。

4 結(jié)果與比較

4.1 二維圓堆砌紋理

本文方法能夠處理具有不規(guī)則形狀的圖形，圖12展示了幾個(gè)不規(guī)則形狀的圓堆砌結(jié)果，可以看出本文的方法對于不規(guī)則圖形具有魯棒性。圖13展示了本文二維圓堆砌紋理的結(jié)果，其中圖13(a)和(b)的紋理圖案在圖12(a)和(b)圓堆砌的基礎(chǔ)上得到，該圖案由3種基本的圖元組成，紅色的問號，黃色的感嘆號以及綠色的句號，本文利用這3種圖元來替代圖12(a)中圓堆砌中的圓。

首先本文采用用貪心算法找到圓堆砌中所有的圓對，圓對中2個(gè)圓形大小相當(dāng)?shù)膱A形會(huì)被問號圖元替代，大小差距較大的圓對則會(huì)被感嘆號替代，剩下的沒有被匹配到圓對中的圓形則會(huì)被用句號來替代。圖13(b)采用了另一種方法生成紋理，對于每一個(gè)圓，在以其圓周為軸，半徑長度為軸的非歐坐標(biāo)系中疊加不同頻率的正弦波就能夠得到不同的圖案。圖13(c)采用了圖片紋理來替換圓形，綠色的荷葉圖案與粉色的蓮花圖案，在進(jìn)行替換的過程為了讓生成的結(jié)果更加具有真實(shí)感，對每一個(gè)圓的位置做了一個(gè)比較小的偏移，最終生成的紋理產(chǎn)生重疊的效果，圖13(d)采用了另外一種思路，對三角網(wǎng)格中的三角形進(jìn)行替代，生成了類似花瓣的紋理。

圖12 不規(guī)則多邊形內(nèi)的圓堆砌((a) C字形；(b) I字形；(c)不規(guī)則形狀)

圖13 二維圓堆砌上的紋理生成((a)符號紋理；(b)星號紋理；(c)池塘紋理；(d)花朵紋理)

4.2 三維網(wǎng)格球堆砌紋理

圖14展示了本文三維網(wǎng)格球堆砌的結(jié)果，圖14(a)與圖14(b)均采用了雞蛋形狀的網(wǎng)格模型用于球堆砌，圖14(c)采用了圓環(huán)作為基礎(chǔ)網(wǎng)格。此外，本文對部分生成的紋理做了平滑處理，圖14(d)所采用的具有S形狀以及螺旋形狀的紋理是定義在圓上的，因此將紋理放在三維球的切平面上，而在三維空間中相鄰球的切平面往往是不相交，2個(gè)相鄰的球的連接處只有一個(gè)切點(diǎn)，因此本文采用樣條線的方式來進(jìn)行連接，從而得到一個(gè)平滑的過渡效果，從圖14的結(jié)果中可以看出，本文，方法在光滑的網(wǎng)格表面有比較好的表現(xiàn)。

圖14 三維網(wǎng)格上球堆砌導(dǎo)出的紋理((a)雞蛋1；(b)水管；(c)圓環(huán)；(d)雞蛋2)

4.3 方法比較

圖15和圖16展示了本文和文獻(xiàn)[19]在二維紋理上的比較，圖15展示了字母圖案填充紋理，本文方法能夠得到類似的結(jié)果，能夠獲得一個(gè)更加稠密的填充。圖15中字母a和c中的方形元素是對圓形替換后的結(jié)果，方形元素的對角線長度等于圓形的半徑。圖16展示了本文與文獻(xiàn)[19]方法在獅子圖案上生成的紋理，文獻(xiàn)[19]設(shè)計(jì)出了對各種圖案都通用的operator，其包括對圖案的分割、填充以及扭曲變形，通過對這些不同的operator進(jìn)行各種組合就可以生成很多不同的紋理圖案。本文首先對圖案進(jìn)行圓堆砌，然后對圓進(jìn)行分組并用不同的規(guī)則生成的圖案替代原有的圓形。從圖中可以看出，本文能夠很好地保持圖案中的一些尖銳特征，雖然采用了不同的方法，本文也能夠得到令人滿意的結(jié)果。

圖15 二維紋理結(jié)果對比((a)文獻(xiàn)[19]中的字母圖案填充；(b)本文的字母圖案填充)

圖16 二維獅子圖案紋理((a)文獻(xiàn)[19]中的獅子紋理；(b)本文的獅子紋理)

圖17展示了本文與文獻(xiàn)[13]方法的對比，用于生成紋理的基礎(chǔ)網(wǎng)格模型是一個(gè)球形，最終生成的是一個(gè)有鏤空結(jié)構(gòu)的花紋球體?？梢詮膱D17(a)中看出，球面的花紋全部由單一的圖元進(jìn)行拼接得到。為了獲得一個(gè)稠密的結(jié)果，文獻(xiàn)[13]算法需要進(jìn)行大量的迭代來對相鄰圖元進(jìn)行變形、裁剪。而本文方法是在考慮了相鄰球之間的連接關(guān)系后直接在球上生成紋理圖案，不需要對圖元做任何變形操作，因此在得到近似結(jié)果的前提下，本文方法在運(yùn)行時(shí)間上有比較大的優(yōu)勢。

圖17 三維紋理結(jié)果對比((a)文獻(xiàn)[13]中的球形紋理；(b)本文的球形紋理；(c)文獻(xiàn)[13]中的兔子紋理；(d)本文的兔子紋理)

4.4 運(yùn)行時(shí)間

本文方法絕大部分時(shí)間用于計(jì)算圓堆砌和球堆砌，表1和表2給出了本文所有案例圓堆砌與球堆砌的運(yùn)行時(shí)間以及對應(yīng)的三角網(wǎng)格的頂點(diǎn)數(shù)量。本文所使用的電腦配置為Intel i7-7000 CPU，8GB RAM。文獻(xiàn)[13]方法在圖17(a)和圖17(c)中的紋理分別用時(shí)1 428 s，816 s。而本文的方法在圖17(b)和圖17(d)分別用時(shí)4.74 s和61.189 s。

表1 圓堆砌運(yùn)行時(shí)間及三角網(wǎng)格頂點(diǎn)數(shù)量

表2 球堆砌運(yùn)行時(shí)間及三角網(wǎng)格頂點(diǎn)

5 結(jié)束語

本文提出的基于圓堆砌的紋理生成方法簡單、魯棒、速度快，能夠處理二維凹多邊形，具有較強(qiáng)的實(shí)用性，同時(shí)對于光滑的三維網(wǎng)格模型也能得到比較好的結(jié)果。但本文方法也有一定的局限性，不能很好地保持三維網(wǎng)格模型的尖銳特征，如圖17(d)中兔子的耳朵部分，在生成紋理的種類上也存在較大的限制。圓堆砌問題是一個(gè)很經(jīng)典的問題，在很多領(lǐng)域都有廣泛地應(yīng)用，本文主要將圓堆砌用于紋理生成，對于圓堆砌在其他領(lǐng)域的應(yīng)用未來將展開更多研究。

[1] SCHIFTNER A, H?BINGER M, WALLNER J, et al. Packing circles and spheres on surfaces[C]//ACM SIGGRAPH Asia 2009 Papers on - SIGGRAPH Asia '09. New York: ACM Press, 2009: 1-8.

[2] WEI L Y, LEFEBVRE S, KWATRA V, et al. State of the art in example-based texture synthesis[C]//Eurographics 2009, State of the Art Report, EG-STAR. Eindhoven: Eurographics Association, 2009: 93-117.

[3] BARNES C, SHECHTMAN E, GOLDMAN D B, et al. The generalized PatchMatch correspondence algorithm[C]// Computer vision - ECCV 2010. Berlin: Springer, 2010: 29-43.

[4] DUMAS J, LU A, LEFEBVRE S, et al. By-example synthesis of structurally sound patterns[J]. ACM Transactions on Graphics, 2015, 34(4): 137.

[5] ZHOU K, HUANG X, WANG X, et al. Mesh quilting for geometric texture synthesis[C]//SIGGRAPH '06: ACM SIGGRAPH 2006 Papers. New York: ACM Press, 2006: 690-697.

[6] SENDIK O, COHEN-OR D. Deep correlations for texture synthesis[J]. ACM Transactions on Graphics, 2017, 36(5): 161.

[7] ZHOU Y, ZHU Z, BAI X, et al. Non-stationary texture synthesis by adversarial expansion[EB/OL]. [2022-05-20]. https://arxiv.org/abs/1805.04487.

[8] BARLA P, BRESLAV S, THOLLOT J, et al. Stroke pattern analysis and synthesis[J]. Computer Graphics Forum, 2006, 25(3): 663-671.

[9] IJIRI T, MêCH R, IGARASHI T, et al. An example-based procedural system for element arrangement[J]. Computer Graphics Forum, 2008, 27(2): 429-436.

[10] TU P H, WEI L Y, YATANI K, et al. Continuous curve textures[J]. ACM Transactions on Graphics, 2020, 39(6): 168.

[11] SAPUTRA R A, KAPLAN C S, ASENTE P, et al. FLOWPAK: flow-based ornamental element packing[C]//The 43rd Graphics Interface Conference. New York: ACM Press, 2017: 8-15.

[12] HU W C, CHEN Z G, PAN H, et al. Surface mosaic synthesis with irregular tiles[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 22(3): 1302-1313.

[13] CHEN W K, ZHANG X L, XIN S Q, et al. Synthesis of filigrees for digital fabrication[J]. ACM Transactions on Graphics, 2016, 35(4): 98.

[14] CHEN W K, MA Y X, LEFEBVRE S, et al. Fabricable tile decors[J]. ACM Transactions on Graphics, 2017, 36(6): 175.

[15] ZEHNDER J, COROS S, THOMASZEWSKI B. Designing structurally-sound ornamental curve networks[J]. ACM Transactions on Graphics, 2016, 35(4): 99.

[16] FANNI F A, PELLACINI F, SCATENI R, et al. PAVEL: decorative patterns with packed volumetric elements[EB/OL]. [2022-06-17]. https://arxiv.org/abs/2102.01029.

[17] SETHIAN J A. Fast marching methods[J]. SIAM Review, 1999, 41(2): 199-235.

[18] EBERT D S. Texturing & modeling: a procedural approach[M]. 3rd ed. Amsterdam: Morgan Kaufmann Publishers, 2003.

[19] SANTONI C, PELLACINI F. gTangle: a grammar for the procedural generation of tangle patterns[J]. ACM Transactions on Graphics, 2016, 35(6): 182.

[20] NAZZARO G, PUPPO E, PELLACINI F. geoTangle: interactive design of geodesic tangle patterns on surfaces[J]. ACM Transactions on Graphics, 2022, 41(2): 12.

[21] LOI H, HURTUT T, VERGNE R, et al. Programmable 2D arrangements for element texture design[J]. ACM Transactions on Graphics, 2017, 36(3): 27.

[22] GUO J W, JIANG H Y, BENES B, et al. Inverse procedural modeling of branching structures by inferring L-systems[J]. ACM Transactions on Graphics, 2020, 39(5): 155.

[23] WONG M T, ZONGKER D E, SALESIN D H. Computer- generated floral ornament[C]//The 25th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press, 1998: 423-434.

[24] BYRD R H, NOCEDAL J, WALTZ R A. Knitro: an integrated package for nonlinear optimization[M]//Nonconvex Optimization and Its Applications. Boston: Springer, 2006: 35-59.

Circle packing based texture generation

HE Ke-yu, CHEN Zhong-gui

(School of Informatics, Xiamen University, Xiamen Fujian 361005, China)

Artificial decorative textures are in wide use in our lives. The traditional case-based texture generation methods would first place some small primitives on the target area, then iteratively grow these primitives, and finally fill the entire target area. In the iteration process, there would be intersections and overlays between adjacent primitives, entailing the deforming, clipping, and other processing of primitives, which was usually time-consuming. Procedure-based methods can generate textures with rich layers in the two-dimensional plane by designing various rules with complex structures. However, such methods would be difficult to extend to the 3D space. This paper provided a texture generation method based on circle packing, thereby generating 2D or 3D textures. As an NP-hard problem, the circle packing problem could be converted into a nonlinear optimization problem, so that it could be quickly and approximately solved. With the problem solved, different rules could be defined to fill or replace the circle to generate textures. Since the texture is generated by rules, the proposed method could avoid intersections and overlays between primitives.

circle packing; sphere packing; non-linear optimization; texture generation; remeshing

TP 391

10.11996/JG.j.2095-302X.2022061114

A

2095-302X(2022)06-1114-10

2022-07-31；

：2022-10-25

國家自然科學(xué)基金(61972327)；福建省自然科學(xué)基金資助項(xiàng)目(2022J01001)

何科雨(1998-)，男，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)。E-mail：1205486810@qq.com

陳中貴(1982-)，男，教授，博士。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)、幾何造型與處理、計(jì)算機(jī)輔助設(shè)計(jì)等。E-mail：chenzhonggui@xmu.edu.cn

31 July，2022；

25 October，2022

National Natural Science Foundation of China (61972327); Natural Science Foundation of Fujian Province (2022J01001)

HE Ke-yu (1998-), master student. His main research interest covers computer graphics. E-mail：1205486810@qq.com

CHEN Zhong-gui (1982-), professor, Ph.D. His main research interests cover computer graphics, geometric modeling and processing, computer-aided design, etc. E-mail：chenzhonggui@xmu.edu.cn