divyanx / hgeom

A Java libray for creating and editing half-edge data structure

HGeom

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

Creation of a half-edge data structure in HGeom

There are two ways to create a half-edge data structure with HGeom:

1. Creation of a half-edge data structure from a list of polygons

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]);
   

2. Creation of a half-edge data structure from a list of edges

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]);