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