multi-edge bevel on half-edge structure

Question

I am looking for a sample implementation, or pseudo code, of multi-edge bevel on a half-edge datastructure. Single edge bevel is easy - but multiple-edges at once... I tried now for several hours without success. I'm only struggling with the topological changes, pushing the vertices propperly doesn't look that difficult. Basically, I'm looking for an algorithm on how to get from the left mesh to the right mesh on a half-edge data structure:

Can anyone point me to a paper, a book or a sample implementation of multi-edge bevel?

Answer 1

We can split the operation into two conceptual steps. First, double the red edges. Second, explode the vertices incident to at least one red edge.

The first step can be accomplished one edge at a time. Given a red edge e, create another edge e'. For one half edge of e, insert one half edge of e' as the next half-edge with the same head in clockwise order. For the other half edge of e, insert the other half edge of e' as the next half edge with the same head in counterclockwise order.

The second step can be accomplished one vertex at a time. Given a vertex v incident to at least one red edge, group the half edges with head v as follows. Break that circular list (1) between every adjacent pair of red half edges that arose from the same original edge (2) between every adjacent pair of white edges (adjacent means that the two half edges are next/previous in clockwise/counterclockwise order). For each break, create a new edge. Splice everything together. (This involves operating on the ends of the broken pieces and the new edges. I think that a detailed description at the level of detail in this answer would be unhelpful.)