e1d9aa05c0ad8ba69ccfaf60fccd46d803451b04
[blender.git] / source / blender / bmesh / operators / dissolveops.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "bmesh.h"
6 #include "mesh_intern.h"
7 #include "bmesh_private.h"
8 #include "BLI_arithb.h"
9
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13
14 #define FACE_MARK       1
15 #define FACE_ORIG       2
16 #define FACE_NEW        4
17 #define EDGE_MARK       1
18
19 #define VERT_MARK       1
20
21 static int check_hole_in_region(BMesh *bm, BMFace *f) {
22         BMWalker regwalker;
23         BMIter liter2;
24         BMLoop *l2, *l3;
25         BMFace *f2;
26         
27         /*checks if there are any unmarked boundary edges in the face region*/
28
29         BMW_Init(&regwalker, bm, BMW_ISLAND, FACE_MARK, 0);
30         f2 = BMW_Begin(&regwalker, f);
31         for (; f2; f2=BMW_Step(&regwalker)) {
32                 l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_FACE, f2);
33                 for (; l2; l2=BMIter_Step(&liter2)) {                   
34                         l3 = bmesh_radial_nextloop(l2);
35                         if (BMO_TestFlag(bm, l3->f, FACE_MARK) 
36                             != BMO_TestFlag(bm, l2->f, FACE_MARK))
37                         {
38                                 if (!BMO_TestFlag(bm, l2->e, EDGE_MARK)) {
39                                         return 0;
40                                 }
41                         }
42                 }
43         }
44         BMW_End(&regwalker);
45
46         return 1;
47 }
48
49 void dissolvefaces_exec(BMesh *bm, BMOperator *op)
50 {
51         BMOIter oiter;
52         BMIter liter, liter2, liter3;
53         BMLoop *l, *l2, *l3;
54         BMFace *f, *f2, *nf = NULL;
55         V_DECLARE(region);
56         V_DECLARE(regions);
57         BMLoop ***regions = NULL;
58         BMLoop **region = NULL;
59         BMWalker regwalker;
60         int i, j, fcopied;
61
62         BMO_Flag_Buffer(bm, op, "faces", FACE_MARK, BM_FACE);
63         
64         /*collect regions*/
65         f = BMO_IterNew(&oiter, bm, op, "faces", BM_FACE);
66         for (; f; f=BMO_IterStep(&oiter)) {
67                 if (!BMO_TestFlag(bm, f, FACE_MARK)) continue;
68
69                 V_RESET(region);
70                 region = NULL; /*forces different allocation*/
71
72                 /*yay, walk!*/
73                 BMW_Init(&regwalker, bm, BMW_ISLAND, FACE_MARK, 0);
74                 f2 = BMW_Begin(&regwalker, f);
75                 for (; f2; f2=BMW_Step(&regwalker)) {
76                         l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_FACE, f2);
77                         for (; l2; l2=BMIter_Step(&liter2)) {
78                                 l3 = BMIter_New(&liter3, bm, BM_LOOPS_OF_LOOP, l2);
79                                 for (; l3; l3=BMIter_Step(&liter3)) {
80                                         if (!BMO_TestFlag(bm, l3->f, FACE_MARK)) {
81                                                 V_GROW(region);
82                                                 region[V_COUNT(region)-1] = l2;
83                                                 break;
84                                         }
85                                 }
86                                 if (bmesh_radial_nextloop(l2) == l2) {
87                                         V_GROW(region);
88                                         region[V_COUNT(region)-1] = l2;
89                                 }
90                         }
91                 }                               
92                 BMW_End(&regwalker);
93
94                 BMW_Init(&regwalker, bm, BMW_ISLAND, FACE_MARK, 0);
95                 f2 = BMW_Begin(&regwalker, f);
96                 for (; f2; f2=BMW_Step(&regwalker)) {
97                         BMO_ClearFlag(bm, f2, FACE_MARK);
98                         BMO_SetFlag(bm, f2, FACE_ORIG);
99                 }
100
101                 BMW_End(&regwalker);
102
103                 if (BMO_HasError(bm)) {
104                         BMO_ClearStack(bm);
105                         BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
106                         goto cleanup;
107                 }
108                 
109                 V_GROW(region);
110                 V_GROW(regions);
111                 regions[V_COUNT(regions)-1] = region;
112                 region[V_COUNT(region)-1] = NULL;
113         }
114         
115         for (i=0; i<V_COUNT(regions); i++) {
116                 BMEdge **edges = NULL;
117                 V_DECLARE(edges);
118
119                 region = regions[i];
120                 for (j=0; region[j]; j++) {
121                         V_GROW(edges);
122                         edges[V_COUNT(edges)-1] = region[j]->e;
123                 }
124                 
125                 if (!region[0]) {
126                         BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, 
127                                         "Could not find boundary of dissolve region");
128                         goto cleanup;
129                 }
130
131                 if (region[0]->e->v1 == region[0]->v)
132                         f= BM_Make_Ngon(bm, region[0]->e->v1, region[0]->e->v2,  edges, j, 1);
133                 else
134                         f= BM_Make_Ngon(bm, region[0]->e->v2, region[0]->e->v1,  edges, j, 1);
135                 
136                 V_FREE(edges);
137
138                 if (!f) {
139                         BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, 
140                                         "Could not create merged face");
141                         goto cleanup;
142                 }
143
144                 /*if making the new face failed (e.g. overlapping test)
145                   unmark the original faces for deletion.*/
146                 BMO_ClearFlag(bm, f, FACE_ORIG);
147                 BMO_SetFlag(bm, f, FACE_NEW);
148
149                 fcopied = 0;
150                 l=BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
151                 for (; l; l=BMIter_Step(&liter)) {
152                         /*ensure winding is identical*/
153                         l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_LOOP, l);
154                         for (; l2; l2=BMIter_Step(&liter2)) {
155                                 if (BMO_TestFlag(bm, l2->f, FACE_ORIG)) {
156                                         if (l2->v != l->v)
157                                                 bmesh_loop_reverse(bm, l2->f);
158                                         break;
159                                 }
160                         }
161                         
162                         /*copy over attributes*/
163                         l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_LOOP, l);
164                         for (; l2; l2=BMIter_Step(&liter2)) {
165                                 if (BMO_TestFlag(bm, l2->f, FACE_ORIG)) {
166                                         if (!fcopied) {
167                                                 BM_Copy_Attributes(bm, bm, l2->f, f);
168                                                 fcopied = 1;
169                                         }
170                                         BM_Copy_Attributes(bm, bm, l2, l);
171                                         break;
172                                 }
173                         }
174                 }
175         }
176
177         BMO_CallOpf(bm, "del geom=%ff context=%d", FACE_ORIG, DEL_FACES);
178         if (BMO_HasError(bm)) goto cleanup;
179
180         BMO_Flag_To_Slot(bm, op, "regionout", FACE_NEW, BM_FACE);
181
182 cleanup:
183         /*free/cleanup*/
184         for (i=0; i<V_COUNT(regions); i++) {
185                 if (regions[i]) V_FREE(regions[i]);
186         }
187
188         V_FREE(regions);
189 }
190
191 /*almost identical to dissolve edge, except it cleans up vertices*/
192 void dissolve_edgeloop_exec(BMesh *bm, BMOperator *op)
193 {
194         BMOperator fop;
195         BMOIter oiter;
196         BMIter iter;
197         BMVert *v, **verts = NULL;
198         V_DECLARE(verts);
199         BMEdge *e;
200         BMFace *f;
201         int i;
202
203         BMO_ITER(e, &oiter, bm, op, "edges", BM_EDGE) {
204                 if (BM_Edge_FaceCount(e) == 2) {
205                         BMO_SetFlag(bm, e->v1, VERT_MARK);
206                         BMO_SetFlag(bm, e->v2, VERT_MARK);
207
208                         BM_Join_Faces(bm, e->loop->f, 
209                                       ((BMLoop*)e->loop->radial.next->data)->f,
210                                       e);
211                 }
212         }
213
214         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
215                 if (BMO_TestFlag(bm, v, VERT_MARK) && 
216                         BM_Vert_EdgeCount(v) == 2) 
217                 {
218                         V_GROW(verts);
219                         verts[V_COUNT(verts)-1] = v;
220                 }
221         }
222
223         /*clean up extreneous 2-valence vertices*/
224         for (i=0; i<V_COUNT(verts); i++) {
225                 BM_Collapse_Vert(bm, verts[i]->edge, verts[i], 1.0);
226         }
227         
228         V_FREE(verts);
229
230         //BMO_InitOpf(bm, &fop, "dissolvefaces faces=%ff", FACE_MARK);
231         //BMO_Exec_Op(bm, &fop);
232
233         //BMO_CopySlot(op, &fop, "regionout", "regionout");
234
235         //BMO_Finish_Op(bm, &fop);
236 }
237
238
239 void dissolveedges_exec(BMesh *bm, BMOperator *op)
240 {
241         BMOperator fop;
242         BMOIter oiter;
243         BMIter iter;
244         BMVert *v;
245         BMEdge *e;
246         BMFace *f;
247         int i;
248
249         BMO_ITER(e, &oiter, bm, op, "edges", BM_EDGE) {
250                 if (BM_Edge_FaceCount(e) == 2) {
251                         BMO_SetFlag(bm, e->v1, VERT_MARK);
252                         BMO_SetFlag(bm, e->v2, VERT_MARK);
253
254                         BM_Join_Faces(bm, e->loop->f, 
255                                       ((BMLoop*)e->loop->radial.next->data)->f,
256                                       e);
257                 }
258         }
259
260         //BMO_InitOpf(bm, &fop, "dissolvefaces faces=%ff", FACE_MARK);
261         //BMO_Exec_Op(bm, &fop);
262
263         //BMO_CopySlot(op, &fop, "regionout", "regionout");
264
265         //BMO_Finish_Op(bm, &fop);
266 }
267
268 static int test_extra_verts(BMesh *bm, BMVert *v)
269 {
270         BMIter iter, liter, iter2, iter3;
271         BMFace *f, *f2;
272         BMLoop *l;
273         BMEdge *e;
274         int found;
275
276         /*test faces around verts for verts that would be wronly killed
277           by dissolve faces.*/
278         f = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v);
279         for (; f; f=BMIter_Step(&iter)) {
280                 l=BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
281                 for (; l; l=BMIter_Step(&liter)) {
282                         if (!BMO_TestFlag(bm, l->v, VERT_MARK)) {
283                                 /*if an edge around a vert is a boundary edge,
284                                    then dissolve faces won't destroy it.
285                                    also if it forms a boundary with one
286                                    of the face regions*/
287                                 found = 0;
288                                 e = BMIter_New(&iter2, bm, BM_EDGES_OF_VERT, l->v);
289                                 for (; e; e=BMIter_Step(&iter2)) {
290                                         if (BM_Edge_FaceCount(e)==1) found = 1;
291                                         f2 = BMIter_New(&iter3, bm, BM_FACES_OF_EDGE, e);
292                                         for (; f2; f2=BMIter_Step(&iter3)) {
293                                                 if (!BMO_TestFlag(bm, f2, FACE_MARK)) {
294                                                         found = 1;
295                                                         break;
296                                                 }
297                                         }
298                                         if (found) break;
299                                 }
300                                 if (!found) return 0;
301                         }
302                 }
303         }
304
305         return 1;
306 }
307 void dissolveverts_exec(BMesh *bm, BMOperator *op)
308 {
309         BMOpSlot *vinput;
310         BMIter iter, fiter;
311         BMVert *v;
312         BMFace *f;
313         int i;
314         
315         vinput = BMO_GetSlot(op, "verts");
316         BMO_Flag_Buffer(bm, op, "verts", VERT_MARK, BM_VERT);
317         
318         for (v=BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v=BMIter_Step(&iter)) {
319                 if (BMO_TestFlag(bm, v, VERT_MARK)) {
320                         f=BMIter_New(&fiter, bm, BM_FACES_OF_VERT, v);
321                         for (; f; f=BMIter_Step(&fiter)) {
322                                 BMO_SetFlag(bm, f, FACE_ORIG);
323                                 BMO_SetFlag(bm, f, FACE_MARK);
324                         }
325                         
326                         /*check if our additions to the input to face dissolve
327                           will destroy nonmarked vertices.*/
328                         if (!test_extra_verts(bm, v)) {
329                                 f=BMIter_New(&fiter, bm, BM_FACES_OF_VERT, v);
330                                 for (; f; f=BMIter_Step(&fiter)) {
331                                         if (BMO_TestFlag(bm, f, FACE_ORIG)) {
332                                                 BMO_ClearFlag(bm, f, FACE_MARK);
333                                                 BMO_ClearFlag(bm, f, FACE_ORIG);
334                                         }
335                                 }
336                         } else {
337                                 f=BMIter_New(&fiter, bm, BM_FACES_OF_VERT, v);
338                                 for (; f; f=BMIter_Step(&fiter)) {
339                                         BMO_ClearFlag(bm, f, FACE_ORIG);
340                                 }
341                         }
342                 }
343         }
344
345         BMO_CallOpf(bm, "dissolvefaces faces=%ff", FACE_MARK);
346         if (BMO_HasError(bm)) {
347                         char *msg;
348
349                         BMO_GetError(bm, &msg, NULL);
350                         BMO_ClearStack(bm);
351                         BMO_RaiseError(bm, op, BMERR_DISSOLVEVERTS_FAILED,msg);
352         }
353         
354         /*clean up any remaining*/
355         for (v=BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL); v; v=BMIter_Step(&iter)) {
356                 if (BMO_TestFlag(bm, v, VERT_MARK)) {
357                         if (!BM_Dissolve_Vert(bm, v)) {
358                                 BMO_RaiseError(bm, op, 
359                                         BMERR_DISSOLVEVERTS_FAILED, NULL);
360                                 return;
361                         }
362                 }
363         }
364
365 }
366
367 /*this code is for cleaning up two-edged faces, it shall become
368   it's own function one day.*/
369 #if 0
370                 /*clean up two-edged faces*/
371                 /*basic idea is to keep joining 2-edged faces until their
372                   gone.  this however relies on joining two 2-edged faces
373                   together to work, which doesn't.*/
374                 found3 = 1;
375                 while (found3) {
376                         found3 = 0;
377                         for (f=BMIter_New(&iter, bm, BM_FACES_OF_MESH, NULL); f; f=BMIter_Step(&iter)){
378                                 if (!BM_Validate_Face(bm, f, stderr)) {
379                                         printf("error.\n");
380                                 }
381
382                                 if (f->len == 2) {
383                                         //this design relies on join faces working
384                                         //with two-edged faces properly.
385                                         //commenting this line disables the
386                                         //outermost loop.
387                                         //found3 = 1;
388                                         found2 = 0;
389                                         l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
390                                         fe = l->e;
391                                         for (; l; l=BMIter_Step(&liter)) {
392                                                 f2 = BMIter_New(&fiter, bm,
393                                                                 BM_FACES_OF_EDGE, l->e);
394                                                 for (; f2; f2=BMIter_Step(&fiter)) {
395                                                         if (f2 != f) {
396                                                                 BM_Join_Faces(bm, f, f2, l->e);
397                                                                 found2 = 1;
398                                                                 break;
399                                                         }
400                                                 }
401                                                 if (found2) break;
402                                         }
403
404                                         if (!found2) {
405                                                 bmesh_kf(bm, f);
406                                                 bmesh_ke(bm, fe);
407                                         }
408                                 } /*else if (f->len == 3) {
409                                         BMEdge *ed[3];
410                                         BMVert *vt[3];
411                                         BMLoop *lp[3];
412                                         int i=0;
413
414                                         //check for duplicate edges
415                                         l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
416                                         for (; l; l=BMIter_Step(&liter)) {
417                                                 ed[i] = l->e;   
418                                                 lp[i] = l;
419                                                 vt[i++] = l->v;
420                                         }
421                                         if (vt[0] == vt[1] || vt[0] == vt[2]) {
422                                                 i += 1;
423                                         }
424                                 }*/
425                         }
426                 }
427                 if (oldlen == len) break;
428                 oldlen = len;
429
430 #endif