DCEL: Doubly-Connected Edge List，可直译为双连接边列表，也可称为半边结构以便理解。DCEL为我们提供了一种描述多边形网格的方式。通过该方式，我们很容易找到顶点，边或面片的邻域而无需搜索整个面片列表。 在接下来的定义中，我们会看到这种快速访问是非常有用的。
在给出DCEL的具体结构之前，先列出若干基本假设：
- 三维模型包含顶点、边、面片三部分结构，在空间中分别是0维、1维和2维的。面即为物体表面的某一多边形区域，边是相邻两个面的交线段或一个面的边缘，顶点为相邻边的交点。
- 每条边只与最多两个面相邻
- 每个面片均有自己的朝向，以区分内侧和外侧
- 两个相邻的面片朝向相同
总览
- 以半边的概念为核心。
DCEL结构将每个边拆分为两个方向相反的半边矢量，两个半边互称twins，均包含一个指向对方的指针，以及指向自己起始顶点坐标的指针。
这里的指针可以是字面意义上的C/C++语言中的指针变量，也可以是句柄/索引或其他寻址方式。只要满足快速访问目标对象的条件即可。
通常以半边的左侧为外部方向，该方向包含与其相邻的面片，右侧为内部方向，该方向包含该半边的twins。每个半边都仅与一个面片相邻。
详细数据结构
半边数据结构中包含了三种对象：顶点、半边和面片。每个对象均为固定长度，并包含了指向其他对象的指针。详细说明见下图：
有了上述基本结构之后，有时还需要一些额外信息作为支撑：
- 迭代器(Iterators)：使用数组或列表存储，用于完整遍历整个面片，保证每个半边结构都被访问到，且仅访问一次。
- 无穷面(The Infinite Face)：原始的定义没有解决边界情况，因此引入无穷面的概念保证结构上的统一。下图中的红色空间即可看作无穷面。
- 关联数据(Associated Data)：三维模型中除了点/边/面的信息外，可能还需要加入其他信息，例如法线、顶点颜色等。按照使用频率，经常使用的数据可以在半边结构的基础上进行一定扩展，不常使用的数据可以构建一个哈希表，确保它们的对应关系，并尽量在线性时间内可访问。
文末参考资料中还列出了一些特殊情况及其处理方法（比如面片中的孔，仅与一个面相邻的边，非直线段的边、LoD(Level of Detail)等），根据具体需求使用。
Ryan Holmes做的DCEL简单实现(C++)：ExampleCode.zip
DCEL优缺点
优点
- 邻域快速查找
对于任意点的邻域都能在恒定时间内访问。 即使顶点位置发生变化，也可以根据需要快速计算出面片的法线。 同样，还可以根据每个与顶点相邻的面快速计算顶点处的法线。 当网格局部发生改变时，仅需对局部内容进行重新计算。 同样，LoD、压缩存储、细分算法(Loop/Catmull-Clark等)也更容易进行。
- 灵活的数据形式
如果不确定要创建或加载的模型是三角形面片集合还是包含较大尺寸的多边形，则DCEL是一种节省空间的存储方法。因为它可以用相同方式处理模型中的每个多边形，不必针对不同多边形修改存储区的大小。
- 有限的区域
DCEL仅存储流形网格(manifold mesh)，这有助于在不同算法后（如，三角化、平滑、简化等）保持网格一致性，避免出现孔结构或面片翻转。
缺点
参考资料中分别列举了4条不那么独立的缺点，大致可以总结为：
DCEL结构的定义可能包含了一些不常用的结构，并占用了更多的存储空间。在处理实际问题的过程中，一定存在更有针对性的方案来取代DCEL这种通用性的方案。
参考资料：http://www.holmes3d.net/graphics/dcel/