skip assigning vars for inline bmesh flag funcs, just cast.
[blender.git] / source / blender / bmesh / intern / bmesh_newcore.c
1 #include <limits.h>
2
3 #include "BLI_math_vector.h"
4
5 #include "BKE_customdata.h"
6 #include "BKE_DerivedMesh.h"
7
8 #include "BLI_utildefines.h"
9 #include "BLI_blenlib.h"
10 #include "BLI_listbase.h"
11 #include "BLI_mempool.h"
12 #include "BLI_ghash.h"
13 #include "BLI_array.h"
14
15 #include "DNA_listBase.h"
16
17 #include "bmesh_class.h"
18
19 #include "bmesh_iterators.h"
20 #include "bmesh_private.h"
21
22 BMVert *BM_Make_Vert(BMesh *bm, float co[3], struct BMVert *example) {
23         BMVert *v = BLI_mempool_calloc(bm->vpool);
24         
25         bm->totvert += 1;
26
27         v->head.type = BM_VERT;
28
29         if (co) copy_v3_v3(v->co, co);
30         
31         /*allocate flags*/
32         v->head.flags = BLI_mempool_calloc(bm->toolflagpool);
33
34         CustomData_bmesh_set_default(&bm->vdata, &v->head.data);
35         
36         if (example) {
37                 BM_Copy_Attributes(bm, bm, (BMVert*)example, (BMVert*)v);
38         }
39
40         CHECK_ELEMENT(bm, v);
41
42         return (BMVert*) v;
43 }
44
45 /**
46  *                      BMESH EDGE EXIST
47  *
48  *  Finds out if two vertices already have an edge
49  *  connecting them. Note that multiple edges may
50  *  exist between any two vertices, and therefore
51  *  This function only returns the first one found.
52  *
53  *  Returns -
54  *      BMEdge pointer
55  */
56 BMEdge *BM_Edge_Exist(BMVert *v1, BMVert *v2)
57 {
58         BMIter iter;
59         BMEdge *e;
60
61         BM_ITER(e, &iter, NULL, BM_EDGES_OF_VERT, v1) {
62                 if (e->v1 == v2 || e->v2 == v2)
63                         return e;
64         }
65
66         return NULL;
67 }
68
69 BMEdge *BM_Make_Edge(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge *example, int nodouble) {
70         BMEdge *e;
71         
72         if (nodouble && (e=(BMEdge*)BM_Edge_Exist(v1, v2)))
73                 return (BMEdge*)e;
74         
75         e = BLI_mempool_calloc(bm->epool);
76         bm->totedge += 1;
77         e->head.type = BM_EDGE;
78         
79         /*allocate flags*/
80         e->head.flags = BLI_mempool_calloc(bm->toolflagpool);
81
82         e->v1 = (BMVert*) v1;
83         e->v2 = (BMVert*) v2;
84         
85         
86         CustomData_bmesh_set_default(&bm->edata, &e->head.data);
87         
88         bmesh_disk_append_edge(e, e->v1);
89         bmesh_disk_append_edge(e, e->v2);
90         
91         if (example)
92                 BM_Copy_Attributes(bm, bm, (BMEdge*)example, (BMEdge*)e);
93         
94         CHECK_ELEMENT(bm, e);
95
96         return (BMEdge*) e;
97 }
98
99 static BMLoop *bmesh_create_loop(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, BMLoop *example){
100         BMLoop *l=NULL;
101
102         l = BLI_mempool_calloc(bm->lpool);
103         l->next = l->prev = NULL;
104         l->v = v;
105         l->e = e;
106         l->f = f;
107         l->radial_next = l->radial_prev = NULL;
108         l->head.data = NULL;
109         l->head.type = BM_LOOP;
110
111         bm->totloop++;
112
113         if(example)
114                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->head.data, &l->head.data);
115         else
116                 CustomData_bmesh_set_default(&bm->ldata, &l->head.data);
117
118         return l;
119 }
120
121 static BMLoop *BM_Add_FaceBoundary(BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte) {
122         BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
123         BMLoop *l = (BMLoop*)bmesh_create_loop(bm, startv, starte, f, NULL);
124         
125         bmesh_radial_append(starte, l);
126
127         lst->first = lst->last = (BMLoop*)l;
128         BLI_addtail(&f->loops, lst);
129         
130         l->f = f;
131         
132         return l;       
133 }
134
135 BMFace *BM_Copy_Face(BMesh *bm, BMFace *f, int copyedges, int copyverts)
136 {
137         BMEdge **edges = NULL;
138         BMVert **verts = NULL;
139         BLI_array_staticdeclare(edges, 256);
140         BLI_array_staticdeclare(verts, 256);
141         BMLoop *l, *l2;
142         BMFace *f2;
143         int i;
144
145         l = bm_firstfaceloop(f);
146         do {
147                 if (copyverts) {
148                         BMVert *v = BM_Make_Vert(bm, l->v->co, l->v);
149                         BLI_array_append(verts, v);
150                 } else {        
151                         BLI_array_append(verts, l->v);
152                 }
153                 l = l->next;
154         } while (l != bm_firstfaceloop(f));
155
156         l = bm_firstfaceloop(f);
157         i = 0;
158         do {
159                 if (copyedges) {
160                         BMEdge *e;
161                         BMVert *v1, *v2;
162                         
163                         if (l->e->v1 == verts[i]) {
164                                 v1 = verts[i];
165                                 v2 = verts[(i+1)%f->len];
166                         } else {
167                                 v2 = verts[i];
168                                 v1 = verts[(i+1)%f->len];
169                         }
170                         
171                         e = BM_Make_Edge(bm,  v1, v2, l->e, 0);
172                         BLI_array_append(edges, e);
173                 } else {
174                         BLI_array_append(edges, l->e);
175                 }
176                 
177                 i++;
178                 l = l->next;
179         } while (l != bm_firstfaceloop(f));
180         
181         f2 = BM_Make_Face(bm, verts, edges, f->len);
182         
183         BM_Copy_Attributes(bm, bm, f, f2);
184         
185         l = bm_firstfaceloop(f);
186         l2 = bm_firstfaceloop(f2);
187         do {
188                 BM_Copy_Attributes(bm, bm, l, l2);
189                 l = l->next;
190                 l2 = l2->next;
191         } while (l != bm_firstfaceloop(f));
192         
193         return f2;
194 }
195
196 BMFace *BM_Make_Face(BMesh *bm, BMVert **verts, BMEdge **edges, int len) {
197         BMFace *f;
198         BMLoop *l, *startl, *lastl;
199         int i;
200         
201         if (len == 0) {
202                 /*just return NULL for now*/
203                 return NULL;
204         }
205         
206         f = BLI_mempool_calloc(bm->fpool);
207         bm->totface += 1;
208         f->head.type = BM_FACE;
209
210         startl = lastl = (BMLoop*) BM_Add_FaceBoundary(bm, (BMFace*)f, verts[0], edges[0]);
211         
212         startl->v = (BMVert*) verts[0];
213         startl->e = (BMEdge*) edges[0];
214         for (i=1; i<len; i++) {
215                 l = (BMLoop *)bmesh_create_loop(bm, verts[i], edges[i], (BMFace *)f, edges[i]->l);
216                 
217                 l->f = (BMFace*) f;
218                 bmesh_radial_append(edges[i], l);
219
220                 l->prev = lastl;
221                 lastl->next = l;
222                 lastl = l;
223         }
224         
225         /*allocate flags*/
226         f->head.flags = BLI_mempool_calloc(bm->toolflagpool);
227
228         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
229         
230         startl->prev = lastl;
231         lastl->next = startl;
232         
233         f->len = len;
234         f->totbounds = 0;
235         
236         CHECK_ELEMENT(bm, f);
237
238         return (BMFace*) f;
239 }
240
241 int bmesh_check_element(BMesh *UNUSED(bm), void *element, int type) {
242         BMHeader *head = element;
243         int err = 0;
244
245         if (!element)
246                 return 1;
247
248         if (head->type != type)
249                 return 2;
250         
251         switch (type) {
252         case BM_VERT: {
253                 BMVert *v = element;
254                 if (v->e && v->e->head.type != BM_EDGE) {
255                         err |= 4;
256                 }
257                 break;
258         }
259         case BM_EDGE: {
260                 BMEdge *e = element;
261                 if (e->l && e->l->head.type != BM_LOOP)
262                         err |= 8;
263                 if (e->l && e->l->f->head.type != BM_FACE)
264                         err |= 16;
265                 if (e->dlink1.prev == NULL || e->dlink2.prev == NULL || e->dlink1.next == NULL || e->dlink2.next == NULL)
266                         err |= 32;
267                 if (e->l && (e->l->radial_next == NULL || e->l->radial_prev == NULL))
268                         err |= 64;
269                 if (e->l && e->l->f->len <= 0)
270                         err |= 128;
271                 break;
272         }
273         case BM_LOOP: {
274                 BMLoop *l = element, *l2;
275                 int i;
276
277                 if (l->f->head.type != BM_FACE)
278                         err |= 256;
279                 if (l->e->head.type != BM_EDGE)
280                         err |= 512;
281                 if (l->v->head.type !=  BM_VERT)
282                         err |= 1024;
283                 if (!BM_Vert_In_Edge(l->e, l->v)) {
284                         printf("eek!! fatal bmesh error! evil!\n");
285                         err |= 2048;
286                 }
287
288                 if (l->radial_next == NULL || l->radial_prev == NULL)
289                         err |= (1<<12);
290                 if (l->f->len <= 0)
291                         err |= (1<<13);
292
293                 /*validate boundary loop--invalid for hole loops, of course,
294                   but we won't be allowing those for a while yet*/
295                 l2 = l;
296                 i = 0;
297                 do {
298                         if (i >= 9999999)
299                                 break;
300
301                         i++;
302                         l2 = l2->next;
303                 } while (l2 != l);
304
305                 if (i != l->f->len || l2 != l)
306                         err |= (1<<14);
307
308                 if (!bmesh_radial_validate(bmesh_radial_length(l), l))
309                         err |= (1<<15);
310
311                 break;
312         }
313         case BM_FACE: {
314                 BMFace *f = element;
315                 BMLoop *l;
316                 int len=0;
317
318                 if (!f->loops.first)
319                         err |= (1<<16);
320                 l = bm_firstfaceloop(f);
321                 do {
322                         if (l->f != f) {
323                                 printf("yeek!! loop inside one face points to another!\n");
324                                 err |= (1<<17);
325                         }
326
327                         if (!l->e)
328                                 err |= (1<<18);
329                         if (!l->v)
330                                 err |= (1<<19);
331                         if (!BM_Vert_In_Edge(l->e, l->v) || !BM_Vert_In_Edge(l->e, l->next->v)) {
332                                 err |= (1<<20);
333                         }
334
335                         if (!bmesh_radial_validate(bmesh_radial_length(l), l))
336                                 err |= (1<<21);
337
338                         if (!bmesh_disk_count(l->v) || !bmesh_disk_count(l->next->v))
339                                 err |= (1<<22);
340
341                         len++;
342                         l = l->next;
343                 } while (l != bm_firstfaceloop(f));
344
345                 if (len != f->len)
346                         err |= (1<<23);
347         }
348         }
349
350         if (err) {
351                 bmesh_error();
352         }
353
354         return err;
355 }
356
357 static void bmesh_kill_loop(BMesh *bm, BMLoop *l) {
358         bm->totloop--;
359         if (l->head.data)
360                 CustomData_bmesh_free_block(&bm->ldata, &l->head.data);
361
362         if (l->head.flags)
363                 BLI_mempool_free(bm->toolflagpool, l->head.flags);
364         BLI_mempool_free(bm->lpool, l);
365 }
366
367 void BM_Kill_Face_Edges(BMesh *bm, BMFace *f) {
368         BMEdge **edges = NULL;
369         BLI_array_staticdeclare(edges, 256);
370         BMLoop *l;
371         int i;
372         
373         l = bm_firstfaceloop(f);
374         do {
375                 BLI_array_append(edges, l->e);
376                 l = l->next;
377         } while (l != bm_firstfaceloop(f));
378         
379         for (i=0; i<BLI_array_count(edges); i++) {
380                 BM_Kill_Edge(bm, edges[i]);
381         }
382         
383         BLI_array_free(edges);
384 }
385
386 void BM_Kill_Face_Verts(BMesh *bm, BMFace *f) {
387         BMVert**verts = NULL;
388         BLI_array_staticdeclare(verts, 256);
389         BMLoop *l;
390         int i;
391         
392         l = bm_firstfaceloop(f);
393         do {
394                 BLI_array_append(verts, l->v);
395                 l = l->next;
396         } while (l != bm_firstfaceloop(f));
397         
398         for (i=0; i<BLI_array_count(verts); i++) {
399                 BM_Kill_Vert(bm, verts[i]);
400         }
401         
402         BLI_array_free(verts);
403 }
404
405 void BM_Kill_Face(BMesh *bm, BMFace *f) {
406         BMLoopList *ls, *lsnext;
407
408         CHECK_ELEMENT(bm, f);
409
410         for (ls=f->loops.first; ls; ls=lsnext) {
411                 BMLoop *l, *lnext;
412
413                 lsnext = ls->next;
414                 l = ls->first;
415                 do {
416                         lnext = l->next;
417
418                         bmesh_radial_remove_loop((BMLoop*)l, (BMEdge *)l->e);
419                         bmesh_kill_loop(bm, (BMLoop*)l);
420
421                         l = lnext;
422                 } while (l != ls->first);
423                 
424                 BLI_mempool_free(bm->looplistpool, ls);
425         }
426         
427         if (bm->act_face == f)
428                 bm->act_face = NULL;
429         
430         bm->totface--;
431         BM_remove_selection(bm, f);
432         if (f->head.data)
433                 CustomData_bmesh_free_block(&bm->pdata, &f->head.data);
434
435         BLI_mempool_free(bm->toolflagpool, f->head.flags);
436
437         BLI_mempool_free(bm->fpool, f);
438 }
439
440 void BM_Kill_Edge(BMesh *bm, BMEdge *e) {
441
442         bmesh_disk_remove_edge(e, e->v1);
443         bmesh_disk_remove_edge(e, e->v2);
444                 
445         if (e->l) {
446                 BMLoop *l = e->l, *lnext, *startl=e->l;
447                         
448                 do {
449                         lnext = l->radial_next;
450                         if (lnext->f == l->f) {
451                                 BM_Kill_Face(bm, l->f);
452                                 break;                                  
453                         }
454                         
455                         BM_Kill_Face(bm, l->f);
456                 
457                         if (l == lnext)
458                                 break;
459                         l = lnext;
460                 } while (l != startl);
461         }
462         
463         bm->totedge--;
464         BM_remove_selection(bm, e);
465         if (e->head.data)
466                 CustomData_bmesh_free_block(&bm->edata, &e->head.data);
467
468         BLI_mempool_free(bm->toolflagpool, e->head.flags);
469         BLI_mempool_free(bm->epool, e);
470 }
471
472 void BM_Kill_Vert(BMesh *bm, BMVert *v) {
473         if (v->e) {
474                 BMEdge *e, *nexte;
475                 
476                 e = v->e;
477                 while (v->e) {
478                         nexte=bmesh_disk_nextedge(e, v);
479                         BM_Kill_Edge(bm, (BMEdge*)e);
480                         e = nexte;
481                 }
482         }
483
484         bm->totvert--;
485         BM_remove_selection(bm, v);
486         if (v->head.data)
487                 CustomData_bmesh_free_block(&bm->vdata, &v->head.data);
488
489         BLI_mempool_free(bm->toolflagpool, v->head.flags);
490         BLI_mempool_free(bm->vpool, v);
491 }
492
493 /********** private disk and radial cycle functions ************/
494
495 /**
496  *                      bmesh_loop_reverse
497  *
498  *      FLIP FACE EULER
499  *
500  *      Changes the winding order of a face from CW to CCW or vice versa.
501  *      This euler is a bit peculiar in compairson to others as it is its
502  *      own inverse.
503  *
504  *      TODO: reinsert validation code.
505  *
506  *  Returns -
507  *      1 for success, 0 for failure.
508  */
509
510 static int bmesh_loop_length(BMLoop *l)
511 {
512         BMLoop *ol = l;
513         int i = 0;
514
515         do {
516                 l = l->next;
517                 i++;
518         } while (l != ol);
519
520         return i;
521 }
522
523 static int bmesh_loop_reverse_loop(BMesh *bm, BMFace *f, BMLoopList *lst){
524         BMLoop *l = lst->first, *curloop, *oldprev, *oldnext;
525         BMEdge **edar = NULL;
526         MDisps *md;
527         BLI_array_staticdeclare(edar, 64);
528         int i, j, edok, len = 0, do_disps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
529
530         len = bmesh_loop_length(l);
531
532         for(i=0, curloop = l; i< len; i++, curloop= ((BMLoop*)(curloop->next)) ){
533                 bmesh_radial_remove_loop(curloop, curloop->e);
534                 /*in case of border edges we HAVE to zero out curloop->radial Next/Prev*/
535                 curloop->radial_next = curloop->radial_prev = NULL;
536                 BLI_array_append(edar, curloop->e);
537         }
538
539         /*actually reverse the loop.*/
540         for(i=0, curloop = l; i < len; i++){
541                 oldnext = ((BMLoop*)(curloop->next));
542                 oldprev = ((BMLoop*)(curloop->prev));
543                 curloop->next = (BMLoop*)oldprev;
544                 curloop->prev = (BMLoop*)oldnext;
545                 curloop = oldnext;
546                 
547                 if (do_disps) {
548                         float (*co)[3];
549                         int x, y, sides;
550                         
551                         md = CustomData_bmesh_get(&bm->ldata, curloop->head.data, CD_MDISPS);
552                         if (!md->totdisp || !md->disps)
553                                 continue;
554                                         
555                         sides=sqrt(md->totdisp);
556                         co = md->disps;
557                         
558                         for (x=0; x<sides; x++) {
559                                 for (y=0; y<x; y++) {
560                                         swap_v3_v3(co[y*sides+x], co[sides*x + y]);
561                                 }
562                         }
563                 }
564         }
565
566         if(len == 2){ //two edged face
567                 //do some verification here!
568                 l->e = edar[1];
569                 ((BMLoop*)(l->next))->e = edar[0];
570         }
571         else{
572                 for(i=0, curloop = l; i < len; i++, curloop = ((BMLoop*)(curloop->next)) ){
573                         edok = 0;
574                         for(j=0; j < len; j++){
575                                 edok = bmesh_verts_in_edge(curloop->v, ((BMLoop*)(curloop->next))->v, edar[j]);
576                                 if(edok){
577                                         curloop->e = edar[j];
578                                         break;
579                                 }
580                         }
581                 }
582         }
583         /*rebuild radial*/
584         for(i=0, curloop = l; i < len; i++, curloop = curloop->next)
585                 bmesh_radial_append(curloop->e, curloop);
586
587         /*validate radial*/
588         for(i=0, curloop = l; i < len; i++, curloop = curloop->next) {
589                 CHECK_ELEMENT(bm, curloop);
590                 CHECK_ELEMENT(bm, curloop->e);
591                 CHECK_ELEMENT(bm, curloop->v);
592                 CHECK_ELEMENT(bm, curloop->f);
593         }
594
595         BLI_array_free(edar);
596
597         CHECK_ELEMENT(bm, f);
598
599         return 1;
600 }
601
602 int bmesh_loop_reverse(BMesh *bm, BMFace *f)
603 {
604         return bmesh_loop_reverse_loop(bm, f, f->loops.first);
605 }
606
607 static void bmesh_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
608 {
609         BMHeader **eles = veles;
610         int i;
611
612         for (i=0; i<tot; i++) {
613                 bmesh_api_setflag(eles[i], flag);
614         }
615 }
616
617 static void bmesh_clear_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
618 {
619         BMHeader **eles = veles;
620         int i;
621
622         for (i=0; i<tot; i++) {
623                 bmesh_api_clearflag(eles[i], flag);
624         }
625 }
626
627 #define FACE_MARK       (1<<10)
628
629 static int count_flagged_radial(BMesh *bm, BMLoop *l, int flag)
630 {
631         BMLoop *l2 = l;
632         int i = 0, c=0;
633
634         do {
635                 if (!l2) {
636                         bmesh_error();
637                         goto error;
638                 }
639                 
640                 i += bmesh_api_getflag(l2->f, flag) ? 1 : 0;
641                 l2 = bmesh_radial_nextloop(l2);
642                 if (c >= 800000) {
643                         bmesh_error();
644                         goto error;
645                 }
646                 c++;
647         } while (l2 != l);
648
649         return i;
650
651 error:
652         BMO_RaiseError(bm, bm->currentop, BMERR_MESH_ERROR, NULL);
653         return 0;
654 }
655
656 static int count_flagged_disk(BMVert *v, int flag)
657 {
658         BMEdge *e = v->e;
659         int i=0;
660
661         if (!e)
662                 return 0;
663
664         do {
665                 i += bmesh_api_getflag(e, flag) ? 1 : 0;
666                 e = bmesh_disk_nextedge(e, v);
667         } while (e != v->e);
668
669         return i;
670 }
671
672 static int disk_is_flagged(BMVert *v, int flag)
673 {
674         BMEdge *e = v->e;
675
676         if (!e)
677                 return 0;
678
679         do {
680                 BMLoop *l = e->l;
681
682                 if (!l) {
683                         return 0;
684                 }
685                 
686                 if (bmesh_radial_length(l) == 1)
687                         return 0;
688                 
689                 do {
690                         if (!bmesh_api_getflag(l->f, flag))
691                                 return 0;
692
693                         l = l->radial_next;
694                 } while (l != e->l);
695
696                 e = bmesh_disk_nextedge(e, v);
697         } while (e != v->e);
698
699         return 1;
700 }
701
702 /* Midlevel Topology Manipulation Functions */
703
704 /*joins a collected group of faces into one.  only restriction on
705   the input data is that the faces must be connected to each other.*/
706 BMFace *BM_Join_Faces(BMesh *bm, BMFace **faces, int totface)
707 {
708         BMFace *f, *newf;
709         BMLoopList *lst;
710         BMLoop *l;
711         BMEdge **edges = NULL;
712         BMEdge **deledges = NULL;
713         BMVert **delverts = NULL;
714         BLI_array_staticdeclare(edges, 64);
715         BLI_array_staticdeclare(deledges, 64);
716         BLI_array_staticdeclare(delverts, 64);
717         BMVert *v1=NULL, *v2=NULL;
718         ListBase holes = {NULL, NULL};
719         const char *err = NULL;
720         int i, tote=0;
721
722         if (!totface) {
723                 bmesh_error();
724                 return NULL;
725         }
726
727         if (totface == 1)
728                 return faces[0];
729
730         bmesh_systag_elements(bm, faces, totface, _FLAG_JF);
731
732         for (i=0; i<totface; i++) {
733                 f = faces[i];
734                 l = bm_firstfaceloop(f);
735                 do {
736                         int rlen = count_flagged_radial(bm, l, _FLAG_JF);
737
738                         if (rlen > 2) {
739                                 err = "Input faces do not form a contiguous manifold region";
740                                 goto error;
741                         } else if (rlen == 1) {
742                                 BLI_array_append(edges, l->e);
743
744                                 if (!v1) {
745                                         v1 = l->v;
746                                         v2 = BM_OtherEdgeVert(l->e, l->v);
747                                 }
748                                 tote++;
749                         } else if (rlen == 2) {
750                                 int d1, d2;
751
752                                 d1 = disk_is_flagged(l->e->v1, _FLAG_JF);
753                                 d2 = disk_is_flagged(l->e->v2, _FLAG_JF);
754
755                                 if (!d1 && !d2 && !bmesh_api_getflag(l->e, _FLAG_JF)) {
756                                         BLI_array_append(deledges, l->e);
757                                         bmesh_api_setflag(l->e, _FLAG_JF);
758                                 } else {
759                                         if (d1 && !bmesh_api_getflag(l->e->v1, _FLAG_JF)) {
760                                                 BLI_array_append(delverts, l->e->v1);
761                                                 bmesh_api_setflag(l->e->v1, _FLAG_JF);
762                                         }
763
764                                         if (d2 && !bmesh_api_getflag(l->e->v2, _FLAG_JF)) {
765                                                 BLI_array_append(delverts, l->e->v2);
766                                                 bmesh_api_setflag(l->e->v2, _FLAG_JF);
767                                         }
768                                 }
769                         }
770
771                         l = l->next;
772                 } while (l != bm_firstfaceloop(f));
773
774                 for (lst=f->loops.first; lst; lst=lst->next) {
775                         if (lst == f->loops.first) continue;
776                         
777                         BLI_remlink(&f->loops, lst);
778                         BLI_addtail(&holes, lst);
779                 }
780         }
781
782         /*create region face*/
783         newf = BM_Make_Ngon(bm, v1, v2, edges, tote, 0);
784         if (!newf || BMO_HasError(bm)) {
785                 if (!BMO_HasError(bm)) 
786                         err = "Invalid boundary region to join faces";
787                 goto error;
788         }
789
790         /*copy over loop data*/
791         l = bm_firstfaceloop(newf);
792         do {
793                 BMLoop *l2 = l->radial_next;
794
795                 do {
796                         if (bmesh_api_getflag(l2->f, _FLAG_JF))
797                                 break;
798                         l2 = l2->radial_next;
799                 } while (l2 != l);
800
801                 if (l2 != l) {
802                         /*I think this is correct?*/
803                         if (l2->v != l->v) {
804                                 l2 = l2->next;
805                         }
806
807                         BM_Copy_Attributes(bm, bm, l2, l);
808                 }
809
810                 l = l->next;
811         } while (l != bm_firstfaceloop(newf));
812         
813         BM_Copy_Attributes(bm, bm, faces[0], newf);
814
815         /*add holes*/
816         BLI_movelisttolist(&newf->loops, &holes);
817
818         /*update loop face pointers*/
819         for (lst=newf->loops.first; lst; lst=lst->next) {
820                 l = lst->first;
821                 do {
822                         l->f = newf;
823                         l = l->next;
824                 } while (l != lst->first);
825         }
826
827         bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
828         bmesh_api_clearflag(newf, _FLAG_JF);
829
830         /* handle multires data*/
831         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
832                 l = bm_firstfaceloop(newf);
833                 do {
834                         for (i=0; i<totface; i++) {
835                                 BM_loop_interp_multires(bm, l, faces[i]);
836                         }
837                         
838                         l = l->next;
839                 } while (l != bm_firstfaceloop(newf));
840         }       
841
842         /*delete old geometry*/
843         for (i=0; i<BLI_array_count(deledges); i++) {
844                 BM_Kill_Edge(bm, deledges[i]);
845         }
846
847         for (i=0; i<BLI_array_count(delverts); i++) {
848                 BM_Kill_Vert(bm, delverts[i]);
849         }
850         
851         BLI_array_free(edges);
852         BLI_array_free(deledges);
853         BLI_array_free(delverts);
854
855         CHECK_ELEMENT(bm, newf);
856         return newf;
857 error:
858         bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
859         BLI_array_free(edges);
860         BLI_array_free(deledges);
861         BLI_array_free(delverts);
862
863         if (err) {
864                 BMO_RaiseError(bm, bm->currentop, BMERR_DISSOLVEFACES_FAILED, err);
865         }
866         return NULL;
867 }
868
869 static BMFace *bmesh_addpolylist(BMesh *bm, BMFace *UNUSED(example)) {
870         BMFace *f;
871         BMLoopList *lst;
872
873         f = BLI_mempool_calloc(bm->fpool);
874         lst = BLI_mempool_calloc(bm->looplistpool);
875
876         f->head.type = BM_FACE;
877         BLI_addtail(&f->loops, lst);
878         bm->totface++;
879
880         /*allocate flags*/
881         f->head.flags = BLI_mempool_calloc(bm->toolflagpool);
882
883         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
884
885         f->len = 0;
886         f->totbounds = 1;
887
888         return (BMFace*) f;
889 }
890
891 /**
892  *                      bmesh_SFME
893  *
894  *      SPLIT FACE MAKE EDGE:
895  *
896  *      Takes as input two vertices in a single face. An edge is created which divides the original face
897  *      into two distinct regions. One of the regions is assigned to the original face and it is closed off.
898  *      The second region has a new face assigned to it.
899  *
900  *      Examples:
901  *
902  *     Before:               After:
903  *       ----------           ----------
904  *       |                |           |        |
905  *       |        |           |   f1   |
906  *      v1   f1   v2          v1======v2
907  *       |        |           |   f2   |
908  *       |        |           |        |
909  *       ----------           ----------
910  *
911  *      Note that the input vertices can be part of the same edge. This will
912  *  result in a two edged face. This is desirable for advanced construction
913  *  tools and particularly essential for edge bevel. Because of this it is
914  *  up to the caller to decide what to do with the extra edge.
915  *
916  *  If holes is NULL, then both faces will lose
917  *  all holes from the original face.  Also, you cannot split between
918  *  a hole vert and a boundary vert; that case is handled by higher-
919  *  level wrapping functions (when holes are fully implemented, anyway).
920  *
921  *  Note that holes represents which holes goes to the new face, and of
922  *  course this requires removing them from the exitsing face first, since
923  *  you cannot have linked list links inside multiple lists.
924  *
925  *      Returns -
926  *  A BMFace pointer
927  */
928 BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2,
929                                    BMLoop **rl, ListBase *holes)
930 {
931
932         BMFace *f2;
933         BMLoop *v1loop = NULL, *v2loop = NULL, *curloop, *f1loop=NULL, *f2loop=NULL;
934         BMEdge *e;
935         BMLoopList *lst, *lst2;
936         int i, len, f1len, f2len;
937
938         /*verify that v1 and v2 are in face.*/
939         len = f->len;
940         for(i = 0, curloop = bm_firstfaceloop(f); i < len; i++, curloop = curloop->next) {
941                 if(curloop->v == v1) v1loop = curloop;
942                 else if(curloop->v == v2) v2loop = curloop;
943         }
944
945         if(!v1loop || !v2loop) return NULL;
946
947         /*allocate new edge between v1 and v2*/
948         e = BM_Make_Edge(bm, v1, v2, NULL, 0);
949
950         f2 = bmesh_addpolylist(bm,f);
951         f1loop = bmesh_create_loop(bm,v2,e,f,v2loop);
952         f2loop = bmesh_create_loop(bm,v1,e,f2,v1loop);
953
954         f1loop->prev = v2loop->prev;
955         f2loop->prev = v1loop->prev;
956         v2loop->prev->next = f1loop;
957         v1loop->prev->next = f2loop;
958
959         f1loop->next = v1loop;
960         f2loop->next = v2loop;
961         v1loop->prev = f1loop;
962         v2loop->prev = f2loop;
963
964         lst = f->loops.first;
965         lst2 = f2->loops.first;
966
967         lst2->first = lst2->last = f2loop;
968         lst->first = lst->last = f1loop;
969
970         /*validate both loops*/
971         /*I dont know how many loops are supposed to be in each face at this point! FIXME!*/
972
973         /*go through all of f2's loops and make sure they point to it properly.*/
974         curloop = lst2->first;
975         f2len = 0;
976         do {
977                 curloop->f = f2;
978
979                 curloop = curloop->next;
980                 f2len++;
981         } while (curloop != lst2->first);
982
983         /*link up the new loops into the new edges radial*/
984         bmesh_radial_append(e, f1loop);
985         bmesh_radial_append(e, f2loop);
986
987         f2->len = f2len;
988
989         f1len = 0;
990         curloop = lst->first;
991         do {
992                 f1len++;
993                 curloop = curloop->next;
994         } while (curloop != lst->first);
995
996         f->len = f1len;
997
998         if(rl) *rl = f2loop;
999
1000         if (holes) {
1001                 BLI_movelisttolist(&f2->loops, holes);
1002         } else {
1003                 /*this code is not significant until holes actually work ;) */
1004                 //printf("warning: call to split face euler without holes argument; holes will be tossed.\n");
1005                 for (lst=f->loops.last; lst != f->loops.first; lst=lst2) {
1006                         lst2 = lst->prev;
1007                         BLI_mempool_free(bm->looplistpool, lst);
1008                 }
1009         }
1010
1011         CHECK_ELEMENT(bm, e);
1012         CHECK_ELEMENT(bm, f);
1013         CHECK_ELEMENT(bm, f2);
1014         
1015         return f2;
1016 }
1017
1018 /**
1019  *                      bmesh_SEMV
1020  *
1021  *      SPLIT EDGE MAKE VERT:
1022  *      Takes a given edge and splits it into two, creating a new vert.
1023  *
1024  *
1025  *              Before: OV---------TV
1026  *              After:  OV----NV---TV
1027  *
1028  *  Returns -
1029  *      BMVert pointer.
1030  *
1031 */
1032
1033 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re){
1034         BMLoop *nextl;
1035         BMEdge *ne;
1036         BMVert *nv, *ov;
1037         int i, edok, valance1=0, valance2=0;
1038
1039         if(bmesh_vert_in_edge(e,tv) == 0) return NULL;
1040         ov = bmesh_edge_getothervert(e,tv);
1041
1042         /*count valance of v1*/
1043         valance1 = bmesh_disk_count(ov);
1044
1045         /*count valance of v2*/
1046         valance2 = bmesh_disk_count(tv);
1047
1048         nv = BM_Make_Vert(bm, tv->co, tv);
1049         ne = BM_Make_Edge(bm, nv, tv, e, 0);
1050
1051         bmesh_disk_remove_edge(ne, tv);
1052         bmesh_disk_remove_edge(ne, nv);
1053
1054         /*remove e from v2's disk cycle*/
1055         bmesh_disk_remove_edge(e, tv);
1056
1057         /*swap out tv for nv in e*/
1058         bmesh_edge_swapverts(e, tv, nv);
1059
1060         /*add e to nv's disk cycle*/
1061         bmesh_disk_append_edge(e, nv);
1062
1063         /*add ne to nv's disk cycle*/
1064         bmesh_disk_append_edge(ne, nv);
1065
1066         /*add ne to tv's disk cycle*/
1067         bmesh_disk_append_edge(ne, tv);
1068
1069         /*verify disk cycles*/
1070         edok = bmesh_disk_validate(valance1, ov->e, ov);
1071         if(!edok) bmesh_error();
1072         edok = bmesh_disk_validate(valance2, tv->e, tv);
1073         if(!edok) bmesh_error();
1074         edok = bmesh_disk_validate(2, nv->e, nv);
1075         if(!edok) bmesh_error();
1076
1077         /*Split the radial cycle if present*/
1078         nextl = e->l;
1079         e->l = NULL;
1080         if(nextl) {
1081                 BMLoop *nl, *l;
1082                 int radlen = bmesh_radial_length(nextl);
1083                 int first1=0, first2=0;
1084
1085                 /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
1086                 while(nextl) {
1087                         l=nextl;
1088                         l->f->len++;
1089                         nextl = nextl!=nextl->radial_next ? nextl->radial_next : NULL;
1090                         bmesh_radial_remove_loop(l, NULL);
1091
1092                         nl = bmesh_create_loop(bm,NULL,NULL,l->f,l);
1093                         nl->prev = l;
1094                         nl->next = (l->next);
1095                         nl->prev->next = nl;
1096                         nl->next->prev = nl;
1097                         nl->v = nv;
1098
1099                         /*assign the correct edge to the correct loop*/
1100                         if(bmesh_verts_in_edge(nl->v, nl->next->v, e)) {
1101                                 nl->e = e;
1102                                 l->e = ne;
1103
1104                                 /*append l into ne's rad cycle*/
1105                                 if(!first1) {
1106                                         first1 = 1;
1107                                         l->radial_next = l->radial_prev = NULL;
1108                                 }
1109
1110                                 if(!first2) {
1111                                         first2 = 1;
1112                                         l->radial_next = l->radial_prev = NULL;
1113                                 }
1114                                 
1115                                 bmesh_radial_append(nl->e, nl);
1116                                 bmesh_radial_append(l->e, l);
1117                         }
1118                         else if(bmesh_verts_in_edge(nl->v,((BMLoop*)(nl->next))->v,ne)){
1119                                 nl->e = ne;
1120                                 l->e = e;
1121
1122                                 /*append l into ne's rad cycle*/
1123                                 if(!first1) {
1124                                         first1 = 1;
1125                                         l->radial_next = l->radial_prev = NULL;
1126                                 }
1127
1128                                 if(!first2) {
1129                                         first2 = 1;
1130                                         l->radial_next = l->radial_prev = NULL;
1131                                 }
1132
1133                                 bmesh_radial_append(nl->e, nl);
1134                                 bmesh_radial_append(l->e, l);
1135                         }
1136
1137                 }
1138
1139                 /*verify length of radial cycle*/
1140                 edok = bmesh_radial_validate(radlen, e->l);
1141                 if(!edok) bmesh_error();
1142                 edok = bmesh_radial_validate(radlen, ne->l);
1143                 if(!edok) bmesh_error();
1144
1145                 /*verify loop->v and loop->next->v pointers for e*/
1146                 for(i=0,l=e->l; i < radlen; i++, l = l->radial_next){
1147                         if(!(l->e == e)) bmesh_error();
1148                         //if(!(l->radial_next == l)) bmesh_error();
1149                         if( ((BMLoop*)(l->prev))->e != ne && ((BMLoop*)(l->next))->e != ne) bmesh_error();
1150                         edok = bmesh_verts_in_edge(l->v, ((BMLoop*)(l->next))->v, e);
1151                         if(!edok) bmesh_error();
1152                         if(l->v == ((BMLoop*)(l->next))->v) bmesh_error();
1153                         if(l->e == ((BMLoop*)(l->next))->e) bmesh_error();
1154
1155                         /*verify loop cycle for kloop->f*/
1156                         CHECK_ELEMENT(bm, l);
1157                         CHECK_ELEMENT(bm, l->v);
1158                         CHECK_ELEMENT(bm, l->e);
1159                         CHECK_ELEMENT(bm, l->f);
1160                 }
1161                 /*verify loop->v and loop->next->v pointers for ne*/
1162                 for(i=0,l=ne->l; i < radlen; i++, l = l->radial_next){
1163                         if(!(l->e == ne)) bmesh_error();
1164                         //if(!(l->radial_next == l)) bmesh_error();
1165                         if( ((BMLoop*)(l->prev))->e != e && ((BMLoop*)(l->next))->e != e) bmesh_error();
1166                         edok = bmesh_verts_in_edge(l->v, ((BMLoop*)(l->next))->v, ne);
1167                         if(!edok) bmesh_error();
1168                         if(l->v == ((BMLoop*)(l->next))->v) bmesh_error();
1169                         if(l->e == ((BMLoop*)(l->next))->e) bmesh_error();
1170
1171                         CHECK_ELEMENT(bm, l);
1172                         CHECK_ELEMENT(bm, l->v);
1173                         CHECK_ELEMENT(bm, l->e);
1174                         CHECK_ELEMENT(bm, l->f);
1175                 }
1176         }
1177
1178         CHECK_ELEMENT(bm, ne);
1179         CHECK_ELEMENT(bm, nv);
1180         CHECK_ELEMENT(bm, e);
1181         CHECK_ELEMENT(bm, tv);
1182
1183         if(re) *re = ne;
1184         return nv;
1185 }