A little over a year and a half ago I booted up Houdini and took my first steps down a dark and disgusting spiral towards my new life as a technical artist. The video that inspired my jump, Simon Fiedler’s Learning Reel, showcased various and mind blowing CG tools he’d built while training in Houdini. One example in particular showcased a hexagonal pattern generator. Which led me to the bold question of “how he do dat? give pls.”

Luckily for me this seemed to be a common interest among motion graphics artists, which brought me to a number of forum posts describing various methods of creating hexagonal grids. Methods included everything from papers on Islamic pattern generation to art directable Voronoi Clustering. However one method in particular absolutely blew my mind; that method was described as computing the dual of a graph. This might instantly ring a few bells if you are a Houdini user. By default the Divide SOP (node, if you aren’t familiar with Houdini’s naming conventions) has a toggle dubbed “Compute Dual.” That’s great, but I come from the mentality where if I don’t understand how the tool works on a fundamental level, I don’t feel like I can properly squeeze all the power I want from it. And let’s be real, as artists we want to abuse the shit out of these tools. That innate need to know how it works, is what drove me to uncover a method of computing the dual purely in VEX code, which is what we’ll be exploring today.

Well what even is a dual graph? imagine we have two triangles, that share 1 complete edge. Now for every shared edge, you would remove that shared edge, and connect the centers of the two triangles, passing through the position where the old edge was.

However, I knew that it would never be that simple, especially since edges are defined typically as pairs of vertices. Thankfully, computer scientists have been smashing their face into this problem for years, and came up with a lovely data structure to help us think about edges, dubbed Half-Edges. If we have two polygons that share a complete edge, we can think of their half edges, as taking that shared edge and splitting it into two edges, one for each of the polygons. Don’t just take my word for it, the Sesi’s staff’s got our back: http://www.sidefx.com/docs/houdini/vex/halfedges

Half-Edge Visualization

Before I go any further, let me say that this code is not a replacement for the divide sop, which can natively compute the dual. Use that, it’s slightly more efficient (only at the meshing process though, I swear!), however by building the method by hand we give ourselves the ability to manipulate the final output in ways I previously thought weren’t possible.

Reading through the above doc’s and having the description and visuals I’ve outlined above, you might start to see how this is going to come together. Now let’s dive into some VEX. All of our code will live in an attribute wrangle running over primitives.

int boundary, num_eq, edge, edge2 = -1;
int pp[] = primpoints(0, @primnum);
edge = primhedge(0, @primnum);
int i = 0;

In this block of code all we’re doing is creating an array for each polygon, that contains a list of all the points in the currently queried polygon. Then we’re grabbing a random starting Half Edge on our queried polygon.
From here we need a way to test a few things about that half edge. First we need to make sure it’s in our queried polygon, then we need a way to both grab a neighboring edge, and test it to make sure it’s actually a neighbor. Luckily for us, the half-edge doc’s come to the rescue once again.
The last thing we need, is a way to break out of this proposed loop. Since we’re going to inevitably test the half edge of every point on a prim, we can say that as long as we’ve looped over every point in the queried primitive, then we can break! Super simple.

while(hedge_prim(0, edge) == @primnum) 
{
   edge2 = hedge_nextequiv(0, edge);
   if(hedge_isequiv(0, edge2, edge))
   {
       if(i < len(pp)) //stop when more edges than prims
       {
           i++;
       }
       else
       {
           break;
       }
   }
}

Now that we’ve tested to make sure the edges are neighbors, all that’s really left is to grab the centers of the polygons, and connect them. Easier said than done, but we have some great tools at our disposal. But before we get into that, holy shit look at this baby tapir.

Now when running in primitive mode, the global variable @P refers to the centroids of your polygon. Likewise, the prim() function, when pulling the “P” or position attribute, also grabs the centroid of your queried polygon.
So let’s poot that into our code:

while(hedge_prim(0, edge) == @primnum) 
{
   edge2 = hedge_nextequiv(0, edge);
   if(hedge_isequiv(0, edge2, edge))
   {
       if(i < len(pp)) //stop when more edges than prims
       {
           int pta = addpoint(0, @P);
           int neighbor = hedge_prim(0, edge2);
           vector neighborP = prim(0, "P", neighbor);
           int ptb = addpoint(0, neighborP);
           connect(pta, ptb, hedge_srcpoint(0, edge2));
          
           edge = hedge_next(0, edge);
           i++;
       }
       else
       {
           removeprim(0, @primnum, 1);
           break;
       }
   }
}

Radical.
Guys we are so gosh darn close. The last things we need to do are: connect the center points, iterate the edge (aka move onto the next edge and then repeat), remove the original geometry and then finally mesh the output. So let’s see how we would connect these two points. To do this, we’re going to create a function, since it’ll make our code look much cleaner.

void connect(int a, b, primnum)
{
   int prim = addprim(0, "polyline");
   addvertex(0, prim, a); //add vertex a
   addvertex(0, prim, b); //add vertex b
   setprimattrib(0, "prim", prim, primnum, "set");
}

The attribute we set at the end of our connect function is actually going to be how we ultimately mesh our graph. I needed a method of giving each new polygon an ID corresponding to the current “cycle” of our graph. Cycle is the fancy graph theory way of saying closed loop. What I realized when building this tool, is that you can get this number, by grabbing the source point number of your neighbor edge. The only explanation I can give as to why this is true, is that the source point of your neighboring edge will be the same for every edge used to compute one cycle. Here’s a visual showing each dual vertex connecting back to it’s source point:

Red lines show connections to the source points, grey lines are the original primitives, and white is the final dual.

So to wrap up the code we need to add 3 final things, a way to iterate the edge, a way to remove the initial geometry and then a way to mesh. We can actually move meshing until after we’ve finished the code, so really we only need 2 more lines. To make life even easier, the half-edge functions come with a great feature that will automagically iterate to the next edge in the loop, hedge_next().

Here’s the final code:

void connect(int a, b, primnum)
{
   int prim = addprim(0, "polyline");
   addvertex(0, prim, a); //add vertex b
   addvertex(0, prim, b); //add vertex b
   setprimattrib(0, "prim", prim, primnum, "set");
}
int i, boundary, num_eq, edge, edge2 = -1;
int pp[] = primpoints(0, @primnum);
edge = primhedge(0, @primnum);
i = 0;
while(hedge_prim(0, edge) == @primnum) 
{
   edge2 = hedge_nextequiv(0, edge);
   if(hedge_isequiv(0, edge2, edge))
   {
       if(i < len(pp))
       {
           int pta = addpoint(0, @P);
           int neighbor = hedge_prim(0, edge2);
           vector neighborP = prim(0, "P", neighbor);
           int ptb = addpoint(0, neighborP);
           connect(pta, ptb, hedge_srcpoint(0, edge2));
          
           edge = hedge_next(0, edge);
           i++;
       }
       else
       {
           removeprim(0, @primnum, 1);
           break;
       }
   }
}

We did it fools! You might notice this generates more primitives than are needed to create a dual graph that looks correct, however that is purposeful. These extra primitives will come in handy when meshing. The meshing process just involves a few more nodes, however rather than make this post any longer, I’ve attached the final project file below (with code comments!).

One caveat about the meshing process is that it will be pretty slow unless you are running the latest version of Houdini 16(16.0.577), due to the addition of the fuse sop being included in compile blocks. If you don’t know what that means, don’t trip. The compile block is a beast in it’s own right and definitely deserves a post for itself.

I’m totally open to any suggestions on speeding up the meshing, as it’s an interesting problem. One idea I had was to triangulate the duals by connecting back to the source point in the connect function we defined. However that just makes even more points which slows down the meshing process. Regardless, this process taught me a ton about edge flow working with half edges. It also opened up a lot of doors for more complex geometry manipulation in the future. Feel free to reach out if anything was unclear, if you just want to say sup or if you want to hire me… Cuz ya know, paying rent is pretty chill… Either way, I’m always down to nerd out over some Houdini stuff :)

HIP FILE