mesh_looptools.py

                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 ###############
##########################################

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


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

    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)


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


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


##########################################
####### 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
            elif n < 0:
                n = 0
            
            if interpolation == 'cubic':
                ax, bx, cx, dx, tx = splines[i][n][0]
                x = ax + bx*(m-tx) + cx*(m-tx)**2 + dx*(m-tx)**3
                ay, by, cy, dy, ty = splines[i][n][1]
                y = ay + by*(m-ty) + cy*(m-ty)**2 + dy*(m-ty)**3
                az, bz, cz, dz, tz = splines[i][n][2]
                z = az + bz*(m-tz) + cz*(m-tz)**2 + dz*(m-tz)**3
                change.append([p, mathutils.Vector([x,y,z])])
            else: # interpolation == 'linear'
                a, d, t, u = splines[i][n]
                if u == 0:
                    u = 1e-8
                change.append([p, ((m-t)/u)*d + a])
    for c in change:
        move.append([c[0], (bm_mod.verts[c[0]].co + c[1]) / 2])
    
    return(move)


##########################################
####### Space functions ##################
##########################################

# calculate relative positions compared to first knot
def space_calculate_t(bm_mod, knots):
    tknots = []
    loc_prev = False
    len_total = 0
    for k in knots:
        loc = mathutils.Vector(bm_mod.verts[k].co[:])
        if not loc_prev:
            loc_prev = loc
        len_total += (loc - loc_prev).length
        tknots.append(len_total)
        loc_prev = loc
    amount = len(knots)
    t_per_segment = len_total / (amount - 1)
    tpoints = [i * t_per_segment for i in range(amount)]
    
    return(tknots, tpoints)


# change the location of the points to their place on the spline
def space_calculate_verts(bm_mod, interpolation, tknots, tpoints, points,
splines):
    move = []
    for p in points:
        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
            move.append([p, mathutils.Vector([x,y,z])])
        else: # interpolation == 'linear'
            a, d, t, u = splines[n]
            move.append([p, ((m-t)/u)*d + a])
    
    return(move)


##########################################
####### Operators ########################
##########################################

# bridge operator
class Bridge(bpy.types.Operator):
    bl_idname = 'mesh.looptools_bridge'
    bl_label = "Bridge / Loft"
    bl_description = "Bridge two, or loft several, loops of vertices"
    bl_options = {'REGISTER', 'UNDO'}
    
    cubic_strength = bpy.props.FloatProperty(name = "Strength",
        description = "Higher strength results in more fluid curves",
        default = 1.0,
        soft_min = -3.0,
        soft_max = 3.0)
    interpolation = bpy.props.EnumProperty(name = "Interpolation mode",
        items = (('cubic', "Cubic", "Gives curved results"),
            ('linear', "Linear", "Basic, fast, straight interpolation")),
        description = "Interpolation mode: algorithm used when creating "\
            "segments",
        default = 'cubic')
    loft = bpy.props.BoolProperty(name = "Loft",
        description = "Loft multiple loops, instead of considering them as "\
            "a multi-input for bridging",
        default = False)
    loft_loop = bpy.props.BoolProperty(name = "Loop",
        description = "Connect the first and the last loop with each other",
        default = False)
    min_width = bpy.props.IntProperty(name = "Minimum width",
        description = "Segments with an edge smaller than this are merged "\
            "(compared to base edge)",
        default = 0,
        min = 0,
        max = 100,
        subtype = 'PERCENTAGE')
    mode = bpy.props.EnumProperty(name = "Mode",
        items = (('basic', "Basic", "Fast algorithm"), ('shortest',
            "Shortest edge", "Slower algorithm with better vertex matching")),
        description = "Algorithm used for bridging",
        default = 'shortest')
    remove_faces = bpy.props.BoolProperty(name = "Remove faces",
        description = "Remove faces that are internal after bridging",
        default = True)
    reverse = bpy.props.BoolProperty(name = "Reverse",
        description = "Manually override the direction in which the loops "\
                      "are bridged. Only use if the tool gives the wrong " \
                      "result",
        default = False)
    segments = bpy.props.IntProperty(name = "Segments",
        description = "Number of segments used to bridge the gap "\
            "(0 = automatic)",
        default = 1,
        min = 0,
        soft_max = 20)
    twist = bpy.props.IntProperty(name = "Twist",
        description = "Twist what vertices are connected to each other",
        default = 0)
    
    @classmethod
    def poll(cls, context):
        ob = context.active_object
        return (ob and ob.type == 'MESH' and context.mode == 'EDIT_MESH')
    
    def draw(self, context):
        layout = self.layout
        #layout.prop(self, "mode") # no cases yet where 'basic' mode is needed
        
        # top row
        col_top = layout.column(align=True)
        row = col_top.row(align=True)
        col_left = row.column(align=True)
        col_right = row.column(align=True)
        col_right.active = self.segments != 1
        col_left.prop(self, "segments")
        col_right.prop(self, "min_width", text="")
        # bottom row
        bottom_left = col_left.row()
        bottom_left.active = self.segments != 1
        bottom_left.prop(self, "interpolation", text="")
        bottom_right = col_right.row()
        bottom_right.active = self.interpolation == 'cubic'
        bottom_right.prop(self, "cubic_strength")
        # boolean properties
        col_top.prop(self, "remove_faces")
        if self.loft:
            col_top.prop(self, "loft_loop")
        
        # override properties
        col_top.separator()
        row = layout.row(align = True)
        row.prop(self, "twist")
        row.prop(self, "reverse")
    
    def invoke(self, context, event):
        # load custom settings
        context.window_manager.looptools.bridge_loft = self.loft
        settings_load(self)
        return self.execute(context)
    
    def execute(self, context):
        # initialise
        global_undo, object, bm = initialise()
        edge_faces, edgekey_to_edge, old_selected_faces, smooth = \
            bridge_initialise(bm, self.interpolation)
        settings_write(self)
        
        # check cache to see if we can save time
        input_method = bridge_input_method(self.loft, self.loft_loop)
        cached, single_loops, loops, derived, mapping = cache_read("Bridge",
            object, bm, input_method, False)
        if not cached:
            # get loops
            loops = bridge_get_input(bm)
            if loops:
                # reorder loops if there are more than 2
                if len(loops) > 2:
                    if self.loft:
                        loops = bridge_sort_loops(bm, loops, self.loft_loop)
                    else:
                        loops = bridge_match_loops(bm, loops)
        
        # saving cache for faster execution next time
        if not cached:
            cache_write("Bridge", object, bm, input_method, False, False,
                loops, False, False)
        
        if loops:
            # calculate new geometry
            vertices = []
            faces = []
            max_vert_index = len(bm.verts)-1
            for i in range(1, len(loops)):
                if not self.loft and i%2 == 0:
                    continue
                lines = bridge_calculate_lines(bm, loops[i-1:i+1],
                    self.mode, self.twist, self.reverse)
                vertex_normals = bridge_calculate_virtual_vertex_normals(bm,
                    lines, loops[i-1:i+1], edge_faces, edgekey_to_edge)
                segments = bridge_calculate_segments(bm, lines,
                    loops[i-1:i+1], self.segments)
                new_verts, new_faces, max_vert_index = \
                    bridge_calculate_geometry(bm, lines, vertex_normals,
                    segments, self.interpolation, self.cubic_strength,
                    self.min_width, max_vert_index)
                if new_verts:
                    vertices += new_verts
                if new_faces:
                    faces += new_faces
            # make sure faces in loops that aren't used, aren't removed
            if self.remove_faces and old_selected_faces:
                bridge_save_unused_faces(bm, old_selected_faces, loops)
            # create vertices
            if vertices:
                bridge_create_vertices(bm, vertices)
            # create faces
            if faces:
                bridge_create_faces(object, bm, faces, self.twist)
                bridge_select_new_faces(bm, len(faces), smooth)
            # edge-data could have changed, can't use cache next run
            if faces and not vertices:
                cache_delete("Bridge")
            # delete internal faces
            if self.remove_faces and old_selected_faces:
                bridge_remove_internal_faces(bm, old_selected_faces)
            # make sure normals are facing outside
            bpy.ops.mesh.normals_make_consistent()