多邊形網(wǎng)格上的流形曲面構(gòu)造技術(shù)研究

UniversityofScienceandTechnologyAdissertationformaster’sResearchonManifoldConstructionOverPolyhedralAuthor: ChunZhangSpeciality: ComputerGraphicsSupervisor: Prof.LigangLiuFinishedTime: May,2017摘摘基于任意多邊形網(wǎng)格的流形曲面構(gòu)造技術(shù)通過將輸入的網(wǎng)格劃分成若干個具有區(qū)域的標(biāo)卡（chart，并每個標(biāo)卡上別建立述該標(biāo)卡局（mdigunto）gfunction域共作，建于始格光曲。用項術(shù)成面及參數(shù)化；轉(zhuǎn)換函數(shù)（transitionfunction）的構(gòu)造；混合函數(shù)的構(gòu)造；形狀函數(shù)坐標(biāo)卡作不同的處理，內(nèi)部坐標(biāo)卡的處理方式與開網(wǎng)格上坐標(biāo)卡的處理方式相同，IManifoldconstructionoverpolyhedralmeshistobuildsmoothsurfacebydivid-inginputmeshintoseveralcollectionsofchartswithoverlapregions.Thenforeachindividualchart,aembeddingfunctionwhichrepresentslocalgeometryandblendingfunctionwhichrepresentstheimportanceoflocalgeometryonthefinalconstructedsurfacearebuilt.Finally,embeddingfunctionssharingthesameareblendedtogethertogetthefinalsurfacewhichapproximatestheinputmesh.Withsuchtechnol-ogy,generatedsurfacesalwayshavehighordersofsmoothnessandcanbeofarbitrarytopology.Asitisalocalconstructionmethod,itisefficientandhaswideapplicabilityonsurfacemodeling.Besides,thereisnoneedofextrapatchingortrimmingoperationswhichincreasecomputationalcostandresultinlowordersofsmoothnesscomparedwithtraditionalsurfaceconstructionmethods.Firstly,weintroducesometraditionalsurfaceconstructionandpointouttheircorrespondingadvantagesanddisadvantages.Then,manifoldconstructiontheoryispresented,andimportantfactorswhenconstructingsurfaceswiththismethodareshown,suchastheselectionandparameterizationofcharts,constructionoftransi-tionfunctions,constructionofblendingfunctionsandconstructionofembeddingfunc-tions.Wehavesurveyedgeometriccomputingresearchesinmanifoldconstructionanddividethemintothreecategoriesaccordingtothecharacteristicsofthesemethods:tra-ditionalmanifoldconstruction,canonicalsurfacesbasedconstruction,andmanifoldspline.Eachcategoryisintroducedindetail.However,themethodsofthefirstcategoryrequireinputmeshestohavespecialkindsofconnectivity,suchastrianglemesh,quadmeshandsoon.Otherwise,extrasubdivisionstepshouldbeapplied,whichwillincreasethenumberofchartstoalargetyandhenceincreasecomputationalcost.Asforthesecondandthirdcategories,aglobalparameterizationmustbeapplied,whichiscomplicatedinimplementation.Tosolvetheseproblem,weextendexistingmethodstomesheswitharbitraryconnectivityandproposeamoreeffectiveandconvenientmethodbytheuseofabivariatesplinefunctionwhichhascompactsupportandcandefineonanyshapeof2Dpolygon.Fornon-closedpolyhedralmesh,weapplyaglobalparameterizationanddirectlydivideitintoseveralcharts.Askillfultechnologyisappliedtobuildblendingfunctionforeachchart.Asforclosedpolyhedralmesh,weproposetosegmentthemeshintoasequenceofquadrilalpatcheswithoutanyoverlaps.Thenchartsarebuildforeachindividualpatchanddifferentprocessshouldbeappliedoninnerchartsandboundarycharts.Forinnercharts,theprocessisthesamewiththatofnon-closedpolyhedralmesh.Whileforboundarycharts,asetofspecialtransformationsareappliedtostichboundarychartstogether.Thus,allthepatchesaresmoothlystitchedandthefinalconstructedsurfacecanalsoachieveanyrequiredsmoothness.Finally,wemakeaconclusiononboththeexistingmanifoldconstructionmethodsandourproposedmethod.Besides,wealsopointoutsomefutureworksofmanifold:manifoldconstruction,arbitrarytopology,smoothness,arbitrarydral摘摘要I目錄V第一章緒論1流形的定義 2流形曲面構(gòu)造方法簡介 3流形曲面構(gòu)造中的重要因素 31.3.1坐標(biāo)卡的選取以及參數(shù)化 31.3.2轉(zhuǎn)換函數(shù)的構(gòu)造···········································41.3.3混合函數(shù)的構(gòu)造···········································41.3.4形狀函數(shù)的構(gòu)造···········································51.4·········································6·····································72.1···································72.1.1·············································72.1.2矩形參數(shù)域···············································92.1.3圓形參數(shù)域···············································2.2·································2.2.1·······························2.2.2Voronoi細(xì)分區(qū)域建立坐標(biāo)卡······························2.3·····························2.3.11-·······························2.4·······················································第三章任意多邊形網(wǎng)格上的流形曲面構(gòu)造方················3.2·····································3.1···················································目第第四章總結(jié)與展望4.1總結(jié)4.2展望參考文獻(xiàn)致謝在讀期間的學(xué)與取得的研究成果四邊形3.3.2流形的定義[1] 兩種形式的混合函數(shù) 卡[2] 邊坐標(biāo)卡與頂點坐標(biāo)卡之間轉(zhuǎn)換函數(shù)的構(gòu)造：ΨF1E為邊坐標(biāo)卡到面坐標(biāo)卡的轉(zhuǎn)換函數(shù)；ΨF1V為面坐標(biāo)卡到頂點坐標(biāo)卡的轉(zhuǎn)換函數(shù)[2] 左圖：坐標(biāo)卡的參數(shù)化過程，其中，Li是分段雙線性映射，ci的構(gòu)造見右圖；右圖：ci是建立在規(guī)則星形上的每塊菱形上的，是一個線性函數(shù)和Z4/ki的組合[3] (a)原始網(wǎng)格特征用紅色線條畫出（b創(chuàng)建的流形曲面（- 參數(shù)域上幾個坐標(biāo)卡的示例[4] 幾個基于面定義的坐標(biāo)卡和基于點定義的坐標(biāo)卡[5] k階連續(xù)星平面上的兩個坐標(biāo)卡（陰影區(qū)域）[6] CiCi和Ci是邊坐標(biāo)卡；Ci和 ?i 不與任何坐標(biāo)卡的區(qū)域；圖中粗線為Cs連續(xù)的光滑曲線[7]。應(yīng)[7] 的環(huán)面，帶標(biāo)記的頂點對應(yīng)左圖的頂點[8] 卡[8] 參數(shù)化到多邊形上；(f重建出來的光滑曲面，不同的顏色代表不同的坐標(biāo)卡的中心區(qū)域[9] 將規(guī)范區(qū)域（球面、多邊形）上的坐標(biāo)卡映射到平面；MW通過旋轉(zhuǎn)、伸縮變換將平面上的指定區(qū)域映射到圓上[9] 流形樣條創(chuàng)建時的關(guān)鍵因素：M為任意拓?fù)浣Y(jié)構(gòu)的三角形網(wǎng)格，F(xiàn)為流形樣條曲面，中間兩行是兩個有區(qū)域的樣條曲面片(?α(Uα),Cα,Fα)、(?β(Uβ),Cβ,Fβ)二者對應(yīng)的坐標(biāo)卡之間的轉(zhuǎn)換函數(shù)為仿射變換?αβ。Z為奇異點周圍的區(qū)域[10] 構(gòu)建高虧格網(wǎng)格與多面體的一一對應(yīng)關(guān)系[12] (b)去除頂點后的流形定義域；(c)去除頂點后創(chuàng)建的T樣條曲面(d)奇異點附近填補(bǔ)后的完整曲面[12] 利用離散Ricci流誘導(dǎo)出網(wǎng)格的仿射結(jié)構(gòu)[13] B(n)(u,v)定義在相同多邊形上、不同參數(shù)值下的顏 卡的示例:以紅色頂點為中心、綠色面為1鄰域 建立在不同坐標(biāo)卡上的混合函數(shù)B(n)(u,v)的 ，其中3, 0.05[?1,1]×[?1,1]坐標(biāo)卡的邊界，內(nèi)部的黑色多邊形為目標(biāo)多邊形 目標(biāo)多邊形的創(chuàng)建（vi上的坐標(biāo)卡采用線性變換isi(x?vi)將坐標(biāo)卡的參數(shù)域邊界歸一化到[?1,1]×[?1,1]上，得到多邊形(P1,P2,,P5)，然后將此多邊形的每條邊√向內(nèi)部移動 2nδsin(45?+θi)的距離，得到目標(biāo)多邊(Q1Q2Q5)，其中，θi為PiPi+1與x軸之間的最小夾角（b）多邊形(P1,P2,P3,P4)為歸一化后的坐標(biāo)卡的參數(shù)域邊界，綠色√

2nδ的距離得到新的多邊形(P1,P2,P3,P4) （c）Catmull- 基于任意多邊形網(wǎng)格生成的光滑曲面 坐標(biāo)卡參數(shù)域的構(gòu)造過程：（左圖）將坐標(biāo)卡的每個面均勻參數(shù)（均可以經(jīng)過線性變換以及變換Z4/ki得到一個彎曲的楔形面，將圖中綠色部分為其中一個楔形面 以B(n)(u,v)作為混合函數(shù)的流形曲面構(gòu)造 6片：（a）輸入網(wǎng)格；（b） viP1、P2上的頂點；畫黑色虛線的正方形區(qū)域分別為P1、P2的參數(shù)域，其中，僅畫出頂點vi的鄰域（綠域?qū)⑵渲幸粋€網(wǎng)格片的參數(shù)域作旋轉(zhuǎn)、平移變換后，頂點vi的鄰域能夠無縫拼接到一起 （a）頂點vi為網(wǎng)格片P1P2和P3的角點，圖中僅畫出P1P2和P3的部分參數(shù)域，綠域為頂點vi的1鄰域，每個網(wǎng)格片上頂點vi的1鄰域均延拓至包含該鄰域的矩形上（藍(lán)色虛線），并且相鄰矩形對應(yīng)邊等長；（b）lkgkz4/k將延拓后的矩形區(qū)域拼接到一起，整合成一個新的坐標(biāo)卡 第一章緒論Bézier[19–22]。vanWijk23]提出了一個基域的一個重要突破。此后，Reif[24]BézierG1T[25–28]曲面構(gòu)造技術(shù)由于允許T在于對規(guī)整控制網(wǎng)的需求，盡管前人很多方法都在逐步降低這一需求，但光滑性約束方程,于是在涉及到多片拼接的邊界點處,若要達(dá)到二階、三階及以細(xì)分曲面（SubdivisionSurfaces）[29,30]是一個網(wǎng)格序列的極限，網(wǎng)格序列則是通過采用一組細(xì)分規(guī)則（一般是平均）在給定初始網(wǎng)格中反復(fù)插入新頂點獲得的。Chaikin[31]首次將其應(yīng)用于幾何建模鄰域。其中最為著名的是Catmull-Clark細(xì)分算法[32]，通過一種四邊形網(wǎng)格的細(xì)分法則，構(gòu)造出任意拓?fù)浣Y(jié)造的三角形網(wǎng)格上的細(xì)分算法[33]、n邊域算法[34]、蝶形算法[35]等。這種方服參數(shù)曲面處理任意拓?fù)渚W(wǎng)格存在的。在實際應(yīng)用中，這種方法更為方便、基于離散網(wǎng)格的流形曲面構(gòu)造技術(shù)是一種新興的曲面造型技術(shù)，由GrimmHughs[2]1995若干個具有區(qū)域的坐標(biāo)卡，然后在每個坐標(biāo)卡上分別建立描述該坐標(biāo)卡局部幾何信息的形狀函數(shù)以及描述該坐標(biāo)卡上形狀函數(shù)對重建后流形曲面影響程的合數(shù)最利形函在標(biāo)之的域的同用造1不同于傳統(tǒng)NURBS構(gòu)造，基于離散網(wǎng)格的流形曲面構(gòu)造技術(shù)無需進(jìn)行拼接操流形的1.1.1.一個n維Ck原型微分流形（proto-manifold）K集合 {Vj|V∈Ui,Ui∈C}，其中 Φ{?ij:以下幾個

→i

∈Ui,

∈j其中，?ij滿?ij是一個Ck連續(xù)的一一映射函 x,?x∈(?ij ?ik(x)?x∈VikVj事實上，Vij描述了坐標(biāo)卡Ui中與Uj重合的區(qū)域，而轉(zhuǎn)換?ijVj圖 流形的定義[1]2流形曲面構(gòu)造方法流形曲面構(gòu)造方法一般可以描述為以下過程。給出一個多邊形網(wǎng)格M(V,F)（V為該多邊形網(wǎng)格的頂點集，F(xiàn)為對應(yīng)的面的集合，我們想構(gòu)造一個光滑的流形曲面S去近它。首先，以該網(wǎng)格為流形曲面構(gòu)造域D，建立坐標(biāo)卡i{(Ui?i)}N，其中，?iUiR2是一個一一映射，所Ui能夠?qū)完全覆蓋。任意兩個坐標(biāo)卡(Ui,?i)和j,j之間可能存在區(qū)域，也就是說Ui和j可能相交。如果Ui和j相交，那么，定義一個轉(zhuǎn)換函數(shù)?ijj???1，i分別建立描述該坐標(biāo)卡局部幾何信息的形狀函數(shù){qi(x):?i(Ui)→R3}N {wi(x):?i(Ui)→

∑

1

轉(zhuǎn)換函?ij混合函數(shù)的函數(shù)值以及k階導(dǎo)數(shù)值在該坐標(biāo)卡的邊界上是否等于形狀函數(shù)的光滑流形曲面構(gòu)造中的重要因素3數(shù)化到球面上（虧格為0）或者將其切開后，參數(shù)化到雙曲圓盤上（虧格大于0轉(zhuǎn)換函數(shù)的數(shù)義兩坐卡區(qū)在自數(shù)上一對關(guān)，時了保證最終構(gòu)造的流形曲面的連續(xù)性，所有轉(zhuǎn)換函數(shù)的連續(xù)性也需要達(dá)到一定的1.1所示。[1–373637]都采用間接性方法來構(gòu)造[8938,39]則通過將兩個坐標(biāo)卡上的映射函數(shù)（混合函數(shù)的上局部幾何形狀對整體曲面的影響程度。為了保證最終構(gòu)造的流形曲面的光滑k階導(dǎo)數(shù)值在坐標(biāo)卡的邊界上為（由(1.)可。4定義在矩形上的混合函數(shù)（不妨設(shè)為w(u,v)）可以表示為某種單變量函η(tw(u, 規(guī)則，將參數(shù)域基于面等幾何元素劃分成若干個不的區(qū)域，每個區(qū)域可以連處為1，邊界處為0。圖 兩種形式的混合函數(shù)形狀函數(shù)的用樣條函數(shù)（B樣條函數(shù)、T樣條函數(shù)、Powell-Sabin樣條函數(shù)等）去近[1]，來描述特征。5本文內(nèi)容及結(jié)構(gòu)章緒，紹傳的面型術(shù)，它的缺，而流形曲面構(gòu)造技術(shù)，然后分別介紹了其構(gòu)造流程以及構(gòu)造過程中的幾個重要因于任意多邊形網(wǎng)格建立流形曲面的方法。該方法主要是利用可以在平面任意多6該項技術(shù)得到了廣大學(xué)者的認(rèn)可以及后續(xù)更深入的研究。通過對目前已經(jīng)的傳統(tǒng)意義上的流形構(gòu)造方法不規(guī)則參根據(jù)網(wǎng)格的頂點、邊、面分別建立坐標(biāo)Catmull-Clark細(xì)分后，取細(xì)分換函數(shù)的構(gòu)造如圖2.2所示。只有不同類型的坐標(biāo)卡之間存在區(qū)域，即：頂點坐標(biāo)卡與邊坐標(biāo)7圖 圖2.2 邊坐標(biāo)卡與頂點坐標(biāo)卡之間轉(zhuǎn)換函數(shù)的構(gòu)造：ΨF1E為邊坐標(biāo)卡到面坐標(biāo)卡的轉(zhuǎn)換函數(shù)；ΨF1V為面坐標(biāo)卡到頂點坐標(biāo)卡的轉(zhuǎn)換函數(shù)[2]?；陧旤c的1鄰域建立坐標(biāo)卡上的每個面均是由一個正方形經(jīng)過映射Z4/ki得到，其中ki是頂點坐標(biāo)Zk1/k2，是一個C∞函數(shù)。然后，基于正方形建立混合函數(shù)，從而定義了面上的混合該方法最大的優(yōu)勢在于構(gòu)造了C∞連續(xù)的轉(zhuǎn)換函數(shù)，然后再通過多項式近細(xì)分曲面的方法建立形狀函數(shù)，可以構(gòu)造出C∞連續(xù)的流形曲面。如果在建立形狀函數(shù)時，加入C0基函數(shù)，則可以描述帶特征的模型，如2.4所示。8圖 ciZ/i[3]圖2.4 （ce（b）方框的放大圖[1]。矩形參kk鄰域建立坐標(biāo)卡后，每個坐標(biāo)卡形狀函數(shù)[4–6]。此時，可以分為兩種情況：參數(shù)域是包含頂點或者面的k鄰域的最小矩形。圖 參數(shù)域上幾個坐標(biāo)卡的示例[4]當(dāng)輸入為封閉網(wǎng)格時，首先，采用Catmull-Clark細(xì)分方法將其細(xì)分，從而2.6所示，基于頂點或者面的k鄰域定義的坐標(biāo)9方向移動一段距離時經(jīng)過的區(qū)域（如圖2.7中的陰影區(qū)域。因此，每個坐圖 幾個基于面定義的坐標(biāo)卡和基于點定義的坐標(biāo)卡[5]圖 k階連續(xù)星平面上的兩個坐標(biāo)卡（陰影區(qū)域）[6]圓形參坐標(biāo)卡[7,37]，如圖2.8所示。其中，面坐標(biāo)卡是三角形，對應(yīng)的參數(shù)域是彎圖 Ci、Ci和Ci是邊坐標(biāo)卡；Ci和 ；?i 每個面坐標(biāo)卡對應(yīng)于三個頂點坐標(biāo)卡的區(qū)域，每個邊坐標(biāo)卡以及相鄰的兩個面坐標(biāo)卡對應(yīng)于兩個頂點坐標(biāo)卡的區(qū)域。如圖2.9所示，每個邊坐標(biāo)圖 邊坐標(biāo)卡的參數(shù)化：圖中的數(shù)字代表參數(shù)化時，正方形邊的對 [7]基于規(guī)范區(qū)域的流形構(gòu)當(dāng)n 0時，將該網(wǎng)格參數(shù)化到球面上，然后以球面為定義域，來創(chuàng)建相當(dāng) 1時，將該網(wǎng)格參數(shù)化到平面上，并在該平面上創(chuàng)建流形曲面當(dāng)n>1時，將該網(wǎng)格參數(shù)化到雙曲空間上邊數(shù)為4n的多邊形上，然后以該多邊形為定義域，來創(chuàng)建流形曲面。根據(jù)拓?fù)鋵W(xué)知識，對于虧格為n的多邊形網(wǎng)格，可以沿著2n條切割線切開，然后參數(shù)化到邊數(shù)為4n的多邊形上，如圖2.10所示。多邊形上的每對邊（例如(a,a?1)）對應(yīng)于網(wǎng)格上的而這在歐拉空間上是的。從而，我們需要在雙曲空間上來建立對應(yīng)是，第i個坐標(biāo)卡的映射結(jié)合第j個坐標(biāo)卡的逆映射即構(gòu)成了這兩個坐標(biāo)卡圖2.10 的頂點對應(yīng)左圖的頂點[8]。立坐標(biāo)卡；基于Voronoi細(xì)分區(qū)域建立坐標(biāo)卡。2n+2個坐標(biāo)卡，使得這些坐標(biāo)卡可以將多邊2n2n條切割線建立的單位正方形，覆蓋圖 從左到右依次為：內(nèi)部坐標(biāo)卡；邊坐標(biāo)卡的一個示例；頂點坐標(biāo) [8]坐標(biāo)卡上的混合函數(shù)則是定義在正方形上的積函數(shù)?；赩oronoi細(xì)分區(qū)域建立坐標(biāo)卡Voronoi1鄰域面，[9]2.12展示了該類方法的構(gòu)造過程。每個坐標(biāo)卡都可以使用對應(yīng)的變換MD參數(shù)化到平面上，然后經(jīng)過一系列的旋轉(zhuǎn)變換、仿射變換MW映射到圓上，如圖2.13所示。因此，可以在圓上建立每個坐2.12(a2的環(huán)面；(b)初始的環(huán)線；(c切線；(d)將網(wǎng)格切開后參數(shù)化到多邊形上；(f)重建出來的光滑曲面，不同的顏色代表不同的坐標(biāo)卡的中心區(qū)域[9]。2.13球面（第一行）和環(huán)面（第二行）上坐標(biāo)卡映射函數(shù)的構(gòu)造：MD將規(guī)范區(qū)域（球域映射到圓上[9]?；跇訔l曲面推廣的流形構(gòu)造Gu[10]理論上證明了：傳統(tǒng)樣條理論本質(zhì)上是基于仿射幾何不變量，Gu等人[10]：只要將流形上的奇異點去除，剩下的部分便具有仿射結(jié)統(tǒng)方式定義樣條曲面，如圖2.14所示。中間兩行是兩個有區(qū)域的樣條曲面片(?α(Uα),Cα,Fα)、(?β(Uβ),Cβ,Fβ)二?αβ。Z為奇異點周圍的區(qū)域[10]。假設(shè)兩個有區(qū)域的坐標(biāo)卡在部分擁有同樣的控制網(wǎng)格，那么根據(jù)樣條曲面的參數(shù)仿射不變性，定義在這兩個坐標(biāo)卡上的樣條曲面在部分具無需像其他方法那樣需要將具有區(qū)域的多個坐標(biāo)卡上的形狀函數(shù)線性組合根據(jù)網(wǎng)格仿射結(jié)構(gòu)獲取方式的不同，將此類方法具體劃分成兩類：基于全純1-形式（oomorphc1form）誘導(dǎo)出仿射結(jié)構(gòu)；基于離散cci流誘導(dǎo)出仿射基于全純1-形式誘導(dǎo)出仿射根據(jù)黎曼曲面的知識，我們知道利用黎曼曲面上全純1-形式的積分，可以來造形射該法以理意格拓曲，且入結(jié)構(gòu)，這對流形樣條的構(gòu)造非常重要。但該方法的缺點是：曲面上的全純1-形式存在2.3.1.AM，這里的共形結(jié)構(gòu)是指，坐標(biāo)卡之間的轉(zhuǎn)換函數(shù)均為共形映射。全純1-形式w是一種復(fù)微分形式，使得在每個坐標(biāo)卡(U,?)∈A上 )根據(jù)上述得到的微分形式wf(z)dz找出奇異點，將奇異點以及其鄰面去除，計算出能將余下部分完住的坐標(biāo)卡[10,40]。坐標(biāo)卡的計算流程選擇頂Pα∈Uα?P∈

UαP

ww然后在每個坐標(biāo)卡上建立樣條曲面（三角形域上的B樣條曲面或者Powell-Sabin樣條曲面），并采用傳統(tǒng)的空洞填補(bǔ)技術(shù)對奇異點附近區(qū)域進(jìn)行填2.15所示，對于虧格大于1的曲面，根據(jù)共形結(jié)構(gòu)上所有軌跡經(jīng)過奇形平面上，然后在每個面片上定義T樣條曲面，從而將所有面片粘合到一[11]。[11]?；陔x散Ricci流誘導(dǎo)出仿射Ricci流可以看成是一個特殊的凸能量函數(shù)的負(fù)梯度流，它的收斂速度非?？?。利用circlepacking把網(wǎng)格度量定義在頂點處，然后從R3誘導(dǎo)的度量出當(dāng)輸入網(wǎng)格虧格大于1時，采用離散Ricci流方法將原始網(wǎng)格以及具有相同上的參數(shù)化，建立二者之間的一一對應(yīng)關(guān)系[12]，如圖2.16所示。圖 構(gòu)建高虧格網(wǎng)格與多面體的一一對應(yīng)關(guān)系[12]于多面體的面和邊建立坐標(biāo)卡，并在每個坐標(biāo)卡上構(gòu)造相應(yīng)的T樣條曲面。最后，再將去除的頂點周圍采用空洞填補(bǔ)技術(shù)進(jìn)行填補(bǔ)，如圖2.17所示。如圖2.18所示：用戶在網(wǎng)格上選取一個奇異點，并選取經(jīng)過奇異點的切割線將網(wǎng)格切開；利用離Ricci流計算出平面上的circlepacking度量，從而2.17創(chuàng)建T樣條流形時對奇異點的處理：(a)頂點均為奇異點的多面體；(b)去除頂點后的流形定義域；(c去除頂點后創(chuàng)建的T樣條曲面；(d奇異點附近填補(bǔ)后的完整曲[12]。.的中心坐標(biāo)卡；能將某條切割線覆蓋住的邊坐標(biāo)卡[13]。坐標(biāo)卡之間的轉(zhuǎn)奇異點數(shù)最少為1。另外，奇異點的位置可以靈活選擇。圖 利用離散Ricci流誘導(dǎo)出網(wǎng)格的仿射結(jié)構(gòu)[13]小對這三大類作詳細(xì)的介紹以及總結(jié)出它們的優(yōu)缺點。表1展示了這些文章各自表 所有流形曲面構(gòu)造文章的特111[4,5的綜1C∞11有關(guān)11C∞C0基分層B12n：2n+和圓上2[8,38的綜2Voronoi細(xì)分區(qū)2基于全純1-形構(gòu)經(jīng)過細(xì)分3經(jīng)過細(xì)分（插值頂點和法向3T3331分類一列中，1代表傳統(tǒng)意義上的流形構(gòu)造方法；2代表基于規(guī)范區(qū)域的流形構(gòu)造方法；3代表基于樣條曲面推廣第三章目前已有的流形曲面構(gòu)造技術(shù)的共同優(yōu)點是：能夠生成具有高階光滑性的具有特定的連接關(guān)系（的網(wǎng)格等，否則，就需要采取額外的細(xì)分步驟，而該細(xì)分步驟會大大增加坐標(biāo)卡的數(shù)量；而基于規(guī)范區(qū)域的流形構(gòu)造方法和基于樣條曲面推廣的流形構(gòu)造方法都需要一個整體的參數(shù)化步驟，顯然會提高算法其復(fù)雜度。流形曲面的方法。根據(jù)給定的多邊形網(wǎng)格，分別基于每個頂點的1鄰域建立坐標(biāo)卡，由于頂點的1鄰域面可以是各種不同的多邊形的集合，那么，坐標(biāo)卡的參數(shù)域邊混合[44]提出了一種雙參數(shù)樣條函數(shù)B(n)(u,v)。該函數(shù)具有緊支集并且可[01]，并且越接近多邊形內(nèi)部，函數(shù)值13.1展示了定義在相同多邊形上、不同參數(shù)值下的樣條函數(shù)的顏，其中n控制了該函數(shù)的連續(xù)性，δ控制了該函數(shù)的混合范圍（01之間的范圍。下面給出該函數(shù)的具體定義。3.1.144□R22δ2δ的正方形區(qū)域，其中δ>0。對任意給定的多邊形??R2，我們定義如下函數(shù){B(0)(u, χ(u,

(u,v)∈ 1

(u,v)?∈B(n)(u,

B(n?1)(s,t)χ□(s?u,t?性質(zhì) (i)非負(fù)性：0?B(n)(u,v)?光滑性：B(n)(u,v)Cn?1單位分解性（PartitionofUnity）：∑

k

那 k

(u, 1圖 B(n)(u,v)定義在相同多邊形上、不同參數(shù)值下的顏當(dāng)該雙變量樣條函數(shù)定義在矩形D[s,t,w,h]上時，其中，(s,t)為該矩形單變量樣條函數(shù)的內(nèi)積形式。該單變量樣條函數(shù)是基于單位階躍函數(shù)Hn(x)定義的。在區(qū)間[a,b]（a?b）上： H(b?x)?H(a?x) B(n)(u, (u) )

2nδsin(45?+θ)。其中，θ

與x0θ?π2Pk(p)B?k(p)。

Pk(p)B?k 是有界的，而上述提到的雙參數(shù)樣條函數(shù)的單位分解性只有在全平面R2上才滿足。因此，不能直接將上述模型推廣到參數(shù)曲面上。另外，由(3.3)可知，為了計算出目標(biāo)物體上某一點的函數(shù)值，必須要計算出該點在每個子區(qū)域上局部特征Pk(p)以及樣條函數(shù)值B?k(p)。顯然，這種全局計算模型的計算量會大大增開網(wǎng)格上的流形構(gòu)造給定開網(wǎng)格M {V,F}，其中，V為該網(wǎng)格所有頂點的集合，并且|V| 示了該創(chuàng)建過程。首先，將網(wǎng)格M進(jìn)行三角化，三角化的過程不引進(jìn)任何新的頂點。然后采用ARAP[45]參數(shù)化方法將三角化后的網(wǎng)格參數(shù)化到平面上，由于化方法可以靈活選取。接下來，基于網(wǎng)格頂點的1鄰域建立坐標(biāo)卡{(Ui,?i)}N 每個坐標(biāo)卡上，通過多項式近原始網(wǎng)格的細(xì)分網(wǎng)格來獲得該坐標(biāo)卡狀函數(shù){qi(x)}N ，并巧妙地利用3.1中提到的雙參數(shù)樣條函數(shù)作為該坐標(biāo)卡上1.1可以改寫為：

wj)qj(x∈ 圖3.2開網(wǎng)格上的流形曲面構(gòu)造流程：輸入具有任意連接關(guān)系的開網(wǎng)格（左圖平面上的參數(shù)化（中圖；使用本節(jié)方法構(gòu)造出的光滑曲面（右圖。圖中展示了構(gòu)造過程中其中一個坐標(biāo)卡的示例:以紅色頂點為中心、綠色面為1鄰域。由于轉(zhuǎn)換函數(shù)和形狀函數(shù)均為C∞這就要求混合函數(shù)可以在任意的平面多邊形上建立，同時還須具有緊支集以及3.1混合函數(shù)的為了保證最終生成曲面的光滑性，根據(jù)(3.4)，混合函數(shù)的函數(shù)值以及k0。若直接基于坐標(biāo)卡的參數(shù)域邊界3.1中提到的雙參數(shù)樣條函數(shù)作為該坐標(biāo)卡上的混合函數(shù)，則混合函數(shù)值在,其函數(shù)值在坐標(biāo)卡的參數(shù)域邊界處為0。圖3.3建立在不同坐標(biāo)卡上的混合函數(shù)B(n)(u,v)的 ，其中n=3,δ=0.05。外部的黃色多邊形為歸一化到[?1,1]]√Bn,(u,)

2nδsin(45?+θ)√

2nδsin(45?+θ)形的頂點即可。然而，這種方法獲得的目標(biāo)多邊形很有可能會產(chǎn)生、折疊的現(xiàn)象，尤其是當(dāng)坐標(biāo)卡的參數(shù)域邊界形成的多邊形相對于參數(shù)n、δ比較小時。為了解決這一問題，在進(jìn)行移動操作前，利用線性變換Γi si(x?vi)（設(shè)該坐標(biāo)卡是基于頂點vi定義的）將坐標(biāo)卡的參數(shù)域邊界歸一化到[?1,1]×[?1,1]上，然后再進(jìn)行上述移動操作。圖3.4(a)描述了這一過程。若此時獲得的目標(biāo)多邊形仍然有、折疊，則適當(dāng)?shù)卦龃髎i，然后進(jìn)行移動操作。對于定義在邊界頂點上的坐標(biāo)卡，利用上述方法構(gòu)造的該坐標(biāo)卡上的混合函數(shù)在該頂點處值為0；而基于該頂點的1鄰域頂點建立的各個坐標(biāo)卡上的混合函數(shù)在該頂點處的值也都均為0。此時(3.4)在該頂點處是沒有意義的，其各√22nδPP1Q151PP14133dP2d 圖3.4目標(biāo)多邊形的創(chuàng)建（a對于定義在頂點v上的坐標(biāo)卡,采用線性變換Γi)=si(x?i)[?1,1[?1,1](P1P2

?=2nδsin(45θi的距離，得到目?(Q1Q2Q5)，其中，PiPi+1x軸之間的最小夾角（b）′) (P1P2P3P4為歸一化后′) d=22nδ。P,P,P,。 ?的混合函數(shù)。對于坐標(biāo)卡(Ui,?i)上的頂點p,對應(yīng)的混合函數(shù)值為B(n) i?算法 目標(biāo)多邊形的構(gòu)輸出:QiStep1:利用線性變換i si(x?vi)將Pi歸一化到[?1,1][?11上Step2:Ifvi為邊界頂 i′P′i′

2nδ

令 √Step3Pi的每條邊向內(nèi)部移動2nδsin(45?θ),Step4:whileQi或者折形狀(Ui,?i)qi(x){al(x)}L

其中，基函數(shù)al(x)均為雙參數(shù)多項式函數(shù)，系數(shù)cil(l12L是通過求解∑ cilal(xk)? k=1這里，p1,p2,...,pm為坐標(biāo)卡(Ui,?i)上的觀測數(shù)據(jù)，由多邊形網(wǎng)格經(jīng)過Catmull-Clark細(xì)分得到；x1,x2,...,xm為p1,p2,...,pm對應(yīng)于坐標(biāo)卡參數(shù)域上的利用文章[36]中方法，可采用最小二乘求解上述優(yōu)化問題(3.6)。而?dmin(14,k1)k為該坐標(biāo)卡所結(jié)根據(jù)(3.4)，生成最終的曲面。由于混合函數(shù)是Cn?1連續(xù)的，形狀數(shù)是C∞連續(xù)的，則生成的光滑曲面是Cn?1理多項式曲面。參數(shù)n3.5tmulllrk細(xì)分曲面之間的差別。尤其是在多邊形網(wǎng)格的頂點附近，差異較大，這主要是由傳統(tǒng)的細(xì)分曲面在奇異點處的光滑性難以保證導(dǎo)致圖3.6些曲面均具有很好的重建效果。 （b（cCatmull-圖 基于任意多邊形網(wǎng)格生成的光滑曲面封閉網(wǎng)格上的流形構(gòu)造方法四邊形網(wǎng)格——四邊形網(wǎng)格建立流形曲面。目前為止，Ying和Zorin[36]針對四章[3]：C∞曲面的導(dǎo)數(shù)值可能會隨著導(dǎo)數(shù)階次的上升而具有更高的階；構(gòu)造Cn連續(xù)的曲面會降低導(dǎo)數(shù)值的階，同時也會提高曲面的質(zhì)量。于是，我們可以將3.1雙參數(shù)樣條函數(shù)代替文章[36]中的多項式作為混合函數(shù)，從而構(gòu)造同開網(wǎng)格上的流形曲面構(gòu)造方法，我們基于頂點的1鄰域建立坐標(biāo)卡，每個頂點的1鄰域面均為四邊形。圖3.7描述了坐標(biāo)卡參數(shù)域的構(gòu)造過程：首先將坐[001ii為中心頂點的度）變換到彎曲的楔形面上；將彎曲的楔形面分別經(jīng)過一定角度的Z12正方形邊界x1、y1處值為0，在1即可；然后將該函數(shù)映射紹3.1雙參數(shù)樣條函數(shù)在長方形上的表達(dá)形式，然后引出正方形上滿足條由于定義在矩形上的函數(shù)B(n)(u,v)2nδ圖37（左圖）將坐標(biāo)卡的每個面均勻參數(shù)化到平面上，得到（右圖星形上的每個楔形面均可以經(jīng)過線性變換以及變換Z/i得到一個彎曲的楔形面，將彎曲的楔形面分別經(jīng)過一定角度的旋轉(zhuǎn)，得到該坐標(biāo)卡的參數(shù)域。圖中綠色部分為其中一個楔形面。邊處值為0，在左下角頂點處值為1的函數(shù)可以表示為：?(n)(u, (u) 對于正方形[0,1]×[0,1]，s,t,w,h分別取值s0，t 當(dāng)nδ?0.5時，函數(shù)?(n)(u,v)在正方形邊界x1、 1處值為0，在原點坐標(biāo)卡上形狀函數(shù)的構(gòu)造跟開網(wǎng)格的情形一樣，采用多項式近細(xì)分網(wǎng)格獲得。因此，我們可以根據(jù)(1.1)構(gòu)建出Cn?1連續(xù)的光滑曲面。圖3.8展示圖 以B(n)(u,v)作為混合函數(shù)的流形曲面構(gòu)造任意多邊形若要保證最終生成曲面的光滑性，最關(guān)鍵的因一是要構(gòu)造光滑的轉(zhuǎn)換n（n>4）這一問題，相關(guān)鄰域的研究者們基本上都采用細(xì)分步驟來獲得具有特殊連接關(guān)系的網(wǎng)格（三角形網(wǎng)格、四邊形網(wǎng)格等 圖3.9 {Pi}m3.9所示。然后，采用Floater41][0,1[0,1]上。=面構(gòu)造方法相同，我們基于網(wǎng)格片Pi的每個頂點建立坐標(biāo)卡jj}= ij（Ni為網(wǎng)格片Pi中頂點的個數(shù)。對基于網(wǎng)格片內(nèi)部頂點建立的坐標(biāo)卡，我們可以直接采用3.2中的方法直接構(gòu)造混合函數(shù)和形狀函數(shù)。而對基于網(wǎng)格片邊界對于邊界坐標(biāo)卡，我們根據(jù)其是否是基于網(wǎng)格片的四個角點之一創(chuàng)建的來ii或者多個網(wǎng)格片上。當(dāng)v不是網(wǎng)格片的角點時，i同時位于兩個網(wǎng)格片上。將其中一個網(wǎng)格片重合的邊為i所在的邊，如圖3.10所示。于是，兩個網(wǎng)格片上分別基于頂點v建立的坐標(biāo)卡整合到一起，作為同一個坐標(biāo)卡，然后分別在該當(dāng)v為網(wǎng)格片的角點時，vi同時位于兩個以上的網(wǎng)格片若這些網(wǎng)格片的個數(shù)不為4，無法通過簡單的旋轉(zhuǎn)、平移變換將定義在頂點vivi3.10viP1、P2P1、P2的參數(shù)域，其中，僅畫出頂點vi的鄰域（綠域?qū)⑵渲幸粋€網(wǎng)格片的參數(shù)域作旋轉(zhuǎn)、平vi的鄰域能夠無縫拼接到一起。vi所在的幾個網(wǎng)i格片作線性變換以及 z4/ki（ki為這些網(wǎng)格片的個數(shù)）變換，使得ivi3.10所示。由此，每個網(wǎng)格片上基于頂點vi創(chuàng)建的坐標(biāo)卡進(jìn)行延拓，使得其參數(shù)1 1 gkP2 3.11（a）viP1,P2P3P1,P2P3的部分參數(shù)域，綠域為頂點vi的1鄰域，每個網(wǎng)格片上頂點vi的1鄰域均延拓至包含該（變換gk=z4/k將延拓后的矩形區(qū)域拼接到一起，整合成一個新的坐標(biāo)卡。第四章總網(wǎng)格上的流形曲面構(gòu)造技術(shù)是一個局部性構(gòu)造技術(shù)，相較于傳統(tǒng)曲面造型有高階光滑性。該項技術(shù)主要是通過將網(wǎng)格劃分成若干個具有區(qū)域的坐標(biāo)卡，并在每個坐標(biāo)卡上建立描述該坐標(biāo)卡局部幾何信息的形狀函數(shù)以及代表該形狀函數(shù)對最終曲面影響程度大小的混合函數(shù)，從而利用形狀函數(shù)在坐標(biāo)卡之間的域的同用構(gòu)建原始格的滑面。本文將目前已有的流形曲面構(gòu)造技術(shù)分為三大類：傳統(tǒng)意義上的流形構(gòu)造每一類作了詳細(xì)介紹，并總結(jié)出它們的優(yōu)缺點：傳統(tǒng)意義上的流形構(gòu)造方法是）（4的網(wǎng)格等）妙地將兩個坐標(biāo)卡上的映射函數(shù)組合起來從而得到對應(yīng)的轉(zhuǎn)換函數(shù)，大大降低條曲面推廣的流形構(gòu)造方法將樣條理論成功推廣到了流形區(qū)域上，是樣條理論針對目前已有的流形構(gòu)造方法的缺點本文提出了一個高效便捷的基于任意連接關(guān)系的網(wǎng)格直接創(chuàng)建流形曲面的方。通過巧妙運用文章[4]可以在平面任意多邊形上創(chuàng)建的、具有緊支集的雙變量樣條函數(shù)作為混合函數(shù)，創(chuàng)建出光滑性可控的流形曲面這是人工作上的一個突破然而對于開網(wǎng)格而言整體參數(shù)化的過程中若出現(xiàn)網(wǎng)格上素的翻轉(zhuǎn)生成曲面的對應(yīng)區(qū)域?qū)幸欢ǔ潭鹊淖冃螌τ诜忾]網(wǎng)格而言網(wǎng)格分割成若干個互不的四邊形網(wǎng)格片的方法還有待進(jìn)一步的研究以期得到一個自動簡便的分割方法另外，混合函數(shù)的參數(shù)n、δ需要謹(jǐn)慎選取，如果nδ太大，那么我們所構(gòu)造的目標(biāo)多邊形相對于坐標(biāo)卡的邊界多邊形而言會顯得很小，以至于曲面上某些點處的混合函數(shù)值在所有包含該頂點的坐標(biāo)卡上均為。由于C2連續(xù)的曲面已經(jīng)足夠我們進(jìn)行一般的幾何分析，因此，我們在本文中直接選取n ，δ 0.0。展流形構(gòu)造技術(shù)在工業(yè)制造中的推尋找不依賴于仿射結(jié)構(gòu)的樣條機(jī)制模型上特征的描目前，能夠描述模型上特征的方法只有兩種。一種是通過在構(gòu)造形狀函數(shù)時加入基函數(shù)，從而刻畫模型上的特征，但是該方法不能保證定的特征區(qū)域一定是0特征的描述，然而，該方法必須要用戶指定特征的具置，并且構(gòu)造轉(zhuǎn)換函數(shù)的過程比較復(fù)雜，構(gòu)造的結(jié)果相對而言也不是很理想。因此，尋找一個有效的描述模型上特征的流形曲面構(gòu)造技術(shù)仍然是我們需要共同努力的方向。在任意多邊形網(wǎng)格上的后續(xù)推具有任意連接關(guān)系的多邊形網(wǎng)格上的流形曲面構(gòu)造技術(shù)還有待進(jìn)一步WangR,LiuL,YangZ,etal.ConstructionofManifoldsviaCompatibleSparseRepresenta-tions.ACMTransactionsonGraphics(TOG),2016,35(2):14.GrimmCM,HughesJF.Modelingsurfacesofarbitrarytopologyusingmanifolds.ProceedingsofProceedingsofthe22ndannualconferenceonComputergraphicsandinctivetechniques.ACM,1995.359–368.TosunE,ZorinD.Manifold-basedsurfaceswithboundaries.ComputerAidedGeometricDesign,2011,28(1):1–22.NavauJC,GarciaNP.Modellingsurfacesfromnarirregularmeshes.ComputerAidedGeometricDesign,2000,17(1):1–15.NavauJC,GarciaNP.Modelingsurfacesfrommeshesofarbitrarytopology.ComputerAidedGeometricDesign,2000,17(7):643–671.Cotrina-NavauJ,-GarciaN,Vigo-AngladaM.Agenericapproachtoformsurfacegeneration.ProceedingsofProceedingsoftheseventhACMsymposiumonSolidmodelingandapplications.ACM,2002.35–44.DellaVecchiaG,JüttlerB,KimMS.Aconstructionofrationalmanifoldsurfacesofarbitrarytopologyandsmoothnessfromtriangularmeshes.ComputerAidedGeometricDesign,2008,GrimmC,HughesJ.Parameterizingn-holedtori.ProceedingsofMathematicsofSurfaces.Springer,2003:14–29.GrimmC,JuT,PhanL,etal.Adaptivesmoothsurfacefittingwithmanifolds.TheVisualComputer,2009,25(5):589–597.GuX,HeY,QinH.Manifoldsplines.GraphicalModels,2006,HeY,WangK,WangH,etal.ManifoldT-spline.ProceedingsofInternationalConferenceonGeometricModelingandProcessing.Springer,2006.409–422.WangH,HeY,LiX,etal.Polycubesplines.Computer-AidedDesign,2008,GuX,HeY,JinM,etal.Manifoldsplineswithasingleextraordinarypoint.Computer-AidedDesign,2008,40(6):676–690.ForseyDR,BarsRH.HierarchicalB-splinerefinement.ACMSiggraphComputerGraph-ics,1988,22(4):205–212.PieglL,TillerW.TheNURBSbook.SpringerScience&BusinessMedia,HughesTJ,RealiA,SangalliG.EfficientquadratureforNURBS-basedisogeometricysis.Computermethodsinappliedmechanicsandengineering,2010,199(5):301–313.EckM,HoppeH.AutomaticreconstructionofB-splinesurfacesofarbitrarytopologicaltype.ProceedingsofProceedingsofthe23rdannualconferenceonComputergraphicsandinc-tivetechniques.ACM,1996.325–334.KrishnamurthyV,LevoyM.Fittingsmoothsurfacestodensepolygonmeshes.ProceedingsofProceedingsofthe23rdannualconferenceonComputergraphicsandinctivetechniques.ACM,1996.313–324.GregoryJA,ZhouJ.Fillingpolygonalholeswithbicubicpatches.ComputerAidedGeometricDesign,1994,11(4):391–410.LoopC.Smoothsplinesurfacesoverirregularmeshes.ProceedingsofProceedingsofthe21stannualconferenceonComputergraphicsandin ctivetechniques.ACM,1994.303–310.PetersJ.BiquarticC1-surfacesplinesoverirregularmeshes.Computer-AidedDesign,1995,VanWijkJJ.Bicubicpatchesforapproximatingnon-rectangularcontrol-pointmeshes.Com-puterAidedGeometricDesign,1986,3(1):1–13.ReifU.BiquadraticG-splinesurfaces.ComputerAidedGeometricDesign,1995,12(2):193–SilvettiA,DelrieuxC,CastroS.T-Splines:anewschemaforC/sup2/splineinterpolation.ProceedingsofComputerScienceSociety,1997.Proceedings.,XVIIInternationalConferenceoftheChilean.IEEE,1997.240–245.SederbergTW,ZhengJ,BakenovA,etal.T-splinesandT-NURCCs.ProceedingsofACMtransactionsongraphics(TOG),volume22.ACM,2003.477–484.LiX,ZhengJ,SederbergTW,etal.OnlinearindependenceofT-splineblendingfunctions.ComputerAidedGeometricDesign,2012,29(1):63–76.ZhangJ,LiX.Onthelinearindependenceandpartitionofunityofarbitrarydegreeysis-suitableT-splines.CommunicationsinMathematicsandStatistics,2015,3(3):353–364.DooD,SabinM.Asubdivisionalgorithmforsmoothingdownirregularlyshapedpolyhedrons.ProceedingsofProceedingsoninctivetechniquesincomputeraideddesign,volume157.Bologna,1978.165.Nie?nerM,LoopC,MeyerM,etal.Feature-adaptiveGPUrenderingofCatmull-Clarksub-divisionsurfaces.ACMTransactions