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