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 compliant>
  20
  21
  22 def mesh_linked_faces(mesh):
  23     '''
  24     Splits the mesh into connected parts,
  25     these parts are returned as lists of faces.
  26     used for seperating cubes from other mesh elements in the 1 mesh
  27     '''
  28
  29     # Build vert face connectivity
  30     vert_faces = [[] for i in range(len(mesh.vertices))]
  31     for f in mesh.faces:
  32         for v in f.vertices:
  33             vert_faces[v].append(f)
  34
  35     # sort faces into connectivity groups
  36     face_groups = [[f] for f in mesh.faces]
  37     face_mapping = list(range(len(mesh.faces)))  # map old, new face location
  38
  39     # Now clump faces iterativly
  40     ok = True
  41     while ok:
  42         ok = False
  43
  44         for i, f in enumerate(mesh.faces):
  45             mapped_index = face_mapping[f.index]
  46             mapped_group = face_groups[mapped_index]
  47
  48             for v in f.vertices:
  49                 for nxt_f in vert_faces[v]:
  50                     if nxt_f != f:
  51                         nxt_mapped_index = face_mapping[nxt_f.index]
  52
  53                         # We are not a part of the same group
  54                         if mapped_index != nxt_mapped_index:
  55                             ok = True
  56
  57                             # Assign mapping to this group so they all map to this group
  58                             for grp_f in face_groups[nxt_mapped_index]:
  59                                 face_mapping[grp_f.index] = mapped_index
  60
  61                             # Move faces into this group
  62                             mapped_group.extend(face_groups[nxt_mapped_index])
  63
  64                             # remove reference to the list
  65                             face_groups[nxt_mapped_index] = None
  66
  67     # return all face groups that are not null
  68     # this is all the faces that are connected in their own lists.
  69     return [fg for fg in face_groups if fg]
  70
  71
  72 def edge_face_count_dict(mesh):
  73     face_edge_keys = [face.edge_keys for face in mesh.faces]
  74     face_edge_count = {}
  75     for face_keys in face_edge_keys:
  76         for key in face_keys:
  77             try:
  78                 face_edge_count[key] += 1
  79             except:
  80                 face_edge_count[key] = 1
  81
  82     return face_edge_count
  83
  84
  85 def edge_face_count(mesh):
  86     edge_face_count_dict = edge_face_count_dict(mesh)
  87     return [edge_face_count_dict.get(ed.key, 0) for ed in mesh.edges]
  88
  89
  90 def edge_loops_from_faces(mesh, faces=None, seams=()):
  91     """
  92     Edge loops defined by faces
  93
  94     Takes me.faces or a list of faces and returns the edge loops
  95     These edge loops are the edges that sit between quads, so they dont touch
  96     1 quad, note: not connected will make 2 edge loops, both only containing 2 edges.
  97
  98     return a list of edge key lists
  99     [ [(0,1), (4, 8), (3,8)], ...]
 100
 101     return a list of edge vertex index lists
 102     """
 103
 104     OTHER_INDEX = 2, 3, 0, 1  # opposite face index
 105
 106     if faces is None:
 107         faces = mesh.faces
 108
 109     edges = {}
 110
 111     for f in faces:
 112 #            if len(f) == 4:
 113         if f.vertices_raw[3] != 0:
 114             edge_keys = f.edge_keys
 115             for i, edkey in enumerate(f.edge_keys):
 116                 edges.setdefault(edkey, []).append(edge_keys[OTHER_INDEX[i]])
 117
 118     for edkey in seams:
 119         edges[edkey] = []
 120
 121     # Collect edge loops here
 122     edge_loops = []
 123
 124     for edkey, ed_adj in edges.items():
 125         if 0 < len(ed_adj) < 3:  # 1 or 2
 126             # Seek the first edge
 127             context_loop = [edkey, ed_adj[0]]
 128             edge_loops.append(context_loop)
 129             if len(ed_adj) == 2:
 130                 other_dir = ed_adj[1]
 131             else:
 132                 other_dir = None
 133
 134             ed_adj[:] = []
 135
 136             flipped = False
 137
 138             while 1:
 139                 # from knowing the last 2, look for th next.
 140                 ed_adj = edges[context_loop[-1]]
 141                 if len(ed_adj) != 2:
 142
 143                     if other_dir and flipped == False:  # the original edge had 2 other edges
 144                         flipped = True  # only flip the list once
 145                         context_loop.reverse()
 146                         ed_adj[:] = []
 147                         context_loop.append(other_dir)  # save 1 lookiup
 148
 149                         ed_adj = edges[context_loop[-1]]
 150                         if len(ed_adj) != 2:
 151                             ed_adj[:] = []
 152                             break
 153                     else:
 154                         ed_adj[:] = []
 155                         break
 156
 157                 i = ed_adj.index(context_loop[-2])
 158                 context_loop.append(ed_adj[not  i])
 159
 160                 # Dont look at this again
 161                 ed_adj[:] = []
 162
 163     return edge_loops
 164
 165
 166 def edge_loops_from_edges(mesh, edges=None):
 167     """
 168     Edge loops defined by edges
 169
 170     Takes me.edges or a list of edges and returns the edge loops
 171
 172     return a list of vertex indices.
 173     [ [1, 6, 7, 2], ...]
 174
 175     closed loops have matching start and end values.
 176     """
 177     line_polys = []
 178
 179     # Get edges not used by a face
 180     if edges is None:
 181         edges = mesh.edges
 182
 183     if not hasattr(edges, "pop"):
 184         edges = edges[:]
 185
 186     edge_dict = {ed.key: ed for ed in mesh.edges if ed.select}
 187
 188     while edges:
 189         current_edge = edges.pop()
 190         vert_end, vert_start = current_edge.vertices[:]
 191         line_poly = [vert_start, vert_end]
 192
 193         ok = True
 194         while ok:
 195             ok = False
 196             #for i, ed in enumerate(edges):
 197             i = len(edges)
 198             while i:
 199                 i -= 1
 200                 ed = edges[i]
 201                 v1, v2 = ed.vertices
 202                 if v1 == vert_end:
 203                     line_poly.append(v2)
 204                     vert_end = line_poly[-1]
 205                     ok = 1
 206                     del edges[i]
 207                     # break
 208                 elif v2 == vert_end:
 209                     line_poly.append(v1)
 210                     vert_end = line_poly[-1]
 211                     ok = 1
 212                     del edges[i]
 213                     #break
 214                 elif v1 == vert_start:
 215                     line_poly.insert(0, v2)
 216                     vert_start = line_poly[0]
 217                     ok = 1
 218                     del edges[i]
 219                     # break
 220                 elif v2 == vert_start:
 221                     line_poly.insert(0, v1)
 222                     vert_start = line_poly[0]
 223                     ok = 1
 224                     del edges[i]
 225                     #break
 226         line_polys.append(line_poly)
 227
 228     return line_polys
 229
 230
 231 def ngon_tesselate(from_data, indices, fix_loops=True):
 232     '''
 233     Takes a polyline of indices (fgon)
 234     and returns a list of face indicie lists.
 235     Designed to be used for importers that need indices for an fgon to create from existing verts.
 236
 237     from_data: either a mesh, or a list/tuple of vectors.
 238     indices: a list of indices to use this list is the ordered closed polyline to fill, and can be a subset of the data given.
 239     fix_loops: If this is enabled polylines that use loops to make multiple polylines are delt with correctly.
 240     '''
 241
 242     from mathutils import Vector
 243     vector_to_tuple = Vector.to_tuple
 244
 245     if not indices:
 246         return []
 247
 248     def mlen(co):
 249         return abs(co[0]) + abs(co[1]) + abs(co[2])  # manhatten length of a vector, faster then length
 250
 251     def vert_treplet(v, i):
 252         return v, vector_to_tuple(v, 6), i, mlen(v)
 253
 254     def ed_key_mlen(v1, v2):
 255         if v1[3] > v2[3]:
 256             return v2[1], v1[1]
 257         else:
 258             return v1[1], v2[1]
 259
 260     if not PREF_FIX_LOOPS:
 261         '''
 262         Normal single concave loop filling
 263         '''
 264         if type(from_data) in (tuple, list):
 265             verts = [Vector(from_data[i]) for ii, i in enumerate(indices)]
 266         else:
 267             verts = [from_data.vertices[i].co for ii, i in enumerate(indices)]
 268
 269         for i in range(len(verts) - 1, 0, -1):  # same as reversed(xrange(1, len(verts))):
 270             if verts[i][1] == verts[i - 1][0]:
 271                 verts.pop(i - 1)
 272
 273         fill = fill_polygon([verts])
 274
 275     else:
 276         '''
 277         Seperate this loop into multiple loops be finding edges that are used twice
 278         This is used by lightwave LWO files a lot
 279         '''
 280
 281         if type(from_data) in (tuple, list):
 282             verts = [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)]
 283         else:
 284             verts = [vert_treplet(from_data.vertices[i].co, ii) for ii, i in enumerate(indices)]
 285
 286         edges = [(i, i - 1) for i in range(len(verts))]
 287         if edges:
 288             edges[0] = (0, len(verts) - 1)
 289
 290         if not verts:
 291             return []
 292
 293         edges_used = set()
 294         edges_doubles = set()
 295         # We need to check if any edges are used twice location based.
 296         for ed in edges:
 297             edkey = ed_key_mlen(verts[ed[0]], verts[ed[1]])
 298             if edkey in edges_used:
 299                 edges_doubles.add(edkey)
 300             else:
 301                 edges_used.add(edkey)
 302
 303         # Store a list of unconnected loop segments split by double edges.
 304         # will join later
 305         loop_segments = []
 306
 307         v_prev = verts[0]
 308         context_loop = [v_prev]
 309         loop_segments = [context_loop]
 310
 311         for v in verts:
 312             if v != v_prev:
 313                 # Are we crossing an edge we removed?
 314                 if ed_key_mlen(v, v_prev) in edges_doubles:
 315                     context_loop = [v]
 316                     loop_segments.append(context_loop)
 317                 else:
 318                     if context_loop and context_loop[-1][1] == v[1]:
 319                         #raise "as"
 320                         pass
 321                     else:
 322                         context_loop.append(v)
 323
 324                 v_prev = v
 325         # Now join loop segments
 326
 327         def join_seg(s1, s2):
 328             if s2[-1][1] == s1[0][1]:
 329                 s1, s2 = s2, s1
 330             elif s1[-1][1] == s2[0][1]:
 331                 pass
 332             else:
 333                 return False
 334
 335             # If were stuill here s1 and s2 are 2 segments in the same polyline
 336             s1.pop()  # remove the last vert from s1
 337             s1.extend(s2)  # add segment 2 to segment 1
 338
 339             if s1[0][1] == s1[-1][1]:  # remove endpoints double
 340                 s1.pop()
 341
 342             s2[:] = []  # Empty this segment s2 so we dont use it again.
 343             return True
 344
 345         joining_segments = True
 346         while joining_segments:
 347             joining_segments = False
 348             segcount = len(loop_segments)
 349
 350             for j in range(segcount - 1, -1, -1):  # reversed(range(segcount)):
 351                 seg_j = loop_segments[j]
 352                 if seg_j:
 353                     for k in range(j - 1, -1, -1):  # reversed(range(j)):
 354                         if not seg_j:
 355                             break
 356                         seg_k = loop_segments[k]
 357
 358                         if seg_k and join_seg(seg_j, seg_k):
 359                             joining_segments = True
 360
 361         loop_list = loop_segments
 362
 363         for verts in loop_list:
 364             while verts and verts[0][1] == verts[-1][1]:
 365                 verts.pop()
 366
 367         loop_list = [verts for verts in loop_list if len(verts) > 2]
 368         # DONE DEALING WITH LOOP FIXING
 369
 370         # vert mapping
 371         vert_map = [None] * len(indices)
 372         ii = 0
 373         for verts in loop_list:
 374             if len(verts) > 2:
 375                 for i, vert in enumerate(verts):
 376                     vert_map[i + ii] = vert[2]
 377                 ii += len(verts)
 378
 379         fill = tesselate_polygon([[v[0] for v in loop] for loop in loop_list])
 380         #draw_loops(loop_list)
 381         #raise 'done loop'
 382         # map to original indices
 383         fill = [[vert_map[i] for i in reversed(f)] for f in fill]
 384
 385     if not fill:
 386         print('Warning Cannot scanfill, fallback on a triangle fan.')
 387         fill = [[0, i - 1, i] for i in range(2, len(indices))]
 388     else:
 389         # Use real scanfill.
 390         # See if its flipped the wrong way.
 391         flip = None
 392         for fi in fill:
 393             if flip != None:
 394                 break
 395             for i, vi in enumerate(fi):
 396                 if vi == 0 and fi[i - 1] == 1:
 397                     flip = False
 398                     break
 399                 elif vi == 1 and fi[i - 1] == 0:
 400                     flip = True
 401                     break
 402
 403         if not flip:
 404             for i, fi in enumerate(fill):
 405                 fill[i] = tuple([ii for ii in reversed(fi)])
 406
 407     return fill