rewrite edgenet fill bmesh operator.
[blender.git] / source / blender / bmesh / tools / bmesh_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): Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/tools/bmesh_edgenet.c
24  *  \ingroup bmesh
25  *
26  * Edgenet Fill.
27  *
28  */
29
30 #include <limits.h>
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_utildefines.h"
35 #include "BLI_alloca.h"
36 #include "BLI_mempool.h"
37 #include "BLI_linklist.h"
38
39 #include "bmesh.h"
40
41 #ifdef __GNUC__
42 #  pragma GCC diagnostic error "-Wsign-conversion"
43 #  if (__GNUC__ * 100 + __GNUC_MINOR__) >= 406  /* gcc4.6+ only */
44 #    pragma GCC diagnostic error "-Wsign-compare"
45 #    pragma GCC diagnostic error "-Wconversion"
46 #  endif
47 #endif
48
49 /* Data for one end of an edge involved in a bevel */
50 typedef struct VertNetInfo {
51         BMVert *prev;               /* previous vertex */
52         int pass;                   /* path scanning pass value, for internal calculation */
53         int face;                   /* face index connected to the edge between this and the previous vert */
54         int flag;                   /* flag */
55 } VertNetInfo;
56
57 enum {
58         VNINFO_FLAG_IS_MIXFACE = (1 << 0),
59 };
60
61 /**
62  * Check if this edge can be used in a path.
63  */
64 static bool bm_edge_step_ok(BMEdge *e)
65 {
66         return BM_elem_flag_test(e, BM_ELEM_TAG) && ((e->l == NULL) || (e->l->radial_next == e->l));
67 }
68
69 static int bm_edge_face(BMEdge *e)
70 {
71         return e->l ? BM_elem_index_get(e->l->f) : -1;
72 }
73
74 /**
75  * Get the next available edge we can use to attempt tp calculate a path from.
76  */
77 static BMEdge *bm_edgenet_edge_get_next(
78         BMesh *bm,
79         LinkNode **edge_queue, BLI_mempool *edge_queue_pool)
80 {
81         BMEdge *e;
82         BMIter iter;
83
84         while (*edge_queue) {
85                 e = BLI_linklist_pop_pool(edge_queue, edge_queue_pool);
86                 if (bm_edge_step_ok(e)) {
87                         return e;
88                 }
89         }
90
91         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
92                 if (bm_edge_step_ok(e)) {
93                         return e;
94                 }
95         }
96
97         return NULL;
98 }
99
100
101 /**
102  * Edge loops are built up using links to the 'prev' member.
103  * with each side of the loop having its own pass (negated from the other).
104  *
105  * This function returns half a loop, the caller needs to run twice to get both sides.
106  */
107 static unsigned int bm_edgenet_path_from_pass(
108         BMVert *v, LinkNode **v_ls,
109         VertNetInfo *vnet_info, BLI_mempool *path_pool)
110 {
111         VertNetInfo *vn = &vnet_info[BM_elem_index_get(v)];
112         const int pass = vn->pass;
113         unsigned int v_ls_tot = 0;
114
115         do {
116                 BLI_linklist_prepend_pool(v_ls, v, path_pool);
117                 v_ls_tot += 1;
118                 v = vn->prev;
119                 vn = &vnet_info[BM_elem_index_get(v)];
120         } while ((vn->pass == pass));
121
122         return v_ls_tot;
123 }
124
125 /**
126  * Specialized wrapper for #BM_face_exists_overlap_subset
127  * that gets the verts from a path before we allocate it in the correct order.
128  */
129 static bool bm_edgenet_path_check_overlap(
130         BMVert *v1, BMVert *v2,
131         VertNetInfo *vnet_info)
132 {
133         /* vert order doesn't matter */
134         unsigned int v_ls_tot = 0;
135         LinkNode *v_ls;
136         BMVert *v_pair[2] = {v1, v2};
137         unsigned int i;
138
139         for (i = 0; i < 2; i++) {
140                 BMVert *v = v_pair[i];
141                 VertNetInfo *vn = &vnet_info[BM_elem_index_get(v)];
142                 const int pass = vn->pass;
143                 do {
144                         BLI_linklist_prepend_alloca(&v_ls, v);
145                         v_ls_tot += 1;
146                         v = vn->prev;
147                         vn = &vnet_info[BM_elem_index_get(v)];
148                 } while ((vn->pass == pass));
149         }
150
151         if (v_ls_tot) {
152                 BMVert **vert_arr = BLI_array_alloca(vert_arr, v_ls_tot);
153                 LinkNode *v_lnk;
154                 for (i = 0, v_lnk = v_ls; i < v_ls_tot; v_lnk = v_lnk->next, i++) {
155                         vert_arr[i] = v_lnk->link;
156                 }
157
158                 return BM_face_exists_overlap_subset(vert_arr, (int)v_ls_tot);
159         }
160         else {
161                 return false;
162         }
163 }
164
165 /**
166  * Create a face from the path.
167  */
168 static BMFace *bm_edgenet_face_from_path(
169         BMesh *bm, LinkNode *path, const unsigned int path_len)
170 {
171         BMFace *f;
172         LinkNode *v_lnk;
173         unsigned int i;
174         unsigned int i_prev;
175
176         BMVert **vert_arr = BLI_array_alloca(vert_arr, path_len);
177         BMEdge **edge_arr = BLI_array_alloca(edge_arr, path_len);
178
179         for (v_lnk = path, i = 0; v_lnk; v_lnk = v_lnk->next, i++) {
180                 vert_arr[i] = v_lnk->link;
181         }
182
183         i_prev = path_len - 1;
184         for (i = 0; i < path_len; i++) {
185                 edge_arr[i_prev] = BM_edge_exists(vert_arr[i], vert_arr[i_prev]);
186                 i_prev = i;
187         }
188
189         /* no need for this, we do overlap checks before allowing the path to be used */
190 #if 0
191         if (BM_face_exists_multi(vert_arr, edge_arr, path_len)) {
192                 return NULL;
193         }
194 #endif
195
196         f = BM_face_create(bm, vert_arr, edge_arr, (int)path_len, 0);
197
198         return f;
199 }
200
201 /**
202  * Step along the path from \a v_curr to any vert not already in the path.
203  *
204  * \return The connecting edge if the path is found, otherwise NULL.
205  */
206 static BMEdge *bm_edgenet_path_step(
207         BMVert *v_curr, LinkNode **v_ls,
208         VertNetInfo *vnet_info, BLI_mempool *path_pool)
209 {
210         const VertNetInfo *vn_curr = &vnet_info[BM_elem_index_get(v_curr)];
211
212         BMEdge *e;
213         BMIter iter;
214         unsigned int tot = 0;
215         unsigned int v_ls_tot = 0;
216
217         BM_ITER_ELEM (e, &iter, v_curr, BM_EDGES_OF_VERT) {
218                 BMVert *v_next = BM_edge_other_vert(e, v_curr);
219                 if (v_next != vn_curr->prev) {
220                         if (bm_edge_step_ok(e)) {
221                                 VertNetInfo *vn_next = &vnet_info[BM_elem_index_get(v_next)];
222
223                                 /* check we're not looping back on ourselves */
224                                 if (vn_curr->pass != vn_next->pass) {
225
226                                         if (vn_curr->pass == -vn_next->pass) {
227                                                 if ((vn_curr->flag & VNINFO_FLAG_IS_MIXFACE) ||
228                                                         (vn_next->flag & VNINFO_FLAG_IS_MIXFACE))
229                                                 {
230                                                         /* found connecting edge */
231                                                         if (bm_edgenet_path_check_overlap(v_curr, v_next, vnet_info) == false) {
232                                                                 return e;
233                                                         }
234                                                 }
235                                         }
236                                         else {
237                                                 vn_next->face = bm_edge_face(e);
238                                                 vn_next->pass = vn_curr->pass;
239                                                 vn_next->prev = v_curr;
240
241                                                 /* flush flag down the path */
242                                                 vn_next->flag &= ~VNINFO_FLAG_IS_MIXFACE;
243                                                 if ((vn_curr->flag & VNINFO_FLAG_IS_MIXFACE) ||
244                                                         (vn_next->face == -1) ||
245                                                         (vn_next->face != vn_curr->face))
246                                                 {
247                                                         vn_next->flag |= VNINFO_FLAG_IS_MIXFACE;
248                                                 }
249
250                                                 /* add to the list! */
251                                                 BLI_linklist_prepend_pool(v_ls, v_next, path_pool);
252                                                 v_ls_tot += 1;
253                                         }
254                                 }
255                         }
256                         tot += 1;
257                 }
258         }
259
260         /* trick to walk along wire-edge paths */
261         if (v_ls_tot == 1 && tot == 1) {
262                 v_curr = BLI_linklist_pop_pool(v_ls, path_pool);
263                 bm_edgenet_path_step(v_curr, v_ls, vnet_info, path_pool);
264         }
265
266         return NULL;
267 }
268
269 /**
270  * Given an edge, find the first path that can form a face.
271  *
272  * \return A linked list of verts.
273  */
274 static LinkNode *bm_edgenet_path_calc(
275         BMEdge *e, const int pass_nr, const unsigned int path_cost_max,
276         unsigned int *r_path_len, unsigned int *r_path_cost,
277         VertNetInfo *vnet_info, BLI_mempool *path_pool)
278 {
279         VertNetInfo *vn_1, *vn_2;
280         const int f_index = bm_edge_face(e);
281         bool found;
282
283         LinkNode *v_ls_prev = NULL;
284         LinkNode *v_ls_next = NULL;
285
286         unsigned int path_cost_accum = 0;
287
288         BLI_assert(bm_edge_step_ok(e));
289
290         *r_path_len = 0;
291         *r_path_cost = 0;
292
293         vn_1 = &vnet_info[BM_elem_index_get(e->v1)];
294         vn_2 = &vnet_info[BM_elem_index_get(e->v2)];
295
296         vn_1->pass =  pass_nr;
297         vn_2->pass = -pass_nr;
298
299         vn_1->prev = e->v2;
300         vn_2->prev = e->v1;
301
302         vn_1->face =
303         vn_2->face = f_index;
304
305         vn_1->flag =
306         vn_2->flag = (f_index == -1) ? VNINFO_FLAG_IS_MIXFACE : 0;
307
308         /* prime the searchlist */
309         BLI_linklist_prepend_pool(&v_ls_prev, e->v1, path_pool);
310         BLI_linklist_prepend_pool(&v_ls_prev, e->v2, path_pool);
311
312         do {
313                 found = false;
314
315                 /* no point to continue, we're over budget */
316                 if (path_cost_accum >= path_cost_max) {
317                         BLI_linklist_free_pool(v_ls_next, NULL, path_pool);
318                         BLI_linklist_free_pool(v_ls_prev, NULL, path_pool);
319                         return NULL;
320                 }
321
322                 while (v_ls_prev) {
323                         const LinkNode *v_ls_next_old = v_ls_next;
324                         BMVert *v = BLI_linklist_pop_pool(&v_ls_prev, path_pool);
325                         BMEdge *e_found = bm_edgenet_path_step(v, &v_ls_next, vnet_info, path_pool);
326
327                         if (e_found) {
328                                 LinkNode *path = NULL;
329                                 unsigned int path_len;
330                                 BLI_linklist_free_pool(v_ls_next, NULL, path_pool);
331                                 BLI_linklist_free_pool(v_ls_prev, NULL, path_pool);
332
333                                 // BLI_assert(BLI_mempool_count(path_pool) == 0);
334
335                                 path_len = bm_edgenet_path_from_pass(e_found->v1, &path, vnet_info, path_pool);
336                                 BLI_linklist_reverse(&path);
337                                 path_len += bm_edgenet_path_from_pass(e_found->v2, &path, vnet_info, path_pool);
338                                 *r_path_len = path_len;
339                                 *r_path_cost = path_cost_accum;
340                                 return path;
341                         }
342                         else {
343                                 /* check if a change was made */
344                                 if (v_ls_next_old != v_ls_next) {
345                                         found = true;
346                                 }
347                         }
348
349                 }
350                 BLI_assert(v_ls_prev == NULL);
351
352                 path_cost_accum++;
353
354                 /* swap */
355                 v_ls_prev = v_ls_next;
356                 v_ls_next = NULL;
357
358         } while (found);
359
360         BLI_assert(v_ls_prev == NULL);
361         BLI_assert(v_ls_next == NULL);
362
363         /* tag not to search again */
364         BM_elem_flag_disable(e, BM_ELEM_TAG);
365
366         return NULL;
367 }
368
369 /**
370  * Wrapper for #bm_edgenet_path_calc which ensures all included edges
371  * _don't_ have a better option.
372  */
373 static LinkNode *bm_edgenet_path_calc_best(
374         BMEdge *e, int *pass_nr, unsigned int path_cost_max,
375         unsigned int *r_path_len, unsigned int *r_path_cost,
376         VertNetInfo *vnet_info, BLI_mempool *path_pool)
377 {
378         LinkNode *path;
379         unsigned int path_cost;
380
381         path = bm_edgenet_path_calc(e, *pass_nr, path_cost_max,
382                                     r_path_len, &path_cost,
383                                     vnet_info, path_pool);
384         (*pass_nr)++;
385
386         if (path == NULL) {
387                 return NULL;
388         }
389         else if (path_cost <= 1) {
390                 /* any face that takes 1-2 iterations to find we consider valid */
391                 return path;
392         }
393         else {
394                 /* Check every edge to see if any can give a better path.
395                  * This avoids very strange/long paths from being created. */
396
397                 const unsigned int path_len = *r_path_len;
398                 unsigned int i, i_prev;
399                 BMVert **vert_arr = BLI_array_alloca(vert_arr, path_len);
400                 LinkNode *v_lnk;
401
402                 for (v_lnk = path, i = 0; v_lnk; v_lnk = v_lnk->next, i++) {
403                         vert_arr[i] = v_lnk->link;
404                 }
405
406                 i_prev = path_len - 1;
407                 for (i = 0; i < path_len; i++) {
408                         BMEdge *e_other = BM_edge_exists(vert_arr[i], vert_arr[i_prev]);
409                         if (e_other != e) {
410                                 LinkNode *path_test;
411                                 unsigned int path_len_test;
412                                 unsigned int path_cost_test;
413
414                                 path_test = bm_edgenet_path_calc(e_other, *pass_nr, path_cost,
415                                                                  &path_len_test, &path_cost_test,
416                                                                  vnet_info, path_pool);
417                                 (*pass_nr)++;
418
419                                 if (path_test) {
420                                         BLI_assert(path_cost_test < path_cost);
421
422                                         BLI_linklist_free_pool(path, NULL, path_pool);
423                                         path = path_test;
424                                         *r_path_len = path_len_test;
425                                         *r_path_cost = path_cost_test;
426                                         path_cost = path_cost_test;
427                                 }
428                         }
429
430                         i_prev = i;
431                 }
432         }
433         return path;
434 }
435
436 /**
437  * Fill in faces from an edgenet made up of boundary and wire edges.
438  *
439  * \note New faces currently don't have their normals calculated and are flipped randomly.
440  *       The caller needs to flip faces correctly.
441  *
442  * \param bm  The mesh to operate on.
443  * \param use_edge_tag  Only fill tagged edges.
444  * \param face_oflag  if nonzero, apply all new faces with this bmo flag.
445  */
446 void BM_mesh_edgenet(BMesh *bm, const bool use_edge_tag, const short face_oflag)
447 {
448         VertNetInfo *vnet_info = MEM_callocN(sizeof(*vnet_info) * (size_t)bm->totvert, __func__);
449         BLI_mempool *edge_queue_pool = BLI_mempool_create(sizeof(LinkNode), 1, 512, 0);
450         BLI_mempool *path_pool = BLI_mempool_create(sizeof(LinkNode), 1, 512, 0);
451         LinkNode *edge_queue = NULL;
452
453         BMEdge *e;
454         BMIter iter;
455
456         int pass_nr = 1;
457
458         if (use_edge_tag == false) {
459                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
460                         BM_elem_flag_enable(e, BM_ELEM_TAG);
461                         BM_elem_flag_set(e, BM_ELEM_TAG, bm_edge_step_ok(e));
462                 }
463         }
464
465         BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE);
466
467         while (true) {
468                 LinkNode *path = NULL;
469                 unsigned int path_len;
470                 unsigned int path_cost;
471
472                 e = bm_edgenet_edge_get_next(bm, &edge_queue, edge_queue_pool);
473                 if (e == NULL) {
474                         break;
475                 }
476
477                 BLI_assert(bm_edge_step_ok(e) == true);
478
479                 path = bm_edgenet_path_calc_best(e, &pass_nr, UINT_MAX,
480                                                  &path_len, &path_cost,
481                                                  vnet_info, path_pool);
482
483                 if (path) {
484                         BMFace *f = bm_edgenet_face_from_path(bm, path, path_len);
485                         /* queue edges to operate on */
486                         BMLoop *l_first, *l_iter;
487                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
488                         do {
489                                 if (bm_edge_step_ok(l_iter->e)) {
490                                         BLI_linklist_prepend_pool(&edge_queue, l_iter->e, edge_queue_pool);
491                                 }
492                         } while ((l_iter = l_iter->next) != l_first);
493
494                         if (face_oflag) {
495                                 BMO_elem_flag_enable(bm, f, face_oflag);
496                         }
497
498                         /* the face index only needs to be unique, not kept valid */
499                         BM_elem_index_set(f, bm->totface - 1);  /* set_dirty */
500                 }
501
502                 BLI_linklist_free_pool(path, NULL, path_pool);
503                 BLI_assert(BLI_mempool_count(path_pool) == 0);
504         }
505
506         bm->elem_index_dirty |= BM_FACE;
507
508         BLI_mempool_destroy(edge_queue_pool);
509         BLI_mempool_destroy(path_pool);
510         MEM_freeN(vnet_info);
511 }