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