Code Cleanup: update to mempool, use flag rather then bool args.
[blender.git] / source / blender / bmesh / operators / bmo_create.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_heap.h"
26 #include "BLI_listbase.h"
27 #include "BLI_math.h"
28 #include "BLI_array.h"
29 #include "BLI_smallhash.h"
30 #include "BLI_rand.h"
31
32 #include "bmesh.h"
33
34
35 #define EDGE_MARK       1
36 #define EDGE_VIS        2
37
38 #define FACE_NEW        1
39
40 #define ELE_NEW         1
41 #define ELE_OUT         2
42 #define ELE_ORIG        4
43
44 #define FACE_IGNORE     16
45
46 typedef struct EPathNode {
47         struct EPathNode *next, *prev;
48         BMVert *v;
49         BMEdge *e;
50         BMEdge *cure;
51 } EPathNode;
52
53 typedef struct EPath {
54         ListBase nodes;
55         float weight;
56         int group;
57 } EPath;
58
59 typedef struct PathBase {
60         BLI_mempool *nodepool, *pathpool;
61 } PathBase;
62
63 typedef struct EdgeData {
64         int tag;
65         int ftag;
66         BMDiskLink v1_disk_link, v2_disk_link;
67 } EdgeData;
68
69 typedef struct VertData {
70         BMEdge *e;
71         float no[3], offco[3], sco[3]; /* offco is vertex coordinate slightly offset randoml */
72         int tag;
73 } VertData;
74
75 static int count_edge_faces(BMesh *bm, BMEdge *e);
76
77 /****  rotation system code * */
78
79 #define RS_GET_EDGE_LINK(e, v, e_data)  (                                     \
80         (v) == ((BMEdge *)(e))->v1 ?                                              \
81                         &(((EdgeData *)(e_data))->v1_disk_link) :                         \
82                         &(((EdgeData *)(e_data))->v2_disk_link)                           \
83         )
84
85
86 static int rotsys_append_edge(BMEdge *e, BMVert *v,
87                               EdgeData *edata, VertData *vdata)
88 {
89         EdgeData *ed = &edata[BM_elem_index_get(e)];
90         VertData *vd = &vdata[BM_elem_index_get(v)];
91         
92         if (!vd->e) {
93                 Link *e1 = (Link *)RS_GET_EDGE_LINK(e, v, ed);
94
95                 vd->e = e;
96                 e1->next = e1->prev = (Link *)e;
97         }
98         else {
99                 BMDiskLink *dl1, *dl2, *dl3;
100                 EdgeData *ved = &edata[BM_elem_index_get(vd->e)];
101
102                 dl1 = RS_GET_EDGE_LINK(e, v, ed);
103                 dl2 = RS_GET_EDGE_LINK(vd->e, v, ved);
104                 dl3 = dl2->prev ? RS_GET_EDGE_LINK(dl2->prev, v, &edata[BM_elem_index_get(dl2->prev)]) : NULL;
105
106                 dl1->next = vd->e;
107                 dl1->prev = dl2->prev;
108
109                 dl2->prev = e;
110                 if (dl3) {
111                         dl3->next = e;
112                 }
113         }
114
115         return TRUE;
116 }
117
118 static void UNUSED_FUNCTION(rotsys_remove_edge)(BMEdge *e, BMVert *v,
119                                                 EdgeData *edata, VertData *vdata)
120 {
121         EdgeData *ed = edata + BM_elem_index_get(e);
122         VertData *vd = vdata + BM_elem_index_get(v);
123         BMDiskLink *e1, *e2;
124
125         e1 = RS_GET_EDGE_LINK(e, v, ed);
126         if (e1->prev) {
127                 e2 = RS_GET_EDGE_LINK(e1->prev, v, ed);
128                 e2->next = e1->next;
129         }
130
131         if (e1->next) {
132                 e2 = RS_GET_EDGE_LINK(e1->next, v, ed);
133                 e2->prev = e1->prev;
134         }
135
136         if (vd->e == e)
137                 vd->e = (e != e1->next) ? e1->next : NULL;
138
139         e1->next = e1->prev = NULL;
140 }
141
142 static BMEdge *rotsys_nextedge(BMEdge *e, BMVert *v,
143                                EdgeData *edata, VertData *UNUSED(vdata))
144 {
145         if (v == e->v1)
146                 return edata[BM_elem_index_get(e)].v1_disk_link.next;
147         if (v == e->v2)
148                 return edata[BM_elem_index_get(e)].v2_disk_link.next;
149         return NULL;
150 }
151
152 static BMEdge *rotsys_prevedge(BMEdge *e, BMVert *v,
153                                EdgeData *edata, VertData *UNUSED(vdata))
154 {
155         if (v == e->v1)
156                 return edata[BM_elem_index_get(e)].v1_disk_link.prev;
157         if (v == e->v2)
158                 return edata[BM_elem_index_get(e)].v2_disk_link.prev;
159         return NULL;
160 }
161
162 static void rotsys_reverse(BMEdge *UNUSED(e), BMVert *v, EdgeData *edata, VertData *vdata)
163 {
164         BMEdge **edges = NULL;
165         BMEdge *e_first;
166         BMEdge *e;
167         BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE);
168         int i, totedge;
169         
170         e = e_first = vdata[BM_elem_index_get(v)].e;
171         do {
172                 BLI_array_append(edges, e);
173                 e = rotsys_nextedge(e, v, edata, vdata);
174         } while (e != e_first);
175         
176         totedge = BLI_array_count(edges);
177         for (i = 0; i < totedge / 2; i++) {
178                 SWAP(BMEdge *, edges[i], edges[totedge - 1 - i]);
179         }
180         
181         vdata[BM_elem_index_get(v)].e = NULL;
182         for (i = 0; i < totedge; i++) {
183                 rotsys_append_edge(edges[i], v, edata, vdata);
184         }
185         
186         BLI_array_free(edges);
187 }
188
189 static int UNUSED_FUNCTION(rotsys_count)(BMVert *v, EdgeData *edata, VertData *vdata)
190 {
191         BMEdge *e = vdata[BM_elem_index_get(v)].e;
192         int i = 0;
193
194         if (!e)
195                 return 0;
196
197         do {
198                 if (!e)
199                         return 0;
200                 e =  rotsys_nextedge(e, v, edata, vdata);
201
202                 if (i >= (1 << 20)) {
203                         printf("bmesh error: infinite loop in disk cycle!\n");
204                         return 0;
205                 }
206
207                 i += 1;
208         } while (e != vdata[BM_elem_index_get(v)].e);
209
210         return i;
211 }
212
213 static int UNUSED_FUNCTION(rotsys_fill_faces)(BMesh *bm, EdgeData *edata, VertData *vdata)
214 {
215         BMIter iter;
216         BMEdge *e, **edges = NULL;
217         BLI_array_declare(edges);
218         BMVert *v, **verts = NULL;
219         BMFace *f;
220         BLI_array_declare(verts);
221         SmallHash visithash, *hash = &visithash;
222         int i;
223         
224         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
225                 BMEdge *e2, *starte;
226                 BMVert *startv;
227                 int rad, ok;
228                 
229                 rad = count_edge_faces(bm, e);
230                 
231                 if (rad < 2)
232                         starte = e;
233                 else
234                         continue;
235                 
236                 /* do two passes, going forward then backwar */
237                 for (i = 0; i < 2; i++) {
238                         BLI_smallhash_init(hash);
239                         
240                         BLI_array_empty(verts);
241                         BLI_array_empty(edges);
242
243                         startv = v = starte->v1;
244                         e2 = starte;
245                         ok = 1;
246                         if (!v || !e2)
247                                 continue;
248
249                         do {
250                                 if (BLI_smallhash_haskey(hash, (intptr_t)e2) ||
251                                     BLI_smallhash_haskey(hash, (intptr_t)v))
252                                 {
253                                         ok = 0;
254                                         break;
255                                 }
256                                 
257                                 BLI_array_append(verts, v);
258                                 BLI_array_append(edges, e2);
259                                 
260                                 BLI_smallhash_insert(hash, (intptr_t)e2, NULL);
261
262                                 v = BM_edge_other_vert(e2, v);
263                                 e2 = i ? rotsys_prevedge(e2, v, edata, vdata) : rotsys_nextedge(e2, v, edata, vdata);
264                         } while (e2 != starte && v != startv);
265                         
266                         BLI_smallhash_release(hash);
267                         
268                         if (!ok || BLI_array_count(edges) < 3)
269                                 continue;
270                         
271                         f = BM_face_create_ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), TRUE);
272                         if (!f)
273                                 continue;
274                 }
275         }
276         
277         return 0;
278 }
279
280 static void rotsys_make_consistent(BMesh *bm, EdgeData *edata, VertData *vdata)
281 {
282         BMIter iter;
283         BMEdge *e;
284         BMVert *v, **stack = NULL;
285         BLI_array_declare(stack);
286         int i;
287         
288         for (i = 0; i < bm->totvert; i++) {
289                 vdata[i].tag = 0;
290         }
291         
292         while (1) {
293                 VertData *vd;
294                 BMVert *startv = NULL;
295                 float dis;
296                 
297                 v = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL);
298                 for (i = 0; i < bm->totvert; i++, BM_iter_step(&iter)) {
299                         vd = vdata + BM_elem_index_get(v);
300                         
301                         if (vd->tag)
302                                 continue;
303                         
304                         if (!startv || dot_v3v3(vd->offco, vd->offco) > dis) {
305                                 dis = dot_v3v3(vd->offco, vd->offco);
306                                 startv = v;
307                         }
308                 }
309                 
310                 if (!startv)
311                         break;
312                 
313                 vd = vdata + BM_elem_index_get(startv);
314                 
315                 BLI_array_empty(stack);
316                 BLI_array_append(stack, startv);
317                 
318                 vd->tag = 1;
319                 
320                 while (BLI_array_count(stack)) {
321                         v = BLI_array_pop(stack);
322                         vd = vdata + BM_elem_index_get(v);
323                         
324                         if (!vd->e)
325                                 continue;
326                         
327                         e = vd->e;
328                         do {
329                                 BMVert *v2 = BM_edge_other_vert(e, v);
330                                 VertData *vd2 = vdata + BM_elem_index_get(v2);
331                                 
332                                 if (dot_v3v3(vd->no, vd2->no) < 0.0f + FLT_EPSILON * 2) {
333                                         rotsys_reverse(e, v2, edata, vdata);
334                                         mul_v3_fl(vd2->no, -1.0f);
335                                 }
336
337                                 if (!vd2->tag) {
338                                         BLI_array_append(stack, v2);
339                                         vd2->tag = 1;
340                                 }
341                                 
342                                 e = rotsys_nextedge(e, v, edata, vdata);
343                         } while (e != vd->e);
344                 }
345         }
346
347         BLI_array_free(stack);
348 }
349
350 static void init_rotsys(BMesh *bm, EdgeData *edata, VertData *vdata)
351 {
352         BMIter iter;
353         BMEdge *e;
354         BMEdge **edges = NULL;
355         BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE);
356         BMVert *v;
357         /* BMVert **verts = NULL; */
358         /* BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE); */ /* UNUSE */
359         int i;
360         
361 #define SIGN(n) ((n)<0.0f)
362         
363         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
364                 BMIter eiter;
365                 float no[3], cent[3];
366                 int j, k = 0, totedge = 0;
367                 
368                 if (BM_elem_index_get(v) == -1)
369                         continue;
370                 
371                 BLI_array_empty(edges);
372                 
373                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
374                         if (BMO_elem_flag_test(bm, e, EDGE_MARK)) {
375                                 BLI_array_append(edges, e);
376                                 totedge++;
377                         }
378                 }
379                 
380                 copy_v3_v3(cent, v->co);
381                 
382                 zero_v3(no);
383                 for (i = 0; i < totedge; i++) {
384                         BMEdge *e1, *e2;
385                         float cno[3], vec1[3], vec2[3];
386                         
387                         e1 = edges[i];
388                         e2 = edges[(i + 1) % totedge];
389
390                         sub_v3_v3v3(vec1, (BM_edge_other_vert(e1, v))->co, v->co);
391                         sub_v3_v3v3(vec2, (BM_edge_other_vert(e2, v))->co, v->co);
392                         
393                         cross_v3_v3v3(cno, vec1, vec2);
394                         normalize_v3(cno);
395                         
396                         if (i && dot_v3v3(cno, no) < 0.0f + FLT_EPSILON * 10)
397                                 mul_v3_fl(cno, -1.0f);
398                         
399                         add_v3_v3(no, cno);
400                         normalize_v3(no);
401                 }
402                 
403                 /* generate plane-flattened coordinate */
404                 for (i = 0; i < totedge; i++) {
405                         BMEdge *e1;
406                         BMVert *v2;
407                         float cvec[3], vec1[3];
408                         
409                         e1 = edges[i];
410                         v2 = BM_edge_other_vert(e1, v);
411                         
412                         sub_v3_v3v3(vec1, v2->co, v->co);
413                         
414                         cross_v3_v3v3(cvec, vec1, no);
415                         cross_v3_v3v3(vec1, cvec, no);
416                         normalize_v3(vec1);
417                         
418                         mul_v3_fl(vec1, len_v3v3(v2->co, v->co));
419                         add_v3_v3(vec1, v->co);
420                         
421                         copy_v3_v3(vdata[BM_elem_index_get(v2)].sco, vec1);
422                 }
423                 
424                 BLI_srandom(0);
425                 
426                 /* first, ensure no 0 or 180 angles between adjacent
427                  * (and that adjacent's adjacent) edges */
428                 for (i = 0, k = 0; i < totedge; i++) {
429                         BMEdge *e1, *e2, *e3 = NULL;
430                         BMVert *v1, *v2, *v3;
431                         VertData *vd1, *vd2, *vd3;
432                         float vec1[3], vec2[3], vec3[3], size;
433                         int s1, s2, s3;
434                         
435                         if (totedge < 3)
436                                 continue;
437                         
438                         e1 = edges[(i + totedge - 1) % totedge];
439                         e2 = edges[i];
440                         e3 = edges[(i + 1) % totedge];
441                         
442                         v1 = BM_edge_other_vert(e1, v);
443                         v2 = BM_edge_other_vert(e2, v);
444                         v3 = BM_edge_other_vert(e3, v);
445
446                         vd1 = vdata + BM_elem_index_get(v1);
447                         vd2 = vdata + BM_elem_index_get(v2);
448                         vd3 = vdata + BM_elem_index_get(v3);
449                         
450                         sub_v3_v3v3(vec1, vd1->sco, cent);
451                         sub_v3_v3v3(vec2, vd2->sco, cent);
452                         sub_v3_v3v3(vec3, vd3->sco, cent);
453                         
454                         size = (len_v3(vec1) + len_v3(vec3)) * 0.01f;
455                         normalize_v3(vec1); normalize_v3(vec2); normalize_v3(vec3);
456                         
457 #ifdef STRAIGHT
458 #undef STRAIGHT
459 #endif
460 #define STRAIGHT(vec11, vec22) (fabsf(dot_v3v3((vec11), (vec22))) > 1.0f - ((float)FLT_EPSILON * 1000.0f))
461                         
462                         s1 = STRAIGHT(vec1, vec2); s2 = STRAIGHT(vec2, vec3); s3 = STRAIGHT(vec1, vec3);
463                         
464                         if (s1 || s2 || s3) {
465                                 copy_v3_v3(cent, v->co);
466
467                                 for (j = 0; j < 3; j++) {
468                                         float fac = (BLI_frand() - 0.5f)*size;
469                                         cent[j] += fac;
470                                 }
471                                 
472                                 if (k < 2000) {
473                                         i = 0;
474                                         k++;
475                                         continue;
476                                 }
477                                 else {
478                                         k++;
479                                         continue;
480                                 }
481
482                         }
483                 }
484                 
485                 copy_v3_v3(vdata[BM_elem_index_get(v)].offco, cent);
486                 //copy_v3_v3(v->co, cent);
487                 
488                 /* now, sort edges so the triangle fan of all edges
489                  * has a consistent normal.  this is the same as
490                  * sorting by polar coordinates along a group normal */
491                 for (j = 0; j < totedge; j++) {
492                         for (i = 0; i < totedge; i++) {
493                                 BMEdge *e1, *e2, *e3 = NULL;
494                                 BMVert *v1, *v2, *v3;
495                                 VertData *vd1, *vd2, *vd3;
496                                 float vec1[3], vec2[3], vec3[3], n1[3], n2[3], n3[3];
497                                 int s1, s2, s3;
498                                 
499                                 e1 = edges[(i + totedge - 1) % totedge];
500                                 e2 = edges[i];
501                                 e3 = edges[(i + 1) % totedge];
502                                 
503                                 v1 = BM_edge_other_vert(e1, v);
504                                 v2 = BM_edge_other_vert(e2, v);
505                                 v3 = BM_edge_other_vert(e3, v);
506
507                                 vd1 = vdata + BM_elem_index_get(v1);
508                                 vd2 = vdata + BM_elem_index_get(v2);
509                                 vd3 = vdata + BM_elem_index_get(v3);
510
511                                 sub_v3_v3v3(vec1, vd1->sco, cent);
512                                 sub_v3_v3v3(vec2, vd2->sco, cent);
513                                 sub_v3_v3v3(vec3, vd3->sco, cent);
514                                 
515                                 cross_v3_v3v3(n1, vec1, vec2);
516                                 cross_v3_v3v3(n2, vec2, vec3);
517                                 cross_v3_v3v3(n3, vec1, vec3);
518
519                                 /* Other way to determine if two vectors approach are (nearly) parallel: the
520                                  * cross product of the two vectors will approach zero */
521                                 s1 = (dot_v3v3(n1, n1) < (0.0f + FLT_EPSILON * 10));
522                                 s2 = (dot_v3v3(n2, n2) < (0.0f + FLT_EPSILON * 10));
523                                 s3 = (totedge < 3) ? 0 : (dot_v3v3(n3, n3) < (0.0f + FLT_EPSILON * 10));
524
525                                 normalize_v3(n1); normalize_v3(n2); normalize_v3(n3);
526                                 
527                                 if (s1 || s2 || s3) {
528                                         fprintf(stderr, "%s: s1: %d, s2: %d, s3: %dx (bmesh internal error)\n", __func__, s1, s2, s3);
529                                 }
530                                 if (dot_v3v3(n1, n2) < 0.0f) {
531                                         if (dot_v3v3(n1, n3) >= 0.0f + FLT_EPSILON * 10) {
532                                                 SWAP(BMEdge *, edges[i], edges[(i + 1) % totedge]);
533                                         }
534                                         else {
535                                                 SWAP(BMEdge *, edges[(i + totedge - 1) % totedge], edges[(i + 1) % totedge]);
536                                                 SWAP(BMEdge *, edges[i], edges[(i + 1) % totedge]);
537                                         }
538                                 }
539                         }
540                 }
541                 
542 #undef STRAIGHT
543
544                 zero_v3(no);
545
546                 /* yay, edges are sorted */
547                 for (i = 0; i < totedge; i++) {
548                         BMEdge *e1 = edges[i], *e2 = edges[(i + 1) % totedge];
549                         float eno[3];
550                         
551                         normal_tri_v3(eno, BM_edge_other_vert(e1, v)->co, v->co, BM_edge_other_vert(e2, v)->co);
552                         add_v3_v3(no, eno);
553                         
554                         rotsys_append_edge(edges[i], v, edata, vdata);
555                 }
556                 
557                 normalize_v3(no);
558                 copy_v3_v3(vdata[BM_elem_index_get(v)].no, no);
559         }
560         
561         /* now, make sure rotation system is topologically consistent
562          * (e.g. vert normals consistently point either inside or outside) */
563         rotsys_make_consistent(bm, edata, vdata);
564
565         //rotsys_fill_faces(bm, edata, vdata);
566
567 #if 0
568         /* create visualizing geometr */
569         BMVert *lastv;
570         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
571                 BMVert *v2;
572                 BMFace *f;
573                 int totedge = BM_vert_edge_count(v);
574
575                 if (BM_elem_index_get(v) == -1)
576                         continue;
577                 
578                 //cv = BM_vert_create(bm, cent, v);
579                 //BM_elem_index_set(cv, -1);  /* set_dirty! */
580                 i = 0;
581                 e = vdata[BM_elem_index_get(v)].e;
582                 lastv = NULL;
583                 do {
584                         BMEdge *e2;
585                         BMVert *v2;
586                         float f = ((float)i / (float)totedge) * 0.35 + 0.05;
587                         float co[3];
588                         
589                         if (!e)
590                                 break;
591
592                         if (!BM_edge_other_vert(e, v))
593                                 continue;
594                         
595                         sub_v3_v3v3(co, (BM_edge_other_vert(e, v))->co, vdata[BM_elem_index_get(v)].offco);
596                         mul_v3_fl(co, f);
597                         add_v3_v3(co, vdata[BM_elem_index_get(v)].offco);
598                         
599                         v2 = BM_vert_create(bm, co, NULL);
600                         BM_elem_index_set(v2, -1); /* set_dirty! */
601                         //BM_edge_create(bm, cv, v2, NULL, FALSE);
602                         
603                         BM_elem_select_set(bm, v2, TRUE);
604                         if (lastv) {
605                                 e2 = BM_edge_create(bm, lastv, v2, NULL, FALSE);
606                                 BM_elem_select_set(bm, e2, TRUE);
607                         }
608                         
609                         lastv = v2;
610                         
611                         e = rotsys_nextedge(e, v, edata, vdata);
612                         i++;
613                 } while (e != vdata[BM_elem_index_get(v)].e);
614         }
615 #endif
616
617         BLI_array_free(edges);
618 }
619
620 static PathBase *edge_pathbase_new(void)
621 {
622         PathBase *pb = MEM_callocN(sizeof(PathBase), "PathBase");
623
624         pb->nodepool = BLI_mempool_create(sizeof(EPathNode), 1, 512, BLI_MEMPOOL_SYSMALLOC);
625         pb->pathpool = BLI_mempool_create(sizeof(EPath), 1, 512, BLI_MEMPOOL_SYSMALLOC);
626
627         return pb;
628 }
629
630 static void edge_pathbase_free(PathBase *pathbase)
631 {
632         BLI_mempool_destroy(pathbase->nodepool);
633         BLI_mempool_destroy(pathbase->pathpool);
634         MEM_freeN(pathbase);
635 }
636
637 static EPath *edge_copy_add_path(PathBase *pb, EPath *path, BMVert *appendv, BMEdge *e)
638 {
639         EPath *path2;
640         EPathNode *node, *node2;
641
642         path2 = BLI_mempool_alloc(pb->pathpool);
643         path2->nodes.first = path2->nodes.last = NULL;
644         path2->weight = 0.0f;
645         path2->group = path->group;
646         
647         for (node = path->nodes.first; node; node = node->next) {
648                 node2 = BLI_mempool_alloc(pb->nodepool);
649                 *node2 = *node;
650                 BLI_addtail(&path2->nodes, node2);
651         }
652
653         node2 = BLI_mempool_alloc(pb->nodepool);
654         node2->v = appendv;
655         node2->e = e;
656         node2->cure = NULL;
657
658         BLI_addtail(&path2->nodes, node2);
659
660         return path2;
661 }
662
663 static EPath *edge_path_new(PathBase *pb, BMVert *start, BMEdge *starte)
664 {
665         EPath *path;
666         EPathNode *node;
667
668         path = BLI_mempool_alloc(pb->pathpool);
669         node = BLI_mempool_alloc(pb->nodepool);
670         
671         path->nodes.first = path->nodes.last = NULL;
672         
673         node->v = start;
674         node->e = starte;
675         node->cure = NULL;
676
677         BLI_addtail(&path->nodes, node);
678         path->weight = 0.0f;
679
680         return path;
681 }
682
683 static float edge_weight_path(EPath *path, EdgeData *edata, VertData *UNUSED(vdata))
684 {
685         EPathNode *node, *first = path->nodes.first;
686         float w = 0.0;
687
688         for (node = path->nodes.first; node; node = node->next) {
689                 if (node->e && node != path->nodes.first) {
690                         w += edata[BM_elem_index_get(node->e)].ftag;
691                         if (node->prev) {
692                                 /* BMESH_TOD */
693                                 (void)first;
694                                 //w += len_v3v3(node->v->co, first->e->v1->co) * 0.0001f;
695                                 //w += len_v3v3(node->v->co, first->e->v2->co) * 0.0001f;
696                         }
697                 }
698
699                 w += 1.0f;
700         }
701
702         return w;
703 }
704
705
706 static void edge_free_path(PathBase *pathbase, EPath *path)
707 {
708         EPathNode *node, *next;
709
710         for (node = path->nodes.first; node; node = next) {
711                 next = node->next;
712                 BLI_mempool_free(pathbase->nodepool, node);
713         }
714
715         BLI_mempool_free(pathbase->pathpool, path);
716 }
717
718 static EPath *edge_find_shortest_path(BMesh *bm, BMOperator *op, BMEdge *edge, EdgeData *edata,
719                                       VertData *vdata, PathBase *pathbase, int group)
720 {
721         BMEdge *e;
722         GHash *gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "createops find shortest path");
723         BMVert *v1, *v2;
724         BMVert **verts = NULL;
725         BLI_array_staticdeclare(verts, 1024);
726         Heap *heap = BLI_heap_new();
727         EPath *path = NULL, *path2;
728         BMVert *startv;
729         BMVert *endv;
730         EPathNode *node;
731         int i, use_restrict = BMO_slot_bool_get(op, "use_restrict");
732
733         startv = edata[BM_elem_index_get(edge)].ftag ? edge->v2 : edge->v1;
734         endv = edata[BM_elem_index_get(edge)].ftag ? edge->v1 : edge->v2;
735         
736         path = edge_path_new(pathbase, startv, edge);
737         BLI_ghash_insert(gh, startv, NULL);
738         BLI_heap_insert(heap, path->weight, path);
739         path->group = group;
740
741         while (BLI_heap_size(heap)) {
742                 VertData *vd;
743                 EPathNode *last;
744                 BMFace *f = NULL;
745                 
746                 path = BLI_heap_popmin(heap);
747                 last = path->nodes.last;
748                 v1 = last->v;
749                 
750                 if (v1 == endv) {
751                         /* make sure this path loop doesn't already exist */
752                         i = 0;
753                         BLI_array_empty(verts);
754                         for (i = 0, node = path->nodes.first; node; node = node->next, i++) {
755                                 BLI_array_growone(verts);
756                                 verts[i] = node->v;
757                         }
758
759                         if (BM_face_exists(bm, verts, i, &f)) {
760                                 if (!BMO_elem_flag_test(bm, f, FACE_IGNORE)) {
761                                         BLI_ghash_remove(gh, endv, NULL, NULL);
762                                         continue;
763                                 }
764                         }
765                         break;
766                 }
767                 
768                 vd = vdata + BM_elem_index_get(v1);
769                 if (!vd->e)
770                         continue;
771                 
772                 v2 = NULL;
773                 while (1) {
774                         if (!last->cure) {
775                                 last->cure = e = vdata[BM_elem_index_get(last->v)].e;
776                         }
777                         else {
778                                 last->cure = e = rotsys_nextedge(last->cure, last->v, edata, vdata);
779                                 if (last->cure == vdata[BM_elem_index_get(last->v)].e) {
780                                         v2 = NULL;
781                                         break;
782                                 }
783                         }
784                         
785                         if (e == edge || !BMO_elem_flag_test(bm, e, EDGE_MARK)) {
786                                 continue;
787                         }
788
789                         v2 = BM_edge_other_vert(e, last->v);
790                         
791                         if (BLI_ghash_haskey(gh, v2)) {
792                                 v2 = NULL;
793                                 continue;
794                         }
795                         
796                         if (use_restrict && BMO_slot_map_contains(bm, op, "restrict", e)) {
797                                 int group = BMO_slot_map_int_get(bm, op, "restrict", e);
798                                 
799                                 if (!(group & path->group)) {
800                                         v2 = NULL;
801                                         continue;
802                                 }
803                         }
804
805                         break;
806                 }
807                 
808                 if (!v2) {
809                         if (path) {
810                                 edge_free_path(pathbase, path);
811                                 path = NULL;
812                         }
813                         continue;
814                 }
815                 
816                 /* add path back into hea */
817                 BLI_heap_insert(heap, path->weight, path);
818                 
819                 /* put v2 in gh ma */
820                 BLI_ghash_insert(gh, v2, NULL);
821
822                 path2 = edge_copy_add_path(pathbase, path, v2, e);
823                 path2->weight = edge_weight_path(path2, edata, vdata);
824
825                 BLI_heap_insert(heap, path2->weight, path2);
826         }
827         
828         if (path && ((EPathNode *)path->nodes.last)->v != endv) {
829                 edge_free_path(pathbase, path);
830                 path = NULL;
831         }
832
833         BLI_array_free(verts);
834         BLI_heap_free(heap, NULL);
835         BLI_ghash_free(gh, NULL, NULL);
836
837         return path;
838 }
839
840 static int count_edge_faces(BMesh *bm, BMEdge *e)
841 {
842         int i = 0;
843         BMLoop *l = e->l;
844         
845         if (!l) {
846                 return 0;
847         }
848
849         do {
850                 if (!BMO_elem_flag_test(bm, l->f, FACE_IGNORE)) {
851                         i++;
852                 }
853
854                 l = l->radial_next;
855         } while (l != e->l);
856
857         return i;
858 }
859
860 void bmo_edgenet_fill_exec(BMesh *bm, BMOperator *op)
861 {
862         BMIter iter;
863         BMOIter siter;
864         BMFace *f;
865         BMEdge *e, *edge;
866         BMVert **verts = NULL;
867         BLI_array_declare(verts);
868         EPath *path;
869         EPathNode *node;
870         EdgeData *edata;
871         VertData *vdata;
872         BMEdge **edges = NULL;
873         PathBase *pathbase;
874         BLI_array_declare(edges);
875         int use_restrict   = BMO_slot_bool_get(op, "use_restrict");
876         int use_fill_check = BMO_slot_bool_get(op, "use_fill_check");
877         int i, j, group = 0;
878         unsigned int winding[2]; /* accumulte winding directions for each edge which has a face */
879
880         if (!bm->totvert || !bm->totedge)
881                 return;
882
883         pathbase = edge_pathbase_new();
884
885         edata = MEM_callocN(sizeof(EdgeData) * bm->totedge, "EdgeData");
886         vdata = MEM_callocN(sizeof(VertData) * bm->totvert, "VertData");
887         
888         BMO_slot_buffer_flag_enable(bm, op, "edges", EDGE_MARK, BM_EDGE);
889         BMO_slot_buffer_flag_enable(bm, op, "excludefaces", FACE_IGNORE, BM_FACE);
890         
891         BM_mesh_elem_index_ensure(bm, BM_VERT);
892
893         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
894                 BMO_elem_flag_enable(bm, f, ELE_ORIG);
895         }
896
897         i = 0;
898         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
899                 BM_elem_index_set(e, i); /* set_inline */
900                 
901                 if (!BMO_elem_flag_test(bm, e, EDGE_MARK)) {
902                         edata[i].tag = 2;
903                 }
904
905                 i++;
906         }
907         bm->elem_index_dirty &= ~BM_EDGE;
908
909         init_rotsys(bm, edata, vdata);
910         
911         while (1) {
912                 edge = NULL;
913                 group = 0;
914                 
915                 BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
916                         /* if restrict is on, only start on faces in the restrict map */
917                         if (use_restrict && !BMO_slot_map_contains(bm, op, "restrict", e))
918                                 continue;
919
920                         if (edata[BM_elem_index_get(e)].tag < 2) {
921                                 edge = e;
922
923                                 if (use_restrict) {
924                                         int i = 0, j = 0, gi = 0;
925                                         
926                                         group = BMO_slot_map_int_get(bm, op, "restrict", e);
927                                         
928                                         for (i = 0; i < 30; i++) {
929                                                 if (group & (1 << i)) {
930                                                         j++;
931                                                         gi = i;
932
933                                                         if (j - 1 == edata[BM_elem_index_get(e)].tag) {
934                                                                 break;
935                                                         }
936                                                 }
937                                         }
938
939                                         group = (1 << gi);
940                                 }
941                                 
942                                 break;
943                         }
944                 }
945
946                 if (!edge)
947                         break;
948
949                 edata[BM_elem_index_get(edge)].tag += 1;
950
951                 path = edge_find_shortest_path(bm, op, edge, edata, vdata, pathbase, group);
952                 if (!path)
953                         continue;
954                 
955                 winding[0] = winding[1] = 0;
956
957                 BLI_array_empty(edges);
958                 BLI_array_empty(verts);
959                 i = 0;
960                 for (node = path->nodes.first; node; node = node->next) {
961                         if (!node->next)
962                                 continue;
963
964                         e = BM_edge_exists(node->v, node->next->v);
965                         
966                         /* this should never happe */
967                         if (!e)
968                                 break;
969                         
970                         /* check on the winding */
971                         if (e->l) {
972                                 BMVert *test_v1, *test_v2;
973                                 /* we want to use the reverse winding to the existing order */
974                                 BM_edge_ordered_verts(edge, &test_v2, &test_v1);
975
976                                 /* edges vote on which winding wins out */
977                                 winding[(test_v1 == node->v)]++;
978                         }
979
980                         edata[BM_elem_index_get(e)].ftag++;
981                         BLI_array_growone(edges);
982                         edges[i++] = e;
983
984                         BLI_array_append(verts, node->v);
985                 }
986                 
987                 BLI_array_growone(edges);
988                 edges[i++] = edge;
989                 edata[BM_elem_index_get(edge)].ftag++;
990                 
991                 for (j = 0; j < i; j++) {
992                         if (count_edge_faces(bm, edges[j]) >= 2) {
993                                 edge_free_path(pathbase, path);
994                                 break;
995                         }
996                 }
997
998                 if (j != i) {
999                         continue;
1000                 }
1001
1002                 if (i) {
1003                         BMVert *v1, *v2;
1004
1005                         /* to define the winding order must select first edge,
1006                          * otherwise we could leave this as-is */
1007                         edge = edges[0];
1008
1009                         /* if these are even it doesnt really matter what to do,
1010                          * with consistent geometry one will be zero, the choice is clear */
1011                         if (winding[0] > winding[1]) {
1012                                 v1 = verts[0];
1013                                 v2 = verts[1];
1014                         }
1015                         else {
1016                                 v1 = verts[1];
1017                                 v2 = verts[0];
1018                         }
1019
1020                         if ((use_fill_check == FALSE) ||
1021                             /* fairly expensive check - see if there are already faces filling this area */
1022                             (BM_face_exists_multi_edge(bm, edges, i) == FALSE))
1023                         {
1024                                 f = BM_face_create_ngon(bm, v1, v2, edges, i, TRUE);
1025                                 if (f && !BMO_elem_flag_test(bm, f, ELE_ORIG)) {
1026                                         BMO_elem_flag_enable(bm, f, FACE_NEW);
1027                                 }
1028
1029                                 if (use_restrict) {
1030                                         BMO_slot_map_int_insert(bm, op, "faceout_groupmap", f, path->group);
1031                                 }
1032                         }
1033                 }
1034                 
1035                 edge_free_path(pathbase, path);
1036         }
1037
1038         BMO_slot_buffer_from_flag(bm, op, "faceout", FACE_NEW, BM_FACE);
1039
1040         BLI_array_free(edges);
1041         BLI_array_free(verts);
1042         edge_pathbase_free(pathbase);
1043         MEM_freeN(edata);
1044         MEM_freeN(vdata);
1045 }
1046
1047 static BMEdge *edge_next(BMesh *bm, BMEdge *e)
1048 {
1049         BMIter iter;
1050         BMEdge *e2;
1051         int i;
1052
1053         for (i = 0; i < 2; i++) {
1054                 BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i ? e->v2 : e->v1) {
1055                         if ((BMO_elem_flag_test(bm, e2, EDGE_MARK)) &&
1056                             (!BMO_elem_flag_test(bm, e2, EDGE_VIS)) &&
1057                             (e2 != e))
1058                         {
1059                                 return e2;
1060                         }
1061                 }
1062         }
1063
1064         return NULL;
1065 }
1066
1067 void bmo_edgenet_prepare(BMesh *bm, BMOperator *op)
1068 {
1069         BMOIter siter;
1070         BMEdge *e;
1071         BMEdge **edges1 = NULL, **edges2 = NULL, **edges;
1072         BLI_array_declare(edges1);
1073         BLI_array_declare(edges2);
1074         BLI_array_declare(edges);
1075         int ok = 1;
1076         int i, count;
1077
1078         BMO_slot_buffer_flag_enable(bm, op, "edges", EDGE_MARK, BM_EDGE);
1079         
1080         /* validate that each edge has at most one other tagged edge in the
1081          * disk cycle around each of it's vertices */
1082         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
1083                 for (i = 0; i < 2; i++) {
1084                         count = BMO_vert_edge_flags_count(bm, i ? e->v2 : e->v1, EDGE_MARK);
1085                         if (count > 2) {
1086                                 ok = 0;
1087                                 break;
1088                         }
1089                 }
1090
1091                 if (!ok) {
1092                         break;
1093                 }
1094         }
1095
1096         /* we don't have valid edge layouts, retur */
1097         if (!ok) {
1098                 return;
1099         }
1100
1101         /* find connected loops within the input edge */
1102         count = 0;
1103         while (1) {
1104                 BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
1105                         if (!BMO_elem_flag_test(bm, e, EDGE_VIS)) {
1106                                 if (BMO_vert_edge_flags_count(bm, e->v1, EDGE_MARK) == 1 ||
1107                                     BMO_vert_edge_flags_count(bm, e->v2, EDGE_MARK) == 1)
1108                                 {
1109                                         break;
1110                                 }
1111                         }
1112                 }
1113                 
1114                 if (!e) {
1115                         break;
1116                 }
1117
1118                 if (!count) {
1119                         edges = edges1;
1120                 }
1121                 else if (count == 1) {
1122                         edges = edges2;
1123                 }
1124                 else {
1125                         break;
1126                 }
1127                 
1128                 i = 0;
1129                 while (e) {
1130                         BMO_elem_flag_enable(bm, e, EDGE_VIS);
1131                         BLI_array_growone(edges);
1132                         edges[i] = e;
1133
1134                         e = edge_next(bm, e);
1135                         i++;
1136                 }
1137
1138                 if (!count) {
1139                         edges1 = edges;
1140                         BLI_array_set_length(edges1, BLI_array_count(edges));
1141                 }
1142                 else {
1143                         edges2 = edges;
1144                         BLI_array_set_length(edges2, BLI_array_count(edges));
1145                 }
1146
1147                 BLI_array_empty(edges);
1148                 count++;
1149         }
1150
1151         if (edges1 && BLI_array_count(edges1) > 2 &&
1152             BM_edge_share_vert_count(edges1[0], edges1[BLI_array_count(edges1) - 1]))
1153         {
1154                 if (edges2 && BLI_array_count(edges2) > 2 &&
1155                     BM_edge_share_vert_count(edges2[0], edges2[BLI_array_count(edges2) - 1]))
1156                 {
1157                         BLI_array_free(edges1);
1158                         BLI_array_free(edges2);
1159                         return;
1160                 }
1161                 else {
1162                         edges1 = edges2;
1163                         edges2 = NULL;
1164                 }
1165         }
1166
1167         if (edges2 && BLI_array_count(edges2) > 2 &&
1168             BM_edge_share_vert_count(edges2[0], edges2[BLI_array_count(edges2) - 1]))
1169         {
1170                 edges2 = NULL;
1171         }
1172
1173         /* two unconnected loops, connect the */
1174         if (edges1 && edges2) {
1175                 BMVert *v1, *v2, *v3, *v4;
1176                 float dvec1[3];
1177                 float dvec2[3];
1178
1179                 if (BLI_array_count(edges1) == 1) {
1180                         v1 = edges1[0]->v1;
1181                         v2 = edges1[0]->v2;
1182                 }
1183                 else {
1184                         v1 = BM_vert_in_edge(edges1[1], edges1[0]->v1) ? edges1[0]->v2 : edges1[0]->v1;
1185                         i  = BLI_array_count(edges1) - 1;
1186                         v2 = BM_vert_in_edge(edges1[i - 1], edges1[i]->v1) ? edges1[i]->v2 : edges1[i]->v1;
1187                 }
1188
1189                 if (BLI_array_count(edges2) == 1) {
1190                         v3 = edges2[0]->v1;
1191                         v4 = edges2[0]->v2;
1192                 }
1193                 else {
1194                         v3 = BM_vert_in_edge(edges2[1], edges2[0]->v1) ? edges2[0]->v2 : edges2[0]->v1;
1195                         i  = BLI_array_count(edges2) - 1;
1196                         v4 = BM_vert_in_edge(edges2[i - 1], edges2[i]->v1) ? edges2[i]->v2 : edges2[i]->v1;
1197                 }
1198
1199                 /* if there is ever bowtie quads between two edges the problem is here! [#30367] */
1200 #if 0
1201                 normal_tri_v3(dvec1, v1->co, v2->co, v4->co);
1202                 normal_tri_v3(dvec2, v1->co, v4->co, v3->co);
1203 #else
1204                 {
1205                         /* save some CPU cycles and skip the sqrt and 1 subtraction */
1206                         float a1[3], a2[3], a3[3];
1207                         sub_v3_v3v3(a1, v1->co, v2->co);
1208                         sub_v3_v3v3(a2, v1->co, v4->co);
1209                         sub_v3_v3v3(a3, v1->co, v3->co);
1210                         cross_v3_v3v3(dvec1, a1, a2);
1211                         cross_v3_v3v3(dvec2, a2, a3);
1212                 }
1213 #endif
1214                 if (dot_v3v3(dvec1, dvec2) < 0.0f) {
1215                         SWAP(BMVert *, v3, v4);
1216                 }
1217
1218                 e = BM_edge_create(bm, v1, v3, NULL, TRUE);
1219                 BMO_elem_flag_enable(bm, e, ELE_NEW);
1220                 e = BM_edge_create(bm, v2, v4, NULL, TRUE);
1221                 BMO_elem_flag_enable(bm, e, ELE_NEW);
1222         }
1223         else if (edges1) {
1224                 BMVert *v1, *v2;
1225
1226                 if (BLI_array_count(edges1) > 1) {
1227                         v1 = BM_vert_in_edge(edges1[1], edges1[0]->v1) ? edges1[0]->v2 : edges1[0]->v1;
1228                         i  = BLI_array_count(edges1) - 1;
1229                         v2 = BM_vert_in_edge(edges1[i - 1], edges1[i]->v1) ? edges1[i]->v2 : edges1[i]->v1;
1230                         e  = BM_edge_create(bm, v1, v2, NULL, TRUE);
1231                         BMO_elem_flag_enable(bm, e, ELE_NEW);
1232                 }
1233         }
1234         
1235         BMO_slot_buffer_from_flag(bm, op, "edgeout", ELE_NEW, BM_EDGE);
1236
1237         BLI_array_free(edges1);
1238         BLI_array_free(edges2);
1239 }
1240
1241 /* this is essentially new fke */
1242 void bmo_contextual_create_exec(BMesh *bm, BMOperator *op)
1243 {
1244         BMOperator op2;
1245         BMOIter oiter;
1246         BMIter iter;
1247         BMHeader *h;
1248         BMVert *v, *verts[4];
1249         BMEdge *e;
1250         BMFace *f;
1251         int totv = 0, tote = 0, totf = 0, amount;
1252
1253         /* count number of each element type we were passe */
1254         BMO_ITER(h, &oiter, bm, op, "geom", BM_VERT|BM_EDGE|BM_FACE) {
1255                 switch (h->htype) {
1256                         case BM_VERT: totv++; break;
1257                         case BM_EDGE: tote++; break;
1258                         case BM_FACE: totf++; break;
1259                 }
1260
1261                 BMO_elem_flag_enable(bm, (BMElemF *)h, ELE_NEW);
1262         }
1263         
1264         /* --- Support for Special Case ---
1265          * where there is a contiguous edge ring with one isolated vertex.
1266          *
1267          * This example shows 2 edges created from 3 verts
1268          * with 1 free standing vertex. Dotted lines denote the 2 edges that are created.
1269          *
1270          * note that this works for any sided shape.
1271          *
1272          * +--------+
1273          * |        .
1274          * |        .
1275          * |        .
1276          * |        .
1277          * +........+ <-- starts out free standing.
1278          *
1279          */
1280
1281         /* Here we check for consistancy and create 2 edges */
1282         if (totf == 0 && totv >= 4 && totv == tote + 2) {
1283                 /* find a free standing vertex and 2 endpoint verts */
1284                 BMVert *v_free = NULL, *v_a = NULL, *v_b = NULL;
1285                 int ok = TRUE;
1286
1287
1288                 BMO_ITER(v, &oiter, bm, op, "geom", BM_VERT) {
1289                         /* count how many flagged edges this vertex uses */
1290                         int tot_edges = 0;
1291                         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
1292                                 if (BMO_elem_flag_test(bm, e, ELE_NEW)) {
1293                                         tot_edges++;
1294                                         if (tot_edges > 2) {
1295                                                 break;
1296                                         }
1297                                 }
1298                         }
1299
1300                         if (tot_edges == 0) {
1301                                 /* only accept 1 free vert */
1302                                 if (v_free == NULL)  v_free = v;
1303                                 else                 ok = FALSE;  /* only ever want one of these */
1304                         }
1305                         else if (tot_edges == 1) {
1306                                 if (v_a == NULL)       v_a = v;
1307                                 else if (v_b == NULL)  v_b = v;
1308                                 else                   ok = FALSE;  /* only ever want 2 of these */
1309                         }
1310                         else if (tot_edges == 2) {
1311                                 /* do nothing, regular case */
1312                         }
1313                         else {
1314                                 ok = FALSE; /* if a vertex has 3+ edge users then cancel - this is only simple cases */
1315                         }
1316
1317                         if (ok == FALSE) {
1318                                 break;
1319                         }
1320                 }
1321
1322                 if (ok == TRUE && v_free && v_a && v_b) {
1323                         e = BM_edge_create(bm, v_free, v_a, NULL, TRUE);
1324                         BMO_elem_flag_enable(bm, e, ELE_NEW);
1325
1326                         e = BM_edge_create(bm, v_free, v_b, NULL, TRUE);
1327                         BMO_elem_flag_enable(bm, e, ELE_NEW);
1328                 }
1329         }
1330         /* --- end special case support, continue as normal --- */
1331
1332         /* call edgenet create */
1333         /* call edgenet prepare op so additional face creation cases wor */
1334         BMO_op_initf(bm, &op2, "edgenet_prepare edges=%fe", ELE_NEW);
1335         BMO_op_exec(bm, &op2);
1336         BMO_slot_buffer_flag_enable(bm, &op2, "edgeout", ELE_NEW, BM_EDGE);
1337         BMO_op_finish(bm, &op2);
1338
1339         BMO_op_initf(bm, &op2, "edgenet_fill edges=%fe use_fill_check=%b", ELE_NEW, TRUE);
1340         BMO_op_exec(bm, &op2);
1341
1342         /* return if edge net create did somethin */
1343         if (BMO_slot_buffer_count(bm, &op2, "faceout")) {
1344                 BMO_slot_copy(&op2, op, "faceout", "faceout");
1345                 BMO_op_finish(bm, &op2);
1346                 return;
1347         }
1348
1349         BMO_op_finish(bm, &op2);
1350         
1351         /* now call dissolve face */
1352         BMO_op_initf(bm, &op2, "dissolve_faces faces=%ff", ELE_NEW);
1353         BMO_op_exec(bm, &op2);
1354         
1355         /* if we dissolved anything, then return */
1356         if (BMO_slot_buffer_count(bm, &op2, "regionout")) {
1357                 BMO_slot_copy(&op2, op, "regionout", "faceout");
1358                 BMO_op_finish(bm, &op2);
1359                 return;
1360         }
1361
1362         BMO_op_finish(bm, &op2);
1363
1364         /* now, count how many verts we hav */
1365         amount = 0;
1366         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
1367                 if (BMO_elem_flag_test(bm, v, ELE_NEW)) {
1368                         verts[amount] = v;
1369                         amount++;
1370
1371                         if (amount > 4) break;
1372                 }
1373         }
1374
1375         if (amount == 2) {
1376                 /* create edg */
1377                 e = BM_edge_create(bm, verts[0], verts[1], NULL, TRUE);
1378                 BMO_elem_flag_enable(bm, e, ELE_OUT);
1379         }
1380         else if (amount == 3) {
1381                 /* create triangl */
1382                 f = BM_face_create_quad_tri(bm, verts[0], verts[1], verts[2], NULL, NULL, TRUE);
1383
1384                 if (f) {
1385                         BMO_elem_flag_enable(bm, f, ELE_OUT);
1386                 }
1387         }
1388         else if (amount == 4) {
1389                 f = NULL;
1390
1391                 /* the order of vertices can be anything, 6 cases to check */
1392                 if (is_quad_convex_v3(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co)) {
1393                         f = BM_face_create_quad_tri(bm, verts[0], verts[1], verts[2], verts[3], NULL, TRUE);
1394                 }
1395                 else if (is_quad_convex_v3(verts[0]->co, verts[2]->co, verts[3]->co, verts[1]->co)) {
1396                         f = BM_face_create_quad_tri(bm, verts[0], verts[2], verts[3], verts[1], NULL, TRUE);
1397                 }
1398                 else if (is_quad_convex_v3(verts[0]->co, verts[2]->co, verts[1]->co, verts[3]->co)) {
1399                         f = BM_face_create_quad_tri(bm, verts[0], verts[2], verts[1], verts[3], NULL, TRUE);
1400                 }
1401                 else if (is_quad_convex_v3(verts[0]->co, verts[1]->co, verts[3]->co, verts[2]->co)) {
1402                         f = BM_face_create_quad_tri(bm, verts[0], verts[1], verts[3], verts[2], NULL, TRUE);
1403                 }
1404                 else if (is_quad_convex_v3(verts[0]->co, verts[3]->co, verts[2]->co, verts[1]->co)) {
1405                         f = BM_face_create_quad_tri(bm, verts[0], verts[3], verts[2], verts[1], NULL, TRUE);
1406                 }
1407                 else if (is_quad_convex_v3(verts[0]->co, verts[3]->co, verts[1]->co, verts[2]->co)) {
1408                         f = BM_face_create_quad_tri(bm, verts[0], verts[3], verts[1], verts[2], NULL, TRUE);
1409                 }
1410                 else {
1411                         printf("cannot find nice quad from concave set of vertices\n");
1412                 }
1413
1414                 if (f) {
1415                         BMO_elem_flag_enable(bm, f, ELE_OUT);
1416                 }
1417         }
1418 }