common.py

    if __is_polygon_flipped(clip_uvs):
        clip_uvs.reverse()
    subject_uvs = RingBuffer(subject_uvs)
    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
    if __is_polygon_same(clip_uvs, subject_uvs, same_polygon_threshold):
        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

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

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

        prev = None
        error = False
        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

        # 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

        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):
    """Return true when point is inside of the polygon by using
    'Crossing number algorithm'.
    """

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

        # If the point exactly matches to the point of the polygon,
        # this point is not in polygon.
        if uv_start1.x == uv_start2.x and uv_start1.y == uv_start2.y:
            return False

        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


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

    ob = context.active_object
    if ob is not None:
        objs.append(ob)

    objs = list(set(objs))
    return objs


def get_overlapped_uv_info(bm_list, faces_list, uv_layer_list,
                           mode, same_polygon_threshold=0.0000001):
    # at first, check island overlapped
    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)
        isl.extend([(i, uv_layer, bm) for i in info])

    overlapped_isl_pairs = []
    overlapped_uv_layer_pairs = []
    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:]:
            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])
            overlapped_uv_layer_pairs.append([uv_layer_1, uv_layer_2])
            overlapped_bm_paris.append([bm_1, bm_2])

    # check polygon overlapped (inter UV islands)
    overlapped_uvs = []
    for oip, uvlp, bmp in zip(overlapped_isl_pairs,
                              overlapped_uv_layer_pairs,
                              overlapped_bm_paris):
        for clip in oip[0]["faces"]:
            f_clip = clip["face"]
            clip_uvs = [l[uvlp[0]].uv.copy() for l in f_clip.loops]
            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

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

    # check polygon overlapped (intra UV island)
    for info, uv_layer, bm in isl:
        for i in range(len(info["faces"])):
            clip = info["faces"][i]
            f_clip = clip["face"]
            clip_uvs = [l[uv_layer].uv.copy() for l in f_clip.loops]
            for j in range(len(info["faces"])):
                if j <= i:
                    continue

                subject = info["faces"][j]
                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

                subject_uvs = [l[uv_layer].uv.copy() for l in f_subject.loops]
                # slow operation, apply Weiler-Atherton cliping algorithm
                result, polygons = \
                    __do_weiler_atherton_cliping(clip_uvs, subject_uvs,
                                                 mode, same_polygon_threshold)
                if result:
                    overlapped_uvs.append({"clip_bmesh": bm,
                                           "subject_bmesh": bm,
                                           "clip_face": f_clip,
                                           "subject_face": f_subject,
                                           "clip_uv_layer": uv_layer,
                                           "subject_uv_layer": uv_layer,
                                           "subject_uvs": subject_uvs,
                                           "polygons": polygons})

    return overlapped_uvs


def get_flipped_uv_info(bm_list, faces_list, uv_layer_list):
    flipped_uvs = []
    for bm, faces, uv_layer in zip(bm_list, faces_list, uv_layer_list):
        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]
                flipped_uvs.append({"bmesh": bm,
                                    "face": f,
                                    "uv_layer": uv_layer,
                                    "uvs": uvs,
                                    "polygons": [polygon.as_list()]})

    return flipped_uvs


def __is_polygon_same(points1, points2, threshold):
    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
            if diff.length < threshold:
                pts2.remove(p2)
                break
        else:
            return False

    return True


def _is_uv_loop_connected(l1, l2, uv_layer):
    uv1 = l1[uv_layer].uv
    uv2 = l2[uv_layer].uv
    return uv1.x == uv2.x and uv1.y == uv2.y


def create_uv_graph(loops, uv_layer):
    # For looking up faster.
    loop_index_to_loop = {}     # { loop index: loop }
    for l in loops:
        loop_index_to_loop[l.index] = l

    # Setup relationship between uv_vert and loops.
    # uv_vert is a representative of the loops which shares same
    # UV coordinate.
    uv_vert_to_loops = {}   # { uv_vert: loops belonged to uv_vert }
    loop_to_uv_vert = {}    # { loop: uv_vert belonged to }
    for l in loops:
        found = False
        for k in uv_vert_to_loops.keys():
            if _is_uv_loop_connected(k, l, uv_layer):
                uv_vert_to_loops[k].append(l)
                loop_to_uv_vert[l] = k
                found = True
                break
        if not found:
            uv_vert_to_loops[l] = [l]
            loop_to_uv_vert[l] = l

    # Collect adjacent uv_vert.
    uv_adj_verts = {}       # { uv_vert: adj uv_vert list }
    for v, vs in uv_vert_to_loops.items():
        uv_adj_verts[v] = []
        for ll in vs:
            ln = ll.link_loop_next
            lp = ll.link_loop_prev
            uv_adj_verts[v].append(loop_to_uv_vert[ln])
            uv_adj_verts[v].append(loop_to_uv_vert[lp])
        uv_adj_verts[v] = list(set(uv_adj_verts[v]))

    # Setup uv_vert graph.
    graph = Graph()
    for v in uv_adj_verts.keys():
        graph.add_node(
            Node(v.index, {"uv_vert": v, "loops": uv_vert_to_loops[v]})
        )
    edges = []
    for v, adjs in uv_adj_verts.items():
        n1 = graph.get_node(v.index)
        for a in adjs:
            n2 = graph.get_node(a.index)
            edges.append(tuple(sorted((n1.key, n2.key))))
    edges = list(set(edges))
    for e in edges:
        n1 = graph.get_node(e[0])
        n2 = graph.get_node(e[1])
        graph.add_edge(n1, n2)

    return graph