Крыло-край против пол-края

Question

Я пытаюсь понять представление границ (B-rep) и не могу найти преимущества структуры данных с половинным краем по сравнению с структурой с крылым краем. Я обнаружил в этой книге, что крылатый край не может представлять состояние, в котором существует вершина, но нет ребер в пространстве. Но нет образца.

В другой книге говорится, что в направлении края есть неясность.

И, наконец, на этой веб-странице приводятся причины производительности.

Answer 1

Я нашел решение в этой статье.

С 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; }
}

На лицевой стороне вам нужно только сохранить один из ограничивающих ребер, так как структура образует двойной связанный список, вы можете получить другие ребра:

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)

Мы должны использовать условное выражение (?:) в цикле, чтобы найти следующее ребро. На современных процессорах это приводит к снижению производительности, как описано в этом посте.

У структуры данных с половинным краем нет этой проблемы (но она занимает больше памяти).