本帖最后由 Jessesn 于 2014-6-15 10:15 编辑
看到一篇非常不错的技术贴，转载过来和大家分享一下 :)
原文作者与来源：小土刀叨，如需转载烦请注明来源
【翻译】The Half-Edge Data Structure最新计算机图形学作业可能要用到半边数据结构，但是网上真正把基本概念说清楚的中文资源我实在是没找到，于是只好翻译一篇国外的我觉得写的比较不错的 文章（甚至还带了点代码！） 其实同学们最需要理解的就是，无论是顶点列表还是面列表还是接下来要提到的半边结构，实际上就是某种描述三维物体的方式，究其根本，就是因为应用场景的不同，所选择的不同的存储到内存中的方式，有些我们看起来比较直观的描述方式（三维的话无非就是点线面），对于某些特定的运算反而会增加额外的计算量，在我看来只要能在看到数据的时候大致能想象出点线面的位置朝向什么的，就差不多了。废话不多说，接下来就是原文翻译。
表示多边形网格(polygon mesh)的一个常用方式就是使用共享的顶点列表和面的列表（里面包含面所含的顶点）。这样的表示方法在许多情况下都非常方便和高效，但是在某些特定的领域，反而会比较低效。
举例来说，网格简化(mesh simplification)通常需要把一条边退化成一个顶点。这个操作需要删除与这条边邻接的面并且更新面中存储的与这条边相关的顶点数据。这种多边形“手术”需要我们了解网格的组成部分的邻接关系，例如面和顶点。虽然我们肯定可以用之前提及的网格表示方法来实现网格简化，但是代价会比较高。许多情况下需要遍历面或者点的列表，甚至两者都要。 其他类似的多边形网格的邻接性查询还包括： 哪些面使用这个顶点？ 哪些边使用这个顶点？ 那些面以这条边为边界？ 哪些边在这个面上？ 哪些面在与这个面邻接？
为了高效实现这些邻接性查询，人们开发了更加复杂的边表示方法(b-reps)来显式描述顶点、边还有面的邻接信息。
这之中最常用的是 Winged-Edge数据结构，其中每条边包含了指向其两个顶点，两个邻接面的指针以及指向从其终点延伸出去的四条边的指针。这种结构可以让我们在常数时间内判断哪些点与面与该边连接，但是面对其他类型的查询，这种结构会带来更大的开销。 半边(half-edge)数据结构是一种略微复杂的边表示方法(b-reps)并且在其上做之前提到的所有操作都可以在常数时间完成。更优秀的是，即使包含了面、顶点和边的邻接信息，数据结构的大小是固定的且紧凑的。 这些特性是的半边数据结构成为了许多应用的最佳选择，但是其只能表示 流形表面( manifold surfaces)，而在某些情况下被证明是不可用的。流形的数学定义指的是曲面上的每一点都被其附近的复合盘的拓扑结构的区域包围（注：这句话好难翻译，建议直接看英文wiki）。对于多边形网格来说，这意味着每条边是且只能是两个面的边，t-junctions和internal polygons和网格中的空缺时，不能使用半边结构（这里术语就不翻译了）。
之所以称为半边数据结构，是因为在这个结构中并不会存储网格的边的信息，取而代之的是半边(half-edges)。半边这么叫，就是因为它其实是一条边的一半，等于是把一条边保持长度不变，形式上分为两条半边（因为按照定义边没有宽度或者至少是单位宽度，这就是一个假象划分）。这两条半边组合在一起称为一条边，也就是一条边等于一对半边。半边是有方向的，并且一条边的一对半边有相反的方向。
下图展示了三角形网格的一小部分的半边描述。黄点是定点，蓝边是半边，其中的箭头表示指针（为了不画得太乱，删除了一些） 可以很清楚地看到围绕一个面的三条边形成了一个环(circular linked list)。这个链表既可以顺时针也可以逆时针，只要在使用中保持一致就好。环中的每半边存储一个指向以其为边的面的指针（图中没有画出来）、指向半边终点的指针（同样没画出来）和指向它的另一条半边（就是合起来组成一条边的那个半边）的指针。
| 
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏
分享
