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