Half-Edge Mesh

Posted by trevor.patt on 08/15/2012 · 4 Comments 

Each segment of this network has two half-edges

Though the logic behind the data-structure of a half-edge mesh can be difficult or unintuitive to work with at first, once it becomes clear, it can become difficult to imagine working without recourse to functions that will tell you which face an edge is adjacent to, which edges meet at a vertex, or what the next edge (traveling around the perimeter) of a face is. I find the data available from Grasshopper’s mesh components, such as the Proximity, Delauney, or Voronoi functions, to be inconsistent and incomplete. The properties of Mesh and BRep classes in RhinoCommon are slightly better, but both contain puzzling gaps in the data they supply.

This definition constructs a half-edge datastructure from a (flattened) list of the segments alone, making this especially useful for unstructured networks such as curves split by intersection (as in the video above and the example definition) or more complex structures such as those generated by Auxin Flux Canalisation.

One particular difference from the Processing version is that faces are not reproduced as surfaces nor are they guaranteed to be convertible into surfaces. Here they function more like loops which continue until they close. This means that segments jutting into a face are included in the face edge like cul-de-sacs and also that the outer edge is also considered as a face (though ‘inside-out’), as you can see about 7 seconds into the video. Certain outputs have also been converted from single entries into dataTrees such as the faceIncidentEdge output which in the Processing example only returned one value and required a loop to find the rest. For an environment that is primarily text-based this isn’t a problem but for Grasshopper it seemed to make more sense to output the whole list enabling the Select Item and Select Branch components to be used rather than dictating the use of additional scripts.

An example of native Grasshopper components used to parse an HEM structure, click to read the detailed explanation in Flickr

A few warnings about the defintion: this hasn’t been extensively tested on networks where edges might intersect without a node at that intersection (as often occurs with the Proximity command when two edges cross) though it works in the cases I have tried. I do know that duplicate edges (which often come with the Auxin Flux definition) will almost immediately cause a crash. It also seems that networks of over 1200 segments force a crash on my computer. It is probably wise to use the remove duplicate edges functions from either Karamba or Kangaroo. At the moment this definition is written for networks which are approximately parallel to the xy-plane, meaning that 2.5- or 3-dimensional networks are ok, but that the sorting for faces is done by planar angles and the code will not know how to sort a node whose junctions are in a vertical plane. Future versions will allow the input of a reference plane or surface to remove this limitation.

Grasshopper definition canvas

(ghx download: see below ⇓)

 

Half-Edge Mesh, now capable of thousands of ½-edges

UPDATE:
I’ve almost completely rewritten this Half-Edge Mesh definition to use a similar strategy as in the DLA definition to partition the space into a grid of rectangles (these are the new inputs: X Bounds, Y Bounds, and #Grid Divisions). This greatly speeds up the calculations for identifying and indexing the vertices.
Along the way, I’ve eliminated a number of redundant calculations and adjusted a few weird bits of code that may or may not have been causing errors.

This example is composed of >1100 vertices, >1000 faces, and >4000 ½-edges derived from a network of crossing polylines

Updated again 19 February → (new .gh download)

Filed under Grasshopper · Tagged with computational geometry, data structure, face, geometry, half-edge mesh, intersection, network, rhino