This script overcomes a problem with Blender’s Join as Shapes function: mismatched vertex indexing. Watch the video for more.
Here is the script.
Just save it somewhere and install it using the usual method.
join_as_shapes_by_topology.py
bl_info = {
"name" : "Join as Shapes by Topology",
"description" : "Uses topological BFS to overcome scrambled vertex indices",
"author" : "Michael Thomas Greer",
"version" : (1, 1),
"blender" : (2, 80, 0),
"location" : "Object Data Properties > Shape Keys > Shape Key Specials",
"warning" : "",
"doc_url" : "https://blenderartists.org/t/join-as-shapes-by-topology-new-add-on-i-wrote/1512963",
"support" : "COMMUNITY",
"category" : "Mesh"
}
import bpy, bmesh
from collections import deque
#--------------------------------------------------------------------------------------------------
# Join as Shapes by Topology
#--------------------------------------------------------------------------------------------------
# This script adds (or updates) a shape key using a source object mesh.
# It traces the topology of each mesh's edges. This is to repair problems
# caused when the vertex indices of the two meshes become out of sync (due
# to editing or something).
#
# 0 Save your work!
# 1 Select Source object
# 2 Tab to EDIT MODE
# 3 Select three connected vertices belonging to a single face
# 4 Tab to OBJECT MODE
# 5 Select Target object
# 6 Tab to EDIT MODE
# 7 Select the corresponding three vertices of the corresponding face, in the SAME ORDER
# 8 Tab to OBJECT MODE
# 9 Select Source Object then Shift+Select the Target Object
# 10 Run this script
#
# A new shape key in the Target object will be created with the name of the Source object.
# The two meshes must have the same edge topology!
#--------------------------------------------------------------------------------------------------
# ALGORITHM DESCRIPTION
#--------------------------------------------------------------------------------------------------
# This is just a BFS across all faces in the mesh.
#
# Each face is discovered by following edge order.
#
# Collected is a mapping of vertices in the order in which they were encountered.
# The user specifies the initial order by selecting three corresponding vertices on each mesh.
#
# Since both meshes are traversed the same way, the order in which vertices are encountered
# are identical for both meshes. Thereafter we can simply lookup vertices by the encounter
# index to modify the target mesh's vertex positions to match the source mesh's.
def show_message(message = "", title = "Join as Shapes by Topology", icon = 'INFO'):
"""Display a message to the user, via popup, print, and clipboard."""
def draw(self, context):
self.layout.label(text=message)
bpy.context.window_manager.popup_menu(draw, title = title, icon = icon)
bpy.context.window_manager.clipboard = message
print(title + ":\n " + icon + ": " + message)
class Error(Exception):
def __init__(self, message):
self.message = message
def find_first_face_index(vert0, vert1, vert2): # BMVert, BMVert, BMVert
"""Find the initial face on the mesh using the three vertices the user has selected"""
fs0 = [f.index for f in vert0.link_faces]
fs1 = [f.index for f in vert1.link_faces]
fs2 = [f.index for f in vert2.link_faces]
fs = list(set(fs0) & set(fs1) & set(fs2))
if len(fs) != 1:
raise Error("The three selected vertices must belong to the same face")
return fs[0]
def find_next_face_index(f0, vert0, vert1): # index, BMVert, BMVert
"""Find the face adjacent to face[f0] sharing edge (v0, v1)"""
fs = [f.index for f in vert0.link_faces if (f in vert1.link_faces) and (f.index != f0)]
match len(fs):
case 0: return None
case 1: return fs[0]
raise Error("Non-manifold mesh -- script requires no more than 2 faces per edge!")
def find_index_of(xs, p):
"""Return the index of the first element in xs that satisfies predicate p, else -1"""
return next((n for n, x in enumerate(xs) if p(x)), -1)
def walk_face_edges(mesh, f, v0, v1): # mesh, index, index, index
"""
Returns a list of edges to add to build_vertex_map().edges_yet_to_process.
Both edges and per edge vertices are returned in order of topological traversal!
See build_vertex_map().edges_yet_to_process
"""
edges = []
face_edges = mesh.faces[f].edges
try:
while len(edges) < len(face_edges):
edges.append((f, v0, v1))
edge = next(e for e in face_edges if e.other_vert(mesh.verts[v1]) not in [None, mesh.verts[v0]])
v0, v1 = v1, edge.other_vert(mesh.verts[v1]).index
except:
raise Error("Mesh data is corrupt")
return edges
def comparable_edge(v0, v1): # index, index
"""
Return a tuple where v0, v1 are in strictly-increasing order.
While order matters when assigning vertices a traversal index,
it is possible (likely even) that an edge may be traversed in a
different direction when following the edges of the adjoining face.
Thus, in order to facilitate set membership testing (whether or not a
particular edge has yet been encountered) we store the indices in value
order.
See build_vertex_map().edges_processed
"""
return (v0, v1) if v0 < v1 else (v1, v0)
def build_vertex_map(mesh):
"""
Returns dictionary { vertex_traversal_index : blenders_vertex_index, ... }
Precondition: 3 === len(mesh.select_history)
"""
mesh.verts.ensure_lookup_table()
mesh.edges.ensure_lookup_table()
mesh.faces.ensure_lookup_table()
v0 = mesh.select_history[0]
v1 = mesh.select_history[1]
v2 = mesh.select_history[2]
# We actually build the INVERSE dictionary...
vmap = {}
f0 = find_first_face_index(v0, v1, v2)
faces_encountered_so_far = set({f0}) # set of mesh face indices
# A queue of edges to be processed (push back, pop front)
# Edge and vertex order is important!
edges_yet_to_process = deque([ (f0, v0.index, v1.index) ])
# Set of edges we have already handled
edges_processed = set() # {comparable_edge, ...}
while len(edges_yet_to_process) > 0:
# Get next edge to process
f, v0, v1 = edges_yet_to_process.popleft()
if comparable_edge(v0, v1) in edges_processed:
continue
# Update edge tracking and vertex dictionary
edges_processed.add(comparable_edge(v0, v1))
if v0 not in vmap: vmap[v0] = len(vmap)
if v1 not in vmap: vmap[v1] = len(vmap)
# Find the other face (if any) sharing the edge
f = find_next_face_index(f, mesh.verts[v0], mesh.verts[v1])
if (f is None) or (f in faces_encountered_so_far):
continue
faces_encountered_so_far.add(f)
# Walk the edges of the face, starting with v0 --> v1
edges_yet_to_process += walk_face_edges(mesh, f, v0, v1)
# Invert the wrong-way dictionary we built for return
return { v:k for k,v in vmap.items() }
def join_as_shapes_by_topology():
if len(bpy.context.selected_objects) != 2:
raise Error("Select Source then Target objects before running script")
target = bpy.context.selected_objects[0]
source = bpy.context.selected_objects[1]
if (bpy.context.active_object != target):
target = bpy.context.selected_objects[1]
source = bpy.context.selected_objects[0]
if (target.type != 'MESH') or (source.type != 'MESH'):
raise Error("Both Source and Target objects must be MESH objects")
# Add shape key (if necessary)
if target.data.shape_keys is None:
target.shape_key_add(name="Basis", from_mix=False)
sk = target.data.shape_keys.key_blocks.get(source.name)
if sk is None:
sk = target.shape_key_add(name=source.name, from_mix=False)
# Access bmesh data
bpy.ops.object.mode_set(mode='EDIT')
target_mesh = bmesh.from_edit_mesh(target.data)
source_mesh = bmesh.from_edit_mesh(source.data)
if len(target_mesh.select_history) != 3:
raise Error("Target object " + target.name +
": Select three connected vertices belonging to a single face")
if len(source_mesh.select_history) != 3:
raise Error("Source object " + source.name +
": Select the three vertices corresponding to those in the target mesh, in the SAME ORDER")
# Build vertex maps/dictionary (topology traversal vertex index --> bmesh vertex index)
try: target_vmap = build_vertex_map(target_mesh)
except Error as e: raise Error(target.name + ": " + e.message)
try: source_vmap = build_vertex_map(source_mesh)
except Error as e: raise Error(source.name + ": " + e.message)
# Update target Shape Key vertex coordinates to match source vertex coordinates
sk = target_mesh.verts.layers.shape[sk.name] # <-- BMLayerItem
N = min(len(target_vmap), len(source_vmap))
for n in range(N):
target_mesh.verts[target_vmap[n]][sk] = source_mesh.verts[source_vmap[n]].co
# All done
bpy.ops.object.mode_set(mode='OBJECT')
show_message('Done (' + str(N) + " vertices)")
class Join_as_Shapes_by_Topology(bpy.types.Operator):
"""
Uses topological BFS to overcome scrambled vertex indices
"""
bl_idname = "object.join_as_shapes_by_topology"
bl_label = "Join as Shapes by Topology"
bl_options = {'REGISTER', 'UNDO'}
def execute(self, context):
try:
join_as_shapes_by_topology()
except Error as e:
bpy.ops.object.mode_set(mode='OBJECT')
show_message(e.message, icon='ERROR')
return {'FINISHED'}
def join_as_shapes_by_topology_menu_func(self, context):
self.layout.operator(Join_as_Shapes_by_Topology.bl_idname)
def register():
bpy.utils.register_class(Join_as_Shapes_by_Topology)
bpy.types.MESH_MT_shape_key_context_menu.append(join_as_shapes_by_topology_menu_func)
def unregister():
bpy.utils.unregister_class(Join_as_Shapes_by_Topology)
bpy.types.MESH_MT_shape_key_context_menu.remove(join_as_shapes_by_topology_menu_func)
if __name__ == "__main__":
register()
Comments and Questions welcome.
