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