mantis/utilities.py

#fool: should be wrColor like prColor... dumb

def wrapRed(skk):    return "\033[91m{}\033[00m".format(skk)
def wrapGreen(skk):  return "\033[92m{}\033[00m".format(skk)
def wrapPurple(skk): return "\033[95m{}\033[00m".format(skk)
def wrapWhite(skk):  return "\033[97m{}\033[00m".format(skk)
def wrapOrange(skk):  return "\033[0;33m{}\033[00m".format(skk)

# these should reimplement the print interface..
def prRed(*args): print (*[wrapRed(arg) for arg in args])
def prGreen(*args): print (*[wrapGreen(arg) for arg in args])
def prPurple(*args): print (*[wrapPurple(arg) for arg in args])
def prWhite(*args): print (*[wrapWhite(arg) for arg in args])
def prOrange(*args): print (*[wrapOrange(arg) for arg in args])



# add THIS to the top of a file for easy access:
# from mantis.utilities import (prRed, prGreen, prPurple, prWhite,
#                               prOrange,
#                               wrapRed, wrapGreen, wrapPurple, wrapWhite,
#                               wrapOrange,)

def float_lerp(a : float, b : float, factor : float)  -> float:
    return (a * (1.0 - factor)) + (b * factor)

# A fuction for getting to the end of a Reroute.
# TODO: this seems really inefficient!
def socket_seek(start_link, links):
    link = start_link
    while(link.from_socket):
        for newlink in links:
            if link.from_socket.node.inputs:
                if link.from_node.bl_idname != 'NodeReroute':
                    return link.from_socket
                if newlink.to_socket == link.from_socket.node.inputs[0]:
                    link=newlink; break
        else:
            break
    return link.from_socket

# THIS ONE is better. I don't know what I was thinking up above.
# TODO: try and refactor to use this function instead
def find_reroute_start_socket(reroute, track='BACK'):
    # "BACK" traces back through the tree
    # "FORWARD" traces forward through the tree
    socket = None
    while (reroute and track == 'BACK'):
        if len(reroute.inputs[0].links) == 1:
            link = reroute.inputs[0].links[0]
            socket = link.from_socket
            if link.from_node.bl_idname == 'NodeReroute':
                reroute =  link.from_node
            else:
                link, reroute = None, None
    while (reroute and track == 'FORWARD'):
        if len(reroute.outputs[0].links) == 1:
            link = reroute.outputs[0].links[0]
            socket = link.to_socket
            if link.to_node.bl_idname == 'NodeReroute':
                reroute =  link.to_node
            else:
                link, reroute = None, None
    return socket

# this creates fake links that have the same interface as Blender's
# so that I can bypass Reroutes
def clear_reroutes(links):
    from .base_definitions import DummyLink
    kept_links, rerouted_starts = [], []
    rerouted = []
    all_links = links.copy()
    while(all_links):
        link = all_links.pop()
        to_cls = link.to_socket.node.bl_idname
        from_cls = link.from_socket.node.bl_idname
        reroute_classes = ["NodeReroute"]
        if (to_cls in reroute_classes and
            from_cls in reroute_classes):
                rerouted.append(link)
        elif (to_cls in reroute_classes and not
            from_cls in reroute_classes):
                rerouted.append(link)
        elif (from_cls in reroute_classes and not
            to_cls in reroute_classes):
                rerouted_starts.append(link)
        else:
            kept_links.append(link)
    for start in rerouted_starts:
        from_socket = socket_seek(start, rerouted)
        new_link = DummyLink(from_socket=from_socket, to_socket=start.to_socket, nc_from=None, nc_to=None, multi_input_sort_id=start.multi_input_sort_id )
        kept_links.append(new_link)
    return kept_links

def tree_from_nc(sig, base_tree):
    if (sig[0] == 'MANTIS_AUTOGENERATED'):
        sig = sig[:-2] # cut off the end part of the signature (because it uses socket.name and socket.identifier)
        # this will lead to totally untraceble bugs in the event of a change in how signatures are assigned
    tree = base_tree
    for i, path_item in enumerate(sig):
        if (i == 0) or (i == len(sig) - 1):
            continue
        tree = tree.nodes.get(path_item).node_tree
    return tree
    
def get_node_prototype(sig, base_tree):
    return tree_from_nc(sig, base_tree).nodes.get( sig[-1] )


##################################################################################################
# groups and changing sockets -- this is used extensively by Schema.
##################################################################################################

# this one returns None if there is an error.
def get_socket_maps(node, force=False):
    maps = [{}, {}]
    node_collection = ["inputs", "outputs"]
    links = ["from_socket", "to_socket"]
    for collection, map, linked_socket in zip(node_collection, maps, links):
        for sock in getattr(node, collection):
            if sock.is_linked:
                other_sockets = []
                # Sort the links first (in case they are mult-input), because Blender doesn't
                links = sorted(list(sock.links), key = lambda l : l.multi_input_sort_id)
                # HACK here because Blender will crash if the socket values in the NodeReroute
                #  are mutated. Because this seems to happen in a deffered way, I can't account
                #  for it except by checking the node later...
                # TODO: The fact that I need this hack means I can probably solve this problem
                #  for all node types in a safer way, since they may also be dynamic somehow
                for l in links:
                    if "from" in linked_socket and l.from_node.bl_idname == "NodeReroute":
                        other_sockets.append(l.from_node)
                    elif "to" in linked_socket and l.to_node.bl_idname == "NodeReroute":
                        other_sockets.append(l.to_node)
                    else:
                        other_sockets.append(getattr(l, linked_socket))
                from bpy.types import NodeSocket
                keep_sockets=[]
                for other_socket in other_sockets.copy():
                    if isinstance(other_socket, NodeSocket) and \
                        other_socket.bl_idname == 'NodeSocketUndefined':
                            continue # this one is bad
                    keep_sockets.append(other_socket)
                # if len(keep_sockets) == 0:
                #     keep_sockets = None
                map[sock.identifier]= keep_sockets
            elif hasattr(sock, "default_value"):
                if sock.get("default_value") is not None:
                    val = sock['default_value']
                elif sock.bl_idname == "EnumCurveSocket" and sock.get("default_value") is None:
                    # HACK I need to add this special case because during file-load,
                    #  this value is None and should not be altered until it is set once.
                    continue
                elif "Enum" in sock.bl_idname and isinstance(sock.get("default_value"), int):
                    continue # for string enum properties that have not yet initialized (at startup)
                elif (val := sock.default_value) is not None:
                    pass
                elif not force:
                    continue
                map[sock.identifier]=val
            else:
                from .socket_definitions import no_default_value
                if sock.bl_idname in no_default_value:
                    map[sock.identifier]=None
                else:
                    raise RuntimeError(f"ERROR: Could not get socket data for socket of type: {sock.bl_idname}")
    return maps

# this function is completely overloaded with different purposes and code paths
# TODO refactor everything that funnels into this function
# make this stuff simpler.
def do_relink(node, s, map, in_out='INPUT', parent_name = ''):
    if not node.__class__.is_registered_node_type(): return
    tree = node.id_data; interface_in_out = 'OUTPUT' if in_out == 'INPUT' else 'INPUT'
    if hasattr(node, "node_tree"):
        tree = node.node_tree
        interface_in_out=in_out
    from bpy.types import NodeSocket, Node
    get_string = '__extend__'
    if s: get_string = s.identifier
    from .base_definitions import SchemaUINode
    if (hasattr(node, "node_tree") or isinstance(node, SchemaUINode)) and get_string not in map.keys():
        # this happens when we are creating a new node group and need to update it from nothing.
        return
    val = map[get_string] # this will throw an error if the socket isn't there. Good!
    if isinstance(val, list):
        for sub_val in val:
            # this will only happen once because it assigns s, so it is safe to do in the for loop.
            if s is None:
                socket = sub_val
                if sub_val.bl_idname == "NodeReroute":
                    # we have to trace the reroute node...
                    if in_out == 'INPUT':
                        socket = find_reroute_start_socket(sub_val)
                    else:
                        socket = find_reroute_start_socket(sub_val, track="FORWARD")
                sock_type = socket.interface_type
                name = unique_socket_name(node, socket, tree)
                if parent_name:
                    interface_socket = update_interface(tree.interface, name, interface_in_out, sock_type, parent_name)
                if in_out =='INPUT':
                    s = node.inputs.new(sock_type, name, identifier=interface_socket.identifier)
                else:
                    s = node.outputs.new(sock_type, name, identifier=interface_socket.identifier)
                if parent_name == 'Array': s.display_shape='SQUARE_DOT'
                if parent_name == 'Constant': s.display_shape='CIRCLE_DOT'
                # then move it up and delete the other link.
                # this also needs to modify the interface of the node tree.
            if isinstance(sub_val, NodeSocket):
                l = None
                if in_out =='INPUT':
                    l = node.id_data.links.new(input=sub_val, output=s)
                else:
                    l = node.id_data.links.new(input=s, output=sub_val)
                if l is None:
                    raise RuntimeError("Could not create link")
            elif isinstance(sub_val, Node):
                l = None
                # this happens when it is a NodeReroute
                if not s.is_output:
                    l = node.id_data.links.new(input=sub_val.outputs[0], output=s)
                else:
                    l = node.id_data.links.new(input=s, output=sub_val.inputs[0])
                if l is None:
                    raise RuntimeError("Could not create link")
            else:
                raise RuntimeError("Unhandled case in do_relink()")
    elif get_string != "__extend__":
        if not s.is_output:
            from bpy.app import version as bpy_version
            if bpy_version >=(4,5,0): # VERSIONING
                # for some reason, this is throwing an error now
                from bpy.types import bpy_prop_array
                if isinstance(val, bpy_prop_array):
                    if in_out == "INPUT" and s.input == False:
                        return # doesn't matter, this is a Matrix socket in a bone or something
                    raise RuntimeError(
                          f"Cannot set property in socket of type {s.bl_idname} due to bug in Blender: "
                          f"{node.id_data.name}:{node.name}:{s.name} ")
                    # TODO: report this weird bug!
            try:
                s.default_value = val
            except (AttributeError, ValueError): # must be readonly or maybe it doesn't have a d.v.
                pass

def update_interface(interface, name, in_out, sock_type, parent_name):
    from bpy.app import version as bpy_version
    if parent_name:
        if not (interface_parent := interface.items_tree.get(parent_name)):
            interface_parent = interface.new_panel(name=parent_name)
        if bpy_version != (4,5,0):
            socket = interface.new_socket(name=name,in_out=in_out, socket_type=sock_type, parent=interface_parent)
        else: # blender 4.5.0 LTS, have to workaround a bug!
            from .versioning import workaround_4_5_0_interface_update
            socket = workaround_4_5_0_interface_update(tree=interface.id_data, name=name, in_out=in_out,
                                                       sock_type=sock_type, parent_name=parent_name, do_parent=True)
        if parent_name == 'Connection':
            in_out = 'OUTPUT' if in_out == 'INPUT' else 'INPUT' # flip this make sure connections always do both
            interface.new_socket(name=name,in_out=in_out, socket_type=sock_type, parent=interface_parent)
        return socket
    else:
        raise RuntimeError(wrapRed("Cannot add interface item to tree without specifying type."))


# D.node_groups['Rigging Nodes'].interface.new_socket('beans', description='the b word', socket_type='NodeSocketGeometry')
#UGLY BAD REFACTOR
def relink_socket_map_add_socket(node, socket_collection, item, in_out=None,):
    from bpy.app import version as bpy_version
    if not in_out: in_out=item.in_out
    if node.bl_idname in ['MantisSchemaGroup'] and item.parent and item.parent.name == 'Array':
        multi = True if in_out == 'INPUT' else False
        # have to work around a bug in 4.5.0 that prevents me from declaring custom socket types
        # I have arbitrarily chosen to use the NodeSocketGeometry type to signal that this one is affected.
        if bpy_version == (4, 5, 0) and item.bl_socket_idname == 'NodeSocketGeometry':
            from .versioning import socket_add_workaround_for_4_5_0_LTS
            s = socket_add_workaround_for_4_5_0_LTS(item, socket_collection, multi)
        else:
            s = socket_collection.new(type=item.bl_socket_idname, name=item.name, identifier=item.identifier,  use_multi_input=multi)
    else:
        if bpy_version == (4, 5, 0) and item.bl_socket_idname == 'NodeSocketGeometry':
            from .versioning import socket_add_workaround_for_4_5_0_LTS
            s = socket_add_workaround_for_4_5_0_LTS(item, socket_collection, multi=False,)
        else:
            s = socket_collection.new(type=item.bl_socket_idname, name=item.name, identifier=item.identifier)
    if item.parent.name == 'Array': s.display_shape = 'SQUARE_DOT'
    elif item.parent.name == 'Constant': s.display_shape='CIRCLE_DOT'
    return s

# TODO REFACTOR THIS
# I did this awful thing because I needed the above code
# but I have provided this interface to Mantis
# I did not follow the Single Responsibility Principle
# I am now suffering for it, as I rightly deserve.
def relink_socket_map(node, socket_collection, map, item, in_out=None,):
    s = relink_socket_map_add_socket(node, socket_collection, item, in_out=None,)
    do_relink(node, s, map)

def unique_socket_name(node, other_socket, tree):
    name_stem = other_socket.bl_label; num=0
    # if hasattr(other_socket, "default_value"):
    #     name_stem = type(other_socket.default_value).__name__
    for item in tree.interface.items_tree:
        if item.item_type == 'PANEL': continue
        if other_socket.is_output and item.in_out == 'INPUT': continue
        if not other_socket.is_output and item.in_out == 'OUTPUT': continue
        if name_stem in item.name: num+=1
    name = name_stem + '.' + str(num).zfill(3)
    return name

##############################
# Dealing with Objects
##############################

# use this to ensure the active object is set back when changing it
def preserve_active_object(func):
    def wrapper(*args, **kwargs):
        import bpy
        original_active = bpy.context.active_object
        func(*args, **kwargs)
        bpy.context.view_layer.objects.active = original_active
    return wrapper

def switch_mode(mode='OBJECT', objects = []):
    active = None
    if objects:
        from bpy import context, ops
        active = objects[-1]
        context.view_layer.objects.active = active
        if (active):
            with context.temp_override(**{'active_object':active, 'selected_objects':objects}):
                ops.object.mode_set(mode=mode)
    return active

# run this in Object mode, during bFinalize
@preserve_active_object
def bind_modifier_operator(modifier, operator):
        # now we have to bind it
        ob = modifier.id_data
        ob.modifiers.active = modifier
        import bpy
        bpy.context.view_layer.objects.active = ob
        # Context override does not do anything here... it isn't handled in the C code
        # I have verified this by building Blender with print statements to debug.

        # let's just make sure the target object has its modifiers disabled and update the dg
        targ_attr = "target"
        if hasattr(modifier, "object"): targ_attr = "object"
        target = getattr(modifier, targ_attr)
        if target:
            prWhite(f"Binding Deformer {modifier.name} to target {target.name}")
            operator(modifier=modifier.name)

def import_widget_obj(path,):
    from bpy.app import version as bpy_version
    from bpy import context, data
    from os import path as os_path
    file_name = os_path.split(path)[-1]
    obj_name = os_path.splitext(file_name)[0]
    if bpy_version < (4,5,0):
        original_active = context.active_object
        # for blender versions prior to 4.5.0, we have to import with an operator
        from bpy.ops import wm as wm_ops
        ob_names_before = data.objects.keys()
        wm_ops.obj_import(
            filepath=path,
            check_existing=False,
            forward_axis='NEGATIVE_Z',
            up_axis='Y',
            validate_meshes=True,)
        # just make sure the active object doesn't change
        context.view_layer.objects.active = original_active
        # the below is a HACK... I can find the objects in the .obj file
        # by scanning the file for the "o" prefix and checking the name.
        # but that may be slow if the obj is big. which would make a bad widget!
        ob = None
        for ob in data.objects:
            if ob.name in ob_names_before: continue
            return ob # return the first one, that should be the one
        else: # no new object was found - fail.
            # I don't expect this to happen unless there is an error in the operator.
            raise RuntimeError(f"Failed to import {file_name}. This is probably"
                                "a bug or a corrupted file.")
    else:
        prWhite(f"INFO: using Geometry Nodes to import {file_name}")
        mesh = data.meshes.new(obj_name)
        ob = data.objects.new(name=obj_name, object_data=mesh)
        # we'll do a geometry nodes import
        context.collection.objects.link(ob)
        import_modifier = ob.modifiers.new("Import OBJ", type="NODES")
        ng = data.node_groups.get("Import OBJ")
        if ng is None:
            from .geometry_node_graphgen import gen_import_obj_node_group
            ng = gen_import_obj_node_group()
        import_modifier.node_group = ng
        import_modifier["Socket_0"]=path
        return ob

def import_object_from_file(path):
    # first let's check to see if we need it.
    from os import path as os_path
    file_name = os_path.split(path)[-1]
    obj_name = os_path.splitext(file_name)[0]
    extension = os_path.splitext(file_name)[1]
    if extension == '.obj':
        return import_widget_obj(path,)
    else:
        raise RuntimeError(f"Failed to parse filename {path}")
        
def import_curve_data_to_object(curve_name, curve_data):
    # the curve data will come as a single curve's data
    from bpy import data
    curve_object = data.objects.new(curve_name, data.curves.new(name=curve_name, type='CURVE'))

    for spline in curve_data:
        curve_object.data.splines.new(type=spline['type'])

##############################
#  READ TREE and also Schema Solve!
##############################

# TODO: refactor the following two functions, they should be one function with arguments.
def init_connections(nc):
    c, hc = [], []
    for i in nc.outputs.values():
        for l in i.links:
            # if l.from_node != nc:
            #     continue
            if l.is_hierarchy:
                hc.append(l.to_node)
            c.append(l.to_node)
    nc.hierarchy_connections = hc
    nc.connections = c

def init_dependencies(nc):
    c, hc = [], []
    for i in nc.inputs.values():
        for l in i.links:
            # if l.to_node != nc:
            #     continue
            if l.is_hierarchy:
                hc.append(l.from_node)
            c.append(l.from_node)
    nc.hierarchy_dependencies = hc
    nc.dependencies = c

def schema_dependency_handle_item(schema, all_nc, item,):
    hierarchy = True
    from .base_definitions import from_name_filter, to_name_filter
    if item.in_out == 'INPUT':
        dependencies = schema.dependencies
        hierarchy_dependencies = schema.hierarchy_dependencies
        if item.parent and item.parent.name == 'Array':
            for schema_idname in ['SchemaArrayInput', 'SchemaArrayInputGet', 'SchemaArrayInputAll']:
                if (nc := all_nc.get( (*schema.signature, schema_idname) )):
                    for to_link in nc.outputs[item.name].links:
                        if to_link.to_socket in to_name_filter:
                            # hierarchy_reason='a'
                            hierarchy = False
                    for from_link in schema.inputs[item.identifier].links:
                        if from_link.from_socket in from_name_filter:
                            hierarchy = False
                            # hierarchy_reason='b'
                        if from_link.from_node not in dependencies:
                            if hierarchy:
                                hierarchy_dependencies.append(from_link.from_node)
                            dependencies.append(from_link.from_node)
        if item.parent and item.parent.name == 'Constant':
            if nc := all_nc.get((*schema.signature, 'SchemaConstInput')):
                for to_link in nc.outputs[item.name].links:
                    if to_link.to_socket in to_name_filter:
                        # hierarchy_reason='dependencies'
                        hierarchy = False
                for from_link in schema.inputs[item.identifier].links:
                    if from_link.from_socket in from_name_filter:
                        # hierarchy_reason='d'
                        hierarchy = False
                    if from_link.from_node not in dependencies:
                        if hierarchy:
                            hierarchy_dependencies.append(from_link.from_node)
                        dependencies.append(from_link.from_node)
        if item.parent and item.parent.name == 'Connection':
            if nc := all_nc.get((*schema.signature, 'SchemaIncomingConnection')):
                for to_link in nc.outputs[item.name].links:
                    if to_link.to_socket in to_name_filter:
                        # hierarchy_reason='e'
                        hierarchy = False
                for from_link in schema.inputs[item.identifier].links:
                    if from_link.from_socket in from_name_filter:
                        # hierarchy_reason='f'
                        hierarchy = False
                    if from_link.from_node not in dependencies:
                        if hierarchy:
                            hierarchy_dependencies.append(from_link.from_node)
                        dependencies.append(from_link.from_node)

def init_schema_dependencies(schema, all_nc):
    """ Initialize the dependencies for Schema, and mark them as hierarchy or non-hierarchy dependencies
        Non-hierarchy dependencies are e.g. drivers and custom transforms.
    """
    tree = schema.prototype.node_tree
    if tree is None:
        raise RuntimeError(f"Cannot get dependencies for schema {schema}")
    schema.dependencies = []
    schema.hierarchy_dependencies = []
    for l in schema.inputs["Schema Length"].links:
        schema.hierarchy_dependencies.append(l.from_node)
    if tree.interface:
        for item in tree.interface.items_tree:
            if item.item_type == 'PANEL':
                continue
            schema_dependency_handle_item(schema, all_nc, item,)

def check_and_add_root(n, roots, include_non_hierarchy=False):
    if (include_non_hierarchy * len(n.dependencies)) > 0:
        return 
    elif len(n.hierarchy_dependencies) > 0:
        return
    roots.append(n)

def get_link_in_out(link):
    from .base_definitions import replace_types
    from_name, to_name = link.from_socket.node.name, link.to_socket.node.name
    # catch special bl_idnames and bunch the connections up
    if link.from_socket.node.bl_idname in replace_types:
        from_name = link.from_socket.node.bl_idname 
    if link.to_socket.node.bl_idname in replace_types:
        to_name = link.to_socket.node.bl_idname
    return from_name, to_name

def link_node_containers(tree_path_names, link, local_nc, from_suffix='', to_suffix=''):
    dummy_types = ["DUMMY", "DUMMY_SCHEMA"]
    from_name, to_name = get_link_in_out(link)
    nc_from = local_nc.get( (*tree_path_names, from_name+from_suffix) )
    nc_to = local_nc.get( (*tree_path_names, to_name+to_suffix))
    if (nc_from and nc_to):
        from_s, to_s = link.from_socket.name, link.to_socket.name
        if nc_to.node_type in dummy_types: to_s = link.to_socket.identifier
        if nc_from.node_type in dummy_types: from_s = link.from_socket.identifier
        try:
            connection = nc_from.outputs[from_s].connect(node=nc_to, socket=to_s, sort_id=link.multi_input_sort_id)
            if connection is None:
                prWhite(f"Already connected: {from_name}:{from_s}->{to_name}:{to_s}")
            return connection
        except KeyError as e:
            prRed(f"{nc_from}:{from_s} or {nc_to}:{to_s} missing; review the connections printed below:")
            print (nc_from.outputs.keys())
            print (nc_to.inputs.keys())
            raise e
    else:
        prRed(nc_from, nc_to, (*tree_path_names, from_name+from_suffix), (*tree_path_names, to_name+to_suffix))
        raise RuntimeError(wrapRed("Link not connected: %s -> %s in tree %s" % (from_name, to_name, tree_path_names[-1])))
    
def get_all_dependencies(nc):
    from .base_definitions import GraphError
    """ find all dependencies for a mantis node"""
    nodes = []
    check_nodes = [nc]
    nodes_checked = set()
    while (len(check_nodes) > 0):
        node = check_nodes.pop()
        nodes_checked.add (node)
        connected_nodes = node.hierarchy_dependencies
        for new_node in connected_nodes:
            if new_node in nodes:
                continue
            nodes.append(new_node)
            if new_node not in nodes_checked:
                check_nodes.append(new_node)
    return nodes
                
def get_all_nodes_of_type(base_tree, bl_idname):
    nodes = []
    check_nodes = list(base_tree.nodes)
    while (len(check_nodes) > 0):
        node = check_nodes.pop()
        if node.bl_idname in bl_idname:
            nodes.append(node)
        if hasattr(node, "node_tree"):
            check_nodes.extend(list(node.node_tree.nodes))
    return nodes

def trace_all_nodes_from_root(root, nodes):
    from .base_definitions import GraphError
    """ find all dependencies for a mantis node"""
    nodes.add(root); check_nodes = [root]
    nodes_checked = set()
    while (len(check_nodes) > 0):
        node = check_nodes.pop(); nodes_checked.add (node)
        connected_nodes = []
        for output in node.outputs:
            for l in output.links:
                if l.to_node not in nodes:
                    connected_nodes.append(l.to_node)
        for new_node in connected_nodes:
            nodes.add(new_node)
            if new_node not in nodes_checked:
                check_nodes.append(new_node)
    return nodes
            
##################################################################################################
# misc
##################################################################################################

# TODO: get the matrix to return a mathutils.Matrix so I don't need a function call here
def to_mathutils_value(socket):
    if hasattr(socket, "default_value"):
        val = socket.default_value
        if socket.bl_idname in ['MatrixSocket']:
            return socket.TellValue()
        else:
            return val
    else:
        return None


def all_trees_in_tree(base_tree, selected=False):
    """ Recursively finds all trees referenced in a given base-tree."""
    # note that this is recursive but not by tail-end recursion
    # a while-loop is a better way to do recursion in Python.
    trees = [base_tree]
    can_descend = True
    check_trees = [base_tree]
    while (len(check_trees) > 0): # this seems innefficient, why 2 loops?
        new_trees = []
        while (len(check_trees) > 0):
            tree = check_trees.pop()
            for node in tree.nodes:
                if selected == True and node.select == False:
                    continue
                if new_tree := getattr(node, "node_tree", None):
                    if new_tree in trees: continue 
                    new_trees.append(new_tree)
                    trees.append(new_tree)
        check_trees = new_trees
    return trees

# this is a destructive operation, not a pure function or whatever. That isn't good but I don't care.
def SugiyamaGraph(tree, iterations):
        from grandalf.graphs import Vertex, Edge, Graph, graph_core
        class defaultview(object):
            w,h = 1,1
            xz = (0,0)
        
        graph = Graph()
        no_links = set()
        verts = {}
        for n in tree.nodes:
            if n.select == True:
                v = Vertex(n.name)
                v.view = defaultview()
                v.view.xy = n.location
                v.view.h = n.height*2.5
                v.view.w = n.width*2.2
                verts[n.name] = v
                no_links.add(n.name)
                graph.add_vertex(v)
            n.select=False
            
        edges = []
        inverted_edges=[]
        not_a_root = set()
        for link in tree.links:
            if (link.from_node.name not in verts.keys()) or (link.to_node.name not in verts.keys()):
                continue # problem??
            weight = 1 # maybe this is useful
            not_a_root.add(link.to_node.name) # if it has a edge-input it is not a root.
            e = Edge(verts[link.from_node.name], verts[link.to_node.name], weight)
            graph.add_edge(e)
            edges.append(e )
            if link.is_valid == False:
                inverted_edges.append(e)
            if link.from_node.name in no_links:
                no_links.remove(link.from_node.name)
            if link.to_node.name in no_links:
                no_links.remove(link.to_node.name)
        try:
            from grandalf.layouts import SugiyamaLayout
            # .C[0] is the first "graph core" that contains a connected graph.
            sug = SugiyamaLayout(graph.C[0]) 
            sug.init_all()
            sug.draw(iterations)
            # Digco is good for small graphs.
            # from grandalf.layouts import DigcoLayout
            # dco = DigcoLayout(graph.C[0])
            # dco.init_all()
            # dco.draw(iterations)
        except KeyboardInterrupt:
            pass # just use what it has calculated so far, I guess

        for v in graph.C[0].sV:
            for n in tree.nodes:
                if n.name == v.data:
                    n.location.x = v.view.xy[1]
                    n.location.y = v.view.xy[0]
                    n.select = True
        
        # now we can take all the input nodes and try to put them in a sensible place
        # not sure why but this absolutely does not do anything
        for n_name in no_links:
            n = tree.nodes.get(n_name)
            next_node = None
            for output in n.outputs:
                if output.is_linked == True:
                    next_node = output.links[0].to_node
                    break
            # let's see if the next node
            if next_node:
                # need to find the other node in the same layer...
                other_node = None
                for s_input in next_node.inputs:
                    if s_input.is_linked:
                        other_node = s_input.links[0].from_node
                        if other_node is n:
                            continue
                        else:
                            break
                if other_node:
                    n.location = other_node.location
                    n.location.y -= other_node.height*2
                else: # we'll just position it next to the next node
                    n.location = next_node.location
                    n.location.x -= next_node.width*1.5
        

def project_point_to_plane(point, origin, normal):
    return point - normal.dot(point- origin)*normal

##################################################################################################
# stuff I should probably refactor!!
##################################################################################################

# This is really, really stupid way to do this
def gen_nc_input_for_data(socket):
    # Class List #TODO deduplicate
    from . import xForm_nodes, link_nodes, misc_nodes, primitives_nodes, deformer_nodes, math_nodes, schema_nodes
    from .internal_containers import NoOpNode
    classes = {}
    for module in [xForm_nodes, link_nodes, misc_nodes, primitives_nodes, deformer_nodes, math_nodes, schema_nodes]:
        for cls in module.TellClasses():
            classes[cls.__name__] = cls
    #
    socket_class_map = {
                        "MatrixSocket"                         : classes["InputMatrix"],
                        "xFormSocket"                          : None,
                        "RelationshipSocket"                   : NoOpNode,
                        "DeformerSocket"                       : NoOpNode,
                        "GeometrySocket"                       : classes["InputExistingGeometryData"],
                        "EnableSocket"                         : classes["InputBoolean"],
                        "HideSocket"                           : classes["InputBoolean"],
                        #
                        "DriverSocket"                         : None,
                        "DriverVariableSocket"                 : None, 
                        "FCurveSocket"                         : None, 
                        "KeyframeSocket"                       : None,
                        "BoneCollectionSocket"                 : classes["InputString"],
                        #
                        "xFormParameterSocket"                 : None,
                        "ParameterBoolSocket"                  : classes["InputBoolean"],
                        "ParameterIntSocket"                   : classes["InputFloat"],  #TODO: make an Int node for this
                        "ParameterFloatSocket"                 : classes["InputFloat"],
                        "ParameterVectorSocket"                : classes["InputVector"],
                        "ParameterStringSocket"                : classes["InputString"],
                        #
                        "TransformSpaceSocket"                 : classes["InputTransformSpace"],
                        "BooleanSocket"                        : classes["InputBoolean"],
                        "BooleanThreeTupleSocket"              : classes["InputBooleanThreeTuple"],
                        "RotationOrderSocket"                  : classes["InputRotationOrder"],
                        "QuaternionSocket"                     : None,
                        "QuaternionSocketAA"                   : None,
                        "UnsignedIntSocket"                    : classes["InputFloat"],
                        "IntSocket"                            : classes["InputFloat"],
                        "StringSocket"                         : classes["InputString"],
                        #
                        "BoolUpdateParentNode"                 : classes["InputBoolean"],
                        "IKChainLengthSocket"                  : classes["InputFloat"],
                        "EnumInheritScale"                     : classes["InputString"],
                        "EnumRotationMix"                      : classes["InputString"],
                        "EnumRotationMixCopyTransforms"        : classes["InputString"],
                        "EnumMaintainVolumeStretchTo"          : classes["InputString"],
                        "EnumRotationStretchTo"                : classes["InputString"],
                        "EnumTrackAxis"                        : classes["InputString"],
                        "EnumUpAxis"                           : classes["InputString"],
                        "EnumLockAxis"                         : classes["InputString"],
                        "EnumLimitMode"                        : classes["InputString"],
                        "EnumYScaleMode"                       : classes["InputString"],
                        "EnumXZScaleMode"                      : classes["InputString"],
                        "EnumCurveSocket"                      : classes["InputString"],
                        "EnumMetaRigSocket"                    : classes["InputString"],
                        # Deformers
                        "EnumSkinning"                         : classes["InputString"],
                        #
                        "FloatSocket"                          : classes["InputFloat"],
                        "FloatFactorSocket"                    : classes["InputFloat"],
                        "FloatPositiveSocket"                  : classes["InputFloat"],
                        "FloatAngleSocket"                     : classes["InputFloat"],
                        "VectorSocket"                         : classes["InputVector"],
                        "VectorEulerSocket"                    : classes["InputVector"],
                        "VectorTranslationSocket"              : classes["InputVector"],
                        "VectorScaleSocket"                    : classes["InputVector"],
                        # Drivers             
                        "EnumDriverVariableType"               : classes["InputString"],
                        "EnumDriverVariableEvaluationSpace"    : classes["InputString"],
                        "EnumDriverRotationMode"               : classes["InputString"],
                        "EnumDriverType"                       : classes["InputString"],
                        "EnumKeyframeInterpTypeSocket"         : classes["InputString"],
                        "EnumKeyframeBezierHandleTypeSocket"   : classes["InputString"],
                        # Math
                        "MathFloatOperation"                   : classes["InputString"],
                        "MathVectorOperation"                  : classes["InputString"],
                        "MatrixTransformOperation"             : classes["InputString"],
                        # Schema
                        "WildcardSocket"                       : None,
                       }
    return socket_class_map.get(socket.bl_idname, None)

####################################
# CURVE STUFF
####################################

def make_perpendicular(v1, v2):
    from .base_definitions import FLOAT_EPSILON
    if (v1.length_squared < FLOAT_EPSILON) or (v2.length_squared < FLOAT_EPSILON):
        raise RuntimeError("Cannot generate perpendicular vetor for zero-length vector")
    projected = (v2.dot(v1) / v1.dot(v1)) * v1
    perpendicular = v2 - projected
    return perpendicular

# this stuff could be branchless but I don't use it much TODO
def cap(val, maxValue):
    if (val > maxValue):
        return maxValue
    return val

def capMin(val, minValue):
    if (val < minValue):
        return minValue
    return val

def wrap(min : float, max : float, value: float) -> float:
    range = max-min; remainder = value % range
    if remainder > max: return min + remainder-max
    else: return remainder

def lerpVal(a, b, fac = 0.5):
    return a + ( (b-a) * fac)

#wtf this doesn't do anything even remotely similar to wrap
# HACK BAD FIXME UNBREAK ME BAD
# I don't understand what this function does but I am using it in multiple places?
def old_bad_wrap_that_should_be_refactored(val, maxValue, minValue = None):
    if (val > maxValue):
        return (-1 * ((maxValue - val) + 1))
    if ((minValue) and (val < minValue)):
        return (val + maxValue)
    return val
    #TODO clean this up

def extract_spline_suffix(spline_index):
    return ".spline."+str(spline_index).zfill(3)+".extracted"

def do_extract_spline(data, spline):
    remove_me = []
    for other_spline in data.splines:
        if other_spline != spline: remove_me.append(other_spline)
    while remove_me: data.splines.remove(remove_me.pop())

def extract_spline(curve, spline_index):
    """ Given a curve object and spline index, returns a new object
        containing only the selcted spline. The new object is bound to
        the original curve.
    """
    if len(curve.data.splines) == 1:
        return curve # nothing to do here.
    spline_suffix = extract_spline_suffix(spline_index)
    from bpy import data
    if (new_ob := data.objects.get(curve.name+spline_suffix)) is None:
        new_ob=curve.copy(); new_ob.name=curve.name+spline_suffix
    # if the data exists, it is probably stale, so delete it and start over.
    if (old_data := data.objects.get(curve.data.name+spline_suffix)) is not None:
        data.curves.remove(old_data)
    new_data=curve.data.copy(); new_data.name=curve.data.name+spline_suffix
    new_ob.data = new_data
    # do not check for index error here, it is the calling function's responsibility
    do_extract_spline(new_data, new_data.splines[spline_index])
    return new_ob

def bind_extracted_spline_to_curve(new_ob, curve):
    # Set up a relationship between the new object and the old object
    # now, weirdly enough - we can't use parenting very easily because Blender
    # defines the parent on a curve relative to the evaluated path animation
    # Setting the inverse matrix is too much work. Use Copy Transforms instead.
    from .xForm_nodes import reset_object_data
    reset_object_data(new_ob)
    c = new_ob.constraints.new("COPY_TRANSFORMS"); c.target=curve
    new_ob.parent=curve
    return new_ob

def get_extracted_spline_object(proto_curve, spline_index, mContext):
    # we're storing it separately like this to ensure all nodes use the same
    #   object if they extract the same spline for use by Mantis.
    # this should be transparent to the user since it is working around a
    #   a limitation in Blender.
    extracted_spline_name = proto_curve.name+extract_spline_suffix(spline_index)
    if curve := mContext.b_objects.get(extracted_spline_name):
        return curve
    else:
        curve = extract_spline(proto_curve, spline_index)
        if curve.name != proto_curve.name: # if there is only one spline, no
            bind_extracted_spline_to_curve(curve, proto_curve)# dupe is created.
        mContext.b_objects[extracted_spline_name] = curve
        return curve

def nurbs_copy_bez_spline(curve, bez_spline, do_setup=True):
    other_spline= curve.data.splines.new('NURBS')
    other_spline.use_endpoint_u=True
    other_spline.use_bezier_u=True
    bez_pts = bez_spline.bezier_points
    bez_data=[]
    for i, bez_pt in enumerate(bez_pts):
        if i > 0:
            bez_data.append(bez_pt.handle_left.copy())
        bez_data.append(bez_pt.co.copy())
        if i != len(bez_pts)-1:
            bez_data.append(bez_pt.handle_right.copy())
    other_spline.points.add(len(bez_data)-1)
    for i, pt in enumerate(bez_data):
        other_spline.points[i].co=(*pt,1.0) # add the W value here
    if do_setup: # do the stuff that makes it behave the same as a bez spline
        other_spline.use_endpoint_u = True; other_spline.use_bezier_u = True
        other_spline.order_u=4 # set to 1 for poly
    return other_spline

def RibbonMeshEdgeLengths(m, ribbon):
    tE = ribbon[0]; bE = ribbon[1]; c = ribbon[2]
    lengths = []
    for i in range( len( tE ) ): #tE and bE are same length
        if (c == True):
            v1NextInd = tE[old_bad_wrap_that_should_be_refactored((i+1), len(tE) - 1)]
        else:
            v1NextInd = tE[cap((i+1) , len(tE) - 1 )]
        v1 = m.vertices[tE[i]]; v1Next = m.vertices[v1NextInd]
        if (c == True):
            v2NextInd = bE[old_bad_wrap_that_should_be_refactored((i+1), len(bE) - 1)]
        else:
            v2NextInd = bE[cap((i+1) , len(bE) - 1 )]
        v2 = m.vertices[bE[i]]; v2Next = m.vertices[v2NextInd]
        
        v = v1.co.lerp(v2.co, 0.5); vNext = v1Next.co.lerp(v2Next.co, 0.5)
        # get the center, edges may not be straight so total length 
        #  of one edge may be more than the ribbon center's length
        lengths.append(( v - vNext ).length)
    return lengths

def EnsureCurveIsRibbon(crv, defaultRadius = 0.1):
    from .base_definitions import FLOAT_EPSILON
    crvRadius = 0
    crv.data.offset = 0
    if (crv.data.bevel_depth < FLOAT_EPSILON):
        crvRadius = crv.data.extrude
    else: #Set ribbon from bevel depth
        crvRadius = crv.data.bevel_depth
        crv.data.bevel_depth = 0
        crv.data.extrude = crvRadius
    if (crvRadius < FLOAT_EPSILON):
        crv.data.extrude = defaultRadius

def SetRibbonData(m, ribbon):
    #maybe this could be incorporated into the DetectWireEdges function?
    #maybe I can check for closed poly curves here? under what other circumstance
    # will I find the ends of the wire have identical coordinates?
    ribbonData = []
    tE = ribbon[0].copy(); bE = ribbon[1].copy()# circle = ribbon[2]
    #
    lengths = RibbonMeshEdgeLengths(m, ribbon)
    lengths.append(0)
    totalLength = sum(lengths)
    # m.calc_normals() #calculate normals
    # it appears this has been removed.
    for i, (t, b) in enumerate(zip(tE, bE)):
        ind = old_bad_wrap_that_should_be_refactored( (i + 1), len(tE) - 1 )
        tNext = tE[ind]; bNext = bE[ind]
        ribbonData.append(  ( (t,b), (tNext, bNext), lengths[i] ) )
        #if this is a circle, the last v in vertData has a length, otherwise 0
    return ribbonData, totalLength

def WireMeshEdgeLengths(m, wire):
    circle = False
    vIndex = wire.copy()
    for e in m.edges:
        if ((e.vertices[0] == vIndex[-1]) and (e.vertices[1] == vIndex[0])):
            #this checks for an edge between the first and last vertex in the wire
            circle = True
            break
    lengths = []
    for i in range(len(vIndex)):
        v = m.vertices[vIndex[i]]
        if (circle == True):
            vNextInd = vIndex[old_bad_wrap_that_should_be_refactored((i+1), len(vIndex) - 1)]
        else:
            vNextInd = vIndex[cap((i+1), len(vIndex) - 1 )]
        vNext = m.vertices[vNextInd]
        lengths.append(( v.co - vNext.co ).length)
    #if this is a circular wire mesh, this should wrap instead of cap
    return lengths

def GetDataFromWire(m, wire):
    vertData = []
    vIndex = wire.copy()
    lengths = WireMeshEdgeLengths(m, wire)
    lengths.append(0)
    totalLength = sum(lengths)
    for i, vInd in enumerate(vIndex):
        #-1 to avoid IndexError
        vNext = vIndex[ (old_bad_wrap_that_should_be_refactored(i+1, len(vIndex) - 1)) ]
        vertData.append((vInd, vNext, lengths[i]))
    #if this is a circle, the last v in vertData has a length, otherwise 0
    return vertData, totalLength

def DetectWireEdges(mesh):
    # Returns a list of vertex indices belonging to wire meshes
    # NOTE: this assumes a mesh object with only wire meshes
    ret = []
    import bmesh
    bm = bmesh.new()
    try:
        bm.from_mesh(mesh)
        ends = []
        for v in bm.verts:
            if (len(v.link_edges) == 1):
                ends.append(v.index)
        for e in bm.edges:
            assert (e.is_wire == True),"This function can only run on wire meshes"
            if (e.verts[1].index - e.verts[0].index != 1):
                ends.append(e.verts[1].index)
                ends.append(e.verts[0].index)
        for i in range(len(ends)//2): # // is floor division
            beg = ends[i*2]
            end = ends[(i*2)+1]
            indices = [(j + beg) for j in range ((end - beg) + 1)]
            ret.append(indices)
    finally:
        bm.free()
        return ret

def FindNearestPointOnWireMesh(m, pointsList):
    from mathutils import Vector
    from mathutils.geometry import intersect_point_line
    from math import sqrt
    wires = DetectWireEdges(m)
    ret = []
    # prevFactor = None
    for wire, points in zip(wires, pointsList):
        vertData, total_length = GetDataFromWire(m, wire)
        factorsOut = []
        for p in points:
            prevDist = float('inf')
            curDist  = float('inf')
            v1 = None
            v2 = None
            for i in range(len(vertData) - 1):
                #but it shouldn't check the last one
                if (p == m.vertices[i].co):
                    v1 = vertData[i]
                    v2 = vertData[i+1]
                    offset = 0
                    break
                else:
                    curDist = ( ((m.vertices[vertData[i][0]].co - p).length) +
                                ((m.vertices[vertData[i][1]].co - p).length) )/2
                if (curDist < prevDist):
                    v1 = vertData[i]
                    v2 = vertData[i+1]
                    prevDist = curDist
                    offset = intersect_point_line(p, m.vertices[v1[0]].co, 
                                                     m.vertices[v2[0]].co)[1]
            if (offset < 0):
                offset = 0
            elif (offset > 1):
                offset = 1
            # Assume the vertices are in order
            v1Length = 0
            v2Length = v2[2]
            for i in range(v1[0]):
                v1Length += vertData[i][2]
            factor = ((offset * (v2Length)) + v1Length )/total_length
            factor = wrap(0, 1, factor) # doesn't hurt to wrap it if it's over 1 or less than 0
            factorsOut.append(factor)
        ret.append( factorsOut )
    return ret


def mesh_from_curve(crv, context, ribbon=True):
    """Utility function for converting a mesh to a curve
       which will return the correct mesh even with modifiers"""
    import bpy
    m = None
    bevel = crv.data.bevel_depth
    extrude = crv.data.extrude
    offset = crv.data.offset
    try:
        if (len(crv.modifiers) > 0):
            do_unlink = False
            if (not context.scene.collection.all_objects.get(crv.name)):
                context.collection.objects.link(crv) # i guess this forces the dg to update it?
                do_unlink = True
            dg = context.view_layer.depsgraph
            # just gonna modify it for now lol
            if ribbon:
                EnsureCurveIsRibbon(crv)
            else:
                crv.data.bevel_depth=0
                crv.data.extrude=0
                crv.data.offset=0
            # try:
            dg.update()
            mOb = crv.evaluated_get(dg)
            m = bpy.data.meshes.new_from_object(mOb)
            m.name=crv.data.name+'_mesh'
            if (do_unlink):
                context.collection.objects.unlink(crv)
        else: # (ಥ﹏ಥ) why can't I just use this !
            # for now I will just do it like this
            if ribbon:
                EnsureCurveIsRibbon(crv)
            else:
                crv.data.bevel_depth=0
                crv.data.extrude=0
                crv.data.offset=0
            m = bpy.data.meshes.new_from_object(crv)
    finally:
        crv.data.bevel_depth = bevel
        crv.data.extrude = extrude
        crv.data.offset = offset
    return m

def DetectRibbon(f, bm, skipMe):
    fFirst = f.index
    cont = True
    circle = False
    tEdge, bEdge = [],[]
    while (cont == True):
        skipMe.add(f.index)
        tEdge.append (f.loops[0].vert.index) # top-left
        bEdge.append (f.loops[3].vert.index) # bottom-left
        nEdge = bm.edges.get([f.loops[1].vert, f.loops[2].vert])
        nFaces = nEdge.link_faces
        if (len(nFaces) == 1): 
            cont = False
        else:
            for nFace in nFaces:
                if (nFace != f):
                    f = nFace
                    break
            if (f.index == fFirst):
                cont = False
                circle = True
        if (cont == False): # we've reached the end, get the last two:
            tEdge.append (f.loops[1].vert.index) # top-right
            bEdge.append (f.loops[2].vert.index) # bottom-right
            # this will create a loop for rings -- 
            #  "the first shall be the last and the last shall be first"
    return (tEdge,bEdge,circle)

def DetectRibbons(m, fReport = None):
    # Returns list of vertex indices belonging to ribbon mesh edges
    # NOTE: this assumes a mesh object with only ribbon meshes
    # ---DO NOT call this script with a mesh that isn't a ribbon!--- #
    import bmesh
    bm = bmesh.new()
    bm.from_mesh(m)
    mIslands, mIsland = [], []
    skipMe = set()
    bm.faces.ensure_lookup_table()
    #first, get a list of mesh islands
    for f in bm.faces:
        if (f.index in skipMe):
            continue #already done here
        checkMe = [f]
        while (len(checkMe) > 0):
            facesFound = 0
            for f in checkMe:
                if (f.index in skipMe):
                    continue #already done here
                mIsland.append(f)
                skipMe.add(f.index)
                for e in f.edges:
                    checkMe += e.link_faces
            if (facesFound == 0):
                #this is the last iteration
                mIslands.append(mIsland)
                checkMe, mIsland = [], []
    ribbons = []
    skipMe = set() # to store ends already checked
    for mIsl in mIslands:
        ribbon = None
        first = float('inf')
        for f in mIsl:
            if (f.index in skipMe):
                continue #already done here
            if (f.index < first):
                first = f.index
            adjF = 0
            for e in f.edges:
                adjF+= (len(e.link_faces) - 1)
                # every face other than this one is added to the list
            if (adjF == 1):
                ribbon = (DetectRibbon(f, bm, skipMe) )
                break
        if (ribbon == None):
            ribbon = (DetectRibbon(bm.faces[first], bm, skipMe) )
        ribbons.append(ribbon)
    # print (ribbons)
    return ribbons

def data_from_ribbon_mesh(m, factorsList, mat, ribbons = None, fReport = None):
    #Note, factors list should be equal in length the the number of wires
    #Now working for multiple wires, ugly tho
    if (ribbons == None):
        ribbons = DetectRibbons(m, fReport=fReport)
        if (ribbons is None):
            if (fReport):
                fReport(type = {'ERROR'}, message="No ribbon to get data from.")
            else:  
                print ("No ribbon to get data from.")
            return None
    ret = []
    for factors, ribbon in zip(factorsList, ribbons):
        points  = []
        widths  = []
        normals = []
        ribbonData, totalLength = SetRibbonData(m, ribbon)

        for fac in factors:
            if (fac == 0):
                data = ribbonData[0]
                curFac = 0
            elif (fac == 1):
                data = ribbonData[-1]
                curFac = 0
            else:
                targetLength = totalLength * fac
                data = ribbonData[0]
                curLength = 0
                for ( (t, b), (tNext, bNext), length,) in ribbonData:
                    if (curLength >= targetLength):
                        break
                    curLength += length
                    data = ( (t, b), (tNext, bNext), length,)
                targetLengthAtEdge = (curLength - targetLength)
                if (targetLength == 0):
                    curFac = 0
                elif (targetLength == totalLength):
                    curFac = 1
                else:
                    # NOTE: This can be Zero. Find out why!
                    if data[2] == 0:
                        curFac=0
                    else:
                        curFac = 1 - (targetLengthAtEdge/ data[2]) #length
            t1 = m.vertices[data[0][0]]; b1 = m.vertices[data[0][1]]
            t2 = m.vertices[data[1][0]]; b2 = m.vertices[data[1][1]]
            #location
            loc1 = (t1.co).lerp(b1.co, 0.5)
            loc2 = (t2.co).lerp(b2.co, 0.5)
            #width
            w1 = (t1.co - b1.co).length/2
            w2 = (t2.co - b2.co).length/2 #radius, not diameter
            #normal
            n1 = (t1.normal).slerp(b1.normal, 0.5)
            n2 = (t1.normal).slerp(b2.normal, 0.5)
            if ((data[0][0] > data[1][0]) and (ribbon[2] == False)):
                curFac = 0
                #don't interpolate if at the end of a ribbon that isn't circular
            if ( 0 < curFac < 1):
                outPoint = loc1.lerp(loc2, curFac)
                outNorm  = n1.lerp(n2, curFac)
                outWidth = w1 + ( (w2-w1) * curFac)
            elif (curFac <= 0):
                outPoint = loc1.copy()
                outNorm = n1
                outWidth = w1
            elif (curFac >= 1):
                outPoint = loc2.copy()
                outNorm = n2
                outWidth = w2
            outPoint = mat @ outPoint
            outNorm.normalize()
            points.append ( outPoint.copy() ) #copy because this is an actual vertex location
            widths.append ( outWidth )
            normals.append( outNorm )
        ret.append( (points, widths, normals) )
    return ret # this is a list of tuples containing three lists




#This bisection search is generic, and it searches based on the
# magnitude of the error, rather than the sign.
# If the sign of the error is meaningful, a simpler function
# can be used.
def do_bisect_search_by_magnitude(
        owner, 
        attribute,
        index = None,
        test_function = None,
        modify = None,
        max_iterations = 10000,
        threshold = 0.0001,
        thresh2   = 0.0005,
        context = None,
        update_dg = None,
    ):
    from math import floor
    i = 0; best_so_far = 0; best = float('inf')
    min = 0; center = max_iterations//2; max = max_iterations
    # enforce getting the absolute value, in case the function has sign information
    # The sign may be useful in a sign-aware bisect search, but this one is more robust!
    test = lambda : abs(test_function(owner, attribute, index, context = context,))
    while (i <= max_iterations):
        upper = (max - ((max-center))//2)
        modify(owner, attribute, index, upper, context = context); error1 = test()
        lower = (center - ((center-min))//2)
        modify(owner, attribute, index, lower, context = context); error2 = test()
        if (error1 < error2):
            min = center
            center, check = upper, upper
            error = error1
        else:
            max = center
            center, check = lower, lower
            error = error2
        if (error <= threshold) or (min == max-1):
            break
        if (error < thresh2):
            j = min
            while (j < max):
                modify(owner, attribute, index, j * 1/max_iterations, context = context)
                error = test()
                if (error < best):
                    best_so_far = j; best = error
                if (error <= threshold):
                    break
                j+=1
            else: # loop has completed without finding a solution
                i = best_so_far; error = test()
                modify(owner, attribute, index, best_so_far, context = context)
                break
        if (error < best):
            best_so_far = check; best = error
        i+=1
        if update_dg:
            update_dg.update()
    else: # Loop has completed without finding a solution
        i = best_so_far
        modify(owner, attribute, best_so_far, context = context); i+=1