Get vertices of an edge-loop and sort them around their unit circle

[Cieroceramics]

hello fine Tech artists.
I am trying to build a tool for maya that will create or snap joints around an edge loop.

such that the joints are placed in order around the circle.
its very important that the joints are in order because its part of my workflow.

to achieve this, I have found medium success storing the vertices, and sorting them using the aTan2 function.

however this only works sometimes, as I believe arcTan only works for one quadrant of a circle.

just wondering if anyone else has come across this issue and has any bright ideas.

[tfox_TD]

The atan function not working for the whole circle is the reason that atan2 exists. The atan2 function takes 2 arguments and uses their signs to make it work for the whole circle. Which, of course, means you need to pass signed values to that function. And for it to work the way you want it, either the verts have to be centered around the origin, or you have to get the angles relative to some center point. This can absolutely work, but there’s lots of failure cases.

---

Now for the fun part! Is it guaranteed that it will be a unit circle? Would the tool be more useful if you didn’t require that? Could a function that sorts vertices in any edge loop be useful? I say YES!

So I was going to give you general instructions on how to do this, but then … well. Here, have some code!

For the sake of simplicity, I assumed a couple things: First, the loop connects back to itself. Second, the loop doesn’t cross itself. You can take those things into account, but that would require a much more complicated function. Also, this code is completely untested.

Basically, this uses a dictionary of neighboring vertices to walk around the edge loop, one vert at a time.

def sortVertRing(vertices):
    # Here's a sneaky edge case. 3 vertices are always sorted
    if len(vertices) == 3:
        return vertices

    neighborDict = {}
    for vert in vertices:
        # You'll have to implement this `getNeighbors` function yourself
        rawNeighbors = getNeighbors(vert)
        # Ignore any vertices that aren't already in the edge loop
        loopNeighbors = [n for n in rawNeighbors if n in vertices]
        # I'm assuming that Vertices is a non-intersecting loop
        # so any value list in neighborDict will have length of 2
        assert len(loopNeighbors) == 2
        neighborDict[vert] = loopNeighbors

    # Create the output list
    vertLoop = []

    # It doesn't matter which vertex we start with because we can
    # pick a new starting vert after the fact really easily
    start = neighborDict.keys()[0]
    vertLoop.append(start)

    # Then it doesn't matter which neighbor vertex we go to from there
    # because we can easily reverse the list after the fact
    vertLoop.append(neighborDict[start][0])

    # Now follow the loop around until we get back to the beginning
    while vertLoop[0] != vertLoop[-1]:
        # Get the neighbors of the last vert in the loop so far
        # nextNeighbors should have length 2
        nextNeighbors = neighborDict[vertLoop[-1]]
        # We don't want to go backwards, so if nextNeighbors[0]
        # is already in the list, pick the other neighbor
        if nextNeighbors[0] == vertLoop[-2]
            vertLoop.append(nextNeighbors[1])
        else:
            vertLoop.append(nextNeighbors[0])

    # Since the first and last item in the list are the same
    # because of the while loop, chop off the last thing
    return vertLoop[:-1]

[Cieroceramics]

holy smokes, the reason I was experiencing the issue is likely because I wasn’t averaging out the vertices. but as you say, there are several failure cases that I want to be able to address.
and then you put this code here and it sort of completely blew my mind.
on holiday right now,
but I will make a follow up post after I try this with more details.

I hope this doesn’t depends too heavily on vert order. because sometimes I get models that have vertices in just completely bonkers positions

[tfox_TD]

It doesn’t depend at all on vert order, and that’s by design. Each vert knows its neighbors to both sides regardless of the vertex ordering. The only thing we don’t know is if the left vert, or the right vert is the first neighbor in the list.

Instead of using numbers, I’ll use letters. Hopefully that will illustrate that numbers don’t matter, all that matters is the relationship in neighborDict.

neighborDict = {
    a: [e, b],
    b: [c, a],
    c: [b, d],
    d: [c, e],
    e: [a, d],
}

Say we start the while loop with vertLoop = [a, b]. As long as we’ve got 2 verts that are neighbors as the first 2 items in vertLoop, the code will work (For instance, it would still work if we started with vertLoop = [e, d])

So we look in the dict for the last item in the current loop (that’s b in this case), and see that its neighbors are [c, a]. So we check, is the first item c right before b in vertLoop? It’s not, so we can append that to vertLoop.

Now we’ve got vertLoop = [a, b, c], so we look in the dict and find c and see its neighbors are [b, d]. So we check is b right before c in vertLoop? It is, so we can append the other neighbor to our list. In this case, that’s d.

This keeps going like that until we get to vertLoop = [a, b, c, d, e, a]. Notice how a got added to the end? Well, now the first and last item in the list are the same. That means we’ve come back to where we started, so we’ve got an entire loop! So we can just chop off that ending a and return.

Now that you’ve got the loop, it’s easy to do something like
vertLoop = reversed(vertLoop) to reverse it.
Or vertLoop = vertLoop[3:] + vertLoop[:3] to shift the loop so you’re starting with the item at index 3.

[Cieroceramics]

well your solutions works like a charm,
the remaining bits are on me.

first off is the code I am using to get neighbors.
I tried searching up polyInfo and polyListComponentConversion but my code ended up being a complete mess of string parsing.
so I ended up with this instead.

def getNeighbors(vert):
    list = []
    for dir in ("up", "down", "left", "right"):
        mc.select(vert)
        mc.pickWalk(direction = dir)
        if mc.ls(sl=True)  not in list:
            list.append(mc.ls(sl=True))
    return list

which works as long as I change your loopNeighbors = [n for n in rawNeighbors if n in vertices]
to be loopNeighbors = [n for n in rawNeighbors if n in vertices[0]]

however it only works when the camera is in a good position, which isn’t a very friendly imo.
what do you think? polyInfo node and loop through string manipulations til my PC starts smoking ?

[tfox_TD]

Funny story: I actually got to use the code I wrote for you the other day at work!
That means I got to flesh out that code into something a bit more production ready. (Also, this geometry connectivity stuff is my absolute favorite task, so I maaaayyyy have gone a bit overboard )

One annoying thing (as you found out) is the string parsing. I handle that with mayaSelRange
Then I get the neighbors with buildNeighborDict. No pickwalking required. Also, I have a very strong aversion to doing anything with selection during the execution of a script.
Then with a little thought, I figured out how to handle multiple loops and loops that don’t connect back to themselves. Thats what sortLoops does.

from maya import cmds

def mayaSelRange(vals):
    """Convert maya cmds.ls() component selection list into indices

    Arguments:
        vals (list): A list of components like what you get out of cmds.ls(sl=True)

    Returns:
        list: A list of integer indices
    """
    out = []
    for val in vals:
        nn = val.split('[')[1][:-1].split(':')
        nn = list(map(int, nn))
        out.extend(range(nn[0], nn[-1] + 1))
    return out


def buildNeighborDict(vertColl):
    """ Parse vertices into a dictionary of neighbors, limited to the original vertex set

    Arguments:
        vertColl (list):  A list of verts like what you get out of cmds.ls(sl=True)

    Returns:
        dict: A dictionary formatted like {vertIndex: [neighborVertIdx, ...], ...}
    """
    # Get the object name
    objName = vertColl[0].split('.')[0]
    verts = set(mayaSelRange(vertColl))
    neighborDict = {}
    for v in verts:
        vname = '{0}.vtx[{1}]'.format(objName, v)
        edges = cmds.polyListComponentConversion(vname, fromVertex=True, toEdge=True)
        neighbors = cmds.polyListComponentConversion(
            edges, fromEdge=True, toVertex=True
        )
        neighbors = set(mayaSelRange(neighbors))
        neighbors.remove(v)
        neighborDict[v] = list(neighbors & verts)
    return neighborDict


def sortLoops(neighborDict):
    """Sort vertex loop neighbors into individual loops

    Arguments:
        neighborDict (dict):  A dictionary formatted like {vertIndex: [neighborVertIdx, ...], ...}

    Returns:
        list of lists: A list of lists containing ordered vertex loops.
            Only if the loop is closed, the first and last element will be the same.
    """
    neighborDict = dict(neighborDict)  # work on a copy of the dict so I don't destroy the original
    loops = []

    # If it makes it more than 1000 times through this code, something is probably wrong
    # This way I don't get stuck in an infinite loop like I could with while(neighborDict)
    for _ in range(1000):
        if not neighborDict:
            break
        vertLoop = [neighborDict.keys()[0]]
        vertLoop.append(neighborDict[vertLoop[-1]][0])

        # Loop over this twice: Once forward, and once backward
        # This handles loops that don't connect back to themselves
        for i in range(2):
            vertLoop = vertLoop[::-1]
            while vertLoop[0] != vertLoop[-1]:
                nextNeighbors = neighborDict[vertLoop[-1]]
                if len(nextNeighbors) == 1:
                    break
                elif nextNeighbors[0] == vertLoop[-2]:
                    vertLoop.append(nextNeighbors[1])
                else:
                    vertLoop.append(nextNeighbors[0])

        # Remove vertices I've already seen from the dict
        # Don't remove the same vert twice if the first and last items are the same
        start = 0
        if vertLoop[0] == vertLoop[-1]:
            start = 1
        for v in vertLoop[start:]:
            del neighborDict[v]
        loops.append(vertLoop)
    else:
        raise RuntimeError("You made it through 1000 loops, and you still aren't done?  Something must be wrong")
    return loops

[Cieroceramics]

this solution has gotten me alot further along, I appreciate your input.
but I have a few more challenges. (which I am sure you have considered )

first is ordinance
while it is nice to have order I want to be able to say which vertex in the loop is first.
my strategy was to use a queue.

 vList = sortVertRing(vertices)
 vertexQue = deque (vList)
 vertexQue.rotate(shift)

and honestly this seems to satisfy my needs, but the problem comes when we try to add more.

direction.
It seems like the direction it decides to go, is completely random, and sometimes it would be nice to be able to depend on this.
my solution is to modify the above code to look like this.

        vQue = deque (vList)
        if isReversed:
            vQue = deque (vList.reverse())
        vQue.rotate(shift)

this makes sense in my brain, but I will admit I am not as intimate with your logic as I maybe should be.
it seems like I am back to where I started now with vertices being ordered all over the place.

one laaast little thing that may be the root of all my problems. and may be a completely different thing entirely. but here goes…
the first and the halfway vertices may need to be doubled up. what I mean by that is…
say for example I am snapping 12 joints to an edgeloop that has 10 vertices.
I want to be able to have joints 1 -6 snap to vertices 1-6 and joints 7-11 to snap to joints 6-10 and finally joint 12 will snap back to joint 1.
I have a solution but the logic is probably sloppy, and as I said, what is causing my problems.

for i, c in enumerate(joints):
            if len(vQue)+2 == len(joints):
                if i >= len(joints)/2:
                    i = i -1
            snap_joint_to_vert(vert = vQue[i],joint =  c)

this doesn’t really account for the last joint, and will throw an index out of bounds error if there are too many, but I am thinking I Need to rethink my approach here.

thanks again for all the help.

[tfox_TD]

First, shifting and reversing are really easy already. You don’t have to use a queue, and I talked about that in my second post:

Now that you’ve got the loop, it’s easy to do something like
vertLoop = reversed(vertLoop) to reverse it.
Or vertLoop = vertLoop[3:] + vertLoop[:3] to shift the loop so you’re starting with the item at index 3.

[edit] Oops, that shift doesn’t take into account when the the first and last items of the list are the same… If that’s the case you may want something like vertLoop[3: -1] + vertLoop[: 3 + 1]

But you say the direction it decides to go is random. And it absolutely is! However, you say you want to be able to depend on it being a certain direction, and my question is “Relative to what?” The relationship between vertices doesn’t change if you tumble the mesh, so if you’re looking for consistency, you’ve gotta define a viewpoint for it to be relative to. Like “Clockwise starting at the highest Y value when looking along -Z”. And that’s perfectly fine, but it has to be defined, and you have to come up with its rules. (This may be where you use an atan2)

As for your doubled up joints … take a look at the code in my third post. The docstring for sortLoops says “if the loop is closed, the first and last element will be the same.”

So given a loop like loop = [a, b, c, d, e, f, a], you can just slice it like this to build two sets of vertices.

loop[: (len(loop) // 2) + 1]  # [a, b, c, d]
loop[len(loop) // 2: ]  # [d, e, f, a]