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