第06章 翼边数据结构：拓扑表示的鼻祖与工程取舍

本章定位：翼边数据结构（Winged-Edge, WE）是三维实体造型史上第一个系统化的多面体拓扑数据结构。本章从图论与可定向曲面理论出发，建立翼边结构的代数模型，推导其不变量与遍历复杂度，并通过与半边结构（Half-Edge, HE）的系统对比，揭示"集中存储 vs 分散存储"这一工程取舍的深层逻辑。

---

摘要

翼边数据结构由 MIT 的 Bruce Baumgart 于 1975 年在其博士论文中提出，是三维实体造型领域第一个系统化的多面体拓扑数据结构。其核心思想是在每条边上集中存储全部邻接信息——两个端点、两侧面以及两端点处的四条"翼"边，共计 8 个指针。本文从图论与可定向曲面理论出发，建立翼边结构的代数模型，严格推导其不变量、欧拉操作合法性条件与遍历复杂度；通过引入邻接信息熵与更新代价函数两个度量，定量比较翼边与半边结构的工程特性；并以欧拉操作 mef 为例，逐步剖析翼边更新复杂性的根源。分析表明：翼边在查询灵活性上具有优势，但在更新局部性上处于劣势；半边结构通过"一分为二"的拆分将更新局部化，从而在工程上胜出。翼边结构虽然已被主流几何内核淘汰，但作为拓扑数据结构的鼻祖，其设计思想对现代图数据库、知识图谱的边中心存储仍有借鉴价值。

关键词：翼边结构；半边结构；拓扑数据结构；欧拉操作；可定向曲面；邻接信息熵

---

6.1 概述与背景

翼边数据结构（Winged-Edge Data Structure，简称 WE 结构）是三维实体造型历史上第一个系统化的多面体拓扑数据结构，由 MIT 的 Bruce Baumgart 在 1975 年的博士论文《Winged-Edge Polyhedron Representation for Computer Vision》中提出。

虽然它在今天的主流几何内核中已基本被半边结构（第 5 章）和辐射边结构（第 7 章）取代，但理解翼边结构仍有不可替代的价值：

1. 历史地位：它是后续所有边数据结构的鼻祖，半边与辐射边都是在其基础上的简化或扩展，理解翼边就理解了这一族结构的共同出发点；
2. 设计思想：翼边"在一条边上集中存储其全部邻接信息"的思想，在某些查询模式下仍有参考价值；
3. 经典文献：许多经典教材（Mantyla 1988）以翼边为入门结构，理解它有助于阅读经典文献；
4. 工程教学：翼边结构的兴衰是"复杂 vs 简洁"工程取舍的经典案例，对软件设计有教学意义。

翼边结构的核心思想是：在每条边上集中存储它的全部邻接信息——两个端点、两侧的两个面、以及两端点处的"翼"（顺时针与逆时针的下一边）。之所以叫"翼边"，是因为从一条边看出去，两端各有两条邻边像翅膀一样展开。这种集中存储使从一条边出发的邻接查询非常灵活——一次访问就能拿到边的所有拓扑邻居。但代价是更新操作复杂：插入或删除一条边需要更新四个邻边的多个指针，容易出错。正是这一更新复杂性促使 Weiler 后来提出半边结构来简化。

本章创新点：引入邻接信息熵 $H_{\text{adj}}$ 度量拓扑结构的查询效率，引入更新代价函数 $C_{\text{update}}$ 度量修改操作的复杂度，通过二者的权衡分析，定量解释"为何半边取代翼边"这一工程史实。

---

6.2 历史与发展演进

翼边结构诞生于 1970 年代中期计算机视觉与实体造型的交汇。Baumgart 在 MIT 做计算机视觉研究时，需要从多视图重建三维多面体并维护其拓扑，于 1975 年提出翼边结构。同期剑桥的 Braid 在开发 BUILD-1 实体造型系统，也面临拓扑维护问题。翼边结构是第一个把"边"作为拓扑枢纽、在其上集中存储邻接信息的数据结构，开创了以边为中心的拓扑表示范式。

6.2.1 演进时间线

年份	事件	关键贡献
1975	Baumgart 提出翼边结构	第一个以边为中心的拓扑数据结构
1978	Baumgart 提出半翼边（Half-Winged Edge）	简化版的初步尝试
1986	Weiler 系统化半边结构	“一条边存两侧"改为"两个半边各存一侧”
1980s	Weiler 提出辐射边结构	支持非流形，ACIS 采纳
1988	Mantyla 教材以翼边入门	教学长期保留翼边

至此，以边为中心的拓扑数据结构族完成：翼边（鼻祖）→ 半边（流形简化）→ 辐射边（非流形扩展）。

6.2.2 工程淘汰与教学保留

在教材方面，Mantyla 1988 的《An Introduction to Solid Modeling》以翼边为入门结构，使翼边在教学中长期保留。但工程实现中，翼边已基本淘汰——OCCT、CGAL、Parasolid 都不用纯翼边。翼边今天主要见于教材与历史文献。

演进规律：拓扑数据结构的演进遵循"查询-更新权衡"原则：查询效率的提升往往以更新复杂度为代价，反之亦然。翼边选择了"查询集中、更新分散"，半边选择了"查询分散、更新集中"——工程实践表明，在交互式建模场景中更新频率远高于极端查询频率，因此更新局部性成为决定性因素。

---

6.3 核心概念与定义

6.3.1 翼边的形式化定义

定义 6.1（翼边） 设 $M$ 为可定向闭合多面体，$e$ 为 $M$ 的一条有向边，$e:v_s\to v_e$。翼边结构为 $e$ 关联以下 8 个指针：

$$\text{WE}(e)=⟨v_s,v_e,f_L,f_R,e_{LC},e_{LCC},e_{RC},e_{RCC}⟩$$

其中：

• $v_s,v_e$：边 $e$ 的起点与终点；
• $f_L,f_R$：沿 $e$ 方向看，$e$ 的左侧面与右侧面；
• $e_{LC},e_{LCC}$：左面 $f_L$ 内，$v_s$ 端与 $v_e$ 端的邻边（顺时针/逆时针）；
• $e_{RC},e_{RCC}$：右面 $f_R$ 内，$v_s$ 端与 $v_e$ 端的邻边（顺时针/逆时针）。

定义 6.2（翼） 从边 $e$ 看，在面 $f$ 内 $e$ 的两端各有一条邻边（因为面是环），这两条邻边像翅膀从 $e$ 展开，称为 $e$ 在 $f$ 内的翼。顺逆时针区分两端。

6.3.2 邻接信息熵

定义 6.3（邻接信息熵） 设拓扑结构中从任一元素出发，一次访问可获得的邻接元素数期望为 $k$，则定义：

$$H_{\text{adj}}={\log }_{2}k$$

单位为比特（bit）。$H_{\text{adj}}$ 越大，单次访问获得的信息越多，查询效率越高。

对翼边结构，从边 $e$ 出发一次访问可得：2 端点 + 2 面 + 4 翼边 = 8 个邻接元素，故：

$$H_{\text{adj}}^{\text{WE}}={\log }_{2}8=3\text{ bit}$$

对半边结构，从半边 $h$ 出发一次访问可得：1 起点 + 1 面 + 1 对偶半边 + 1 后继 + 1 前驱 = 5 个邻接元素，故：

$$H_{\text{adj}}^{\text{HE}}={\log }_{2}5\approx 2.32\text{ bit}$$

结论：翼边的邻接信息熵比半边高约 $29\%$，查询效率更高——这是翼边"集中存储"优势的定量表达。

6.3.3 更新代价函数

定义 6.4（更新代价函数） 设某拓扑操作的更新步骤涉及 $n_p$ 个指针写入，且指针分散在 $n_e$ 个元素上，则定义更新代价：

$$C_{\text{update}}=n_p+\lambda \cdot n_e$$

其中 $\lambda >0$ 为分散惩罚系数（反映跨元素更新的缓存失效与出错概率）。

以“分裂面”操作 mef 为例：

• 翼边：需更新 5 条边的多个指针，$n_p\approx 16$，$n_e=5$，$C_{\text{update}}^{\text{WE}}=16+5\lambda$；
• 半边：需更新 4 个半边的局部指针，$n_p\approx 8$，$n_e=4$，$C_{\text{update}}^{\text{HE}}=8+4\lambda$。

当 $\lambda \approx 2$ 时，$C_{\text{update}}^{\text{WE}}\approx 26$，$C_{\text{update}}^{\text{HE}}\approx 16$，半边更新代价低约 $38\%$。

6.3.4 方向约定与不变量

方向约定（Mantyla 约定）：从边方向 $v_s\to v_e$ 看，左面 $f_L$ 在左、右面 $f_R$ 在右；顺逆时针从面外看。

不变量（Invariants） 合法翼边结构需满足：

1. 流形性：每条边的左右面不同，即 $f_L\ne f_R$；
2. 翼对偶性：若 $e^{\prime }=e_{LC}(e)$，则 $e$ 是 $e^{\prime }$ 在相应位置的翼，即 $e_{RC}(e^{\prime })=e$ 或 $e_{RCC}(e^{\prime })=e$；
3. 遍历闭合性：从任一元素出发沿翼遍历，必回到起点。

这些不变量比半边更复杂，维护更难——这正是翼边被淘汰的结构性原因。

---

6.4 技术原理详解

6.4.1 邻接查询

翼边结构的邻接查询能力如下：

查询目标	操作	复杂度
边的端点	edge.startVertex、edge.endVertex	$O(1)$
边两侧面	edge.leftFace、edge.rightFace	$O(1)$
面的所有边	从面任一邻边出发，沿翼遍历	$O(n_f)$
顶点的所有邻边	从顶点任一邻边出发，沿翼遍历	$O(d_v)$

其中 $n_f$ 为面的边数，$d_v$ 为顶点的度。

面的边遍历比半边复杂——半边直接 next 链，翼边需根据"当前边在面的哪一侧"选择对应的翼指针。这增加了遍历代码的分支。

6.4.2 遍历复杂度分析

定理 6.1（翼边面遍历复杂度） 遍历面 $f$ 的所有 $n_f$ 条边，翼边结构需 $n_f$ 次分支判断 + $n_f$ 次指针访问，总复杂度为：

$$T_{\text{WE}}(f)=n_f\cdot (c_{\text{branch}}+c_{\text{ptr}})$$

半边结构仅需 $n_f$ 次指针访问：

$$T_{\text{HE}}(f)=n_f\cdot c_{\text{ptr}}$$

其中 $c_{\text{branch}}>0$ 为分支判断代价。故：

$$\frac{T_{\text{WE}}}{T_{\text{HE}}}=1+\frac{c_{\text{branch}}}{c_{\text{ptr}}}>1$$

现代 CPU 上分支预测失败代价约 $10\sim 20$ 周期，指针访问约 $1\sim 4$ 周期，故翼边遍历实际比半边慢 $3\sim 6$ 倍。

6.4.3 更新操作：以 mef 为例

以“在面内加一条边分裂面”（mef，Make Edge-Face）为例，剖析翼边的更新复杂性。

翼边版 mef 步骤：

1. 创建新边 $e_{\text{new}}$，设其端点 $v_1,v_2$；
2. 找原面 $f$ 中 $v_1,v_2$ 处的邻边 $e_1,e_2$；
3. 设 $e_{\text{new}}$ 的左右面、翼边指针——需正确指向 $e_1,e_2$ 及其翼；
4. 更新 $e_1,e_2$ 的翼指针指向 $e_{\text{new}}$；
5. 更新 $e_1,e_2$ 的其他翼的指针（因为翼对偶性）；
6. 创建新面 $f_{\text{new}}$，更新相关边的面指针。

每步都涉及多个指针更新，且需保持顺逆时针约定一致。相比半边的“局部 4 指针更新”，翼边更新要改 5 条边的多个指针，易出错。

半边版 mef 步骤：

1. 创建两条对偶半边 $h_{\text{new}},h_{\text{new}}^{\prime }$；
2. 拆分原半边链，插入 $h_{\text{new}},h_{\text{new}}^{\prime }$；
3. 创建新面 $f_{\text{new}}$，设 $h_{\text{new}}.\text{face}=f_{\text{new}}$。

仅涉及 4 个半边的局部指针更新，且每步独立。

6.4.4 非流形限制

翼边假设每条边恰好两侧各一面（流形）。非流形（多面沿一边）无法表示，需辐射边。

定理 6.2（翼边的流形性约束） 翼边结构能表示的拓扑集合恰为可定向闭合 $2$-流形多面体。非流形边（如三面共享一边）在翼边中无对应表示。

---

6.5 数学理论与公式推导

6.5.1 边定向与左右面

命题 6.1 在可定向曲面 $S$ 上，一条有向边 $e:v_s\to v_e$ 把局部曲面分为左右两侧，$f_L$ 与 $f_R$ 由 $S$ 的定向唯一确定。

证明：可定向曲面 $S$ 上存在连续非零法向量场 $\mathbf{n}:S\to {\mathbb{R}}^3$。沿 $e$ 方向取切向量 $\mathbf{t}$，则 $\mathbf{n}\times \mathbf{t}$ 指向 $e$ 的左侧，$-\mathbf{n}\times \mathbf{t}$ 指向右侧。$f_L$ 是左侧面、$f_R$ 是右侧面，由 $\mathbf{n},\mathbf{t}$ 唯一确定。$\square$

这对应半边的两个有向半边各属一面：$h_L$ 属 $f_L$，$h_R$ 属 $f_R$。

6.5.2 翼边的图论基础

定义 6.5（边图） 多面体 $M$ 的边图 $G(M)=(V,E)$，顶点为 $M$ 的顶点，边为 $M$ 的边。

命题 6.2 多面体 $M$ 的边图 $G(M)$ 中，每个顶点的邻边形成一个循环（面环绕顶点）。

证明：顶点 $v$ 处的所有面环绕 $v$，形成一个面环（face cycle）。每个面在 $v$ 处贡献两条邻边，这些邻边按面环顺序构成 $v$ 的邻边循环。$\square$

翼边结构在边上存“端点处的循环邻边”，即存了边图的邻接信息。这与半边存“环内 next”是同一信息的不同组织。

6.5.3 欧拉公式与不变量

定理 6.3（欧拉公式） 对亏格 $G$ 的闭合可定向多面体：

$$V-E+F=2-2G$$

翼边结构表示的闭合多面体满足此式。翼边不变量（左右面不同、翼遍历闭合）是欧拉操作合法性的保证。

推论 6.1 翼边结构的所有欧拉操作（mef、kemr、mev、kev 等）必须保持 $V-E+F$ 不变。这是欧拉操作合法性的代数判据。

6.5.4 遍历复杂度定理

定理 6.4（翼边遍历复杂度） 遍历翼边结构的面 $f$（$n_f$ 条边），时间复杂度为：

$$T_{\text{WE}}(f)=\Theta (n_f)$$

与半边同阶，但实际常数大于半边（因需分支判断左右面）。

定理 6.5（邻接信息熵上界） 任何以边为中心的拓扑数据结构，其邻接信息熵满足：

$$H_{\text{adj}}\le {\log }_2(2+2+2\cdot \bar{d})={\log }_2(4+2\bar{d})$$

其中 $\bar{d}$ 为平均顶点度。翼边达到 $3$ bit（$\bar{d}=2$），已接近上界。

---

6.6 算法与数据结构详解

6.6.1 翼边结构类定义

struct WingedEdge {
    Vertex* start;              // 起点
    Vertex* end;                // 终点
    Face*   leftFace;           // 左侧面
    Face*   rightFace;          // 右侧面
    WingedEdge* leftCW;         // 左面 start 端顺时针邻边
    WingedEdge* leftCCW;        // 左面 end 端逆时针邻边
    WingedEdge* rightCW;        // 右面 start 端顺时针邻边
    WingedEdge* rightCCW;       // 右面 end 端逆时针邻边
};

struct Vertex {
    Point3D point;
    WingedEdge* edge;           // 任一邻边
};

struct Face {
    WingedEdge* edge;           // 任一邻边
    Surface* surface;
};

6.6.2 遍历面的所有边

翼边版：

std::vector<WingedEdge*> iterateFaceEdgesWE(Face* face) {
    std::vector<WingedEdge*> result;
    WingedEdge* e0 = face->edge;
    WingedEdge* e = e0;
    do {
        result.push_back(e);
        // 判断 e 在 face 的哪一侧
        if (e->leftFace == face) {
            e = e->leftCW;      // 沿左面顺时针前进
        } else {
            e = e->rightCW;     // 沿右面顺时针前进
        }
    } while (e != e0);
    return result;
}

半边版：

std::vector<HalfEdge*> iterateFaceEdgesHE(Face* face) {
    std::vector<HalfEdge*> result;
    HalfEdge* h0 = face->outerLoop;
    HalfEdge* h = h0;
    do {
        result.push_back(h);
        h = h->next;            // 直接 next，无需分支
    } while (h != h0);
    return result;
}

半边无需“判断在哪一侧”的分支，直接 next，更简洁高效。这是半边胜出的体现。

6.6.3 分裂面 mef（翼边版）

void splitFaceWE(Face* face, Vertex* v1, Vertex* v2) {
    // 1. 找 v1, v2 在 face 中的邻边
    WingedEdge* e1 = findEdgeAt(face, v1);
    WingedEdge* e2 = findEdgeAt(face, v2);

    // 2. 创建新边
    Face* newFace = new Face();
    WingedEdge* eNew = new WingedEdge();
    eNew->start = v1;
    eNew->end = v2;
    eNew->leftFace = face;
    eNew->rightFace = newFace;

    // 3. 设翼指针——需仔细按顺逆时针约定
    eNew->leftCW  = e1->对应翼;
    eNew->leftCCW = e2->对应翼;
    eNew->rightCW = e2;
    eNew->rightCCW = e1;

    // 4. 更新 e1, e2 及其翼的指针指向 eNew
    // ... 多个指针更新（易错）

    // 5. 创建新面
    newFace->edge = eNew;
}

更新步骤明显比半边的 mef 多，且易错。这是翼边被淘汰的工程原因。

6.6.4 半边版 mef（对比）

void splitFaceHE(Face* face, Vertex* v1, Vertex* v2) {
    // 1. 找 v1, v2 在 face 中的半边
    HalfEdge* h1 = findHalfEdgeAt(face, v1);
    HalfEdge* h2 = findHalfEdgeAt(face, v2);

    // 2. 创建两条对偶半边
    Face* newFace = new Face();
    HalfEdge* hNew  = new HalfEdge();
    HalfEdge* hNewT = new HalfEdge();  // twin

    // 3. 插入链
    hNew->next = h2;
    hNew->prev = h1;
    h2->prev = hNew;
    h1->next = hNew;

    hNewT->next = h1;
    hNewT->prev = h2;
    h1->prev = hNewT;
    h2->next = hNewT;

    // 4. 设面
    hNew->face = face;
    hNewT->face = newFace;

    // 5. 设端点
    hNew->origin = v1;
    hNewT->origin = v2;
}

仅涉及 4 个半边的局部指针更新，且每步独立。

---

6.7 主流软件实现对比

6.7.1 内核实现现状

主流内核均不使用纯翼边：

内核	拓扑结构	说明
OCCT	TopoDS_*	半边思想
Parasolid	状态机	混合拓扑
CGM	容差拓扑	工程化半边
ACIS	辐射边	支持非流形
CGAL	半边	教学与算法
OpenMesh	半边	学术与图形学

翼边在工程中已淘汰。

6.7.2 与半边的取舍

维度	翼边	半边
指针/边	8	10（5 × 2）
邻接信息熵	3 bit	2.32 bit
遍历分支	有	无
更新代价	高	低
更新局部性	差	好
工程采用	否	是

核心结论：半边总指针略多但更新局部，翼边总指针少但更新全局。工程上更新频率高，半边胜。

6.7.3 与辐射边的关系

辐射边在翼边/半边基础上支持非流形，是另一维度的扩展。翼边 → 半边（简化更新） 与 翼边 → 辐射边（扩展非流形） 是两条演进线。

---

6.8 操作步骤教程

6.8.1 步骤一：对比翼边与半边遍历

写两段伪代码（如上 6.6.2 节）对比面遍历。翼边需分支判断左右面，半边直接 next。亲手实现两版本，体会半边的简洁。

6.8.2 步骤二：用 CGAL 半边理解翼边的简化

CGAL Polyhedron_3 用半边，遍历面边用 he->next()。对比翼边需判断左右面选翼指针，体会半边如何把翼边的分支消除。

// CGAL 半边遍历面
for (auto h = f->facet_begin(); h != f->facet_end(); ++h) {
    // 直接 next，无分支
}

6.8.3 步骤三：阅读 Mantyla 教材

Mantyla 1988 以翼边讲欧拉操作，对照半边实现，理解欧拉操作在两种结构下的差异。

6.8.4 步骤四：实现简易翼边结构

用 Python 实现一个简易翼边结构建立方体，遍历面边、做一次 mef。对比同功能半边实现的代码量与出错率。

class WEdge:
    def __init__(self):
        self.start = self.end = None
        self.leftFace = self.rightFace = None
        self.leftCW = self.leftCCW = None
        self.rightCW = self.rightCCW = None

# 建立方体需为 12 边各设 8 指针，代码冗长易错
# 对比半边每半边只设 5 指针

6.8.5 步骤五：理解为何被淘汰

通过步骤四的实现，亲身体会翼边更新的复杂——这是它被半边取代的根本原因。

---

6.9 应用场景与案例

6.9.1 1970s 计算机视觉多视图重建

Baumgart 用翼边从多视图重建多面体，翼边的集中邻接信息支持高效的拓扑验证与遍历。历史意义：这是拓扑数据结构首次服务于计算机视觉任务。

6.9.2 早期实体造型系统

BUILD-1 等早期系统探索过翼边类结构，后转向半边。

6.9.3 教学价值

翼边是理解拓扑数据结构演进的入门，许多课程用它讲“为何半边更好”。教学要点：

1. 理解"集中存储 vs 分散存储"的工程取舍；
2. 理解拓扑不变量的维护复杂度；
3. 理解数据结构演进的历史逻辑。

6.9.4 现代借鉴

翼边"集中存邻接"的思想在现代图数据库、知识图谱的边中心存储中仍有借鉴价值。例如：

• 属性图模型：边存储端点、属性、索引；
• RDF 三元组：主语-谓语-宾语的边中心表示；
• 超图数据库：边可连接多个顶点的扩展。

创新借鉴：将翼边的"边集中存储"思想推广到图神经网络的消息传递——每条边在传播时聚合两端节点与邻边的信息，与翼边的邻接信息集中有相似之处。

---

6.10 常见问题与调优

6.10.1 更新操作易错

问题：翼边的多指针更新易遗漏或设错。

调优：

• 改用半边；
• 若必须用翼边，仔细按约定逐步设指针并验证不变量；
• 引入不变量检查器，每次更新后验证三条不变量。

6.10.2 遍历需分支

问题：面遍历需判断左右面选翼指针，代码复杂。

调优：

• 半边直接 next；
• 若必须用翼边，可在面内预存遍历起点与方向，减少分支。

6.10.3 非流形不支持

问题：翼边假设流形。

调优：辐射边。

6.10.4 内存未必省

问题：翼边 8 指针/边 vs 半边 10 指针/边，翼边略省但更新代价抵消。

调优：现代更关注更新频率，选半边。

6.10.5 误以为翼边"更先进"

问题：实际翼边是鼻祖但已被半边取代。

调优：理解演进，选半边或辐射边。

---

6.11 发展趋势与展望

6.11.2 思想借鉴

翼边"集中存储邻接"的思想在某些图查询场景仍有参考价值（如知识图谱的边集中存储邻居）。

现代映射：

翼边概念	现代对应
边集中存端点	图的边表
边集中存面	图的边属性
翼边存邻边	图的邻接边索引

6.11.2 思想借鉴

翼边"集中存邻接"的思想在某些图查询场景仍有参考价值（如知识图谱的边集中存邻居）。

现代映射：

翼边概念	现代对应
边集中存端点	图的边表
边集中存面	图的边属性
翼边存邻边	图的邻接边索引

6.11.3 演进研究

研究新结构时常回溯翼边作起点，理解"集中 vs 分散"取舍。

6.11.4 未来方向

• GPU 友好拓扑：翼边的集中存储在 GPU 上可能因缓存友好而有新价值；
• 可微分拓扑：翼边的不变量可作为可微分约束；
• 量子拓扑：拓扑不变量的量子计算表示。

---

6.12 小结

翼边数据结构由 Baumgart 1975 提出，是三维实体造型第一个系统化拓扑数据结构。核心思想是在每条边上集中存储 8 个邻接指针（2 端点 + 2 面 + 4 翼边），使从边出发的邻接查询灵活。但更新操作复杂（需改多条边多个指针），促使 Weiler 1986 提出半边结构简化。翼边今天已基本被半边（流形）与辐射边（非流形）取代，无主流内核使用，但作为鼻祖有教学与历史价值。

核心要点：

1. 邻接信息熵：翼边 $H_{\text{adj}}=3$ bit，半边 $H_{\text{adj}}=2.32$ bit，翼边查询更高效；
2. 更新代价：翼边 $\sim 26$，半边 $\sim 16$，半边更新更经济；
3. 工程取舍：更新频率高于查询频率时，选半边；
4. 演进规律：翼边 → 半边（简化更新）与翼边 → 辐射边（扩展非流形）是两条演进线。

理解翼边是理解拓扑数据结构演进（翼边 → 半边 → 辐射边）的起点，也是理解"集中 vs 分散"工程取舍的经典案例。

---

6.13 延伸阅读

• Baumgart, B. Winged-Edge Polyhedron Representation for Computer Vision. MIT AI TR-74, 1975.
• Mantyla, M. An Introduction to Solid Modeling. Computer Science Press, 1988. —— 以翼边入门的经典教材。
• Weiler, K. “Topology as a Framework for Computational Geometry.” SIGGRAPH Course Notes, 1986. —— 半边取代翼边。
• Kettner, L. “Using Generic Programming for Designing a Data Structure for Polyhedral Surfaces.” Computational Geometry, 13(1):65-90, 1999. —— CGAL 半边设计。
• Botsch, M., et al. “OpenMesh: A Generic and Efficient Polygon Mesh Data Structure.” OpenSG Symposium, 2002. —— 现代半边实现。
• 本报告第 5 章半边、第 7 章辐射边。

---

参考文献

[1] Baumgart, B. G. (1975). Winged-Edge Polyhedron Representation for Computer Vision. MIT AI Technical Report TR-74.
[2] Mantyla, M. (1988). An Introduction to Solid Modeling. Computer Science Press.
[3] Weiler, K. (1986). Topology as a framework for computational geometry. SIGGRAPH Course Notes.
[4] Kettner, L. (1999). Using generic programming for designing a data structure for polyhedral surfaces. Computational Geometry, 13(1), 65-90.
[5] Botsch, M., Steinberg, S., Bischoff, S., & Kobbelt, L. (2002). OpenMesh: A generic and efficient polygon mesh data structure. OpenSG Symposium.
[6] Euler, L. (1758). Elementa doctrinae solidorum. Novi Commentarii Academiae Scientiarum Petropolitanae, 4, 109-140.