4
$\begingroup$

I could select a couple of vertices and get the path by calling this:

bpy.ops.object.mode_set(mode = 'EDIT') 
bpy.ops.mesh.select_mode(type="VERT")
bpy.ops.mesh.select_all(action = 'DESELECT')
bpy.ops.object.mode_set(mode = 'OBJECT')
obj.data.vertices[0].select = True
obj.data.vertices[3].select = True
bpy.ops.object.mode_set(mode='EDIT')
bpy.ops.mesh.shortest_path_select()

Then I would get the path of vertices properly selected, I could get them in python by iterating through all of them and check if .select = True.

The problem I have is that I need the list of vertices sorted following the path, from the initial one to the last one, not the list sorted by the vertex index.

Is that possible with shortest_path_select ?

$\endgroup$

2 Answers 2

4
$\begingroup$

As of 3.5.1, there is no built-in function to fully handle this task. However, using v.link_edges to obtain the edges connected to a vertex offers significant utility. Summarizing how the code works, this method:

  • uses bm.verts instead of obj.data.vertices and selects the shortest path

  • enters a while loop to append to a sorted list (terminates when it reaches the final index)

  • within the while loop I

    1. get the connected edge to the vertex in question (starts at initial vertex), which is the only linked edge that is also selected

    2. get the connected vertex to the vertex in question

    3. append the connected vertex to the sorted list and assign vertex in question to the freshly found connected vertex to use for the next iteration

    4. deselects the current connected edge so that the next connected edge can be found within the next iteration.

Note: Upon obtaining the vertices of the next edge, it's unknown whether verts[0] or verts[1] of this edge is truly the next connected vertex. Therefore, if the 0th vert is found to have already been sorted, the true next connected vert is guaranteed to be the 1st vert, otherwise it's the 0th vert.

import bpy
import bmesh

# get the mesh object 
obj = bpy.context.object

# choose initial and final indices
initial = 137
final  = 37

# select shortest path between starting and ending points
bpy.ops.object.mode_set(mode = 'EDIT')

# create sphere bmesh
me = obj.data
bm = bmesh.from_edit_mesh(me)

# make sure the BMesh is up-to-date
bm.verts.ensure_lookup_table()

# get bmesh verts
verts = bm.verts

# set mode to vert select 
bpy.ops.mesh.select_mode(type= 'VERT')

# deselect all
bpy.ops.mesh.select_all(action = 'DESELECT')

# select verts at these indices
v = verts[initial]
v.select = True
verts[final].select = True

# select shortest path
bpy.ops.mesh.shortest_path_select()

# initialize sorted vertices list
sorted_verts = [v]

# initialize set of indices that have already been sorted
sorted_indices = {initial}

# while loop to append to sorted verts
while v.index != final:

    # get connected edge as a single-element generator
    connected_edge = (e for e in v.link_edges if e.select)

    # get the edge itself
    e = next(connected_edge)

    # get 0th vert of the edge
    v = e.verts[0]
    
    # not gauranteed that verts[0] is the "next" vertex. It could just as well be verts[1]
    # rather check if index is in set of already sorted indices compared to checking if v is in sorted_verts list
    if v.index in sorted_indices:
        v = e.verts[1]
    
    # append to list and add to set
    sorted_verts.append(v)
    sorted_indices.add(v.index)
    
    # deselect connected edge
    e.select = False
 
print('\n------ sorted vertex indices --------')
for v in sorted_verts:
    print(v.index)

# may be of benifit to again select the shortest path for visualizations after the script has already ran   
#verts[initial].select = True
#verts[final].select = True
#bpy.ops.mesh.shortest_path_select()

[1]: https://i.stack.imgur.com/MrrUI.png

As you can see, the magnitude of the printed indices decrease between some indices and increase between other indices in the sorted list, indicating this list is not sorted by the magnitude of the indices.

enter image description here

Image addressing the mistake I made caught by @MarkusVonBroady

$\endgroup$
7
  • 1
    $\begingroup$ Great! I thought there was something built-in for this, but your solution is just as good, Thanks! $\endgroup$
    – Walrfi
    Jun 20, 2023 at 7:17
  • 1
    $\begingroup$ Look at this spiral: i.imgur.com/Zbuh2yl.png The closest vertex is not always the next vertex of the closest path!. Instead for each vertex you should look for a connected vertex, present in the list (actually set for performance) of vertices. Once moving through a vertex, remove it from the set (so you don't move back + performance) $\endgroup$ Jun 20, 2023 at 23:02
  • $\begingroup$ Thanks for noticing @MarkusvonBroady please see my edit $\endgroup$ Jun 21, 2023 at 3:07
  • 1
    $\begingroup$ pairs[edge_vert_indices[1]] = edge_vert_indices[0] is very sus, why this way, rather than the other way around - because when you tested the other way around you got an error? 😜 You have 50% chance to get an error on first iteration, because either initial was the first vertex of its edge (and then it won't be a key in a dictionary and you will get the KeyError) or the second, in which case you're lucky (for this iteration at least. Try this, a new plane, subdivide with 3 cuts, initial=0 and final=12 - I get the error. $\endgroup$ Jun 21, 2023 at 9:40
  • 1
    $\begingroup$ If you used bmesh, you could start with the v = bm.verts[initial], then find the selected connected edge e = next(e for e in v.link_edges if e.select), deselect the edge e.select = False, get the other vert v = e.other_vert(v), rinse and repeat 👍 $\endgroup$ Jun 21, 2023 at 9:44
2
$\begingroup$

This is how I would code it:

start = 0
end  = 3

import bpy, bmesh

bm = bmesh.from_edit_mesh(bpy.context.object.data)
bpy.ops.mesh.select_all(action = 'DESELECT')
bm.verts[start].select = True
bm.verts[end].select = True
bpy.ops.mesh.shortest_path_select()

indices = [start]
v = bm.verts[start]
edge = None
for _ in range(len(bm.verts)):  # protect from hanging
    edge = next(e for e in v.link_edges if e.select and e!=edge)
    v = edge.other_vert(v)
    indices.append(v.index)
    if v.index == end:
        break
print("Shortest Path - Vertex indices:", *indices, sep="\n")
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .