new empty package to move bpy utility modules into.
[blender.git] / release / scripts / modules / 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
22 def mesh_linked_faces(mesh):
23     '''
24     Splits the mesh into connected parts,
25     these parts are returned as lists of faces.
26     used for seperating cubes from other mesh elements in the 1 mesh
27     '''
28
29     # Build vert face connectivity
30     vert_faces = [[] for i in range(len(mesh.vertices))]
31     for f in mesh.faces:
32         for v in f.vertices:
33             vert_faces[v].append(f)
34
35     # sort faces into connectivity groups
36     face_groups = [[f] for f in mesh.faces]
37     face_mapping = list(range(len(mesh.faces)))  # map old, new face location
38
39     # Now clump faces iterativly
40     ok = True
41     while ok:
42         ok = False
43
44         for i, f in enumerate(mesh.faces):
45             mapped_index = face_mapping[f.index]
46             mapped_group = face_groups[mapped_index]
47
48             for v in f.vertices:
49                 for nxt_f in vert_faces[v]:
50                     if nxt_f != f:
51                         nxt_mapped_index = face_mapping[nxt_f.index]
52
53                         # We are not a part of the same group
54                         if mapped_index != nxt_mapped_index:
55                             ok = True
56
57                             # Assign mapping to this group so they all map to this group
58                             for grp_f in face_groups[nxt_mapped_index]:
59                                 face_mapping[grp_f.index] = mapped_index
60
61                             # Move faces into this group
62                             mapped_group.extend(face_groups[nxt_mapped_index])
63
64                             # remove reference to the list
65                             face_groups[nxt_mapped_index] = None
66
67     # return all face groups that are not null
68     # this is all the faces that are connected in their own lists.
69     return [fg for fg in face_groups if fg]