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