magic_uv/common.py

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