magic_uv/common.py

   1 # SPDX-FileCopyrightText: 2018-2022 Blender Foundation
   2 #
   3 # SPDX-License-Identifier: GPL-2.0-or-later
   4
   5 __author__ = "Nutti <nutti.metro@gmail.com>"
   6 __status__ = "production"
   7 __version__ = "6.6"
   8 __date__ = "22 Apr 2022"
   9
  10 from collections import defaultdict
  11 from pprint import pprint
  12 from math import fabs, sqrt
  13 import os
  14
  15 import bpy
  16 from mathutils import Vector
  17 import bmesh
  18
  19 from .utils import compatibility as compat
  20 from .utils.graph import Graph, Node
  21
  22
  23 __DEBUG_MODE = False
  24
  25
  26 def is_console_mode():
  27     if "MUV_CONSOLE_MODE" not in os.environ:
  28         return False
  29     return os.environ["MUV_CONSOLE_MODE"] == "true"
  30
  31
  32 def is_valid_space(context, allowed_spaces):
  33     for area in context.screen.areas:
  34         for space in area.spaces:
  35             if space.type in allowed_spaces:
  36                 return True
  37     return False
  38
  39
  40 def is_debug_mode():
  41     return __DEBUG_MODE
  42
  43
  44 def enable_debugg_mode():
  45     # pylint: disable=W0603
  46     global __DEBUG_MODE
  47     __DEBUG_MODE = True
  48
  49
  50 def disable_debug_mode():
  51     # pylint: disable=W0603
  52     global __DEBUG_MODE
  53     __DEBUG_MODE = False
  54
  55
  56 def debug_print(*s):
  57     """
  58     Print message to console in debugging mode
  59     """
  60
  61     if is_debug_mode():
  62         pprint(s)
  63
  64
  65 def check_version(major, minor, _):
  66     """
  67     Check blender version
  68     """
  69
  70     if bpy.app.version[0] == major and bpy.app.version[1] == minor:
  71         return 0
  72     if bpy.app.version[0] > major:
  73         return 1
  74     if bpy.app.version[1] > minor:
  75         return 1
  76     return -1
  77
  78
  79 def redraw_all_areas():
  80     """
  81     Redraw all areas
  82     """
  83
  84     for area in bpy.context.screen.areas:
  85         area.tag_redraw()
  86
  87
  88 def get_space(area_type, region_type, space_type):
  89     """
  90     Get current area/region/space
  91     """
  92
  93     area = None
  94     region = None
  95     space = None
  96
  97     for area in bpy.context.screen.areas:
  98         if area.type == area_type:
  99             break
 100     else:
 101         return (None, None, None)
 102     for region in area.regions:
 103         if region.type == region_type:
 104             if compat.check_version(2, 80, 0) >= 0:
 105                 if region.width <= 1 or region.height <= 1:
 106                     continue
 107             break
 108     else:
 109         return (area, None, None)
 110     for space in area.spaces:
 111         if space.type == space_type:
 112             break
 113     else:
 114         return (area, region, None)
 115
 116     return (area, region, space)
 117
 118
 119 def mouse_on_region(event, area_type, region_type):
 120     pos = Vector((event.mouse_x, event.mouse_y))
 121
 122     _, region, _ = get_space(area_type, region_type, "")
 123     if region is None:
 124         return False
 125
 126     if (pos.x > region.x) and (pos.x < region.x + region.width) and \
 127        (pos.y > region.y) and (pos.y < region.y + region.height):
 128         return True
 129
 130     return False
 131
 132
 133 def mouse_on_area(event, area_type):
 134     pos = Vector((event.mouse_x, event.mouse_y))
 135
 136     area, _, _ = get_space(area_type, "", "")
 137     if area is None:
 138         return False
 139
 140     if (pos.x > area.x) and (pos.x < area.x + area.width) and \
 141        (pos.y > area.y) and (pos.y < area.y + area.height):
 142         return True
 143
 144     return False
 145
 146
 147 def mouse_on_regions(event, area_type, regions):
 148     if not mouse_on_area(event, area_type):
 149         return False
 150
 151     for region in regions:
 152         result = mouse_on_region(event, area_type, region)
 153         if result:
 154             return True
 155
 156     return False
 157
 158
 159 def create_bmesh(obj):
 160     bm = bmesh.from_edit_mesh(obj.data)
 161     if check_version(2, 73, 0) >= 0:
 162         bm.faces.ensure_lookup_table()
 163
 164     return bm
 165
 166
 167 def create_new_uv_map(obj, name=None):
 168     uv_maps_old = {l.name for l in obj.data.uv_layers}
 169     bpy.ops.mesh.uv_texture_add()
 170     uv_maps_new = {l.name for l in obj.data.uv_layers}
 171     diff = uv_maps_new - uv_maps_old
 172
 173     if not list(diff):
 174         return None     # no more UV maps can not be created
 175
 176     # rename UV map
 177     new = obj.data.uv_layers[list(diff)[0]]
 178     if name:
 179         new.name = name
 180
 181     return new
 182
 183
 184 def __get_island_info(uv_layer, islands):
 185     """
 186     get information about each island
 187     """
 188
 189     island_info = []
 190     for isl in islands:
 191         info = {}
 192         max_uv = Vector((-10000000.0, -10000000.0))
 193         min_uv = Vector((10000000.0, 10000000.0))
 194         ave_uv = Vector((0.0, 0.0))
 195         num_uv = 0
 196         for face in isl:
 197             n = 0
 198             a = Vector((0.0, 0.0))
 199             ma = Vector((-10000000.0, -10000000.0))
 200             mi = Vector((10000000.0, 10000000.0))
 201             for l in face['face'].loops:
 202                 uv = l[uv_layer].uv
 203                 ma.x = max(uv.x, ma.x)
 204                 ma.y = max(uv.y, ma.y)
 205                 mi.x = min(uv.x, mi.x)
 206                 mi.y = min(uv.y, mi.y)
 207                 a = a + uv
 208                 n = n + 1
 209             ave_uv = ave_uv + a
 210             num_uv = num_uv + n
 211             a = a / n
 212             max_uv.x = max(ma.x, max_uv.x)
 213             max_uv.y = max(ma.y, max_uv.y)
 214             min_uv.x = min(mi.x, min_uv.x)
 215             min_uv.y = min(mi.y, min_uv.y)
 216             face['max_uv'] = ma
 217             face['min_uv'] = mi
 218             face['ave_uv'] = a
 219         ave_uv = ave_uv / num_uv
 220
 221         info['center'] = ave_uv
 222         info['size'] = max_uv - min_uv
 223         info['num_uv'] = num_uv
 224         info['group'] = -1
 225         info['faces'] = isl
 226         info['max'] = max_uv
 227         info['min'] = min_uv
 228
 229         island_info.append(info)
 230
 231     return island_info
 232
 233
 234 def __parse_island(bm, face_idx, faces_left, island,
 235                    face_to_verts, vert_to_faces):
 236     """
 237     Parse island
 238     """
 239
 240     faces_to_parse = [face_idx]
 241     while faces_to_parse:
 242         fidx = faces_to_parse.pop(0)
 243         if fidx in faces_left:
 244             faces_left.remove(fidx)
 245             island.append({'face': bm.faces[fidx]})
 246             for v in face_to_verts[fidx]:
 247                 connected_faces = vert_to_faces[v]
 248                 for cf in connected_faces:
 249                     faces_to_parse.append(cf)
 250
 251
 252 def __get_island(bm, face_to_verts, vert_to_faces):
 253     """
 254     Get island list
 255     """
 256
 257     uv_island_lists = []
 258     faces_left = set(face_to_verts.keys())
 259     while faces_left:
 260         current_island = []
 261         face_idx = list(faces_left)[0]
 262         __parse_island(bm, face_idx, faces_left, current_island,
 263                        face_to_verts, vert_to_faces)
 264         uv_island_lists.append(current_island)
 265
 266     return uv_island_lists
 267
 268
 269 def __create_vert_face_db(faces, uv_layer):
 270     # create mesh database for all faces
 271     face_to_verts = defaultdict(set)
 272     vert_to_faces = defaultdict(set)
 273     for f in faces:
 274         for l in f.loops:
 275             id_ = l[uv_layer].uv.to_tuple(5), l.vert.index
 276             face_to_verts[f.index].add(id_)
 277             vert_to_faces[id_].add(f.index)
 278
 279     return (face_to_verts, vert_to_faces)
 280
 281
 282 def get_island_info(obj, only_selected=True):
 283     bm = bmesh.from_edit_mesh(obj.data)
 284     if check_version(2, 73, 0) >= 0:
 285         bm.faces.ensure_lookup_table()
 286
 287     return get_island_info_from_bmesh(bm, only_selected)
 288
 289
 290 # Return island info.
 291 #
 292 # Format:
 293 #
 294 # [
 295 #   {
 296 #     faces: [
 297 #       {
 298 #         face: BMFace
 299 #         max_uv: Vector (2D)
 300 #         min_uv: Vector (2D)
 301 #         ave_uv: Vector (2D)
 302 #       },
 303 #       ...
 304 #     ]
 305 #     center: Vector (2D)
 306 #     size: Vector (2D)
 307 #     num_uv: int
 308 #     group: int
 309 #     max: Vector (2D)
 310 #     min: Vector (2D)
 311 #   },
 312 #   ...
 313 # ]
 314 def get_island_info_from_bmesh(bm, only_selected=True):
 315     if not bm.loops.layers.uv:
 316         return None
 317     uv_layer = bm.loops.layers.uv.verify()
 318
 319     # create database
 320     if only_selected:
 321         selected_faces = [f for f in bm.faces if f.select]
 322     else:
 323         selected_faces = [f for f in bm.faces]
 324
 325     return get_island_info_from_faces(bm, selected_faces, uv_layer)
 326
 327
 328 def get_island_info_from_faces(bm, faces, uv_layer):
 329     ftv, vtf = __create_vert_face_db(faces, uv_layer)
 330
 331     # Get island information
 332     uv_island_lists = __get_island(bm, ftv, vtf)
 333     island_info = __get_island_info(uv_layer, uv_island_lists)
 334
 335     return island_info
 336
 337
 338 def get_uvimg_editor_board_size(area):
 339     if area.spaces.active.image:
 340         return area.spaces.active.image.size
 341
 342     return (255.0, 255.0)
 343
 344
 345 def calc_tris_2d_area(points):
 346     area = 0.0
 347     for i, p1 in enumerate(points):
 348         p2 = points[(i + 1) % len(points)]
 349         v1 = p1 - points[0]
 350         v2 = p2 - points[0]
 351         a = v1.x * v2.y - v1.y * v2.x
 352         area = area + a
 353
 354     return fabs(0.5 * area)
 355
 356
 357 def calc_tris_3d_area(points):
 358     area = 0.0
 359     for i, p1 in enumerate(points):
 360         p2 = points[(i + 1) % len(points)]
 361         v1 = p1 - points[0]
 362         v2 = p2 - points[0]
 363         cx = v1.y * v2.z - v1.z * v2.y
 364         cy = v1.z * v2.x - v1.x * v2.z
 365         cz = v1.x * v2.y - v1.y * v2.x
 366         a = sqrt(cx * cx + cy * cy + cz * cz)
 367         area = area + a
 368
 369     return 0.5 * area
 370
 371
 372 def get_faces_list(bm, method, only_selected):
 373     faces_list = []
 374     if method == 'MESH':
 375         if only_selected:
 376             faces_list.append([f for f in bm.faces if f.select])
 377         else:
 378             faces_list.append([f for f in bm.faces])
 379     elif method == 'UV ISLAND':
 380         if not bm.loops.layers.uv:
 381             return None
 382         uv_layer = bm.loops.layers.uv.verify()
 383         if only_selected:
 384             faces = [f for f in bm.faces if f.select]
 385             islands = get_island_info_from_faces(bm, faces, uv_layer)
 386             for isl in islands:
 387                 faces_list.append([f["face"] for f in isl["faces"]])
 388         else:
 389             faces = [f for f in bm.faces]
 390             islands = get_island_info_from_faces(bm, faces, uv_layer)
 391             for isl in islands:
 392                 faces_list.append([f["face"] for f in isl["faces"]])
 393     elif method == 'FACE':
 394         if only_selected:
 395             for f in bm.faces:
 396                 if f.select:
 397                     faces_list.append([f])
 398         else:
 399             for f in bm.faces:
 400                 faces_list.append([f])
 401     else:
 402         raise ValueError("Invalid method: {}".format(method))
 403
 404     return faces_list
 405
 406
 407 def measure_all_faces_mesh_area(bm):
 408     if compat.check_version(2, 80, 0) >= 0:
 409         triangle_loops = bm.calc_loop_triangles()
 410     else:
 411         triangle_loops = bm.calc_tessface()
 412
 413     areas = {face: 0.0 for face in bm.faces}
 414
 415     for loops in triangle_loops:
 416         face = loops[0].face
 417         area = areas[face]
 418         area += calc_tris_3d_area([l.vert.co for l in loops])
 419         areas[face] = area
 420
 421     return areas
 422
 423
 424 def measure_mesh_area(obj, calc_method, only_selected):
 425     bm = bmesh.from_edit_mesh(obj.data)
 426     if check_version(2, 73, 0) >= 0:
 427         bm.verts.ensure_lookup_table()
 428         bm.edges.ensure_lookup_table()
 429         bm.faces.ensure_lookup_table()
 430
 431     faces_list = get_faces_list(bm, calc_method, only_selected)
 432
 433     areas = []
 434     for faces in faces_list:
 435         areas.append(measure_mesh_area_from_faces(bm, faces))
 436
 437     return areas
 438
 439
 440 def measure_mesh_area_from_faces(bm, faces):
 441     face_areas = measure_all_faces_mesh_area(bm)
 442
 443     mesh_area = 0.0
 444     for f in faces:
 445         if f in face_areas:
 446             mesh_area += face_areas[f]
 447
 448     return mesh_area
 449
 450
 451 def find_texture_layer(bm):
 452     if check_version(2, 80, 0) >= 0:
 453         return None
 454     if bm.faces.layers.tex is None:
 455         return None
 456
 457     return bm.faces.layers.tex.verify()
 458
 459
 460 def find_texture_nodes_from_material(mtrl):
 461     nodes = []
 462     if not mtrl.node_tree:
 463         return nodes
 464     for node in mtrl.node_tree.nodes:
 465         tex_node_types = [
 466             'TEX_ENVIRONMENT',
 467             'TEX_IMAGE',
 468         ]
 469         if node.type not in tex_node_types:
 470             continue
 471         if not node.image:
 472             continue
 473         nodes.append(node)
 474
 475     return nodes
 476
 477
 478 def find_texture_nodes(obj):
 479     nodes = []
 480     for slot in obj.material_slots:
 481         if not slot.material:
 482             continue
 483         nodes.extend(find_texture_nodes_from_material(slot.material))
 484
 485     return nodes
 486
 487
 488 def find_image(obj, face=None, tex_layer=None):
 489     images = find_images(obj, face, tex_layer)
 490
 491     if len(images) >= 2:
 492         raise RuntimeError("Find more than 2 images")
 493     if not images:
 494         return None
 495
 496     return images[0]
 497
 498
 499 def find_images(obj, face=None, tex_layer=None):
 500     images = []
 501
 502     # try to find from texture_layer
 503     if tex_layer and face:
 504         if face[tex_layer].image is not None:
 505             images.append(face[tex_layer].image)
 506
 507     # not found, then try to search from node
 508     if not images:
 509         nodes = find_texture_nodes(obj)
 510         for n in nodes:
 511             images.append(n.image)
 512
 513     return images
 514
 515
 516 def measure_all_faces_uv_area(bm, uv_layer):
 517     if compat.check_version(2, 80, 0) >= 0:
 518         triangle_loops = bm.calc_loop_triangles()
 519     else:
 520         triangle_loops = bm.calc_tessface()
 521
 522     areas = {face: 0.0 for face in bm.faces}
 523
 524     for loops in triangle_loops:
 525         face = loops[0].face
 526         area = areas[face]
 527         area += calc_tris_2d_area([l[uv_layer].uv for l in loops])
 528         areas[face] = area
 529
 530     return areas
 531
 532
 533 def measure_uv_area_from_faces(obj, bm, faces, uv_layer, tex_layer,
 534                                tex_selection_method, tex_size):
 535
 536     face_areas = measure_all_faces_uv_area(bm, uv_layer)
 537
 538     uv_area = 0.0
 539     for f in faces:
 540         if f not in face_areas:
 541             continue
 542
 543         f_uv_area = face_areas[f]
 544
 545         # user specified
 546         if tex_selection_method == 'USER_SPECIFIED' and tex_size is not None:
 547             img_size = tex_size
 548         # first texture if there are more than 2 textures assigned
 549         # to the object
 550         elif tex_selection_method == 'FIRST':
 551             img = find_image(obj, f, tex_layer)
 552             # can not find from node, so we can not get texture size
 553             if not img:
 554                 return None
 555             img_size = img.size
 556         # average texture size
 557         elif tex_selection_method == 'AVERAGE':
 558             imgs = find_images(obj, f, tex_layer)
 559             if not imgs:
 560                 return None
 561
 562             img_size_total = [0.0, 0.0]
 563             for img in imgs:
 564                 img_size_total = [img_size_total[0] + img.size[0],
 565                                   img_size_total[1] + img.size[1]]
 566             img_size = [img_size_total[0] / len(imgs),
 567                         img_size_total[1] / len(imgs)]
 568         # max texture size
 569         elif tex_selection_method == 'MAX':
 570             imgs = find_images(obj, f, tex_layer)
 571             if not imgs:
 572                 return None
 573
 574             img_size_max = [-99999999.0, -99999999.0]
 575             for img in imgs:
 576                 img_size_max = [max(img_size_max[0], img.size[0]),
 577                                 max(img_size_max[1], img.size[1])]
 578             img_size = img_size_max
 579         # min texture size
 580         elif tex_selection_method == 'MIN':
 581             imgs = find_images(obj, f, tex_layer)
 582             if not imgs:
 583                 return None
 584
 585             img_size_min = [99999999.0, 99999999.0]
 586             for img in imgs:
 587                 img_size_min = [min(img_size_min[0], img.size[0]),
 588                                 min(img_size_min[1], img.size[1])]
 589             img_size = img_size_min
 590         else:
 591             raise RuntimeError("Unexpected method: {}"
 592                                .format(tex_selection_method))
 593
 594         uv_area += f_uv_area * img_size[0] * img_size[1]
 595
 596     return uv_area
 597
 598
 599 def measure_uv_area(obj, calc_method, tex_selection_method,
 600                     tex_size, only_selected):
 601     bm = bmesh.from_edit_mesh(obj.data)
 602     if check_version(2, 73, 0) >= 0:
 603         bm.verts.ensure_lookup_table()
 604         bm.edges.ensure_lookup_table()
 605         bm.faces.ensure_lookup_table()
 606
 607     if not bm.loops.layers.uv:
 608         return None
 609     uv_layer = bm.loops.layers.uv.verify()
 610     tex_layer = find_texture_layer(bm)
 611     faces_list = get_faces_list(bm, calc_method, only_selected)
 612
 613     # measure
 614     uv_areas = []
 615     for faces in faces_list:
 616         uv_area = measure_uv_area_from_faces(
 617             obj, bm, faces, uv_layer, tex_layer,
 618             tex_selection_method, tex_size)
 619         if uv_area is None:
 620             return None
 621         uv_areas.append(uv_area)
 622
 623     return uv_areas
 624
 625
 626 def diff_point_to_segment(a, b, p):
 627     ab = b - a
 628     normal_ab = ab.normalized()
 629
 630     ap = p - a
 631     dist_ax = normal_ab.dot(ap)
 632
 633     # cross point
 634     x = a + normal_ab * dist_ax
 635
 636     # difference between cross point and point
 637     xp = p - x
 638
 639     return xp, x
 640
 641
 642 # get selected loop pair whose loops are connected each other
 643 def __get_loop_pairs(l, uv_layer):
 644     pairs = []
 645     parsed = []
 646     loops_ready = [l]
 647     while loops_ready:
 648         l = loops_ready.pop(0)
 649         parsed.append(l)
 650         for ll in l.vert.link_loops:
 651             # forward direction
 652             lln = ll.link_loop_next
 653             # if there is same pair, skip it
 654             found = False
 655             for p in pairs:
 656                 if (ll in p) and (lln in p):
 657                     found = True
 658                     break
 659             # two loops must be selected
 660             if ll[uv_layer].select and lln[uv_layer].select:
 661                 if not found:
 662                     pairs.append([ll, lln])
 663                 if (lln not in parsed) and (lln not in loops_ready):
 664                     loops_ready.append(lln)
 665
 666             # backward direction
 667             llp = ll.link_loop_prev
 668             # if there is same pair, skip it
 669             found = False
 670             for p in pairs:
 671                 if (ll in p) and (llp in p):
 672                     found = True
 673                     break
 674             # two loops must be selected
 675             if ll[uv_layer].select and llp[uv_layer].select:
 676                 if not found:
 677                     pairs.append([ll, llp])
 678                 if (llp not in parsed) and (llp not in loops_ready):
 679                     loops_ready.append(llp)
 680
 681     return pairs
 682
 683
 684 # sort pair by vertex
 685 # (v0, v1) - (v1, v2) - (v2, v3) ....
 686 def __sort_loop_pairs(uv_layer, pairs, closed):
 687     rest = pairs
 688     sorted_pairs = [rest[0]]
 689     rest.remove(rest[0])
 690
 691     # prepend
 692     while True:
 693         p1 = sorted_pairs[0]
 694         for p2 in rest:
 695             if p1[0].vert == p2[0].vert:
 696                 sorted_pairs.insert(0, [p2[1], p2[0]])
 697                 rest.remove(p2)
 698                 break
 699             elif p1[0].vert == p2[1].vert:
 700                 sorted_pairs.insert(0, [p2[0], p2[1]])
 701                 rest.remove(p2)
 702                 break
 703         else:
 704             break
 705
 706     # append
 707     while True:
 708         p1 = sorted_pairs[-1]
 709         for p2 in rest:
 710             if p1[1].vert == p2[0].vert:
 711                 sorted_pairs.append([p2[0], p2[1]])
 712                 rest.remove(p2)
 713                 break
 714             elif p1[1].vert == p2[1].vert:
 715                 sorted_pairs.append([p2[1], p2[0]])
 716                 rest.remove(p2)
 717                 break
 718         else:
 719             break
 720
 721     begin_vert = sorted_pairs[0][0].vert
 722     end_vert = sorted_pairs[-1][-1].vert
 723     if begin_vert != end_vert:
 724         return sorted_pairs, ""
 725     if closed and (begin_vert == end_vert):
 726         # if the sequence of UV is circular, it is ok
 727         return sorted_pairs, ""
 728
 729     # if the begin vertex and the end vertex are same, search the UVs which
 730     # are separated each other
 731     tmp_pairs = sorted_pairs
 732     for i, (p1, p2) in enumerate(zip(tmp_pairs[:-1], tmp_pairs[1:])):
 733         diff = p2[0][uv_layer].uv - p1[-1][uv_layer].uv
 734         if diff.length > 0.000000001:
 735             # UVs are separated
 736             sorted_pairs = tmp_pairs[i + 1:]
 737             sorted_pairs.extend(tmp_pairs[:i + 1])
 738             break
 739     else:
 740         p1 = tmp_pairs[0]
 741         p2 = tmp_pairs[-1]
 742         diff = p2[-1][uv_layer].uv - p1[0][uv_layer].uv
 743         if diff.length < 0.000000001:
 744             # all UVs are not separated
 745             return None, "All UVs are not separated"
 746
 747     return sorted_pairs, ""
 748
 749
 750 # get index of the island group which includes loop
 751 def __get_island_group_include_loop(loop, island_info):
 752     for i, isl in enumerate(island_info):
 753         for f in isl['faces']:
 754             for l in f['face'].loops:
 755                 if l == loop:
 756                     return i    # found
 757
 758     return -1   # not found
 759
 760
 761 # get index of the island group which includes pair.
 762 # if island group is not same between loops, it will be invalid
 763 def __get_island_group_include_pair(pair, island_info):
 764     l1_grp = __get_island_group_include_loop(pair[0], island_info)
 765     if l1_grp == -1:
 766         return -1   # not found
 767
 768     for p in pair[1:]:
 769         l2_grp = __get_island_group_include_loop(p, island_info)
 770         if (l2_grp == -1) or (l1_grp != l2_grp):
 771             return -1   # not found or invalid
 772
 773     return l1_grp
 774
 775
 776 # x ---- x   <- next_loop_pair
 777 # |      |
 778 # o ---- o   <- pair
 779 def __get_next_loop_pair(pair):
 780     lp = pair[0].link_loop_prev
 781     if lp.vert == pair[1].vert:
 782         lp = pair[0].link_loop_next
 783         if lp.vert == pair[1].vert:
 784             # no loop is found
 785             return None
 786
 787     ln = pair[1].link_loop_next
 788     if ln.vert == pair[0].vert:
 789         ln = pair[1].link_loop_prev
 790         if ln.vert == pair[0].vert:
 791             # no loop is found
 792             return None
 793
 794     # tri-face
 795     if lp == ln:
 796         return [lp]
 797
 798     # quad-face
 799     return [lp, ln]
 800
 801
 802 # | ---- |
 803 # % ---- %   <- next_poly_loop_pair
 804 # x ---- x   <- next_loop_pair
 805 # |      |
 806 # o ---- o   <- pair
 807 def __get_next_poly_loop_pair(pair):
 808     v1 = pair[0].vert
 809     v2 = pair[1].vert
 810     for l1 in v1.link_loops:
 811         if l1 == pair[0]:
 812             continue
 813         for l2 in v2.link_loops:
 814             if l2 == pair[1]:
 815                 continue
 816             if l1.link_loop_next == l2:
 817                 return [l1, l2]
 818             elif l1.link_loop_prev == l2:
 819                 return [l1, l2]
 820
 821     # no next poly loop is found
 822     return None
 823
 824
 825 # get loop sequence in the same island
 826 def __get_loop_sequence_internal(uv_layer, pairs, island_info, closed):
 827     loop_sequences = []
 828     for pair in pairs:
 829         seqs = [pair]
 830         p = pair
 831         isl_grp = __get_island_group_include_pair(pair, island_info)
 832         if isl_grp == -1:
 833             return None, "Can not find the island or invalid island"
 834
 835         while True:
 836             nlp = __get_next_loop_pair(p)
 837             if not nlp:
 838                 break       # no more loop pair
 839             nlp_isl_grp = __get_island_group_include_pair(nlp, island_info)
 840             if nlp_isl_grp != isl_grp:
 841                 break       # another island
 842             for nlpl in nlp:
 843                 if nlpl[uv_layer].select:
 844                     return None, "Do not select UV which does not belong to " \
 845                                  "the end edge"
 846
 847             seqs.append(nlp)
 848
 849             # when face is triangle, it indicates CLOSED
 850             if (len(nlp) == 1) and closed:
 851                 break
 852
 853             nplp = __get_next_poly_loop_pair(nlp)
 854             if not nplp:
 855                 break       # no more loop pair
 856             nplp_isl_grp = __get_island_group_include_pair(nplp, island_info)
 857             if nplp_isl_grp != isl_grp:
 858                 break       # another island
 859
 860             # check if the UVs are already parsed.
 861             # this check is needed for the mesh which has the circular
 862             # sequence of the vertices
 863             matched = False
 864             for p1 in seqs:
 865                 p2 = nplp
 866                 if ((p1[0] == p2[0]) and (p1[1] == p2[1])) or \
 867                    ((p1[0] == p2[1]) and (p1[1] == p2[0])):
 868                     matched = True
 869             if matched:
 870                 debug_print("This is a circular sequence")
 871                 break
 872
 873             for nlpl in nplp:
 874                 if nlpl[uv_layer].select:
 875                     return None, "Do not select UV which does not belong to " \
 876                                  "the end edge"
 877
 878             seqs.append(nplp)
 879
 880             p = nplp
 881
 882         loop_sequences.append(seqs)
 883     return loop_sequences, ""
 884
 885
 886 def get_loop_sequences(bm, uv_layer, closed=False):
 887     sel_faces = [f for f in bm.faces if f.select]
 888
 889     # get candidate loops
 890     cand_loops = []
 891     for f in sel_faces:
 892         for l in f.loops:
 893             if l[uv_layer].select:
 894                 cand_loops.append(l)
 895
 896     if len(cand_loops) < 2:
 897         return None, "More than 2 UVs must be selected"
 898
 899     first_loop = cand_loops[0]
 900     isl_info = get_island_info_from_bmesh(bm, False)
 901     loop_pairs = __get_loop_pairs(first_loop, uv_layer)
 902     loop_pairs, err = __sort_loop_pairs(uv_layer, loop_pairs, closed)
 903     if not loop_pairs:
 904         return None, err
 905     loop_seqs, err = __get_loop_sequence_internal(uv_layer, loop_pairs,
 906                                                   isl_info, closed)
 907     if not loop_seqs:
 908         return None, err
 909
 910     return loop_seqs, ""
 911
 912
 913 def __is_segment_intersect(start1, end1, start2, end2):
 914     seg1 = end1 - start1
 915     seg2 = end2 - start2
 916
 917     a1 = -seg1.y
 918     b1 = seg1.x
 919     d1 = -(a1 * start1.x + b1 * start1.y)
 920
 921     a2 = -seg2.y
 922     b2 = seg2.x
 923     d2 = -(a2 * start2.x + b2 * start2.y)
 924
 925     seg1_line2_start = a2 * start1.x + b2 * start1.y + d2
 926     seg1_line2_end = a2 * end1.x + b2 * end1.y + d2
 927
 928     seg2_line1_start = a1 * start2.x + b1 * start2.y + d1
 929     seg2_line1_end = a1 * end2.x + b1 * end2.y + d1
 930
 931     if (seg1_line2_start * seg1_line2_end >= 0) or \
 932             (seg2_line1_start * seg2_line1_end >= 0):
 933         return False, None
 934
 935     u = seg1_line2_start / (seg1_line2_start - seg1_line2_end)
 936     out = start1 + u * seg1
 937
 938     return True, out
 939
 940
 941 class RingBuffer:
 942     def __init__(self, arr):
 943         self.__buffer = arr.copy()
 944         self.__pointer = 0
 945
 946     def __repr__(self):
 947         return repr(self.__buffer)
 948
 949     def __len__(self):
 950         return len(self.__buffer)
 951
 952     def insert(self, val, offset=0):
 953         self.__buffer.insert(self.__pointer + offset, val)
 954
 955     def head(self):
 956         return self.__buffer[0]
 957
 958     def tail(self):
 959         return self.__buffer[-1]
 960
 961     def get(self, offset=0):
 962         size = len(self.__buffer)
 963         val = self.__buffer[(self.__pointer + offset) % size]
 964         return val
 965
 966     def next(self):
 967         size = len(self.__buffer)
 968         self.__pointer = (self.__pointer + 1) % size
 969
 970     def reset(self):
 971         self.__pointer = 0
 972
 973     def find(self, obj):
 974         try:
 975             idx = self.__buffer.index(obj)
 976         except ValueError:
 977             return None
 978         return self.__buffer[idx]
 979
 980     def find_and_next(self, obj):
 981         size = len(self.__buffer)
 982         idx = self.__buffer.index(obj)
 983         self.__pointer = (idx + 1) % size
 984
 985     def find_and_set(self, obj):
 986         idx = self.__buffer.index(obj)
 987         self.__pointer = idx
 988
 989     def as_list(self):
 990         return self.__buffer.copy()
 991
 992     def reverse(self):
 993         self.__buffer.reverse()
 994         self.reset()
 995
 996
 997 # clip: reference polygon
 998 # subject: tested polygon
 999 def __do_weiler_atherton_cliping(clip_uvs, subject_uvs, mode,
1000                                  same_polygon_threshold):
1001
1002     clip_uvs = RingBuffer(clip_uvs)
1003     if __is_polygon_flipped(clip_uvs):
1004         clip_uvs.reverse()
1005     subject_uvs = RingBuffer(subject_uvs)
1006     if __is_polygon_flipped(subject_uvs):
1007         subject_uvs.reverse()
1008
1009     debug_print("===== Clip UV List =====")
1010     debug_print(clip_uvs)
1011     debug_print("===== Subject UV List =====")
1012     debug_print(subject_uvs)
1013
1014     # check if clip and subject is overlapped completely
1015     if __is_polygon_same(clip_uvs, subject_uvs, same_polygon_threshold):
1016         polygons = [subject_uvs.as_list()]
1017         debug_print("===== Polygons Overlapped Completely =====")
1018         debug_print(polygons)
1019         return True, polygons
1020
1021     # check if subject is in clip
1022     if __is_points_in_polygon(subject_uvs, clip_uvs):
1023         polygons = [subject_uvs.as_list()]
1024         return True, polygons
1025
1026     # check if clip is in subject
1027     if __is_points_in_polygon(clip_uvs, subject_uvs):
1028         polygons = [subject_uvs.as_list()]
1029         return True, polygons
1030
1031     # check if clip and subject is overlapped partially
1032     intersections = []
1033     while True:
1034         subject_uvs.reset()
1035         while True:
1036             uv_start1 = clip_uvs.get()
1037             uv_end1 = clip_uvs.get(1)
1038             uv_start2 = subject_uvs.get()
1039             uv_end2 = subject_uvs.get(1)
1040             intersected, point = __is_segment_intersect(uv_start1, uv_end1,
1041                                                         uv_start2, uv_end2)
1042             if intersected:
1043                 clip_uvs.insert(point, 1)
1044                 subject_uvs.insert(point, 1)
1045                 intersections.append([point,
1046                                       [clip_uvs.get(), clip_uvs.get(1)]])
1047             subject_uvs.next()
1048             if subject_uvs.get() == subject_uvs.head():
1049                 break
1050         clip_uvs.next()
1051         if clip_uvs.get() == clip_uvs.head():
1052             break
1053
1054     debug_print("===== Intersection List =====")
1055     debug_print(intersections)
1056
1057     # no intersection, so subject and clip is not overlapped
1058     if not intersections:
1059         return False, None
1060
1061     def get_intersection_pair(intersects, key):
1062         for sect in intersects:
1063             if sect[0] == key:
1064                 return sect[1]
1065
1066         return None
1067
1068     # make enter/exit pair
1069     subject_uvs.reset()
1070     subject_entering = []
1071     subject_exiting = []
1072     clip_entering = []
1073     clip_exiting = []
1074     intersect_uv_list = []
1075     while True:
1076         pair = get_intersection_pair(intersections, subject_uvs.get())
1077         if pair:
1078             sub = subject_uvs.get(1) - subject_uvs.get(-1)
1079             inter = pair[1] - pair[0]
1080             cross = sub.x * inter.y - inter.x * sub.y
1081             if cross < 0:
1082                 subject_entering.append(subject_uvs.get())
1083                 clip_exiting.append(subject_uvs.get())
1084             else:
1085                 subject_exiting.append(subject_uvs.get())
1086                 clip_entering.append(subject_uvs.get())
1087             intersect_uv_list.append(subject_uvs.get())
1088
1089         subject_uvs.next()
1090         if subject_uvs.get() == subject_uvs.head():
1091             break
1092
1093     debug_print("===== Enter List =====")
1094     debug_print(clip_entering)
1095     debug_print(subject_entering)
1096     debug_print("===== Exit List =====")
1097     debug_print(clip_exiting)
1098     debug_print(subject_exiting)
1099
1100     # for now, can't handle the situation when fulfill all below conditions
1101     #        * two faces have common edge
1102     #        * each face is intersected
1103     #        * Show Mode is "Part"
1104     #       so for now, ignore this situation
1105     if len(subject_entering) != len(subject_exiting):
1106         if mode == 'FACE':
1107             polygons = [subject_uvs.as_list()]
1108             return True, polygons
1109         return False, None
1110
1111     def traverse(current_list, entering, exiting, p, current, other_list):
1112         result = current_list.find(current)
1113         if not result:
1114             return None
1115         if result != current:
1116             print("Internal Error")
1117             return None
1118         if not exiting:
1119             print("Internal Error: No exiting UV")
1120             return None
1121
1122         # enter
1123         if entering.count(current) >= 1:
1124             entering.remove(current)
1125
1126         current_list.find_and_next(current)
1127         current = current_list.get()
1128
1129         prev = None
1130         error = False
1131         while exiting.count(current) == 0:
1132             p.append(current.copy())
1133             current_list.find_and_next(current)
1134             current = current_list.get()
1135             if prev == current:
1136                 error = True
1137                 break
1138             prev = current
1139
1140         if error:
1141             print("Internal Error: Infinite loop")
1142             return None
1143
1144         # exit
1145         p.append(current.copy())
1146         exiting.remove(current)
1147
1148         other_list.find_and_set(current)
1149         return other_list.get()
1150
1151     # Traverse
1152     polygons = []
1153     current_uv_list = subject_uvs
1154     other_uv_list = clip_uvs
1155     current_entering = subject_entering
1156     current_exiting = subject_exiting
1157
1158     poly = []
1159     current_uv = current_entering[0]
1160
1161     while True:
1162         current_uv = traverse(current_uv_list, current_entering,
1163                               current_exiting, poly, current_uv, other_uv_list)
1164
1165         if current_uv is None:
1166             break
1167
1168         if current_uv_list == subject_uvs:
1169             current_uv_list = clip_uvs
1170             other_uv_list = subject_uvs
1171             current_entering = clip_entering
1172             current_exiting = clip_exiting
1173             debug_print("-- Next: Clip --")
1174         else:
1175             current_uv_list = subject_uvs
1176             other_uv_list = clip_uvs
1177             current_entering = subject_entering
1178             current_exiting = subject_exiting
1179             debug_print("-- Next: Subject --")
1180
1181         debug_print(clip_entering)
1182         debug_print(clip_exiting)
1183         debug_print(subject_entering)
1184         debug_print(subject_exiting)
1185
1186         if not clip_entering and not clip_exiting \
1187                 and not subject_entering and not subject_exiting:
1188             break
1189
1190     polygons.append(poly)
1191
1192     debug_print("===== Polygons Overlapped Partially =====")
1193     debug_print(polygons)
1194
1195     return True, polygons
1196
1197
1198 def __is_polygon_flipped(points):
1199     area = 0.0
1200     for i in range(len(points)):
1201         uv1 = points.get(i)
1202         uv2 = points.get(i + 1)
1203         a = uv1.x * uv2.y - uv1.y * uv2.x
1204         area = area + a
1205     if area < 0:
1206         # clock-wise
1207         return True
1208     return False
1209
1210
1211 def __is_point_in_polygon(point, subject_points):
1212     """Return true when point is inside of the polygon by using
1213     'Crossing number algorithm'.
1214     """
1215
1216     count = 0
1217     for i in range(len(subject_points)):
1218         uv_start1 = subject_points.get(i)
1219         uv_end1 = subject_points.get(i + 1)
1220         uv_start2 = point
1221         uv_end2 = Vector((1000000.0, point.y))
1222
1223         # If the point exactly matches to the point of the polygon,
1224         # this point is not in polygon.
1225         if uv_start1.x == uv_start2.x and uv_start1.y == uv_start2.y:
1226             return False
1227
1228         intersected, _ = __is_segment_intersect(uv_start1, uv_end1,
1229                                                 uv_start2, uv_end2)
1230         if intersected:
1231             count = count + 1
1232
1233     return count % 2
1234
1235
1236 def __is_points_in_polygon(points, subject_points):
1237     for i in range(len(points)):
1238         internal = __is_point_in_polygon(points.get(i), subject_points)
1239         if not internal:
1240             return False
1241
1242     return True
1243
1244
1245 def get_uv_editable_objects(context):
1246     if compat.check_version(2, 80, 0) < 0:
1247         objs = []
1248     else:
1249         objs = [o for o in bpy.data.objects
1250                 if compat.get_object_select(o) and o.type == 'MESH']
1251
1252     ob = context.active_object
1253     if ob is not None:
1254         objs.append(ob)
1255
1256     objs = list(set(objs))
1257     return objs
1258
1259
1260 def get_overlapped_uv_info(bm_list, faces_list, uv_layer_list,
1261                            mode, same_polygon_threshold=0.0000001):
1262     # at first, check island overlapped
1263     isl = []
1264     for bm, uv_layer, faces in zip(bm_list, uv_layer_list, faces_list):
1265         info = get_island_info_from_faces(bm, faces, uv_layer)
1266         isl.extend([(i, uv_layer, bm) for i in info])
1267
1268     overlapped_isl_pairs = []
1269     overlapped_uv_layer_pairs = []
1270     overlapped_bm_paris = []
1271     for i, (i1, uv_layer_1, bm_1) in enumerate(isl):
1272         for i2, uv_layer_2, bm_2 in isl[i + 1:]:
1273             if (i1["max"].x < i2["min"].x) or (i2["max"].x < i1["min"].x) or \
1274                (i1["max"].y < i2["min"].y) or (i2["max"].y < i1["min"].y):
1275                 continue
1276             overlapped_isl_pairs.append([i1, i2])
1277             overlapped_uv_layer_pairs.append([uv_layer_1, uv_layer_2])
1278             overlapped_bm_paris.append([bm_1, bm_2])
1279
1280     # check polygon overlapped (inter UV islands)
1281     overlapped_uvs = []
1282     for oip, uvlp, bmp in zip(overlapped_isl_pairs,
1283                               overlapped_uv_layer_pairs,
1284                               overlapped_bm_paris):
1285         for clip in oip[0]["faces"]:
1286             f_clip = clip["face"]
1287             clip_uvs = [l[uvlp[0]].uv.copy() for l in f_clip.loops]
1288             for subject in oip[1]["faces"]:
1289                 f_subject = subject["face"]
1290
1291                 # fast operation, apply bounding box algorithm
1292                 if (clip["max_uv"].x < subject["min_uv"].x) or \
1293                    (subject["max_uv"].x < clip["min_uv"].x) or \
1294                    (clip["max_uv"].y < subject["min_uv"].y) or \
1295                    (subject["max_uv"].y < clip["min_uv"].y):
1296                     continue
1297
1298                 subject_uvs = [l[uvlp[1]].uv.copy() for l in f_subject.loops]
1299                 # slow operation, apply Weiler-Atherton cliping algorithm
1300                 result, polygons = \
1301                     __do_weiler_atherton_cliping(clip_uvs, subject_uvs,
1302                                                  mode, same_polygon_threshold)
1303                 if result:
1304                     overlapped_uvs.append({"clip_bmesh": bmp[0],
1305                                            "subject_bmesh": bmp[1],
1306                                            "clip_face": f_clip,
1307                                            "subject_face": f_subject,
1308                                            "clip_uv_layer": uvlp[0],
1309                                            "subject_uv_layer": uvlp[1],
1310                                            "subject_uvs": subject_uvs,
1311                                            "polygons": polygons})
1312
1313     # check polygon overlapped (intra UV island)
1314     for info, uv_layer, bm in isl:
1315         for i in range(len(info["faces"])):
1316             clip = info["faces"][i]
1317             f_clip = clip["face"]
1318             clip_uvs = [l[uv_layer].uv.copy() for l in f_clip.loops]
1319             for j in range(len(info["faces"])):
1320                 if j <= i:
1321                     continue
1322
1323                 subject = info["faces"][j]
1324                 f_subject = subject["face"]
1325
1326                 # fast operation, apply bounding box algorithm
1327                 if (clip["max_uv"].x < subject["min_uv"].x) or \
1328                    (subject["max_uv"].x < clip["min_uv"].x) or \
1329                    (clip["max_uv"].y < subject["min_uv"].y) or \
1330                    (subject["max_uv"].y < clip["min_uv"].y):
1331                     continue
1332
1333                 subject_uvs = [l[uv_layer].uv.copy() for l in f_subject.loops]
1334                 # slow operation, apply Weiler-Atherton cliping algorithm
1335                 result, polygons = \
1336                     __do_weiler_atherton_cliping(clip_uvs, subject_uvs,
1337                                                  mode, same_polygon_threshold)
1338                 if result:
1339                     overlapped_uvs.append({"clip_bmesh": bm,
1340                                            "subject_bmesh": bm,
1341                                            "clip_face": f_clip,
1342                                            "subject_face": f_subject,
1343                                            "clip_uv_layer": uv_layer,
1344                                            "subject_uv_layer": uv_layer,
1345                                            "subject_uvs": subject_uvs,
1346                                            "polygons": polygons})
1347
1348     return overlapped_uvs
1349
1350
1351 def get_flipped_uv_info(bm_list, faces_list, uv_layer_list):
1352     flipped_uvs = []
1353     for bm, faces, uv_layer in zip(bm_list, faces_list, uv_layer_list):
1354         for f in faces:
1355             polygon = RingBuffer([l[uv_layer].uv.copy() for l in f.loops])
1356             if __is_polygon_flipped(polygon):
1357                 uvs = [l[uv_layer].uv.copy() for l in f.loops]
1358                 flipped_uvs.append({"bmesh": bm,
1359                                     "face": f,
1360                                     "uv_layer": uv_layer,
1361                                     "uvs": uvs,
1362                                     "polygons": [polygon.as_list()]})
1363
1364     return flipped_uvs
1365
1366
1367 def __is_polygon_same(points1, points2, threshold):
1368     if len(points1) != len(points2):
1369         return False
1370
1371     pts1 = points1.as_list()
1372     pts2 = points2.as_list()
1373
1374     for p1 in pts1:
1375         for p2 in pts2:
1376             diff = p2 - p1
1377             if diff.length < threshold:
1378                 pts2.remove(p2)
1379                 break
1380         else:
1381             return False
1382
1383     return True
1384
1385
1386 def _is_uv_loop_connected(l1, l2, uv_layer):
1387     uv1 = l1[uv_layer].uv
1388     uv2 = l2[uv_layer].uv
1389     return uv1.x == uv2.x and uv1.y == uv2.y
1390
1391
1392 def create_uv_graph(loops, uv_layer):
1393     # For looking up faster.
1394     loop_index_to_loop = {}     # { loop index: loop }
1395     for l in loops:
1396         loop_index_to_loop[l.index] = l
1397
1398     # Setup relationship between uv_vert and loops.
1399     # uv_vert is a representative of the loops which shares same
1400     # UV coordinate.
1401     uv_vert_to_loops = {}   # { uv_vert: loops belonged to uv_vert }
1402     loop_to_uv_vert = {}    # { loop: uv_vert belonged to }
1403     for l in loops:
1404         found = False
1405         for k in uv_vert_to_loops.keys():
1406             if _is_uv_loop_connected(k, l, uv_layer):
1407                 uv_vert_to_loops[k].append(l)
1408                 loop_to_uv_vert[l] = k
1409                 found = True
1410                 break
1411         if not found:
1412             uv_vert_to_loops[l] = [l]
1413             loop_to_uv_vert[l] = l
1414
1415     # Collect adjacent uv_vert.
1416     uv_adj_verts = {}       # { uv_vert: adj uv_vert list }
1417     for v, vs in uv_vert_to_loops.items():
1418         uv_adj_verts[v] = []
1419         for ll in vs:
1420             ln = ll.link_loop_next
1421             lp = ll.link_loop_prev
1422             uv_adj_verts[v].append(loop_to_uv_vert[ln])
1423             uv_adj_verts[v].append(loop_to_uv_vert[lp])
1424         uv_adj_verts[v] = list(set(uv_adj_verts[v]))
1425
1426     # Setup uv_vert graph.
1427     graph = Graph()
1428     for v in uv_adj_verts.keys():
1429         graph.add_node(
1430             Node(v.index, {"uv_vert": v, "loops": uv_vert_to_loops[v]})
1431         )
1432     edges = []
1433     for v, adjs in uv_adj_verts.items():
1434         n1 = graph.get_node(v.index)
1435         for a in adjs:
1436             n2 = graph.get_node(a.index)
1437             edges.append(tuple(sorted((n1.key, n2.key))))
1438     edges = list(set(edges))
1439     for e in edges:
1440         n1 = graph.get_node(e[0])
1441         n2 = graph.get_node(e[1])
1442         graph.add_edge(n1, n2)
1443
1444     return graph