dissolve faces: errors-out on holes, preserves winding, and doesn't delete original...
[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);
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;
53         BMLoop *l, *l2;
54         BMFace *f, *f2, *nf = NULL;
55         V_DECLARE(region);
56         V_DECLARE(regions);
57         BMLoop ***regions = NULL;
58         BMLoop **region = NULL;
59         BMWalker walker, regwalker;
60         int i, j, fcopied;
61
62         BMO_Flag_Buffer(bm, op, BMOP_DISFACES_FACEIN, FACE_MARK);
63         
64         /*collect regions*/
65         f = BMO_IterNew(&oiter, bm, op, BMOP_DISFACES_FACEIN);
66         for (; f; f=BMO_IterStep(&oiter)) {
67                 if (!BMO_TestFlag(bm, f, FACE_MARK)) continue;
68
69                 l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
70                 for (; l; l=BMIter_Step(&liter)) {
71                         l2 = bmesh_radial_nextloop(l);
72                         if (l2!=l && BMO_TestFlag(bm, l2->f, FACE_MARK))
73                                 continue;
74                         if (BM_FacesAroundEdge(l->e) <= 2) {
75                                 V_RESET(region);
76                                 region = NULL; /*forces different allocation*/
77
78                                 /*yay, walk!*/
79                                 BMW_Init(&walker, bm, BMW_ISLANDBOUND, FACE_MARK);
80                                 l = BMW_Begin(&walker, l);
81                                 for (; l; l=BMW_Step(&walker)) {
82                                         V_GROW(region);
83                                         region[V_COUNT(region)-1] = l;
84                                         BMO_SetFlag(bm, l->e, EDGE_MARK);
85                                 }
86                                 BMW_End(&walker);
87
88                                 if (BMO_HasError(bm)) {
89                                         BMO_ClearStack(bm);
90                                         BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
91                                         goto cleanup;
92                                 }
93                                 
94                                 if (region == NULL) continue;
95
96                                 /*check for holes in boundary*/
97                                 if (!check_hole_in_region(bm, region[0]->f)) {
98                                         BMO_RaiseError(bm, op, 
99                                               BMERR_DISSOLVEFACES_FAILED, 
100                                               "Hole(s) in face region");
101                                         goto cleanup;
102                                 }
103                                 
104                                 BMW_Init(&regwalker, bm, BMW_ISLAND, FACE_MARK);
105                                 f2 = BMW_Begin(&regwalker, region[0]->f);
106                                 for (; f2; f2=BMW_Step(&regwalker)) {
107                                         BMO_ClearFlag(bm, f2, FACE_MARK);
108                                         BMO_SetFlag(bm, f2, FACE_ORIG);
109                                 }
110                                 BMW_End(&regwalker);
111
112                                 if (BMO_HasError(bm)) {
113                                         BMO_ClearStack(bm);
114                                         BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
115                                         goto cleanup;
116                                 }
117                                 
118                                 V_GROW(region);
119                                 V_GROW(regions);
120                                 regions[V_COUNT(regions)-1] = region;
121                                 region[V_COUNT(region)-1] = NULL;
122                                 break;
123                         }
124                 }
125         }
126         
127         for (i=0; i<V_COUNT(regions); i++) {
128                 BMEdge **edges = NULL;
129                 V_DECLARE(edges);
130
131                 region = regions[i];
132                 for (j=0; region[j]; j++) {
133                         V_GROW(edges);
134                         edges[V_COUNT(edges)-1] = region[j]->e;
135                 }
136                 
137                 f= BM_Make_Ngon(bm, region[0]->v, region[1]->v,  edges, j, 1);
138                 
139                 /*if making the new face failed (e.g. overlapping test)
140                   unmark the original faces for deletion.*/
141                 BMO_ClearFlag(bm, f, FACE_ORIG);
142                 BMO_SetFlag(bm, f, FACE_NEW);
143
144                 fcopied = 0;
145                 l=BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
146                 for (; l; l=BMIter_Step(&liter)) {
147                         /*ensure winding is identical*/
148                         l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_LOOP, l);
149                         for (; l2; l2=BMIter_Step(&liter2)) {
150                                 if (BMO_TestFlag(bm, l2->f, FACE_ORIG)) {
151                                         if (l2->v != l->v)
152                                                 bmesh_loop_reverse(bm, l2->f);
153                                         break;
154                                 }
155                         }
156                         
157                         /*copy over attributes*/
158                         l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_LOOP, l);
159                         for (; l2; l2=BMIter_Step(&liter2)) {
160                                 if (BMO_TestFlag(bm, l2->f, FACE_ORIG)) {
161                                         if (!fcopied) {
162                                                 BM_Copy_Attributes(bm, bm, l2->f, f);
163                                                 fcopied = 1;
164                                         }
165                                         BM_Copy_Attributes(bm, bm, l2, l);
166                                         break;
167                                 }
168                         }
169                 }
170         }
171
172         BMO_CallOpf(bm, "del geom=%ff context=%d", FACE_ORIG, DEL_FACES);
173         if (BMO_HasError(bm)) return;
174
175         BMO_Flag_To_Slot(bm, op, BMOP_DISFACES_REGIONOUT, FACE_NEW, BM_FACE);
176
177 cleanup:
178         /*free/cleanup*/
179         for (i=0; i<V_COUNT(regions); i++) {
180                 if (regions[i]) V_FREE(regions[i]);
181         }
182
183         V_FREE(regions);
184 }
185
186 void dissolveverts_exec(BMesh *bm, BMOperator *op)
187 {
188         BMOpSlot *vinput;
189         BMIter iter, fiter;
190         BMVert *v;
191         BMFace *f;
192         
193         vinput = BMO_GetSlot(op, BMOP_DISVERTS_VERTIN);
194
195         BMO_Flag_Buffer(bm, op, BMOP_DISVERTS_VERTIN, VERT_MARK);
196         
197         for (v=BMIter_New(&iter, bm, BM_VERTS, NULL); v; v=BMIter_Step(&iter)) {
198                 if (BMO_TestFlag(bm, v, VERT_MARK)) {
199                         f=BMIter_New(&fiter, bm, BM_FACES_OF_VERT, v);
200                         for (; f; f=BMIter_Step(&fiter)) {
201                                 BMO_SetFlag(bm, f, FACE_MARK);
202                         }
203                 }
204         }
205
206         BMO_CallOpf(bm, "dissolvefaces faces=%ff", FACE_MARK);
207         if (BMO_HasError(bm)) {
208                         char *msg;
209
210                         BMO_GetError(bm, &msg, NULL);
211                         BMO_ClearStack(bm);
212                         BMO_RaiseError(bm, op, BMERR_DISSOLVEVERTS_FAILED,msg);
213         }
214 }
215
216 /*this code is for cleaning up two-edged faces, it shall become
217   it's own function one day.*/
218 #if 0
219                 /*clean up two-edged faces*/
220                 /*basic idea is to keep joining 2-edged faces until their
221                   gone.  this however relies on joining two 2-edged faces
222                   together to work, which doesn't.*/
223                 found3 = 1;
224                 while (found3) {
225                         found3 = 0;
226                         for (f=BMIter_New(&iter, bm, BM_FACES, NULL); f; f=BMIter_Step(&iter)){
227                                 if (!BM_Validate_Face(bm, f, stderr)) {
228                                         printf("error.\n");
229                                 }
230
231                                 if (f->len == 2) {
232                                         //this design relies on join faces working
233                                         //with two-edged faces properly.
234                                         //commenting this line disables the
235                                         //outermost loop.
236                                         //found3 = 1;
237                                         found2 = 0;
238                                         l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
239                                         fe = l->e;
240                                         for (; l; l=BMIter_Step(&liter)) {
241                                                 f2 = BMIter_New(&fiter, bm,
242                                                                 BM_FACES_OF_EDGE, l->e);
243                                                 for (; f2; f2=BMIter_Step(&fiter)) {
244                                                         if (f2 != f) {
245                                                                 BM_Join_Faces(bm, f, f2, l->e, 
246                                                                               1, 0);
247                                                                 found2 = 1;
248                                                                 break;
249                                                         }
250                                                 }
251                                                 if (found2) break;
252                                         }
253
254                                         if (!found2) {
255                                                 bmesh_kf(bm, f);
256                                                 bmesh_ke(bm, fe);
257                                         }
258                                 } /*else if (f->len == 3) {
259                                         BMEdge *ed[3];
260                                         BMVert *vt[3];
261                                         BMLoop *lp[3];
262                                         int i=0;
263
264                                         //check for duplicate edges
265                                         l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
266                                         for (; l; l=BMIter_Step(&liter)) {
267                                                 ed[i] = l->e;   
268                                                 lp[i] = l;
269                                                 vt[i++] = l->v;
270                                         }
271                                         if (vt[0] == vt[1] || vt[0] == vt[2]) {
272                                                 i += 1;
273                                         }
274                                 }*/
275                         }
276                 }
277                 if (oldlen == len) break;
278                 oldlen = len;
279
280 #endif