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