Half-Edge Mesh

Half-Edges

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.

Half-Edge Functions

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.

Defintion

Grasshopper definition canvas

(ghx download: see below ⇓)


 
Updated Definition

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.

null

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

null

Updated again 19 February → (new .gh download)

Advertisements
Comments
4 Responses to “Half-Edge Mesh”
  1. heumanndesigntech says:

    Trying this with my own curve networks seems to crash rhino. I am feeding a system of curves with no duplicates, all individual segments (already split by intersection) and all laying in the XY plane. Your example file works, and if I do small sets of curves drawn manually in rhino, it also manages to calculate just fine, but fails on larger sets around 60 lines. Any idea why this is happening?

    • trevor.patt says:

      This kind of crash usually happens when the script runs into an infinite loop while trying to close a ‘face’. Do you have any zero-length curves? These sometimes result when Grasshopper makes an intersection split (when three curves pass through the same point or if a curve is split at its start or end point).

    • trevor.patt says:

      I’ve finally had the time to revisit the code in this definition. Check out the update above.
      It should now be able to take quite large networks (I’ve tested it on a set of 2200 segments) from a rhino file and also to remove zero-length segments automatically. If you have a chance, do let me know if this works for you.

    • trevor.patt says:

      I noticed another bug recently which occurs when an edge is exactly parallel to the y-axis. This gave a divide-by-zero error which usually crashed Rhino.
      In lines 275-278 there is now a condition to deal with this case and to assign the correct angle.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: