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