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 * Edge-Net for filling in open edge-loops.
21 */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_array.h"
26 #include "BLI_math.h"
27
28 #include "bmesh.h"
29 #include "bmesh_tools.h"
30
31 #include "intern/bmesh_operators_private.h" /* own include */
32
33 #define EDGE_MARK 1
34 #define EDGE_VIS 2
35
36 #define ELE_NEW 1
37
bmo_edgenet_fill_exec(BMesh * bm,BMOperator * op)38 void bmo_edgenet_fill_exec(BMesh *bm, BMOperator *op)
39 {
40 BMOperator op_attr;
41 BMOIter siter;
42 BMFace *f;
43 const short mat_nr = BMO_slot_int_get(op->slots_in, "mat_nr");
44 const bool use_smooth = BMO_slot_bool_get(op->slots_in, "use_smooth");
45 // const int sides = BMO_slot_int_get(op->slots_in, "sides");
46
47 if (!bm->totvert || !bm->totedge) {
48 return;
49 }
50
51 BM_mesh_elem_hflag_disable_all(bm, BM_EDGE, BM_ELEM_TAG, false);
52 BMO_slot_buffer_hflag_enable(bm, op->slots_in, "edges", BM_EDGE, BM_ELEM_TAG, false);
53
54 BM_mesh_elem_hflag_disable_all(bm, BM_FACE, BM_ELEM_TAG, false);
55 BM_mesh_edgenet(bm, true, true); /* TODO, sides */
56
57 BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "faces.out", BM_FACE, BM_ELEM_TAG);
58
59 BMO_ITER (f, &siter, op->slots_out, "faces.out", BM_FACE) {
60 f->mat_nr = mat_nr;
61 if (use_smooth) {
62 BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
63 }
64 /* normals are zero'd */
65 BM_face_normal_update(f);
66 }
67
68 /* --- Attribute Fill --- */
69 /* may as well since we have the faces already in a buffer */
70 BMO_op_initf(bm,
71 &op_attr,
72 op->flag,
73 "face_attribute_fill faces=%S use_normals=%b use_data=%b",
74 op,
75 "faces.out",
76 true,
77 true);
78
79 BMO_op_exec(bm, &op_attr);
80
81 /* check if some faces couldn't be touched */
82 if (BMO_slot_buffer_count(op_attr.slots_out, "faces_fail.out")) {
83 BMO_op_callf(bm, op->flag, "recalc_face_normals faces=%S", &op_attr, "faces_fail.out");
84 }
85 BMO_op_finish(bm, &op_attr);
86 }
87
edge_next(BMesh * bm,BMEdge * e)88 static BMEdge *edge_next(BMesh *bm, BMEdge *e)
89 {
90 BMIter iter;
91 BMEdge *e2;
92 int i;
93
94 for (i = 0; i < 2; i++) {
95 BM_ITER_ELEM (e2, &iter, i ? e->v2 : e->v1, BM_EDGES_OF_VERT) {
96 if ((BMO_edge_flag_test(bm, e2, EDGE_MARK)) &&
97 (BMO_edge_flag_test(bm, e2, EDGE_VIS) == false) && (e2 != e)) {
98 return e2;
99 }
100 }
101 }
102
103 return NULL;
104 }
105
bmo_edgenet_prepare_exec(BMesh * bm,BMOperator * op)106 void bmo_edgenet_prepare_exec(BMesh *bm, BMOperator *op)
107 {
108 BMOIter siter;
109 BMEdge *e;
110 BMEdge **edges1 = NULL, **edges2 = NULL, **edges;
111 BLI_array_declare(edges1);
112 BLI_array_declare(edges2);
113 BLI_array_declare(edges);
114 bool ok = true;
115 int i, count;
116
117 BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
118
119 /* validate that each edge has at most one other tagged edge in the
120 * disk cycle around each of its vertices */
121 BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
122 for (i = 0; i < 2; i++) {
123 count = BMO_iter_elem_count_flag(bm, BM_EDGES_OF_VERT, (i ? e->v2 : e->v1), EDGE_MARK, true);
124 if (count > 2) {
125 ok = 0;
126 break;
127 }
128 }
129
130 if (!ok) {
131 break;
132 }
133 }
134
135 /* we don't have valid edge layouts, return */
136 if (!ok) {
137 return;
138 }
139
140 /* find connected loops within the input edge */
141 count = 0;
142 while (1) {
143 BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
144 if (!BMO_edge_flag_test(bm, e, EDGE_VIS)) {
145 if (BMO_iter_elem_count_flag(bm, BM_EDGES_OF_VERT, e->v1, EDGE_MARK, true) == 1 ||
146 BMO_iter_elem_count_flag(bm, BM_EDGES_OF_VERT, e->v2, EDGE_MARK, true) == 1) {
147 break;
148 }
149 }
150 }
151
152 if (!e) {
153 break;
154 }
155
156 if (!count) {
157 edges = edges1;
158 }
159 else if (count == 1) {
160 edges = edges2;
161 }
162 else {
163 break;
164 }
165
166 i = 0;
167 while (e) {
168 BMO_edge_flag_enable(bm, e, EDGE_VIS);
169 BLI_array_grow_one(edges);
170 edges[i] = e;
171
172 e = edge_next(bm, e);
173 i++;
174 }
175
176 if (!count) {
177 edges1 = edges;
178 BLI_array_len_set(edges1, BLI_array_len(edges));
179 }
180 else {
181 edges2 = edges;
182 BLI_array_len_set(edges2, BLI_array_len(edges));
183 }
184
185 BLI_array_clear(edges);
186 count++;
187 }
188
189 if (edges1 && BLI_array_len(edges1) > 2 &&
190 BM_edge_share_vert_check(edges1[0], edges1[BLI_array_len(edges1) - 1])) {
191 if (edges2 && BLI_array_len(edges2) > 2 &&
192 BM_edge_share_vert_check(edges2[0], edges2[BLI_array_len(edges2) - 1])) {
193 BLI_array_free(edges1);
194 BLI_array_free(edges2);
195 return;
196 }
197 edges1 = edges2;
198 edges2 = NULL;
199 }
200
201 if (edges2 && BLI_array_len(edges2) > 2 &&
202 BM_edge_share_vert_check(edges2[0], edges2[BLI_array_len(edges2) - 1])) {
203 edges2 = NULL;
204 }
205
206 /* two unconnected loops, connect the */
207 if (edges1 && edges2) {
208 BMVert *v1, *v2, *v3, *v4;
209 float dvec1[3];
210 float dvec2[3];
211
212 if (BLI_array_len(edges1) == 1) {
213 v1 = edges1[0]->v1;
214 v2 = edges1[0]->v2;
215 }
216 else {
217 v1 = BM_vert_in_edge(edges1[1], edges1[0]->v1) ? edges1[0]->v2 : edges1[0]->v1;
218 i = BLI_array_len(edges1) - 1;
219 v2 = BM_vert_in_edge(edges1[i - 1], edges1[i]->v1) ? edges1[i]->v2 : edges1[i]->v1;
220 }
221
222 if (BLI_array_len(edges2) == 1) {
223 v3 = edges2[0]->v1;
224 v4 = edges2[0]->v2;
225 }
226 else {
227 v3 = BM_vert_in_edge(edges2[1], edges2[0]->v1) ? edges2[0]->v2 : edges2[0]->v1;
228 i = BLI_array_len(edges2) - 1;
229 v4 = BM_vert_in_edge(edges2[i - 1], edges2[i]->v1) ? edges2[i]->v2 : edges2[i]->v1;
230 }
231
232 /* if there is ever bow-tie quads between two edges the problem is here! T30367. */
233 #if 0
234 normal_tri_v3(dvec1, v1->co, v2->co, v4->co);
235 normal_tri_v3(dvec2, v1->co, v4->co, v3->co);
236 #else
237 {
238 /* save some CPU cycles and skip the sqrt and 1 subtraction */
239 float a1[3], a2[3], a3[3];
240 sub_v3_v3v3(a1, v1->co, v2->co);
241 sub_v3_v3v3(a2, v1->co, v4->co);
242 sub_v3_v3v3(a3, v1->co, v3->co);
243 cross_v3_v3v3(dvec1, a1, a2);
244 cross_v3_v3v3(dvec2, a2, a3);
245 }
246 #endif
247 if (dot_v3v3(dvec1, dvec2) < 0.0f) {
248 SWAP(BMVert *, v3, v4);
249 }
250
251 e = BM_edge_create(bm, v1, v3, NULL, BM_CREATE_NO_DOUBLE);
252 BMO_edge_flag_enable(bm, e, ELE_NEW);
253 e = BM_edge_create(bm, v2, v4, NULL, BM_CREATE_NO_DOUBLE);
254 BMO_edge_flag_enable(bm, e, ELE_NEW);
255 }
256 else if (edges1) {
257 BMVert *v1, *v2;
258
259 if (BLI_array_len(edges1) > 1) {
260 v1 = BM_vert_in_edge(edges1[1], edges1[0]->v1) ? edges1[0]->v2 : edges1[0]->v1;
261 i = BLI_array_len(edges1) - 1;
262 v2 = BM_vert_in_edge(edges1[i - 1], edges1[i]->v1) ? edges1[i]->v2 : edges1[i]->v1;
263 e = BM_edge_create(bm, v1, v2, NULL, BM_CREATE_NO_DOUBLE);
264 BMO_edge_flag_enable(bm, e, ELE_NEW);
265 }
266 }
267
268 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, ELE_NEW);
269
270 BLI_array_free(edges1);
271 BLI_array_free(edges2);
272 }
273