对于网格表示，使用“半边沿”优于“翼状边缘”数据结构有什么好处？

我理解两种网格表示，唯一的区别是半边沿使用了定向边，而翼状边使用了无方向边。到目前为止，我还没有想到使用定向边缘有什么用，但是它只会增加内存消耗。

评论

“唯一的区别是，半边使用定向边，而翼状边使用不定向边。”根据我的理解，更像是：半边是双链接的（每个方向可能包含其他信息），而有翼的边通常仅是逆时针方向。
因此，您是说他们使用双向链接的方式只是显式地添加更多信息吗？因为我认为通过使用Half Edge，从网格中进行特定查询可能会获得一些性能。但是直到现在，我仍然无法弄清楚哪个查询。.
当我们使用边缘表示法时，这是一篇很棒的论文，总结了很多内容：graphics.cs.ucdavis.edu/~joy/ecs178/Unit-9/resources / ...

#1 楼

据我所知，半边的主要优点是遍历可以更简单一些，因为可以保证边在每个面内的方向一致。

考虑迭代的问题给定面的所有顶点或边缘，以逆时针顺序排列。在半边结构中，可以通过从该面孔的任意半边开始，然后简单地跟随“下一个”指针，直到回到起点，来完成。在有翼的边缘结构中这有点令人讨厌，因为边缘是任意定向的。您遇到的任何给定边缘都可能相对于您要迭代的脸部沿顺时针或逆时针指向，因此您必须在每个步骤中进行额外的条件检查，以查看是否应向前或向后遍历当前边缘。 br />
其他类型的连接性查询的行为类似：半边版本允许您以一致的顺序跟踪链接，而有翼边版本则需要在每个步骤中进行方向检查。

是否条件实际上是有翼边的性能问题，可能取决于其他因素。对于一个“天真”的实现，它以各种方式将指针分散在内存中，数据分散在内存中，我希望缓存未命中开销会淹没条件语句的任何影响。另一方面，如果您的数据结构非常紧凑，并且缓存中的所有内容都很热，那么由于错误的分支预测等原因，您可能会发现条件语句会产生一些影响。很难说。就性能而言，我宁愿使用半边沿，因为它似乎更易于推理和为其编写正确的代码，即使这会导致少量的内存开销。

顺便说一下，还有其他一些带有网格数据结构的设计选择，这些选择似乎常常与此混淆。评论者提到单链接与双链接，但是自然地，您可以使用半边或有翼边进行单链接或双链接。 （尽管我什至看不到有翼边缘的单链接怎么工作，因为如上所述，您可能必须在查询过程中向后或向前遍历边缘。）

也，这是一个问题，即顶点和面结构是存储其所有边的列表还是仅存储一个边列表（并要求您遍历边以查找其余部分）。如果要有效地处理每个顶点/面的可变长度边列表，会使逻辑变得很复杂（即，每个顶点/面没有单独的堆分配），但这又与边是否为半边无关或有翼边。