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