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