Spelling Cleanup
[blender.git] / source / blender / bmesh / operators / bmo_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): Joseph Eagar
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_array.h"
26
27 #include "bmesh.h"
28
29 #include "bmesh_operators_private.h" /* own include */
30
31 typedef struct EdgeTag {
32         BMVert *newv1, *newv2;
33         BMEdge *newe1, *newe2;
34         int tag;
35 } EdgeTag;
36
37 /* (EDGE_DEL == FACE_DEL) - this must be the case */
38 #define EDGE_DEL        1
39 #define EDGE_SEAM       2
40 #define EDGE_MARK       4
41 #define EDGE_RET1       8
42 #define EDGE_RET2       16
43
44 #define FACE_DEL        1
45 #define FACE_NEW        2
46
47 static BMFace *remake_face(BMesh *bm, EdgeTag *etags, BMFace *f, BMVert **verts, BMEdge **edges_tmp)
48 {
49         BMIter liter1, liter2;
50         EdgeTag *et;
51         BMFace *f2;
52         BMLoop *l, *l2;
53         BMEdge *e;
54         BMVert *lastv1, *lastv2 /* , *v1, *v2 */ /* UNUSED */;
55         int i;
56
57         /* we do final edge last */
58         lastv1 = verts[f->len - 1];
59         lastv2 = verts[0];
60         /* v1 = verts[0]; */ /* UNUSED */
61         /* v2 = verts[1]; */ /* UNUSED */
62         for (i = 0; i < f->len - 1; i++) {
63                 e = BM_edge_create(bm, verts[i], verts[i + 1], NULL, TRUE);
64                 if (!e) {
65                         return NULL;
66                 }
67                 edges_tmp[i] = e;
68         }
69
70         edges_tmp[i] = BM_edge_create(bm, lastv1, lastv2, NULL, TRUE);
71
72         f2 = BM_face_create(bm, verts, edges_tmp, f->len, FALSE);
73         if (!f2) {
74                 return NULL;
75         }
76
77         BM_elem_attrs_copy(bm, bm, f, f2);
78
79         l = BM_iter_new(&liter1, bm, BM_LOOPS_OF_FACE, f);
80         l2 = BM_iter_new(&liter2, bm, BM_LOOPS_OF_FACE, f2);
81         for ( ; l && l2; l = BM_iter_step(&liter1), l2 = BM_iter_step(&liter2)) {
82                 BM_elem_attrs_copy(bm, bm, l, l2);
83                 if (l->e != l2->e) {
84                         /* set up data for figuring out the two sides of
85                          * the split */
86
87                         /* set edges index as dirty after running all */
88                         BM_elem_index_set(l2->e, BM_elem_index_get(l->e)); /* set_dirty! */
89                         et = &etags[BM_elem_index_get(l->e)];
90                         
91                         if (!et->newe1) {
92                                 et->newe1 = l2->e;
93                         }
94                         else if (!et->newe2) {
95                                 et->newe2 = l2->e;
96                         }
97                         else {
98                                 /* Only two new edges should be created from each original edge
99                                  *  for edge split operation */
100
101                                 //BLI_assert(et->newe1 == l2->e || et->newe2 == l2->e);
102                                 et->newe2 = l2->e;
103                         }
104
105                         if (BMO_elem_flag_test(bm, l->e, EDGE_SEAM)) {
106                                 BMO_elem_flag_enable(bm, l2->e, EDGE_SEAM);
107                         }
108
109                         BM_elem_attrs_copy(bm, bm, l->e, l2->e);
110                 }
111
112                 BMO_elem_flag_enable(bm, l->e, EDGE_MARK);
113                 BMO_elem_flag_enable(bm, l2->e, EDGE_MARK);
114         }
115
116         return f2;
117 }
118
119 static void tag_out_edges(BMesh *bm, EdgeTag *etags, BMOperator *UNUSED(op))
120 {
121         EdgeTag *et;
122         BMIter iter;
123         BMLoop *l, *startl;
124         BMEdge *e;
125         BMVert *v;
126         int i, ok;
127         
128         ok = 0;
129         while (ok++ < 100000) {
130                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
131                         if (!BMO_elem_flag_test(bm, e, EDGE_SEAM))
132                                 continue;
133
134                         et = &etags[BM_elem_index_get(e)];
135                         if (!et->tag && e->l) {
136                                 break;
137                         }
138                 }
139                 
140                 if (!e) {
141                         break;
142                 }
143
144                 /* ok we found an edge, part of a region of splits we need
145                  * to identify.  now walk along it */
146                 for (i = 0; i < 2; i++) {
147                         l = e->l;
148                         
149                         v = i ? l->next->v : l->v;
150
151                         while (1) {
152                                 et = &etags[BM_elem_index_get(l->e)];
153                                 if (et->newe1 == l->e) {
154                                         if (et->newe1) {
155                                                 BMO_elem_flag_enable(bm, et->newe1, EDGE_RET1);
156                                                 BMO_elem_flag_disable(bm, et->newe1, EDGE_SEAM);
157                                         }
158                                         if (et->newe2) {
159                                                 BMO_elem_flag_enable(bm, et->newe2, EDGE_RET2);
160                                                 BMO_elem_flag_disable(bm, et->newe2, EDGE_SEAM);
161                                         }
162                                 }
163                                 else {
164                                         if (et->newe1) {
165                                                 BMO_elem_flag_enable(bm, et->newe1, EDGE_RET2);
166                                                 BMO_elem_flag_disable(bm, et->newe1, EDGE_SEAM);
167                                         }
168                                         if (et->newe2) {
169                                                 BMO_elem_flag_enable(bm, et->newe2, EDGE_RET1);
170                                                 BMO_elem_flag_disable(bm, et->newe2, EDGE_SEAM);
171                                         }
172                                 }
173
174                                 /* If the original edge was non-manifold edges, then it is
175                                  * possible l->e is not et->newe1 or et->newe2. So always clear
176                                  * the flag on l->e as well, to prevent infinite looping. */
177                                 BMO_elem_flag_disable(bm, l->e, EDGE_SEAM);
178
179                                 startl = l;
180                                 do {
181                                         l = BM_face_other_loop(l->e, l->f, v);
182                                         if (l == startl || BM_edge_face_count(l->e) != 2) {
183                                                 break;
184                                         }
185                                         l = l->radial_next;
186                                 } while (l != startl && !BMO_elem_flag_test(bm, l->e, EDGE_SEAM));
187                                 
188                                 if (l == startl || !BMO_elem_flag_test(bm, l->e, EDGE_SEAM)) {
189                                         break;
190                                 }
191
192                                 v = (l->v == v) ? l->next->v : l->v;
193                         }
194                 }
195         }
196 }
197
198 void bmo_edgesplit_exec(BMesh *bm, BMOperator *op)
199 {
200         EdgeTag *etags, *et;
201         BMIter iter, liter;
202         BMOIter siter;
203         BMFace *f, *f2;
204         BMLoop *l, *nextl, *prevl, *l2, *l3;
205         BMEdge *e, *e2;
206         BMVert *v, *v2, **verts = NULL;
207         BLI_array_declare(verts);
208         BMEdge **edges_tmp = NULL;
209         BLI_array_declare(edges_tmp);
210         int i, j;
211
212         BMO_slot_buffer_flag_enable(bm, op, "edges", EDGE_SEAM, BM_EDGE);
213         
214         /* single marked edges unconnected to any other marked edges
215          * are illegal, go through and unmark them */
216         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
217                 for (i = 0; i < 2; i++) {
218                         BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i ? e->v2 : e->v1) {
219                                 if (e != e2 && BMO_elem_flag_test(bm, e2, EDGE_SEAM)) {
220                                         break;
221                                 }
222                         }
223                         if (e2) {
224                                 break;
225                         }
226                 }
227
228                 if (!e2) {
229                         BMO_elem_flag_disable(bm, e, EDGE_SEAM);
230                 }
231         }
232
233         etags = MEM_callocN(sizeof(EdgeTag) * bm->totedge, "EdgeTag");
234
235         BM_mesh_elem_index_ensure(bm, BM_EDGE);
236
237 #ifdef ETV
238 #  undef ETV
239 #endif
240 #ifdef SETETV
241 #  undef SETETV
242 #endif
243
244 #define ETV(et, v, l) (l->e->v1 == v ? et->newv1 : et->newv2)
245 #define SETETV(et, v, l, vs) l->e->v1 == v ? (et->newv1 = vs) : (et->newv2 = vs)
246
247         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
248
249                 if (BMO_elem_flag_test(bm, f, FACE_NEW)) {
250                         continue;
251                 }
252
253                 BLI_array_empty(verts);
254                 BLI_array_growitems(verts, f->len);
255                 memset(verts, 0, sizeof(BMVert *) * f->len);
256
257                 /* this is passed onto remake_face() so it doesnt need to allocate
258                  * a new array on each call. */
259                 BLI_array_empty(edges_tmp);
260                 BLI_array_growitems(edges_tmp, f->len);
261
262                 i = 0;
263                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
264                         if (!BMO_elem_flag_test(bm, l->e, EDGE_SEAM)) {
265                                 if (!verts[i]) {
266
267                                         et = &etags[BM_elem_index_get(l->e)];
268                                         if (ETV(et, l->v, l)) {
269                                                 verts[i] = ETV(et, l->v, l);
270                                         }
271                                         else
272                                         {
273                                                 verts[i] = l->v;
274                                         }
275                                 }
276                                 i++;
277                                 continue;
278                         }
279
280                         nextl = l->next;
281                         prevl = l->prev;
282                         
283                         for (j = 0; j < 2; j++) {
284                                 /* correct as long as i & j dont change during the loop */
285                                 const int fv_index = j ? (i + 1) % f->len : i; /* face vert index */
286                                 l2 = j ? nextl : prevl;
287                                 v = j ? l2->v : l->v;
288
289                                 if (BMO_elem_flag_test(bm, l2->e, EDGE_SEAM)) {
290                                         if (verts[fv_index] == NULL) {
291                                                 /* make unique vert here for this face only */
292                                                 v2 = BM_vert_create(bm, v->co, v);
293                                                 verts[fv_index] = v2;
294                                         }
295                                         else {
296                                                 v2 = verts[fv_index];
297                                         }
298                                 }
299                                 else {
300                                         /* generate unique vert for non-seam edge(s)
301                                          * around the manifold vert fan if necessary */
302
303                                         /* first check that we have two seam edges
304                                          * somewhere within this fa */
305                                         l3 = l2;
306                                         do {
307                                                 if (BM_edge_face_count(l3->e) != 2) {
308                                                         /* if we hit a boundary edge, tag
309                                                          * l3 as null so we know to disconnect
310                                                          * it */
311                                                         if (BM_edge_face_count(l3->e) == 1) {
312                                                                 l3 = NULL;
313                                                         }
314                                                         break;
315                                                 }
316
317                                                 l3 = l3->radial_next;
318                                                 l3 = BM_face_other_loop(l3->e, l3->f, v);
319                                         } while (l3 != l2 && !BMO_elem_flag_test(bm, l3->e, EDGE_SEAM));
320
321                                         if (l3 == NULL || (BMO_elem_flag_test(bm, l3->e, EDGE_SEAM) && l3->e != l->e)) {
322                                                 et = &etags[BM_elem_index_get(l2->e)];
323                                                 if (ETV(et, v, l2) == NULL) {
324                                                         v2 = BM_vert_create(bm, v->co, v);
325                                                         
326                                                         l3 = l2;
327                                                         do {
328                                                                 SETETV(et, v, l3, v2);
329                                                                 if (BM_edge_face_count(l3->e) != 2) {
330                                                                         break;
331                                                                 }
332
333                                                                 l3 = l3->radial_next;
334                                                                 l3 = BM_face_other_loop(l3->e, l3->f, v);
335                                                                 
336                                                                 et = &etags[BM_elem_index_get(l3->e)];
337                                                         } while (l3 != l2 && !BMO_elem_flag_test(bm, l3->e, EDGE_SEAM));
338                                                 }
339                                                 else {
340                                                         v2 = ETV(et, v, l2);
341                                                 }
342
343                                                 verts[fv_index] = v2;
344                                         }
345                                         else {
346                                                 verts[fv_index] = v;
347                                         }
348                                 }
349                         }
350
351                         i++;
352                 }
353
354                 /* debugging code, quick way to find the face/vert combination
355                  * which is failing assuming quads start planer - campbell */
356 #if 0
357                 if (f->len == 4) {
358                         float no1[3];
359                         float no2[3];
360                         float angle_error;
361                         printf(" ** found QUAD\n");
362                         normal_tri_v3(no1, verts[0]->co, verts[1]->co, verts[2]->co);
363                         normal_tri_v3(no2, verts[0]->co, verts[2]->co, verts[3]->co);
364                         if ((angle_error = angle_v3v3(no1, no2)) > 0.05) {
365                                 printf("     ERROR %.4f\n", angle_error);
366                                 print_v3("0", verts[0]->co);
367                                 print_v3("1", verts[1]->co);
368                                 print_v3("2", verts[2]->co);
369                                 print_v3("3", verts[3]->co);
370
371                         }
372                 }
373                 else {
374                         printf(" ** fount %d len face\n", f->len);
375                 }
376 #endif
377
378                 f2 = remake_face(bm, etags, f, verts, edges_tmp);
379                 if (!f2) {
380                         continue;
381                 }
382
383                 BMO_elem_flag_enable(bm, f, FACE_DEL);
384                 BMO_elem_flag_enable(bm, f2, FACE_NEW);
385         }
386         
387         /* remake_face() sets invalid indecies,
388          * likely these will be corrected on operator exit anyway */
389         bm->elem_index_dirty &= ~BM_EDGE;
390
391         /* cant call the operator because 'tag_out_edges'
392          * relies on original index values, from before editing geometry */
393
394 #if 0
395         BMO_op_callf(bm, "del geom=%ff context=%i", FACE_DEL, DEL_ONLYFACES);
396 #else
397         BMO_remove_tagged_context(bm, FACE_DEL, DEL_ONLYFACES);
398 #endif
399
400         /* test EDGE_MARK'd edges if we need to delete them, EDGE_MARK
401          * is set in remake_face */
402         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
403                 if (BMO_elem_flag_test(bm, e, EDGE_MARK)) {
404                         if (!e->l) {
405                                 BMO_elem_flag_enable(bm, e, EDGE_DEL);
406                         }
407                 }
408         }
409
410 #if 0
411         BMO_op_callf(bm, "del geom=%fe context=%i", EDGE_DEL, DEL_EDGES);
412 #else
413         BMO_remove_tagged_context(bm, EDGE_DEL, DEL_EDGES);
414 #endif
415         
416         tag_out_edges(bm, etags, op);
417         BMO_slot_from_flag(bm, op, "edgeout1", EDGE_RET1, BM_EDGE);
418         BMO_slot_from_flag(bm, op, "edgeout2", EDGE_RET2, BM_EDGE);
419
420         BLI_array_free(verts);
421         BLI_array_free(edges_tmp);
422         if (etags) MEM_freeN(etags);
423 }
424
425 #undef ETV
426 #undef SETETV