# Sort half-edges around common vertex in 3d

I'm trying to figure out this problem for very long time and am no getting nowhere. I'm working on a simple 3d modeler that uses half-edge data structure.

Say I have non-manifold geometry where two triangles share a common vertex, as shown in the image below. And I want to add another triangle such that now three triangles share a common vertex. Once we add the new triangle we need to reorder the half-edges around the common vertex. In 2d this ordering is done by sorting the half-edges from the common vertex clockwise, as explained in this post.

However in 3d this becomes a nightmare. If the same three triangles share the common vertex but have an arbitrary orientation in 3d space and are not coplanar. How can one possibly sort the half-edges?

I experimented with using the common vertex normal to construct a plane, and project all the half-edges around the vertex to that plane. After which we could sort them clockwise relative to the plane. But I've found this approach to have a lot of issues. And now I'm all out of ideas.

• What exactly do you mean by a "non-manifold geometry"? Is your graph embedded (or can be embedded) on a fixed surface that is not necessarily a manifold? How do you add your triangle? Do you simply give the coordinates of the vertices in $\mathbb{R}^3$? Sep 20, 2020 at 9:20
• @Discretelizard Unfortunately I'm not sure how to answer the first two questions. I used the term non-manifold geometry to refer to the case where polygons share the same vertex. Also yes the triangle is constructed by simply specifying vertex coordinates in R3. Sep 20, 2020 at 16:16
• – D.W.
Jan 14, 2021 at 19:08

It seems that the problem here is that you try to determine something similar to a rotation system from a skeleton1 embedded in $$\mathbb{R}^3$$. The problem here is that such a skeleton is not enough to uniquely define a rotation system, because rotation systems encode embeddings of a graph onto a surface. Without having access to a given surface as a reference, almost any rotation along a vertex is possible, and you will not be able to find the "right" one.

So what can you do? This likely depends a bit on what it is you are actually modelling. Since the rotation around a vertex is a concept that depends on a surface, to determine it you will have to decide what your surface looks like, at least locally around the vertex you're inserting a triangle in. Likely, the edges that are part of a triangle should always be consecutive in the ordering, but that doesn't give all the information.

One possible approach on how to decide where a new triangle fits into the ordering, is to look at all consecutive pairs of triangles in the existing ordering, and insert the new triangle in between the pair with smallest distance to the new triangle. (Note that you have to store the ordering around the vertex explicitly, you cannot compute this on the fly)

More precisely, to determine where to place a new triangle incident to vertex $$v$$ in the ordering around $$v$$, consider all pairs of consecutive edges $$(e_i,e_{i+1})$$ that do not form a triangle with vertices $$(a,b)$$ being their endpoints not equal to $$v$$. Let $$(x,y)$$ be the new vertices of the triangle. Place the edges of the new triangle in between the pair of edges $$(e_i,e_{i+1})$$ such that $$\min(\|a-x\|+\|b-y\|, \|a-y\|+\|b-x\|)$$ (or another similarity measure of the pairs $$(x,y)$$ and $$(a,b)$$) is minimized.

For example, in the figure below, vertices with the same colors are the pairs we'd compare with our new vertices $$x,y$$.

1: I will assume that you just have a graph for now, but perhaps a simplicial complex might be a better description? I don't think it matters much for the discussion here, though.

• Thanks! Defining some keywords like rotation system I can use to do more research on this topic is definitely helpful! With regards to "insert the new triangle in between the pair with smallest distance to the new triangle" - could you clarify this a bit more? I'm not sure what you mean by smallest distance between triangles? Sep 20, 2020 at 16:09
• Well, I'm a bit vague on the distance part because I'm not sure what would work. It kind of depends on what you want to do, which is also not entirely clear to me. If you don't yet know precisely what it is you want, you should either look at what others did that had similar goals to you, or experiment on your own. I can give more concrete rule, but you should probably treat it as just a starting point. Sep 20, 2020 at 17:30
• What I want to do is to create a simple 3d modeling software using half-edge. I add new points in R3 space and generate edges or polygons from them. In this particular case I would like to create a new triangle that has common vertex with other triangles. So I would create two new vertices and select the common vertex and generate a new triangle by adding 6 new half-edges and connected them with the rest of the structure. Or would you like to know some other specifics? Sep 20, 2020 at 18:26
• Yes the edges of same triangle are consecutive (if they were not consecutive triangles would overlap each other right(?)). I tried to visualize what you described imgur.com/a/MBH06MU. Say I have three triangles and I would like to add new one with new vertices $(x,y)$. I also marked all consecutive edges radiating from the common vertex. I'm not sure what you mean by end-vertices $(a,b)$? Sep 20, 2020 at 18:33
• To give an example I would like to create something similar to OpenMesh graphics.rwth-aachen.de/software/openmesh Sep 20, 2020 at 18:37