release/scripts/modules/bpy_extras/mesh_utils.py

   1 # ##### BEGIN GPL LICENSE BLOCK #####
   2 #
   3 #  This program is free software; you can redistribute it and/or
   4 #  modify it under the terms of the GNU General Public License
   5 #  as published by the Free Software Foundation; either version 2
   6 #  of the License, or (at your option) any later version.
   7 #
   8 #  This program is distributed in the hope that it will be useful,
   9 #  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 #  GNU General Public License for more details.
  12 #
  13 #  You should have received a copy of the GNU General Public License
  14 #  along with this program; if not, write to the Free Software Foundation,
  15 #  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16 #
  17 # ##### END GPL LICENSE BLOCK #####
  18
  19 # <pep8-80 compliant>
  20
  21 __all__ = (
  22     "mesh_linked_faces",
  23     "edge_face_count_dict",
  24     "edge_face_count",
  25     "edge_loops_from_faces",
  26     "edge_loops_from_edges",
  27     "ngon_tesselate",
  28     "face_random_points",
  29     )
  30
  31
  32 def mesh_linked_faces(mesh):
  33     """
  34     Splits the mesh into connected faces, use this for seperating cubes from
  35     other mesh elements within 1 mesh datablock.
  36
  37     :arg mesh: the mesh used to group with.
  38     :type mesh: :class:`bpy.types.Mesh`
  39     :return: lists of lists containing faces.
  40     :rtype: list
  41     """
  42
  43     # Build vert face connectivity
  44     vert_faces = [[] for i in range(len(mesh.vertices))]
  45     for f in mesh.faces:
  46         for v in f.vertices:
  47             vert_faces[v].append(f)
  48
  49     # sort faces into connectivity groups
  50     face_groups = [[f] for f in mesh.faces]
  51     face_mapping = list(range(len(mesh.faces)))  # map old, new face location
  52
  53     # Now clump faces iterativly
  54     ok = True
  55     while ok:
  56         ok = False
  57
  58         for i, f in enumerate(mesh.faces):
  59             mapped_index = face_mapping[f.index]
  60             mapped_group = face_groups[mapped_index]
  61
  62             for v in f.vertices:
  63                 for nxt_f in vert_faces[v]:
  64                     if nxt_f != f:
  65                         nxt_mapped_index = face_mapping[nxt_f.index]
  66
  67                         # We are not a part of the same group
  68                         if mapped_index != nxt_mapped_index:
  69                             ok = True
  70
  71                             # Assign mapping to this group so they
  72                             # all map to this group
  73                             for grp_f in face_groups[nxt_mapped_index]:
  74                                 face_mapping[grp_f.index] = mapped_index
  75
  76                             # Move faces into this group
  77                             mapped_group.extend(face_groups[nxt_mapped_index])
  78
  79                             # remove reference to the list
  80                             face_groups[nxt_mapped_index] = None
  81
  82     # return all face groups that are not null
  83     # this is all the faces that are connected in their own lists.
  84     return [fg for fg in face_groups if fg]
  85
  86
  87 def edge_face_count_dict(mesh):
  88     """
  89     :return: dict of edge keys with their value set to the number of
  90        faces using each edge.
  91     :rtype: dict
  92     """
  93     face_edge_keys = [face.edge_keys for face in mesh.faces]
  94     face_edge_count = {}
  95     for face_keys in face_edge_keys:
  96         for key in face_keys:
  97             try:
  98                 face_edge_count[key] += 1
  99             except:
 100                 face_edge_count[key] = 1
 101
 102     return face_edge_count
 103
 104
 105 def edge_face_count(mesh):
 106     """
 107     :return: list face users for each item in mesh.edges.
 108     :rtype: list
 109     """
 110     edge_face_count = edge_face_count_dict(mesh)
 111     get = dict.get
 112     return [get(edge_face_count, ed.key, 0) for ed in mesh.edges]
 113
 114
 115 def edge_loops_from_faces(mesh, faces=None, seams=()):
 116     """
 117     Edge loops defined by faces
 118
 119     Takes me.faces or a list of faces and returns the edge loops
 120     These edge loops are the edges that sit between quads, so they dont touch
 121     1 quad, note: not connected will make 2 edge loops,
 122     both only containing 2 edges.
 123
 124     return a list of edge key lists
 125     [[(0, 1), (4, 8), (3, 8)], ...]
 126
 127     :arg mesh: the mesh used to get edge loops from.
 128     :type mesh: :class:`bpy.types.Mesh`
 129     :arg faces: optional face list to only use some of the meshes faces.
 130     :type faces: :class:`bpy.types.MeshFaces`, sequence or or NoneType
 131     :return: return a list of edge vertex index lists.
 132     :rtype: list
 133     """
 134
 135     OTHER_INDEX = 2, 3, 0, 1  # opposite face index
 136
 137     if faces is None:
 138         faces = mesh.faces
 139
 140     edges = {}
 141
 142     for f in faces:
 143 #        if len(f) == 4:
 144         if f.vertices_raw[3] != 0:
 145             edge_keys = f.edge_keys
 146             for i, edkey in enumerate(f.edge_keys):
 147                 edges.setdefault(edkey, []).append(edge_keys[OTHER_INDEX[i]])
 148
 149     for edkey in seams:
 150         edges[edkey] = []
 151
 152     # Collect edge loops here
 153     edge_loops = []
 154
 155     for edkey, ed_adj in edges.items():
 156         if 0 < len(ed_adj) < 3:  # 1 or 2
 157             # Seek the first edge
 158             context_loop = [edkey, ed_adj[0]]
 159             edge_loops.append(context_loop)
 160             if len(ed_adj) == 2:
 161                 other_dir = ed_adj[1]
 162             else:
 163                 other_dir = None
 164
 165             ed_adj[:] = []
 166
 167             flipped = False
 168
 169             while 1:
 170                 # from knowing the last 2, look for th next.
 171                 ed_adj = edges[context_loop[-1]]
 172                 if len(ed_adj) != 2:
 173                     # the original edge had 2 other edges
 174                     if other_dir and flipped == False:
 175                         flipped = True  # only flip the list once
 176                         context_loop.reverse()
 177                         ed_adj[:] = []
 178                         context_loop.append(other_dir)  # save 1 lookiup
 179
 180                         ed_adj = edges[context_loop[-1]]
 181                         if len(ed_adj) != 2:
 182                             ed_adj[:] = []
 183                             break
 184                     else:
 185                         ed_adj[:] = []
 186                         break
 187
 188                 i = ed_adj.index(context_loop[-2])
 189                 context_loop.append(ed_adj[not  i])
 190
 191                 # Dont look at this again
 192                 ed_adj[:] = []
 193
 194     return edge_loops
 195
 196
 197 def edge_loops_from_edges(mesh, edges=None):
 198     """
 199     Edge loops defined by edges
 200
 201     Takes me.edges or a list of edges and returns the edge loops
 202
 203     return a list of vertex indices.
 204     [ [1, 6, 7, 2], ...]
 205
 206     closed loops have matching start and end values.
 207     """
 208     line_polys = []
 209
 210     # Get edges not used by a face
 211     if edges is None:
 212         edges = mesh.edges
 213
 214     if not hasattr(edges, "pop"):
 215         edges = edges[:]
 216
 217     while edges:
 218         current_edge = edges.pop()
 219         vert_end, vert_start = current_edge.vertices[:]
 220         line_poly = [vert_start, vert_end]
 221
 222         ok = True
 223         while ok:
 224             ok = False
 225             #for i, ed in enumerate(edges):
 226             i = len(edges)
 227             while i:
 228                 i -= 1
 229                 ed = edges[i]
 230                 v1, v2 = ed.vertices
 231                 if v1 == vert_end:
 232                     line_poly.append(v2)
 233                     vert_end = line_poly[-1]
 234                     ok = 1
 235                     del edges[i]
 236                     # break
 237                 elif v2 == vert_end:
 238                     line_poly.append(v1)
 239                     vert_end = line_poly[-1]
 240                     ok = 1
 241                     del edges[i]
 242                     #break
 243                 elif v1 == vert_start:
 244                     line_poly.insert(0, v2)
 245                     vert_start = line_poly[0]
 246                     ok = 1
 247                     del edges[i]
 248                     # break
 249                 elif v2 == vert_start:
 250                     line_poly.insert(0, v1)
 251                     vert_start = line_poly[0]
 252                     ok = 1
 253                     del edges[i]
 254                     #break
 255         line_polys.append(line_poly)
 256
 257     return line_polys
 258
 259
 260 def ngon_tesselate(from_data, indices, fix_loops=True):
 261     '''
 262     Takes a polyline of indices (fgon) and returns a list of face
 263     indicie lists. Designed to be used for importers that need indices for an
 264     fgon to create from existing verts.
 265
 266     from_data: either a mesh, or a list/tuple of vectors.
 267     indices: a list of indices to use this list is the ordered closed polyline
 268        to fill, and can be a subset of the data given.
 269     fix_loops: If this is enabled polylines that use loops to make multiple
 270        polylines are delt with correctly.
 271     '''
 272
 273     from mathutils.geometry import tesselate_polygon
 274     from mathutils import Vector
 275     vector_to_tuple = Vector.to_tuple
 276
 277     if not indices:
 278         return []
 279
 280     def mlen(co):
 281         # manhatten length of a vector, faster then length
 282         return abs(co[0]) + abs(co[1]) + abs(co[2])
 283
 284     def vert_treplet(v, i):
 285         return v, vector_to_tuple(v, 6), i, mlen(v)
 286
 287     def ed_key_mlen(v1, v2):
 288         if v1[3] > v2[3]:
 289             return v2[1], v1[1]
 290         else:
 291             return v1[1], v2[1]
 292
 293     if not fix_loops:
 294         '''
 295         Normal single concave loop filling
 296         '''
 297         if type(from_data) in {tuple, list}:
 298             verts = [Vector(from_data[i]) for ii, i in enumerate(indices)]
 299         else:
 300             verts = [from_data.vertices[i].co for ii, i in enumerate(indices)]
 301
 302         # same as reversed(range(1, len(verts))):
 303         for i in range(len(verts) - 1, 0, -1):
 304             if verts[i][1] == verts[i - 1][0]:
 305                 verts.pop(i - 1)
 306
 307         fill = tesselate_polygon([verts])
 308
 309     else:
 310         '''
 311         Seperate this loop into multiple loops be finding edges that are
 312         used twice. This is used by lightwave LWO files a lot
 313         '''
 314
 315         if type(from_data) in {tuple, list}:
 316             verts = [vert_treplet(Vector(from_data[i]), ii)
 317                      for ii, i in enumerate(indices)]
 318         else:
 319             verts = [vert_treplet(from_data.vertices[i].co, ii)
 320                      for ii, i in enumerate(indices)]
 321
 322         edges = [(i, i - 1) for i in range(len(verts))]
 323         if edges:
 324             edges[0] = (0, len(verts) - 1)
 325
 326         if not verts:
 327             return []
 328
 329         edges_used = set()
 330         edges_doubles = set()
 331         # We need to check if any edges are used twice location based.
 332         for ed in edges:
 333             edkey = ed_key_mlen(verts[ed[0]], verts[ed[1]])
 334             if edkey in edges_used:
 335                 edges_doubles.add(edkey)
 336             else:
 337                 edges_used.add(edkey)
 338
 339         # Store a list of unconnected loop segments split by double edges.
 340         # will join later
 341         loop_segments = []
 342
 343         v_prev = verts[0]
 344         context_loop = [v_prev]
 345         loop_segments = [context_loop]
 346
 347         for v in verts:
 348             if v != v_prev:
 349                 # Are we crossing an edge we removed?
 350                 if ed_key_mlen(v, v_prev) in edges_doubles:
 351                     context_loop = [v]
 352                     loop_segments.append(context_loop)
 353                 else:
 354                     if context_loop and context_loop[-1][1] == v[1]:
 355                         #raise "as"
 356                         pass
 357                     else:
 358                         context_loop.append(v)
 359
 360                 v_prev = v
 361         # Now join loop segments
 362
 363         def join_seg(s1, s2):
 364             if s2[-1][1] == s1[0][1]:
 365                 s1, s2 = s2, s1
 366             elif s1[-1][1] == s2[0][1]:
 367                 pass
 368             else:
 369                 return False
 370
 371             # If were stuill here s1 and s2 are 2 segments in the same polyline
 372             s1.pop()  # remove the last vert from s1
 373             s1.extend(s2)  # add segment 2 to segment 1
 374
 375             if s1[0][1] == s1[-1][1]:  # remove endpoints double
 376                 s1.pop()
 377
 378             s2[:] = []  # Empty this segment s2 so we dont use it again.
 379             return True
 380
 381         joining_segments = True
 382         while joining_segments:
 383             joining_segments = False
 384             segcount = len(loop_segments)
 385
 386             for j in range(segcount - 1, -1, -1):  # reversed(range(segcount)):
 387                 seg_j = loop_segments[j]
 388                 if seg_j:
 389                     for k in range(j - 1, -1, -1):  # reversed(range(j)):
 390                         if not seg_j:
 391                             break
 392                         seg_k = loop_segments[k]
 393
 394                         if seg_k and join_seg(seg_j, seg_k):
 395                             joining_segments = True
 396
 397         loop_list = loop_segments
 398
 399         for verts in loop_list:
 400             while verts and verts[0][1] == verts[-1][1]:
 401                 verts.pop()
 402
 403         loop_list = [verts for verts in loop_list if len(verts) > 2]
 404         # DONE DEALING WITH LOOP FIXING
 405
 406         # vert mapping
 407         vert_map = [None] * len(indices)
 408         ii = 0
 409         for verts in loop_list:
 410             if len(verts) > 2:
 411                 for i, vert in enumerate(verts):
 412                     vert_map[i + ii] = vert[2]
 413                 ii += len(verts)
 414
 415         fill = tesselate_polygon([[v[0] for v in loop] for loop in loop_list])
 416         #draw_loops(loop_list)
 417         #raise 'done loop'
 418         # map to original indices
 419         fill = [[vert_map[i] for i in reversed(f)] for f in fill]
 420
 421     if not fill:
 422         print('Warning Cannot scanfill, fallback on a triangle fan.')
 423         fill = [[0, i - 1, i] for i in range(2, len(indices))]
 424     else:
 425         # Use real scanfill.
 426         # See if its flipped the wrong way.
 427         flip = None
 428         for fi in fill:
 429             if flip is not None:
 430                 break
 431             for i, vi in enumerate(fi):
 432                 if vi == 0 and fi[i - 1] == 1:
 433                     flip = False
 434                     break
 435                 elif vi == 1 and fi[i - 1] == 0:
 436                     flip = True
 437                     break
 438
 439         if not flip:
 440             for i, fi in enumerate(fill):
 441                 fill[i] = tuple([ii for ii in reversed(fi)])
 442
 443     return fill
 444
 445
 446 def face_random_points(num_points, faces):
 447     """
 448     Generates a list of random points over mesh faces.
 449
 450     :arg num_points: the number of random points to generate on each face.
 451     :type int:
 452     :arg faces: list of the faces to generate points on.
 453     :type faces: :class:`bpy.types.MeshFaces`, sequence
 454     :return: list of random points over all faces.
 455     :rtype: list
 456     """
 457
 458     from random import random
 459     from mathutils.geometry import area_tri
 460
 461     # Split all quads into 2 tris, tris remain unchanged
 462     tri_faces = []
 463     for f in faces:
 464         tris = []
 465         verts = f.id_data.vertices
 466         fv = f.vertices[:]
 467         tris.append((verts[fv[0]].co,
 468                      verts[fv[1]].co,
 469                      verts[fv[2]].co,
 470                     ))
 471         if len(fv) == 4:
 472             tris.append((verts[fv[0]].co,
 473                          verts[fv[3]].co,
 474                          verts[fv[2]].co,
 475                         ))
 476         tri_faces.append(tris)
 477
 478     # For each face, generate the required number of random points
 479     sampled_points = [None] * (num_points * len(faces))
 480     for i, tf in enumerate(tri_faces):
 481         for k in range(num_points):
 482             # If this is a quad, we need to weight its 2 tris by their area
 483             if len(tf) != 1:
 484                 area1 = area_tri(*tf[0])
 485                 area2 = area_tri(*tf[1])
 486                 area_tot = area1 + area2
 487
 488                 area1 = area1 / area_tot
 489                 area2 = area2 / area_tot
 490
 491                 vecs = tf[0 if (random() < area1) else 1]
 492             else:
 493                 vecs = tf[0]
 494
 495             u1 = random()
 496             u2 = random()
 497             u_tot = u1 + u2
 498
 499             if u_tot > 1:
 500                 u1 = 1.0 - u1
 501                 u2 = 1.0 - u2
 502
 503             side1 = vecs[1] - vecs[0]
 504             side2 = vecs[2] - vecs[0]
 505
 506             p = vecs[0] + u1 * side1 + u2 * side2
 507
 508             sampled_points[num_points * i + k] = p
 509
 510     return sampled_points