HEM functions

Half-Edge Mesh functions

Offset, Distance, and Walk over Half-Edge Mesh

Presented here are three functions for working with Half-Edge Meshes in Grasshopper.

The first uses the lists of vertex’ incident edges (vIE) to calculate the bisecting angles at intersections in-between branches and create an offset of the graph which can be uniquely defined at every vertex (in black and grey in the image above). The output creates two sets of polylines: one which defines the faces and one which defines a polygon around the intersection (in the case of two-segment intersections, this is a straight, bisecting line segment). This is useful for giving a graph material thickness or for offsetting faces inward to suggest circulation capacity along the edges.

The second function analyses the distance of every edge to a point at one of the nodes over the graph (red-yellow-blue gradient in the image above). That is, the distance it would take to walk from one of the origin points to the midpoint of that edge taking shortest path from node to node along edges only. This can be used to take into account the embedded graph distance two points are from one another rather than straight-line Cartesian distance. It could also be used to compute the Space Syntax component of Depth Distance.

The third function traces a random walk over the graph from one or more starting points (the grey circles in the image above show the current position of the walk, the path is hidden from the preview). This allows one to animate HEM analyses from multiple points linked in a smooth progression as in the animation below. A Boolean toggle allows one to eliminate direct backtracking (except at dead-ends, of course) or to permit a limited amount.

This example, using the street network of Lausanne has over 12600 half-edges. Each frame calculated in just under 1 minute

Grasshopper Canvas

Grasshopper Definition

(.gh download, and Rhino5 base .3dm)

4 Responses to “HEM functions”
  1. Daniel says:

    Hi Trevor
    Very excited about these new functions for grasshopper – thank you very much!
    Now that a half-edge mesh has been implemented in grasshopper, I was wondering whether this offset function could be inverted so that the straight skeleton of a polygon could be computed (a la the CGAL definitions?, though they are in C++…)

    Great work anyhow, thanks


    • trevor.patt says:

      It’s an interesting idea to combine this with a straight skeleton and might help address one of the problems the offset is currently faced with: self-intersection on tight corners when the offset distance is to large.
      bad offsets

      I took a pass at a basic implementation of the Straight Skeleton on the HEM, and while it’s not as robust as CGAL’s, it is a start. On the backend, I think the code could be better integrated with the HEM data structure than it is now (though you could always merge the straight skeleton and the original HEM segments and calculate a second HEM of the results).

      To really solve my offset problem, it will need to be able to compute incrementally and have a way of handling split events, but that’s another day.

      • Daniel says:

        Hi Trevor.
        I really didnt anticipate you’d get this up and running so quickly! Thanks so much!

        For those split events, I’m not sure if you have seen this before (and it looks at cases of weighted straight-skeletons rather than uniform), but http://twak.blogspot.com.au/2011/01/degeneracy-in-weighted-straight.html has a quite thorough run-down of split-event types and their resolutions. It does look quite complicated though.
        Hope this is informative!


      • trevor.patt says:

        Daniel, yeah normally not so quick, but you got your comment in at just the right time.
        The interesting thing the definition as written now actually works on most split events like the inverted pentagon/double-triangle polygon I see in the link. I need to look a little closer to isolate exactly what conditions are still triggering an error. In any case the link you sent look like something to pore over. Thanks!

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: