黎明的剔透里伸出了你沁清的曖昧

Graphics|EngineDev|GameDev|2D&3D Art

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

60 隨筆 :: 1 文章 :: 18 評論 :: 0 Trackbacks

公告

Please feel free to reach me through email: crazyinit(at)gmail(dot)com, this is the preferred way.

常用鏈接

留言簿(3)

隨筆分類(83)

文章檔案(1)

2013年11月 (1)

相冊

圖片

搜索

閱讀排行榜

評論排行榜

三角網格(Triangle Mesh)

最簡單的情形，多邊形網格不過是一個多邊形列表；三角網格就是全部由三角形組成的多邊形網格。多邊形和三角網格在圖形學和建模中廣泛使用，用來模擬復雜物體的表面，如建筑、車輛、人體，當然還有茶壺等。圖14.1給出一些例子：

當然，任意多邊形網格都能轉換成三角網格，三角網格以其簡單性而吸引人，相對于一般多邊形網格，許多操作對三角網格更容易。

1 表示網格

三角網格為一個三角形列表，所以最直接的表示方法是用三角形數組：

Listing 14.1: A trivial representation of a triangle mesh

struct Triangle {
  Vector3 p[3];
};

struct TriangleMesh {
  int triCount;
  Triangle *triList;
};

對于某些應用程序，這種表示方法已經足夠。然而，術語"網格"隱含的相鄰三角形的連通性卻未在這種簡單表示中有任何體現。實際應用中出現的三角網格，每個三角形都和其他三角形共享邊。于是，三角網格需要存儲三類信息：

頂點。每個三角形都有三個頂點，各頂點都有可能和其他三角形共享。
.
邊。連接兩個頂點的邊，每個三角形有三條邊。
.
面。每個三角形對應一個面，我們可以用頂點或邊列表表示面。

1.1 索引三角網格

在索引三角網格中，我們維護了兩個列表：頂點表(Vertex buffer)與三角形表(Index Buffer)。

每個頂點包含一個3D位置，也可能有如紋理映射坐標、表面法向量、光照值等附加數據。

每個三角形由頂點列表的三個索引組成。通常，頂點列出的順序是非常重要的，因為我們必須考慮面的"正面"和"反面"。從前面看時，我們將用順時針方向列出頂點。另外一些信息也存在這一級中，如預先計算的表面法向量，表面屬性（紋理映射）等。

程序清單14.2給出了一段高度簡化的代碼：
Listing 14.2: Indexed triangle mesh

// struct Vertex is the information we store at the vertex level
struct Vertex
{
// 3D position of the vertex
Vector3 p;

// Other information could include texture mapping coordinates,
// a surface normal, lighting values, etc.
}

// struct Triangle is the information we store at the triangle level
struct Triangle
{
// Indices into the vertex list
int vertex[3];

// Other information could include a normal, material information, etc.
}

// struct TriangleMesh stores an indexed triangle mesh
struct TriangleMesh
{
// The vertices
int vertexCount;
Vertex *vertexList;

// The triangles
int triangleCount;
Triangle *triangleList;
};

實踐中，三角網格類會有一系列方法，用于存取和維護頂點、三角形列表。當然，存儲多邊形網格，還需要定義一個多邊形類，用來表達有任意多頂點的面。為簡化和提高效率，我們可以對每個多邊形的最大定點數做出限制。注意到，索引三角形列表中的鄰接信息是隱含的。例如：邊信息沒有直接存儲，但我們還是可以通過搜索三角形表找出公共邊。和前面"三角形數組"方式相比，這種方式確實能節省不少空間。原因是信息存于頂點級別，它的整數索引比之三角形數組里存儲的頂點重復率要小得多。

1.2 高級技術

簡單索引三角網格對于基本應用已經足夠了，但為了更加高效地實現某些操作還可以進行一些改進。主要的問題是鄰接信息沒有顯式表達，所以必須從三角形列表中搜索。另一種表達方法可以在常數時間內取得這種信息。

方法是維護一個邊列表，每個邊由兩個端點定義，同時維護一個共享該邊的三角形列表。這樣，三角形可視為三條邊而非三個點的列表，也就是說它是邊列表而不是點列表的索引。該思想的一個擴展稱作"winged edge"模型，對每一頂點，存儲使用該點的邊的索引。

2 針對渲染的特殊表達

大多數圖形卡并不直接支持索引三角網，渲染三角形時，一般是將三個頂點同時提交。這樣，共享頂點會多次提交，三角形用到一次就提交一次。因為內存和圖形硬件間的數據傳輸是瓶頸，所以許多API和硬件支持特殊的三角網格式以減少傳輸量?；舅枷胧桥判螯c和面，使得現存中已有的三角形不需要再次傳輸。

從最高靈活性到最低靈活性，我們討論三種方案：頂點緩存，三角帶，三角扇。

2.1 頂點緩存

與其說頂點緩存是一種特殊的存儲格式，不如說是API和硬件之間的一種存儲策略，用以發揮連續三角形頂點一致性的特點。通常，高級代碼不需要了解頂點緩存是如何實現和執行的。

和其他緩存機制類似，頂點緩存基于最近使用的數據將來仍被使用的原則。圖形處理器緩存一小部分（如，16個）最近使用的頂點，當API要發送頂點時，首先探測緩存內是否已存在。當然，這要求API了解圖形卡緩存的大小和替換機制。若緩存內沒有該頂點，則發生脫靶，API發送頂點并更新緩存；若緩存內有該頂點，就命中，API通知圖形卡"使用緩存內位置x的頂點"。

頂點緩存其實是一種底層的優化手段，任何三角網都可用高級代碼實現正確渲染而不用考慮緩存。但進行頂點順序的調整，使共享頂點的三角形集中發送有助于提高效率。這種調整只需要進行一次，并且可以離線進行，它只會對性能有幫助，不會使沒有緩存的系統性能降低。善用緩存，可能使發送到顯卡的頂點數降低到平均每三角形少于一個。

2.2 三角帶

三角帶是一個三角形列表，其中每個三角形都與前一個三角形共享一邊，圖14.2顯示了一個三角帶的例子。

注意頂點列出的順序使得每三個連續的點都能構成一個三角形。例如：

頂點1、2、3構成第一個三角形。
.
頂點2、3、4構成第二個三角形。
.
頂點3、4、5構成第三個三角形。

在圖14.2中，頂點以構成三角形帶的順序編號。"索引"信息不再需要，因為頂點順序已經隱式定義了三角形。通常，列表前部有頂點數目，或末尾處有一特殊碼表示"列表結束"。

注意到，頂點順序在順指針和逆時針間不斷變換（見圖14.3）。某些平臺上，需要指出第一個三角形的頂點順序，而有些平臺上順序是固定的。

最佳情況下，三角帶可用n+2個頂點存儲n個面。n很大時，每個三角形平均發送一個頂點，遺憾的是，這只是最佳情況。實踐中，很多網格是一個三角形帶無法表達的，不僅如此，3個以上三角形共享的頂點還是要多次發送給圖形卡。從另一方面說，每個三角形至少要發送一個頂點。但在頂點緩存機制中，有可能將每個三角形發送的頂點數降到一個以下。當然，頂點緩存需要額外的簿記信息（索引和緩存管理數據），可是盡管這些額外信息對單個頂點來講相對較大，操作速度也會相對下降，但發送頂點數最少的系統在特定平臺上速度最快。

假設用一種生成三角帶的直接方法，用三角帶表示三角網需要的頂點數為t+2s，t為三角形數目，s為三角帶數目。每個三角帶的第一個三角形對應三個頂點，以后每個三角形對應一頂點。因為我們希望最小化發往圖形卡的頂點數，所以三角帶的數目應盡可能少，即三角帶越長越好。STRIPE方法給出了一種三角帶數目接近理論下限的生成手段。

另一個希望減少三角形帶數目的原因在于建立各三角形需要額外時間。從另一方面說，分別渲染兩個長為n的三角帶所需時間長于渲染一個長為2n的三角帶，即使這個三角帶中的三角形數多于兩個分開帶中三角形數量的和。于是，我們經常通過使用退化三角形連接多個三角帶，從而將整個網格置于一個連續的三角帶中，退化的意思是面積為0。圖14.4顯示了如何重復頂點以將兩個三角形合并為一個。

圖14.4的含義不太明顯，但這里有四個退化三角形用于連接兩個三角帶從而維持正確的順指針、逆時針順序。頂點7、8間的邊實際包含兩個退化三角形，圖14.5指出了圖14.4中包含的三角形。

退化三角形面積為0不需要渲染，所以不會影響效率。實際上要發送到圖形卡的頂點仍然只是第一列的頂點：

1，2，3，4，5，6，7，8，9，10，11，12，13

這符合我們每三個連續頂點表示一個三角形的約定。

一些硬件（如PS2上的GS）可以跳過三角帶中的三角形，方法是通過一個頂點上的標志位指出"不必繪制"此三角形。這給我們一種方法可以有效的從任意點開始新三角形帶而不必重復頂點或使用退化三角形。例如，圖14.4中的兩個三角帶可以如圖14.6那樣連接，其中灰色表示頂點被標記"不必繪制"。

2.3 三角扇

三角扇和三角帶類似，但不如三角帶靈活，所以很少使用。圖14.7所示即為三角扇。

三角扇使用n+2個頂點存儲n個面，和三角帶相同。但是，第一個頂點必須為所有三角形共享，所以實踐中不太經常能找到大型三角扇應用的場合。并且，三角扇不能像三角帶那樣連接。所以，三角扇只能在特殊場合應用，對一般應用來說，三角帶更靈活。

3 三角形網格可在三角形或頂點級保存額外信息。

3.1 紋理映射坐標

紋理映射是將位圖（稱作"紋理圖"或簡稱"紋理"）貼到多邊形表面的過程。這里只給出一個高度簡化的解釋：我們希望將2D紋理貼到多邊形表面上，同時考慮多邊形在攝像機空間的方向。對多邊形中每個需要渲染的像素都要計算2D紋理映射坐標，這些坐標用以索引紋理圖，從而為相應像素著色。

通常，在頂點保存紋理映射坐標，三角形面中其余各點的坐標通過插值進行計算。

3.2 表面法向量

許多應用程序中，網格上的各點都需要一個表面法向量。它可以用來：

計算光照。
.
進行背面剔除。
.
模擬粒子在表面"彈跳"的效果。
.
通過只考慮正面而加速碰撞檢測。

表面法向量可能保存于三角形級或頂點級，或兩者皆有。

三角形級法向量可以通過兩向量叉乘的方法輕松獲得，而頂點級法向量的計算則困難一些。首先，應注意到頂點處其實是沒有法向量定義的，因為此處網格表面不連續。第二，三角網是對連續表面的逼近，所以我們實際想要的是連續表面的法向量。根據產生三角網的方法，這種信息不一定現成可得。如果網格是自動生成的，比如說從參數曲面上，則可以直接獲得法向量。

若法向量沒有提供，則必得有現成數據（頂點位置和三角形）生成。一個技巧是平均相鄰三角形的表面法向量并將結果標準化。當然，這要求知道三角形法向量。一般可以假設三角形頂點以順時針列出，通過叉乘計算外表面的法向量。如果頂點順序不能假設時，可使用Glassner建議的方法。

通過平均三角形法向量求得頂點法向量是一種經驗性方法，大多數情況下都能工作得很好。但是有必要指出，某些情況下，其結果并不是所期望的。最明顯的例子是兩個法向量剛好相反的三角形共享一個頂點。這種情形常發生在"公告板"物體上。"公告板"由兩個三角形背靠背構成，它的兩個法向量方向恰好相反，其平均值為0不能標準化。為解決這種問題，必須拆開所謂的"雙面"三角形。

平均頂點法向量的另一個問題會在應用Gouraud著色時發生，這里給出一個簡化的解釋：光照是按頂點法向量逐點計算的。如果使用平均三角形法向量計算的頂點法向量，某些應該有尖銳邊緣的地方會顯得"過于平滑"。以最簡單的盒子為例，邊緣處應該有一個劇烈的關照變化。如果我們使用平均頂點法向量，這個劇烈變化會消失。如圖14.8所示：

根本問題在于盒子邊緣不連續，而這種不連續卻不能很好的被表達，因為每個頂點只有一個法向量。其實仍然可以使用面拆分解決問題：換句話說，重復不連續處的頂點。這樣做之后，人為的構造了一個不連續以防止頂點法向量被平均。這種"裂縫"在網格拓撲中可能會導致問題，但在如渲染、光線追蹤等任務中沒有問題。

另一個小問題是這種平均會導致結果向較多擁有相同法向量的三角形偏移。例如，若干三角形共享一個頂點，但其中兩個共面。則平均出的法向量會發生偏移，因為共面三角形的法向量重復了兩次，相比于其他法向量有更多"發言權"。于是，即使表面并未變化，也會使頂點法向量發生改變。我們可以修正此錯誤，但幸運的是實踐中這并不是什么大問題，因為頂點法向量本來就是一種近似。

3.3 光照值

另一種常由頂點維護的信息是光照值。這些光照值用于沿表面的插值，典型的方法是Gouraud著色。有些時候，頂點處僅保存法向量，渲染時動態計算光照值。

4 拓撲與一致性

三角網格的拓撲是指當在三角網格中不考慮頂點位置與其他幾何性質的邏輯連通性時，兩個頂點數相同且三角形互聯方式一致的三角網格為同拓撲的，即使它們對應的物體完全不同。從另一方面說，盡管形狀不同，拉伸網格但不打破鄰接性，我們得到的是同拓撲的網格。

有一種特殊網格稱作封閉網絡，又稱作"流形"。概念上，封閉網格完美地覆蓋物體表面，網格中沒有間隙，從外面完全無法看到任何三角形的背面。這是一種重要的網格，它的點和邊組成形式就像平面圖，即如果將頂點當成平面點，用直線連接頂點，此封閉網格可以畫在一個2D平面上，而且沒有邊交叉。平面圖符合Euler方程：v-e+f=2，其中v為頂點數，e為邊數，f為網格上的面數。

實踐中，我們經常遇到拓撲異常的三角網格，導致網格不封閉：

孤立頂點：頂點未被任何三角形使用。
.
重復頂點：完全相同的頂點。使用這些點的三角形幾何上相鄰而邏輯上不相鄰，多數情況下，我們不希望看到這種現象，應該刪除。
.
退化三角形：使用一頂點超過一次的三角形。意味著這個三角形沒有面積，一般這種三角形應該刪除。
.
開放邊：僅為一個三角形所使用。
.
超過兩個三角形共享的邊：封閉網格中，任一邊必須為兩個三角形共享。
.
重復面：網格中包含有兩個或更多相同的面。這是不希望看到的，應該去掉多余面而只保留一個。
.

根據應用的不同，上述異?？赡苁菄乐氐腻e誤，也可能是小錯誤，或者無關緊要。

5 逐三角形/點操作

三角網格是頂點和三角形的列表。三角網格的一系列基本操作都是逐點和逐三角形應用基本操作的結果。最明顯的，渲染和轉換都屬于這種操作。為渲染三角網格，我們逐個三角形渲染，如要向三角網格應用轉換，如旋轉和縮放等，應逐頂點進行。

5.1 焊接頂點

當兩個或更多頂點（也許有誤差）時，將它們焊接在一起是有益處的。更加準確地說，刪除其余的，只剩一個。例如，我們要焊接圖14.9中的A和B，有兩個步驟：

步驟1，掃描三角形列表，將對B的引用全部替換成對A的引用。
.
步驟2，現在B是孤立點，將它從頂點列表中刪除。

焊接頂點的目的有兩個。首先，去除重復頂點，節約內存。這是一種重要的優化方法，使得對網格的操作（如渲染和轉換）更快。其次，使幾何上相鄰的邊在邏輯上也是相鄰的。

上面討論的是兩個頂點的焊接，實踐中，我們常常希望找出與焊接點鄰近的所有頂點。這個想法是非常直接的，但有幾個細節需要明確。

（1）焊接前應去除孤立點，我們不想讓任何未被使用的點影響正被使用的點，如圖14.10所示：

（2）當兩個頂點均來自"細長"三角形，焊接可能產生退化三角形，如圖14.11所示（這和邊縮坍類似）。這樣的三角形應被刪除，通常它們的數量并不大。焊接常會顯著減少頂點數，同時也會除去一小部分細長面。

（3）焊接時，似乎應該用原頂點的平均作為新頂點，而不是簡單地選擇其中一個而拋棄另一個。這種方式不偏向任何一個頂點，，在只有少量頂點需要焊接時這似乎是個好主意。然而，焊接自動進行的時候可能引起"多米諾"效應，導致原來不在誤差容限內的多個點被焊接。

圖14.12中，點A和B在誤差容限內應被焊接。我們"聰明地"焊接這兩個點，計算A和B的平均值得到一個新的點D?，F在C和D又在容限范圍內被焊接，最終產生E。結果是點A和C被焊接了，它們本不在誤差容限內的。并且，我們"聰明的"嘗試也失敗了，因為A、B和C被焊接，但結果并不是這三個點的平均。

這還不是最壞的情形，至少沒有點跑出誤差容限外去。但確實可以故意用更多頂點和不同順序制造這種惡毒的例子，更不幸的是實踐中確實存在這種問題，建模程序和自動生成程序常這么干。其實，即使不平均生成新坐標，依然會有上面的問題。例如不考慮平均坐標，以為應用一個簡單的規則"總是將高序數頂點焊接到低序數頂點"就可以解決這個問題。

有一些防止出現上述問題的方法。比如，可以先找出所有誤差容限內的頂點組，再焊接它們；或者不考慮已經焊接過的頂點；或者記錄原頂點坐標，當頂點和它們相比在容限外時就不焊接。這些方法都過于復雜，我們不應為不顯著的性能而增加復雜性。焊接是為了去除重復頂點，而不是為了網格消減：即大量減少三角形數，而盡量保持三角網外形不變。關于網格消減，必須使用更加高級的算法。

另外一個問題是關于三角網的附加信息的，如表面法向量、紋理映射坐標等。當點焊接時，先前的不連續消失了，圖14.8就是一個例子。

最后，頂點焊接的直接實現非常慢。即使在當今的硬件條件下，數千個點和面的焊接也要用掉數秒鐘。尋找焊接頂點對的算法是O(n2)復雜度的。一次焊接后的頂點索引替換需要遍歷整個三角形列表；刪除一個頂點也需要遍歷三角形列表以修復比刪除點序號高的頂點的索引。幸運的是，加以思考，我們可以找到一個快得多的算法。

5.2 面拆分

面拆分即復制頂點，使邊不再被共用，它和焊接剛好相反。顯然，面拆分會導致拓撲間斷，因為面不再鄰接。而這正是我們的目的，使得幾何間斷的地方拓撲也是間斷的（如角和邊）。圖14.13顯示了兩個三角形的拆分，盡管我們把兩個三角形分開以顯示這里有多個邊和頂點，這只是為了顯示，頂點沒有移動，新的頂點和邊其實是重合的。

實踐中，我們經常要拆分所有面。

5.3 邊縮坍

邊縮坍是將邊縮減為頂點的方法，與之對應的是頂點拆分。如圖14.14所示，注意到邊縮坍使邊的兩個頂點變為一個，共享該邊的三角形（圖14.14中陰影部分）消失。邊縮坍常用于網格消減，因為它減少了頂點和三角形數量。

5.4 網格消減

網格消減是將三角形和頂點數較多的網格變為三角形和頂點數相對較少的網格，并且要求網格外觀和主要頂點盡可能保持不變。Hugues Hoppe指出zhi只用邊縮坍就可以達到好的效果，選擇要縮坍的邊相對費時，視啟發方法的復雜性而定。盡管選取縮坍對象的時間較長，但縮坍操作本身并不復雜。我們可將此過程離線記錄下來，在實時需要時"重放"它，即可得到任意精細程序的風格。Hoppe的論文描述了如何利用頂點拆分來反演邊縮坍過程，用此反演法生成的網格稱為漸進式網格。

posted on 2011-11-01 22:34 情絕格調(fresmaster) 閱讀(2513) 評論(0) 編輯收藏引用所屬分類: Graphics

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: glAlphaFunc in OpenGL ES2.0 Gamma Correction Hemi-Sphere Lighting Light Mapping GLSL.Ambient occlusion GLSL.High Dynamic Range GLSL.Depth Of Field GLSL.Image post-processing GLSL.Parallax mapping GLSL.Refract & Reflect & Diffraction

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品