rewrite edgenet fill bmesh operator.
[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
41 #include "intern/bmesh_operators_private.h" /* own include */
42
43 #define EDGE_MARK       1
44 #define EDGE_VIS        2
45
46 #define FACE_NEW        1
47
48 #define ELE_NEW         1
49 #define ELE_ORIG        4
50
51 void bmo_edgenet_fill_exec(BMesh *bm, BMOperator *op)
52 {
53         BMOIter siter;
54         BMFace *f;
55         const short mat_nr        = BMO_slot_int_get(op->slots_in,  "mat_nr");
56         const bool use_smooth     = BMO_slot_bool_get(op->slots_in, "use_smooth");
57
58         if (!bm->totvert || !bm->totedge)
59                 return;
60
61         BMO_slot_buffer_hflag_enable(bm, op->slots_in, "edges", BM_EDGE, BM_ELEM_TAG, false);
62
63         BM_mesh_edgenet(bm, true, FACE_NEW);
64
65         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_NEW);
66
67         BMO_ITER (f, &siter, op->slots_out, "faces.out", BM_FACE) {
68                 f->mat_nr = mat_nr;
69                 if (use_smooth) {
70                         BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
71                 }
72                 /* normals are zero'd */
73                 BM_face_normal_update(f);
74         }
75
76         /* recalc normals,
77          * TODO, could do checks to make normals consistent */
78         {
79                 BMO_op_callf(bm, op->flag,
80                              "recalc_face_normals faces=%S",
81                              op, "faces.out");
82         }
83 }
84
85 static BMEdge *edge_next(BMesh *bm, BMEdge *e)
86 {
87         BMIter iter;
88         BMEdge *e2;
89         int i;
90
91         for (i = 0; i < 2; i++) {
92                 BM_ITER_ELEM (e2, &iter, i ? e->v2 : e->v1, BM_EDGES_OF_VERT) {
93                         if ((BMO_elem_flag_test(bm, e2, EDGE_MARK)) &&
94                             (!BMO_elem_flag_test(bm, e2, EDGE_VIS)) &&
95                             (e2 != e))
96                         {
97                                 return e2;
98                         }
99                 }
100         }
101
102         return NULL;
103 }
104
105 void bmo_edgenet_prepare_exec(BMesh *bm, BMOperator *op)
106 {
107         BMOIter siter;
108         BMEdge *e;
109         BMEdge **edges1 = NULL, **edges2 = NULL, **edges;
110         BLI_array_declare(edges1);
111         BLI_array_declare(edges2);
112         BLI_array_declare(edges);
113         int ok = 1;
114         int i, count;
115
116         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
117
118         /* validate that each edge has at most one other tagged edge in the
119          * disk cycle around each of it's vertices */
120         BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
121                 for (i = 0; i < 2; i++) {
122                         count = BMO_iter_elem_count_flag(bm,  BM_EDGES_OF_VERT, (i ? e->v2 : e->v1), EDGE_MARK, true);
123                         if (count > 2) {
124                                 ok = 0;
125                                 break;
126                         }
127                 }
128
129                 if (!ok) {
130                         break;
131                 }
132         }
133
134         /* we don't have valid edge layouts, retur */
135         if (!ok) {
136                 return;
137         }
138
139         /* find connected loops within the input edge */
140         count = 0;
141         while (1) {
142                 BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
143                         if (!BMO_elem_flag_test(bm, e, EDGE_VIS)) {
144                                 if (BMO_iter_elem_count_flag(bm, BM_EDGES_OF_VERT, e->v1, EDGE_MARK, true) == 1 ||
145                                     BMO_iter_elem_count_flag(bm, BM_EDGES_OF_VERT, e->v2, EDGE_MARK, true) == 1)
146                                 {
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_elem_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_length_set(edges1, BLI_array_count(edges));
179                 }
180                 else {
181                         edges2 = edges;
182                         BLI_array_length_set(edges2, BLI_array_count(edges));
183                 }
184
185                 BLI_array_empty(edges);
186                 count++;
187         }
188
189         if (edges1 && BLI_array_count(edges1) > 2 &&
190             BM_edge_share_vert_check(edges1[0], edges1[BLI_array_count(edges1) - 1]))
191         {
192                 if (edges2 && BLI_array_count(edges2) > 2 &&
193                     BM_edge_share_vert_check(edges2[0], edges2[BLI_array_count(edges2) - 1]))
194                 {
195                         BLI_array_free(edges1);
196                         BLI_array_free(edges2);
197                         return;
198                 }
199                 else {
200                         edges1 = edges2;
201                         edges2 = NULL;
202                 }
203         }
204
205         if (edges2 && BLI_array_count(edges2) > 2 &&
206             BM_edge_share_vert_check(edges2[0], edges2[BLI_array_count(edges2) - 1]))
207         {
208                 edges2 = NULL;
209         }
210
211         /* two unconnected loops, connect the */
212         if (edges1 && edges2) {
213                 BMVert *v1, *v2, *v3, *v4;
214                 float dvec1[3];
215                 float dvec2[3];
216
217                 if (BLI_array_count(edges1) == 1) {
218                         v1 = edges1[0]->v1;
219                         v2 = edges1[0]->v2;
220                 }
221                 else {
222                         v1 = BM_vert_in_edge(edges1[1], edges1[0]->v1) ? edges1[0]->v2 : edges1[0]->v1;
223                         i  = BLI_array_count(edges1) - 1;
224                         v2 = BM_vert_in_edge(edges1[i - 1], edges1[i]->v1) ? edges1[i]->v2 : edges1[i]->v1;
225                 }
226
227                 if (BLI_array_count(edges2) == 1) {
228                         v3 = edges2[0]->v1;
229                         v4 = edges2[0]->v2;
230                 }
231                 else {
232                         v3 = BM_vert_in_edge(edges2[1], edges2[0]->v1) ? edges2[0]->v2 : edges2[0]->v1;
233                         i  = BLI_array_count(edges2) - 1;
234                         v4 = BM_vert_in_edge(edges2[i - 1], edges2[i]->v1) ? edges2[i]->v2 : edges2[i]->v1;
235                 }
236
237                 /* if there is ever bow-tie quads between two edges the problem is here! [#30367] */
238 #if 0
239                 normal_tri_v3(dvec1, v1->co, v2->co, v4->co);
240                 normal_tri_v3(dvec2, v1->co, v4->co, v3->co);
241 #else
242                 {
243                         /* save some CPU cycles and skip the sqrt and 1 subtraction */
244                         float a1[3], a2[3], a3[3];
245                         sub_v3_v3v3(a1, v1->co, v2->co);
246                         sub_v3_v3v3(a2, v1->co, v4->co);
247                         sub_v3_v3v3(a3, v1->co, v3->co);
248                         cross_v3_v3v3(dvec1, a1, a2);
249                         cross_v3_v3v3(dvec2, a2, a3);
250                 }
251 #endif
252                 if (dot_v3v3(dvec1, dvec2) < 0.0f) {
253                         SWAP(BMVert *, v3, v4);
254                 }
255
256                 e = BM_edge_create(bm, v1, v3, NULL, BM_CREATE_NO_DOUBLE);
257                 BMO_elem_flag_enable(bm, e, ELE_NEW);
258                 e = BM_edge_create(bm, v2, v4, NULL, BM_CREATE_NO_DOUBLE);
259                 BMO_elem_flag_enable(bm, e, ELE_NEW);
260         }
261         else if (edges1) {
262                 BMVert *v1, *v2;
263
264                 if (BLI_array_count(edges1) > 1) {
265                         v1 = BM_vert_in_edge(edges1[1], edges1[0]->v1) ? edges1[0]->v2 : edges1[0]->v1;
266                         i  = BLI_array_count(edges1) - 1;
267                         v2 = BM_vert_in_edge(edges1[i - 1], edges1[i]->v1) ? edges1[i]->v2 : edges1[i]->v1;
268                         e  = BM_edge_create(bm, v1, v2, NULL, BM_CREATE_NO_DOUBLE);
269                         BMO_elem_flag_enable(bm, e, ELE_NEW);
270                 }
271         }
272
273         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, ELE_NEW);
274
275         BLI_array_free(edges1);
276         BLI_array_free(edges2);
277 }