Avoiding repetition artifacts with chaos mosaic

Chaos mosaic or chaos mapping is a method to extend limited size textures to huge uv-mapped surfaces while avoiding repetition artifacts.
You might have for example a grass covered ground texture that is detailed and would map to a 2 x 2 meter square quite well. If you would apply this to a 10 x 10 meter field and scale to its proper size, obvious repetition artifacts would be visible:

A chaos mosaic on the other hand would take randomly selected squares from a texture giving the appearance of an endless texture without repetition:

At close range you would still be able to make out the seams but for large objects seen from a distance this probably wouldn't be noticeable.
This technique only gives good results for non-patterned textures like groundcover, asphalt, plaster etc. but in those cases it might be just what you are looking for and it is quite fast.
In an older article I showed a chaos mosaic implementation in Open Shading Language but I like to work with the GPU as much as possible so I implemented the same technique in just nodes.

Node group


The noodle takes the uv-coordinates and then you can plug in the transformed coordinates into you texture. The scale can then be adjusted as needed. The rotation gives an additional amount of randomness to the final material but depending on the texture this might not always improve the visual quality.
The .blend file with the node group is available from my GitGub repository. Just download the chaosmap.blend and then in your own .blend use File → Append to select the nodegroup Chaosmap. It will then become available in the Add → Group menu of the node editor.

Improvements

To reduce the visibility of the seams between the tiles you can mix two chaos mosaics: the second one should use slightly offset and rotated uv-coordinates and then you can use for example a noise texture with a scale comparable to the actual textures to mix the two:

The result has less visible seams but is also somewhat blurred:

The highlighted area shows a visible seam:



Especially at close range:



Some details

You can examine the details of the nodegroup if you like but the basic principle is that it takes the original uv-coordinate, determines in which grid section this falls and then maps the relative position of the point inside this grid to a relative position inside randomly selected square in the unit uv-map. (This square is randomly selected but always the same square for the same grid section)

Tiny Blender Addon: Snap and transform

I was doing some arch-viz the other day and I was placing a lot of objects in a large scene. The objects where placeholders that I created on the spot and more often than not I needed to move the origin of the new mesh object to a selected vertex for easy positioning, scaling, rotating etc.

This is of course simple enough: select Snap cursor to selected in edit mode, switch to object mode and then select Transform → origin to 3d cursor.
But it is also a lot of actions for a simple operation, especially if you doing this a hundred times in a scene...

Another common scenario that I encounter is that I want to position the origin at the lowest point of a mesh. This is a little bit more involved as far as the code is concerned, a small explanation below for those who are interested in doing this on large meshes in a fast way.

Anyway, here is a small add-on: Edit mode origin tools. It does nothing fancy, it will just create two new menu entries in edit mode:
Mesh → Snap → Origin to selected,
Mesh → Snap → Origin to lowest vertex (along z-axis)
and save you some time :-)

Code availability

Download it from my GitHub repository (right-click on the first link and select save as ...) and in Blender go to File → User preferences → Add-ons → install from file ... (don't forget to enable it after installation. Note that the downloaded file is called snapandtransform.py while the add-on will appear as Edit mode transform tools)

Finding the location of the lowest vertex (fast)

If we want to get all the vertex coordinates fast, we got to switch to object mode first (line 2), get the number of vertices present (line 4) and the allocate an empty numpy array to hold all coordinates (line 7). Then we can use the foreach_get() method to get all coords (the co attribute of the verts array) in one go (line 8). It will be a flattened array so we have to reshape it to an array of 3-vectors (line 9).
 def execute(self, context):
  bpy.ops.object.editmode_toggle()
  me = context.active_object.data
  count = len(me.vertices)
  if count > 0:  # degenerate mesh, but better safe than sorry
   shape = (count, 3)
   verts = np.empty(count*3, dtype=np.float32)
   me.vertices.foreach_get('co', verts)
   verts.shape = shape
   verts2 = np.ones((count,4))
   verts2[:,:3] = verts
   M = np.array(context.active_object.matrix_world,
       dtype=np.float32)
   verts = (M @ verts2.T).T[:,:3]
   min_co = verts[np.argsort(verts[:,2])[0]]
   context.scene.cursor_location = min_co
   bpy.ops.object.origin_set(type='ORIGIN_CURSOR')
  bpy.ops.object.editmode_toggle()
  return {'FINISHED'}
Now all the coordinates will be in object space so we will want to convert all of them to world space. For this we need to multiply each of them with the matrix_world of the object. This is necessary because due to rotations the lowest vertex in object space need not be the lowest vertex in world space!

The world matrix is a 4x4 matrix (one that holds not only scale and rotation but translation as well) so we need to extend all our coordinate vectors with a fourth coordinate of 1 (lines 10,11). We also convert the matrix_world to a numpy array (line 12).

Line 14 is then where all the magic happens: we multiply our numpy world matrix M with our array of extend coordinates using the new @ operator. (new since Python 3.5 and especially added to allow numpy code to be better readable). The double transpose is to allow matrix multiplication of a 4x4 matrix with a list of 4-vectors and transform the result back again. The fourth coordinate of the result is dropped by the [:,:3] slice index.

Now that we have converted all coordinates to world space, all we have to do is the find the index of the coordinate with the lowest z-coordinate with argsort() and assign this to the position of the 3d-cursor before calling the origin-set() operator.

Nodeset: bugfix and small new feature


The nodeset add-on I talked about in a previous article had a small bug: if your texture set was something different than a collection of .png files the extra files that should be loaded automatically were in fact not loaded. This is fixed in the latest version (201707011445)

Code availability

The change is already committed in the GitHub repository. (right click the link to download).

New feature

Because of a bug in Blender a material with a normal map node will show up as all black if you use the experimental adaptive subdivision / micro polygon displacement. If you change the normal maps space from tangent to object this does not happen so I added a user preferences setting to do this automatically.

Converting Blender Filmic LUTs for use in Substance Painter

with the new Filmic Blender color management options getting a lot of attention I wanted to get the exact same looks when creating textures in Substance Painter.
Substance Painter supports LUTs in so called 3d format which are stored in .exr files. So our challenge is twofold: convert the bundled Blender Filmic LUTs to this format and of course to get results in Substance that match Blender as closely as possible.
The results of 3 of the filmic LUTs are compared side by side in the image below:

I made this comparison collage by keeping parameters like exposure (1) and gamma (also 1) the same in both Blender and Substance Painter and then took screenshots. I glued the screenshots together in GIMP. This way I could see all images on the same monitor. This is important because if the applied profiles are the same and both displays are sRGB, two monitors will still differ in their color response and it is fiendishly difficult to calibrate them (unless you have a very expensive monitor with the associated color calibration kit). My own monitors are not even the same brand so it is an easy trap to fall into if you compare images on two different monitors side by side.
Anyway, even this way when you have a close look the images are close in tone but not 100% identical and I am not sure what is causing this. There might be slight differences in camera aperture, focal blur and multiple importance sampling of the environment and of course Cycles' ray model is not the same as Iray's Substance painting mode renderer. Still, I think this is pretty close and useful to compare textures in Substance under different looks before transferring them to Blender.

How the LUTs were generated

I used the Python bindings of the OpenColorIO and OpenImageIO libraries to create a small script (code below). These are in fact the libraries Blender uses to work with color conversions.

The script takes a linear to linear transform that is encoded as an .exr image and creates a new .exr for each 'Look' in Blender's OCIO config file that is defined in the 'Filmic Log' process space.
The docs for the Python bindings for both libraries are not an easy read and the APIs have some small inconsistencies so it took some time to get it working. The code is far from beautiful but i commented the relevant parts. I am open to any critique that can help to improve the transforms.
Note that the code is not plug and play and i have no intention of improving that :-)

The Substance LUTs

They can be downloaded from my GitHub repository. They are bundled in one .zip file and should be unpacked before importing them in Substance Painter.

The code

#export LD_LIBRARY_PATH=/home/michel/ocio/lib
#export OCIO=/home/michel/Downloads/blender-2.78-b94a433ca34-linux-glibc219-x86_64/2.78/datafiles/colormanagement/config.ocio
#python 2.7
#
# run as
# python transformlook.py
#
# expects linear_to_linear.exr in the current directory and will write the transform there too

import OpenImageIO as OIIO  #  already installed using Ubuntu pkg manager
from sys import path
from array import array
path.append('/home/michel/ocio/lib/python2.7/site-packages/')
import PyOpenColorIO as OCIO

config = OCIO.GetCurrentConfig()

for look in config.getLooks():
 if look.getProcessSpace() == 'Filmic Log':
  lookname = look.getName()
  print(lookname)

  transform = OCIO.DisplayTransform()
  transform.setInputColorSpaceName(OCIO.Constants.ROLE_SCENE_LINEAR)
  transform.setView('Filmic')
  transform.setLooksOverrideEnabled(True)
  transform.setLooksOverride(lookname)
  transform.setDisplay('sRGB')
  processor = config.getProcessor(transform)

  # indentiy transform from https://support.allegorithmic.com/documentation/display/SPDOC/Color+Profile
  img = OIIO.ImageInput.open('linear_to_linear.exr')
  spec = img.spec()
  spec.set_format(OIIO.FLOAT) # for some reason this is not extracted from the image
  pixels = img.read_image()
  img.close()

  outfile = lookname + '.exr'
  transformedpixels = processor.applyRGB(pixels)
  imgout = OIIO.ImageOutput.create(outfile)
  ok=imgout.open(outfile, spec, OIIO.Create)
  if not ok:
   print(OIIO.geterror())
   break
  # ImageInput.read_image() returns a list of floats, and applyRGB(0 returns one too, but ImgOutput.write_image
  # expects an array of float and will die when passed a list. Bit inconsistent I think.
  a = array('d')
  a.fromlist(transformedpixels)
  imgout.write_image(a)
  imgout.close()


Nodeset: add a principled shader

Even though there are better paid and free PBR nodegroups/shaders available for Blender (for example from Jeffrey Hepburn or Remington Graphics) the new Principled BSDF (a.k.a. Disney shader or PBR shader) will no doubt prove popular with Blenderheads because it is so simple to use and gives decent results.

So I added an option to add this shader along with all the imported texture sets as well as a normal map node, basically giving you a one-click (almost) option to add a PBR material based on a set of textures from your favorite texturing tool. The new functionality is a available from Add -> Texture menu in the Node editor and sits alongside the original Set of images entry:

The resulting node setup (after selecting a set of textures) will look like this:
Note that this will of course only work with the new Blender 2.79 or with a recent daily build. If the Principled BSDF is not available in your version of Blender it will simply be omitted.

Code availability

The latest version of the code (201706251223) is available on GitHub (right click and select save as ... , then in Blender File -> user preferences ... -> Add-ons -> Install from file .... Don't forget to remove the previously installed version first!)

A short video demo:

Previous articles

Previous articles about the Nodeset add-on:
NODESET: IMPORT SUBSTANCE PAINTER TEXTURES INTO BLENDER
NODESET: TINY UPDATE MIGHT SAVE EVEN SOME MORE TIME
NODESET: SUPPORT FOR AMBIENT OCCLUSION MAPS
NODESET: MORE FLEXIBILITY

Substance Painter experiment



Inspired by a real life flower pot in our garden but weathered quite a lot more:


Sale: Blender Market turns 3


There is something to celebrate: Friday June 9 Blender Market turns 3.
To celebrate, many products will carry a 25% discount that day up til Sunday 11 (applied at checkout, and remember they are on Chicago time), including all products is my shop :-)

How to add a progress indicator to the Info header in Blender

There are many ways to signal progress for long running operations in Blender but the one I like best is the slider which is present when you render a scene. That kind of indicator is pretty clear and at the same time not to intrusive.



However there seems to be no way to add such a progress indicator for other purposes.

Now the menu bar at the top is actually the header of an area within the Info editor, so I tried to add a Panel to this header by specifying 'HEADER' for its bl_region_type. That didn't work: no errors but no visible header either.

So after some digging around I came up with a different approach: replacing the draw() method of the Info header. After all, everything is Python and being a truly dynamic language means we can monkey patch anything.

Basically we get the original draw() method, replace it with our own and call the original again. After this call we add a scene property to the layout of the header and use this float property to signal progress. The result looks like this:



The relevant code looks like this:

# update function to tag all info areas for redraw
def update(self, context):
    areas = context.window.screen.areas
    for area in areas:
        if area.type == 'INFO':
            area.tag_redraw()

# a variable where we can store the original draw funtion
info_header_draw = lambda s,c: None

def register():
    # a value between [0,100] will show the slider
    Scene.progress_indicator = FloatProperty(
                                    default=-1,
                                    subtype='PERCENTAGE',
                                    precision=1,
                                    min=-1,
                                    soft_min=0,
                                    soft_max=100,
                                    max=101,
                                    update=update)

    # the label in front of the slider can be configured
    Scene.progress_indicator_text = StringProperty(
                                    default="Progress",
                                    update=update)

    # save the original draw method of the Info header
    global info_header_draw
    info_header_draw = bpy.types.INFO_HT_header.draw

    # create a new draw function
    def newdraw(self, context):
        global info_header_draw
        # first call the original stuff
        info_header_draw(self, context)
        # then add the prop that acts as a progress indicator
        if (context.scene.progress_indicator >= 0 and
            context.scene.progress_indicator <= 100) :
            self.layout.separator()
            text = context.scene.progress_indicator_text
            self.layout.prop(context.scene,
                                "progress_indicator",
                                text=text,
                                slider=True)

    # replace it
    bpy.types.INFO_HT_header.draw = newdraw

The register() function defines two new scene properties: progress_indicator to hold a value in the range [0,100] which will be shown to indicate progress and progress_indicator_text to hold a configurable label. They refer to an update() function that will be called every time that the value of the property is changed. The update() function just tags any area the is an INFO editor (theoretically there could be more than one) for redraw which will cause the draw() method to be called for any of its regions, including the header region.

Line 30 stores a reference to the original draw() method of the the Info header. Next we define a new method newdraw() that will call the original draw() method (line 36) and then add the new scene property progress_indicator but only if it has a value between zero and 100.

The new function is then used to replace the existing draw function.

How to use the progress indicator

Long running operations are probably best implemented as modal operators and using the progress indicator from a modal operator is very simple. An example of such an operator is shown below (which also starts a timer that will send timer events to the modal operator. The operator will stop after 9 timer ticks and update the progress indicator on each tick. After the final tick it will set the value to 101 which will stop the progress indicator from being displayed:

class TestProgressModal(bpy.types.Operator):
    bl_idname = 'scene.testprogressmodal'
    bl_label = 'Test Progress Modal'
    bl_options = {'REGISTER'}

    def modal(self, context, event):
        if event.type == 'TIMER':
            self.ticks += 1
        if self.ticks > 9:
            context.scene.progress_indicator = 101 # done
            context.window_manager.event_timer_remove(self.timer)
            return {'CANCELLED'}

        context.scene.progress_indicator = self.ticks*10

        return {'RUNNING_MODAL'}

    def invoke(self, context, event):
        self.ticks = 0
        context.scene.progress_indicator_text = "Heavy modal job"
        context.scene.progress_indicator = 0
        wm = context.window_manager
        self.timer = wm.event_timer_add(1.0, context.window)
        wm.modal_handler_add(self)
        return {'RUNNING_MODAL'}

It is possible to update the progress indicator from a long running non-modal's execute() method as well but although the update functions associated with the scene properties will be called and hence the area tagged for redraw, an actual redraw is only initiated after the operator finishes. There is a way around with a documented but unsupported hack as shown in the code below (line 13):

class TestProgress(bpy.types.Operator):
    bl_idname = 'scene.testprogress'
    bl_label = 'Test Progress'
    bl_options = {'REGISTER'}

    def execute(self, context):
        context.scene.progress_indicator_text = "Heavy job"
        context.scene.progress_indicator = 0
        for tick in range(10):
            sleep(1) # placeholder for heavy work
            context.scene.progress_indicator = tick*10
            # see https://docs.blender.org/api/current/info_gotcha.html
            bpy.ops.wm.redraw_timer(type='DRAW_WIN_SWAP', iterations=1)

        context.scene.progress_indicator = 101 # done
        return {"FINISHED"}

Code availability

The full code which includes the two sample operators that illustrate how to use the progress indicator is available on GitHub.

How to remove user installed add-ons in bulk

I admit that this is probably not a problem many people have but as an add-on developer I find myself every now an then in the situation that I want remove a whole bunch of user installed add-ons in one go.

What I often do when I develop a collection of add-ons is define a common category for all of them that is not one of the predefined categories. That way I can at least easily find them and see them grouped together in the user preferences.

Removing a single add-on is simple but to remove a bunch of user installed add-ons is less so because you have to locate the Blender user config directory (which is different on various operating systems) and you'll have to open each add-on file (or __init__.py file in a subdirectory if it's a multi-file add-on) to see if it defines the relevant category.

Tedious, but fortunately Blender can help. The code below shows you how. It is not an add-on itself, it is meant to be run from the command line inside Blender or from Blender's text editor (clicking Run Script). Removing stuff always carries the risk of accidental deletion so be careful (and use this snippet at your own risk. And keep back-ups, but careful people always do that, right? ). And yes, this code removes add-ons, not just disables them!


import bpy
from bpy.utils import script_path_user
from addon_utils import modules, module_bl_info

import os.path

userdir = script_path_user()

def remove_user_installed_addons(cat='Experimental development', dry_run=True):
    for mod in modules():
        if module_bl_info(mod)['category'] == cat:
            if os.path.dirname(mod.__file__).startswith(userdir):
                print("removing " + mod.__name__)
                if not dry_run:
                    bpy.ops.wm.addon_remove(module=mod.__name__)

remove_user_installed_addons(cat='Experimental development', dry_run=False)

As you can see, Blender provides us with an addon_utils module that has both a function modules() to produce a list of all add-ons (both enabled and not-enabled)  and a function module_bl_info() that returns the bl_info block of an add-on as a dictionary.
So all we have to do is loop over all installed modules, check if the module is part of the specified category and if so, use the script_path_user() function to determine if the directory that the add-on sits in, is in the user path (so we don't accidentally remove bundled Blender add-ons).
If it checks out, we user the addon_remove() operator to do the actual removal.

Blender Add-on Cookbook

I am pleased to announce that my new book Blender Add-on Cookbook is now available on Smashwords and Blender Market
A sample (PDF) is available to give you a small taste of what this book offers.

A Cookbook?

It is a cookbook for Blender add-on developers who want to go one step further and want to add a professional touch to their creations or want to add functionality that isn't so straight forward to implement.

This book offers more than 30 examples of practical issues you may encounter when developing Blender add-ons. It gives you practical solutions with fully documented code samples, offers insight and advice based on years of developing add-ons and is fully illustrated.

Each recipe also comes with links to relevant reference sites and Blender API sections, and each code snippet comes with a small example add-on that can be downloaded from GitHub so you can simply test the given examples.

The book contains a proper index and is available in ePub format. (The Blender Market edition will be available in PDF and Mobi formats as well).

E-book promotion

Promotion!

From one minute past midnight on March 5 Pacific time, till 11:59pm on March 11, Smashwords will host its ninth annual read an e-book week promotion. Many e-books will be heavily discounted or even free.

I participate as well, with 50% off my e-books on Creating add-ons for Blender and Open Shading Language for Blender. They weren't expensive to begin with but still, every saving counts :-)

If you want to get in on this deal, just click on one of the book links above and follow the instruction. During the sale a discount Coupon will be listed next to the book entry. This coupon can then be entered on check-out.

Enjoy!

Nodeset: more flexibility

Prompted by a question from Packsod 百草头 I've added the option to disable filtering the list of files. It's still enabled by default and in fact you can now specify a fragment to be used in the filter pattern.

This means that if all your texture sets normally contain an albedo map with _alb in its name, that you not only can configure which files to load but also you can restrict the list of visible files to pick from, to anything you like. This greatly reduces the clutter when selecting a texture collection from a folder that contains many texture sets. (remember that even though you see a limited list from which you only pick one file, other textures with the same name and matching configured suffixes will still be loaded).

This means you can configure any set of suffixes that your favorite texture editing program uses in these settings and save it along with your user preferences, an example is shown below.


I also added the option to make suffix filtering case sensitive or insensitive. This is set to insensitive by default.

Code availability

The latest version of the code (201702051650) is available on GitHub (right click and select save as ... , then in Blender File -> user preferences ... -> Add-ons -> Install from file .... Don't forget to remove the previously installed version first)

Previous articles

Previous articles about the Nodeset add-on:
NODESET: IMPORT SUBSTANCE PAINTER TEXTURES INTO BLENDER
NODESET: TINY UPDATE MIGHT SAVE EVEN SOME MORE TIME
NODESET: SUPPORT FOR AMBIENT OCCLUSION MAPS

Add-on: Creating a chain of objects, nearest neighbor approximation

In a previous article I started with a very naive solution to create a chain of objects that have a parent-child relation along the shortest path.

This naive solution works but is so slow that even for 10 objects it starts getting unworkable. So the improved version uses a simplistic nearest neighbor approximation that works well with even thousands of objects. It has one drawback, you have to make sure that the active object is at one of the ends of the collection of selected objects because that is where our algorithm starts. This works quite well for artistic use, but in the future I might still try to add the Chistofides algorithm to make it more general.

Anyway, the code is simple enough and the relevant function is shown below:

def object_list2(objects, active=0):
 """
 Return an approximate shortest path through objects starting at the
 active index using the nearest neighbor heuristic.
 """

 s = time()

 # calculate a kd tree to quickly answer nearest neighbor queries
 kd = kdtree.KDTree(len(objects))
 for i, ob in enumerate(objects):
  kd.insert(ob.location, i)
 kd.balance()

 current = objects[active]
 chain = [current]  # we start at the chosen object
 added = {active}
 for i in range(1,len(objects)):  # we know how many objects to add
  # when looking for the nearest neighbor we start with two neigbors
  # (because we include the object itself in the search) and if
  # the other neigbors is not yet in the chain we add it, otherwise
  # we expand our search to a maximum of the total number of objects
  for n in range(2,len(objects)):
   neighbors = { index for _,index,_ in kd.find_n(current.location, n) }
   neighbors -= added
   if neighbors:  # strictly speaking we shoudl assert that len(neighbors) == 1
    chain.extend(objects[i] for i in neighbors)
    added |= neighbors
    break
  current = chain[-1]

 print("{n:d} objects {t:.1f}s".format(t=time()-s, n=len(objects)))

 return chain

Code availability

The full improved version is available on the same GitHub location. (click 'Raw' to download the Python file)

Add-on: Creating a chain of objects

While working on a project I came across a problem that is surprisingly hard to tackle: chaining a collection of objects along the shortest path.

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__)