What I want for this specific example is to parent a collection of objects to each other in such a way that we have a linear chain of parent-child relations. On top of that I want this chain to be as short as possible, that is, going from parent to child along the chain of objects, I want the length of this path to be minimal.

To illustrate what I mean, the first image shows what I am after while the second image shows a decidedly sub-optimal chain of parent-child relations:

The problem itself is well known (finding the shortest Hamiltonian path, closely related to the Traveling Salesman problem) but unfortunately solving this problem exactly is very costly in computational terms.

The code below shows a working but very naive implementation that I intend to use as a starting point for later improvements. It works in the sense that it finds the shortest path between a collection of selected objects and creates the chain of parent-child relations but the time to compute the solution increases more that exponentially (factorial to be precise: 8 objects will for example take 0.1 seconds, 9 objects will take nine times as much, i.e. almost 1 second and 10 objects will take ten times as much still, i.e. 10 seconds and so on). To make this remotely useful, for example to chain a necklace of 100 beads, we will have to implement some clever heuristics. That is something I intend to cover in future articles.

## Code availability

The current code is shown in full below but the add-on as it evolves will be available on GitHub. (click 'Raw' to download the Python file)import bpy from mathutils import kdtree from itertools import permutations as perm from functools import lru_cache from time import time from math import factorial as fac bl_info = { "name": "Chain selected objects", "author": "Michel Anders (varkenvarken)", "version": (0, 0, 201701220957), "blender": (2, 78, 0), "location": "View3D > Object > Chain selected objects", "description": """Combine selected objects to a list of parent-child relations based on proximity""", "category": "Object"} def object_list(objects): """ Return the shortest Hamiltonian path through a collection of objects. This is calculated using a brute force method that is certainly not intented for real life use because for example going from ten to eleven objects will increase the running time elevenfold and even with caching expensive distance calculations this quickly becomes completely unworkable. But this routine is intended as our baseline algorithm that is meant to be replaced with an approximation algorithm that is 'good enough' for our purposes. """ @lru_cache() def distance_squared(a,b): return (objects[a].location-objects[b].location).length_squared def length_squared(chain): sum = 0.0 for i in range(len(chain)-1): sum += distance_squared(chain[i],chain[i+1]) return sum s = time() shortest_d2 = 1e30 shortest_chain = None n_half = fac(len(objects))//2 for i,chain in enumerate(perm(range(len(objects)))): if i >= n_half: break d2 = length_squared(chain) if d2 < shortest_d2: shortest_d2 = d2 shortest_chain = chain print("{n:d} objects {t:.1f}s".format(t=time()-s, n=len(objects))) return [objects[i] for i in shortest_chain] class ChainSelectedObjects(bpy.types.Operator): bl_idname = 'object.chainselectedobjects' bl_label = 'Chain selected objects' bl_options = {'REGISTER', 'UNDO'} @classmethod def poll(self, context): return (context.mode == 'OBJECT' and len(context.selected_objects) > 1) def execute(self, context): objects = object_list(context.selected_objects.copy()) for ob in objects: ob.select = False ob = objects.pop() first = ob while objects: context.scene.objects.active = ob child = objects.pop() child.select = True bpy.ops.object.parent_set(keep_transform=True) child.select = False ob = child first.select = True context.scene.objects.active = first return {"FINISHED"} def menu_func(self, context): self.layout.operator( ChainSelectedObjects.bl_idname, text=ChainSelectedObjects.bl_label, icon='PLUGIN') def register(): bpy.utils.register_module(__name__) bpy.types.VIEW3D_MT_object.append(menu_func) def unregister(): bpy.types.VIEW3D_MT_object.remove(menu_func) bpy.utils.unregister_module(__name__)

## No comments:

## Post a Comment