io_export_paper_model.py

# -*- coding: utf-8 -*-
# ##### BEGIN GPL LICENSE BLOCK #####
#
#  This program is free software: you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation, either version 2 of the License, or
#  (at your option) any later version.
#
#  This program is distributed in the hope that it will be useful,
#  but without any warranty; without even the implied warranty of
#  merchantability or fitness for a particular purpose.  See the
#  GNU General Public License for more details.
#
#  You should have received a copy of the GNU General Public License
#  along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
# ##### END GPL LICENSE BLOCK #####

bl_info = {
    "name": "Export Paper Model",
    "author": "Addam Dominec",
    "version": (0, 9),
    "blender": (2, 73, 0),
    "location": "File > Export > Paper Model",
    "warning": "",
    "description": "Export printable net of the active mesh",
    "category": "Import-Export",
    "wiki_url": "http://wiki.blender.org/index.php/Extensions:2.6/Py/"
                "Scripts/Import-Export/Paper_Model",
    "tracker_url": "https://developer.blender.org/T38441"
}

# TODO:
# sanitize the constructors Edge, Face, UVFace so that they don't edit their parent object
# The Exporter classes should take parameters as a whole pack, and parse it themselves
# remember objects selected before baking (except selected to active)
# add 'estimated number of pages' to the export UI
# profile QuickSweepline vs. BruteSweepline with/without blist: for which nets is it faster?
# rotate islands to minimize area -- and change that only if necessary to fill the page size
# Sticker.vertices should be of type Vector

# check conflicts in island naming and either:
#  * append a number to the conflicting names or
#  * enumerate faces uniquely within all islands of the same name (requires a check that both label and abbr. equals)


"""

Additional links:
    e-mail: adominec {at} gmail {dot} com

"""
import bpy
import bl_operators
import bgl
import mathutils as M
from re import compile as re_compile
from itertools import chain, repeat
from math import pi, ceil

try:
    import os.path as os_path
except ImportError:
    os_path = None

try:
    from blist import blist
except ImportError:
    blist = list

default_priority_effect = {
    'CONVEX': 0.5,
    'CONCAVE': 1,
    'LENGTH': -0.05
}

global_paper_sizes = [
    ('USER', "User defined", "User defined paper size"),
    ('A4', "A4", "International standard paper size"),
    ('A3', "A3", "International standard paper size"),
    ('US_LETTER', "Letter", "North American paper size"),
    ('US_LEGAL', "Legal", "North American paper size")
]


def first_letters(text):
    """Iterator over the first letter of each word"""
    for match in first_letters.pattern.finditer(text):
        yield text[match.start()]
first_letters.pattern = re_compile("((?<!\w)\w)|\d")


def is_upsidedown_wrong(name):
    """Tell if the string would get a different meaning if written upside down"""
    chars = set(name)
    mistakable = set("69NZMWpbqd")
    rotatable = set("80oOxXIl").union(mistakable)
    return chars.issubset(rotatable) and not chars.isdisjoint(mistakable)


def pairs(sequence):
    """Generate consecutive pairs throughout the given sequence; at last, it gives elements last, first."""
    i = iter(sequence)
    previous = first = next(i)
    for this in i:
        yield previous, this
        previous = this
    yield this, first


def argmax_pair(array, key):
    """Find an (unordered) pair of indices that maximize the given function"""
    n = len(array)
    mi, mj, m = None, None, None
    for i in range(n):
        for j in range(i+1, n):
            k = key(array[i], array[j])
            if not m or k > m:
                mi, mj, m = i, j, k
    return mi, mj


def fitting_matrix(v1, v2):
    """Get a matrix that rotates v1 to the same direction as v2"""
    return (1 / v1.length_squared) * M.Matrix((
        (v1.x*v2.x + v1.y*v2.y, v1.y*v2.x - v1.x*v2.y),
        (v1.x*v2.y - v1.y*v2.x, v1.x*v2.x + v1.y*v2.y)))


def z_up_matrix(n):
    """Get a rotation matrix that aligns given vector upwards."""
    b = n.xy.length
    s = n.length
    if b > 0:
        return M.Matrix((
            (n.x*n.z/(b*s), n.y*n.z/(b*s), -b/s),
            (-n.y/b, n.x/b, 0),
            (0, 0, 0)
        ))
    else:
        # no need for rotation
        return M.Matrix((
            (1, 0, 0),
            (0, (-1 if n.z < 0 else 1), 0),
            (0, 0, 0)
        ))


def create_blank_image(image_name, dimensions, alpha=1):
    """Create a new image and assign white color to all its pixels"""
    image_name = image_name[:64]
    width, height = int(dimensions.x), int(dimensions.y)
    image = bpy.data.images.new(image_name, width, height, alpha=True)
    if image.users > 0:
        raise UnfoldError(
            "There is something wrong with the material of the model. "
            "Please report this on the BlenderArtists forum. Export failed.")
    image.pixels = [1, 1, 1, alpha] * (width * height)
    image.file_format = 'PNG'
    return image


def bake(face_indices, uvmap, image):
    import bpy
    is_cycles = (bpy.context.scene.render.engine == 'CYCLES')
    if is_cycles:
        # please excuse the following mess. Cycles baking API does not seem to allow better.
        ob = bpy.context.active_object
        me = ob.data
        # add a disconnected image node that defines the bake target
        temp_nodes = dict()
        for mat in me.materials:
            mat.use_nodes = True
            img = mat.node_tree.nodes.new('ShaderNodeTexImage')
            img.image = image
            temp_nodes[mat] = img
            mat.node_tree.nodes.active = img
            uvmap.active = True
        # move all excess faces to negative numbers (that is the only way to disable them)
        loop = me.uv_layers[me.uv_layers.active_index].data
        face_indices = set(face_indices)
        ignored_uvs = [
            face.loop_start + i
            for face in me.polygons if face.index not in face_indices
            for i, v in enumerate(face.vertices)]
        for vid in ignored_uvs:
            loop[vid].uv *= -1
        bake_type = bpy.context.scene.cycles.bake_type
        sta = bpy.context.scene.render.bake.use_selected_to_active
        try:
            bpy.ops.object.bake(type=bake_type, margin=0, use_selected_to_active=sta, cage_extrusion=100, use_clear=False)
        except RuntimeError as e:
            raise UnfoldError(*e.args)
        finally:
            for mat, node in temp_nodes.items():
                mat.node_tree.nodes.remove(node)
        for vid in ignored_uvs:
            loop[vid].uv *= -1
    else:
        texfaces = uvmap.data
        for fid in face_indices:
            texfaces[fid].image = image
        bpy.ops.object.bake_image()
        for fid in face_indices:
            texfaces[fid].image = None


class UnfoldError(ValueError):
    pass


class Unfolder:
    def __init__(self, ob):
        self.ob = ob
        self.mesh = Mesh(ob.data, ob.matrix_world)
        self.mesh.check_correct()
        self.tex = None

    def prepare(self, cage_size=None, create_uvmap=False, mark_seams=False, priority_effect=default_priority_effect, scale=1):
        """Create the islands of the net"""
        self.mesh.generate_cuts(cage_size / scale if cage_size else None, priority_effect)
        is_landscape = cage_size and cage_size.x > cage_size.y
        self.mesh.finalize_islands(is_landscape)
        self.mesh.enumerate_islands()
        if create_uvmap:
            self.tex = self.mesh.save_uv()
        if mark_seams:
            self.mesh.mark_cuts()

    def copy_island_names(self, island_list):
        """Copy island label and abbreviation from the best matching island in the list"""
        orig_islands = [{face.id for face in item.faces} for item in island_list]
        matching = list()
        for i, island in enumerate(self.mesh.islands):
            islfaces = {uvface.face.index for uvface in island.faces}
            matching.extend((len(islfaces.intersection(item)), i, j) for j, item in enumerate(orig_islands))
        matching.sort(reverse=True)
        available_new = [True for island in self.mesh.islands]
        available_orig = [True for item in island_list]
        for face_count, i, j in matching:
            if available_new[i] and available_orig[j]:
                available_new[i] = available_orig[j] = False
                self.mesh.islands[i].label = island_list[j].label
                self.mesh.islands[i].abbreviation = island_list[j].abbreviation

    def save(self, properties):
        """Export the document"""
        # Note about scale: input is directly in blender length
        # Mesh.scale_islands multiplies everything by a user-defined ratio
        # exporters (SVG or PDF) multiply everything by 1000 (output in millimeters)
        Exporter = SVG if properties.file_format == 'SVG' else PDF
        filepath = properties.filepath
        extension = properties.file_format.lower()
        filepath = bpy.path.ensure_ext(filepath, "." + extension)
        # page size in meters
        page_size = M.Vector((properties.output_size_x, properties.output_size_y))
        # printable area size in meters
        printable_size = page_size - 2 * properties.output_margin * M.Vector((1, 1))
        unit_scale = bpy.context.scene.unit_settings.scale_length
        ppm = properties.output_dpi * 100 / 2.54  # pixels per meter

        # after this call, all dimensions will be in meters
        self.mesh.scale_islands(unit_scale/properties.scale)
        if properties.do_create_stickers:
            self.mesh.generate_stickers(properties.sticker_width, properties.do_create_numbers)
        elif properties.do_create_numbers:
            self.mesh.generate_numbers_alone(properties.sticker_width)

        text_height = properties.sticker_width if (properties.do_create_numbers and len(self.mesh.islands) > 1) else 0
        aspect_ratio = printable_size.x / printable_size.y
        # title height must be somewhat larger that text size, glyphs go below the baseline
        self.mesh.finalize_islands(is_landscape=(printable_size.x > printable_size.y), title_height=text_height * 1.2)
        self.mesh.fit_islands(cage_size=printable_size)

        if properties.output_type != 'NONE':
            # bake an image and save it as a PNG to disk or into memory
            image_packing = properties.image_packing if properties.file_format == 'SVG' else 'ISLAND_EMBED'
            use_separate_images = image_packing in ('ISLAND_LINK', 'ISLAND_EMBED')
            tex = self.mesh.save_uv(cage_size=printable_size, separate_image=use_separate_images, tex=self.tex)
            if not tex:
                raise UnfoldError("The mesh has no UV Map slots left. Either delete a UV Map or export the net without textures.")

            sce = bpy.context.scene
            rd = sce.render
            bk = rd.bake
            if rd.engine == 'CYCLES':
                recall = sce.cycles.bake_type, bk.use_selected_to_active, bk.margin, bk.cage_extrusion, bk.use_cage, bk.use_clear, bk.use_pass_direct, bk.use_pass_indirect
                # recall use_pass...
                lookup = {'TEXTURE': 'DIFFUSE', 'AMBIENT_OCCLUSION': 'AO', 'RENDER': 'COMBINED', 'SELECTED_TO_ACTIVE': 'COMBINED'}
                sce.cycles.bake_type = lookup[properties.output_type]
                bk.use_pass_direct = bk.use_pass_indirect = (properties.output_type != 'TEXTURE')
                bk.use_selected_to_active = (properties.output_type == 'SELECTED_TO_ACTIVE')
                bk.margin, bk.cage_extrusion, bk.use_cage, bk.use_clear = 0, 10, False, False
            else:
                recall = rd.engine, rd.bake_type, rd.use_bake_to_vertex_color, rd.use_bake_selected_to_active, rd.bake_distance, rd.bake_bias, rd.bake_margin, rd.use_bake_clear
                rd.engine = 'BLENDER_RENDER'
                lookup = {'TEXTURE': 'TEXTURE', 'AMBIENT_OCCLUSION': 'AO', 'RENDER': 'FULL', 'SELECTED_TO_ACTIVE': 'FULL'}
                rd.bake_type = lookup[properties.output_type]
                rd.use_bake_selected_to_active = (properties.output_type == 'SELECTED_TO_ACTIVE')
                rd.bake_margin, rd.bake_distance, rd.bake_bias, rd.use_bake_to_vertex_color, rd.use_bake_clear = 0, 0, 0.001, False, False

            if image_packing == 'PAGE_LINK':
                self.mesh.save_image(tex, printable_size * ppm, filepath)
            elif image_packing == 'ISLAND_LINK':
                image_dir = filepath[:filepath.rfind(".")]
                self.mesh.save_separate_images(tex, ppm, image_dir)
            elif image_packing == 'ISLAND_EMBED':
                self.mesh.save_separate_images(tex, ppm, filepath, embed=Exporter.encode_image)

            # revoke settings
            if rd.engine == 'CYCLES':
                sce.cycles.bake_type, bk.use_selected_to_active, bk.margin, bk.cage_extrusion, bk.use_cage, bk.use_clear, bk.use_pass_direct, bk.use_pass_indirect = recall
            else:
                rd.engine, rd.bake_type, rd.use_bake_to_vertex_color, rd.use_bake_selected_to_active, rd.bake_distance, rd.bake_bias, rd.bake_margin, rd.use_bake_clear = recall
            if not properties.do_create_uvmap:
                tex.active = True
                bpy.ops.mesh.uv_texture_remove()

        exporter = Exporter(page_size, properties.style, properties.output_margin, (properties.output_type == 'NONE'), properties.angle_epsilon)
        exporter.do_create_stickers = properties.do_create_stickers
        exporter.text_size = properties.sticker_width
        exporter.write(self.mesh, filepath)


class Mesh:
    """Wrapper for Bpy Mesh"""

    def __init__(self, mesh, matrix):
        self.vertices = dict()
        self.edges = dict()
        self.edges_by_verts_indices = dict()
        self.faces = dict()
        self.islands = list()
        self.data = mesh
        self.pages = list()
        for bpy_vertex in mesh.vertices:
            self.vertices[bpy_vertex.index] = Vertex(bpy_vertex, matrix)
        for bpy_edge in mesh.edges:
            edge = Edge(bpy_edge, self, matrix)
            self.edges[bpy_edge.index] = edge
            self.edges_by_verts_indices[(edge.va.index, edge.vb.index)] = edge
            self.edges_by_verts_indices[(edge.vb.index, edge.va.index)] = edge
        for bpy_face in mesh.polygons:
            face = Face(bpy_face, self)
            self.faces[bpy_face.index] = face
        for edge in self.edges.values():
            edge.choose_main_faces()
            if edge.main_faces:
                edge.calculate_angle()

    def check_correct(self, epsilon=1e-6):
        """Check for invalid geometry"""
        null_edges = {i for i, e in self.edges.items() if e.vector.length < epsilon and e.faces}
        null_faces = {i for i, f in self.faces.items() if f.normal.length_squared < epsilon}
        twisted_faces = {i for i, f in self.faces.items() if f.is_twisted()}
        if not (null_edges or null_faces or twisted_faces):
            return
        bpy.context.tool_settings.mesh_select_mode = False, bool(null_edges), bool(null_faces or twisted_faces)
        for vertex in self.data.vertices:
            vertex.select = False
        for edge in self.data.edges:
            edge.select = (edge.index in null_edges)
        for face in self.data.polygons:
            face.select = (face.index in null_faces or face.index in twisted_faces)
        cure = ("Remove Doubles and Triangulate" if (null_edges or null_faces) and twisted_faces
            else "Triangulate" if twisted_faces
            else "Remove Doubles")
        raise UnfoldError(
            "The model contains:\n" +
            (" {} zero-length edge(s)\n".format(len(null_edges)) if null_edges else "") +
            (" {} zero-area face(s)\n".format(len(null_faces)) if null_faces else "") +
            (" {} twisted polygon(s)\n".format(len(twisted_faces)) if twisted_faces else "") +
            "The offenders are selected and you can use {} to fix them. Export failed.".format(cure))

    def generate_cuts(self, page_size, priority_effect):
        """Cut the mesh so that it can be unfolded to a flat net."""
        # warning: this constructor modifies its parameter (face)
        islands = {Island(face) for face in self.faces.values()}
        # check for edges that are cut permanently
        edges = [edge for edge in self.edges.values() if not edge.force_cut and len(edge.faces) > 1]

        if edges:
            average_length = sum(edge.vector.length for edge in edges) / len(edges)
            for edge in edges:
                edge.generate_priority(priority_effect, average_length)
            edges.sort(reverse=False, key=lambda edge: edge.priority)
            for edge in edges:
                if edge.vector.length_squared == 0:
                    continue
                face_a, face_b = edge.main_faces
                island_a, island_b = face_a.uvface.island, face_b.uvface.island
                if island_a is not island_b:
                    if len(island_b.faces) > len(island_a.faces):
                        island_a, island_b = island_b, island_a
                    if island_a.join(island_b, edge, size_limit=page_size):
                        islands.remove(island_b)

        self.islands = sorted(islands, reverse=True, key=lambda island: len(island.faces))

        for edge in self.edges.values():
            # some edges did not know until now whether their angle is convex or concave
            if edge.main_faces and (edge.main_faces[0].uvface.flipped or edge.main_faces[1].uvface.flipped):
                edge.calculate_angle()
            # ensure that the order of faces corresponds to the order of uvedges
            if edge.main_faces:
                reordered = [None, None]
                for uvedge in edge.uvedges:
                    try:
                        index = edge.main_faces.index(uvedge.uvface.face)
                        reordered[index] = uvedge
                    except ValueError:
                        reordered.append(uvedge)
                edge.uvedges = reordered

        for island in self.islands:
            # if the normals are ambiguous, flip them so that there are more convex edges than concave ones
            if any(uvface.flipped for uvface in island.faces):
                island_edges = {uvedge.edge for uvedge in island.edges if not uvedge.edge.is_cut(uvedge.uvface.face)}
                balance = sum((+1 if edge.angle > 0 else -1) for edge in island_edges)
                if balance < 0:
                    island.is_inside_out = True

            # construct a linked list from each island's boundary
            # uvedge.neighbor_right is clockwise = forward = via uvedge.vb if not uvface.flipped
            neighbor_lookup, conflicts = dict(), dict()
            for uvedge in island.boundary:
                uvvertex = uvedge.va if uvedge.uvface.flipped else uvedge.vb
                if uvvertex not in neighbor_lookup:
                    neighbor_lookup[uvvertex] = uvedge
                else:
                    if uvvertex not in conflicts:
                        conflicts[uvvertex] = [neighbor_lookup[uvvertex], uvedge]
                    else:
                        conflicts[uvvertex].append(uvedge)

            for uvedge in island.boundary:
                uvvertex = uvedge.vb if uvedge.uvface.flipped else uvedge.va
                if uvvertex not in conflicts:
                    # using the 'get' method so as to handle single-connected vertices properly
                    uvedge.neighbor_right = neighbor_lookup.get(uvvertex, uvedge)
                    uvedge.neighbor_right.neighbor_left = uvedge
                else:
                    conflicts[uvvertex].append(uvedge)

            # resolve merged vertices with more boundaries crossing
            def direction_to_float(vector):
                return (1 - vector.x/vector.length) if vector.y > 0 else (vector.x/vector.length - 1)
            for uvvertex, uvedges in conflicts.items():
                def is_inwards(uvedge):
                    return uvedge.uvface.flipped == (uvedge.va is uvvertex)

                def uvedge_sortkey(uvedge):
                    if is_inwards(uvedge):
                        return direction_to_float(uvedge.va.co - uvedge.vb.co)
                    else:
                        return direction_to_float(uvedge.vb.co - uvedge.va.co)

                uvedges.sort(key=uvedge_sortkey)
                for right, left in (
                        zip(uvedges[:-1:2], uvedges[1::2]) if is_inwards(uvedges[0])
                        else zip([uvedges[-1]] + uvedges[1::2], uvedges[:-1:2])):
                    left.neighbor_right = right
                    right.neighbor_left = left
        return True

    def mark_cuts(self):
        """Mark cut edges in the original mesh so that the user can see"""
        for bpy_edge in self.data.edges:
            edge = self.edges[bpy_edge.index]
            bpy_edge.use_seam = len(edge.uvedges) > 1 and edge.is_main_cut

    def generate_stickers(self, default_width, do_create_numbers=True):
        """Add sticker faces where they are needed."""
        def uvedge_priority(uvedge):
            """Returns whether it is a good idea to stick something on this edge's face"""
            # TODO: it should take into account overlaps with faces and with other stickers
            return uvedge.uvface.face.area / sum((vb.co - va.co).length for (va, vb) in pairs(uvedge.uvface.vertices))

        def add_sticker(uvedge, index, target_island):
            uvedge.sticker = Sticker(uvedge, default_width, index, target_island)
            uvedge.island.add_marker(uvedge.sticker)

        for edge in self.edges.values():
            if edge.is_main_cut and len(edge.uvedges) >= 2 and edge.vector.length_squared > 0:
                uvedge_a, uvedge_b = edge.uvedges[:2]
                if uvedge_priority(uvedge_a) < uvedge_priority(uvedge_b):
                    uvedge_a, uvedge_b = uvedge_b, uvedge_a
                target_island = uvedge_a.island
                left_edge, right_edge = uvedge_a.neighbor_left.edge, uvedge_a.neighbor_right.edge
                if do_create_numbers:
                    for uvedge in [uvedge_b] + edge.uvedges[2:]:
                        if ((uvedge.neighbor_left.edge is not right_edge or uvedge.neighbor_right.edge is not left_edge) and
                                uvedge not in (uvedge_a.neighbor_left, uvedge_a.neighbor_right)):
                            # it will not be clear to see that these uvedges should be sticked together
                            # So, create an arrow and put the index on all stickers
                            target_island.sticker_numbering += 1
                            index = str(target_island.sticker_numbering)
                            if is_upsidedown_wrong(index):
                                index += "."
                            target_island.add_marker(Arrow(uvedge_a, default_width, index))
                            break
                    else:
                        # if all uvedges to be sticked are easy to see, create no numbers
                        index = None
                else:
                    index = None
                add_sticker(uvedge_b, index, target_island)
            elif len(edge.uvedges) > 2:
                index = None
                target_island = edge.uvedges[0].island
            if len(edge.uvedges) > 2:
                for uvedge in edge.uvedges[2:]:
                    add_sticker(uvedge, index, target_island)

    def generate_numbers_alone(self, size):
        global_numbering = 0
        for edge in self.edges.values():
            if edge.is_main_cut and len(edge.uvedges) >= 2:
                global_numbering += 1
                index = str(global_numbering)
                if is_upsidedown_wrong(index):
                    index += "."
                for uvedge in edge.uvedges:
                    uvedge.island.add_marker(NumberAlone(uvedge, index, size))

    def enumerate_islands(self):
        for num, island in enumerate(self.islands, 1):
            island.number = num
            island.generate_label()

    def scale_islands(self, scale):
        for island in self.islands:
            for point in chain((vertex.co for vertex in island.vertices), island.fake_vertices):
                point *= scale

    def finalize_islands(self, is_landscape=False, title_height=0):
        for island in self.islands:
            if title_height:
                island.title = "[{}] {}".format(island.abbreviation, island.label)
            points = list(vertex.co for vertex in island.vertices) + island.fake_vertices
            angle = M.geometry.box_fit_2d(points)
            rot = M.Matrix.Rotation(angle, 2)
            # ensure that the island matches page orientation (portrait/landscape)
            dimensions = M.Vector(max(r * v for v in points) - min(r * v for v in points) for r in rot)
            if dimensions.x > dimensions.y != is_landscape:
                rot = M.Matrix.Rotation(angle + pi / 2, 2)
            for point in points:
                # note: we need an in-place operation, and Vector.rotate() seems to work for 3d vectors only
                point[:] = rot * point
            for marker in island.markers:
                marker.rot = rot * marker.rot
            bottom_left = M.Vector((min(v.x for v in points), min(v.y for v in points) - title_height))
            for point in points:
                point -= bottom_left
            island.bounding_box = M.Vector((max(v.x for v in points), max(v.y for v in points)))

    def largest_island_ratio(self, page_size):
        return max(i / p for island in self.islands for (i, p) in zip(island.bounding_box, page_size))

    def fit_islands(self, cage_size):
        """Move islands so that they fit onto pages, based on their bounding boxes"""

        def try_emplace(island, page_islands, cage_size, stops_x, stops_y, occupied_cache):
            """Tries to put island to each pair from stops_x, stops_y
            and checks if it overlaps with any islands present on the page.
            Returns True and positions the given island on success."""
            bbox_x, bbox_y = island.bounding_box.xy
            for x in stops_x:
                if x + bbox_x > cage_size.x:
                    continue
                for y in stops_y:
                    if y + bbox_y > cage_size.y or (x, y) in occupied_cache:
                        continue
                    for i, obstacle in enumerate(page_islands):
                        # if this obstacle overlaps with the island, try another stop
                        if (x + bbox_x > obstacle.pos.x and
                                obstacle.pos.x + obstacle.bounding_box.x > x and
                                y + bbox_y > obstacle.pos.y and
                                obstacle.pos.y + obstacle.bounding_box.y > y):
                            if x >= obstacle.pos.x and y >= obstacle.pos.y:
                                occupied_cache.add((x, y))
                            # just a stupid heuristic to make subsequent searches faster
                            if i > 0:
                                page_islands[1:i+1] = page_islands[:i]
                                page_islands[0] = obstacle
                            break
                    else:
                        # if no obstacle called break, this position is okay
                        island.pos.xy = x, y
                        page_islands.append(island)
                        stops_x.append(x + bbox_x)
                        stops_y.append(y + bbox_y)
                        return True
            return False

        def drop_portion(stops, border, divisor):
            stops.sort()
            # distance from left neighbor to the right one, excluding the first stop
            distances = [right - left for left, right in zip(stops, chain(stops[2:], [border]))]
            quantile = sorted(distances)[len(distances) // divisor]
            return [stop for stop, distance in zip(stops, chain([quantile], distances)) if distance >= quantile]

        if any(island.bounding_box.x > cage_size.x or island.bounding_box.y > cage_size.y for island in self.islands):
            raise UnfoldError(
                "An island is too big to fit onto page of the given size. "
                "Either downscale the model or find and split that island manually.\n"
                "Export failed, sorry.")
        # sort islands by their diagonal... just a guess
        remaining_islands = sorted(self.islands, reverse=True, key=lambda island: island.bounding_box.length_squared)
        page_num = 1

        while remaining_islands:
            # create a new page and try to fit as many islands onto it as possible
            page = Page(page_num)
            page_num += 1
            occupied_cache = set()
            stops_x, stops_y = [0], [0]
            for island in remaining_islands:
                try_emplace(island, page.islands, cage_size, stops_x, stops_y, occupied_cache)
                # if overwhelmed with stops, drop a quarter of them
                if len(stops_x)**2 > 4 * len(self.islands) + 100:
                    stops_x = drop_portion(stops_x, cage_size.x, 4)
                    stops_y = drop_portion(stops_y, cage_size.y, 4)
            remaining_islands = [island for island in remaining_islands if island not in page.islands]
            self.pages.append(page)

    def save_uv(self, cage_size=M.Vector((1, 1)), separate_image=False, tex=None):
        # TODO: mode switching should be handled by higher-level code
        bpy.ops.object.mode_set()
        # note: assuming that the active object's data is self.mesh
        if not tex:
            tex = self.data.uv_textures.new()
            if not tex:
                return None
        tex.name = "Unfolded"
        tex.active = True
        # TODO: this is somewhat dirty, but I do not see a nicer way in the API
        loop = self.data.uv_layers[self.data.uv_layers.active_index]
        if separate_image:
            for island in self.islands:
                island.save_uv_separate(loop)
        else:
            for island in self.islands:
                island.save_uv(loop, cage_size)
        return tex

    def save_image(self, tex, page_size_pixels: M.Vector, filename):
        for page in self.pages:
            image = create_blank_image("{} {} Unfolded".format(self.data.name[:14], page.name), page_size_pixels, alpha=1)
            image.filepath_raw = page.image_path = "{}_{}.png".format(filename, page.name)
            faces = [uvface.face.index for island in page.islands for uvface in island.faces]
            bake(faces, tex, image)
            image.save()
            image.user_clear()
            bpy.data.images.remove(image)

    def save_separate_images(self, tex, scale, filepath, embed=None):
        # omitting this may cause a "Circular reference in texture stack" error
        recall = {texface: texface.image for texface in tex.data}
        for texface in tex.data:
            texface.image = None
        for i, island in enumerate(self.islands, 1):
            image_name = "{} isl{}".format(self.data.name[:15], i)
            image = create_blank_image(image_name, island.bounding_box * scale, alpha=0)
            bake([uvface.face.index for uvface in island.faces], tex, image)
            if embed:
                island.embedded_image = embed(image)
            else:
                from os import makedirs
                image_dir = filepath
                makedirs(image_dir, exist_ok=True)
                image_path = os_path.join(image_dir, "island{}.png".format(i))
                image.filepath_raw = image_path
                image.save()
                island.image_path = image_path
            image.user_clear()
            bpy.data.images.remove(image)
        for texface, img in recall.items():
            texface.image = img


class Vertex:
    """BPy Vertex wrapper"""
    __slots__ = ('index', 'co', 'edges', 'uvs')

    def __init__(self, bpy_vertex, matrix):
        self.index = bpy_vertex.index
        self.co = matrix * bpy_vertex.co
        self.edges = list()
        self.uvs = list()

    def __hash__(self):
        return hash(self.index)

    def __eq__(self, other):
        return self.index == other.index


class Edge:
    """Wrapper for BPy Edge"""
    __slots__ = ('va', 'vb', 'faces', 'main_faces', 'uvedges',
        'vector', 'angle',
        'is_main_cut', 'force_cut', 'priority', 'freestyle')

    def __init__(self, edge, mesh, matrix=1):
        self.va = mesh.vertices[edge.vertices[0]]
        self.vb = mesh.vertices[edge.vertices[1]]
        self.vector = self.vb.co - self.va.co
        self.faces = list()
        # if self.main_faces is set, then self.uvedges[:2] must correspond to self.main_faces, in their order
        # this constraint is assured at the time of finishing mesh.generate_cuts
        self.uvedges = list()

        self.force_cut = edge.use_seam  # such edges will always be cut
        self.main_faces = None  # two faces that may be connected in the island
        # is_main_cut defines whether the two main faces are connected
        # all the others will be assumed to be cut
        self.is_main_cut = True
        self.priority = None
        self.angle = None
        self.freestyle = getattr(edge, "use_freestyle_mark", False)  # freestyle edges will be highlighted
        self.va.edges.append(self)  # FIXME: editing foreign attribute
        self.vb.edges.append(self)  # FIXME: editing foreign attribute

    def choose_main_faces(self):
        """Choose two main faces that might get connected in an island"""
        if len(self.faces) == 2:
            self.main_faces = self.faces
        elif len(self.faces) > 2:
            # find (with brute force) the pair of indices whose faces have the most similar normals
            i, j = argmax_pair(self.faces, key=lambda a, b: abs(a.normal.dot(b.normal)))
            self.main_faces = [self.faces[i], self.faces[j]]

    def calculate_angle(self):
        """Calculate the angle between the main faces"""
        face_a, face_b = self.main_faces
        if face_a.normal.length_squared == 0 or face_b.normal.length_squared == 0:
            self.angle = -3  # just a very sharp angle
            return
        # correction if normals are flipped
        a_is_clockwise = ((face_a.vertices.index(self.va) - face_a.vertices.index(self.vb)) % len(face_a.vertices) == 1)
        b_is_clockwise = ((face_b.vertices.index(self.va) - face_b.vertices.index(self.vb)) % len(face_b.vertices) == 1)
        is_equal_flip = True
        if face_a.uvface and face_b.uvface:
            a_is_clockwise ^= face_a.uvface.flipped
            b_is_clockwise ^= face_b.uvface.flipped
            is_equal_flip = (face_a.uvface.flipped == face_b.uvface.flipped)
            # TODO: maybe this need not be true in _really_ ugly cases: assert(a_is_clockwise != b_is_clockwise)
        if a_is_clockwise != b_is_clockwise:
            if (a_is_clockwise == (face_b.normal.cross(face_a.normal).dot(self.vector) > 0)) == is_equal_flip:
                # the angle is convex
                self.angle = face_a.normal.angle(face_b.normal)
            else:
                # the angle is concave
                self.angle = -face_a.normal.angle(face_b.normal)
        else:
            # normals are flipped, so we know nothing
            # so let us assume the angle be convex
            self.angle = face_a.normal.angle(-face_b.normal)

    def generate_priority(self, priority_effect, average_length):
        """Calculate the priority value for cutting"""
        angle = self.angle
        if angle > 0:
            self.priority = priority_effect['CONVEX'] * angle / pi
        else:
            self.priority = priority_effect['CONCAVE'] * (-angle) / pi
        self.priority += (self.vector.length / average_length) * priority_effect['LENGTH']

    def is_cut(self, face):
        """Return False if this edge will the given face to another one in the resulting net
        (useful for edges with more than two faces connected)"""
        # Return whether there is a cut between the two main faces
        if self.main_faces and face in self.main_faces:
            return self.is_main_cut
        # All other faces (third and more) are automatically treated as cut
        else:
            return True

    def other_uvedge(self, this):
        """Get an uvedge of this edge that is not the given one
        causes an IndexError if case of less than two adjacent edges"""
        return self.uvedges[1] if this is self.uvedges[0] else self.uvedges[0]


class Face:
    """Wrapper for BPy Face"""
    __slots__ = ('index', 'edges', 'vertices', 'uvface',
        'loop_start', 'area', 'normal')

    def __init__(self, bpy_face, mesh):
        self.index = bpy_face.index
        self.edges = list()
        self.vertices = [mesh.vertices[i] for i in bpy_face.vertices]
        self.loop_start = bpy_face.loop_start
        self.area = bpy_face.area
        self.uvface = None
        self.normal = M.geometry.normal(v.co for v in self.vertices)
        for verts_indices in bpy_face.edge_keys:
            edge = mesh.edges_by_verts_indices[verts_indices]
            self.edges.append(edge)
            edge.faces.append(self)  # FIXME: editing foreign attribute

    def is_twisted(self):
        if len(self.vertices) > 3:
            center = sum((vertex.co for vertex in self.vertices), M.Vector((0, 0, 0))) / len(self.vertices)
            plane_d = center.dot(self.normal)
            diameter = max((center - vertex.co).length for vertex in self.vertices)
            for vertex in self.vertices:
                # check coplanarity
                if abs(vertex.co.dot(self.normal) - plane_d) > diameter * 0.01:
                    return True
        return False

    def __hash__(self):
        return hash(self.index)


class Island:
    """Part of the net to be exported"""
    __slots__ = ('faces', 'edges', 'vertices', 'fake_vertices', 'uvverts_by_id', 'boundary', 'markers',
        'pos', 'bounding_box',
        'image_path', 'embedded_image',
        'number', 'label', 'abbreviation', 'title',
        'has_safe_geometry', 'is_inside_out',
        'sticker_numbering')

    def __init__(self, face):
        """Create an Island from a single Face"""
        self.faces = list()
        self.edges = set()
        self.vertices = set()
        self.fake_vertices = list()
        self.markers = list()
        self.label = None
        self.abbreviation = None
        self.title = None
        self.pos = M.Vector((0, 0))
        self.image_path = None
        self.embedded_image = None
        self.is_inside_out = False  # swaps concave <-> convex edges
        self.has_safe_geometry = True
        self.sticker_numbering = 0
        uvface = UVFace(face, self)
        self.vertices.update(uvface.vertices)
        self.edges.update(uvface.edges)
        self.faces.append(uvface)
        # speedup for Island.join
        self.uvverts_by_id = {uvvertex.vertex.index: [uvvertex] for uvvertex in self.vertices}
        # UVEdges on the boundary
        self.boundary = list(self.edges)

    def join(self, other, edge: Edge, size_limit=None, epsilon=1e-6) -> bool:
        """
        Try to join other island on given edge
        Returns False if they would overlap
        """

        class Intersection(Exception):
            pass

        class GeometryError(Exception):
            pass

        def is_below(self, other, correct_geometry=True):
            if self is other:
                return False
            if self.top < other.bottom:
                return True
            if other.top < self.bottom:
                return False
            if self.max.tup <= other.min.tup:
                return True
            if other.max.tup <= self.min.tup:
                return False
            self_vector = self.max.co - self.min.co
            min_to_min = other.min.co - self.min.co
            cross_b1 = self_vector.cross(min_to_min)
            cross_b2 = self_vector.cross(other.max.co - self.min.co)
            if cross_b2 < cross_b1:
                cross_b1, cross_b2 = cross_b2, cross_b1
            if cross_b2 > 0 and (cross_b1 > 0 or (cross_b1 == 0 and not self.is_uvface_upwards())):
                return True
            if cross_b1 < 0 and (cross_b2 < 0 or (cross_b2 == 0 and self.is_uvface_upwards())):
                return False
            other_vector = other.max.co - other.min.co
            cross_a1 = other_vector.cross(-min_to_min)
            cross_a2 = other_vector.cross(self.max.co - other.min.co)
            if cross_a2 < cross_a1:
                cross_a1, cross_a2 = cross_a2, cross_a1
            if cross_a2 > 0 and (cross_a1 > 0 or (cross_a1 == 0 and not other.is_uvface_upwards())):
                return False
            if cross_a1 < 0 and (cross_a2 < 0 or (cross_a2 == 0 and other.is_uvface_upwards())):
                return True
            if cross_a1 == cross_b1 == cross_a2 == cross_b2 == 0:
                if correct_geometry:
                    raise GeometryError
                elif self.is_uvface_upwards() == other.is_uvface_upwards():
                    raise Intersection
                return False
            if self.min.tup == other.min.tup or self.max.tup == other.max.tup:
                return cross_a2 > cross_b2
            raise Intersection

        class QuickSweepline:
            """Efficient sweepline based on binary search, checking neighbors only"""
            def __init__(self):
                self.children = blist()

            def add(self, item, cmp=is_below):
                low, high = 0, len(self.children)
                while low < high:
                    mid = (low + high) // 2
                    if cmp(self.children[mid], item):
                        low = mid + 1
                    else:
                        high = mid
                self.children.insert(low, item)

            def remove(self, item, cmp=is_below):
                index = self.children.index(item)
                self.children.pop(index)
                if index > 0 and index < len(self.children):
                    # check for intersection
                    if cmp(self.children[index], self.children[index-1]):
                        raise GeometryError

        class BruteSweepline:
            """Safe sweepline which checks all its members pairwise"""
            def __init__(self):
                self.children = set()
                self.last_min = None, []
                self.last_max = None, []

            def add(self, item, cmp=is_below):
                for child in self.children:
                    if child.min is not item.min and child.max is not item.max:
                        cmp(item, child, False)
                self.children.add(item)

            def remove(self, item):
                self.children.remove(item)

        def sweep(sweepline, segments):
            """Sweep across the segments and raise an exception if necessary"""
            # careful, 'segments' may be a use-once iterator
            events_add = sorted(segments, reverse=True, key=lambda uvedge: uvedge.min.tup)
            events_remove = sorted(events_add, reverse=True, key=lambda uvedge: uvedge.max.tup)
            while events_remove:
                while events_add and events_add[-1].min.tup <= events_remove[-1].max.tup:
                    sweepline.add(events_add.pop())
                sweepline.remove(events_remove.pop())

        def root_find(value, tree):
            """Find the root of a given value in a forest-like dictionary
            also updates the dictionary using path compression"""
            parent, relink = tree.get(value), list()
            while parent is not None:
                relink.append(value)
                value, parent = parent, tree.get(parent)
            tree.update(dict.fromkeys(relink, value))
            return value

        def slope_from(position):
            def slope(uvedge):
                vec = (uvedge.vb.co - uvedge.va.co) if uvedge.va.tup == position else (uvedge.va.co - uvedge.vb.co)
                return (vec.y / vec.length + 1) if ((vec.x, vec.y) > (0, 0)) else (-1 - vec.y / vec.length)
            return slope

        # find edge in other and in self
        for uvedge in edge.uvedges:
            if uvedge.uvface.face in uvedge.edge.main_faces:
                if uvedge.uvface.island is self and uvedge in self.boundary:
                    uvedge_a = uvedge
                elif uvedge.uvface.island is other and uvedge in other.boundary:
                    uvedge_b = uvedge
                else:
                    return False

        # check if vertices and normals are aligned correctly
        verts_flipped = uvedge_b.va.vertex is uvedge_a.va.vertex
        flipped = verts_flipped ^ uvedge_a.uvface.flipped ^ uvedge_b.uvface.flipped
        # determine rotation
        # NOTE: if the edges differ in length, the matrix will involve uniform scaling.
        # Such situation may occur in the case of twisted n-gons
        first_b, second_b = (uvedge_b.va, uvedge_b.vb) if not verts_flipped else (uvedge_b.vb, uvedge_b.va)
        if not flipped:
            rot = fitting_matrix(first_b.co - second_b.co, uvedge_a.vb.co - uvedge_a.va.co)
        else:
            flip = M.Matrix(((-1, 0), (0, 1)))
            rot = fitting_matrix(flip * (first_b.co - second_b.co), uvedge_a.vb.co - uvedge_a.va.co) * flip
        trans = uvedge_a.vb.co - rot * first_b.co
        # extract and transform island_b's boundary
        phantoms = {uvvertex: UVVertex(rot*uvvertex.co + trans, uvvertex.vertex) for uvvertex in other.vertices}

        # check the size of the resulting island
        if size_limit:
            # first check: bounding box
            left = min(min(seg.min.co.x for seg in self.boundary), min(vertex.co.x for vertex in phantoms))
            right = max(max(seg.max.co.x for seg in self.boundary), max(vertex.co.x for vertex in phantoms))