我們可以將離散表面表示為多邊形網格。 多邊形網格可以被認為是圖（具有頂點和頂點之間的邊）加上面列表，其中面是邊的環。

推薦： 使用 NSDT場景設計器 快速搭建 3D場景。

下面，我們將網格指定為頂點列表和面列表，其中每個面都指定為頂點環。 網格的邊是隱含的——邊連接面的相鄰頂點。

由於不含冗餘信息，面列表表示在磁碟存儲中很受歡迎，但是很難編寫直接在這種表示上運行的算法。 例如，判斷v6和v3是否連接，我們必須遍歷面列表，直到找到（或找不到）我們正在尋找的邊。

可以在恆定時間內回答此類查詢的流行數據結構是半邊（ HalfEdge）數據結構。 在半邊數據結構中，我們通過用一對有向半邊孿生表示每條邊來顯式存儲網格的邊，兩個半邊孿生中的每一個都指向相反的方向。 半邊存儲對其孿生的引用，以及對沿同一面或孔的前一個和下一個半邊的引用。 頂點存儲其位置和對源自該頂點的任意半邊的引用，而面存儲屬於該面的任意半邊。 半邊數據結構存儲頂點、面和半邊記錄的數組。

上圖為半邊 h 及其孿生、下一個和前一個半邊的可視化。 h 還存儲對其原始頂點和入射面的引用。

為了表示邊界邊緣（與孔相鄰的邊），我們有兩種選擇。 我們可以用雙指針為空的單個半邊表示邊界邊，或者我們可以將邊界邊表示為一對半邊，與孔相鄰的半邊具有空面指針。 事實證明，後一種設計選擇導致更簡單的代碼，因為我們很快就會看到獲得半邊的孿生是比獲得半邊的面更常見的操作，並且能夠簡單地假設我們有一個非空孿生導致的特殊情況要少得多。

下面我們展示了一個更複雜的網格的半邊圖和記錄表，要表示的網格如下圖所示：

可以在編輯器中編輯網格頂點和連接：

# Enter your mesh definition in OBJ format below...
v 1.0 4.0 0.0
v 3.0 4.0 0.0
v 0.0 2.0 0.0
v 2.0 2.0 0.0
v 4.0 2.0 0.0
v 1.0 0.0 0.0
v 3.0 0.0 0.0
f 1 3 4
f 1 4 2
f 2 4 5
f 3 6 4
f 4 6 7
f 4 7 5

對應的記錄如下：

遍歷面的頂點/邊

有時我們需要遍歷一個面以獲得它的所有頂點或半邊。 例如，如果我們想計算一個面的質心，我們必須找到面的所有頂點的位置。

在代碼中，給定面 f，這看起來像這樣：

start_he = f.halfedge
he = start_he
do {
    # do something useful

    he = he.next
} while he != start_he

請注意，我們使用 do-while 循環而不是 while 循環，因為我們想在循環疊代結束時檢查條件。 在第一次疊代開始時， he == start_he，因此如果我們在循環開始時檢查條件，我們的循環將不會運行任何疊代。

要以相反的方向遍歷面，可以簡單地將 he.next 替換為 he.prev。

圍繞一個頂點進行遍歷

前面我們描述了如何構造面疊代器。 另一個有用的疊代器是頂點疊代器。 通常，我們想要圍繞一個頂點疊代頂點環（也稱為頂點傘）。 更具體地說，我們想要遍歷所有以給定頂點為原點的半邊。

在本文中我們將假定面的頂點順序為逆時針（這是 OpenGL 中的默認設置）。

給定頂點 v，以逆時針順序遍歷所有從 v 出來的半邊，代碼如下所示：

start_he = v.halfedge
he = start_he
do {
    # do something useful

    he = he.prev.twin
} while he != start_he

請注意，即使存在邊界半邊或非三角形面，我們的代碼仍然有效。

以順時針順序遍歷頂點環與以逆時針順序遍歷環非常相似，只是我們將 he = he.prev.twin 替換為 he = he.twin.next。

修改半邊數據結構

前面我們討論了如何疊代面和頂點環。 修改半邊數據結構比較棘手，因為如果記錄修改不當，引用很容易變得不一致。

作為練習，我們將介紹如何實現 EdgeFlip 算法，給定兩個三角形面中間的半邊，翻轉半邊及其孿生的方向。

我們將在算法的每一步顯示記錄表。

我們從突出顯示的輸入半邊開始（下面網格中的 e3 或 e2，但假設是 e3）。

我們首先獲取所有受影響的半邊的引用，因為在網格處於不一致狀態時遍歷網格將很困難。

def FlipEdge(HalfEdge e):
    e5 = e.prev
    e4 = e.next
    twin = e.twin
    e1 = twin.prev
    e0 = twin.next

接下來，我們確保沒有對 e 或 twin（圖中的 e3 和 e2）的面或頂點引用，我們將在執行邊翻轉的過程中回收它們。

    for he in {e0, e1, e4, e5}:
        he.origin.halfedge = &he
    e1.face.halfedge = &e1
    e5.face.halfedge = &e5

這些操作是安全的，因為代表性半邊的選擇是任意的； 網格仍處於一致狀態。 受影響的單元格顏色為淺藍色，但並非所有單元格都更改為與其舊值不同的值。

接下來我們回收e和twin。 我們將（任意地）讓 e 成為圖中的頂部對角線半邊，並且 twin 成為它的孿生。 我們可以按照下圖填寫e和twin的成員。 在此之後，我們的數據結構將變得不一致。 我們用紅色勾勒出不一致的單元。

    e.next = &e5
    e.prev = &e0
    e.origin = e1.origin
    e.face = e5.face
    twin.next = &e1
    twin.prev = &e4
    twin.origin = e5.origin
    twin.face = e1.face

我們更新受影響的下一個和上一個參考。 同樣，我們可以參考圖表來填寫這些值。

    e0.next = &e
    e1.next = &e4
    e4.next = &twin
    e5.next = &e0
    e0.prev = &e5
    e1.prev = &twin
    e4.prev = &e1
    e5.prev = &e

原文連結：http://www.bimant.com/blog/halfedge-crash-tutorial/