correct own incorrect check bmesh edgerin subdivide, also add missing break in orthog...
[blender.git] / source / blender / bmesh / operators / bmo_bridge.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, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_bridge.c
24  *  \ingroup bmesh
25  *
26  * Connect verts across faces (splits faces) and bridge tool.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_math.h"
32 #include "BLI_utildefines.h"
33 #include "BLI_listbase.h"
34
35 #include "bmesh.h"
36
37 #include "intern/bmesh_operators_private.h" /* own include */
38
39 #define EDGE_MARK       4
40 #define EDGE_OUT        8
41 #define FACE_OUT        16
42
43 /* el_a and el_b _must_ be same size */
44 static void bm_bridge_splice_loops(BMesh *bm, LinkData *el_a, LinkData *el_b, const float merge_factor)
45 {
46         BMOperator op_weld;
47         BMOpSlot *slot_targetmap;
48
49         BMO_op_init(bm, &op_weld, 0, "weld_verts");
50
51         slot_targetmap = BMO_slot_get(op_weld.slots_in, "targetmap");
52
53         do {
54                 BMVert *v_a = el_a->data, *v_b = el_b->data;
55                 BM_data_interp_from_verts(bm, v_a, v_b, v_b, merge_factor);
56                 interp_v3_v3v3(v_b->co, v_a->co, v_b->co, merge_factor);
57                 BLI_assert(v_a != v_b);
58                 BMO_slot_map_elem_insert(&op_weld, slot_targetmap, v_a, v_b);
59         } while ((el_b = el_b->next),
60                  (el_a = el_a->next));
61
62         BMO_op_exec(bm, &op_weld);
63         BMO_op_finish(bm, &op_weld);
64 }
65
66 /* get the 2 loops matching 2 verts.
67  * first attempt to get the face corners that use the edge defined by v1 & v2,
68  * if that fails just get any loop thats on the vert (the first one) */
69 static void bm_vert_loop_pair(BMesh *bm, BMVert *v1, BMVert *v2, BMLoop **l1, BMLoop **l2)
70 {
71         BMEdge *e = BM_edge_exists(v1, v2);
72         BMLoop *l = e->l;
73
74         if (l) {
75                 if (l->v == v1) {
76                         *l1 = l;
77                         *l2 = l->next;
78                 }
79                 else {
80                         *l2 = l;
81                         *l1 = l->next;
82                 }
83         }
84         else {
85                 /* fallback to _any_ loop */
86                 *l1 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v1, 0);
87                 *l2 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v2, 0);
88         }
89 }
90
91 /* el_b can have any offset */
92 static float bm_edgeloop_offset_length(LinkData *el_a, LinkData *el_b,
93                                        LinkData *el_b_first, const float len_max)
94 {
95         float len = 0.0f;
96         BLI_assert(el_a->prev == NULL);  /* must be first */
97         do {
98                 len += len_v3v3(((BMVert *)el_a->data)->co, ((BMVert *)el_b->data)->co);
99         } while ((el_b = el_b->next ? el_b->next : el_b_first),
100                  (el_a = el_a->next) && (len < len_max));
101         return len;
102 }
103
104 static void bm_bridge_best_rotation(struct BMEdgeLoopStore *el_store_a, struct BMEdgeLoopStore *el_store_b)
105 {
106         ListBase *lb_a = BM_edgeloop_verts_get(el_store_a);
107         ListBase *lb_b = BM_edgeloop_verts_get(el_store_b);
108         LinkData *el_a = lb_a->first;
109         LinkData *el_b = lb_b->first;
110         LinkData *el_b_first = el_b;
111         LinkData *el_b_best = NULL;
112
113         float len_best = FLT_MAX;
114
115         for (; el_b; el_b = el_b->next) {
116                 const float len = bm_edgeloop_offset_length(el_a, el_b, el_b_first, len_best);
117                 if (len < len_best) {
118                         el_b_best = el_b;
119                         len_best = len;
120                 }
121         }
122
123         if (el_b_best) {
124                 BLI_rotatelist(lb_b, el_b_best);
125         }
126 }
127
128 static void bm_face_edges_tag_out(BMesh *bm, BMFace *f)
129 {
130         BMLoop *l_iter, *l_first;
131         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
132         do {
133                 BMO_elem_flag_enable(bm, l_iter->e, EDGE_OUT);
134         } while ((l_iter = l_iter->next) != l_first);
135 }
136
137 static bool bm_edge_test_cb(BMEdge *e, void *bm_v)
138 {
139         return BMO_elem_flag_test((BMesh *)bm_v, e, EDGE_MARK);
140 }
141
142 static void bridge_loop_pair(BMesh *bm,
143                              struct BMEdgeLoopStore *el_store_a,
144                              struct BMEdgeLoopStore *el_store_b,
145                              const bool use_merge, const float merge_factor)
146 {
147         const float eps = 0.00001f;
148         LinkData *el_a_first, *el_b_first;
149         const bool is_closed = BM_edgeloop_is_closed(el_store_a) && BM_edgeloop_is_closed(el_store_b);
150         int el_store_a_len, el_store_b_len;
151         bool el_store_b_free = false;
152         float el_dir[3];
153         float dot_a, dot_b;
154         const bool use_edgeout = true;
155
156         el_store_a_len = BM_edgeloop_length_get((struct BMEdgeLoopStore *)el_store_a);
157         el_store_b_len = BM_edgeloop_length_get((struct BMEdgeLoopStore *)el_store_b);
158
159         if (el_store_a_len < el_store_b_len) {
160                 SWAP(int, el_store_a_len, el_store_b_len);
161                 SWAP(struct BMEdgeLoopStore *, el_store_a, el_store_b);
162         }
163
164         if (use_merge) {
165                 BLI_assert((el_store_a_len == el_store_b_len));
166         }
167
168         if (el_store_a_len != el_store_b_len) {
169                 BM_mesh_elem_hflag_disable_all(bm, BM_FACE | BM_EDGE, BM_ELEM_TAG, false);
170         }
171
172         sub_v3_v3v3(el_dir, BM_edgeloop_center_get(el_store_a), BM_edgeloop_center_get(el_store_b));
173
174         if (is_closed) {
175                 /* if all loops are closed this will calculate twice for all loops */
176                 BM_edgeloop_calc_normal(bm, el_store_a);
177                 BM_edgeloop_calc_normal(bm, el_store_b);
178         }
179         else {
180                 ListBase *lb_a = BM_edgeloop_verts_get(el_store_a);
181                 ListBase *lb_b = BM_edgeloop_verts_get(el_store_b);
182
183                 /* normalizing isn't strictly needed but without we may get very large values */
184                 float no[3];
185                 float dir_a[3], dir_b[3];
186
187                 sub_v3_v3v3(dir_a,
188                             ((BMVert *)(((LinkData *)lb_a->first)->data))->co,
189                             ((BMVert *)(((LinkData *)lb_a->last)->data))->co);
190                 sub_v3_v3v3(dir_b,
191                             ((BMVert *)(((LinkData *)lb_b->first)->data))->co,
192                             ((BMVert *)(((LinkData *)lb_b->last)->data))->co);
193
194                 /* make the directions point out from the normals, 'no' is used as a temp var */
195                 cross_v3_v3v3(no, dir_a, el_dir); cross_v3_v3v3(dir_a, no, el_dir);
196                 cross_v3_v3v3(no, dir_b, el_dir); cross_v3_v3v3(dir_b, no, el_dir);
197
198                 if (dot_v3v3(dir_a, dir_b) < 0.0f) {
199                         BM_edgeloop_flip(bm, el_store_b);
200                 }
201
202                 normalize_v3_v3(no, el_dir);
203                 BM_edgeloop_calc_normal_aligned(bm, el_store_a, no);
204                 BM_edgeloop_calc_normal_aligned(bm, el_store_b, no);
205         }
206
207         dot_a = dot_v3v3(BM_edgeloop_normal_get(el_store_a), el_dir);
208         dot_b = dot_v3v3(BM_edgeloop_normal_get(el_store_b), el_dir);
209
210         if (UNLIKELY((len_squared_v3(el_dir) < eps) ||
211                      ((fabsf(dot_a) < eps) && (fabsf(dot_b) < eps))))
212         {
213                 /* in this case there is no depth between the two loops,
214                  * eg: 2x 2d circles, one scaled smaller,
215                  * in this case 'el_dir' cant be used, just ensure we have matching flipping. */
216                 if (dot_v3v3(BM_edgeloop_normal_get(el_store_a),
217                              BM_edgeloop_normal_get(el_store_b)) < 0.0f)
218                 {
219                         BM_edgeloop_flip(bm, el_store_b);
220                 }
221         }
222         else if ((dot_a < 0.0f) != (dot_b < 0.0f)) {
223                 BM_edgeloop_flip(bm, el_store_b);
224         }
225
226         /* we only care about flipping if we make faces */
227         if (use_merge == false) {
228                 float no[3];
229
230                 add_v3_v3v3(no, BM_edgeloop_normal_get(el_store_a), BM_edgeloop_normal_get(el_store_b));
231
232                 if (dot_v3v3(no, el_dir) < 0.0f) {
233                         BM_edgeloop_flip(bm, el_store_a);
234                         BM_edgeloop_flip(bm, el_store_b);
235                 }
236
237                 /* vote on winding (so new face winding is based on existing connected faces) */
238                 if (bm->totface) {
239                         struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b};
240                         int i;
241                         int winding_votes = 0;
242                         int winding_dir = 1;
243                         for (i = 0; i < 2; i++, winding_dir = -winding_dir) {
244                                 LinkData *el;
245                                 for (el = BM_edgeloop_verts_get(estore_pair[i])->first; el; el = el->next) {
246                                         LinkData *el_next = BM_EDGELINK_NEXT(estore_pair[i], el);
247                                         if (el_next) {
248                                                 BMEdge *e = BM_edge_exists(el->data, el_next->data);
249                                                 if (e && BM_edge_is_boundary(e)) {
250                                                         winding_votes += ((e->l->v == el->data) ? winding_dir : -winding_dir);
251                                                 }
252                                         }
253                                 }
254                         }
255
256                         if (winding_votes < 0) {
257                                 BM_edgeloop_flip(bm, el_store_a);
258                                 BM_edgeloop_flip(bm, el_store_b);
259                         }
260                 }
261         }
262
263         if (el_store_a_len > el_store_b_len) {
264                 el_store_b = BM_edgeloop_copy(el_store_b);
265                 BM_edgeloop_expand(bm, el_store_b, el_store_a_len);
266                 el_store_b_free = true;
267         }
268
269         if (is_closed) {
270                 bm_bridge_best_rotation(el_store_a, el_store_b);
271         }
272
273         /* Assign after flipping is finalized */
274         el_a_first = BM_edgeloop_verts_get(el_store_a)->first;
275         el_b_first = BM_edgeloop_verts_get(el_store_b)->first;
276
277
278         if (use_merge) {
279                 bm_bridge_splice_loops(bm, el_a_first, el_b_first, merge_factor);
280         }
281         else {
282                 LinkData *el_a = el_a_first;
283                 LinkData *el_b = el_b_first;
284
285                 LinkData *el_a_next;
286                 LinkData *el_b_next;
287
288
289                 while (true) {
290                         BMFace *f, *f_example;
291                         BMLoop *l_iter;
292                         BMVert *v_a, *v_b, *v_a_next, *v_b_next;
293
294                         BMLoop *l_a = NULL;
295                         BMLoop *l_b = NULL;
296                         BMLoop *l_a_next = NULL;
297                         BMLoop *l_b_next = NULL;
298
299                         if (is_closed) {
300                                 el_a_next = BM_EDGELINK_NEXT(el_store_a, el_a);
301                                 el_b_next = BM_EDGELINK_NEXT(el_store_b, el_b);
302                         }
303                         else {
304                                 el_a_next = el_a->next;
305                                 el_b_next = el_b->next;
306                                 if (ELEM(NULL, el_a_next, el_b_next)) {
307                                         break;
308                                 }
309                         }
310
311                         v_a = el_a->data;
312                         v_b = el_b->data;
313                         v_a_next = el_a_next->data;
314                         v_b_next = el_b_next->data;
315
316                         /* get loop data - before making the face */
317                         if (v_b != v_b_next) {
318                                 bm_vert_loop_pair(bm, v_a, v_a_next, &l_a, &l_a_next);
319                                 bm_vert_loop_pair(bm, v_b, v_b_next, &l_b, &l_b_next);
320                         }
321                         else {
322                                 /* lazy, could be more clever here */
323                                 bm_vert_loop_pair(bm, v_a, v_a_next, &l_a, &l_a_next);
324                                 l_b = l_b_next = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v_b, 0);
325                         }
326
327                         if (l_a && l_a_next == NULL) l_a_next = l_a;
328                         if (l_a_next && l_a == NULL) l_a = l_a_next;
329                         if (l_b && l_b_next == NULL) l_b_next = l_b;
330                         if (l_b_next && l_b == NULL) l_b = l_b_next;
331                         f_example = l_a ? l_a->f : (l_b ? l_b->f : NULL);
332
333                         if (v_b != v_b_next) {
334                                 BMVert *v_arr[4] = {v_a, v_b, v_b_next, v_a_next};
335                                 if (BM_face_exists(v_arr, 4, &f) == false) {
336                                         /* copy if loop data if its is missing on one ring */
337                                         f = BM_face_create_ngon_verts(bm, v_arr, 4, 0, false, true);
338
339                                         l_iter = BM_FACE_FIRST_LOOP(f);
340                                         if (l_b)      BM_elem_attrs_copy(bm, bm, l_b,      l_iter); l_iter = l_iter->next;
341                                         if (l_b_next) BM_elem_attrs_copy(bm, bm, l_b_next, l_iter); l_iter = l_iter->next;
342                                         if (l_a_next) BM_elem_attrs_copy(bm, bm, l_a_next, l_iter); l_iter = l_iter->next;
343                                         if (l_a)      BM_elem_attrs_copy(bm, bm, l_a,      l_iter);
344                                 }
345                         }
346                         else {
347                                 BMVert *v_arr[3] = {v_a, v_b, v_a_next};
348                                 if (BM_face_exists(v_arr, 3, &f) == false) {
349                                         /* fan-fill a triangle */
350                                         f = BM_face_create_ngon_verts(bm, v_arr, 3, 0, false, true);
351
352                                         l_iter = BM_FACE_FIRST_LOOP(f);
353                                         if (l_b)      BM_elem_attrs_copy(bm, bm, l_b,      l_iter); l_iter = l_iter->next;
354                                         if (l_a_next) BM_elem_attrs_copy(bm, bm, l_a_next, l_iter); l_iter = l_iter->next;
355                                         if (l_a)      BM_elem_attrs_copy(bm, bm, l_a,      l_iter);
356                                 }
357                         }
358
359                         if (f_example && (f_example != f)) {
360                                 BM_elem_attrs_copy(bm, bm, f_example, f);
361                         }
362                         BMO_elem_flag_enable(bm, f, FACE_OUT);
363                         BM_elem_flag_enable(f, BM_ELEM_TAG);
364
365                         /* tag all edges of the face, untag the loop edges after */
366                         if (use_edgeout) {
367                                 bm_face_edges_tag_out(bm, f);
368                         }
369
370                         if (el_a_next == el_a_first) {
371                                 break;
372                         }
373
374                         el_a = el_a_next;
375                         el_b = el_b_next;
376                 }
377         }
378
379         if (el_store_a_len != el_store_b_len) {
380                 struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b};
381                 int i;
382
383                 BMOperator op_sub;
384                 /* when we have to bridge between different sized edge-loops,
385                  * be clever and post-process for best results */
386
387
388                 /* triangulate inline */
389                 BMO_op_initf(bm, &op_sub, 0,
390                              "triangulate faces=%hf",
391                              BM_ELEM_TAG, true);
392                 /* calc normals for input faces before executing */
393                 {
394                         BMOIter siter;
395                         BMFace *f;
396                         BMO_ITER (f, &siter, op_sub.slots_in, "faces", BM_FACE) {
397                                 BM_face_normal_update(f);
398                         }
399                 }
400                 BMO_op_exec(bm, &op_sub);
401                 BMO_slot_buffer_flag_enable(bm, op_sub.slots_out, "faces.out", BM_FACE, FACE_OUT);
402                 BMO_slot_buffer_hflag_enable(bm, op_sub.slots_out, "faces.out", BM_FACE, BM_ELEM_TAG, false);
403                 BMO_op_finish(bm, &op_sub);
404
405
406                 /* tag verts on each side so we can restrict rotation of edges to verts on the same side */
407                 for (i = 0; i < 2; i++) {
408                         LinkData *el;
409                         for (el = BM_edgeloop_verts_get(estore_pair[i])->first; el; el = el->next) {
410                                 BM_elem_flag_set((BMVert *)el->data, BM_ELEM_TAG, i);
411                         }
412                 }
413
414
415                 BMO_op_initf(bm, &op_sub, 0,
416                              "beautify_fill faces=%hf edges=ae use_restrict_tag=%b",
417                              BM_ELEM_TAG, true);
418
419                 if (use_edgeout) {
420                         BMOIter siter;
421                         BMFace *f;
422                         BMO_ITER (f, &siter, op_sub.slots_in, "faces", BM_FACE) {
423                                 BMO_elem_flag_enable(bm, f, FACE_OUT);
424                                 bm_face_edges_tag_out(bm, f);
425                         }
426                 }
427
428                 BMO_op_exec(bm, &op_sub);
429                 /* there may also be tagged faces that didnt rotate, mark input */
430
431                 if (use_edgeout) {
432                         BMOIter siter;
433                         BMFace *f;
434                         BMO_ITER (f, &siter, op_sub.slots_out, "geom.out", BM_FACE) {
435                                 BMO_elem_flag_enable(bm, f, FACE_OUT);
436                                 bm_face_edges_tag_out(bm, f);
437                         }
438                 }
439                 else {
440                         BMO_slot_buffer_flag_enable(bm, op_sub.slots_out, "geom.out", BM_FACE, FACE_OUT);
441                 }
442
443                 BMO_op_finish(bm, &op_sub);
444         }
445
446         if (use_edgeout && use_merge == false) {
447                 /* we've enabled all face edges above, now disable all loop edges */
448                 struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b};
449                 int i;
450                 for (i = 0; i < 2; i++) {
451                         LinkData *el;
452                         for (el = BM_edgeloop_verts_get(estore_pair[i])->first; el; el = el->next) {
453                                 LinkData *el_next = BM_EDGELINK_NEXT(estore_pair[i], el);
454                                 if (el_next) {
455                                         if (el->data != el_next->data) {
456                                                 BMEdge *e = BM_edge_exists(el->data, el_next->data);
457                                                 BMO_elem_flag_disable(bm, e, EDGE_OUT);
458                                         }
459                                 }
460                         }
461                 }
462         }
463
464         if (el_store_b_free) {
465                 BM_edgeloop_free(el_store_b);
466         }
467 }
468
469 void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op)
470 {
471         ListBase eloops = {NULL};
472         LinkData *el_store;
473
474         /* merge-bridge support */
475         const bool  use_pairs    = BMO_slot_bool_get(op->slots_in,  "use_pairs");
476         const bool  use_merge    = BMO_slot_bool_get(op->slots_in,  "use_merge");
477         const float merge_factor = BMO_slot_float_get(op->slots_in, "merge_factor");
478         const bool  use_cyclic   = BMO_slot_bool_get(op->slots_in,  "use_cyclic") && (use_merge == false);
479         int count;
480         bool change = false;
481
482         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
483
484         count = BM_mesh_edgeloops_find(bm, &eloops, bm_edge_test_cb, bm);
485
486         BM_mesh_edgeloops_calc_center(bm, &eloops);
487
488         if (count < 2) {
489                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
490                                 "Select at least two edge loops");
491                 goto cleanup;
492         }
493
494         if (use_pairs && (count % 2)) {
495                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
496                                 "Select an even number of loops to bridge pairs");
497                 goto cleanup;
498         }
499
500         if (use_merge) {
501                 bool match = true;
502                 const int eloop_len = BM_edgeloop_length_get(eloops.first);
503                 for (el_store = eloops.first; el_store; el_store = el_store->next) {
504                         if (eloop_len != BM_edgeloop_length_get((struct BMEdgeLoopStore *)el_store)) {
505                                 match = false;
506                                 break;
507                         }
508                 }
509                 if (!match) {
510                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
511                                         "Selected loops must have equal edge counts");
512                         goto cleanup;
513                 }
514         }
515
516         if (count > 2) {
517                 if (use_pairs) {
518                         BM_mesh_edgeloops_calc_normal(bm, &eloops);
519                 }
520                 BM_mesh_edgeloops_calc_order(bm, &eloops, use_pairs);
521         }
522
523         for (el_store = eloops.first; el_store; el_store = el_store->next) {
524                 LinkData *el_store_next = el_store->next;
525
526                 if (el_store_next == NULL) {
527                         if (use_cyclic && (count > 2)) {
528                                 el_store_next = eloops.first;
529                         }
530                         else {
531                                 break;
532                         }
533                 }
534
535                 bridge_loop_pair(bm,
536                                  (struct BMEdgeLoopStore *)el_store,
537                                  (struct BMEdgeLoopStore *)el_store_next,
538                                  use_merge, merge_factor);
539                 if (use_pairs) {
540                         el_store = el_store->next;
541                 }
542                 change = true;
543         }
544
545 cleanup:
546         BM_mesh_edgeloops_free(&eloops);
547
548         if (change) {
549                 if (use_merge == false) {
550                         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
551                         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
552                 }
553         }
554 }