多邊形網(wǎng)格處理系列第二篇

文章目錄

• • @[toc]
• 2. 網(wǎng)格數(shù)據(jù)結(jié)構(gòu)
• • 基于面的數(shù)據(jù)結(jié)構(gòu)
  • • 基本情況
    • 優(yōu)缺點
    • 改進(jìn)的face-based數(shù)據(jù)結(jié)構(gòu)
  • 基于邊的數(shù)據(jù)結(jié)構(gòu)
  • 基于半邊的數(shù)據(jù)結(jié)構(gòu)
  • • 基于有向邊的數(shù)據(jù)結(jié)構(gòu)
    • 小結(jié)

2. 網(wǎng)格數(shù)據(jù)結(jié)構(gòu)

• 判斷一種數(shù)據(jù)結(jié)構(gòu)的好壞標(biāo)準(zhǔn)包括（但不限于）：
  • 構(gòu)建它的時間
  • 響應(yīng)特定查找的時間
  • 執(zhí)行特定操作的時間
  • 存儲消耗與冗余

基于面的數(shù)據(jù)結(jié)構(gòu)

基本情況

• 每個面包含3個頂點位置，不能表示網(wǎng)格連接關(guān)系
• 也被稱為triangle soup或者polygon soup
• 一些數(shù)據(jù)轉(zhuǎn)換格式，如stereolighography（STL）使用這種這種表示方式
• 假設(shè)使用32 bit的單精度數(shù)表示頂點坐標(biāo)，則每個三角形需要3×3×4 bytes。再根據(jù)歐拉定理，面的個數(shù)大約是頂點的兩倍，因此總共可能需要72 bytes/vertex

優(yōu)缺點

• 不能顯式表示連接關(guān)系

  • 一些常見的操作不方便：
    • 訪問獨立的頂點、邊和面，使用非特定的順序
    • 有向遍歷一個面的所有邊，找到下一條/上一條邊
    • 訪問邊的相鄰面，根據(jù)朝向有左邊的面或右邊的面
    • 給定一條邊，訪問它的兩個端點
    • 給定一個頂點，至少一個相鄰面或者邊是可訪問的（one-ring neighborhood，1-鄰域）

• 頂點和對應(yīng)的數(shù)據(jù)會重復(fù)多次

  • 通過建立關(guān)于面的索引，可以大幅減少冗余數(shù)據(jù)，indexed face set 或shared-vertex。

indexed face se被廣泛用于OFF，OBJ，VRML；也被用于OpenGL vertex array

改進(jìn)的face-based數(shù)據(jù)結(jié)構(gòu)

• 頂點存儲坐標(biāo)之外，還存儲一個相鄰面（incident face）
• 面存儲對應(yīng)頂點之外，還存儲它的相鄰三角形（neighboring triangles）

通過增加連通信息，可以訪問到頂點的one-ring neighborhood，并執(zhí)行上述操作

• 這種改進(jìn)的數(shù)據(jù)結(jié)構(gòu)被用于CGAL，大約是24 bytes/face × 2 + 16 bytes/vertex = 64 bytes/vertex
• 這種數(shù)據(jù)結(jié)構(gòu)也有缺陷，不能顯式存儲邊；列舉一個中心頂點的one-ring需要區(qū)分不同情況

基于邊的數(shù)據(jù)結(jié)構(gòu)

泛用多邊形網(wǎng)格大多是基于邊的，蓋因連接關(guān)系主要與邊有關(guān)。最有名的edge-based data structure有winged-edge和quad-edge

• Winged-edge，每個邊存儲它的兩個端點，它的兩個鄰接面，它在左邊的面和右邊的面的下一條和上一條邊；每個頂點存儲它的相鄰邊（之一）；每個面存儲它的相鄰邊（之一）。總開銷16 bytes/vertex + 32 bytes/edge +4 bytes/face = 120 bytes/vertex
  
• 基于邊的表示可以表征任意多邊形，但是one-ring遍歷依然需要判斷不同情形。最終，被半邊結(jié)構(gòu)解決掉這個問題

基于半邊的數(shù)據(jù)結(jié)構(gòu)

• 半邊數(shù)據(jù)結(jié)構(gòu)的最大特點就是把原本不帶方向的邊分離成兩個不同方向的半邊，這種數(shù)據(jù)結(jié)構(gòu)可以表征任意有向的（orientable）2-manifolds（沒有復(fù)雜邊和頂點）多邊形網(wǎng)格
• 半邊數(shù)據(jù)結(jié)構(gòu)中，半邊之中按照逆時針（counterclockwise）順序環(huán)繞每個面和邊緣（boundary）。每個boundary可以看成是一個空的面。據(jù)此，每條半邊有唯一的角點（corner），這個角點可以存儲紋理坐標(biāo)、法向等
  
• 每個半邊存儲：
  • 它指向的頂點
  • 它的鄰接面（逆時針方向）
  • 這個面的下一條半邊（逆時針方向）
  • 這個面的上一條半邊
  • 以及它的反向邊

若半邊總是成對出現(xiàn)，可以不存儲;

上一條半邊也可以省略，蓋因用遍歷可以找到

• 相應(yīng)的，每個面存儲它的鄰接半邊；每個頂點存儲它的出邊
• 總存儲量大約是16 bytes/vertex + 20 bytes/halfedge × 6 + 4 bytes/face × 2 = 144 bytes/vertex
• 半邊數(shù)據(jù)結(jié)構(gòu)方便遍歷每種元素（頂點、邊、半邊、面）的相鄰元素，尤其方便one-ring enumeration

基于有向邊的數(shù)據(jù)結(jié)構(gòu)

Directed-edge data structure是一種節(jié)約存儲的半邊數(shù)據(jù)結(jié)構(gòu)的變種，專為三角形網(wǎng)格設(shè)計

因為每3條半邊組成一個三角形，所以一條半邊的鄰接面和它在這個鄰接面中的序號都是可以固定計算的：
$$\begin{gathered} face(h)=h/3 \\ fac{e}_{i}ndex(h)=h\mathrm{m}\mathrm{o}\mathrm{d}3 \end{gathered}$$
但是處理邊緣的時候比較棘手，需要使用特殊標(biāo)記，如負(fù)數(shù)來表示反向半邊是不存在的

類似的，也可以設(shè)置專為四邊形網(wǎng)格的有向邊數(shù)據(jù)結(jié)構(gòu)。但是這兩者是不能合并的。因此，除了存儲優(yōu)勢外，經(jīng)典半邊適用性更廣

小結(jié)

建議使用已有的數(shù)據(jù)結(jié)構(gòu)，如CGAL，OpenMesh，MeshLab等

總結(jié)

以上是生活随笔為你收集整理的【笔记】Polygon mesh processing读书笔记（2）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。