[[dev:halfedge]]

This is a description of JPatchs Half-Edge datastructure which is used to represent polygon (SDS) objects. It is very similar to a Winged-Edge datastructure. This first part is an introduction, the actual structures used in JPatch are a bit more complex and are covered in detail below.

Winged-Edge structures use three classes for boundary-representations (b-reps) of meshes: *Faces*, *Edges* and *Vertices*.
Each *Face* has a number of *Edges* (at least three) and each *Edge* has exactly two *Vertices*. Each *Egde* is adjacent to exactly two *Faces*.

To be able to perform queries quickly (and in constant time), JPatch uses a Half-Edge structure. That means that every *Edge* is actually represented by two Objects, two *HalfEdges*. Most topological information is stored in those *HalfEdges*.
Each *HalfEdge* belongs to exactly one *Face* and stores pointers to:

- the
*Face*it belongs to - its starting
*Vertex* - its pair
*HalfEdge* - the next
*HalfEdge*of the*Face* - the previous
*HalfEdge*of the*Face*

A *HalfEdge* and its pair *HalfEdge* represent one *Edge*, although there is no separate *Edge* class.

*Faces* and *Vertices* are quite simple. Each *Face* stores a pointer to one of its *HalfEdges*, and each *Vertex* stores a pointer to one of the *HalfEdges* that originate at this *Vertrex*.

The class diagram above shows the *Vertex*, *Face* and *HalfEdge* classes and their relationship. The diagram below shows a topology made of two *Faces*, and some of the objects used to represent it. Note that the structure as discussed until now would not allow to represent open topologies, since each edge must be adjacent to exactly two faces (thus the polyhedra must be closed). JPatch does allow open polyhedra, the details are discussed below.

The structure can be queried in different ways. Here are some examples:

The method *getEdges()* of the *Face* class returns an Iterable that iterates over all *HalfEdges* of this *Face*. It first returns the *HalfEdge* the *Face* points to. It then returns *edge.next* and so on until all edges have been traversed.

The method *getAdjacentEdges* of the *Vertex* class returns an Iterable that iterates over all *HalfEdges* adjacent to this *Vertex*. It first returns the *HalfEdge* the *Vertex* points to. It then returns *edge.pair.next* and so on until all edges have been traversed.

The method *getAdjacentFaces* of the *Vertex* class returns an Iterable that iterates over all *Faces* adjacent to this *Vertex*. It first returns the *Face* of *edge.pair*. It then returns *Face* of *edge.next.pair* and so on until all faces have been traversed.

The *HalfEdge* class has four query functions:

*getFirstVertex()*returns the*Vertex*this*HalfEdge*points to.*getSecondVertex()*returns the*Vertex*the pair*HalfEdge*points to.*getRightFace()*returns the*Face*this*HalfEdge*points to.*getLeftFace()*returns the*Face*the pair*HalfEdge*points to.

Note that, in the example above, the polyhedron is not closed. Thus some *HalfEdges* have their *next* and *prev* edges and their *Face* set to *null*. For the queries on *Vertices* to work it is therefor crucial to have their *HalfEdge* pointer set to the first *HalfEdge* (e.g edge11 for vertex4 in the example above). This is ensured by calling the *Vertex’* *validate()* method.

The code that dices (i.e. tesselates) the faces of the subdivision surface requires that each face has exactly four sides. Fortunately, after one level of subdivision, all faces are quadrilaterals, so all we’ve got to do is to perform the first level of subdivision on the Half-Edge datastructure and then pass the result to the Dicer. After the first level of subdivision old vertex-points move to a new position and new vertices (one per face and one per edge) are introduced.
Since these new vertices are needed all the time, all Classes (*Vertex*, *HalfEdge* and *Face*) got an additional field that points to their *Level2Vertex*.
A class hierarchy was introduces, the base class for *Vertices* is now *AbstractVertex* with the subclasses *TopLevelVertex* and *Level2Vertex*. *Level2Vertex* is an abstract class and adds the method *void computeDerivedPosition()*.
The diagram below shows a more complete version of the class diagram:

Note that HalfEdge has got a private inner subclass called *SecondaryEdge*. To avoid programming errors, creating a new *HalfEdge* will always create its pair *HalfEdge* and connect both. The one returned by the public constructor is called the primary - its *isPrimary()* method returns *true* and its *getPrimary()* method returns a reference to itseld.
The “secondary” (pair) *HalfEdge* is of type *SecondaryEdge*. Its *isPrimary()* method returns false and its *getPrimaty()* method returns its pair *HalfEdge*.

The *bindVertexPoint()*, *bindEdgePoint()* and *bindFacePoint()* methods create the *Level2Vertices* of a *Vertex*, *HalfEdge* or *Face*, respectively.