Deprecated: Function set_magic_quotes_runtime() is deprecated in /storage/content/76/1004576/wiki.jpatch3d.org/public_html/inc/common.php on line 33 Deprecated: Function split() is deprecated in /storage/content/76/1004576/wiki.jpatch3d.org/public_html/inc/auth.php on line 95 Deprecated: Function split() is deprecated in /storage/content/76/1004576/wiki.jpatch3d.org/public_html/inc/common.php on line 743 dev:halfedge [DokuWiki]

JPatchs Half-Edge datastructure

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.

Queries

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

Get all HalfEdges of a Face

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.

Get all HelfEdges adjacent to a Vertex

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.

Get all Faces adjacent to a Vertex

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.

Querying Vertices and Faces of edges

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.

A closer look

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.