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

何科雨，陳中貴

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

何科雨，陳中貴

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

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

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

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

1 相關工作

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

1.1 圓堆砌

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

1.2 紋理生成

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

1.2.1 基于實例的紋理生成方法

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

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

1.2.2 過程化的紋理生成方法

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

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

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

2 圓堆砌問題的求解

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

2.1 問題描述

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

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

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

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

其中，為1指向的單位方向向量；和1和分別為2個圓圓心坐標；與1分別為2個圓半徑。

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

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

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

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

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

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

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

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

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

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

3.1 二維平面的圓堆砌

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

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

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

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

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

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

算法1.圓堆砌算法。

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

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

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

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

步驟3.固定邊界；

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

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

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

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

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

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

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

步驟4.翻邊以維持Delaunay結構。

算法3.插入圓算法。

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

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

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

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

步驟3.設置初始位置；

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

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

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

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

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

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個閉合多邊形構成，內(nèi)部的閉合多邊形為孔洞，圖9(b)為將初始網(wǎng)格重新網(wǎng)格化后的結果，利用算法2對圖9(b)網(wǎng)格中的每一個非邊界頂點進行優(yōu)化后就得到了圖9(c)，圖9(d)展示了在空白部分插入圓(紅色)后得到的結果，圖9(e)展示了部分凹結構的細節(jié)。

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

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

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

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

3.3 二維平面的紋理生成

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

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

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

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

4 結果與比較

4.1 二維圓堆砌紋理

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

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

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

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

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

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

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

4.3 方法比較

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

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

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

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

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

4.4 運行時間

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

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

表2 球堆砌運行時間及三角網(wǎng)格頂點

5 結束語

本文提出的基于圓堆砌的紋理生成方法簡單、魯棒、速度快，能夠處理二維凹多邊形，具有較強的實用性，同時對于光滑的三維網(wǎng)格模型也能得到比較好的結果。但本文方法也有一定的局限性，不能很好地保持三維網(wǎng)格模型的尖銳特征，如圖17(d)中兔子的耳朵部分，在生成紋理的種類上也存在較大的限制。圓堆砌問題是一個很經(jī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

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

何科雨(1998-)，男，碩士研究生。主要研究方向為計算機圖形學。E-mail：1205486810@qq.com

陳中貴(1982-)，男，教授，博士。主要研究方向為計算機圖形學、幾何造型與處理、計算機輔助設計等。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