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