HGeom is a Java library for creating and manipulating half-edge data structure
A half-edge data structure is a model for representing a polygon mesh
It allows efficient topological operations on a mesh such as removing a vertex or an edge, splitting a polygon or merging 2 polygons
Traversals of meshes along vertices, edges or polygons are also efficiently performed with the help of a half-edge data structure
A half-edge data structure is modelized in HGeom by the Java class HMesh
To create a HMesh, see below
Go here to find a description of HMesh and to know how to edit a HMesh
Go here to learn how to navigate inside a HMesh
Go here for some examples of HMesh uses
There are two ways to create a half-edge data structure with HGeom:
A HMesh can be automatically generated from a list of polygons where each polygon is defined by a list of indices to vertices.
Let's take this mesh as an example:
The mesh contains 7 vertices:
| Vertex indices | Vertices |
|---|---|
| 0 | v0 |
| 1 | v1 |
| 2 | v2 |
| 3 | v3 |
| 4 | v4 |
| 5 | v5 |
| 6 | v6 |
and 3 polygons:
| Polygon indices | Polygon | Polygon definition as indices to vertices |
|---|---|---|
| 0 | p0 | [0, 1, 2, 6] |
| 1 | p1 | [2, 5, 6] |
| 2 | p2 | [2, 3, 4, 5] |
To generate a HMesh from this mesh, we first create a FaceSource from the collection of polygons:
// The polygons as arrays of indices to vertices:
int[][] polygons = {{0, 1, 2, 6}, {2, 5, 6}, {2, 3, 4, 5}};
// Build the face source. a FaceSource can be built from
// various types of iterable collection of faces / polygons
FaceSource faceSource = new FaceSource(polygons);
We then convert the FaceSource into a HMesh:
Optional<HMesh> mesh = faceSource.toHMesh();
Or, by extracting the result from the Optional:
HMesh mesh = faceSource.toHMesh().orElseThrow(
() -> new IllegalStateException(
"couldn't convert polygons into a half-edge DS"));Each initial edge is splitted into 2 half-edges in the generated half-edge data structure:
The generated half-edge data structure contains 4 polygons, that is, one more than the initial number of polygons:
- 3 polygons modelizing the 3 intial polygons : [0, 1, 2, 6], [2, 5, 6], [2, 3, 4, 5] (in the half-edge data structure, a polygon is a cycle of half-edges, each one connecting 2 vertices)
- An extra polygon which is the outer border of the mesh : [0 6 5 4 3 2 1]
The half-edge data structure is automatically generated by an algorithm wich uses the topological links between the initial polygons to produce half-edges and connect them together. A generated HMesh is always consistent
If 2D coordinates are attached to the vertices:
| Vertex indices | Vertices | 2D coords |
|---|---|---|
| 0 | v0 | [0, 0] |
| 1 | v1 | [0, 1] |
| 2 | v2 | [1, 1] |
| 3 | v3 | [2, 1] |
| 4 | v4 | [2, 0] |
| 5 | v5 | [1.7, 0] |
| 6 | v6 | [1, 0] |
Then a HMesh2D (a version of HMesh for the 2D space) can be created using these coordinates:
int[][] polygons = {{0, 1, 2, 6}, {2, 5, 6}, {2, 3, 4, 5}};
double[][] vertexCoords = {{0, 0}, {0, 1}, {1, 1}, {2, 1}, {2, 0}, {1.7, 0}, {1, 0}};
FaceSource faceSource = new FaceSource(polygons);
// Wrap the vertex coordinates into a Coords2DSource. a Coords2DSource can wrap
// various types of iterable collection of 2D coordinates
Coords2DSource coordSource = new Coords2DSource(vertexCoords);
// Crate the HMesh using both the FaceSource and the Coords2DSource
HMesh2D mesh = faceSource.toHMesh2D(coordSource).orElseThrow(...);
If 3D coordinates are attached to the vertices, a HMesh3D can similarly be created with the help of a Coords3DSource
If some data are attached either to the polygons or to the vertices :
| Vertex indices | Vertices | Weights |
|---|---|---|
| 0 | v0 | 3.5 |
| 1 | v1 | 2.1 |
| 2 | v2 | 5.5 |
| 3 | v3 | 7.4 |
| 4 | v4 | 2.3 |
| 5 | v5 | 6.7 |
| 6 | v6 | 4.7 |
| Polygon indices | Polygon | Colors |
|---|---|---|
| 0 | p0 | Green |
| 1 | p1 | Red |
| 2 | p2 | Yellow |
Then, these data can be associated to the HMesh's elements with a more elaborate conversion process:
int[][] polygons = {{0, 1, 2, 6}, {2, 5, 6}, {2, 3, 4, 5}};
double[] vertexWeights = {3.5, 2.1, 5.5, 7.4, 2.3, 6.7, 4.7};
Color[] polygonColors = {Color.Green, Color.Red, Color.Yellow};
FaceSource faceSource = new FaceSource(faces);
// Create a converter to HMesh
ToHMeshConverter converter = new ToHMeshConverter();
// Convert the face source using the converter. The result is a HConversion
HConversion<HMesh> conversion = converter.convert(faceSource).orElseThrow(...);
// Extract the HMesh from the HConversion
HMesh mesh = conversion.mesh();
// Use the HConversion to convert the initial data into
// data associated to the vertices of the HMesh
HDData<HVertex> meshVertexWeights = conversion.meshVertexDoubleData(i -> vertexWeights[i]);
// Use the HConversion to convert the initial data into
// data associated to the faces of the HMesh
HData<HFace> meshFaceColors = conversion.meshFaceData(i -> polygonColors[i]);
A HMesh can automatically be generated from a list of edges where each edge is defined by a pair of indices to vertices.
Let's take this set of edges as an example:
The edges are defined as pair of indices to vertices:
| Edge indices | Edge | Edge definition as pair of indices to vertices |
|---|---|---|
| 0 | e0 | [1, 0] |
| 1 | e1 | [2, 1] |
| 2 | e2 | [2, 5] |
| 3 | e3 | [3, 2] |
| 4 | e4 | [5, 3] |
| 5 | e5 | [3, 4] |
| 6 | e6 | [5, 4] |
| 7 | e7 | [5, 6] |
| 8 | e8 | [0, 6] |
To generate a HMesh from this mesh, we first create a EdgeSource from the collection of edges:
// The edges as arrays of pairs of indices to vertices:
int[][] edges = {{1, 0}, {2, 1}, {2, 5}, {3, 2}, {5, 3}, {3, 4}, {5, 4}, {5, 6}, {0, 6}};
// Build the edge source. a EdgeSource can be build from
// various types of iterable collection of edges
EdgeSource edgeSource = new EdgeSource(edges);
We can then convert the EdgeSource into a HMesh using a PolygonWindingProvider:
PolygonWindingProvider polygonWindingProvider = ...
HMesh mesh = faceSource.toHMesh(polygonWindingProvider).orElseThrow(...);
A polygon winding provider is a tool used by the half-edge data structure conversion process for making the right connections between the edges
Another possibility is to use 2D coordinates associated with the vertices:
// The edges as arrays of pairs of indices to vertices:
int[][] edges = {{1, 0}, {2, 1}, {2, 5}, {3, 2}, {5, 3}, {3, 4}, {5, 4}, {5, 6}, {0, 6}};
double[][] vertexCoords = {{0, 0}, {0, 1}, {.5, 1}, {2, 1}, {2, 0}, {1.5, 0}, {.5, 0}};
EdgeSource edgeSource = new EdgeSource(edges);
Coords2DSource coordSource = new Coords2DSource(vertexCoords);
HMesh2D mesh = edgeSource.toHMesh(coordSource).orElseThrow(...);
Here, it is the 2D coordinates that are used to connect the edges
Extra data can be associated with both the vertices and the edges in the similar way than for the polygons:
int[][] edges = {{1, 0}, {2, 1}, {2, 5}, {3, 2}, {5, 3}, {3, 4}, {5, 4}, {5, 6}, {0, 6}};
double[][] vertexCoords = {{0, 0}, {0, 1}, {.5, .5}, {2, 1}, {2, 0}, {1.5, 0}, {.5, 0}};
double[] vertexWeights = {3.5, 2.1, 5.5, 7.4, 2.3, 6.7, 4.7};
Color[] edgeColors = {Color.Green, Color.Red, Color.Yellow, Color.Blue, ...};
EdgeSource edgeSource = new EdgeSource(edges);
Coords2DSource coordSource = new Coords2DSource(vertexCoords);
// Create a converter to HMesh
ToHMeshConverter converter = new ToHMeshConverter();
// Convert the edge source using the converter.
HConversion<HMesh> conversion = converter.convert(edgeSource, coordSource).orElseThrow(...);
// Extract the HMesh from the HConversion
HMesh mesh = conversion.mesh();
// Use the HConversion to convert the initial data into
// data associated to the vertices of the HMesh
HDData<HVertex> meshVertexWeights = conversion.meshVertexDoubleData(i -> vertexWeights[i]);
// Use the HConversion to convert the initial data into
// data associated to the edges of the HMesh
HData<HEdge> meshEdgeColors = conversion.meshEdgeData(i -> edgeColors[i]);