shortest

In [1]:

"""
Given a mesh and two vertex indices find the shortest path
between the two vertices while only traveling along edges
of the mesh using a distance-weighted graph search.
"""

Out[1]:

'\nGiven a mesh and two vertex indices find the shortest path\nbetween the two vertices while only traveling along edges\nof the mesh using a distance-weighted graph search.\n'

In [2]:

import trimesh
import numpy as np
import networkx as nx

In [3]:

# test on a sphere mesh
mesh = trimesh.primitives.Sphere()

In [4]:

# edges without duplication
edges = mesh.edges_unique

In [5]:

# the actual length of each unique edge
length = mesh.edges_unique_length

In [6]:

# create the graph with edge attributes for length
g = nx.Graph()
for edge, L in zip(edges, length):
    g.add_edge(*edge, length=L)

In [7]:

# arbitrary indices of mesh.vertices to test with
start = 0
end = int(len(mesh.vertices) / 2.0)

In [8]:

# run the shortest path query using length for edge weight
path = nx.shortest_path(g,
                        source=start,
                        target=end,
                        weight='length')

In [9]:

# VISUALIZE RESULT
# make the sphere white
mesh.visual.face_colors = [255,255,255,255]
# Path3D with the path between the points
path_visual = trimesh.load_path(mesh.vertices[path])

In [10]:

# create a scene with the mesh, path, and points
scene = trimesh.Scene([path_visual, mesh ])

In [11]:

scene.show()

Out[11]: