Merging r59130 through r59135 from trunk into soc-2013-depsgraph_mt
[blender.git] / source / blender / bmesh / tools / bmesh_edgesplit.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/tools/bmesh_edgesplit.c
24  *  \ingroup bmesh
25  *
26  * Edge-Split.
27  *
28  */
29
30 #include "MEM_guardedalloc.h"
31
32 #include "BLI_utildefines.h"
33
34 #include "bmesh.h"
35
36 #include "bmesh_edgesplit.h"  /* own include */
37
38
39 /**
40  * Remove the BM_ELEM_TAG flag for edges we cant split
41  *
42  * un-tag edges not connected to other tagged edges,
43  * unless they are on a boundary
44  */
45 static void bm_edgesplit_validate_seams(BMesh *bm)
46 {
47         BMIter iter;
48         BMEdge *e;
49
50         unsigned char *vtouch;
51
52         BM_mesh_elem_index_ensure(bm, BM_VERT);
53
54         vtouch = MEM_callocN(sizeof(char) * bm->totvert, __func__);
55
56         /* tag all boundary verts so as not to untag an edge which is inbetween only 2 faces [] */
57         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
58
59                 /* unrelated to flag assignment in this function - since this is the
60                  * only place we loop over all edges, disable tag */
61                 BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
62
63                 if (e->l == NULL) {
64                         BM_elem_flag_disable(e, BM_ELEM_TAG);
65                 }
66                 else if (BM_edge_is_boundary(e)) {
67                         unsigned char *vt;
68                         vt = &vtouch[BM_elem_index_get(e->v1)]; if (*vt < 2) (*vt)++;
69                         vt = &vtouch[BM_elem_index_get(e->v2)]; if (*vt < 2) (*vt)++;
70
71                         /* while the boundary verts need to be tagged,
72                          * the edge its self can't be split */
73                         BM_elem_flag_disable(e, BM_ELEM_TAG);
74                 }
75         }
76
77         /* single marked edges unconnected to any other marked edges
78          * are illegal, go through and unmark them */
79         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
80                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
81                         /* lame, but we don't want the count to exceed 255,
82                          * so just count to 2, its all we need */
83                         unsigned char *vt;
84                         vt = &vtouch[BM_elem_index_get(e->v1)]; if (*vt < 2) (*vt)++;
85                         vt = &vtouch[BM_elem_index_get(e->v2)]; if (*vt < 2) (*vt)++;
86                 }
87         }
88         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
89                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
90                         if (vtouch[BM_elem_index_get(e->v1)] == 1 &&
91                                 vtouch[BM_elem_index_get(e->v2)] == 1)
92                         {
93                                 BM_elem_flag_disable(e, BM_ELEM_TAG);
94                         }
95                 }
96         }
97
98         MEM_freeN(vtouch);
99 }
100
101 void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, const bool copy_select)
102 {
103         BMIter iter;
104         BMEdge *e;
105
106         bool use_ese = false;
107         GHash *ese_gh = NULL;
108
109         if (copy_select && bm->selected.first) {
110                 BMEditSelection *ese;
111
112                 ese_gh = BLI_ghash_ptr_new(__func__);
113                 for (ese = bm->selected.first; ese; ese = ese->next) {
114                         if (ese->htype != BM_FACE) {
115                                 BLI_ghash_insert(ese_gh, ese->ele, ese);
116                         }
117                 }
118
119                 use_ese = true;
120         }
121
122         if (tag_only == false) {
123                 BM_mesh_elem_hflag_enable_all(bm, BM_EDGE | (use_verts ? BM_VERT : 0), BM_ELEM_TAG, false);
124         }
125
126         if (use_verts) {
127                 /* prevent one edge having both verts unflagged
128                  * we could alternately disable these edges, either way its a corner case.
129                  *
130                  * This is needed so we don't split off the edge but then none of its verts which
131                  * would leave a duplicate edge.
132                  */
133                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
134                         if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
135                                 if (UNLIKELY(((BM_elem_flag_test(e->v1, BM_ELEM_TAG) == false) &&
136                                               (BM_elem_flag_test(e->v2, BM_ELEM_TAG) == false))))
137                                 {
138                                         BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
139                                         BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
140                                 }
141                         }
142                 }
143         }
144
145         bm_edgesplit_validate_seams(bm);
146
147         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
148                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
149                         /* this flag gets copied so we can be sure duplicate edges get it too (important) */
150                         BM_elem_flag_enable(e, BM_ELEM_INTERNAL_TAG);
151
152                         /* keep splitting until each loop has its own edge */
153                         while (!BM_edge_is_boundary(e)) {
154                                 BMLoop *l_sep = e->l;
155                                 bmesh_edge_separate(bm, e, l_sep, copy_select);
156                                 BLI_assert(l_sep->e != e);
157
158                                 if (use_ese) {
159                                         BMEditSelection *ese = BLI_ghash_lookup(ese_gh, e);
160                                         if (UNLIKELY(ese)) {
161                                                 BM_select_history_store_after_notest(bm, ese, l_sep->e);
162                                         }
163                                 }
164                         }
165
166                         BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
167                         BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
168                 }
169         }
170
171         if (use_verts) {
172                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
173                         if (BM_elem_flag_test(e->v1, BM_ELEM_TAG) == false) {
174                                 BM_elem_flag_disable(e->v1, BM_ELEM_TAG);
175                         }
176                         if (BM_elem_flag_test(e->v2, BM_ELEM_TAG) == false) {
177                                 BM_elem_flag_disable(e->v2, BM_ELEM_TAG);
178                         }
179                 }
180         }
181
182         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
183                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
184                         unsigned int i;
185                         for (i = 0; i < 2; i++) {
186                                 BMVert *v = ((&e->v1)[i]);
187                                 if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
188                                         BM_elem_flag_disable(v, BM_ELEM_TAG);
189
190                                         if (use_ese) {
191                                                 BMVert **vtar;
192                                                 int vtar_len;
193
194                                                 bmesh_vert_separate(bm, v, &vtar, &vtar_len, copy_select);
195
196                                                 if (vtar_len) {
197                                                         BMEditSelection *ese = BLI_ghash_lookup(ese_gh, v);
198                                                         if (UNLIKELY(ese)) {
199                                                                 int j;
200                                                                 for (j = 0; j < vtar_len; j++) {
201                                                                         BLI_assert(v != vtar[j]);
202                                                                         BM_select_history_store_after_notest(bm, ese, vtar[j]);
203                                                                 }
204                                                         }
205                                                 }
206                                                 MEM_freeN(vtar);
207                                         }
208                                         else {
209                                                 bmesh_vert_separate(bm, v, NULL, NULL, copy_select);
210                                         }
211                                 }
212                         }
213                 }
214         }
215
216         if (use_ese) {
217                 BLI_ghash_free(ese_gh, NULL, NULL);
218         }
219 }