select and store a list of verts along a portion of a contiguous edge

[charles le guen]

Hi guys

Any idea how to select and store an ordered list of verts along a portion of a contiguous edge?

In other words:

Given two selected vertices (vert1 and vert2) on a contiguous edge, select all of the verts from vert1 to vert2 (inclusive) and store them in that order for future manipulation.

That would allow one to do stuff to them (such as create a joint chain snapped to those points, create cloth constraints along those points, etc).

Right now it's easy to select the edges manually and convert that selection to verts and then run scriptX.  The problem with that semi-automated process is that the order of verts isn't in a straight line from vert1 to vert2.

Maya has a command called shortestEdgePath, but it seems to be flawed in how it calculates the shortestEdgePath (and since it selects an edge path rather than an ordered set of verts, even if it worked well, it still wouldn't produce the result I'm looking for)

Thanks for any ideas you may have to share

C

[Paul Molodowitch]

What exactly do you mean by a "contiguous edge"?

Do you mean the edge chain that connects them that has the fewest number of edges? The shortest total distance?

- Paul

C

--
view archives: http://groups.google.com/group/python_inside_maya
change your subscription settings: http://groups.google.com/group/python_inside_maya/subscribe

[charles le guen]

yes, exactly

[Ted Charlton]

Select the edges and the initial vertex.

Place the edges in a set.

Convert edges to vertices and place them in a set as well.

Remove the initial vertex from the set of vertices

Beginning with your initial vertex, convert vertex to edge.

Compare the returned edges to the membership of your edge set to identify the edge you need to follow.

Now convert the found edge to vertices.

The only vertex in the set out of the two returned from the edge to vertices operation is the next vertex.

Repeat thus walking the selected edges in order, storing the vertices in the desired order.

[Jesse Capper]

How is the calculation of shortestEdgePath flawed? It's worked in the situations I've tried it, though they certainly haven't been exhaustive.

[charles le guen]

create a default polySphere in a new scene and run these two lines: 

import pymel.core as pm

pm.polySelect( 'pSphere1', shortestEdgePath=(274, 260) )

You'll see shortestEdgePath finds a route that isn't a straight line between the two verts.

[Jesse Capper]

The undocumented command polySelectSp works for me in that situation, it also returns verts and not edges. The verts still aren't ordered so you would have to solve that from the return list using something like Ted's method.

import pymel.core as pm

sph = pm.polySphere()[0]

pm.select(pm.polySelectSp( '%s.vtx[%d]' % (sph, 260),'%s.vtx[%d]' % (sph, 274) , q=True, loop=True ))

[Paul Molodowitch]

Interesting that polySelect(shortestEdgePath=1) doesn't, in fact, select the shortest edge path... sounds like a bug. Have you submitted it?

 

And, unfortunately, polySelectSp(loop=1) isn't what he's looking for either - it bases it's selection on topology. Ie, if you have an edge incoming to a vert that has 4 total edges on it, it will always select as the outgoing edge the "middle" edge relative to it, topology wise.  This can result in in results that are very far from the "shortest path".

Well.. if you want to roll your own, you can always try a "greedy algorithm".  You can look up that term online for more details, but the basic idea would go something like this:

You would keep a list of potential edge/vert paths, with their total distance, and sorted by their total distance. (Initially, your list of potential paths would only have a single edge path, and that edge path would only have a single vert - your start vert - and no edges.) Then, at each point in the algorithm, pop off the shortest current edge path and inspect it; if it ends with your desired end vert, you're done. Otherwise, find all other edges which connect to that path's end vert, and create a new edge path for all of these.  (So, ie, if you started with an edge path of length 6 whose end vert connected to 4 other edges, then you would create 4 new edge paths of length 7.)  For each of these new edge paths, update their total length, and add them into your sorted list in the correct position.  Then repeat the algorithm until you find your desired vert (or run out of paths to try).  The edge path you end up finding is guaranteed to be the shortest (or, at least, tied for the shortest) path between your verts.

Hope that helps...

- Paul

[Jesse Capper]

Ah, I was thinking he meant along an edge loop.

How would you generate the initial list of potential paths/find all other edges that connect to an end vert?

[Paul Molodowitch]

Well, like I said, the initial list would only have one trivial "path" - one that only had a single vert, that represented both your start and end point.

As for querying connection information - I think you can use either polyInfo or the MItMesh*.getConnected* methods for that.  The MItMesh*.getConnected* methods are also wrapped by pymel on the Mesh* component classes. Be warned though - the exact definitions maya uses for "connected" for the various components can be somewhat inconsistent / confusing...

- Paul

--

[Jesse Capper]

Ah, not sure why I didn't get that at first. So you're continually expanding out from the initial vertex and testing every edge that's connected to it; then repeating that process for the verts at the ends of all those edges, etc, etc? 

Are there other (more complex) methods that could be used to reach the same solution more efficiently, or is the time it takes to traverse edges fast enough to not worry about it?

Thanks!

[Paul Molodowitch]

There probably are somewhat faster methods to get the answer - but this is actually a particular example of what's more generally known as "the travelling salesman problem" - http://en.wikipedia.org/wiki/Travelling_salesman_problem - a problem that's known (and, in fact, proven) to be "very hard" to compute correctly... and my method is a known "fairly good/fast" solution to the problem.

Note - it seems that the algorithm I've outlined is actually different from what the wikipedia mentions as a "greedy" solution to the problem.  Their method is much simpler, and they define it http://en.wikipedia.org/wiki/Greedy_algorithm as "At each stage visit an unvisited city nearest to the current city"... wheres the one I outlined might be described as "At each stage examine the current shortest path, and generate new paths from it".

One optimization to what I outlined earlier though - you should keep a mapping from "final vert" to the current shortest path to that vert (or, perhaps, to it's index within your sorted list); then, when inspecting the "current shortest path", and generating new paths from it, check if any of your potential new paths have a "final vert" you've already visited; if not, add it like normal; if so, check if the new path has a length shorter than the old path ending at that vert, and if not, skip it - otherwise, update the vert-to-shortest-path mapping, and remove the old-shortest-path from your sorted list of paths.

That way, the sorted list of paths will always contain a list of the shortest-known-paths to verts, with no duplicate end-verts in it.

Also - since this IS something which could take a while, it's definitely a case where it should be implemented in C++ if possible... (Though you can always prototype in python if you want to get a better understanding of the algorithm first...)

- Paul