有翼边缘与半边

Question

我试图理解边界表示(B-rep)，但我找不到半边数据结构相对于有翼边数据结构的优势。我在this book中发现，有翼边不能表示空间中有顶点但没有边的状态。但是没有样本。

Another book说，在边缘方向上有一个模糊性。

最后，在this web page上，调用性能原因。

Answer 1

我已经在this paper中找到了解决方案。

有了winged-edge，你就得到了这样的数据结构：

​

​

C#中的代码如下：

public class WingedEdge
{
    public Curve3d Curve { get; set; }

    /// <summary>
    /// Edge of the left loop starting on the end vertex of this edge.
    /// </summary>
    public Edge EndLeftEdge { get; set; }

    /// <summary>
    /// Edge of the right loop starting on the end vertex of this edge.
    /// </summary>
    public Edge EndRightEdge { get; set; }

    /// <summary>
    /// Vertex on the end point of the edge.
    /// </summary>
    public Vertex EndVertex { get; set; }

    /// <summary>
    /// Face on the left side of the edge.
    /// </summary>
    public Face LeftFace { get; set; }

    /// <summary>
    /// Face on the right side of the edge.
    /// </summary>
    public Face RightFace { get; set; }

    /// <summary>
    /// Edge of the left loop ending on the start vertex of this edge.
    /// </summary>
    public Edge StartLeftEdge { get; set; }

    /// <summary>
    /// Edge of the right loop ending on the start vertex of this edge.
    /// </summary>
    public Edge StartRightEdge { get; set; }

    /// <summary>
    /// Vertex on the start point of the edge.
    /// </summary>
    public Vertex StartVertex { get; set; }
}

在face上，你只需要存储其中一个边界边，当结构形成一个双向链表时，你可以检索到其他边：

public class Face
{
    /// <summary>
    /// One of the edges bounding this face.
    /// </summary>
    public WingedEdge FirstEdge { get; set; }
}

但是如果你需要迭代一个面的边缘，你可以使用下面的代码：

WingedEdge edge = face.FirstEdge;
do {
  // Do something with the edge
  WingedEdge edge = edge.LeftFace == face ? edge.LeftNextEdge : edge.RightNextEdge;
} while (edge != face.FirstEdge)

我们必须在循环中使用条件表达式(？:)来查找下一条边。在现代处理器上，这会导致性能下降，正如in this post所描述的那样。

半边数据结构没有这个问题(但需要更多的内存)。