前言

上文我們介紹了半邊網(wǎng)格的底層架構(gòu)，介紹了點、半邊和面所攜帶的信息。本文我們來探討一個半邊網(wǎng)格的應(yīng)用——網(wǎng)格細分。網(wǎng)格細分是一種高效地表達幾何的方法。

網(wǎng)格細分簡述

在 Mesh is Art（1) 中，我們講解了網(wǎng)格數(shù)據(jù)大多數(shù)由三角形或四邊形組成。網(wǎng)格細分技術(shù)為分割曲面提供了解決方案。這種技術(shù)的核心是關(guān)注如何通過細分算法（Subdivision）計算來用大量的較小的網(wǎng)格面來替代原來的曲面，從而細分并優(yōu)化輸入的基礎(chǔ)網(wǎng)格面。并且由此產(chǎn)生的精密網(wǎng)格還可以使用相同的算法來產(chǎn)生更精密的網(wǎng)格，如此可以反復(fù)迭代。隨著迭代步的增加，網(wǎng)格的數(shù)量也不斷地翻倍，從而更加逼近于精確、光滑的初始曲面。

網(wǎng)格細分技術(shù)已經(jīng)被廣泛地應(yīng)用于游戲和動畫產(chǎn)業(yè)當中，在項目中常采用非常粗糙的基礎(chǔ)網(wǎng)格來表達一個物體（大概只需要幾百個多邊形），因此存儲時所占用的計算機資源非常少。我們知道動畫和游戲中常常需要渲染模型，對于模型的渲染時，并不是所有模型都要達到幾十萬網(wǎng)格面級別再去渲染，這樣不僅增加了模型場景中的負擔，還浪費了許多時間。在一個場景中，通常只有距離攝像機近、需要突出表達細節(jié)的模型才會被渲染地非常清晰，其他背景、場景往往不需要那么高精度的表達。因此，網(wǎng)格細分技術(shù)變得十分重要，設(shè)計師只需要建立一些粗糙網(wǎng)格模型，當該模型需要被表達時，將其細分，不需要表達細節(jié)時，就保持不變。

Figure 1：隨著網(wǎng)格細分迭代次數(shù)增加，網(wǎng)格模型逐漸變得精細（從右至左）圖片來源：Pixie3D | Animation Software

Figure 2：隨著網(wǎng)格細分迭代次數(shù)增加，網(wǎng)格模型逐漸變得精細（從左至右）圖片來源：《Subdivision for Modeling and Animation》

在建筑設(shè)計中，許多建筑在設(shè)計階段是由NURBS曲面這樣的光滑連續(xù)曲面建模技術(shù)來設(shè)計的。然而，這些模型在幾何學(xué)方面很容易操作（很容易在計算機中建模），但它們很難被精確地制造出來，由于加工尺度問題，在實際項目中不可避免地要將它們分割成小構(gòu)件，從而制作出能安裝在結(jié)構(gòu)上的表面嵌板（如圖3）。在建造中，即使最后完成時是一個單體結(jié)構(gòu)，通常也需要采用離散單元來拼合的傳統(tǒng)方法。因此，這些項目在建模時經(jīng)常使用離散網(wǎng)格來表示曲面（如圖4、5），來代替一張參數(shù)化連續(xù)的NURBS曲面（至少在工程和制造階段上是這樣）。在 Mesh is Art（2）中，也簡述了一個由細分算法主導(dǎo)的建筑設(shè)計實例。

Figure 3：細分網(wǎng)格在建筑中的應(yīng)用圖片來源：Design and Panelization of Architectural Freeform-Surfaces by Planar Quadrilateral Meshes

Figure 4：用細分網(wǎng)格表達光滑曲面（一）：從左至右依次為：初始光滑曲面、手動創(chuàng)建的初始網(wǎng)格、通過投影算法匹配到初始光滑曲面后的網(wǎng)格、細分之后的網(wǎng)格圖片來源：Design and Panelization of Architectural Freeform-Surfaces by Planar Quadrilateral Meshes

Figure 5：用細分網(wǎng)格表達光滑曲面（二）：初始網(wǎng)格（左）和細分后的網(wǎng)格（右）圖片來源：Design and Panelization of Architectural Freeform-Surfaces by Planar Quadrilateral Meshes

網(wǎng)格細分除了在建造上表達曲面的優(yōu)勢外，還常被用于分析和優(yōu)化。

在幕墻優(yōu)化中，細分曲面常用來控制嵌板的尺寸以及輔助其他優(yōu)化算法。比如當設(shè)計師設(shè)計了一張曲面，需要將該曲面鋪上嵌板，設(shè)計師可以使用細分算法對該曲面不斷地迭代細分，直至嵌板的尺寸符合可加工的尺寸，接著可進行更進一步地平板優(yōu)化和規(guī)格優(yōu)化，當然這兩個問題先放到后面了。

在對于需要執(zhí)行多目標優(yōu)化的曲面來說，網(wǎng)格細分同樣非常有用。在設(shè)計和施工的過程中，通常要對建筑曲面進行優(yōu)化來提高其性能。結(jié)構(gòu)優(yōu)化通常要求在最大限度節(jié)省材料的前提下盡可能小地改變形狀，優(yōu)化的實現(xiàn)可以通過將結(jié)構(gòu)構(gòu)件僅放置在所需要的地方來盡可能減少結(jié)構(gòu)構(gòu)件的數(shù)量，或者通過調(diào)整結(jié)構(gòu)構(gòu)件以便有效地將載荷傳遞到支撐來減少結(jié)構(gòu)構(gòu)件的大小。改變建筑物的形狀可以減小風(fēng)和雪帶來的荷載，當然也可以通過考慮熱環(huán)境、通風(fēng)和采光來優(yōu)化建筑的場地、形狀和遮陽，從而提高建筑的環(huán)境性能。

這些優(yōu)化目標都需要對建筑模型采用一種特殊表式方法來分析其性能。這些分析需要大量離散的類似網(wǎng)格的表示方法，并且所需要的網(wǎng)格的密度會取決于正在執(zhí)行的分析類型。例如有限元結(jié)構(gòu)分析可能會要求網(wǎng)格的離散方式能夠反映給出的支撐結(jié)構(gòu)，計算風(fēng)流分析可能需要更精密的分析網(wǎng)格，而太陽能生成計算會相對精確，可能只需要比較粗糙的網(wǎng)格來表示即可。連續(xù)殼體的有限元結(jié)構(gòu)分析需要形狀函數(shù)來在兩節(jié)點間插入幾何結(jié)構(gòu)，而細分曲面也可用于此。

網(wǎng)格細分可以看作是一種圓滑的過程，細分得到的網(wǎng)格子頂點坐標是由周圍相鄰父頂點的平滑平均值產(chǎn)生。用這種方式，網(wǎng)格的坐標被圓滑，形成更接近初始的近似曲面。這一點已經(jīng)被證明（Zorin et al.，2000），這種生成的近似曲面在非邊界和非奇異頂點處都是C2連續(xù)的，這意味著形態(tài)表面（沒有縫隙）、表面切線（沒有折痕）以及切線的變化率（在視覺反射中沒有變形）都沒有突變（這三點分別是C0，C1和C2連續(xù)性的判斷標準）。這也是細分網(wǎng)格看上去特別美觀的原因。

圓滑過程的另一個優(yōu)點是，細分不僅能可以圓滑頂點坐標，任何一組與頂點關(guān)聯(lián)的數(shù)據(jù)都會被圓滑，如果一個初始的粗糙網(wǎng)格中每一個頂點附帶著一個顏色的信息，所有連續(xù)細分的網(wǎng)格都能夠自動匹配圓滑曲面上的顏色。可以類似地應(yīng)用于更多實際的參數(shù)，例如頂點攜帶的貼圖信息、應(yīng)力值、立面滲透率或透明度值，百葉窗角度或者覆層的偏移距離。在基礎(chǔ)網(wǎng)格上，這些數(shù)據(jù)可以被定義在所需要的頂點上，細分網(wǎng)格后，這些信息將完全以與頂點位置相同的C2連續(xù)的方式均勻地分布在整個曲面上。

細分算法原理

實現(xiàn)網(wǎng)格細分有多種方案，有基于三角形網(wǎng)格的，基于四邊形網(wǎng)格，也有基于高階多邊形及混合網(wǎng)格的。細分算法的基本過程首先是從一張網(wǎng)格面開始，用某種方式在網(wǎng)格上添加點，并對拓撲結(jié)構(gòu)進行優(yōu)化。本文中著重討論兩個細分算法的原理及C#實現(xiàn)。

Loop細分算法

原理

Loop細分算法（Loop，1992）是一種應(yīng)用在三角形網(wǎng)格的算法，如圖6所示，這是從一個球形網(wǎng)格中提取的一張網(wǎng)格面，藍色頂點為父頂點，即網(wǎng)格面原有的頂點，紅色頂點為新創(chuàng)建的子頂點，每個三角形上的每條邊都被新引入的子頂點分割成了兩段，然后每一個三角形都被四個新的小三角形代替。

Figure 6：Loop細分算法的實現(xiàn)步驟：（a）基礎(chǔ)網(wǎng)格；（b）拓撲劃分；（c）圓滑子頂點；（d）圓滑父頂點圖片來源：《Shell Structures for Architecture: Form Finding and Optimization》

內(nèi)部子頂點：設(shè)內(nèi)部邊的兩端點，，其相對的兩個頂點為，，要創(chuàng)建的子頂點為，則

內(nèi)部父頂點：設(shè)內(nèi)部父頂點 $v_0$ 的相鄰點為 $v_1$ ， $v_2$ ，...， $v_n$ ，更新后的父頂點為 $v_{new}$ ，w為權(quán)重值， $n$ 為頂點的價（該頂點的相鄰點的數(shù)量），則
$w=\frac{1}{n}(\frac{5}{8}-(\frac{3}{8}+\frac{1}{4}cos\frac{2\pi}{n})^2)$

$v_{new} = (1-nw)v_0+w\sum_{i=1}^{n} {v_i}$

在細分算法里曲面的邊緣通常需要被特殊處理，比如一條只通過一個面的邊（面的邊緣）。如圖8-a所示，沿著邊界創(chuàng)建的子頂點會被放置在邊界上的邊的中點。如圖8-b所示，邊界上的邊的父頂點會被放置在以原始位置為 $\frac{3}{4}$ 權(quán)重值和相鄰兩個頂點位置各占 $\frac{1}{8}$ 權(quán)重值的位置，而不會考慮內(nèi)部鄰近頂點的位置。

Figure 8：邊界頂點的權(quán)重值圖片來源：《Shell Structures for Architecture: Form Finding and Optimization》

邊界子頂點：設(shè)邊界邊的兩個端點為和，要創(chuàng)建的子頂點為，則

邊界父頂點：設(shè)邊界父頂點 $v_0$ 的相鄰點為 $v_1$ 和 $v_2$ ，更新后的父頂點為 $v_{new}$ ，w為權(quán)重值， $n$ 為頂點的價（該頂點的相鄰點的數(shù)量），則
$v_{new} = \frac{3}{4}v_{0}+\frac{1}{8}(v_1+v_2)$

代碼實現(xiàn)

在Mesh is Art（3）中，我們講解了半邊網(wǎng)格的特性，即半邊網(wǎng)格在處理鄰域查找問題上尤為高效。因此在實現(xiàn)網(wǎng)格細分算法中，半邊網(wǎng)格是最適合的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，這也是為什么我一直在強調(diào)使用半邊數(shù)據(jù)結(jié)構(gòu)，類似細分一樣大量使用網(wǎng)格鄰域查找的算法還有很多。簡略版的Loop細分的C#源碼如下：

 public Mesh Loop(Mesh m)
  {
    PlanktonMesh P = m.ToPlanktonMesh();
    PlanktonMesh NP = new PlanktonMesh();
    PlanktonMesh TP = P;

    for (int v = 0; v < P.Vertices.Count; v++)
    {
      // Loop
      int[] Neighbours = P.Vertices.GetVertexNeighbours(v);

      int Valence = Neighbours.Length;
      double Beta = 0.625 - (Math.Pow((3 + 2 * Math.Cos((2 * Math.PI) / Valence)), 2) * 0.015625);
      double Mult = Beta / Valence;

      Point3d NewPosition = P.Vertices[v].ToPoint3d() * (1 - Beta);

      foreach (int Neighbour in Neighbours)
      {
        NewPosition += P.Vertices[Neighbour].ToPoint3d() * Mult;
      }
      NP.Vertices.Add(NewPosition);
    }
    for (int HE = 0; HE < P.Halfedges.Count; HE += 2)
    {
      int Pair = P.Halfedges.GetPairHalfedge(HE);
      int ThisOpp = P.Halfedges[HE].PrevHalfedge;
      int PairOpp = P.Halfedges[Pair].PrevHalfedge;

      int HeSV = P.Halfedges[HE].StartVertex;
      int PrSV = P.Halfedges[Pair].StartVertex;

      // split the halfedges in the topology lookup mesh
      TP.Halfedges.SplitEdge(HE);
      // ensure that each face has a starting halfedge on an even vertex
      if (P.Halfedges[Pair].AdjacentFace > -1) 
        TP.Faces[P.Halfedges[Pair].AdjacentFace].FirstHalfedge = TP.Halfedges.Count - 1;

      // Loop
      Point3d NewPosition = P.Vertices[HeSV].ToPoint3d() * 0.375 +
      P.Vertices[PrSV].ToPoint3d() * 0.375 +
      P.Vertices[P.Halfedges[ThisOpp].StartVertex].ToPoint3d() * 0.125 +
      P.Vertices[P.Halfedges[PairOpp].StartVertex].ToPoint3d() * 0.125;
      NP.Vertices.Add(NewPosition);
    }
    for (int f = 0; f < P.Faces.Count; f++)
    {
      // add new triangulated faces
      int[] FaceVerts = TP.Faces.GetFaceVertices(f);
      NP.Faces.AddFace(FaceVerts[0], FaceVerts[1], FaceVerts[5]);
      NP.Faces.AddFace(FaceVerts[2], FaceVerts[3], FaceVerts[1]);
      NP.Faces.AddFace(FaceVerts[4], FaceVerts[5], FaceVerts[3]);
      NP.Faces.AddFace(FaceVerts[1], FaceVerts[3], FaceVerts[5]);
    }
    return NP.ToRhinoMesh();
  }

Catmull-Clark細分算法

原理

Catmull-Clark細分是一種基于四邊形的網(wǎng)格細分算法，它所產(chǎn)生的網(wǎng)格能夠達到 $C^{2}$ 連續(xù)，奇異點處為 $C^1$ 連續(xù)。和Loop類似，其實就是父的更新法則和子頂點的創(chuàng)建法則有不同。對于內(nèi)部頂點，位于面中的子頂點創(chuàng)建法則為該面頂點的加權(quán)平均，位于邊界的子頂點的創(chuàng)建法則是內(nèi)部邊兩端點的 $\frac{3}{8}$ ，過該邊的兩張網(wǎng)格面的其他頂點占 $\frac{1}{16}$ 。父頂點的更新法則分兩種，與父頂點相鄰的頂點的權(quán)重為β/k（β=3/2k，k為頂點的價），與父頂點共面卻不相鄰的頂點的權(quán)重為γ/k（γ=1/4k），父頂點挪動前的權(quán)重為1-β-γ。邊界頂點的處理和Loop算法完全相同，這里不再多做解釋了。

Figure 9：Catmull-Clark細分法則圖片來源：《Subdivision for Modeling and Animation》

位于面中的內(nèi)部子頂點：設(shè)四邊形的四個頂點分別為，，，，要創(chuàng)建的子頂點為，則

位于內(nèi)部邊上的子頂點：設(shè)內(nèi)部網(wǎng)格邊的兩端為和，與該邊相鄰的兩個四邊形頂點分別為---和---要創(chuàng)建的子頂點為，則

內(nèi)部父頂點：設(shè)內(nèi)部父頂點 $v_0$ 的相鄰點為 $v_1$ ， $v_2$ ，...， $v_2n$ ，更新后的父頂點為 $v_{new}$ ，β和γ均為權(quán)重值， $n$ 為頂點的價（該頂點的相鄰點的數(shù)量），則
$β=\frac{3}{2n}$$$$γ=\frac{1}{4n}$$$$v_{new} = (1-β-γ)v_0+\frac{β}{n}\sum_{i=1}^{n} {v_{2i}}+\frac{γ}{n}\sum_{i=1}^{n} {v_{2i-1}}$

邊界子頂點：設(shè)邊界邊的兩個端點為 $v_0$ 和 $v_1$ ，要創(chuàng)建的子頂點為 $v_{new}$ ，則
$v_{new} = \frac{v_0+v_1}{2}$
邊界父頂點：設(shè)邊界父頂點 $v_0$ 的相鄰點為 $v_1$ 和 $v_2$ ，更新后的父頂點為 $v_{new}$ ，w為權(quán)重值， $n$ 為頂點的價（該頂點的相鄰點的數(shù)量），則
$v_{new} = \frac{3}{4}v_{0}+\frac{1}{8}(v_1+v_2)$

代碼實現(xiàn)

簡略版的Catmull-Clark細分的C#源碼如下：

public Mesh CatmullClark(Mesh m)
  {
    PlanktonMesh P = m.ToPlanktonMesh();
    PlanktonMesh NP = new PlanktonMesh();
    PlanktonMesh TP = m.ToPlanktonMesh();

    for (int v = 0; v < P.Vertices.Count; v++)
    {
      // Catmull-Clark
      int[] InHEs = P.Vertices.GetIncomingHalfedges(v);

      double Beta = 3.0 / (2 * InHEs.Length);
      double Delta = 1.0 / (4 * InHEs.Length);
      double BetaK = Beta / InHEs.Length;
      double DeltaK = Delta / InHEs.Length;

      Point3d NewPosition = P.Vertices[v].ToPoint3d() * (1 - Beta - Delta);

      foreach (int InHE in InHEs)
      {
        NewPosition += P.Vertices[P.Halfedges[InHE].StartVertex].ToPoint3d() * BetaK;
        NewPosition += P.Vertices[P.Halfedges[P.Halfedges[InHE].PrevHalfedge].StartVertex].ToPoint3d() * DeltaK;
      }
      NP.Vertices.Add(NewPosition);
    }
    for (int HE = 0; HE < P.Halfedges.Count; HE += 2)
    {
      int Pair = P.Halfedges.GetPairHalfedge(HE);
      int ThisOpp = P.Halfedges[HE].PrevHalfedge;
      int PairOpp = P.Halfedges[Pair].PrevHalfedge;

      int HeSV = P.Halfedges[HE].StartVertex;
      int PrSV = P.Halfedges[Pair].StartVertex;

      // split the halfedges in the topology lookup mesh
      TP.Halfedges.SplitEdge(HE);
      // ensure that each face has a starting halfedge on an even vertex
      if (P.Halfedges[Pair].AdjacentFace > -1) TP.Faces[P.Halfedges[Pair].AdjacentFace].FirstHalfedge = TP.Halfedges.Count - 1;

      // Catmull-Clark
      Point3d NewPosition = P.Vertices[HeSV].ToPoint3d() * 0.375 +
        P.Vertices[PrSV].ToPoint3d() * 0.375 +
        P.Vertices[P.Halfedges[P.Halfedges.GetPairHalfedge(P.Halfedges[HE].NextHalfedge)].StartVertex].ToPoint3d() * 0.0625 +
        P.Vertices[P.Halfedges[P.Halfedges[HE].PrevHalfedge].StartVertex].ToPoint3d() * 0.0625 +
        P.Vertices[P.Halfedges[P.Halfedges.GetPairHalfedge(P.Halfedges[Pair].NextHalfedge)].StartVertex].ToPoint3d() * 0.0625 +
        P.Vertices[P.Halfedges[P.Halfedges[Pair].PrevHalfedge].StartVertex].ToPoint3d() * 0.0625;
      NP.Vertices.Add(NewPosition);
    }
    for (int f = 0; f < P.Faces.Count; f++)
    {
      int CenterIdx = NP.Vertices.Count;
      NP.Vertices.Add(P.Faces.GetFaceCenter(f).ToPoint3d());
      int[] FaceVerts = TP.Faces.GetFaceVertices(f);
      for (int nf = 0; nf < FaceVerts.Length; nf += 2)
      {
        int LastVert = nf - 1;
        if (nf == 0) LastVert = FaceVerts.Length - 1;
        NP.Faces.AddFace(FaceVerts[nf], FaceVerts[nf + 1], CenterIdx, FaceVerts[LastVert]);
      }
    }
    return NP.ToRhinoMesh();
  }

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Mesh is Art（4）：網(wǎng)格細分

Mesh is Art（4）：網(wǎng)格細分

前言

網(wǎng)格細分簡述

細分算法原理

Loop細分算法

原理

代碼實現(xiàn)

Catmull-Clark細分算法

原理

代碼實現(xiàn)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Mesh is Art（4）：網(wǎng)格細分

前言

網(wǎng)格細分簡述

細分算法原理

Loop細分算法

原理

代碼實現(xiàn)

Catmull-Clark細分算法

原理

代碼實現(xiàn)

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av