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_triangles",
24    "edge_face_count_dict",
25    "edge_face_count",
26    "edge_loops_from_edges",
27    "ngon_tessellate",
28    "triangle_random_points",
29)
30
31
32def mesh_linked_uv_islands(mesh):
33    """
34    Splits the mesh into connected polygons, use this for separating 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 polygon indices
40    :rtype: list
41    """
42    uv_loops = [luv.uv[:] for luv in mesh.uv_layers.active.data]
43    poly_loops = [poly.loop_indices for poly in mesh.polygons]
44    luv_hash = {}
45    luv_hash_get = luv_hash.get
46    luv_hash_ls = [None] * len(uv_loops)
47    for pi, poly_indices in enumerate(poly_loops):
48        for li in poly_indices:
49            uv = uv_loops[li]
50            uv_hub = luv_hash_get(uv)
51            if uv_hub is None:
52                uv_hub = luv_hash[uv] = [pi]
53            else:
54                uv_hub.append(pi)
55            luv_hash_ls[li] = uv_hub
56
57    poly_islands = []
58
59    # 0 = none, 1 = added, 2 = searched
60    poly_tag = [0] * len(poly_loops)
61
62    while True:
63        poly_index = -1
64        for i in range(len(poly_loops)):
65            if poly_tag[i] == 0:
66                poly_index = i
67                break
68
69        if poly_index != -1:
70            island = [poly_index]
71            poly_tag[poly_index] = 1
72            poly_islands.append(island)
73        else:
74            break  # we're done
75
76        added = True
77        while added:
78            added = False
79            for poly_index in island[:]:
80                if poly_tag[poly_index] == 1:
81                    for li in poly_loops[poly_index]:
82                        for poly_index_shared in luv_hash_ls[li]:
83                            if poly_tag[poly_index_shared] == 0:
84                                added = True
85                                poly_tag[poly_index_shared] = 1
86                                island.append(poly_index_shared)
87                    poly_tag[poly_index] = 2
88
89    return poly_islands
90
91
92def mesh_linked_triangles(mesh):
93    """
94    Splits the mesh into connected triangles, use this for separating cubes from
95    other mesh elements within 1 mesh datablock.
96
97    :arg mesh: the mesh used to group with.
98    :type mesh: :class:`bpy.types.Mesh`
99    :return: lists of lists containing triangles.
100    :rtype: list
101    """
102
103    # Build vert face connectivity
104    vert_tris = [[] for i in range(len(mesh.vertices))]
105    for t in mesh.loop_triangles:
106        for v in t.vertices:
107            vert_tris[v].append(t)
108
109    # sort triangles into connectivity groups
110    tri_groups = [[t] for t in mesh.loop_triangles]
111    # map old, new tri location
112    tri_mapping = list(range(len(mesh.loop_triangles)))
113
114    # Now clump triangles iteratively
115    ok = True
116    while ok:
117        ok = False
118
119        for t in mesh.loop_triangles:
120            mapped_index = tri_mapping[t.index]
121            mapped_group = tri_groups[mapped_index]
122
123            for v in t.vertices:
124                for nxt_t in vert_tris[v]:
125                    if nxt_t != t:
126                        nxt_mapped_index = tri_mapping[nxt_t.index]
127
128                        # We are not a part of the same group
129                        if mapped_index != nxt_mapped_index:
130                            ok = True
131
132                            # Assign mapping to this group so they
133                            # all map to this group
134                            for grp_t in tri_groups[nxt_mapped_index]:
135                                tri_mapping[grp_t.index] = mapped_index
136
137                            # Move triangles into this group
138                            mapped_group.extend(tri_groups[nxt_mapped_index])
139
140                            # remove reference to the list
141                            tri_groups[nxt_mapped_index] = None
142
143    # return all tri groups that are not null
144    # this is all the triangles that are connected in their own lists.
145    return [tg for tg in tri_groups if tg]
146
147
148def edge_face_count_dict(mesh):
149    """
150    :return: dict of edge keys with their value set to the number of
151       faces using each edge.
152    :rtype: dict
153    """
154
155    face_edge_count = {}
156    loops = mesh.loops
157    edges = mesh.edges
158    for poly in mesh.polygons:
159        for i in poly.loop_indices:
160            key = edges[loops[i].edge_index].key
161            try:
162                face_edge_count[key] += 1
163            except:
164                face_edge_count[key] = 1
165
166    return face_edge_count
167
168
169def edge_face_count(mesh):
170    """
171    :return: list face users for each item in mesh.edges.
172    :rtype: list
173    """
174    edge_face_count = edge_face_count_dict(mesh)
175    get = dict.get
176    return [get(edge_face_count, ed.key, 0) for ed in mesh.edges]
177
178
179def edge_loops_from_edges(mesh, edges=None):
180    """
181    Edge loops defined by edges
182
183    Takes me.edges or a list of edges and returns the edge loops
184
185    return a list of vertex indices.
186    [ [1, 6, 7, 2], ...]
187
188    closed loops have matching start and end values.
189    """
190    line_polys = []
191
192    # Get edges not used by a face
193    if edges is None:
194        edges = mesh.edges
195
196    if not hasattr(edges, "pop"):
197        edges = edges[:]
198
199    while edges:
200        current_edge = edges.pop()
201        vert_end, vert_start = current_edge.vertices[:]
202        line_poly = [vert_start, vert_end]
203
204        ok = True
205        while ok:
206            ok = False
207            # for i, ed in enumerate(edges):
208            i = len(edges)
209            while i:
210                i -= 1
211                ed = edges[i]
212                v1, v2 = ed.vertices
213                if v1 == vert_end:
214                    line_poly.append(v2)
215                    vert_end = line_poly[-1]
216                    ok = 1
217                    del edges[i]
218                    # break
219                elif v2 == vert_end:
220                    line_poly.append(v1)
221                    vert_end = line_poly[-1]
222                    ok = 1
223                    del edges[i]
224                    # break
225                elif v1 == vert_start:
226                    line_poly.insert(0, v2)
227                    vert_start = line_poly[0]
228                    ok = 1
229                    del edges[i]
230                    # break
231                elif v2 == vert_start:
232                    line_poly.insert(0, v1)
233                    vert_start = line_poly[0]
234                    ok = 1
235                    del edges[i]
236                    # break
237        line_polys.append(line_poly)
238
239    return line_polys
240
241
242def ngon_tessellate(from_data, indices, fix_loops=True, debug_print=True):
243    """
244    Takes a polyline of indices (ngon) and returns a list of face
245    index lists. Designed to be used for importers that need indices for an
246    ngon to create from existing verts.
247
248    :arg from_data: either a mesh, or a list/tuple of vectors.
249    :type from_data: list or :class:`bpy.types.Mesh`
250    :arg indices: a list of indices to use this list
251       is the ordered closed polyline
252       to fill, and can be a subset of the data given.
253    :type indices: list
254    :arg fix_loops: If this is enabled polylines
255       that use loops to make multiple
256       polylines are delt with correctly.
257    :type fix_loops: bool
258    """
259
260    from mathutils.geometry import tessellate_polygon
261    from mathutils import Vector
262    vector_to_tuple = Vector.to_tuple
263
264    if not indices:
265        return []
266
267    def mlen(co):
268        # Manhatten length of a vector, faster then length.
269        return abs(co[0]) + abs(co[1]) + abs(co[2])
270
271    def vert_from_vector_with_extra_data(v, i):
272        # Calculate data per-vector, for reuse.
273        return v, vector_to_tuple(v, 6), i, mlen(v)
274
275    def ed_key_mlen(v1, v2):
276        if v1[3] > v2[3]:
277            return v2[1], v1[1]
278        else:
279            return v1[1], v2[1]
280
281    if not fix_loops:
282        # Normal single concave loop filling.
283
284        if type(from_data) in {tuple, list}:
285            verts = [Vector(from_data[i]) for ii, i in enumerate(indices)]
286        else:
287            verts = [from_data.vertices[i].co for ii, i in enumerate(indices)]
288
289        # same as reversed(range(1, len(verts))):
290        for i in range(len(verts) - 1, 0, -1):
291            if verts[i][1] == verts[i - 1][0]:
292                verts.pop(i - 1)
293
294        fill = tessellate_polygon([verts])
295
296    else:
297        # Separate this loop into multiple loops be finding edges that are
298        # used twice. This is used by Light-Wave LWO files a lot.
299
300        if type(from_data) in {tuple, list}:
301            verts = [
302                vert_from_vector_with_extra_data(Vector(from_data[i]), ii)
303                for ii, i in enumerate(indices)
304            ]
305        else:
306            verts = [
307                vert_from_vector_with_extra_data(from_data.vertices[i].co, ii)
308                for ii, i in enumerate(indices)
309            ]
310
311        edges = [(i, i - 1) for i in range(len(verts))]
312        if edges:
313            edges[0] = (0, len(verts) - 1)
314
315        if not verts:
316            return []
317
318        edges_used = set()
319        edges_doubles = set()
320        # We need to check if any edges are used twice location based.
321        for ed in edges:
322            edkey = ed_key_mlen(verts[ed[0]], verts[ed[1]])
323            if edkey in edges_used:
324                edges_doubles.add(edkey)
325            else:
326                edges_used.add(edkey)
327
328        # Store a list of unconnected loop segments split by double edges.
329        # will join later
330        loop_segments = []
331
332        v_prev = verts[0]
333        context_loop = [v_prev]
334        loop_segments = [context_loop]
335
336        for v in verts:
337            if v != v_prev:
338                # Are we crossing an edge we removed?
339                if ed_key_mlen(v, v_prev) in edges_doubles:
340                    context_loop = [v]
341                    loop_segments.append(context_loop)
342                else:
343                    if context_loop and context_loop[-1][1] == v[1]:
344                        pass
345                    else:
346                        context_loop.append(v)
347
348                v_prev = v
349        # Now join loop segments
350
351        def join_seg(s1, s2):
352            if s2[-1][1] == s1[0][1]:
353                s1, s2 = s2, s1
354            elif s1[-1][1] == s2[0][1]:
355                pass
356            else:
357                return False
358
359            # If were still here s1 and s2 are 2 segments in the same poly-line.
360            s1.pop()  # remove the last vert from s1
361            s1.extend(s2)  # add segment 2 to segment 1
362
363            if s1[0][1] == s1[-1][1]:  # remove endpoints double
364                s1.pop()
365
366            del s2[:]  # Empty this segment s2 so we don't use it again.
367            return True
368
369        joining_segments = True
370        while joining_segments:
371            joining_segments = False
372            segcount = len(loop_segments)
373
374            for j in range(segcount - 1, -1, -1):  # reversed(range(segcount)):
375                seg_j = loop_segments[j]
376                if seg_j:
377                    for k in range(j - 1, -1, -1):  # reversed(range(j)):
378                        if not seg_j:
379                            break
380                        seg_k = loop_segments[k]
381
382                        if seg_k and join_seg(seg_j, seg_k):
383                            joining_segments = True
384
385        loop_list = loop_segments
386
387        for verts in loop_list:
388            while verts and verts[0][1] == verts[-1][1]:
389                verts.pop()
390
391        loop_list = [verts for verts in loop_list if len(verts) > 2]
392        # DONE DEALING WITH LOOP FIXING
393
394        # vert mapping
395        vert_map = [None] * len(indices)
396        ii = 0
397        for verts in loop_list:
398            if len(verts) > 2:
399                for i, vert in enumerate(verts):
400                    vert_map[i + ii] = vert[2]
401                ii += len(verts)
402
403        fill = tessellate_polygon([[v[0] for v in loop] for loop in loop_list])
404        # draw_loops(loop_list)
405        #raise Exception("done loop")
406        # map to original indices
407        fill = [[vert_map[i] for i in f] for f in fill]
408
409    if not fill:
410        if debug_print:
411            print('Warning Cannot scanfill, fallback on a triangle fan.')
412        fill = [[0, i - 1, i] for i in range(2, len(indices))]
413    else:
414        # Use real scan-fill.
415        # See if its flipped the wrong way.
416        flip = None
417        for fi in fill:
418            if flip is not None:
419                break
420            for i, vi in enumerate(fi):
421                if vi == 0 and fi[i - 1] == 1:
422                    flip = False
423                    break
424                elif vi == 1 and fi[i - 1] == 0:
425                    flip = True
426                    break
427
428        if not flip:
429            for i, fi in enumerate(fill):
430                fill[i] = tuple([ii for ii in reversed(fi)])
431
432    return fill
433
434
435def triangle_random_points(num_points, loop_triangles):
436    """
437    Generates a list of random points over mesh loop triangles.
438
439    :arg num_points: the number of random points to generate on each triangle.
440    :type int:
441    :arg loop_triangles: list of the triangles to generate points on.
442    :type loop_triangles: :class:`bpy.types.MeshLoopTriangle`, sequence
443    :return: list of random points over all triangles.
444    :rtype: list
445    """
446
447    from random import random
448
449    # For each triangle, generate the required number of random points
450    sampled_points = [None] * (num_points * len(loop_triangles))
451    for i, lt in enumerate(loop_triangles):
452        # Get triangle vertex coordinates
453        verts = lt.id_data.vertices
454        ltv = lt.vertices[:]
455        tv = (verts[ltv[0]].co, verts[ltv[1]].co, verts[ltv[2]].co)
456
457        for k in range(num_points):
458            u1 = random()
459            u2 = random()
460            u_tot = u1 + u2
461
462            if u_tot > 1:
463                u1 = 1.0 - u1
464                u2 = 1.0 - u2
465
466            side1 = tv[1] - tv[0]
467            side2 = tv[2] - tv[0]
468
469            p = tv[0] + u1 * side1 + u2 * side2
470
471            sampled_points[num_points * i + k] = p
472
473    return sampled_points
474