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