rna/python api change: rename Mesh.faces --> tessfaces, since existing scripts are...
[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_faces",
23     "edge_face_count_dict",
24     "edge_face_count",
25     "edge_loops_from_faces",
26     "edge_loops_from_edges",
27     "ngon_tessellate",
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 iteratively
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.MeshTessFace`, 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.vertices) == 4:
144             edge_keys = f.edge_keys
145             for i, edkey in enumerate(f.edge_keys):
146                 edges.setdefault(edkey, []).append(edge_keys[OTHER_INDEX[i]])
147
148     for edkey in seams:
149         edges[edkey] = []
150
151     # Collect edge loops here
152     edge_loops = []
153
154     for edkey, ed_adj in edges.items():
155         if 0 < len(ed_adj) < 3:  # 1 or 2
156             # Seek the first edge
157             context_loop = [edkey, ed_adj[0]]
158             edge_loops.append(context_loop)
159             if len(ed_adj) == 2:
160                 other_dir = ed_adj[1]
161             else:
162                 other_dir = None
163
164             ed_adj[:] = []
165
166             flipped = False
167
168             while 1:
169                 # from knowing the last 2, look for the next.
170                 ed_adj = edges[context_loop[-1]]
171                 if len(ed_adj) != 2:
172                     # the original edge had 2 other edges
173                     if other_dir and flipped == False:
174                         flipped = True  # only flip the list once
175                         context_loop.reverse()
176                         ed_adj[:] = []
177                         context_loop.append(other_dir)  # save 1 look-up
178
179                         ed_adj = edges[context_loop[-1]]
180                         if len(ed_adj) != 2:
181                             ed_adj[:] = []
182                             break
183                     else:
184                         ed_adj[:] = []
185                         break
186
187                 i = ed_adj.index(context_loop[-2])
188                 context_loop.append(ed_adj[not  i])
189
190                 # Dont look at this again
191                 ed_adj[:] = []
192
193     return edge_loops
194
195
196 def edge_loops_from_edges(mesh, edges=None):
197     """
198     Edge loops defined by edges
199
200     Takes me.edges or a list of edges and returns the edge loops
201
202     return a list of vertex indices.
203     [ [1, 6, 7, 2], ...]
204
205     closed loops have matching start and end values.
206     """
207     line_polys = []
208
209     # Get edges not used by a face
210     if edges is None:
211         edges = mesh.edges
212
213     if not hasattr(edges, "pop"):
214         edges = edges[:]
215
216     while edges:
217         current_edge = edges.pop()
218         vert_end, vert_start = current_edge.vertices[:]
219         line_poly = [vert_start, vert_end]
220
221         ok = True
222         while ok:
223             ok = False
224             #for i, ed in enumerate(edges):
225             i = len(edges)
226             while i:
227                 i -= 1
228                 ed = edges[i]
229                 v1, v2 = ed.vertices
230                 if v1 == vert_end:
231                     line_poly.append(v2)
232                     vert_end = line_poly[-1]
233                     ok = 1
234                     del edges[i]
235                     # break
236                 elif v2 == vert_end:
237                     line_poly.append(v1)
238                     vert_end = line_poly[-1]
239                     ok = 1
240                     del edges[i]
241                     #break
242                 elif v1 == vert_start:
243                     line_poly.insert(0, v2)
244                     vert_start = line_poly[0]
245                     ok = 1
246                     del edges[i]
247                     # break
248                 elif v2 == vert_start:
249                     line_poly.insert(0, v1)
250                     vert_start = line_poly[0]
251                     ok = 1
252                     del edges[i]
253                     #break
254         line_polys.append(line_poly)
255
256     return line_polys
257
258
259 def ngon_tessellate(from_data, indices, fix_loops=True):
260     '''
261     Takes a polyline of indices (fgon) and returns a list of face
262     indicie lists. Designed to be used for importers that need indices for an
263     fgon to create from existing verts.
264
265     from_data: either a mesh, or a list/tuple of vectors.
266     indices: a list of indices to use this list is the ordered closed polyline
267        to fill, and can be a subset of the data given.
268     fix_loops: If this is enabled polylines that use loops to make multiple
269        polylines are delt with correctly.
270     '''
271
272     from mathutils.geometry import tessellate_polygon
273     from mathutils import Vector
274     vector_to_tuple = Vector.to_tuple
275
276     if not indices:
277         return []
278
279     def mlen(co):
280         # manhatten length of a vector, faster then length
281         return abs(co[0]) + abs(co[1]) + abs(co[2])
282
283     def vert_treplet(v, i):
284         return v, vector_to_tuple(v, 6), i, mlen(v)
285
286     def ed_key_mlen(v1, v2):
287         if v1[3] > v2[3]:
288             return v2[1], v1[1]
289         else:
290             return v1[1], v2[1]
291
292     if not fix_loops:
293         '''
294         Normal single concave loop filling
295         '''
296         if type(from_data) in {tuple, list}:
297             verts = [Vector(from_data[i]) for ii, i in enumerate(indices)]
298         else:
299             verts = [from_data.vertices[i].co for ii, i in enumerate(indices)]
300
301         # same as reversed(range(1, len(verts))):
302         for i in range(len(verts) - 1, 0, -1):
303             if verts[i][1] == verts[i - 1][0]:
304                 verts.pop(i - 1)
305
306         fill = tessellate_polygon([verts])
307
308     else:
309         '''
310         Seperate this loop into multiple loops be finding edges that are
311         used twice. This is used by lightwave LWO files a lot
312         '''
313
314         if type(from_data) in {tuple, list}:
315             verts = [vert_treplet(Vector(from_data[i]), ii)
316                      for ii, i in enumerate(indices)]
317         else:
318             verts = [vert_treplet(from_data.vertices[i].co, ii)
319                      for ii, i in enumerate(indices)]
320
321         edges = [(i, i - 1) for i in range(len(verts))]
322         if edges:
323             edges[0] = (0, len(verts) - 1)
324
325         if not verts:
326             return []
327
328         edges_used = set()
329         edges_doubles = set()
330         # We need to check if any edges are used twice location based.
331         for ed in edges:
332             edkey = ed_key_mlen(verts[ed[0]], verts[ed[1]])
333             if edkey in edges_used:
334                 edges_doubles.add(edkey)
335             else:
336                 edges_used.add(edkey)
337
338         # Store a list of unconnected loop segments split by double edges.
339         # will join later
340         loop_segments = []
341
342         v_prev = verts[0]
343         context_loop = [v_prev]
344         loop_segments = [context_loop]
345
346         for v in verts:
347             if v != v_prev:
348                 # Are we crossing an edge we removed?
349                 if ed_key_mlen(v, v_prev) in edges_doubles:
350                     context_loop = [v]
351                     loop_segments.append(context_loop)
352                 else:
353                     if context_loop and context_loop[-1][1] == v[1]:
354                         #raise "as"
355                         pass
356                     else:
357                         context_loop.append(v)
358
359                 v_prev = v
360         # Now join loop segments
361
362         def join_seg(s1, s2):
363             if s2[-1][1] == s1[0][1]:
364                 s1, s2 = s2, s1
365             elif s1[-1][1] == s2[0][1]:
366                 pass
367             else:
368                 return False
369
370             # If were stuill here s1 and s2 are 2 segments in the same polyline
371             s1.pop()  # remove the last vert from s1
372             s1.extend(s2)  # add segment 2 to segment 1
373
374             if s1[0][1] == s1[-1][1]:  # remove endpoints double
375                 s1.pop()
376
377             s2[:] = []  # Empty this segment s2 so we don't use it again.
378             return True
379
380         joining_segments = True
381         while joining_segments:
382             joining_segments = False
383             segcount = len(loop_segments)
384
385             for j in range(segcount - 1, -1, -1):  # reversed(range(segcount)):
386                 seg_j = loop_segments[j]
387                 if seg_j:
388                     for k in range(j - 1, -1, -1):  # reversed(range(j)):
389                         if not seg_j:
390                             break
391                         seg_k = loop_segments[k]
392
393                         if seg_k and join_seg(seg_j, seg_k):
394                             joining_segments = True
395
396         loop_list = loop_segments
397
398         for verts in loop_list:
399             while verts and verts[0][1] == verts[-1][1]:
400                 verts.pop()
401
402         loop_list = [verts for verts in loop_list if len(verts) > 2]
403         # DONE DEALING WITH LOOP FIXING
404
405         # vert mapping
406         vert_map = [None] * len(indices)
407         ii = 0
408         for verts in loop_list:
409             if len(verts) > 2:
410                 for i, vert in enumerate(verts):
411                     vert_map[i + ii] = vert[2]
412                 ii += len(verts)
413
414         fill = tessellate_polygon([[v[0] for v in loop] for loop in loop_list])
415         #draw_loops(loop_list)
416         #raise 'done loop'
417         # map to original indices
418         fill = [[vert_map[i] for i in reversed(f)] for f in fill]
419
420     if not fill:
421         print('Warning Cannot scanfill, fallback on a triangle fan.')
422         fill = [[0, i - 1, i] for i in range(2, len(indices))]
423     else:
424         # Use real scanfill.
425         # See if its flipped the wrong way.
426         flip = None
427         for fi in fill:
428             if flip is not None:
429                 break
430             for i, vi in enumerate(fi):
431                 if vi == 0 and fi[i - 1] == 1:
432                     flip = False
433                     break
434                 elif vi == 1 and fi[i - 1] == 0:
435                     flip = True
436                     break
437
438         if not flip:
439             for i, fi in enumerate(fill):
440                 fill[i] = tuple([ii for ii in reversed(fi)])
441
442     return fill
443
444
445 def face_random_points(num_points, faces):
446     """
447     Generates a list of random points over mesh faces.
448
449     :arg num_points: the number of random points to generate on each face.
450     :type int:
451     :arg faces: list of the faces to generate points on.
452     :type faces: :class:`bpy.types.MeshTessFace`, sequence
453     :return: list of random points over all faces.
454     :rtype: list
455     """
456
457     from random import random
458     from mathutils.geometry import area_tri
459
460     # Split all quads into 2 tris, tris remain unchanged
461     tri_faces = []
462     for f in faces:
463         tris = []
464         verts = f.id_data.vertices
465         fv = f.vertices[:]
466         tris.append((verts[fv[0]].co,
467                      verts[fv[1]].co,
468                      verts[fv[2]].co,
469                     ))
470         if len(fv) == 4:
471             tris.append((verts[fv[0]].co,
472                          verts[fv[3]].co,
473                          verts[fv[2]].co,
474                         ))
475         tri_faces.append(tris)
476
477     # For each face, generate the required number of random points
478     sampled_points = [None] * (num_points * len(faces))
479     for i, tf in enumerate(tri_faces):
480         for k in range(num_points):
481             # If this is a quad, we need to weight its 2 tris by their area
482             if len(tf) != 1:
483                 area1 = area_tri(*tf[0])
484                 area2 = area_tri(*tf[1])
485                 area_tot = area1 + area2
486
487                 area1 = area1 / area_tot
488                 area2 = area2 / area_tot
489
490                 vecs = tf[0 if (random() < area1) else 1]
491             else:
492                 vecs = tf[0]
493
494             u1 = random()
495             u2 = random()
496             u_tot = u1 + u2
497
498             if u_tot > 1:
499                 u1 = 1.0 - u1
500                 u2 = 1.0 - u2
501
502             side1 = vecs[1] - vecs[0]
503             side2 = vecs[2] - vecs[0]
504
505             p = vecs[0] + u1 * side1 + u2 * side2
506
507             sampled_points[num_points * i + k] = p
508
509     return sampled_points