GitLab

There are some basic relations of half edges all implementations of a half edge grid should comply to.

If not all basic operations are implemented, some test should probably be deactivated for that specific implementation.

Correctness of a single basic operation

• next() should be cyclic and consistent:
  • For interior half edges the cycle length should be equal to the number of edges of the corresponding element type.
    All elements of such a cycle should be interior half edges belonging to the same face.
  • For half edges on the boundary all elements of the cycle should lie on the boundary, too.
• previous() should be cyclic and consistent:
  • For interior half edges the cycle length should be equal to the number of edges of the corresponding element type.
    All elements of such a cycle should be interior half edges belonging to the same face.
  • For half edges on the boundary all elements of the cycle should lie on the boundary, too.
• opposite() should be an involution and consistent:
  • opposite() of opposite() == id
  • A half edge and its opposite() belong to the same edge.

Correctness of combinations of basic operations

• next() and `previous() are the inverse of each other:
  • If both next() and previous() are defined for a half edge:
    next() of previous() == id
previous() of next() == id
• An iteration around a vertex should terminate and be consistent:
  • Whether the vertex belonging to a half edge is its target or source and independently of the specific combination of basic operations used to get the next half edge during this iteration, the iteration should return to the first half edge.
  • The number of steps for an interior vertex should be at least 3.
    The number of steps for an vertex on the boundary should be at least 2.
  • All half edges in such an iteration should have the same vertex.