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