Winged Edge

• Operations:
  • Want to traverse
    • Neighboring faces of a face/vertex
    • Neighboring vertices of a face/vertex
    • Edges of a face
  • Want to modify (add/delete) the polyhedron
• Key ideas of winged-edge:
  • Edge is important topological data structure
  • Also, separate topology from geoemtry
• Edge is the primary data structure

• Pictorially:

• Data types:

  struct he {
    struct he* sym;
    struct he* next;
    struct he* prev;
    struct vert* v;
    struct face* f;
    void* data;
  }
  struct vert {
    struct he* rep;
    void* data;
  }
  struct face {
    struct he* rep;
    void* data;
  }

• Example: Neighboring faces of f

  (picture)

  struct face* f;
  struct he* e;
  struct he* s;
  struct he* fl[LOTS];
  int i;
  
  s = e = f->rep;
  i = 0;
  do {
    fl[i++] = e->sym->f;
    e = e->next;
  } while (e != s);

• Example: Removing an edge

  RemoveEdge(struct he* e) {
    /* fix edge->edge pointers */
    e->prev->next = e->sym->next;
    e->next->prev = e->sym->prev;
    e->sym->next->prev = e->prev;
    e->sym->prev->next = e->next;
  
    /* fix edge->face pointers */
    ee = e->sym->next;
    while (ee != e->sym) {
      ee->f = e->f;
      ee = ee->next;
    }  
  
    /* fix face->edge pointers */
    e->f->rep = e->prev;
  
    /* fix vertex->edge pointers */
    e->v->rep = e->sym->prev;
    e->sym->v->rep = e->prev;
  
    DeleteFace(e->sym->f);
    DeleteEdge(e);
  }

• Variations:
  • Some operations simplified by splitting edge into half-edges
  • Uses a lot of space. Time-space trade-off.

• Manifolds with Boundary
  • Half-edge allows representation of manifold w/boundary

    Set sym pointer to NULL

  • Allows for lone face

    (picture)

  • Makes some constructions easier
  • New Euler formula

    

    where B is number of boundaries

• Duality
  • Faces and vertices are dual

    Representations and rolls are identical

  • Can replace each face with a vertex and each vertex with a face

    (picture)

  • If boundaries, then dual may not be manifold
• Evaluation

  +

  Faces with arbitrary number of sides

  Vertices with arbitrary number of neighbors

  +

  Iterate over everything

  -

  Not space efficient

  -

  Painful to write/debug code

  **

  Simpler data structure better unless you need to modify, iterate

• API
  • Discussions in papers use low level operators
  • Better if user of package does NOT manipulate pointers
  • Higher level ``safe'' operators, iterators:
    • ForeachMeshVertex
    • ForeachFaceVertex
    • Split 3-1
    • RemoveEdge
  • Example: Split all faces 3-1

    ForeachMeshFace(m,f) {
      p = SplitFace3to1(f);
      SetPosition(P,x,y,z);
    }

  • Which operations should we provide?