1ef6725350a4b485058bfd449178983853485b77
[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
6 #include "BLI_utildefines.h"
7 #include "BLI_blenlib.h"
8 #include "BLI_linklist.h"
9 #include "BLI_ghash.h"
10 #include "BLI_math.h"
11 #include "BLI_array.h"
12 #include "BLI_utildefines.h"
13 #include "BLI_smallhash.h"
14
15 #include "bmesh.h"
16 #include "bmesh_private.h"
17
18 #include <stdlib.h>
19 #include <string.h>
20
21 /*
22  * BME_MODS.C
23  *
24  * This file contains functions for locally modifying
25  * the topology of existing mesh data. (split, join, flip ect).
26  *
27 */
28
29 /**
30  *                      bmesh_dissolve_disk
31  *
32  *  Turns the face region surrounding a manifold vertex into 
33  *  A single polygon.
34  *
35  * 
36  * Example:
37  * 
38  *          |=========|             |=========|
39  *          |  \   /  |             |         |
40  * Before:  |    V    |      After: |         |
41  *          |  /   \  |             |         |
42  *          |=========|             |=========|
43  * 
44  * 
45  */
46 #if 1
47 int BM_Dissolve_Vert(BMesh *bm, BMVert *v) {
48         BMIter iter;
49         BMEdge *e;
50         int len=0;
51
52         if (!v) return 0;
53         
54         e = BMIter_New(&iter, bm, BM_EDGES_OF_VERT, v);
55         for (; e; e=BMIter_Step(&iter)) {
56                 len++;
57         }
58         
59         if (len == 1) {
60                 if (v->e) 
61                         BM_Kill_Edge(bm, v->e);
62                 BM_Kill_Vert(bm, v);
63                 return 1;
64         }
65
66         if(BM_Nonmanifold_Vert(bm, v)) {
67                 if (!v->e) BM_Kill_Vert(bm, v);
68                 else if (!v->e->l) {
69                         BM_Kill_Edge(bm, v->e);
70                         BM_Kill_Vert(bm, v);
71                 } else return 0;
72
73                 return 1;
74         }
75
76         return BM_Dissolve_Disk(bm, v);
77 }
78
79 int BM_Dissolve_Disk(BMesh *bm, BMVert *v) {
80         BMFace *f, *f2;
81         BMEdge *e, *keepedge=NULL, *baseedge=NULL;
82         BMLoop *loop;
83         int done, len= 0;
84
85         if(BM_Nonmanifold_Vert(bm, v)) {
86                 return 0;
87         }
88         
89         if(v->e){
90                 /*v->e we keep, what else?*/
91                 e = v->e;
92                 do{
93                         e = bmesh_disk_nextedge(e,v);
94                         if(!(BM_Edge_Share_Faces(e, v->e))){
95                                 keepedge = e;
96                                 baseedge = v->e;
97                                 break;
98                         }
99                         len++;
100                 }while(e != v->e);
101         }
102         
103         /*this code for handling 2 and 3-valence verts
104           may be totally bad.*/
105         if (keepedge == NULL && len == 3) {
106                 /*handle specific case for three-valence.  solve it by
107                   increasing valence to four.  this may be hackish. . .*/
108                 loop = e->l;
109                 if (loop->v == v) loop = (BMLoop*) loop->next;
110                 if (!BM_Split_Face(bm, loop->f, v, loop->v, NULL, NULL))
111                         return 0;
112
113                 BM_Dissolve_Disk(bm, v);
114                 return 1;
115         } else if (keepedge == NULL && len == 2) {
116                 /*handle two-valence*/
117                 f = v->e->l->f;
118                 f2 = ((BMLoop*)v->e->l->radial_next)->f;
119                 
120                 /*collapse the vertex*/
121                 BM_Collapse_Vert(bm, v->e, v, 1.0);
122                 
123                 if (f != f2 && !BM_Join_TwoFaces(bm, f, f2, NULL))
124                         return 0;
125
126                 return 1;
127         }
128
129         if(keepedge){
130                 done = 0;
131                 while(!done){
132                         done = 1;
133                         e = v->e;
134                         do{
135                                 f = NULL;
136                                 len = bmesh_radial_length(e->l);
137                                 if(len == 2 && (e!=baseedge) && (e!=keepedge)) {
138                                         f = BM_Join_TwoFaces(bm, e->l->f, ((BMLoop*)(e->l->radial_next))->f, e);
139                                         /*return if couldn't join faces in manifold
140                                           conditions.*/
141                                         //!disabled for testing why bad things happen
142                                         if (!f) return 0;
143                                 }
144
145                                 if(f){
146                                         done = 0;
147                                         break;
148                                 }
149                                 e = bmesh_disk_nextedge(e, v);
150                         }while(e != v->e);
151                 }
152
153                 /*get remaining two faces*/
154                 f = v->e->l->f;
155                 f2 = ((BMLoop*)v->e->l->radial_next)->f;
156
157                 /*collapse the vertex*/
158                 BM_Collapse_Vert(bm, baseedge, v, 1.0);
159                 
160                 if (f != f2) {
161                         /*join two remaining faces*/
162                         if (!BM_Join_TwoFaces(bm, f, f2, NULL)) return 0;
163                 }
164         }
165
166         return 1;
167 }
168 #else
169 void BM_Dissolve_Disk(BMesh *bm, BMVert *v){
170         BMFace *f;
171         BMEdge *e;
172         BMIter iter;
173         int done, len;
174         
175         if(v->e){
176                 done = 0;
177                 while(!done){
178                         done = 1;
179                         
180                         /*loop the edges looking for an edge to dissolve*/
181                         for (e=BMIter_New(&iter, bm, BM_EDGES_OF_VERT, v); e;
182                              e = BMIter_Step(&iter)) {
183                                 f = NULL;
184                                 len = bmesh_cycle_length(&(e->l->radial));
185                                 if(len == 2){
186                                         f = BM_Join_TwoFaces(bm,e->l->f,((BMLoop*)
187                                               (e->l->radial_next))->f, 
188                                                e);
189                                 }
190                                 if(f){ 
191                                         done = 0;
192                                         break;
193                                 }
194                         };
195                 }
196                 BM_Collapse_Vert(bm, v->e, v, 1.0);
197         }
198 }
199 #endif
200
201 /**
202  *                      bmesh_join_faces
203  *
204  *  joins two adjacenct faces togather.
205  * 
206  *  Returns -
207  *      BMFace pointer
208  */
209  
210 BMFace *BM_Join_TwoFaces(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e) {
211
212         BMLoop *l1, *l2;
213         BMEdge *jed=NULL;
214         BMFace *faces[2] = {f1, f2};
215         
216         jed = e;
217         if(!jed){
218                 /*search for an edge that has both these faces in its radial cycle*/
219                 l1 = bm_firstfaceloop(f1);
220                 do{
221                         if( ((BMLoop*)l1->radial_next)->f == f2 ){
222                                 jed = l1->e;
223                                 break;
224                         }
225                         l1 = ((BMLoop*)(l1->next));
226                 }while(l1!=bm_firstfaceloop(f1));
227         }
228
229         if (!jed) {
230                 bmesh_error();
231                 return NULL;
232         }
233         
234         l1 = jed->l;
235         
236         if (!l1) {
237                 bmesh_error();
238                 return NULL;
239         }
240         
241         l2 = l1->radial_next;
242         if (l1->v == l2->v) {
243                 bmesh_loop_reverse(bm, f2);
244         }
245
246         f1 = BM_Join_Faces(bm, faces, 2);
247         
248         return f1;
249 }
250
251 /*connects two verts together, automatically (if very naively) finding the
252   face they both share (if there is one) and splittling it.  use this at your 
253   own risk, as it doesn't handle the many complex cases it should (like zero-area faces,
254   multiple faces, etc).
255
256   this is really only meant for cases where you don't know before hand the face
257   the two verts belong to for splitting (e.g. the subdivision operator).
258 */
259
260 BMEdge *BM_Connect_Verts(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf) {
261         BMIter iter, iter2;
262         BMVert *v;
263         BMLoop *nl;
264         BMFace *face;
265
266         /*be warned: this can do weird things in some ngon situation, see BM_LegalSplits*/
267         for (face = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v1); face; face=BMIter_Step(&iter)) {
268                 for (v=BMIter_New(&iter2, bm, BM_VERTS_OF_FACE, face); v; v=BMIter_Step(&iter2)) {
269                         if (v == v2) {
270                                 face = BM_Split_Face(bm, face, v1, v2, &nl, NULL);
271
272                                 if (nf) *nf = face;
273                                 return nl->e;
274                         }
275                 }
276         }
277
278         return NULL;
279 }
280
281 /**
282  *                      BM_split_face
283  *
284  *  Splits a single face into two.
285  * 
286  *  Returns -
287  *      BMFace pointer
288  */
289
290 BMFace *BM_Split_Face(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **nl, BMEdge *UNUSED(example))
291 {
292         BMFace *nf, *of;
293         
294         /*do we have a multires layer?*/
295         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
296                 of = BM_Copy_Face(bm, f, 0, 0);
297         }
298         
299         nf = bmesh_sfme(bm, f, v1, v2, nl, NULL);
300         
301         if (nf) {
302                 BM_Copy_Attributes(bm, bm, f, nf);
303                 copy_v3_v3(nf->no, f->no);
304         }
305         
306         /*handle multires update*/
307         if (nf && nf != f && CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
308                 BMLoop *l;
309                 
310                 l = bm_firstfaceloop(f);
311                 do {
312                         BM_loop_interp_from_face(bm, l, of, 0, 1);
313                         l = l->next;
314                 } while (l != bm_firstfaceloop(f));
315
316                 l = bm_firstfaceloop(nf);
317                 do {
318                         BM_loop_interp_from_face(bm, l, of, 0, 1);
319                         l = l->next;
320                 } while (l != bm_firstfaceloop(nf));
321                 
322                 BM_Kill_Face(bm, of);
323                 
324                 BM_multires_smooth_bounds(bm, f);
325                 if (nf) 
326                         BM_multires_smooth_bounds(bm, nf);
327         }
328
329         return nf;
330 }
331
332 /**
333  *                      bmesh_collapse_vert
334  *
335  *  Collapses a vertex that has only two manifold edges
336  *  onto a vertex it shares an edge with. Fac defines
337  *  the amount of interpolation for Custom Data.
338  *
339  *  Note that this is not a general edge collapse function.
340  *
341  *  TODO:
342  *    Insert error checking for KV valance.
343  *
344  *  Returns -
345  *      Nothing
346  */
347  
348 void BM_Collapse_Vert(BMesh *bm, BMEdge *ke, BMVert *kv, float fac){
349         BMFace **faces = NULL, **oldfaces=NULL, *f;
350         BLI_array_staticdeclare(faces, 8);
351         BMIter iter;
352         BMLoop *l=NULL, *kvloop=NULL, *tvloop=NULL;
353         BMVert *tv = bmesh_edge_getothervert(ke,kv);
354         void *src[2];
355         float w[2];
356
357         w[0] = 1.0f - fac;
358         w[1] = fac;
359
360         if(ke->l){
361                 l = ke->l;
362                 do{
363                         if(l->v == tv && ((BMLoop*)(l->next))->v == kv){
364                                 tvloop = l;
365                                 kvloop = ((BMLoop*)(l->next));
366
367                                 src[0] = kvloop->head.data;
368                                 src[1] = tvloop->head.data;
369                                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, kvloop->head.data);
370                         }
371                         l=l->radial_next;
372                 }while(l!=ke->l);
373         }
374
375         BM_ITER(f, &iter, bm, BM_FACES_OF_VERT, kv) {
376                 BLI_array_append(faces, f);
377         }
378         
379         BM_Data_Interp_From_Verts(bm, kv, tv, kv, fac);
380
381         //bmesh_jekv(bm,ke,kv);
382         if (faces && BLI_array_count(faces) > 1) {
383                 BMFace *f2;
384                 BMEdge *e2;
385                 BMVert *tv2;
386
387                 /*ok, no faces, means we have a wire edge*/
388                 e2 = bmesh_disk_nextedge(ke, kv);
389                 tv2 = BM_OtherEdgeVert(e2, kv);
390
391                 f2 = BM_Join_Faces(bm, faces, BLI_array_count(faces));
392                 if (f2) 
393                         BM_Split_Face(bm, f2, tv, tv2, NULL, NULL);
394         } else if (faces && BLI_array_count(faces) == 1) {
395                 BMLoop **loops = NULL;
396                 BMEdge *e;
397                 BMVert **verts = NULL;
398                 BMEdge **edges = NULL;
399                 BMFace *f2;
400                 BLI_array_staticdeclare(verts, 64);
401                 BLI_array_staticdeclare(edges, 64);
402                 BLI_array_staticdeclare(loops, 64);
403                 int i;
404                 
405                 /*create new face excluding kv*/
406                 f = *faces;
407                 l = bm_firstfaceloop(f);
408                 i = 0;
409                 do {
410                         if (l->v != kv) {
411                                 BLI_array_append(verts, l->v);
412
413                                 if (l->e != ke && !BM_Vert_In_Edge(l->e, kv)) { 
414                                         BLI_array_append(edges, l->e);
415                                 } else {
416                                         BMVert *v2;
417                                         
418                                         if (BM_Vert_In_Edge(l->next->e, kv))
419                                                 v2 = BM_OtherEdgeVert(l->next->e, kv);
420                                         else
421                                                 v2 = BM_OtherEdgeVert(l->prev->e, kv);
422                                                 
423                                         e = BM_Make_Edge(bm, BM_OtherEdgeVert(l->e, kv), v2, l->e, 1);
424                                         BLI_array_append(edges, e);
425                                 }
426
427                                 BLI_array_append(loops, l);
428                                 i++;
429                         }
430                         
431                         l = l->next;
432                 } while (l != bm_firstfaceloop(f));
433                 
434                 f2 = BM_Make_Face(bm, verts, edges, BLI_array_count(verts));
435                 l = bm_firstfaceloop(f2);
436                 i = 0;
437                 do {
438                         BM_Copy_Attributes(bm, bm, loops[i], l);
439                         BM_loop_interp_multires(bm, loops[i], l->f);
440                         i++;
441                         l = l->next;
442                 } while (l != bm_firstfaceloop(f2));
443                 
444                 BM_Copy_Attributes(bm, bm, f, f2);
445                 BM_Kill_Face(bm, f);
446                 BM_Kill_Vert(bm, kv);
447         } else {
448                 BMVert *tv2;
449                 BMEdge *e2, *ne;
450
451                 /*ok, no faces, means we have a wire edge*/
452                 e2 = bmesh_disk_nextedge(ke, kv);
453                 tv2 = BM_OtherEdgeVert(e2, kv);
454
455                 ne = BM_Make_Edge(bm, tv, tv2, ke, 0);
456
457                 BM_Kill_Edge(bm, ke);
458                 BM_Kill_Edge(bm, e2);
459                 BM_Kill_Vert(bm, kv);
460         }
461
462         BLI_array_free(faces);
463 }
464
465 /**
466  *                      BM_split_edge
467  *      
468  *      Splits an edge. v should be one of the vertices in e and
469  *  defines the direction of the splitting operation for interpolation
470  *  purposes.
471  *
472  *  Returns -
473  *      the new vert
474  */
475
476 BMVert *BM_Split_Edge(BMesh *bm, BMVert *v, BMEdge *e, BMEdge **ne, float percent) {
477         BMVert *nv, *v2;
478         BMFace **oldfaces = NULL;
479         BMEdge *dummy;
480         BLI_array_staticdeclare(oldfaces, 32);
481         SmallHash hash;
482
483         /*we need this for handling multires*/  
484         if (!ne) 
485                 ne = &dummy;
486
487         /*do we have a multires layer?*/
488         if (CustomData_has_layer(&bm->ldata, CD_MDISPS) && e->l) {
489                 BMLoop *l;
490                 int i;
491                 
492                 l = e->l;
493                 do {
494                         BLI_array_append(oldfaces, l->f);
495                         l = l->radial_next;
496                 } while (l != e->l);
497                 
498                 /*create a hash so we can differentiate oldfaces from new faces*/
499                 BLI_smallhash_init(&hash);
500                 
501                 for (i=0; i<BLI_array_count(oldfaces); i++) {
502                         oldfaces[i] = BM_Copy_Face(bm, oldfaces[i], 1, 1);
503                         BLI_smallhash_insert(&hash, (intptr_t)oldfaces[i], NULL);
504                 }               
505         }
506
507         v2 = bmesh_edge_getothervert(e,v);
508         nv = bmesh_semv(bm,v,e,ne);
509         if (nv == NULL) return NULL;
510
511         sub_v3_v3v3(nv->co,v2->co,v->co);
512         VECADDFAC(nv->co,v->co,nv->co,percent);
513
514         if (ne) {
515                 (*ne)->head.flag = e->head.flag;
516                 BM_Copy_Attributes(bm, bm, e, *ne);
517         }
518
519         /*v->nv->v2*/
520         BM_Data_Facevert_Edgeinterp(bm, v2, v, nv, e, percent); 
521         BM_Data_Interp_From_Verts(bm, v, v2, nv, percent);
522
523         if (CustomData_has_layer(&bm->ldata, CD_MDISPS) && e->l && nv) {
524                 int i, j;
525                 
526                 /*interpolate new/changed loop data from copied old faces*/
527                 for (j=0; j<2; j++) {
528                         for (i=0; i<BLI_array_count(oldfaces); i++) {
529                                 BMEdge *e1 = j ? *ne : e;
530                                 BMLoop *l, *l2;
531                                 
532                                 l = e1->l;
533                                 if (!l) {
534                                         bmesh_error();
535                                         break;
536                                 }
537                                 
538                                 do {
539                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l->f)) {
540                                                 l2 = bm_firstfaceloop(l->f);
541                                                 do {
542                                                         BM_loop_interp_multires(bm, l2, oldfaces[i]);
543                                                         l2 = l2->next;
544                                                 } while (l2 != bm_firstfaceloop(l->f));
545                                         }
546                                         l = l->radial_next;
547                                 } while (l != e1->l);
548                         }
549                 }
550                 
551                 /*destroy the old faces*/
552                 for (i=0; i<BLI_array_count(oldfaces); i++) {
553                         BM_Kill_Face_Verts(bm, oldfaces[i]);
554                 }
555                 
556                 /*fix boundaries a bit, doesn't work too well quite yet*/
557 #if 0
558                 for (j=0; j<2; j++) {
559                         BMEdge *e1 = j ? *ne : e;
560                         BMLoop *l, *l2;
561                         
562                         l = e1->l;
563                         if (!l) {
564                                 bmesh_error();
565                                 break;
566                         }
567                         
568                         do {
569                                 BM_multires_smooth_bounds(bm, l->f);                            
570                                 l = l->radial_next;
571                         } while (l != e1->l);
572                 }
573 #endif
574                 
575                 BLI_array_free(oldfaces);
576                 BLI_smallhash_release(&hash);
577         }
578         
579         return nv;
580 }
581
582 BMVert  *BM_Split_Edge_Multi(BMesh *bm, BMEdge *e, int numcuts)
583 {
584         int i;
585         float percent;
586         BMVert *nv = NULL;
587         
588         for(i=0; i < numcuts; i++){
589                 percent = 1.0f / (float)(numcuts + 1 - i);
590                 nv = BM_Split_Edge(bm, e->v2, e, NULL, percent);
591         }
592         return nv;
593 }
594
595 int BM_Validate_Face(BMesh *bm, BMFace *face, FILE *err) 
596 {
597         BMIter iter;
598         BLI_array_declare(verts);
599         BMVert **verts = NULL;
600         BMLoop *l;
601         int ret = 1, i, j;
602         
603         if (face->len == 2) {
604                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
605                 fflush(err);
606         }
607
608         for (l=BMIter_New(&iter, bm, BM_LOOPS_OF_FACE, face);l;l=BMIter_Step(&iter)) {
609                 BLI_array_growone(verts);
610                 verts[BLI_array_count(verts)-1] = l->v;
611                 
612                 if (l->e->v1 == l->e->v2) {
613                         fprintf(err, "Found bmesh edge with identical verts!\n");
614                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
615                         fflush(err);
616                         ret = 0;
617                 }
618         }
619
620         for (i=0; i<BLI_array_count(verts); i++) {
621                 for (j=0; j<BLI_array_count(verts); j++) {
622                         if (j == i) continue;
623                         if (verts[i] == verts[j]) {
624                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
625                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
626                                 fflush(err);
627                                 ret = 0;
628                         }
629                 }
630         }
631         
632         BLI_array_free(verts);
633         return ret;
634 }
635
636 /*
637             BM Rotate Edge
638
639     Spins an edge topologically, either counter-clockwise or clockwise.
640     If ccw is true, the edge is spun counter-clockwise, otherwise it is
641     spun clockwise.
642     
643     Returns the spun edge.  Note that this works by dissolving the edge
644     then re-creating it, so the returned edge won't have the same pointer
645     address as the original one.
646
647     Returns NULL on error (e.g., if the edge isn't surrounded by exactly
648     two faces).
649 */
650 BMEdge *BM_Rotate_Edge(BMesh *bm, BMEdge *e, int ccw)
651 {
652         BMVert *v1, *v2;
653         BMLoop *l, *l1, *l2, *nl;
654         BMFace *f;
655         BMIter liter;
656
657         v1 = e->v1;
658         v2 = e->v2;
659
660         if (BM_Edge_FaceCount(e) != 2)
661                 return NULL;
662
663         f = BM_Join_TwoFaces(bm, e->l->f, ((BMLoop*)e->l->radial_next)->f, e);
664         
665         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
666                 if (l->v == v1)
667                         l1 = l;
668                 else if (l->v == v2)
669                         l2 = l;
670         }
671         
672         if (ccw) {
673                 l1 = (BMLoop*) l1->prev;
674                 l2 = (BMLoop*) l2->prev;
675         } else {
676                 l1 = (BMLoop*) l1->next;
677                 l2 = (BMLoop*) l2->next;
678         }
679
680         if (!BM_Split_Face(bm, f, l1->v, l2->v, &nl, NULL))
681                 return NULL;
682
683         return nl->e;
684 }