doxygen: add newline after \file
[blender.git] / source / blender / bmesh / operators / bmo_connect.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file
18  * \ingroup bmesh
19  *
20  * Connect verts across faces (splits faces).
21  */
22
23 #include "BLI_utildefines.h"
24 #include "BLI_utildefines_stack.h"
25 #include "BLI_alloca.h"
26 #include "BLI_linklist_stack.h"
27
28 #include "bmesh.h"
29
30 #include "intern/bmesh_operators_private.h" /* own include */
31
32 #define VERT_INPUT      1
33
34 #define EDGE_OUT        1
35 /* Edge spans 2 VERT_INPUT's, its a nop,
36  * but include in "edges.out" */
37 #define EDGE_OUT_ADJ    2
38
39 #define FACE_TAG                2
40 #define FACE_EXCLUDE    4
41
42 static int bm_face_connect_verts(BMesh *bm, BMFace *f, const bool check_degenerate)
43 {
44         const unsigned pair_split_max = f->len / 2;
45         BMLoop *(*loops_split)[2] = BLI_array_alloca(loops_split, pair_split_max);
46         STACK_DECLARE(loops_split);
47         BMVert *(*verts_pair)[2] = BLI_array_alloca(verts_pair, pair_split_max);
48         STACK_DECLARE(verts_pair);
49
50         BMLoop *l_tag_prev = NULL, *l_tag_first = NULL;
51         BMLoop *l_iter, *l_first;
52         uint i;
53
54         STACK_INIT(loops_split, pair_split_max);
55         STACK_INIT(verts_pair, pair_split_max);
56
57         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
58         do {
59                 if (BMO_vert_flag_test(bm, l_iter->v, VERT_INPUT) &&
60                     /* ensure this vertex isnt part of a contiguous group */
61                     ((BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT) == 0) ||
62                      (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT) == 0)))
63                 {
64                         if (!l_tag_prev) {
65                                 l_tag_prev = l_tag_first = l_iter;
66                                 continue;
67                         }
68
69                         if (!BM_loop_is_adjacent(l_tag_prev, l_iter)) {
70                                 BMEdge *e;
71                                 e = BM_edge_exists(l_tag_prev->v, l_iter->v);
72                                 if (e == NULL || !BMO_edge_flag_test(bm, e, EDGE_OUT)) {
73                                         BMLoop **l_pair = STACK_PUSH_RET(loops_split);
74                                         l_pair[0] = l_tag_prev;
75                                         l_pair[1] = l_iter;
76                                 }
77                         }
78
79                         l_tag_prev = l_iter;
80                 }
81         } while ((l_iter = l_iter->next) != l_first);
82
83         if (STACK_SIZE(loops_split) == 0) {
84                 return 0;
85         }
86
87         if (!BM_loop_is_adjacent(l_tag_first, l_tag_prev) &&
88             /* ensure we don't add the same pair twice */
89             (((loops_split[0][0] == l_tag_first) &&
90               (loops_split[0][1] == l_tag_prev)) == 0))
91         {
92                 BMLoop **l_pair = STACK_PUSH_RET(loops_split);
93                 l_pair[0] = l_tag_first;
94                 l_pair[1] = l_tag_prev;
95         }
96
97         if (check_degenerate) {
98                 BM_face_splits_check_legal(bm, f, loops_split, STACK_SIZE(loops_split));
99         }
100         else {
101                 BM_face_splits_check_optimal(f, loops_split, STACK_SIZE(loops_split));
102         }
103
104         for (i = 0; i < STACK_SIZE(loops_split); i++) {
105                 BMVert **v_pair;
106                 if (loops_split[i][0] == NULL) {
107                         continue;
108                 }
109
110                 v_pair = STACK_PUSH_RET(verts_pair);
111                 v_pair[0] = loops_split[i][0]->v;
112                 v_pair[1] = loops_split[i][1]->v;
113         }
114
115         for (i = 0; i < STACK_SIZE(verts_pair); i++) {
116                 BMFace *f_new;
117                 BMLoop *l_new;
118                 BMLoop *l_a, *l_b;
119
120                 if ((l_a = BM_face_vert_share_loop(f, verts_pair[i][0])) &&
121                     (l_b = BM_face_vert_share_loop(f, verts_pair[i][1])))
122                 {
123                         f_new = BM_face_split(bm, f, l_a, l_b, &l_new, NULL, false);
124                 }
125                 else {
126                         f_new = NULL;
127                         l_new = NULL;
128                 }
129
130                 f = f_new;
131
132                 if (!l_new || !f_new) {
133                         return -1;
134                 }
135                 // BMO_face_flag_enable(bm, f_new, FACE_NEW);
136                 BMO_edge_flag_enable(bm, l_new->e, EDGE_OUT);
137         }
138
139         return 1;
140 }
141
142
143 void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
144 {
145         BMOIter siter;
146         BMVert *v;
147         BMFace *f;
148         const bool check_degenerate = BMO_slot_bool_get(op->slots_in,  "check_degenerate");
149         BLI_LINKSTACK_DECLARE(faces, BMFace *);
150
151         BLI_LINKSTACK_INIT(faces);
152
153         /* tag so we won't touch ever (typically hidden faces) */
154         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces_exclude", BM_FACE, FACE_EXCLUDE);
155
156         /* add all faces connected to verts */
157         BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
158                 BMIter iter;
159                 BMLoop *l_iter;
160
161                 BMO_vert_flag_enable(bm, v, VERT_INPUT);
162                 BM_ITER_ELEM (l_iter, &iter, v, BM_LOOPS_OF_VERT) {
163                         f = l_iter->f;
164                         if (!BMO_face_flag_test(bm, f, FACE_EXCLUDE)) {
165                                 if (!BMO_face_flag_test(bm, f, FACE_TAG)) {
166                                         BMO_face_flag_enable(bm, f, FACE_TAG);
167                                         if (f->len > 3) {
168                                                 BLI_LINKSTACK_PUSH(faces, f);
169                                         }
170                                 }
171                         }
172
173                         /* flag edges even if these are not newly created
174                          * this way cut-pairs that include co-linear edges will get
175                          * predictable output. */
176                         if (BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT)) {
177                                 BMO_edge_flag_enable(bm, l_iter->prev->e, EDGE_OUT_ADJ);
178                         }
179                         if (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT)) {
180                                 BMO_edge_flag_enable(bm, l_iter->e, EDGE_OUT_ADJ);
181                         }
182                 }
183         }
184
185         /* connect faces */
186         while ((f = BLI_LINKSTACK_POP(faces))) {
187                 if (bm_face_connect_verts(bm, f, check_degenerate) == -1) {
188                         BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
189                 }
190         }
191
192         BLI_LINKSTACK_FREE(faces);
193
194         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT | EDGE_OUT_ADJ);
195 }