9dfbf951fc0db5c98ba273520816a0501223326d
[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_first(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, const int twist_offset)
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                 /* add twist */
273                 if (twist_offset != 0) {
274                         const int len_b = BM_edgeloop_length_get(el_store_b);
275                         ListBase *lb_b = BM_edgeloop_verts_get(el_store_b);
276                         LinkData *el_b = BLI_rfindlink(lb_b, mod_i(twist_offset, len_b));
277                         BLI_rotatelist_first(lb_b, el_b);
278                 }
279         }
280
281         /* Assign after flipping is finalized */
282         el_a_first = BM_edgeloop_verts_get(el_store_a)->first;
283         el_b_first = BM_edgeloop_verts_get(el_store_b)->first;
284
285
286         if (use_merge) {
287                 bm_bridge_splice_loops(bm, el_a_first, el_b_first, merge_factor);
288         }
289         else {
290                 LinkData *el_a = el_a_first;
291                 LinkData *el_b = el_b_first;
292
293                 LinkData *el_a_next;
294                 LinkData *el_b_next;
295
296
297                 while (true) {
298                         BMFace *f, *f_example;
299                         BMLoop *l_iter;
300                         BMVert *v_a, *v_b, *v_a_next, *v_b_next;
301
302                         BMLoop *l_a = NULL;
303                         BMLoop *l_b = NULL;
304                         BMLoop *l_a_next = NULL;
305                         BMLoop *l_b_next = NULL;
306
307                         if (is_closed) {
308                                 el_a_next = BM_EDGELINK_NEXT(el_store_a, el_a);
309                                 el_b_next = BM_EDGELINK_NEXT(el_store_b, el_b);
310                         }
311                         else {
312                                 el_a_next = el_a->next;
313                                 el_b_next = el_b->next;
314                                 if (ELEM(NULL, el_a_next, el_b_next)) {
315                                         break;
316                                 }
317                         }
318
319                         v_a = el_a->data;
320                         v_b = el_b->data;
321                         v_a_next = el_a_next->data;
322                         v_b_next = el_b_next->data;
323
324                         /* get loop data - before making the face */
325                         if (v_b != v_b_next) {
326                                 bm_vert_loop_pair(bm, v_a, v_a_next, &l_a, &l_a_next);
327                                 bm_vert_loop_pair(bm, v_b, v_b_next, &l_b, &l_b_next);
328                         }
329                         else {
330                                 /* lazy, could be more clever here */
331                                 bm_vert_loop_pair(bm, v_a, v_a_next, &l_a, &l_a_next);
332                                 l_b = l_b_next = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v_b, 0);
333                         }
334
335                         if (l_a && l_a_next == NULL) l_a_next = l_a;
336                         if (l_a_next && l_a == NULL) l_a = l_a_next;
337                         if (l_b && l_b_next == NULL) l_b_next = l_b;
338                         if (l_b_next && l_b == NULL) l_b = l_b_next;
339                         f_example = l_a ? l_a->f : (l_b ? l_b->f : NULL);
340
341                         if (v_b != v_b_next) {
342                                 BMVert *v_arr[4] = {v_a, v_b, v_b_next, v_a_next};
343                                 if (BM_face_exists(v_arr, 4, &f) == false) {
344                                         /* copy if loop data if its is missing on one ring */
345                                         f = BM_face_create_verts(bm, v_arr, 4, NULL, BM_CREATE_NOP, true);
346
347                                         l_iter = BM_FACE_FIRST_LOOP(f);
348                                         if (l_b)      BM_elem_attrs_copy(bm, bm, l_b,      l_iter); l_iter = l_iter->next;
349                                         if (l_b_next) BM_elem_attrs_copy(bm, bm, l_b_next, l_iter); l_iter = l_iter->next;
350                                         if (l_a_next) BM_elem_attrs_copy(bm, bm, l_a_next, l_iter); l_iter = l_iter->next;
351                                         if (l_a)      BM_elem_attrs_copy(bm, bm, l_a,      l_iter);
352                                 }
353                         }
354                         else {
355                                 BMVert *v_arr[3] = {v_a, v_b, v_a_next};
356                                 if (BM_face_exists(v_arr, 3, &f) == false) {
357                                         /* fan-fill a triangle */
358                                         f = BM_face_create_verts(bm, v_arr, 3, NULL, BM_CREATE_NOP, true);
359
360                                         l_iter = BM_FACE_FIRST_LOOP(f);
361                                         if (l_b)      BM_elem_attrs_copy(bm, bm, l_b,      l_iter); l_iter = l_iter->next;
362                                         if (l_a_next) BM_elem_attrs_copy(bm, bm, l_a_next, l_iter); l_iter = l_iter->next;
363                                         if (l_a)      BM_elem_attrs_copy(bm, bm, l_a,      l_iter);
364                                 }
365                         }
366
367                         if (f_example && (f_example != f)) {
368                                 BM_elem_attrs_copy(bm, bm, f_example, f);
369                         }
370                         BMO_elem_flag_enable(bm, f, FACE_OUT);
371                         BM_elem_flag_enable(f, BM_ELEM_TAG);
372
373                         /* tag all edges of the face, untag the loop edges after */
374                         if (use_edgeout) {
375                                 bm_face_edges_tag_out(bm, f);
376                         }
377
378                         if (el_a_next == el_a_first) {
379                                 break;
380                         }
381
382                         el_a = el_a_next;
383                         el_b = el_b_next;
384                 }
385         }
386
387         if (el_store_a_len != el_store_b_len) {
388                 struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b};
389                 int i;
390
391                 BMOperator op_sub;
392                 /* when we have to bridge between different sized edge-loops,
393                  * be clever and post-process for best results */
394
395
396                 /* triangulate inline */
397                 BMO_op_initf(bm, &op_sub, 0,
398                              "triangulate faces=%hf",
399                              BM_ELEM_TAG, true);
400                 /* calc normals for input faces before executing */
401                 {
402                         BMOIter siter;
403                         BMFace *f;
404                         BMO_ITER (f, &siter, op_sub.slots_in, "faces", BM_FACE) {
405                                 BM_face_normal_update(f);
406                         }
407                 }
408                 BMO_op_exec(bm, &op_sub);
409                 BMO_slot_buffer_flag_enable(bm, op_sub.slots_out, "faces.out", BM_FACE, FACE_OUT);
410                 BMO_slot_buffer_hflag_enable(bm, op_sub.slots_out, "faces.out", BM_FACE, BM_ELEM_TAG, false);
411                 BMO_op_finish(bm, &op_sub);
412
413
414                 /* tag verts on each side so we can restrict rotation of edges to verts on the same side */
415                 for (i = 0; i < 2; i++) {
416                         LinkData *el;
417                         for (el = BM_edgeloop_verts_get(estore_pair[i])->first; el; el = el->next) {
418                                 BM_elem_flag_set((BMVert *)el->data, BM_ELEM_TAG, i);
419                         }
420                 }
421
422
423                 BMO_op_initf(bm, &op_sub, 0,
424                              "beautify_fill faces=%hf edges=ae use_restrict_tag=%b method=%i",
425                              BM_ELEM_TAG, true, 1);
426
427                 if (use_edgeout) {
428                         BMOIter siter;
429                         BMFace *f;
430                         BMO_ITER (f, &siter, op_sub.slots_in, "faces", BM_FACE) {
431                                 BMO_elem_flag_enable(bm, f, FACE_OUT);
432                                 bm_face_edges_tag_out(bm, f);
433                         }
434                 }
435
436                 BMO_op_exec(bm, &op_sub);
437                 /* there may also be tagged faces that didnt rotate, mark input */
438
439                 if (use_edgeout) {
440                         BMOIter siter;
441                         BMFace *f;
442                         BMO_ITER (f, &siter, op_sub.slots_out, "geom.out", BM_FACE) {
443                                 BMO_elem_flag_enable(bm, f, FACE_OUT);
444                                 bm_face_edges_tag_out(bm, f);
445                         }
446                 }
447                 else {
448                         BMO_slot_buffer_flag_enable(bm, op_sub.slots_out, "geom.out", BM_FACE, FACE_OUT);
449                 }
450
451                 BMO_op_finish(bm, &op_sub);
452         }
453
454         if (use_edgeout && use_merge == false) {
455                 /* we've enabled all face edges above, now disable all loop edges */
456                 struct BMEdgeLoopStore *estore_pair[2] = {el_store_a, el_store_b};
457                 int i;
458                 for (i = 0; i < 2; i++) {
459                         LinkData *el;
460                         for (el = BM_edgeloop_verts_get(estore_pair[i])->first; el; el = el->next) {
461                                 LinkData *el_next = BM_EDGELINK_NEXT(estore_pair[i], el);
462                                 if (el_next) {
463                                         if (el->data != el_next->data) {
464                                                 BMEdge *e = BM_edge_exists(el->data, el_next->data);
465                                                 BMO_elem_flag_disable(bm, e, EDGE_OUT);
466                                         }
467                                 }
468                         }
469                 }
470         }
471
472         if (el_store_b_free) {
473                 BM_edgeloop_free(el_store_b);
474         }
475 }
476
477 void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op)
478 {
479         ListBase eloops = {NULL};
480         LinkData *el_store;
481
482         /* merge-bridge support */
483         const bool  use_pairs    = BMO_slot_bool_get(op->slots_in,  "use_pairs");
484         const bool  use_merge    = BMO_slot_bool_get(op->slots_in,  "use_merge");
485         const float merge_factor = BMO_slot_float_get(op->slots_in, "merge_factor");
486         const bool  use_cyclic   = BMO_slot_bool_get(op->slots_in,  "use_cyclic") && (use_merge == false);
487         const int   twist_offset = BMO_slot_int_get(op->slots_in,   "twist_offset");
488         int count;
489         bool change = false;
490
491         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
492
493         count = BM_mesh_edgeloops_find(bm, &eloops, bm_edge_test_cb, bm);
494
495         BM_mesh_edgeloops_calc_center(bm, &eloops);
496
497         if (count < 2) {
498                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
499                                 "Select at least two edge loops");
500                 goto cleanup;
501         }
502
503         if (use_pairs && (count % 2)) {
504                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
505                                 "Select an even number of loops to bridge pairs");
506                 goto cleanup;
507         }
508
509         if (use_merge) {
510                 bool match = true;
511                 const int eloop_len = BM_edgeloop_length_get(eloops.first);
512                 for (el_store = eloops.first; el_store; el_store = el_store->next) {
513                         if (eloop_len != BM_edgeloop_length_get((struct BMEdgeLoopStore *)el_store)) {
514                                 match = false;
515                                 break;
516                         }
517                 }
518                 if (!match) {
519                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
520                                         "Selected loops must have equal edge counts");
521                         goto cleanup;
522                 }
523         }
524
525         if (count > 2) {
526                 if (use_pairs) {
527                         BM_mesh_edgeloops_calc_normal(bm, &eloops);
528                 }
529                 BM_mesh_edgeloops_calc_order(bm, &eloops, use_pairs);
530         }
531
532         for (el_store = eloops.first; el_store; el_store = el_store->next) {
533                 LinkData *el_store_next = el_store->next;
534
535                 if (el_store_next == NULL) {
536                         if (use_cyclic && (count > 2)) {
537                                 el_store_next = eloops.first;
538                         }
539                         else {
540                                 break;
541                         }
542                 }
543
544                 bridge_loop_pair(bm,
545                                  (struct BMEdgeLoopStore *)el_store,
546                                  (struct BMEdgeLoopStore *)el_store_next,
547                                  use_merge, merge_factor, twist_offset);
548                 if (use_pairs) {
549                         el_store = el_store->next;
550                 }
551                 change = true;
552         }
553
554 cleanup:
555         BM_mesh_edgeloops_free(&eloops);
556
557         if (change) {
558                 if (use_merge == false) {
559                         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
560                         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
561                 }
562         }
563 }