Skip to content
Snippets Groups Projects
common.py 36.8 KiB
Newer Older
# SPDX-License-Identifier: GPL-2.0-or-later
Nutti's avatar
Nutti committed

# <pep8-80 compliant>
Nutti's avatar
Nutti committed

__author__ = "Nutti <nutti.metro@gmail.com>"
__status__ = "production"
nutti's avatar
nutti committed
__version__ = "6.5"
__date__ = "6 Mar 2021"
Nutti's avatar
Nutti committed

from collections import defaultdict
from pprint import pprint
from math import fabs, sqrt
Nutti's avatar
Nutti committed
import os
Nutti's avatar
Nutti committed

import bpy
from mathutils import Vector
import bmesh

from .utils import compatibility as compat
Nutti's avatar
Nutti committed

Nutti's avatar
Nutti committed


def is_console_mode():
    if "MUV_CONSOLE_MODE" not in os.environ:
        return False
Nutti's avatar
Nutti committed
    return os.environ["MUV_CONSOLE_MODE"] == "true"
nutti's avatar
nutti committed
def is_valid_space(context, allowed_spaces):
    for area in context.screen.areas:
        for space in area.spaces:
            if space.type in allowed_spaces:
                return True
    return False


Nutti's avatar
Nutti committed
def is_debug_mode():
    return __DEBUG_MODE


def enable_debugg_mode():
    # pylint: disable=W0603
    global __DEBUG_MODE
    __DEBUG_MODE = True


def disable_debug_mode():
    # pylint: disable=W0603
    global __DEBUG_MODE
    __DEBUG_MODE = False
Nutti's avatar
Nutti committed


def debug_print(*s):
    """
    Print message to console in debugging mode
    """

Nutti's avatar
Nutti committed
    if is_debug_mode():
Nutti's avatar
Nutti committed
        pprint(s)


def check_version(major, minor, _):
    """
    Check blender version
    """

    if bpy.app.version[0] == major and bpy.app.version[1] == minor:
        return 0
    if bpy.app.version[0] > major:
        return 1
    if bpy.app.version[1] > minor:
        return 1
    return -1


def redraw_all_areas():
    """
    Redraw all areas
    """

    for area in bpy.context.screen.areas:
        area.tag_redraw()


def get_space(area_type, region_type, space_type):
    """
    Get current area/region/space
    """

    area = None
    region = None
    space = None

    for area in bpy.context.screen.areas:
        if area.type == area_type:
            break
    else:
        return (None, None, None)
    for region in area.regions:
        if region.type == region_type:
            if compat.check_version(2, 80, 0) >= 0:
                if region.width <= 1 or region.height <= 1:
                    continue
Nutti's avatar
Nutti committed
            break
    else:
        return (area, None, None)
Nutti's avatar
Nutti committed
    for space in area.spaces:
        if space.type == space_type:
            break
    else:
        return (area, region, None)
Nutti's avatar
Nutti committed

    return (area, region, space)


Nutti's avatar
Nutti committed
def mouse_on_region(event, area_type, region_type):
    pos = Vector((event.mouse_x, event.mouse_y))

    _, region, _ = get_space(area_type, region_type, "")
    if region is None:
        return False

    if (pos.x > region.x) and (pos.x < region.x + region.width) and \
       (pos.y > region.y) and (pos.y < region.y + region.height):
        return True

    return False


def mouse_on_area(event, area_type):
    pos = Vector((event.mouse_x, event.mouse_y))

    area, _, _ = get_space(area_type, "", "")
    if area is None:
        return False

    if (pos.x > area.x) and (pos.x < area.x + area.width) and \
       (pos.y > area.y) and (pos.y < area.y + area.height):
        return True

    return False


def mouse_on_regions(event, area_type, regions):
    if not mouse_on_area(event, area_type):
        return False

    for region in regions:
        result = mouse_on_region(event, area_type, region)
        if result:
            return True

    return False


def create_bmesh(obj):
    bm = bmesh.from_edit_mesh(obj.data)
    if check_version(2, 73, 0) >= 0:
        bm.faces.ensure_lookup_table()

    return bm


def create_new_uv_map(obj, name=None):
    uv_maps_old = {l.name for l in obj.data.uv_layers}
    bpy.ops.mesh.uv_texture_add()
    uv_maps_new = {l.name for l in obj.data.uv_layers}
    diff = uv_maps_new - uv_maps_old

    if not list(diff):
        return None     # no more UV maps can not be created

    # rename UV map
    new = obj.data.uv_layers[list(diff)[0]]
    if name:
        new.name = name

    return new


Nutti's avatar
Nutti committed
def __get_island_info(uv_layer, islands):
    """
    get information about each island
    """

    island_info = []
    for isl in islands:
        info = {}
        max_uv = Vector((-10000000.0, -10000000.0))
        min_uv = Vector((10000000.0, 10000000.0))
        ave_uv = Vector((0.0, 0.0))
        num_uv = 0
        for face in isl:
            n = 0
            a = Vector((0.0, 0.0))
            ma = Vector((-10000000.0, -10000000.0))
            mi = Vector((10000000.0, 10000000.0))
            for l in face['face'].loops:
Nutti's avatar
Nutti committed
                uv = l[uv_layer].uv
                ma.x = max(uv.x, ma.x)
                ma.y = max(uv.y, ma.y)
                mi.x = min(uv.x, mi.x)
                mi.y = min(uv.y, mi.y)
                a = a + uv
                n = n + 1
            ave_uv = ave_uv + a
            num_uv = num_uv + n
            a = a / n
            max_uv.x = max(ma.x, max_uv.x)
            max_uv.y = max(ma.y, max_uv.y)
            min_uv.x = min(mi.x, min_uv.x)
            min_uv.y = min(mi.y, min_uv.y)
            face['max_uv'] = ma
            face['min_uv'] = mi
            face['ave_uv'] = a
        ave_uv = ave_uv / num_uv

        info['center'] = ave_uv
        info['size'] = max_uv - min_uv
        info['num_uv'] = num_uv
        info['group'] = -1
        info['faces'] = isl
        info['max'] = max_uv
        info['min'] = min_uv

        island_info.append(info)

    return island_info


def __parse_island(bm, face_idx, faces_left, island,
                   face_to_verts, vert_to_faces):
    """
    Parse island
    """

nutti's avatar
nutti committed
    faces_to_parse = [face_idx]
    while faces_to_parse:
        fidx = faces_to_parse.pop(0)
        if fidx in faces_left:
            faces_left.remove(fidx)
            island.append({'face': bm.faces[fidx]})
            for v in face_to_verts[fidx]:
                connected_faces = vert_to_faces[v]
Nutti's avatar
Nutti committed
                for cf in connected_faces:
nutti's avatar
nutti committed
                    faces_to_parse.append(cf)
Nutti's avatar
Nutti committed


def __get_island(bm, face_to_verts, vert_to_faces):
    """
    Get island list
    """

    uv_island_lists = []
    faces_left = set(face_to_verts.keys())
    while faces_left:
        current_island = []
        face_idx = list(faces_left)[0]
        __parse_island(bm, face_idx, faces_left, current_island,
                       face_to_verts, vert_to_faces)
        uv_island_lists.append(current_island)

    return uv_island_lists


def __create_vert_face_db(faces, uv_layer):
    # create mesh database for all faces
    face_to_verts = defaultdict(set)
    vert_to_faces = defaultdict(set)
    for f in faces:
        for l in f.loops:
            id_ = l[uv_layer].uv.to_tuple(5), l.vert.index
            face_to_verts[f.index].add(id_)
            vert_to_faces[id_].add(f.index)

    return (face_to_verts, vert_to_faces)


def get_island_info(obj, only_selected=True):
    bm = bmesh.from_edit_mesh(obj.data)
    if check_version(2, 73, 0) >= 0:
        bm.faces.ensure_lookup_table()

    return get_island_info_from_bmesh(bm, only_selected)


def get_island_info_from_bmesh(bm, only_selected=True):
    if not bm.loops.layers.uv:
        return None
    uv_layer = bm.loops.layers.uv.verify()

    # create database
    if only_selected:
        selected_faces = [f for f in bm.faces if f.select]
    else:
        selected_faces = [f for f in bm.faces]

    return get_island_info_from_faces(bm, selected_faces, uv_layer)


def get_island_info_from_faces(bm, faces, uv_layer):
    ftv, vtf = __create_vert_face_db(faces, uv_layer)

    # Get island information
    uv_island_lists = __get_island(bm, ftv, vtf)
    island_info = __get_island_info(uv_layer, uv_island_lists)

    return island_info


def get_uvimg_editor_board_size(area):
    if area.spaces.active.image:
        return area.spaces.active.image.size

    return (255.0, 255.0)


nutti's avatar
nutti committed
def calc_tris_2d_area(points):
Nutti's avatar
Nutti committed
    area = 0.0
    for i, p1 in enumerate(points):
        p2 = points[(i + 1) % len(points)]
        v1 = p1 - points[0]
        v2 = p2 - points[0]
        a = v1.x * v2.y - v1.y * v2.x
        area = area + a

    return fabs(0.5 * area)


nutti's avatar
nutti committed
def calc_tris_3d_area(points):
Nutti's avatar
Nutti committed
    area = 0.0
    for i, p1 in enumerate(points):
        p2 = points[(i + 1) % len(points)]
        v1 = p1 - points[0]
        v2 = p2 - points[0]
        cx = v1.y * v2.z - v1.z * v2.y
        cy = v1.z * v2.x - v1.x * v2.z
        cz = v1.x * v2.y - v1.y * v2.x
        a = sqrt(cx * cx + cy * cy + cz * cz)
        area = area + a

    return 0.5 * area


nutti's avatar
nutti committed
def get_faces_list(bm, method, only_selected):
    faces_list = []
    if method == 'MESH':
        if only_selected:
            faces_list.append([f for f in bm.faces if f.select])
        else:
            faces_list.append([f for f in bm.faces])
    elif method == 'UV ISLAND':
        if not bm.loops.layers.uv:
            return None
        uv_layer = bm.loops.layers.uv.verify()
        if only_selected:
            faces = [f for f in bm.faces if f.select]
            islands = get_island_info_from_faces(bm, faces, uv_layer)
            for isl in islands:
                faces_list.append([f["face"] for f in isl["faces"]])
        else:
            faces = [f for f in bm.faces]
            islands = get_island_info_from_faces(bm, faces, uv_layer)
            for isl in islands:
                faces_list.append([f["face"] for f in isl["faces"]])
    elif method == 'FACE':
        if only_selected:
            for f in bm.faces:
                if f.select:
                    faces_list.append([f])
        else:
            for f in bm.faces:
                faces_list.append([f])
    else:
        raise ValueError("Invalid method: {}".format(method))

    return faces_list


nutti's avatar
nutti committed
def measure_all_faces_mesh_area(bm):
    if compat.check_version(2, 80, 0) >= 0:
        triangle_loops = bm.calc_loop_triangles()
    else:
        triangle_loops = bm.calc_tessface()

    areas = {face: 0.0 for face in bm.faces}

    for loops in triangle_loops:
        face = loops[0].face
        area = areas[face]
        area += calc_tris_3d_area([l.vert.co for l in loops])
        areas[face] = area

    return areas


nutti's avatar
nutti committed
def measure_mesh_area(obj, calc_method, only_selected):
Nutti's avatar
Nutti committed
    bm = bmesh.from_edit_mesh(obj.data)
    if check_version(2, 73, 0) >= 0:
        bm.verts.ensure_lookup_table()
        bm.edges.ensure_lookup_table()
        bm.faces.ensure_lookup_table()

nutti's avatar
nutti committed
    faces_list = get_faces_list(bm, calc_method, only_selected)
Nutti's avatar
Nutti committed

nutti's avatar
nutti committed
    areas = []
    for faces in faces_list:
nutti's avatar
nutti committed
        areas.append(measure_mesh_area_from_faces(bm, faces))
nutti's avatar
nutti committed

    return areas


nutti's avatar
nutti committed
def measure_mesh_area_from_faces(bm, faces):
    face_areas = measure_all_faces_mesh_area(bm)

Nutti's avatar
Nutti committed
    mesh_area = 0.0
nutti's avatar
nutti committed
    for f in faces:
nutti's avatar
nutti committed
        if f in face_areas:
            mesh_area += face_areas[f]
Nutti's avatar
Nutti committed

    return mesh_area


def find_texture_layer(bm):
    if check_version(2, 80, 0) >= 0:
        return None
    if bm.faces.layers.tex is None:
        return None

    return bm.faces.layers.tex.verify()


nutti's avatar
nutti committed
def find_texture_nodes_from_material(mtrl):
nutti's avatar
nutti committed
    if not mtrl.node_tree:
        return nodes
    for node in mtrl.node_tree.nodes:
        tex_node_types = [
            'TEX_ENVIRONMENT',
            'TEX_IMAGE',
        ]
        if node.type not in tex_node_types:
Nutti's avatar
Nutti committed
            continue
nutti's avatar
nutti committed
        if not node.image:
nutti's avatar
nutti committed
        nodes.append(node)

    return nodes


def find_texture_nodes(obj):
    nodes = []
    for slot in obj.material_slots:
        if not slot.material:
            continue
        nodes.extend(find_texture_nodes_from_material(slot.material))

    return nodes


def find_image(obj, face=None, tex_layer=None):
Nutti's avatar
Nutti committed
    images = find_images(obj, face, tex_layer)

    if len(images) >= 2:
        raise RuntimeError("Find more than 2 images")
nutti's avatar
nutti committed
    if not images:
Nutti's avatar
Nutti committed
        return None

    return images[0]


def find_images(obj, face=None, tex_layer=None):
    images = []

    # try to find from texture_layer
    if tex_layer and face:
Nutti's avatar
Nutti committed
        if face[tex_layer].image is not None:
            images.append(face[tex_layer].image)

    # not found, then try to search from node
Nutti's avatar
Nutti committed
    if not images:
        nodes = find_texture_nodes(obj)
Nutti's avatar
Nutti committed
        for n in nodes:
            images.append(n.image)
Nutti's avatar
Nutti committed
    return images
nutti's avatar
nutti committed
def measure_all_faces_uv_area(bm, uv_layer):
    if compat.check_version(2, 80, 0) >= 0:
        triangle_loops = bm.calc_loop_triangles()
    else:
        triangle_loops = bm.calc_tessface()

    areas = {face: 0.0 for face in bm.faces}

    for loops in triangle_loops:
        face = loops[0].face
        area = areas[face]
        area += calc_tris_2d_area([l[uv_layer].uv for l in loops])
        areas[face] = area

    return areas


def measure_uv_area_from_faces(obj, bm, faces, uv_layer, tex_layer,
nutti's avatar
nutti committed
                               tex_selection_method, tex_size):
nutti's avatar
nutti committed

    face_areas = measure_all_faces_uv_area(bm, uv_layer)

    uv_area = 0.0
nutti's avatar
nutti committed
    for f in faces:
nutti's avatar
nutti committed
        if f not in face_areas:
            continue

        f_uv_area = face_areas[f]

        # user specified
nutti's avatar
nutti committed
        if tex_selection_method == 'USER_SPECIFIED' and tex_size is not None:
Nutti's avatar
Nutti committed
            img_size = tex_size
        # first texture if there are more than 2 textures assigned
        # to the object
nutti's avatar
nutti committed
        elif tex_selection_method == 'FIRST':
Nutti's avatar
Nutti committed
            img = find_image(obj, f, tex_layer)
            # can not find from node, so we can not get texture size
            if not img:
                return None
            img_size = img.size
        # average texture size
nutti's avatar
nutti committed
        elif tex_selection_method == 'AVERAGE':
Nutti's avatar
Nutti committed
            imgs = find_images(obj, f, tex_layer)
            if not imgs:
                return None

            img_size_total = [0.0, 0.0]
            for img in imgs:
                img_size_total = [img_size_total[0] + img.size[0],
                                  img_size_total[1] + img.size[1]]
            img_size = [img_size_total[0] / len(imgs),
                        img_size_total[1] / len(imgs)]
        # max texture size
nutti's avatar
nutti committed
        elif tex_selection_method == 'MAX':
Nutti's avatar
Nutti committed
            imgs = find_images(obj, f, tex_layer)
            if not imgs:
                return None

            img_size_max = [-99999999.0, -99999999.0]
            for img in imgs:
                img_size_max = [max(img_size_max[0], img.size[0]),
                                max(img_size_max[1], img.size[1])]
            img_size = img_size_max
        # min texture size
nutti's avatar
nutti committed
        elif tex_selection_method == 'MIN':
Nutti's avatar
Nutti committed
            imgs = find_images(obj, f, tex_layer)
            if not imgs:
                return None

            img_size_min = [99999999.0, 99999999.0]
            for img in imgs:
                img_size_min = [min(img_size_min[0], img.size[0]),
                                min(img_size_min[1], img.size[1])]
            img_size = img_size_min
        else:
nutti's avatar
nutti committed
            raise RuntimeError("Unexpected method: {}"
                               .format(tex_selection_method))
nutti's avatar
nutti committed
        uv_area += f_uv_area * img_size[0] * img_size[1]
nutti's avatar
nutti committed
def measure_uv_area(obj, calc_method, tex_selection_method,
                    tex_size, only_selected):
nutti's avatar
nutti committed
    bm = bmesh.from_edit_mesh(obj.data)
    if check_version(2, 73, 0) >= 0:
        bm.verts.ensure_lookup_table()
        bm.edges.ensure_lookup_table()
        bm.faces.ensure_lookup_table()

    if not bm.loops.layers.uv:
        return None
    uv_layer = bm.loops.layers.uv.verify()
    tex_layer = find_texture_layer(bm)
    faces_list = get_faces_list(bm, calc_method, only_selected)

    # measure
    uv_areas = []
    for faces in faces_list:
        uv_area = measure_uv_area_from_faces(
nutti's avatar
nutti committed
            obj, bm, faces, uv_layer, tex_layer,
            tex_selection_method, tex_size)
nutti's avatar
nutti committed
        if uv_area is None:
            return None
        uv_areas.append(uv_area)

    return uv_areas


Nutti's avatar
Nutti committed
def diff_point_to_segment(a, b, p):
    ab = b - a
    normal_ab = ab.normalized()

    ap = p - a
    dist_ax = normal_ab.dot(ap)

    # cross point
    x = a + normal_ab * dist_ax

    # difference between cross point and point
    xp = p - x

    return xp, x


# get selected loop pair whose loops are connected each other
def __get_loop_pairs(l, uv_layer):
nutti's avatar
nutti committed
    pairs = []
    parsed = []
    loops_ready = [l]
    while loops_ready:
        l = loops_ready.pop(0)
        parsed.append(l)
        for ll in l.vert.link_loops:
Nutti's avatar
Nutti committed
            # forward direction
            lln = ll.link_loop_next
            # if there is same pair, skip it
            found = False
nutti's avatar
nutti committed
            for p in pairs:
Nutti's avatar
Nutti committed
                if (ll in p) and (lln in p):
                    found = True
                    break
            # two loops must be selected
nutti's avatar
nutti committed
            if ll[uv_layer].select and lln[uv_layer].select:
Nutti's avatar
Nutti committed
                if not found:
nutti's avatar
nutti committed
                    pairs.append([ll, lln])
                if (lln not in parsed) and (lln not in loops_ready):
                    loops_ready.append(lln)
Nutti's avatar
Nutti committed

            # backward direction
            llp = ll.link_loop_prev
            # if there is same pair, skip it
            found = False
nutti's avatar
nutti committed
            for p in pairs:
Nutti's avatar
Nutti committed
                if (ll in p) and (llp in p):
                    found = True
                    break
            # two loops must be selected
nutti's avatar
nutti committed
            if ll[uv_layer].select and llp[uv_layer].select:
Nutti's avatar
Nutti committed
                if not found:
nutti's avatar
nutti committed
                    pairs.append([ll, llp])
                if (llp not in parsed) and (llp not in loops_ready):
                    loops_ready.append(llp)
Nutti's avatar
Nutti committed

    return pairs


# sort pair by vertex
# (v0, v1) - (v1, v2) - (v2, v3) ....
def __sort_loop_pairs(uv_layer, pairs, closed):
    rest = pairs
    sorted_pairs = [rest[0]]
    rest.remove(rest[0])

    # prepend
    while True:
        p1 = sorted_pairs[0]
        for p2 in rest:
            if p1[0].vert == p2[0].vert:
                sorted_pairs.insert(0, [p2[1], p2[0]])
                rest.remove(p2)
                break
            elif p1[0].vert == p2[1].vert:
                sorted_pairs.insert(0, [p2[0], p2[1]])
                rest.remove(p2)
                break
        else:
            break

    # append
    while True:
        p1 = sorted_pairs[-1]
        for p2 in rest:
            if p1[1].vert == p2[0].vert:
                sorted_pairs.append([p2[0], p2[1]])
                rest.remove(p2)
                break
            elif p1[1].vert == p2[1].vert:
                sorted_pairs.append([p2[1], p2[0]])
                rest.remove(p2)
                break
        else:
            break

    begin_vert = sorted_pairs[0][0].vert
    end_vert = sorted_pairs[-1][-1].vert
    if begin_vert != end_vert:
        return sorted_pairs, ""
    if closed and (begin_vert == end_vert):
        # if the sequence of UV is circular, it is ok
        return sorted_pairs, ""

    # if the begin vertex and the end vertex are same, search the UVs which
    # are separated each other
    tmp_pairs = sorted_pairs
    for i, (p1, p2) in enumerate(zip(tmp_pairs[:-1], tmp_pairs[1:])):
        diff = p2[0][uv_layer].uv - p1[-1][uv_layer].uv
        if diff.length > 0.000000001:
            # UVs are separated
            sorted_pairs = tmp_pairs[i + 1:]
            sorted_pairs.extend(tmp_pairs[:i + 1])
            break
    else:
        p1 = tmp_pairs[0]
        p2 = tmp_pairs[-1]
        diff = p2[-1][uv_layer].uv - p1[0][uv_layer].uv
        if diff.length < 0.000000001:
            # all UVs are not separated
            return None, "All UVs are not separated"
Nutti's avatar
Nutti committed

    return sorted_pairs, ""


# get index of the island group which includes loop
def __get_island_group_include_loop(loop, island_info):
    for i, isl in enumerate(island_info):
        for f in isl['faces']:
            for l in f['face'].loops:
                if l == loop:
                    return i    # found

    return -1   # not found


# get index of the island group which includes pair.
# if island group is not same between loops, it will be invalid
def __get_island_group_include_pair(pair, island_info):
    l1_grp = __get_island_group_include_loop(pair[0], island_info)
    if l1_grp == -1:
        return -1   # not found

    for p in pair[1:]:
        l2_grp = __get_island_group_include_loop(p, island_info)
        if (l2_grp == -1) or (l1_grp != l2_grp):
            return -1   # not found or invalid

    return l1_grp


# x ---- x   <- next_loop_pair
# |      |
# o ---- o   <- pair
def __get_next_loop_pair(pair):
    lp = pair[0].link_loop_prev
    if lp.vert == pair[1].vert:
        lp = pair[0].link_loop_next
        if lp.vert == pair[1].vert:
            # no loop is found
            return None

    ln = pair[1].link_loop_next
    if ln.vert == pair[0].vert:
        ln = pair[1].link_loop_prev
        if ln.vert == pair[0].vert:
            # no loop is found
            return None

    # tri-face
    if lp == ln:
        return [lp]

    # quad-face
    return [lp, ln]


# | ---- |
# % ---- %   <- next_poly_loop_pair
# x ---- x   <- next_loop_pair
# |      |
# o ---- o   <- pair
def __get_next_poly_loop_pair(pair):
    v1 = pair[0].vert
    v2 = pair[1].vert
    for l1 in v1.link_loops:
        if l1 == pair[0]:
            continue
        for l2 in v2.link_loops:
            if l2 == pair[1]:
                continue
            if l1.link_loop_next == l2:
                return [l1, l2]
            elif l1.link_loop_prev == l2:
                return [l1, l2]

    # no next poly loop is found
    return None


# get loop sequence in the same island
def __get_loop_sequence_internal(uv_layer, pairs, island_info, closed):
    loop_sequences = []
    for pair in pairs:
        seqs = [pair]
        p = pair
        isl_grp = __get_island_group_include_pair(pair, island_info)
        if isl_grp == -1:
            return None, "Can not find the island or invalid island"

        while True:
            nlp = __get_next_loop_pair(p)
            if not nlp:
                break       # no more loop pair
            nlp_isl_grp = __get_island_group_include_pair(nlp, island_info)
            if nlp_isl_grp != isl_grp:
                break       # another island
            for nlpl in nlp:
                if nlpl[uv_layer].select:
                    return None, "Do not select UV which does not belong to " \
                                 "the end edge"

            seqs.append(nlp)

            # when face is triangle, it indicates CLOSED
            if (len(nlp) == 1) and closed:
                break

            nplp = __get_next_poly_loop_pair(nlp)
            if not nplp:
                break       # no more loop pair
            nplp_isl_grp = __get_island_group_include_pair(nplp, island_info)
            if nplp_isl_grp != isl_grp:
                break       # another island

            # check if the UVs are already parsed.
            # this check is needed for the mesh which has the circular
Nutti's avatar
Nutti committed
            matched = False
            for p1 in seqs:
                p2 = nplp
                if ((p1[0] == p2[0]) and (p1[1] == p2[1])) or \
                   ((p1[0] == p2[1]) and (p1[1] == p2[0])):
                    matched = True
            if matched:
                debug_print("This is a circular sequence")
                break

            for nlpl in nplp:
                if nlpl[uv_layer].select:
                    return None, "Do not select UV which does not belong to " \
                                 "the end edge"

            seqs.append(nplp)

            p = nplp

        loop_sequences.append(seqs)
    return loop_sequences, ""


Nutti's avatar
Nutti committed
def get_loop_sequences(bm, uv_layer, closed=False):
Nutti's avatar
Nutti committed
    sel_faces = [f for f in bm.faces if f.select]

    # get candidate loops
    cand_loops = []
    for f in sel_faces:
        for l in f.loops:
            if l[uv_layer].select:
                cand_loops.append(l)

    if len(cand_loops) < 2:
        return None, "More than 2 UVs must be selected"

    first_loop = cand_loops[0]
    isl_info = get_island_info_from_bmesh(bm, False)
    loop_pairs = __get_loop_pairs(first_loop, uv_layer)
Nutti's avatar
Nutti committed
    loop_pairs, err = __sort_loop_pairs(uv_layer, loop_pairs, closed)
Nutti's avatar
Nutti committed
    if not loop_pairs:
        return None, err
    loop_seqs, err = __get_loop_sequence_internal(uv_layer, loop_pairs,
Nutti's avatar
Nutti committed
                                                  isl_info, closed)
Nutti's avatar
Nutti committed
    if not loop_seqs:
        return None, err

    return loop_seqs, ""
Nutti's avatar
Nutti committed


def __is_segment_intersect(start1, end1, start2, end2):
    seg1 = end1 - start1
    seg2 = end2 - start2

    a1 = -seg1.y
    b1 = seg1.x
    d1 = -(a1 * start1.x + b1 * start1.y)

    a2 = -seg2.y
    b2 = seg2.x
    d2 = -(a2 * start2.x + b2 * start2.y)

    seg1_line2_start = a2 * start1.x + b2 * start1.y + d2
    seg1_line2_end = a2 * end1.x + b2 * end1.y + d2

    seg2_line1_start = a1 * start2.x + b1 * start2.y + d1
    seg2_line1_end = a1 * end2.x + b1 * end2.y + d1

    if (seg1_line2_start * seg1_line2_end >= 0) or \
            (seg2_line1_start * seg2_line1_end >= 0):
        return False, None

    u = seg1_line2_start / (seg1_line2_start - seg1_line2_end)
    out = start1 + u * seg1

    return True, out


class RingBuffer:
    def __init__(self, arr):
        self.__buffer = arr.copy()
        self.__pointer = 0

    def __repr__(self):
        return repr(self.__buffer)

    def __len__(self):
        return len(self.__buffer)

    def insert(self, val, offset=0):
        self.__buffer.insert(self.__pointer + offset, val)

    def head(self):
        return self.__buffer[0]

    def tail(self):
        return self.__buffer[-1]

    def get(self, offset=0):
        size = len(self.__buffer)
        val = self.__buffer[(self.__pointer + offset) % size]
        return val

    def next(self):
        size = len(self.__buffer)
        self.__pointer = (self.__pointer + 1) % size

    def reset(self):
        self.__pointer = 0

    def find(self, obj):
        try:
            idx = self.__buffer.index(obj)
        except ValueError:
            return None
        return self.__buffer[idx]

    def find_and_next(self, obj):
        size = len(self.__buffer)
        idx = self.__buffer.index(obj)
        self.__pointer = (idx + 1) % size

    def find_and_set(self, obj):
        idx = self.__buffer.index(obj)
        self.__pointer = idx

    def as_list(self):
        return self.__buffer.copy()

    def reverse(self):
        self.__buffer.reverse()
        self.reset()


# clip: reference polygon
# subject: tested polygon
nutti's avatar
nutti committed
def __do_weiler_atherton_cliping(clip_uvs, subject_uvs, mode,
                                 same_polygon_threshold):
Nutti's avatar
Nutti committed

nutti's avatar
nutti committed
    clip_uvs = RingBuffer(clip_uvs)
Nutti's avatar
Nutti committed
    if __is_polygon_flipped(clip_uvs):
        clip_uvs.reverse()
nutti's avatar
nutti committed
    subject_uvs = RingBuffer(subject_uvs)
Nutti's avatar
Nutti committed
    if __is_polygon_flipped(subject_uvs):
        subject_uvs.reverse()

    debug_print("===== Clip UV List =====")
    debug_print(clip_uvs)
    debug_print("===== Subject UV List =====")
    debug_print(subject_uvs)

    # check if clip and subject is overlapped completely
nutti's avatar
nutti committed
    if __is_polygon_same(clip_uvs, subject_uvs, same_polygon_threshold):
Nutti's avatar
Nutti committed
        polygons = [subject_uvs.as_list()]
        debug_print("===== Polygons Overlapped Completely =====")
        debug_print(polygons)
        return True, polygons

    # check if subject is in clip
    if __is_points_in_polygon(subject_uvs, clip_uvs):
        polygons = [subject_uvs.as_list()]
        return True, polygons

    # check if clip is in subject
    if __is_points_in_polygon(clip_uvs, subject_uvs):
        polygons = [subject_uvs.as_list()]
        return True, polygons

    # check if clip and subject is overlapped partially
    intersections = []
    while True:
        subject_uvs.reset()
        while True:
            uv_start1 = clip_uvs.get()
            uv_end1 = clip_uvs.get(1)
            uv_start2 = subject_uvs.get()
            uv_end2 = subject_uvs.get(1)
            intersected, point = __is_segment_intersect(uv_start1, uv_end1,
                                                        uv_start2, uv_end2)
            if intersected:
                clip_uvs.insert(point, 1)
                subject_uvs.insert(point, 1)
                intersections.append([point,
                                      [clip_uvs.get(), clip_uvs.get(1)]])
            subject_uvs.next()
            if subject_uvs.get() == subject_uvs.head():
                break
        clip_uvs.next()
        if clip_uvs.get() == clip_uvs.head():
            break

    debug_print("===== Intersection List =====")
    debug_print(intersections)

    # no intersection, so subject and clip is not overlapped
    if not intersections:
        return False, None

    def get_intersection_pair(intersects, key):
        for sect in intersects:
            if sect[0] == key:
                return sect[1]

        return None

    # make enter/exit pair
    subject_uvs.reset()
    subject_entering = []
    subject_exiting = []
    clip_entering = []
    clip_exiting = []
    intersect_uv_list = []
    while True:
        pair = get_intersection_pair(intersections, subject_uvs.get())
        if pair:
            sub = subject_uvs.get(1) - subject_uvs.get(-1)
            inter = pair[1] - pair[0]
            cross = sub.x * inter.y - inter.x * sub.y
            if cross < 0:
                subject_entering.append(subject_uvs.get())
                clip_exiting.append(subject_uvs.get())
            else:
                subject_exiting.append(subject_uvs.get())
                clip_entering.append(subject_uvs.get())
            intersect_uv_list.append(subject_uvs.get())

        subject_uvs.next()
        if subject_uvs.get() == subject_uvs.head():
            break

    debug_print("===== Enter List =====")
    debug_print(clip_entering)
    debug_print(subject_entering)
    debug_print("===== Exit List =====")
    debug_print(clip_exiting)
    debug_print(subject_exiting)

    # for now, can't handle the situation when fulfill all below conditions
    #        * two faces have common edge
    #        * each face is intersected
    #        * Show Mode is "Part"
    #       so for now, ignore this situation
    if len(subject_entering) != len(subject_exiting):
        if mode == 'FACE':
            polygons = [subject_uvs.as_list()]
            return True, polygons
        return False, None

    def traverse(current_list, entering, exiting, p, current, other_list):
        result = current_list.find(current)
        if not result:
            return None
        if result != current:
            print("Internal Error")
            return None
        if not exiting:
            print("Internal Error: No exiting UV")
            return None
Nutti's avatar
Nutti committed

        # enter
        if entering.count(current) >= 1:
            entering.remove(current)

        current_list.find_and_next(current)
        current = current_list.get()

        prev = None
        error = False
Nutti's avatar
Nutti committed
        while exiting.count(current) == 0:
            p.append(current.copy())
            current_list.find_and_next(current)
            current = current_list.get()
            if prev == current:
                error = True
                break
            prev = current

        if error:
            print("Internal Error: Infinite loop")
            return None
Nutti's avatar
Nutti committed

        # exit
        p.append(current.copy())
        exiting.remove(current)

        other_list.find_and_set(current)
        return other_list.get()

    # Traverse
    polygons = []
    current_uv_list = subject_uvs
    other_uv_list = clip_uvs
    current_entering = subject_entering
    current_exiting = subject_exiting

    poly = []
    current_uv = current_entering[0]

    while True:
        current_uv = traverse(current_uv_list, current_entering,
                              current_exiting, poly, current_uv, other_uv_list)

        if current_uv is None:
            break

Nutti's avatar
Nutti committed
        if current_uv_list == subject_uvs:
            current_uv_list = clip_uvs
            other_uv_list = subject_uvs
            current_entering = clip_entering
            current_exiting = clip_exiting
            debug_print("-- Next: Clip --")
        else:
            current_uv_list = subject_uvs
            other_uv_list = clip_uvs
            current_entering = subject_entering
            current_exiting = subject_exiting
            debug_print("-- Next: Subject --")

        debug_print(clip_entering)
        debug_print(clip_exiting)
        debug_print(subject_entering)
        debug_print(subject_exiting)

        if not clip_entering and not clip_exiting \
                and not subject_entering and not subject_exiting:
            break

    polygons.append(poly)

    debug_print("===== Polygons Overlapped Partially =====")
    debug_print(polygons)

    return True, polygons


def __is_polygon_flipped(points):
    area = 0.0
    for i in range(len(points)):
        uv1 = points.get(i)
        uv2 = points.get(i + 1)
        a = uv1.x * uv2.y - uv1.y * uv2.x
        area = area + a
    if area < 0:
        # clock-wise
        return True
    return False


def __is_point_in_polygon(point, subject_points):
    count = 0
    for i in range(len(subject_points)):
        uv_start1 = subject_points.get(i)
        uv_end1 = subject_points.get(i + 1)
        uv_start2 = point
        uv_end2 = Vector((1000000.0, point.y))
        intersected, _ = __is_segment_intersect(uv_start1, uv_end1,
                                                uv_start2, uv_end2)
        if intersected:
            count = count + 1

    return count % 2


def __is_points_in_polygon(points, subject_points):
    for i in range(len(points)):
        internal = __is_point_in_polygon(points.get(i), subject_points)
        if not internal:
            return False

    return True


nutti's avatar
nutti committed
def get_uv_editable_objects(context):
    if compat.check_version(2, 80, 0) < 0:
        objs = [context.active_object]
    else:
        objs = [o for o in bpy.data.objects
                if compat.get_object_select(o) and o.type == 'MESH']
        objs.append(context.active_object)

    objs = list(set(objs))
    return objs


nutti's avatar
nutti committed
def get_overlapped_uv_info(bm_list, faces_list, uv_layer_list,
                           mode, same_polygon_threshold=0.0000001):
Nutti's avatar
Nutti committed
    # at first, check island overlapped
nutti's avatar
nutti committed
    isl = []
    for bm, uv_layer, faces in zip(bm_list, uv_layer_list, faces_list):
        info = get_island_info_from_faces(bm, faces, uv_layer)
nutti's avatar
nutti committed
        isl.extend([(i, uv_layer, bm) for i in info])
nutti's avatar
nutti committed

Nutti's avatar
Nutti committed
    overlapped_isl_pairs = []
nutti's avatar
nutti committed
    overlapped_uv_layer_pairs = []
nutti's avatar
nutti committed
    overlapped_bm_paris = []
    for i, (i1, uv_layer_1, bm_1) in enumerate(isl):
        for i2, uv_layer_2, bm_2 in isl[i + 1:]:
Nutti's avatar
Nutti committed
            if (i1["max"].x < i2["min"].x) or (i2["max"].x < i1["min"].x) or \
               (i1["max"].y < i2["min"].y) or (i2["max"].y < i1["min"].y):
                continue
            overlapped_isl_pairs.append([i1, i2])
nutti's avatar
nutti committed
            overlapped_uv_layer_pairs.append([uv_layer_1, uv_layer_2])
nutti's avatar
nutti committed
            overlapped_bm_paris.append([bm_1, bm_2])
Nutti's avatar
Nutti committed

    # next, check polygon overlapped
    overlapped_uvs = []
nutti's avatar
nutti committed
    for oip, uvlp, bmp in zip(overlapped_isl_pairs,
                              overlapped_uv_layer_pairs,
                              overlapped_bm_paris):
Nutti's avatar
Nutti committed
        for clip in oip[0]["faces"]:
            f_clip = clip["face"]
nutti's avatar
nutti committed
            clip_uvs = [l[uvlp[0]].uv.copy() for l in f_clip.loops]
Nutti's avatar
Nutti committed
            for subject in oip[1]["faces"]:
                f_subject = subject["face"]

                # fast operation, apply bounding box algorithm
                if (clip["max_uv"].x < subject["min_uv"].x) or \
                   (subject["max_uv"].x < clip["min_uv"].x) or \
                   (clip["max_uv"].y < subject["min_uv"].y) or \
                   (subject["max_uv"].y < clip["min_uv"].y):
                    continue

nutti's avatar
nutti committed
                subject_uvs = [l[uvlp[1]].uv.copy() for l in f_subject.loops]
Nutti's avatar
Nutti committed
                # slow operation, apply Weiler-Atherton cliping algorithm
nutti's avatar
nutti committed
                result, polygons = \
                    __do_weiler_atherton_cliping(clip_uvs, subject_uvs,
                                                 mode, same_polygon_threshold)
Nutti's avatar
Nutti committed
                if result:
nutti's avatar
nutti committed
                    overlapped_uvs.append({"clip_bmesh": bmp[0],
                                           "subject_bmesh": bmp[1],
                                           "clip_face": f_clip,
Nutti's avatar
Nutti committed
                                           "subject_face": f_subject,
nutti's avatar
nutti committed
                                           "clip_uv_layer": uvlp[0],
                                           "subject_uv_layer": uvlp[1],
Nutti's avatar
Nutti committed
                                           "subject_uvs": subject_uvs,
                                           "polygons": polygons})

    return overlapped_uvs


nutti's avatar
nutti committed
def get_flipped_uv_info(bm_list, faces_list, uv_layer_list):
Nutti's avatar
Nutti committed
    flipped_uvs = []
nutti's avatar
nutti committed
    for bm, faces, uv_layer in zip(bm_list, faces_list, uv_layer_list):
nutti's avatar
nutti committed
        for f in faces:
            polygon = RingBuffer([l[uv_layer].uv.copy() for l in f.loops])
            if __is_polygon_flipped(polygon):
                uvs = [l[uv_layer].uv.copy() for l in f.loops]
nutti's avatar
nutti committed
                flipped_uvs.append({"bmesh": bm,
                                    "face": f,
nutti's avatar
nutti committed
                                    "uv_layer": uv_layer,
                                    "uvs": uvs,
                                    "polygons": [polygon.as_list()]})
Nutti's avatar
Nutti committed

    return flipped_uvs


nutti's avatar
nutti committed
def __is_polygon_same(points1, points2, threshold):
Nutti's avatar
Nutti committed
    if len(points1) != len(points2):
        return False

    pts1 = points1.as_list()
    pts2 = points2.as_list()

    for p1 in pts1:
        for p2 in pts2:
            diff = p2 - p1
nutti's avatar
nutti committed
            if diff.length < threshold:
Nutti's avatar
Nutti committed
                pts2.remove(p2)
                break
        else:
            return False

    return True