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