merge with/from trunk at r35190
[blender.git] / source / blender / bmesh / operators / createops.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_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) (Link*)((v) == ((BMEdge*)(e))->v1 ? &(((EdgeData*)(ed))->dlink1) : &(((EdgeData*)(ed))->dlink2))
69
70 int rotsys_append_edge(struct BMEdge *e, struct BMVert *v, 
71                                                 EdgeData *edata, VertData *vdata)
72 {
73         EdgeData *ed = &edata[BMINDEX_GET(e)];
74         VertData *vd = &vdata[BMINDEX_GET(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[BMINDEX_GET(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[BMINDEX_GET(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 void rotsys_remove_edge(struct BMEdge *e, struct BMVert *v, 
101                                                 EdgeData *edata, VertData *vdata)
102 {
103         EdgeData *ed = edata + BMINDEX_GET(e);
104         VertData *vd = vdata + BMINDEX_GET(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!=e1->next ? (BMEdge*)e1->next : NULL;
120
121         e1->next = e1->prev = NULL;
122 }
123
124 struct BMEdge *rotsys_nextedge(struct BMEdge *e, struct BMVert *v, 
125                                                                         EdgeData *edata, VertData *vdata)
126 {
127         if (v == e->v1)
128                 return edata[BMINDEX_GET(e)].dlink1.next;
129         if (v == e->v2)
130                 return edata[BMINDEX_GET(e)].dlink2.next;
131         return NULL;
132 }
133
134 BMEdge *rotsys_prevedge(BMEdge *e, BMVert *v, 
135                                                 EdgeData *edata, VertData *vdata)
136 {
137         if (v == e->v1)
138                 return edata[BMINDEX_GET(e)].dlink1.prev;
139         if (v == e->v2)
140                 return edata[BMINDEX_GET(e)].dlink2.prev;
141         return NULL;
142 }
143
144 struct BMEdge *rotsys_reverse(struct BMEdge *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[BMINDEX_GET(v)].e;
152         do {
153                 BLI_array_append(edges, e2);
154                 e2 = rotsys_nextedge(e2, v, edata, vdata);
155         } while (e2 != vdata[BMINDEX_GET(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[BMINDEX_GET(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         return 0;
170 }
171
172 int rotsys_count(struct BMVert *v, EdgeData *edata, VertData *vdata)
173 {
174         BMEdge *e = vdata[BMINDEX_GET(v)].e;
175         int i=0;
176
177         if (!e)
178                 return 0;
179
180         do {
181                 if (!e)
182                         return 0;
183                 e =  rotsys_nextedge(e, v, edata, vdata);
184
185                 if (i >= (1<<20)) {
186                         printf("bmesh error: infinite loop in disk cycle!\n");
187                         return 0;
188                 }
189
190                 i += 1;
191         } while (e != vdata[BMINDEX_GET(v)].e);
192
193         return i;
194 }
195
196 int rotsys_fill_faces(BMesh *bm, EdgeData *edata, VertData *vdata)
197 {
198         BMIter iter;
199         BMEdge *e, **edges = NULL;
200         BLI_array_declare(edges);
201         BMVert *v, **verts = NULL;
202         BMFace *f;
203         BLI_array_declare(verts);
204         SmallHash visithash, *hash=&visithash;
205         int i;
206         
207         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
208                 BMEdge *e2, *starte;
209                 BMVert *startv;
210                 int rad, ok;
211                 
212                 rad = count_edge_faces(bm, e);
213                 
214                 if (rad < 2)
215                         starte = e;
216                 else
217                         continue;
218                 
219                 /*do two passes, going forward then backward*/
220                 for (i=0; i<2; i++) {
221                         BLI_smallhash_init(hash);
222                         
223                         BLI_array_empty(verts);
224                         BLI_array_empty(edges);
225
226                         startv = v = starte->v1;
227                         e2 = starte;
228                         ok = 1;
229                         if (!v || !e2)
230                                 continue;
231                                 
232                         do {
233                                 if (BLI_smallhash_haskey(hash, (intptr_t)e2) 
234                                  || BLI_smallhash_haskey(hash, (intptr_t)v)) {
235                                         ok = 0;
236                                         break;
237                                 }
238                                 
239                                 BLI_array_append(verts, v);
240                                 BLI_array_append(edges, e2);
241                                 
242                                 BLI_smallhash_insert(hash, (intptr_t)e2, NULL);
243         
244                                 v = BM_OtherEdgeVert(e2, v);
245                                 e2 = i ? rotsys_prevedge(e2, v, edata, vdata) : rotsys_nextedge(e2, v, edata, vdata);
246                         } while (e2 != starte && v != startv);
247                         
248                         BLI_smallhash_release(hash);
249                         
250                         if (!ok || BLI_array_count(edges) < 3)
251                                 continue;
252                         
253                         f = BM_Make_Ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), 1);
254                         if (!f)
255                                 continue;
256                 }
257         }
258         
259         return 0;
260 }
261
262 void rotsys_make_consistent(BMesh *bm, EdgeData *edata, VertData *vdata)
263 {
264         BMIter iter;
265         BMEdge *e;
266         BMVert *v, **stack=NULL;
267         BLI_array_declare(stack);
268         int i;
269         
270         for (i=0; i<bm->totvert; i++) {
271                 vdata[i].tag = 0;
272         }
273         
274         while (1) {
275                 VertData *vd;
276                 BMVert *startv = NULL;
277                 float dis;
278                 
279                 v = BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL);
280                 for (i=0; i<bm->totvert; i++, BMIter_Step(&iter)) {
281                         vd = vdata + BMINDEX_GET(v);
282                         
283                         if (vd->tag)
284                                 continue;
285                         
286                         if (!startv || dot_v3v3(vd->offco, vd->offco) > dis) {
287                                 dis = dot_v3v3(vd->offco, vd->offco);
288                                 startv = v;
289                         }
290                 }
291                 
292                 if (!startv)
293                         break;
294                 
295                 vd = vdata + BMINDEX_GET(startv);
296                 
297                 BLI_array_empty(stack);
298                 BLI_array_append(stack, startv);
299                 
300                 vd->tag = 1;
301                 
302                 while (BLI_array_count(stack)) {
303                         v = BLI_array_pop(stack);
304                         vd = vdata + BMINDEX_GET(v);
305                         
306                         if (!vd->e)
307                                 continue;
308                         
309                         e = vd->e;
310                         do {
311                                 BMVert *v2 = BM_OtherEdgeVert(e, v);
312                                 VertData *vd2 = vdata + BMINDEX_GET(v2);
313                                 
314                                 if (dot_v3v3(vd->no, vd2->no) < 0.0f+FLT_EPSILON*2) {
315                                         rotsys_reverse(e, v2, edata, vdata);
316                                         mul_v3_fl(vd2->no, -1.0f);
317                                 }
318
319                                 if (!vd2->tag) {
320                                         BLI_array_append(stack, v2);
321                                         vd2->tag = 1;
322                                 }
323                                 
324                                 e = rotsys_nextedge(e, v, edata, vdata);
325                         } while (e != vd->e);
326                 }
327         }
328         
329 }
330
331 void init_rotsys(BMesh *bm, EdgeData *edata, VertData *vdata)
332 {
333         BMIter iter;
334         BMEdge *e;
335         BMEdge **edges = NULL;
336         BLI_array_staticdeclare(edges, 256);
337         BMVert *v, *lastv, **verts = NULL;
338         BLI_array_staticdeclare(verts, 256);
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 (BMINDEX_GET(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[BMINDEX_GET(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+BMINDEX_GET(v1); vd2 = vdata+BMINDEX_GET(v2); vd3 = vdata+BMINDEX_GET(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.01;
430                         normalize_v3(vec1); normalize_v3(vec2); normalize_v3(vec3);
431                         
432                         #ifdef STRAIGHT
433                         #undef STRAIGHT
434                         #endif
435                         #define STRAIGHT(vec11, vec22) (fabs(dot_v3v3((vec11), (vec22))) > 1.0-FLT_EPSILON*1000)
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[BMINDEX_GET(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+BMINDEX_GET(v1); vd2 = vdata+BMINDEX_GET(v2); vd3 = vdata+BMINDEX_GET(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                                 normalize_v3(n1); normalize_v3(n2); normalize_v3(n3);
489                                 
490                                 s1 = STRAIGHT(vec1, vec2); s2 = STRAIGHT(vec2, vec3); s3 = STRAIGHT(vec1, vec3);
491                                                                 
492                                 if (s1 || s2 || s3) {
493                                         printf("yeek! s1: %d, s2: %d, s3: %dx\n", s1, s2, s3);
494                                 }
495                                 if (dot_v3v3(n1, n2) < 0.0f) {
496                                         if (dot_v3v3(n1, n3) >= 0.0f + FLT_EPSILON*10) {
497                                                 SWAP(BMEdge*, edges[i], edges[(i+1)%totedge]);
498                                         } else {
499                                                 SWAP(BMEdge*, edges[(i+totedge-1)%totedge], edges[(i+1)%totedge])
500                                                 SWAP(BMEdge*, edges[i], edges[(i+1)%totedge])
501                                         }
502                                 } 
503                         }
504                 }
505                 
506                 #undef STRAIGHT
507                                 
508                 zero_v3(no);
509                 
510                 /*yay, edges is sorted*/
511                 for (i=0; i<totedge; i++) {
512                         BMEdge *e1 = edges[i], *e2 = edges[(i+1)%totedge];
513                         float eno[3];
514                         
515                         normal_tri_v3(eno, BM_OtherEdgeVert(e1, v)->co, v->co, BM_OtherEdgeVert(e2, v)->co);
516                         add_v3_v3(no, eno);
517                         
518                         rotsys_append_edge(edges[i], v, edata, vdata);
519                 }
520                 
521                 normalize_v3(no);
522                 copy_v3_v3(vdata[BMINDEX_GET(v)].no, no);
523         }
524         
525         /*now, make sure rotation system is topologically consistent
526           (e.g. vert normals consistently point either inside or outside)*/
527         rotsys_make_consistent(bm, edata, vdata);
528
529         //rotsys_fill_faces(bm, edata, vdata);
530
531 #if 0
532         /*create visualizing geometry*/
533         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
534                 BMVert *v2;
535                 BMFace *f;
536                 int totedge = BM_Vert_EdgeCount(v);
537
538                 if (BMINDEX_GET(v) == -1)
539                         continue;
540                 
541                 //cv = BM_Make_Vert(bm, cent, v);
542                 //BMINDEX_SET(cv, -1);
543                 i = 0;
544                 e = vdata[BMINDEX_GET(v)].e;
545                 lastv = NULL;
546                 do {
547                         BMEdge *e2;
548                         BMVert *v2;
549                         float f = ((float)i / (float)totedge)*0.35 + 0.05;
550                         float co[3];
551                         
552                         if (!e)
553                                 break;
554                                 
555                         if (!BM_OtherEdgeVert(e, v))
556                                 continue;
557                         
558                         sub_v3_v3v3(co, (BM_OtherEdgeVert(e, v))->co, vdata[BMINDEX_GET(v)].offco);
559                         mul_v3_fl(co, f);
560                         add_v3_v3(co, vdata[BMINDEX_GET(v)].offco);
561                         
562                         v2 = BM_Make_Vert(bm, co, NULL);
563                         BMINDEX_SET(v2, -1);
564                         //BM_Make_Edge(bm, cv, v2, NULL, 0);
565                         
566                         BM_Select(bm, v2, 1);
567                         if (lastv) {
568                                 e2 =
569                                  BM_Make_Edge(bm, lastv, v2, NULL, 0);
570                                 BM_Select(bm, e2, 1);
571                         }
572                         
573                         lastv = v2;
574                         
575                         e = rotsys_nextedge(e, v, edata, vdata);
576                         i++;
577                 } while (e != vdata[BMINDEX_GET(v)].e);
578         }
579 #endif
580
581         BLI_array_free(edges);
582 }
583
584 PathBase *edge_pathbase_new(void)
585 {
586         PathBase *pb = MEM_callocN(sizeof(PathBase), "PathBase");
587
588         pb->nodepool = BLI_mempool_create(sizeof(EPathNode), 1, 512, 1, 0);
589         pb->pathpool = BLI_mempool_create(sizeof(EPath), 1, 512, 1, 0);
590
591         return pb;
592 }
593
594 void edge_pathbase_free(PathBase *pathbase)
595 {
596         BLI_mempool_destroy(pathbase->nodepool);
597         BLI_mempool_destroy(pathbase->pathpool);
598         MEM_freeN(pathbase);
599 }
600
601 EPath *edge_copy_add_path(PathBase *pb, EPath *path, BMVert *appendv, BMEdge *e)
602 {
603         EPath *path2;
604         EPathNode *node, *node2;
605
606         path2 = BLI_mempool_alloc(pb->pathpool);
607         path2->nodes.first = path2->nodes.last = NULL;
608         path2->weight = 0.0f;
609         path2->group = path->group;
610         
611         for (node=path->nodes.first; node; node=node->next) {
612                 node2 = BLI_mempool_alloc(pb->nodepool);
613                 *node2 = *node;
614                 BLI_addtail(&path2->nodes, node2);
615         }
616
617         node2 = BLI_mempool_alloc(pb->nodepool);
618         node2->v = appendv;
619         node2->e = e;
620         node2->cure = NULL;
621
622         BLI_addtail(&path2->nodes, node2);
623
624         return path2;
625 }
626
627 EPath *edge_path_new(PathBase *pb, BMVert *start, BMEdge *starte)
628 {
629         EPath *path;
630         EPathNode *node;
631
632         path = BLI_mempool_alloc(pb->pathpool);
633         node = BLI_mempool_alloc(pb->nodepool);
634         
635         path->nodes.first = path->nodes.last = NULL;
636         
637         node->v = start;
638         node->e = starte;
639         node->cure = NULL;
640
641         BLI_addtail(&path->nodes, node);
642         path->weight = 0.0f;
643
644         return path;
645 }
646
647 float edge_weight_path(EPath *path, EdgeData *edata, VertData *vdata)
648 {
649         EPathNode *node, *first=path->nodes.first;
650         float w = 0.0;
651
652         for (node=path->nodes.first; node; node=node->next) {
653                 if (node->e && node != path->nodes.first) {
654                         w += edata[BMINDEX_GET(node->e)].ftag;
655                         if (node->prev) {
656                                 //w += len_v3v3(node->v->co, first->e->v1->co)*0.0001f;
657                                 //w += len_v3v3(node->v->co, first->e->v2->co)*0.0001f;                         
658                         }
659                 }
660
661                 w += 1.0f;
662         }
663
664         return w;
665 }
666
667
668 void edge_free_path(PathBase *pathbase, EPath *path)
669 {
670         EPathNode *node, *next;
671
672         for (node=path->nodes.first; node; node=next) {
673                 next = node->next;
674                 BLI_mempool_free(pathbase->nodepool, node);
675         }
676
677         BLI_mempool_free(pathbase->pathpool, path);
678 }
679
680 EPath *edge_find_shortest_path(BMesh *bm, BMOperator *op, BMEdge *edge, EdgeData *edata, 
681                                                                 VertData *vdata, PathBase *pathbase, int group)
682 {
683         BMEdge *e, *starte;
684         GHash *gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "createops find shortest path");
685         BMVert *v1, *v2;
686         BMVert **verts = NULL;
687         BLI_array_staticdeclare(verts, 1024);
688         Heap *heap = BLI_heap_new();
689         EPath *path = NULL, *path2;
690         BMVert *startv;
691         BMVert *endv;
692         EPathNode *node;
693         int i, use_restrict = BMO_Get_Int(op, "use_restrict");
694
695         startv = edata[BMINDEX_GET(edge)].ftag ? edge->v2 : edge->v1;
696         endv = edata[BMINDEX_GET(edge)].ftag ? edge->v1 : edge->v2;
697         
698         path = edge_path_new(pathbase, startv, edge);
699         BLI_ghash_insert(gh, startv, NULL);
700         BLI_heap_insert(heap, path->weight, path);
701         path->group = group;
702
703         while (BLI_heap_size(heap)) {
704                 VertData *vd;
705                 EPathNode *last;
706                 BMFace *f = NULL;
707                 
708                 path = BLI_heap_popmin(heap);
709                 last = path->nodes.last;
710                 v1 = last->v;
711                 
712                 if (v1 == endv) {
713                         /*make sure this path loop doesn't already exist*/
714                         i = 0;
715                         BLI_array_empty(verts);
716                         for (i=0, node = path->nodes.first; node; node=node->next, i++) {
717                                 BLI_array_growone(verts);
718                                 verts[i] = node->v;
719                         }
720
721                         if (BM_Face_Exists(bm, verts, i, &f)) {
722                                 if (!BMO_TestFlag(bm, f, FACE_IGNORE)) {
723                                         BLI_ghash_remove(gh, endv, NULL, NULL);
724                                         continue;
725                                 }
726                         }
727                         break;
728                 }
729                 
730                 vd = vdata + BMINDEX_GET(v1);
731                 if (!vd->e)
732                         continue;
733                 
734                 v2 = NULL;
735                 while (1) {             
736                         if (!last->cure) {
737                                 last->cure = e = vdata[BMINDEX_GET(last->v)].e;
738                         } else {
739                                 last->cure = e = rotsys_nextedge(last->cure, last->v, edata, vdata);
740                                 if (last->cure == vdata[BMINDEX_GET(last->v)].e) {
741                                         v2 = NULL;
742                                         break;
743                                 }
744                         }
745                         
746                         if (e == edge || !BMO_TestFlag(bm, e, EDGE_MARK)) {
747                                 continue;
748                         }
749                                 
750                         v2 = BM_OtherEdgeVert(e, last->v);
751                         
752                         if (BLI_ghash_haskey(gh, v2)) {
753                                 v2 = NULL;
754                                 continue;
755                         }
756                         
757                         if (use_restrict && BMO_InMap(bm, op, "restrict", e)) {
758                                 int group = BMO_Get_MapInt(bm, op, "restrict", e);
759                                 
760                                 if (!(group & path->group)) {
761                                         v2 = NULL;
762                                         continue;
763                                 }
764                         }
765
766                         break;
767                 }
768                 
769                 if (!v2) {
770                         if (path) {
771                                 edge_free_path(pathbase, path);
772                                 path = NULL;
773                         }
774                         continue;
775                 }
776                 
777                 /*add path back into heap*/
778                 BLI_heap_insert(heap, path->weight, path);
779                 
780                 /*put v2 in gh map*/
781                 BLI_ghash_insert(gh, v2, NULL);
782
783                 path2 = edge_copy_add_path(pathbase, path, v2, e);
784                 path2->weight = edge_weight_path(path2, edata, vdata);
785
786                 BLI_heap_insert(heap, path2->weight, path2);
787         }
788         
789         if (path && ((EPathNode*)path->nodes.last)->v != endv) {
790                 edge_free_path(pathbase, path);
791                 path = NULL;
792         }
793                 
794         BLI_array_free(verts);
795         BLI_heap_free(heap, NULL);
796         BLI_ghash_free(gh, NULL, NULL);
797
798         return path;
799 }
800
801 static int count_edge_faces(BMesh *bm, BMEdge *e) {
802         int i=0;
803         BMLoop *l = e->l;
804         
805         if (!l)
806                 return 0;
807         
808         do {
809                 if (!BMO_TestFlag(bm, l->f, FACE_IGNORE))
810                         i++;
811
812                 l = l->radial_next;
813         } while (l != e->l);
814         
815         return i;
816 }
817
818 void bmesh_edgenet_fill_exec(BMesh *bm, BMOperator *op)
819 {
820         BMIter iter;
821         BMOIter siter;
822         BMFace *f;
823         BMEdge *e, *edge;
824         BMVert *v, **verts = NULL;
825         BLI_array_declare(verts);
826         EPath *path;
827         EPathNode *node;
828         EdgeData *edata;
829         VertData *vdata;
830         BMEdge **edges = NULL;
831         PathBase *pathbase = edge_pathbase_new();
832         BLI_array_declare(edges);
833         int use_restrict = BMO_Get_Int(op, "use_restrict");
834         int i, j, group = 0;
835
836         if (!bm->totvert || !bm->totedge)
837                 return;
838
839         edata = MEM_callocN(sizeof(EdgeData)*bm->totedge, "EdgeData");
840         vdata = MEM_callocN(sizeof(VertData)*bm->totvert, "VertData");
841         
842         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
843         BMO_Flag_Buffer(bm, op, "excludefaces", FACE_IGNORE, BM_FACE);
844         
845         i = 0;
846         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
847                 BMINDEX_SET(v, i);
848                 i++;    
849         }
850
851         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
852                 BMO_SetFlag(bm, f, ELE_ORIG);
853         }
854
855         i = 0;
856         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
857                 BMINDEX_SET(e, i);
858                 
859                 if (!BMO_TestFlag(bm, e, EDGE_MARK)) {
860                         edata[i].tag = 2;
861                 }
862
863                 i += 1;
864         }
865
866         init_rotsys(bm, edata, vdata);
867         
868         while (1) {
869                 edge = NULL;
870                 group = 0;
871                 
872                 BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
873                         /*if restrict is on, only start on faces in the restrict map*/
874                         if (use_restrict && !BMO_InMap(bm, op, "restrict", e))
875                                 continue;
876                                 
877                         if (edata[BMINDEX_GET(e)].tag < 2) {
878                                 edge = e;
879
880                                 if (use_restrict) {
881                                         int i=0, j=0, gi=0;
882                                         
883                                         group = BMO_Get_MapInt(bm, op, "restrict", e);                          
884                                         
885                                         for (i=0; i<30; i++) {
886                                                 if (group & (1<<i)) {
887                                                         j++;
888                                                         gi = i;
889
890                                                         if (j-1 == edata[BMINDEX_GET(e)].tag)
891                                                                 break;
892                                                 }
893                                         }
894                                         
895                                         group = 1<<gi;
896                                 }
897                                 
898                                 break;
899                         }
900                 }
901
902                 if (!edge)
903                         break;
904
905                 edata[BMINDEX_GET(edge)].tag += 1;
906
907                 path = edge_find_shortest_path(bm, op, edge, edata, vdata, pathbase, group);
908                 if (!path)
909                         continue;
910                 
911                 BLI_array_empty(edges);
912                 BLI_array_empty(verts);
913                 i = 0;
914                 for (node=path->nodes.first; node; node=node->next) {
915                         if (!node->next)
916                                 continue;
917
918                         e = BM_Edge_Exist(node->v, node->next->v);
919                         
920                         /*this should never happen*/
921                         if (!e)
922                                 break;
923                         
924                         edata[BMINDEX_GET(e)].ftag++;
925                         BLI_array_growone(edges);
926                         edges[i++] = e;
927
928                         BLI_array_append(verts, node->v);
929                 }
930                 
931                 BLI_array_growone(edges);
932                 edges[i++] = edge;
933                 edata[BMINDEX_GET(edge)].ftag++;
934                 
935                 for (j=0; j<i; j++) {
936                         if (count_edge_faces(bm, edges[j]) >= 2) {                      
937                                 edge_free_path(pathbase, path);
938                                 break;
939                         }
940                 }
941                 
942                 if (j != i)
943                         continue;
944                 
945                 if (i) {
946                         f = BM_Make_Ngon(bm, edge->v1, edge->v2, edges, i, 1);
947                         if (f && !BMO_TestFlag(bm, f, ELE_ORIG)) {
948                                 BMO_SetFlag(bm, f, FACE_NEW);
949                         }
950
951                         if (use_restrict)
952                                 BMO_Insert_MapInt(bm, op, "faceout_groupmap", f, path->group);
953                 }
954                 
955                 edge_free_path(pathbase, path);
956         }
957
958         BMO_Flag_To_Slot(bm, op, "faceout", FACE_NEW, BM_FACE);
959
960         BLI_array_free(edges);
961         BLI_array_free(verts);
962         edge_pathbase_free(pathbase);
963         MEM_freeN(edata);
964         MEM_freeN(vdata);
965 }
966
967 /* evaluate if entire quad is a proper convex quad */
968 static int convex(float *v1, float *v2, float *v3, float *v4)
969 {
970         float nor[3], nor1[3], nor2[3], vec[4][2];
971         
972         /* define projection, do both trias apart, quad is undefined! */
973         normal_tri_v3( nor1,v1, v2, v3);
974         normal_tri_v3( nor2,v1, v3, v4);
975         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
976         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
977         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
978
979         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
980                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
981                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
982                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
983                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
984         }
985         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
986                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
987                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
988                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
989                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
990         }
991         else {
992                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
993                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
994                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
995                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
996         }
997         
998         /* linetests, the 2 diagonals have to instersect to be convex */
999         if( isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
1000         return 0;
1001 }
1002
1003 BMEdge *edge_next(BMesh *bm, BMEdge *e)
1004 {
1005         BMIter iter;
1006         BMEdge *e2;
1007         int i;
1008
1009         for (i=0; i<2; i++) {
1010                 BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i?e->v2:e->v1) {
1011                         if (BMO_TestFlag(bm, e2, EDGE_MARK) 
1012                             && !BMO_TestFlag(bm, e2, EDGE_VIS) && e2 != e)
1013                         {
1014                                 return e2;
1015                         }
1016                 }
1017         }
1018
1019         return NULL;
1020 }
1021
1022 void bmesh_edgenet_prepare(BMesh *bm, BMOperator *op)
1023 {
1024         BMOIter siter;
1025         BMIter iter;
1026         BMEdge *e, *e2;
1027         BMEdge **edges1 = NULL, **edges2 = NULL, **edges;
1028         BLI_array_declare(edges1);
1029         BLI_array_declare(edges2);
1030         BLI_array_declare(edges);
1031         int ok = 1;
1032         int i, count;
1033
1034         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
1035         
1036         /*validate that each edge has at most one other tagged edge in the
1037           disk cycle around each of it's vertices*/
1038         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
1039                 for (i=0; i<2; i++) {
1040                         count = BMO_Vert_CountEdgeFlags(bm, i?e->v2:e->v1, EDGE_MARK);
1041                         if (count > 2) {
1042                                 ok = 0;
1043                                 break;
1044                         }
1045                 }
1046
1047                 if (!ok) break;
1048         }
1049
1050         /*we don't have valid edge layouts, return*/
1051         if (!ok)
1052                 return;
1053
1054
1055         /*find connected loops within the input edges*/
1056         count = 0;
1057         while (1) {
1058                 BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
1059                         if (!BMO_TestFlag(bm, e, EDGE_VIS)) {
1060                                 if (BMO_Vert_CountEdgeFlags(bm, e->v1, EDGE_MARK)==1)
1061                                         break;
1062                                 if (BMO_Vert_CountEdgeFlags(bm, e->v2, EDGE_MARK)==1)
1063                                         break;
1064                         }
1065                 }
1066                 
1067                 if (!e) break;
1068                 
1069                 if (!count)
1070                         edges = edges1;
1071                 else if (count==1)
1072                         edges = edges2;
1073                 else break;
1074                 
1075                 i = 0;
1076                 while (e) {
1077                         BMO_SetFlag(bm, e, EDGE_VIS);
1078                         BLI_array_growone(edges);
1079                         edges[i] = e;
1080
1081                         e = edge_next(bm, e);
1082                         i++;
1083                 }
1084
1085                 if (!count) {
1086                         edges1 = edges;
1087                         BLI_array_set_length(edges1, BLI_array_count(edges));
1088                 } else {
1089                         edges2 = edges;
1090                         BLI_array_set_length(edges2, BLI_array_count(edges));
1091                 }
1092
1093                 BLI_array_empty(edges);
1094                 count++;
1095         }
1096
1097 #define EDGECON(e1, e2) (e1->v1 == e2->v1 || e1->v2 == e2->v2 || e1->v1 == e2->v2)
1098
1099         if (edges1 && BLI_array_count(edges1) > 2 && EDGECON(edges1[0], edges1[BLI_array_count(edges1)-1])) {
1100                 if (edges2 && BLI_array_count(edges2) > 2 && EDGECON(edges2[0], edges2[BLI_array_count(edges2)-1])) {
1101                         BLI_array_free(edges1);
1102                         BLI_array_free(edges2);
1103                         return;
1104                 } else {
1105                         edges1 = edges2;
1106                         edges2 = NULL;
1107                 }
1108         }
1109
1110         if (edges2 && BLI_array_count(edges2) > 2 && EDGECON(edges2[0], edges2[BLI_array_count(edges2)-1])) {
1111                 edges2 = NULL;
1112         }
1113
1114         /*two unconnected loops, connect them*/
1115         if (edges1 && edges2) {
1116                 BMVert *v1, *v2, *v3, *v4;
1117
1118                 if (BLI_array_count(edges1)==1) {
1119                         v1 = edges1[0]->v1;
1120                         v2 = edges1[0]->v2;
1121                 } else {
1122                         if (BM_Vert_In_Edge(edges1[1], edges1[0]->v1))
1123                                 v1 = edges1[0]->v2;
1124                         else v1 = edges1[0]->v1;
1125
1126                         i = BLI_array_count(edges1)-1;
1127                         if (BM_Vert_In_Edge(edges1[i-1], edges1[i]->v1))
1128                                 v2 = edges1[i]->v2;
1129                         else v2 = edges1[i]->v1;
1130                 }
1131
1132                 if (BLI_array_count(edges2)==1) {
1133                         v3 = edges2[0]->v1;
1134                         v4 = edges2[0]->v2;
1135                 } else {
1136                         if (BM_Vert_In_Edge(edges2[1], edges2[0]->v1))
1137                                 v3 = edges2[0]->v2;
1138                         else v3 = edges2[0]->v1;
1139
1140                         i = BLI_array_count(edges2)-1;
1141                         if (BM_Vert_In_Edge(edges2[i-1], edges2[i]->v1))
1142                                 v4 = edges2[i]->v2;
1143                         else v4 = edges2[i]->v1;
1144                 }
1145
1146                 if (len_v3v3(v1->co, v3->co) > len_v3v3(v1->co, v4->co)) {
1147                         BMVert *v;
1148                         v = v3;
1149                         v3 = v4;
1150                         v4 = v;
1151                 }
1152
1153                 e = BM_Make_Edge(bm, v1, v3, NULL, 1);
1154                 BMO_SetFlag(bm, e, ELE_NEW);
1155                 e = BM_Make_Edge(bm, v2, v4, NULL, 1);
1156                 BMO_SetFlag(bm, e, ELE_NEW);
1157         } else if (edges1) {
1158                 BMVert *v1, *v2;
1159                 
1160                 if (BLI_array_count(edges1) > 1) {
1161                         if (BM_Vert_In_Edge(edges1[1], edges1[0]->v1))
1162                                 v1 = edges1[0]->v2;
1163                         else v1 = edges1[0]->v1;
1164
1165                         i = BLI_array_count(edges1)-1;
1166                         if (BM_Vert_In_Edge(edges1[i-1], edges1[i]->v1))
1167                                 v2 = edges1[i]->v2;
1168                         else v2 = edges1[i]->v1;
1169
1170                         e = BM_Make_Edge(bm, v1, v2, NULL, 1);
1171                         BMO_SetFlag(bm, e, ELE_NEW);
1172                 }
1173         }
1174         
1175         BMO_Flag_To_Slot(bm, op, "edgeout", ELE_NEW, BM_EDGE);
1176
1177         BLI_array_free(edges1);
1178         BLI_array_free(edges2);
1179
1180 #undef EDGECON
1181 }
1182
1183 /*this is essentially new fkey*/
1184 void bmesh_contextual_create_exec(BMesh *bm, BMOperator *op)
1185 {
1186         BMOperator op2;
1187         BMOIter oiter;
1188         BMIter iter;
1189         BMHeader *h;
1190         BMVert *v, *verts[4];
1191         BMEdge *e;
1192         BMFace *f;
1193         int totv=0, tote=0, totf=0, amount;
1194
1195         /*count number of each element type we were passed*/
1196         BMO_ITER(h, &oiter, bm, op, "geom", BM_VERT|BM_EDGE|BM_FACE) {
1197                 switch (h->type) {
1198                         case BM_VERT: totv++; break;
1199                         case BM_EDGE: tote++; break;
1200                         case BM_FACE: totf++; break;
1201                 }
1202
1203                 BMO_SetFlag(bm, h, ELE_NEW);
1204         }
1205         
1206         /*call edgenet create*/
1207         /*  call edgenet prepare op so additional face creation cases work*/
1208         BMO_InitOpf(bm, &op2, "edgenet_prepare edges=%fe", ELE_NEW);
1209         BMO_Exec_Op(bm, &op2);
1210         BMO_Flag_Buffer(bm, &op2, "edgeout", ELE_NEW, BM_EDGE);
1211         BMO_Finish_Op(bm, &op2);
1212
1213         BMO_InitOpf(bm, &op2, "edgenet_fill edges=%fe", ELE_NEW);
1214         BMO_Exec_Op(bm, &op2);
1215
1216         /*return if edge net create did something*/
1217         if (BMO_CountSlotBuf(bm, &op2, "faceout")) {
1218                 BMO_CopySlot(&op2, op, "faceout", "faceout");
1219                 BMO_Finish_Op(bm, &op2);
1220                 return;
1221         }
1222
1223         BMO_Finish_Op(bm, &op2);
1224         
1225         /*now call dissolve faces*/
1226         BMO_InitOpf(bm, &op2, "dissolvefaces faces=%ff", ELE_NEW);
1227         BMO_Exec_Op(bm, &op2);
1228         
1229         /*if we dissolved anything, then return.*/
1230         if (BMO_CountSlotBuf(bm, &op2, "regionout")) {
1231                 BMO_CopySlot(&op2, op, "regionout", "faceout");
1232                 BMO_Finish_Op(bm, &op2);
1233                 return;
1234         }
1235
1236         BMO_Finish_Op(bm, &op2);
1237
1238         /*now, count how many verts we have*/
1239         amount = 0;
1240         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
1241                 if (BMO_TestFlag(bm, v, ELE_NEW)) {
1242                         verts[amount] = v;
1243                         amount++;
1244
1245                         if (amount > 4) break;
1246                 }
1247         }
1248
1249         if (amount == 2) {
1250                 /*create edge*/
1251                 e = BM_Make_Edge(bm, verts[0], verts[1], NULL, 1);
1252                 BMO_SetFlag(bm, e, ELE_OUT);            
1253         } else if (amount == 3) {
1254                 /*create triangle*/
1255                 BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], NULL, NULL, 1);
1256         } else if (amount == 4) {
1257                 f = NULL;
1258
1259                 /* the order of vertices can be anything, 6 cases to check */
1260                 if( convex(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co) ) {
1261                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], verts[3], NULL, 1);
1262                 }
1263                 else if( convex(verts[0]->co, verts[2]->co, verts[3]->co, verts[1]->co) ) {
1264                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[3], verts[1], NULL, 1);
1265                 }
1266                 else if( convex(verts[0]->co, verts[2]->co, verts[1]->co, verts[3]->co) ) {
1267                         f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[1], verts[3], NULL, 1);
1268                 }
1269                 else if( convex(verts[0]->co, verts[1]->co, verts[3]->co, verts[2]->co) ) {
1270                         f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[3], verts[2], NULL, 1);
1271                 }
1272                 else if( convex(verts[0]->co, verts[3]->co, verts[2]->co, verts[1]->co) ) {
1273                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[2], verts[1], NULL, 1);
1274                 }
1275                 else if( convex(verts[0]->co, verts[3]->co, verts[1]->co, verts[2]->co) ) {
1276                         f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[1], verts[2], NULL, 1);
1277                 }
1278                 else {
1279                         printf("cannot find nice quad from concave set of vertices\n");
1280                 }
1281
1282                 if (f) BMO_SetFlag(bm, f, ELE_OUT);
1283         }
1284 }