mesh_looptools.py

        y = math.sin(t) * r
        locs_2d[i] = [x, y, locs_2d[i][2]]

    return(locs_2d)


# shift loop, so the first vertex is closest to the center
def circle_shift_loop(bm_mod, loop, com):
    verts, circular = loop
    distances = [[(bm_mod.verts[vert].co - com).length, i] \
        for i, vert in enumerate(verts)]
    distances.sort()
    shift = distances[0][1]
    loop = [verts[shift:] + verts[:shift], circular]

    return(loop)


##########################################
####### Curve functions ##################
##########################################

# create lists with knots and points, all correctly sorted
def curve_calculate_knots(loop, verts_selected):
    knots = [v for v in loop[0] if v in verts_selected]
    points = loop[0][:]
    # circular loop, potential for weird splines
    if loop[1]:
        offset = int(len(loop[0]) / 4)
        kpos = []
        for k in knots:
            kpos.append(loop[0].index(k))
        kdif = []
        for i in range(len(kpos) - 1):
            kdif.append(kpos[i+1] - kpos[i])
        kdif.append(len(loop[0]) - kpos[-1] + kpos[0])
        kadd = []
        for k in kdif:
            if k > 2 * offset:
                kadd.append([kdif.index(k), True])
            # next 2 lines are optional, they insert
            # an extra control point in small gaps
            #elif k > offset:
            #   kadd.append([kdif.index(k), False])
        kins = []
        krot = False
        for k in kadd: # extra knots to be added
            if k[1]: # big gap (break circular spline)
                kpos = loop[0].index(knots[k[0]]) + offset
                if kpos > len(loop[0]) - 1:
                    kpos -= len(loop[0])
                kins.append([knots[k[0]], loop[0][kpos]])
                kpos2 = k[0] + 1
                if kpos2 > len(knots)-1:
                    kpos2 -= len(knots)
                kpos2 = loop[0].index(knots[kpos2]) - offset
                if kpos2 < 0:
                    kpos2 += len(loop[0])
                kins.append([loop[0][kpos], loop[0][kpos2]])
                krot = loop[0][kpos2]
            else: # small gap (keep circular spline)
                k1 = loop[0].index(knots[k[0]])
                k2 = k[0] + 1
                if k2 > len(knots)-1:
                    k2 -= len(knots)
                k2 = loop[0].index(knots[k2])
                if k2 < k1:
                    dif = len(loop[0]) - 1 - k1 + k2
                else:
                    dif = k2 - k1
                kn = k1 + int(dif/2)
                if kn > len(loop[0]) - 1:
                    kn -= len(loop[0])
                kins.append([loop[0][k1], loop[0][kn]])
        for j in kins: # insert new knots
            knots.insert(knots.index(j[0]) + 1, j[1])
        if not krot: # circular loop
            knots.append(knots[0])
            points = loop[0][loop[0].index(knots[0]):]
            points += loop[0][0:loop[0].index(knots[0]) + 1]
        else: # non-circular loop (broken by script)
            krot = knots.index(krot)
            knots = knots[krot:] + knots[0:krot]
            if loop[0].index(knots[0]) > loop[0].index(knots[-1]):
                points = loop[0][loop[0].index(knots[0]):]
                points += loop[0][0:loop[0].index(knots[-1])+1]
            else:
                points = loop[0][loop[0].index(knots[0]):\
                    loop[0].index(knots[-1]) + 1]
    # non-circular loop, add first and last point as knots
    else:
        if loop[0][0] not in knots:
            knots.insert(0, loop[0][0])
        if loop[0][-1] not in knots:
            knots.append(loop[0][-1])

    return(knots, points)


# calculate relative positions compared to first knot
def curve_calculate_t(bm_mod, knots, points, pknots, regular, circular):
    tpoints = []
    loc_prev = False
    len_total = 0

    for p in points:
        if p in knots:
            loc = pknots[knots.index(p)] # use projected knot location
        else:
            loc = mathutils.Vector(bm_mod.verts[p].co[:])
        if not loc_prev:
            loc_prev = loc
        len_total += (loc-loc_prev).length
        tpoints.append(len_total)
        loc_prev = loc
    tknots = []
    for p in points:
        if p in knots:
            tknots.append(tpoints[points.index(p)])
    if circular:
        tknots[-1] = tpoints[-1]

    # regular option
    if regular:
        tpoints_average = tpoints[-1] / (len(tpoints) - 1)
        for i in range(1, len(tpoints) - 1):
            tpoints[i] = i * tpoints_average
        for i in range(len(knots)):
            tknots[i] = tpoints[points.index(knots[i])]
        if circular:
            tknots[-1] = tpoints[-1]


    return(tknots, tpoints)


# change the location of non-selected points to their place on the spline
def curve_calculate_vertices(bm_mod, knots, tknots, points, tpoints, splines,
interpolation, restriction):
    newlocs = {}
    move = []

    for p in points:
        if p in knots:
            continue
        m = tpoints[points.index(p)]
        if m in tknots:
            n = tknots.index(m)
        else:
            t = tknots[:]
            t.append(m)
            t.sort()
            n = t.index(m) - 1
        if n > len(splines) - 1:
            n = len(splines) - 1
        elif n < 0:
            n = 0

        if interpolation == 'cubic':
            ax, bx, cx, dx, tx = splines[n][0]
            x = ax + bx*(m-tx) + cx*(m-tx)**2 + dx*(m-tx)**3
            ay, by, cy, dy, ty = splines[n][1]
            y = ay + by*(m-ty) + cy*(m-ty)**2 + dy*(m-ty)**3
            az, bz, cz, dz, tz = splines[n][2]
            z = az + bz*(m-tz) + cz*(m-tz)**2 + dz*(m-tz)**3
            newloc = mathutils.Vector([x,y,z])
        else: # interpolation == 'linear'
            a, d, t, u = splines[n]
            newloc = ((m-t)/u)*d + a

        if restriction != 'none': # vertex movement is restricted
            newlocs[p] = newloc
        else: # set the vertex to its new location
            move.append([p, newloc])

    if restriction != 'none': # vertex movement is restricted
        for p in points:
            if p in newlocs:
                newloc = newlocs[p]
            else:
                move.append([p, bm_mod.verts[p].co])
                continue
            oldloc = bm_mod.verts[p].co
            normal = bm_mod.verts[p].normal
            dloc = newloc - oldloc
            if dloc.length < 1e-6:
                move.append([p, newloc])
            elif restriction == 'extrude': # only extrusions
                if dloc.angle(normal, 0) < 0.5 * math.pi + 1e-6:
                    move.append([p, newloc])
            else: # restriction == 'indent' only indentations
                if dloc.angle(normal) > 0.5 * math.pi - 1e-6:
                    move.append([p, newloc])

    return(move)


# trim loops to part between first and last selected vertices (including)
def curve_cut_boundaries(bm_mod, loops):
    cut_loops = []
    for loop, circular in loops:
        if circular:
            # don't cut
            cut_loops.append([loop, circular])
            continue
        selected = [bm_mod.verts[v].select for v in loop]
        first = selected.index(True)
        selected.reverse()
        last = -selected.index(True)
        if last == 0:
            cut_loops.append([loop[first:], circular])
        else:
            cut_loops.append([loop[first:last], circular])

    return(cut_loops)


# calculate input loops
def curve_get_input(object, bm, boundaries, scene):
    # get mesh with modifiers applied
    derived, bm_mod = get_derived_bmesh(object, bm, scene)

    # vertices that still need a loop to run through it
    verts_unsorted = [v.index for v in bm_mod.verts if \
        v.select and not v.hide]
    # necessary dictionaries
    vert_edges = dict_vert_edges(bm_mod)
    edge_faces = dict_edge_faces(bm_mod)
    correct_loops = []

    # find loops through each selected vertex
    while len(verts_unsorted) > 0:
        loops = curve_vertex_loops(bm_mod, verts_unsorted[0], vert_edges,
            edge_faces)
        verts_unsorted.pop(0)

        # check if loop is fully selected
        search_perpendicular = False
        i = -1
        for loop, circular in loops:
            i += 1
            selected = [v for v in loop if bm_mod.verts[v].select]
            if len(selected) < 2:
                # only one selected vertex on loop, don't use
                loops.pop(i)
                continue
            elif len(selected) == len(loop):
                search_perpendicular = loop
                break
        # entire loop is selected, find perpendicular loops
        if search_perpendicular:
            for vert in loop:
                if vert in verts_unsorted:
                    verts_unsorted.remove(vert)
            perp_loops = curve_perpendicular_loops(bm_mod, loop,
                vert_edges, edge_faces)
            for perp_loop in perp_loops:
                correct_loops.append(perp_loop)
        # normal input
        else:
            for loop, circular in loops:
                correct_loops.append([loop, circular])

    # boundaries option
    if boundaries:
        correct_loops = curve_cut_boundaries(bm_mod, correct_loops)

    return(derived, bm_mod, correct_loops)


# return all loops that are perpendicular to the given one
def curve_perpendicular_loops(bm_mod, start_loop, vert_edges, edge_faces):
    # find perpendicular loops
    perp_loops = []
    for start_vert in start_loop:
        loops = curve_vertex_loops(bm_mod, start_vert, vert_edges,
            edge_faces)
        for loop, circular in loops:
            selected = [v for v in loop if bm_mod.verts[v].select]
            if len(selected) == len(loop):
                continue
            else:
                perp_loops.append([loop, circular, loop.index(start_vert)])

    # trim loops to same lengths
    shortest = [[len(loop[0]), i] for i, loop in enumerate(perp_loops)\
        if not loop[1]]
    if not shortest:
        # all loops are circular, not trimming
        return([[loop[0], loop[1]] for loop in perp_loops])
    else:
        shortest = min(shortest)
    shortest_start = perp_loops[shortest[1]][2]
    before_start = shortest_start
    after_start = shortest[0] - shortest_start - 1
    bigger_before = before_start > after_start
    trimmed_loops = []
    for loop in perp_loops:
        # have the loop face the same direction as the shortest one
        if bigger_before:
            if loop[2] < len(loop[0]) / 2:
                loop[0].reverse()
                loop[2] = len(loop[0]) - loop[2] - 1
        else:
            if loop[2] > len(loop[0]) / 2:
                loop[0].reverse()
                loop[2] = len(loop[0]) - loop[2] - 1
        # circular loops can shift, to prevent wrong trimming
        if loop[1]:
            shift = shortest_start - loop[2]
            if loop[2] + shift > 0 and loop[2] + shift < len(loop[0]):
                loop[0] = loop[0][-shift:] + loop[0][:-shift]
            loop[2] += shift
            if loop[2] < 0:
                loop[2] += len(loop[0])
            elif loop[2] > len(loop[0]) -1:
                loop[2] -= len(loop[0])
        # trim
        start = max(0, loop[2] - before_start)
        end = min(len(loop[0]), loop[2] + after_start + 1)
        trimmed_loops.append([loop[0][start:end], False])

    return(trimmed_loops)


# project knots on non-selected geometry
def curve_project_knots(bm_mod, verts_selected, knots, points, circular):
    # function to project vertex on edge
    def project(v1, v2, v3):
        # v1 and v2 are part of a line
        # v3 is projected onto it
        v2 -= v1
        v3 -= v1
        p = v3.project(v2)
        return(p + v1)

    if circular: # project all knots
        start = 0
        end = len(knots)
        pknots = []
    else: # first and last knot shouldn't be projected
        start = 1
        end = -1
        pknots = [mathutils.Vector(bm_mod.verts[knots[0]].co[:])]
    for knot in knots[start:end]:
        if knot in verts_selected:
            knot_left = knot_right = False
            for i in range(points.index(knot)-1, -1*len(points), -1):
                if points[i] not in knots:
                    knot_left = points[i]
                    break
            for i in range(points.index(knot)+1, 2*len(points)):
                if i > len(points) - 1:
                    i -= len(points)
                if points[i] not in knots:
                    knot_right = points[i]
                    break
            if knot_left and knot_right and knot_left != knot_right:
                knot_left = mathutils.Vector(\
                    bm_mod.verts[knot_left].co[:])
                knot_right = mathutils.Vector(\
                    bm_mod.verts[knot_right].co[:])
                knot = mathutils.Vector(bm_mod.verts[knot].co[:])
                pknots.append(project(knot_left, knot_right, knot))
            else:
                pknots.append(mathutils.Vector(bm_mod.verts[knot].co[:]))
        else: # knot isn't selected, so shouldn't be changed
            pknots.append(mathutils.Vector(bm_mod.verts[knot].co[:]))
    if not circular:
        pknots.append(mathutils.Vector(bm_mod.verts[knots[-1]].co[:]))

    return(pknots)


# find all loops through a given vertex
def curve_vertex_loops(bm_mod, start_vert, vert_edges, edge_faces):
    edges_used = []
    loops = []

    for edge in vert_edges[start_vert]:
        if edge in edges_used:
            continue
        loop = []
        circular = False
        for vert in edge:
            active_faces = edge_faces[edge]
            new_vert = vert
            growing = True
            while growing:
                growing = False
                new_edges = vert_edges[new_vert]
                loop.append(new_vert)
                if len(loop) > 1:
                    edges_used.append(tuple(sorted([loop[-1], loop[-2]])))
                if len(new_edges) < 3 or len(new_edges) > 4:
                    # pole
                    break
                else:
                    # find next edge
                    for new_edge in new_edges:
                        if new_edge in edges_used:
                            continue
                        eliminate = False
                        for new_face in edge_faces[new_edge]:
                            if new_face in active_faces:
                                eliminate = True
                                break
                        if eliminate:
                            continue
                        # found correct new edge
                        active_faces = edge_faces[new_edge]
                        v1, v2 = new_edge
                        if v1 != new_vert:
                            new_vert = v1
                        else:
                            new_vert = v2
                        if new_vert == loop[0]:
                            circular = True
                        else:
                            growing = True
                        break
            if circular:
                break
            loop.reverse()
        loops.append([loop, circular])

    return(loops)


##########################################
####### Flatten functions ################
##########################################

# sort input into loops
def flatten_get_input(bm):
    vert_verts = dict_vert_verts([edgekey(edge) for edge in bm.edges \
        if edge.select and not edge.hide])
    verts = [v.index for v in bm.verts if v.select and not v.hide]

    # no connected verts, consider all selected verts as a single input
    if not vert_verts:
        return([[verts, False]])

    loops = []
    while len(verts) > 0:
        # start of loop
        loop = [verts[0]]
        verts.pop(0)
        if loop[-1] in vert_verts:
            to_grow = vert_verts[loop[-1]]
        else:
            to_grow = []
        # grow loop
        while len(to_grow) > 0:
            new_vert = to_grow[0]
            to_grow.pop(0)
            if new_vert in loop:
                continue
            loop.append(new_vert)
            verts.remove(new_vert)
            to_grow += vert_verts[new_vert]
        # add loop to loops
        loops.append([loop, False])

    return(loops)


# calculate position of vertex projections on plane
def flatten_project(bm, loop, com, normal):
    verts = [bm.verts[v] for v in loop[0]]
    verts_projected = [[v.index, mathutils.Vector(v.co[:]) - \
        (mathutils.Vector(v.co[:])-com).dot(normal)*normal] for v in verts]

    return(verts_projected)


##########################################
####### Gstretch functions ###############
##########################################

# fake stroke class, used to create custom strokes if no GP data is found
class gstretch_fake_stroke():
    def __init__(self, points):
        self.points = [gstretch_fake_stroke_point(p) for p in points]


# fake stroke point class, used in fake strokes
class gstretch_fake_stroke_point():
    def __init__(self, loc):
        self.co = loc


# flips loops, if necessary, to obtain maximum alignment to stroke
def gstretch_align_pairs(ls_pairs, object, bm_mod, method):
    # returns total distance between all verts in loop and corresponding stroke
    def distance_loop_stroke(loop, stroke, object, bm_mod, method):
        stroke_lengths_cache = False
        loop_length = len(loop[0])
        total_distance = 0

        if method != 'regular':
            relative_lengths = gstretch_relative_lengths(loop, bm_mod)

        for i, v_index in enumerate(loop[0]):
            if method == 'regular':
                relative_distance = i / (loop_length - 1)
            else:
                relative_distance = relative_lengths[i]

            loc1 = object.matrix_world * bm_mod.verts[v_index].co
            loc2, stroke_lengths_cache = gstretch_eval_stroke(stroke,
                relative_distance, stroke_lengths_cache)
            total_distance += (loc2 - loc1).length

        return(total_distance)

    if ls_pairs:
        for (loop, stroke) in ls_pairs:
            distance_loop_stroke
            total_dist = distance_loop_stroke(loop, stroke, object, bm_mod,
                method)
            loop[0].reverse()
            total_dist_rev = distance_loop_stroke(loop, stroke, object, bm_mod,
                method)
            if total_dist_rev > total_dist:
                loop[0].reverse()

    return(ls_pairs)


# calculate vertex positions on stroke
def gstretch_calculate_verts(loop, stroke, object, bm_mod, method):
    move = []
    stroke_lengths_cache = False
    loop_length = len(loop[0])
    matrix_inverse = object.matrix_world.inverted()

    # return intersection of line with stroke, or None
    def intersect_line_stroke(vec1, vec2, stroke):
        for i, p in enumerate(stroke.points[1:]):
            intersections = mathutils.geometry.intersect_line_line(vec1, vec2,
                p.co, stroke.points[i].co)
            if intersections and \
            (intersections[0] - intersections[1]).length < 1e-2:
                x, dist = mathutils.geometry.intersect_point_line(
                    intersections[0], p.co, stroke.points[i].co)
                if -1 < dist < 1:
                    return(intersections[0])
        return(None)

    if method == 'project':
        projection_vectors = []
        vert_edges = dict_vert_edges(bm_mod)

        for v_index in loop[0]:
            for ek in vert_edges[v_index]:
                v1, v2 = ek
                v1 = bm_mod.verts[v1]
                v2 = bm_mod.verts[v2]
                if v1.select + v2.select == 1 and not v1.hide and not v2.hide:
                    vec1 = object.matrix_world * v1.co
                    vec2 = object.matrix_world * v2.co
                    intersection = intersect_line_stroke(vec1, vec2, stroke)
                    if intersection:
                        break
            if not intersection:
                v = bm_mod.verts[v_index]
                intersection = intersect_line_stroke(v.co, v.co + v.normal,
                    stroke)
            if intersection:
                move.append([v_index, matrix_inverse * intersection])

    else:
        if method == 'irregular':
            relative_lengths = gstretch_relative_lengths(loop, bm_mod)

        for i, v_index in enumerate(loop[0]):
            if method == 'regular':
                relative_distance = i / (loop_length - 1)
            else: # method == 'irregular'
                relative_distance = relative_lengths[i]
            loc, stroke_lengths_cache = gstretch_eval_stroke(stroke,
                relative_distance, stroke_lengths_cache)
            loc = matrix_inverse * loc
            move.append([v_index, loc])

    return(move)


# create new vertices, based on GP strokes
def gstretch_create_verts(object, bm_mod, strokes, method, conversion,
conversion_distance, conversion_max, conversion_min, conversion_vertices):
    move = []
    stroke_verts = []
    mat_world = object.matrix_world.inverted()
    singles = gstretch_match_single_verts(bm_mod, strokes, mat_world)

    for stroke in strokes:
        stroke_verts.append([stroke, []])
        min_end_point = 0
        if conversion == 'vertices':
            min_end_point = conversion_vertices
            end_point = conversion_vertices
        elif conversion == 'limit_vertices':
            min_end_point = conversion_min
            end_point = conversion_max
        else:
            end_point = len(stroke.points)
        # creation of new vertices at fixed user-defined distances
        if conversion == 'distance':
            method = 'project'
            prev_point = stroke.points[0]
            stroke_verts[-1][1].append(bm_mod.verts.new(mat_world * \
                prev_point.co))
            distance = 0
            limit = conversion_distance
            for point in stroke.points:
                new_distance = distance + (point.co - prev_point.co).length
                iteration = 0
                while new_distance > limit:
                    to_cover = limit - distance + (limit * iteration)
                    new_loc = prev_point.co + to_cover * \
                        (point.co - prev_point.co).normalized()
                    stroke_verts[-1][1].append(bm_mod.verts.new(mat_world * \
                        new_loc))
                    new_distance -= limit
                    iteration += 1
                distance = new_distance
                prev_point = point
        # creation of new vertices for other methods
        else:
            # add vertices at stroke points
            for point in stroke.points[:end_point]:
                stroke_verts[-1][1].append(bm_mod.verts.new(\
                    mat_world * point.co))
            # add more vertices, beyond the points that are available
            if min_end_point > min(len(stroke.points), end_point):
                for i in range(min_end_point -
                (min(len(stroke.points), end_point))):
                    stroke_verts[-1][1].append(bm_mod.verts.new(\
                        mat_world * point.co))
                # force even spreading of points, so they are placed on stroke
                method = 'regular'
    bm_mod.verts.index_update()
    for stroke, verts_seq in stroke_verts:
        if len(verts_seq) < 2:
            continue
        # spread vertices evenly over the stroke
        if method == 'regular':
            loop = [[vert.index for vert in verts_seq], False]
            move += gstretch_calculate_verts(loop, stroke, object, bm_mod,
                method)
        # create edges
        for i, vert in enumerate(verts_seq):
            if i > 0:
                bm_mod.edges.new((verts_seq[i-1], verts_seq[i]))
            vert.select = True
        # connect single vertices to the closest stroke
        if singles:
            for vert, m_stroke, point in singles:
                if m_stroke != stroke:
                    continue
                bm_mod.edges.new((vert, verts_seq[point]))

    bmesh.update_edit_mesh(object.data)

    return(move)


# erases the grease pencil stroke
def gstretch_erase_stroke(stroke, context):
    # change 3d coordinate into a stroke-point
    def sp(loc, context):
        lib = {'name': "",
            'pen_flip': False,
            'is_start': False,
            'location': (0, 0, 0),
            'mouse': (view3d_utils.location_3d_to_region_2d(\
                context.region, context.space_data.region_3d, loc)),
            'pressure': 1,
            'time': 0}
        return(lib)

    if type(stroke) != bpy.types.GPencilStroke:
        # fake stroke, there is nothing to delete
        return

    erase_stroke = [sp(p.co, context) for p in stroke.points]
    if erase_stroke:
        erase_stroke[0]['is_start'] = True
    bpy.ops.gpencil.draw(mode='ERASER', stroke=erase_stroke)


# get point on stroke, given by relative distance (0.0 - 1.0)
def gstretch_eval_stroke(stroke, distance, stroke_lengths_cache=False):
    # use cache if available
    if not stroke_lengths_cache:
        lengths = [0]
        for i, p in enumerate(stroke.points[1:]):
            lengths.append((p.co - stroke.points[i].co).length + \
                lengths[-1])
        total_length = max(lengths[-1], 1e-7)
        stroke_lengths_cache = [length / total_length for length in
            lengths]
    stroke_lengths = stroke_lengths_cache[:]

    if distance in stroke_lengths:
        loc = stroke.points[stroke_lengths.index(distance)].co
    elif distance > stroke_lengths[-1]:
        # should be impossible, but better safe than sorry
        loc = stroke.points[-1].co
    else:
        stroke_lengths.append(distance)
        stroke_lengths.sort()
        stroke_index = stroke_lengths.index(distance)
        interval_length = stroke_lengths[stroke_index+1] - \
            stroke_lengths[stroke_index-1]
        distance_relative = (distance - stroke_lengths[stroke_index-1]) / \
            interval_length
        interval_vector = stroke.points[stroke_index].co - \
            stroke.points[stroke_index-1].co
        loc = stroke.points[stroke_index-1].co + \
            distance_relative * interval_vector

    return(loc, stroke_lengths_cache)


# create fake grease pencil strokes for the active object
def gstretch_get_fake_strokes(object, bm_mod, loops):
    strokes = []
    for loop in loops:
        p1 = object.matrix_world * bm_mod.verts[loop[0][0]].co
        p2 = object.matrix_world * bm_mod.verts[loop[0][-1]].co
        strokes.append(gstretch_fake_stroke([p1, p2]))

    return(strokes)


# get grease pencil strokes for the active object
def gstretch_get_strokes(object):
    gp = object.grease_pencil
    if not gp:
        return(None)
    layer = gp.layers.active
    if not layer:
        return(None)
    frame = layer.active_frame
    if not frame:
        return(None)
    strokes = frame.strokes
    if len(strokes) < 1:
        return(None)

    return(strokes)


# returns a list with loop-stroke pairs
def gstretch_match_loops_strokes(loops, strokes, object, bm_mod):
    if not loops or not strokes:
        return(None)

    # calculate loop centers
    loop_centers = []
    for loop in loops:
        center = mathutils.Vector()
        for v_index in loop[0]:
            center += bm_mod.verts[v_index].co
        center /= len(loop[0])
        center = object.matrix_world * center
        loop_centers.append([center, loop])

    # calculate stroke centers
    stroke_centers = []
    for stroke in strokes:
        center = mathutils.Vector()
        for p in stroke.points:
            center += p.co
        center /= len(stroke.points)
        stroke_centers.append([center, stroke, 0])

    # match, first by stroke use count, then by distance
    ls_pairs = []
    for lc in loop_centers:
        distances = []
        for i, sc in enumerate(stroke_centers):
            distances.append([sc[2], (lc[0] - sc[0]).length, i])
        distances.sort()
        best_stroke = distances[0][2]
        ls_pairs.append([lc[1], stroke_centers[best_stroke][1]])
        stroke_centers[best_stroke][2] += 1 # increase stroke use count

    return(ls_pairs)


# match single selected vertices to the closest stroke endpoint
# returns a list of tuples, constructed as: (vertex, stroke, stroke point index)
def gstretch_match_single_verts(bm_mod, strokes, mat_world):
    # calculate stroke endpoints in object space
    endpoints = []
    for stroke in strokes:
        endpoints.append((mat_world * stroke.points[0].co, stroke, 0))
        endpoints.append((mat_world * stroke.points[-1].co, stroke, -1))

    distances = []
    # find single vertices (not connected to other selected verts)
    for vert in bm_mod.verts:
        if not vert.select:
            continue
        single = True
        for edge in vert.link_edges:
            if edge.other_vert(vert).select:
                single = False
                break
        if not single:
            continue
        # calculate distances from vertex to endpoints
        distance = [((vert.co - loc).length, vert, stroke, stroke_point,
            endpoint_index) for endpoint_index, (loc, stroke, stroke_point) in
            enumerate(endpoints)]
        distance.sort()
        distances.append(distance[0])

    # create matches, based on shortest distance first
    singles = []
    while distances:
        distances.sort()
        singles.append((distances[0][1], distances[0][2], distances[0][3]))
        endpoints.pop(distances[0][4])
        distances.pop(0)
        distances_new = []
        for (i, vert, j, k, l) in distances:
            distance_new = [((vert.co - loc).length, vert, stroke, stroke_point,
                endpoint_index) for endpoint_index, (loc, stroke,
                stroke_point) in enumerate(endpoints)]
            distance_new.sort()
            distances_new.append(distance_new[0])
        distances = distances_new

    return(singles)


# returns list with a relative distance (0.0 - 1.0) of each vertex on the loop
def gstretch_relative_lengths(loop, bm_mod):
    lengths = [0]
    for i, v_index in enumerate(loop[0][1:]):
        lengths.append((bm_mod.verts[v_index].co - \
            bm_mod.verts[loop[0][i]].co).length + lengths[-1])
        total_length = max(lengths[-1], 1e-7)
        relative_lengths = [length / total_length for length in
            lengths]

    return(relative_lengths)


# convert cache-stored strokes into usable (fake) GP strokes
def gstretch_safe_to_true_strokes(safe_strokes):
    strokes = []
    for safe_stroke in safe_strokes:
        strokes.append(gstretch_fake_stroke(safe_stroke))

    return(strokes)


# convert a GP stroke into a list of points which can be stored in cache
def gstretch_true_to_safe_strokes(strokes):
    safe_strokes = []
    for stroke in strokes:
        safe_strokes.append([p.co.copy() for p in stroke.points])

    return(safe_strokes)


# force consistency in GUI, max value can never be lower than min value
def gstretch_update_max(self, context):
    # called from operator settings (after execution)
    if 'conversion_min' in self.keys():
        if self.conversion_min > self.conversion_max:
            self.conversion_max = self.conversion_min
    # called from toolbar
    else:
        lt = context.window_manager.looptools
        if lt.gstretch_conversion_min > lt.gstretch_conversion_max:
            lt.gstretch_conversion_max = lt.gstretch_conversion_min


# force consistency in GUI, min value can never be higher than max value
def gstretch_update_min(self, context):
    # called from operator settings (after execution)
    if 'conversion_max' in self.keys():
        if self.conversion_max < self.conversion_min:
            self.conversion_min = self.conversion_max
    # called from toolbar
    else:
        lt = context.window_manager.looptools
        if lt.gstretch_conversion_max < lt.gstretch_conversion_min:
            lt.gstretch_conversion_min = lt.gstretch_conversion_max


##########################################
####### Relax functions ##################
##########################################

# create lists with knots and points, all correctly sorted
def relax_calculate_knots(loops):
    all_knots = []
    all_points = []
    for loop, circular in loops:
        knots = [[], []]
        points = [[], []]
        if circular:
            if len(loop)%2 == 1: # odd
                extend = [False, True, 0, 1, 0, 1]
            else: # even
                extend = [True, False, 0, 1, 1, 2]
        else:
            if len(loop)%2 == 1: # odd
                extend = [False, False, 0, 1, 1, 2]
            else: # even
                extend = [False, False, 0, 1, 1, 2]
        for j in range(2):
            if extend[j]:
                loop = [loop[-1]] + loop + [loop[0]]
            for i in range(extend[2+2*j], len(loop), 2):
                knots[j].append(loop[i])
            for i in range(extend[3+2*j], len(loop), 2):
                if loop[i] == loop[-1] and not circular:
                    continue
                if len(points[j]) == 0:
                    points[j].append(loop[i])
                elif loop[i] != points[j][0]:
                    points[j].append(loop[i])
            if circular:
                if knots[j][0] != knots[j][-1]:
                    knots[j].append(knots[j][0])
        if len(points[1]) == 0:
            knots.pop(1)
            points.pop(1)
        for k in knots:
            all_knots.append(k)
        for p in points:
            all_points.append(p)

    return(all_knots, all_points)


# calculate relative positions compared to first knot
def relax_calculate_t(bm_mod, knots, points, regular):
    all_tknots = []
    all_tpoints = []
    for i in range(len(knots)):
        amount = len(knots[i]) + len(points[i])
        mix  = []
        for j in range(amount):
            if j%2 == 0:
                mix.append([True, knots[i][round(j/2)]])
            elif j == amount-1:
                mix.append([True, knots[i][-1]])
            else:
                mix.append([False, points[i][int(j/2)]])
        len_total = 0
        loc_prev = False
        tknots = []
        tpoints = []
        for m in mix:
            loc = mathutils.Vector(bm_mod.verts[m[1]].co[:])
            if not loc_prev:
                loc_prev = loc
            len_total += (loc - loc_prev).length
            if m[0]:
                tknots.append(len_total)
            else:
                tpoints.append(len_total)
            loc_prev = loc
        if regular:
            tpoints = []
            for p in range(len(points[i])):
                tpoints.append((tknots[p] + tknots[p+1]) / 2)
        all_tknots.append(tknots)
        all_tpoints.append(tpoints)

    return(all_tknots, all_tpoints)


# change the location of the points to their place on the spline
def relax_calculate_verts(bm_mod, interpolation, tknots, knots, tpoints,
points, splines):
    change = []
    move = []
    for i in range(len(knots)):
        for p in points[i]:
            m = tpoints[i][points[i].index(p)]
            if m in tknots[i]:
                n = tknots[i].index(m)
            else:
                t = tknots[i][:]
                t.append(m)
                t.sort()
                n = t.index(m)-1
            if n > len(splines[i]) - 1:
                n = len(splines[i]) - 1