split dissolve_disk into dissolve_vert dissolve_disk as agreed. also made dissolve...
[blender.git] / source / blender / bmesh / intern / bmesh_mods.c
1 #include <limits.h>
2 #include "MEM_guardedalloc.h"
3
4 #include "DNA_listBase.h"
5 #include "BKE_utildefines.h"
6 #include "BLI_blenlib.h"
7 #include "BLI_linklist.h"
8 #include "BLI_ghash.h"
9 #include "BLI_arithb.h"
10
11 #include "bmesh.h"
12 #include "bmesh_private.h"
13
14 #include <stdlib.h>
15 #include <string.h>
16
17 /*
18  * BME_MODS.C
19  *
20  * This file contains functions for locally modifying
21  * the topology of existing mesh data. (split, join, flip ect).
22  *
23 */
24
25 /**
26  *                      bmesh_dissolve_disk
27  *
28  *  Turns the face region surrounding a manifold vertex into 
29  *  A single polygon.
30  *
31  * 
32  * Example:
33  * 
34  *          |=========|             |=========|
35  *          |  \   /  |             |         |
36  * Before:  |    V    |      After: |         |
37  *          |  /   \  |             |         |
38  *          |=========|             |=========|
39  * 
40  * 
41  */
42 #if 1
43 int BM_Dissolve_Vert(BMesh *bm, BMVert *v) {
44         BMIter iter;
45         BMEdge *e;
46         int len=0;
47
48         if (!v) return 0;
49         
50         e = BMIter_New(&iter, bm, BM_EDGES_OF_VERT, v);
51         for (; e; e=BMIter_Step(&iter)) {
52                 len++;
53         }
54         
55         if (len == 1) {
56                 bmesh_ke(bm, v->edge);
57                 bmesh_kv(bm, v);
58                 return 1;
59         }
60
61         if(BM_Nonmanifold_Vert(bm, v)) {
62                 if (!v->edge) bmesh_kv(bm, v);
63                 else if (!v->edge->loop) {
64                         bmesh_ke(bm, v->edge);
65                         bmesh_kv(bm, v);
66                 } else return 0;
67
68                 return 1;
69         }
70
71         return BM_Dissolve_Disk(bm, v);
72 }
73
74 int BM_Dissolve_Disk(BMesh *bm, BMVert *v) {
75         BMFace *f, *f2;
76         BMEdge *e, *keepedge=NULL, *baseedge=NULL;
77         BMLoop *loop;
78         int done, len;
79
80         if(BM_Nonmanifold_Vert(bm, v)) {
81                 return 0;
82         }
83         
84         if(v->edge){
85                 /*v->edge we keep, what else?*/
86                 e = v->edge;
87                 len = 0;
88                 do{
89                         e = bmesh_disk_nextedge(e,v);
90                         if(!(BM_Edge_Share_Faces(e, v->edge))){
91                                 keepedge = e;
92                                 baseedge = v->edge;
93                                 break;
94                         }
95                         len++;
96                 }while(e != v->edge);
97         }
98         
99         /*this code for handling 2 and 3-valence verts
100           may be totally bad.*/
101         if (keepedge == NULL && len == 3) {
102                 /*handle specific case for three-valence.  solve it by
103                   increasing valence to four.  this may be hackish. . .*/
104                 loop = e->loop;
105                 if (loop->v == v) loop = (BMLoop*) loop->head.next;
106                 BM_Split_Face(bm, loop->f, v, loop->v, NULL, NULL, 0);
107
108                 BM_Dissolve_Disk(bm, v);
109                 return;
110         } else if (keepedge == NULL && len == 2) {
111                 /*handle two-valence*/
112                 f = v->edge->loop->f;
113                 f2 = ((BMLoop*)v->edge->loop->radial.next->data)->f;
114                 /*collapse the vertex*/
115                 BM_Collapse_Vert(bm, v->edge, v, 1.0, 0);
116                 BM_Join_Faces(bm, f, f2, NULL, 0, 0);
117         }
118
119         if(keepedge){
120                 done = 0;
121                 while(!done){
122                         done = 1;
123                         e = v->edge;
124                         do{
125                                 f = NULL;
126                                 len = bmesh_cycle_length(&(e->loop->radial));
127                                 if(len == 2 && (e!=baseedge) && (e!=keepedge)) {
128                                         f = BM_Join_Faces(bm, e->loop->f, ((BMLoop*)(e->loop->radial.next->data))->f, e, 0, 0); 
129                                         /*return if couldn't join faces in manifold
130                                           conditions.*/
131                                         //!disabled for testing why bad things happen
132                                         if (!f) return 0;
133                                 }
134
135                                 if(f){
136                                         done = 0;
137                                         break;
138                                 }
139                                 e = bmesh_disk_nextedge(e, v);
140                         }while(e != v->edge);
141                 }
142
143                 /*get remaining two faces*/
144                 f = v->edge->loop->f;
145                 f2 = ((BMLoop*)v->edge->loop->radial.next->data)->f;
146                 /*collapse the vertex*/
147                 BM_Collapse_Vert(bm, baseedge, v, 1.0, 0);
148
149                 /*join two remaining faces*/
150                 BM_Join_Faces(bm, f, f2, NULL, 0, 0);
151         }
152
153         return 1;
154 }
155 #else
156 void BM_Dissolve_Disk(BMesh *bm, BMVert *v){
157         BMFace *f;
158         BMEdge *e;
159         BMIter iter;
160         int done, len;
161         
162         if(v->edge){
163                 done = 0;
164                 while(!done){
165                         done = 1;
166                         
167                         /*loop the edges looking for an edge to dissolve*/
168                         for (e=BMIter_New(&iter, bm, BM_EDGES_OF_VERT, v); e;
169                              e = BMIter_Step(&iter)) {
170                                 f = NULL;
171                                 len = bmesh_cycle_length(&(e->loop->radial));
172                                 if(len == 2){
173                                         f = BM_Join_Faces(bm,e->loop->f,((BMLoop*)
174                                               (e->loop->radial.next->data))->f, 
175                                                e, 1, 0);
176                                 }
177                                 if(f){ 
178                                         done = 0;
179                                         break;
180                                 }
181                         };
182                 }
183                 BM_Collapse_Vert(bm, v->edge, v, 1.0, 1);
184         }
185 }
186 #endif
187
188 /**
189  *                      bmesh_join_faces
190  *
191  *  joins two adjacenct faces togather. If weldUVs == 1
192  *  and the uv/vcols of the two faces are non-contigous, the
193  *  per-face properties of f2 will be transformed into place
194  *  around f1.
195  * 
196  *  Returns -
197  *      BMFace pointer
198  */
199  
200 BMFace *BM_Join_Faces(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e, int calcnorm, int weldUVs) {
201
202         BMLoop *l1, *l2;
203         BMEdge *jed=NULL;
204         
205         jed = e;
206         if(!jed){
207                 /*search for an edge that has both these faces in its radial cycle*/
208                 l1 = f1->loopbase;
209                 do{
210                         if( ((BMLoop*)l1->radial.next->data)->f == f2 ){
211                                 jed = l1->e;
212                                 break;
213                         }
214                         l1 = ((BMLoop*)(l1->head.next));
215                 }while(l1!=f1->loopbase);
216         }
217
218         l1 = jed->loop;
219         l2 = l1->radial.next->data;
220         if (l1->v == l2->v) {
221                 bmesh_loop_reverse(bm, f2);
222         }
223
224         return bmesh_jfke(bm, f1, f2, jed);
225 }
226
227 /*connects two verts together, automatically (if very naively) finding the
228   face they both share (if there is one) and splittling it.  use this at your 
229   own risk, as it doesn't handle the many complex cases it should (like zero-area faces,
230   multiple faces, etc).
231
232   this is really only meant for cases where you don't know before hand the face
233   the two verts belong to for splitting (e.g. the subdivision operator).
234 */
235
236 BMEdge *BM_Connect_Verts(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf) {
237         BMIter iter, iter2;
238         BMVert *v;
239         BMLoop *nl;
240         BMFace *face;
241
242         /*this isn't the best thing in the world.  it doesn't handle cases where there's
243           multiple faces yet.  that might require a convexity test to figure out which
244           face is "best," and who knows what for non-manifold conditions.*/
245         for (face = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v1); face; face=BMIter_Step(&iter)) {
246                 for (v=BMIter_New(&iter2, bm, BM_VERTS_OF_FACE, face); v; v=BMIter_Step(&iter2)) {
247                         if (v == v2) {
248                                 face = BM_Split_Face(bm, face, v1, v2, &nl, NULL, 1);
249
250                                 if (nf) *nf = face;
251                                 return nl->e;
252                         }
253                 }
254         }
255
256         return NULL;
257 }
258
259 /**
260  *                      BM_split_face
261  *
262  *  Splits a single face into two.
263  * 
264  *  Returns -
265  *      BMFace pointer
266  */
267  
268 BMFace *BM_Split_Face(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **nl, BMEdge *example, int calcnorm)
269 {
270         BMFace *nf;
271         nf = bmesh_sfme(bm,f,v1,v2,nl);
272         
273         /*
274         nf->flag = f->flag;
275         if (example->flag & SELECT) f->flag |= BM_SELECT;
276         nf->h = f->h;
277         nf->mat_nr = f->mat_nr;
278         if (nl && example) {
279                 (*nl)->e->flag = example->flag;
280                 (*nl)->e->h = example->h;
281                 (*nl)->e->crease = example->crease;
282                 (*nl)->e->bweight = example->bweight;
283         }
284         */
285         return nf;
286 }
287
288 /**
289  *                      bmesh_collapse_vert
290  *
291  *  Collapses a vertex that has only two manifold edges
292  *  onto a vertex it shares an edge with. Fac defines
293  *  the amount of interpolation for Custom Data.
294  *
295  *  Note that this is not a general edge collapse function. For
296  *  that see BM_manifold_edge_collapse 
297  *
298  *  TODO:
299  *    Insert error checking for KV valance.
300  *
301  *  Returns -
302  *      Nothing
303  */
304  
305 void BM_Collapse_Vert(BMesh *bm, BMEdge *ke, BMVert *kv, float fac, int calcnorm){
306         void *src[2];
307         float w[2];
308         BMLoop *l=NULL, *kvloop=NULL, *tvloop=NULL;
309         BMVert *tv = bmesh_edge_getothervert(ke,kv);
310
311         w[0] = 1.0f - fac;
312         w[1] = fac;
313
314         if(ke->loop){
315                 l = ke->loop;
316                 do{
317                         if(l->v == tv && ((BMLoop*)(l->head.next))->v == kv){
318                                 tvloop = l;
319                                 kvloop = ((BMLoop*)(l->head.next));
320
321                                 src[0] = kvloop->data;
322                                 src[1] = tvloop->data;
323                                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, kvloop->data);                                                              
324                         }
325                         l=l->radial.next->data;
326                 }while(l!=ke->loop);
327         }
328         BM_Data_Interp_From_Verts(bm, kv, tv, kv, fac);   
329         bmesh_jekv(bm,ke,kv);
330 }
331
332 /**
333  *                      BM_split_edge
334  *      
335  *      Splits an edge. v should be one of the vertices in e and
336  *  defines the direction of the splitting operation for interpolation
337  *  purposes.
338  *
339  *  Returns -
340  *      the new vert
341  */
342
343 BMVert *BM_Split_Edge(BMesh *bm, BMVert *v, BMEdge *e, BMEdge **ne, float percent, int calcnorm) {
344         BMVert *nv, *v2;
345
346         v2 = bmesh_edge_getothervert(e,v);
347         nv = bmesh_semv(bm,v,e,ne);
348         if (nv == NULL) return NULL;
349         VECSUB(nv->co,v2->co,v->co);
350         VECADDFAC(nv->co,v->co,nv->co,percent);
351         if (ne) {
352                 if(bmesh_test_sysflag(&(e->head), BM_SELECT)) bmesh_set_sysflag(&((*ne)->head), BM_SELECT);
353                 if(bmesh_test_sysflag(&(e->head), BM_HIDDEN)) bmesh_set_sysflag(&((*ne)->head), BM_HIDDEN);
354         }
355         /*v->nv->v2*/
356         BM_Data_Facevert_Edgeinterp(bm,v2, v, nv, e, percent);  
357         BM_Data_Interp_From_Verts(bm, v2, v, nv, percent);
358         return nv;
359 }
360
361 BMVert  *BM_Split_Edge_Multi(BMesh *bm, BMEdge *e, int numcuts)
362 {
363         int i;
364         float percent;
365         BMVert *nv = NULL;
366         
367         for(i=0; i < numcuts; i++){
368                 percent = 1.0f / (float)(numcuts + 1 - i);
369                 nv = BM_Split_Edge(bm, e->v2, e, NULL, percent, 0);
370         }
371         return nv;
372 }
373
374 int BM_Validate_Face(BMesh *bm, BMFace *face, FILE *err) 
375 {
376         BMIter iter;
377         V_DECLARE(verts);
378         BMVert **verts = NULL;
379         BMLoop *l;
380         int ret = 1, i, j;
381         
382         if (face->len == 2) {
383                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
384                 fflush(err);
385         }
386
387         for (l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, face);l;l=BMIter_Step(&iter)) {
388                 V_GROW(verts);
389                 verts[V_COUNT(verts)-1] = l->v;
390                 
391                 if (l->e->v1 == l->e->v2) {
392                         fprintf(err, "Found bmesh edge with identical verts!\n");
393                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
394                         fflush(err);
395                         ret = 0;
396                 }
397         }
398
399         for (i=0; i<V_COUNT(verts); i++) {
400                 for (j=0; j<V_COUNT(verts); j++) {
401                         if (j == 0) continue;
402                         if (verts[i] == verts[j]) {
403                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
404                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
405                                 fflush(err);
406                                 ret = 0;
407                         }
408                 }
409         }
410         
411         V_FREE(verts);
412         return ret;
413 }