magic_uv/common.py

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