Blender V5.3
bmesh_path.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
12
13#include "MEM_guardedalloc.h"
14
15#include <algorithm>
16
17#include "BLI_heap_simple.hh"
18#include "BLI_linklist.hh"
19#include "BLI_math_geom_c.hh"
20#include "BLI_math_vector_c.hh"
21
22#include "bmesh.hh"
23#include "bmesh_path.hh" /* own include */
24
25namespace blender {
26
27#define COST_INIT_MAX FLT_MAX
28
29/* -------------------------------------------------------------------- */
32
36static float step_cost_3_v3_ex(
37 const float v1[3], const float v2[3], const float v3[3], bool skip_12, bool skip_23)
38{
39 float d1[3], d2[3];
40
41 /* The cost is based on the simple sum of the length of the two edges. */
42 sub_v3_v3v3(d1, v2, v1);
43 sub_v3_v3v3(d2, v3, v2);
44 const float cost_12 = normalize_v3(d1);
45 const float cost_23 = normalize_v3(d2);
46 const float cost = ((skip_12 ? 0.0f : cost_12) + (skip_23 ? 0.0f : cost_23));
47
48 /* But is biased to give higher values to sharp turns, so that it will take paths with
49 * fewer "turns" when selecting between equal-weighted paths between the two edges. */
50 return cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2)))));
51}
52
53static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3])
54{
55 return step_cost_3_v3_ex(v1, v2, v3, false, false);
56}
57
59
60/* -------------------------------------------------------------------- */
63
65 BMVert *v_a,
66 BMVert **verts_prev,
67 float *cost,
68 const BMCalcPathParams *params)
69{
70 const int v_a_index = BM_elem_index_get(v_a);
71
72 {
73 BMIter eiter;
74 BMEdge *e;
75 /* Loop over faces of face, but do so by first looping over loops. */
76 BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) {
77 BMVert *v_b = BM_edge_other_vert(e, v_a);
78 if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
79 /* We know 'v_b' is not visited, check it out! */
80 const int v_b_index = BM_elem_index_get(v_b);
81 const float cost_cut = params->use_topology_distance ? 1.0f : len_v3v3(v_a->co, v_b->co);
82 const float cost_new = cost[v_a_index] + cost_cut;
83
84 if (cost[v_b_index] > cost_new) {
85 cost[v_b_index] = cost_new;
86 verts_prev[v_b_index] = v_a;
87 BLI_heapsimple_insert(heap, cost_new, v_b);
88 }
89 }
90 }
91 }
92
93 if (params->use_step_face) {
94 BMIter liter;
95 BMLoop *l;
96 /* Loop over faces of face, but do so by first looping over loops. */
97 BM_ITER_ELEM (l, &liter, v_a, BM_LOOPS_OF_VERT) {
98 if (l->f->len > 3) {
99 /* Skip loops on adjacent edges. */
100 BMLoop *l_iter = l->next->next;
101 do {
102 BMVert *v_b = l_iter->v;
103 if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
104 /* We know 'v_b' is not visited, check it out! */
105 const int v_b_index = BM_elem_index_get(v_b);
106 const float cost_cut = params->use_topology_distance ? 1.0f :
107 len_v3v3(v_a->co, v_b->co);
108 const float cost_new = cost[v_a_index] + cost_cut;
109
110 if (cost[v_b_index] > cost_new) {
111 cost[v_b_index] = cost_new;
112 verts_prev[v_b_index] = v_a;
113 BLI_heapsimple_insert(heap, cost_new, v_b);
114 }
115 }
116 } while ((l_iter = l_iter->next) != l->prev);
117 }
118 }
119 }
120}
121
123 BMVert *v_src,
124 BMVert *v_dst,
125 const BMCalcPathParams *params,
126 bool (*filter_fn)(BMVert *, void *user_data),
127 void *user_data)
128{
129 LinkNode *path = nullptr;
130 /* #BM_ELEM_TAG flag is used to store visited edges. */
131 BMVert *v;
132 BMIter viter;
133 HeapSimple *heap;
134 float *cost;
135 BMVert **verts_prev;
136 int i, totvert;
137
138 /* NOTE: would pass #BM_EDGE except we are looping over all faces anyway. */
139 // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
140
141 BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
142 BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
143 BM_elem_index_set(v, i); /* set_inline */
144 }
146
147 /* Allocate. */
148 totvert = bm->totvert;
149 verts_prev = MEM_new_array_zeroed<BMVert *>(totvert, __func__);
150 cost = MEM_new_array_uninitialized<float>(totvert, __func__);
151
152 std::fill_n(cost, totvert, COST_INIT_MAX);
153
154 /*
155 * Arrays are now filled as follows:
156 *
157 * As the search continues, `verts_prev[n]` will be the previous verts on the shortest
158 * path found so far to face `n`. #BM_ELEM_TAG is used to tag elements we have visited,
159 * `cost[n]` will contain the length of the shortest
160 * path to face n found so far, Finally, heap is a priority heap which is built on the
161 * the same data as the cost array, but inverted: it is a work-list of faces prioritized
162 * by the shortest path found so far to the face.
163 */
164
165 /* Regular dijkstra shortest path, but over faces instead of vertices. */
166 heap = BLI_heapsimple_new();
167 BLI_heapsimple_insert(heap, 0.0f, v_src);
168 cost[BM_elem_index_get(v_src)] = 0.0f;
169
170 while (!BLI_heapsimple_is_empty(heap)) {
171 v = static_cast<BMVert *>(BLI_heapsimple_pop_min(heap));
172
173 if (v == v_dst) {
174 break;
175 }
176
179 verttag_add_adjacent(heap, v, verts_prev, cost, params);
180 }
181 }
182
183 if (v == v_dst) {
184 do {
185 BLI_linklist_prepend(&path, v);
186 } while ((v = verts_prev[BM_elem_index_get(v)]));
187 }
188
189 MEM_delete(verts_prev);
190 MEM_delete(cost);
191 BLI_heapsimple_free(heap, nullptr);
192
193 return path;
194}
195
197
198/* -------------------------------------------------------------------- */
201
202static float edgetag_cut_cost_vert(BMEdge *e_a, BMEdge *e_b, BMVert *v)
203{
204 BMVert *v1 = BM_edge_other_vert(e_a, v);
205 BMVert *v2 = BM_edge_other_vert(e_b, v);
206 return step_cost_3_v3(v1->co, v->co, v2->co);
207}
208
209static float edgetag_cut_cost_face(BMEdge *e_a, BMEdge *e_b, BMFace *f)
210{
211 float e_a_cent[3], e_b_cent[3], f_cent[3];
212
213 mid_v3_v3v3(e_a_cent, e_a->v1->co, e_a->v1->co);
214 mid_v3_v3v3(e_b_cent, e_b->v1->co, e_b->v1->co);
215
217
218 return step_cost_3_v3(e_a_cent, e_b_cent, f_cent);
219}
220
222 BMEdge *e_a,
223 BMEdge **edges_prev,
224 float *cost,
225 const BMCalcPathParams *params)
226{
227 const int e_a_index = BM_elem_index_get(e_a);
228
229 /* Unlike vert/face, stepping faces disables scanning connected edges
230 * and only steps over faces (selecting a ring of edges instead of a loop). */
231 if (params->use_step_face == false || e_a->l == nullptr) {
232 BMIter viter;
233 BMVert *v;
234
235 BMIter eiter;
236 BMEdge *e_b;
237
238 BM_ITER_ELEM (v, &viter, e_a, BM_VERTS_OF_EDGE) {
239
240 /* Don't walk over previous vertex. */
241 if ((edges_prev[e_a_index]) && BM_vert_in_edge(edges_prev[e_a_index], v)) {
242 continue;
243 }
244
245 BM_ITER_ELEM (e_b, &eiter, v, BM_EDGES_OF_VERT) {
246 if (!BM_elem_flag_test(e_b, BM_ELEM_TAG) &&
247 /* Prevent the path overlapping itself in rare cases, see: #137456. */
249 {
250 /* We know 'e_b' is not visited, check it out! */
251 const int e_b_index = BM_elem_index_get(e_b);
252 const float cost_cut = params->use_topology_distance ?
253 1.0f :
254 edgetag_cut_cost_vert(e_a, e_b, v);
255 const float cost_new = cost[e_a_index] + cost_cut;
256
257 if (cost[e_b_index] > cost_new) {
258 cost[e_b_index] = cost_new;
259 edges_prev[e_b_index] = e_a;
260 BLI_heapsimple_insert(heap, cost_new, e_b);
261 }
262 }
263 }
264 }
265 }
266 else {
267 BMLoop *l_first, *l_iter;
268
269 l_iter = l_first = e_a->l;
270 do {
271 BMLoop *l_cycle_iter, *l_cycle_end;
272
273 l_cycle_iter = l_iter->next;
274 l_cycle_end = l_iter;
275
276/* Good, but we need to allow this otherwise paths may fail to connect at all. */
277#if 0
278 if (l_iter->f->len > 3) {
279 l_cycle_iter = l_cycle_iter->next;
280 l_cycle_end = l_cycle_end->prev;
281 }
282#endif
283
284 do {
285 BMEdge *e_b = l_cycle_iter->e;
286 if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) {
287 /* We know 'e_b' is not visited, check it out! */
288 const int e_b_index = BM_elem_index_get(e_b);
289 const float cost_cut = params->use_topology_distance ?
290 1.0f :
291 edgetag_cut_cost_face(e_a, e_b, l_iter->f);
292 const float cost_new = cost[e_a_index] + cost_cut;
293
294 if (cost[e_b_index] > cost_new) {
295 cost[e_b_index] = cost_new;
296 edges_prev[e_b_index] = e_a;
297 BLI_heapsimple_insert(heap, cost_new, e_b);
298 }
299 }
300 } while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end);
301 } while ((l_iter = l_iter->radial_next) != l_first);
302 }
303}
304
306 BMEdge *e_src,
307 BMEdge *e_dst,
308 const BMCalcPathParams *params,
309 bool (*filter_fn)(BMEdge *, void *user_data),
310 void *user_data)
311{
312 LinkNode *path = nullptr;
313 /* #BM_ELEM_TAG flag is used to store visited edges. */
314 BMIter iter;
315 HeapSimple *heap;
316 float *cost;
317 BMEdge **edges_prev;
318 int i, totedge;
319
320 {
321 BMVert *v;
324 BM_elem_index_set(v, i); /* set_inline */
325 }
327 }
328
329 {
330 BMEdge *e;
332 BM_elem_flag_set(e, BM_ELEM_TAG, !filter_fn(e, user_data));
333 BM_elem_index_set(e, i); /* set_inline */
334 }
336 }
337
338 /* Allocate. */
339 totedge = bm->totedge;
340 edges_prev = MEM_new_array_zeroed<BMEdge *>(totedge, __func__);
341 cost = MEM_new_array_uninitialized<float>(totedge, __func__);
342
343 std::fill_n(cost, totedge, COST_INIT_MAX);
344
345 /*
346 * Arrays are now filled as follows:
347 *
348 * As the search continues, `edges_prev[n]` will be the previous edge on the shortest
349 * path found so far to edge `n`. #BM_ELEM_TAG is used to tag elements we have visited,
350 * `cost[n]` will contain the length of the shortest
351 * path to edge n found so far, Finally, heap is a priority heap which is built on the
352 * the same data as the cost array, but inverted: it is a work-list of edges prioritized
353 * by the shortest path found so far to the edge.
354 */
355
356 /* Regular dijkstra shortest path, but over edges instead of vertices. */
357 heap = BLI_heapsimple_new();
358 BLI_heapsimple_insert(heap, 0.0f, e_src);
359 cost[BM_elem_index_get(e_src)] = 0.0f;
360
361 BMEdge *e = nullptr;
362 while (!BLI_heapsimple_is_empty(heap)) {
363 e = static_cast<BMEdge *>(BLI_heapsimple_pop_min(heap));
364
365 if (e == e_dst) {
366 break;
367 }
368
371
372 /* Prevent the path overlapping itself in rare cases, see: #137456. */
375
376 edgetag_add_adjacent(heap, e, edges_prev, cost, params);
377 }
378 }
379
380 if (e == e_dst) {
381 do {
382 BLI_linklist_prepend(&path, e);
383 } while ((e = edges_prev[BM_elem_index_get(e)]));
384 }
385
386 MEM_delete(edges_prev);
387 MEM_delete(cost);
388 BLI_heapsimple_free(heap, nullptr);
389
390 return path;
391}
392
394
395/* -------------------------------------------------------------------- */
398
400 BMFace *f_b,
401 BMEdge *e,
402 const void *const f_endpoints[2])
403{
404 float f_a_cent[3];
405 float f_b_cent[3];
406 float e_cent[3];
407
410#if 0
411 mid_v3_v3v3(e_cent, e->v1->co, e->v2->co);
412#else
413 /* For triangle fans it gives better results to pick a point on the edge. */
414 {
415 float ix_e[3], ix_f[3];
416 isect_line_line_v3(e->v1->co, e->v2->co, f_a_cent, f_b_cent, ix_e, ix_f);
417 const float factor = line_point_factor_v3(ix_e, e->v1->co, e->v2->co);
418 if (factor < 0.0f) {
419 copy_v3_v3(e_cent, e->v1->co);
420 }
421 else if (factor > 1.0f) {
422 copy_v3_v3(e_cent, e->v2->co);
423 }
424 else {
425 copy_v3_v3(e_cent, ix_e);
426 }
427 }
428#endif
429
430 return step_cost_3_v3_ex(
431 f_a_cent, e_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
432}
433
435 BMFace *f_b,
436 BMVert *v,
437 const void *const f_endpoints[2])
438{
439 float f_a_cent[3];
440 float f_b_cent[3];
441
444
445 return step_cost_3_v3_ex(
446 f_a_cent, v->co, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
447}
448
450 BMFace *f_a,
451 BMFace **faces_prev,
452 float *cost,
453 const void *const f_endpoints[2],
454 const BMCalcPathParams *params)
455{
456 const int f_a_index = BM_elem_index_get(f_a);
457
458 /* Loop over faces of face, but do so by first looping over loops. */
459 {
460 BMIter liter;
461 BMLoop *l_a;
462
463 BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
464 BMLoop *l_first, *l_iter;
465
466 l_iter = l_first = l_a;
467 do {
468 BMFace *f_b = l_iter->f;
469 if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
470 /* We know 'f_b' is not visited, check it out! */
471 const int f_b_index = BM_elem_index_get(f_b);
472 const float cost_cut = params->use_topology_distance ?
473 1.0f :
474 facetag_cut_cost_edge(f_a, f_b, l_iter->e, f_endpoints);
475 const float cost_new = cost[f_a_index] + cost_cut;
476
477 if (cost[f_b_index] > cost_new) {
478 cost[f_b_index] = cost_new;
479 faces_prev[f_b_index] = f_a;
480 BLI_heapsimple_insert(heap, cost_new, f_b);
481 }
482 }
483 } while ((l_iter = l_iter->radial_next) != l_first);
484 }
485 }
486
487 if (params->use_step_face) {
488 BMIter liter;
489 BMLoop *l_a;
490
491 BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
492 BMIter litersub;
493 BMLoop *l_b;
494 BM_ITER_ELEM (l_b, &litersub, l_a->v, BM_LOOPS_OF_VERT) {
495 if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) {
496 BMFace *f_b = l_b->f;
497 if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
498 /* We know 'f_b' is not visited, check it out! */
499 const int f_b_index = BM_elem_index_get(f_b);
500 const float cost_cut = params->use_topology_distance ?
501 1.0f :
502 facetag_cut_cost_vert(f_a, f_b, l_a->v, f_endpoints);
503 const float cost_new = cost[f_a_index] + cost_cut;
504
505 if (cost[f_b_index] > cost_new) {
506 cost[f_b_index] = cost_new;
507 faces_prev[f_b_index] = f_a;
508 BLI_heapsimple_insert(heap, cost_new, f_b);
509 }
510 }
511 }
512 }
513 }
514 }
515}
516
518 BMFace *f_src,
519 BMFace *f_dst,
520 const BMCalcPathParams *params,
521 bool (*filter_fn)(BMFace *, void *user_data),
522 void *user_data)
523{
524 LinkNode *path = nullptr;
525 /* #BM_ELEM_TAG flag is used to store visited edges. */
526 BMFace *f;
527 BMIter fiter;
528 HeapSimple *heap;
529 float *cost;
530 BMFace **faces_prev;
531 int i, totface;
532
533 /* Start measuring face path at the face edges, ignoring their centers. */
534 const void *const f_endpoints[2] = {f_src, f_dst};
535
536 /* NOTE: would pass #BM_EDGE except we are looping over all faces anyway. */
537 // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG
538
539 BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
540 BM_elem_flag_set(f, BM_ELEM_TAG, !filter_fn(f, user_data));
541 BM_elem_index_set(f, i); /* set_inline */
542 }
544
545 /* Allocate. */
546 totface = bm->totface;
547 faces_prev = MEM_new_array_zeroed<BMFace *>(totface, __func__);
548 cost = MEM_new_array_uninitialized<float>(totface, __func__);
549
550 std::fill_n(cost, totface, COST_INIT_MAX);
551
552 /*
553 * Arrays are now filled as follows:
554 *
555 * As the search continues, `faces_prev[n]` will be the previous face on the shortest
556 * path found so far to face `n`. #BM_ELEM_TAG is used to tag elements we have visited,
557 * `cost[n]` will contain the length of the shortest
558 * path to face n found so far, Finally, heap is a priority heap which is built on the
559 * the same data as the cost array, but inverted: it is a work-list of faces prioritized
560 * by the shortest path found so far to the face.
561 */
562
563 /* Regular dijkstra shortest path, but over faces instead of vertices. */
564 heap = BLI_heapsimple_new();
565 BLI_heapsimple_insert(heap, 0.0f, f_src);
566 cost[BM_elem_index_get(f_src)] = 0.0f;
567
568 while (!BLI_heapsimple_is_empty(heap)) {
569 f = static_cast<BMFace *>(BLI_heapsimple_pop_min(heap));
570
571 if (f == f_dst) {
572 break;
573 }
574
577 facetag_add_adjacent(heap, f, faces_prev, cost, f_endpoints, params);
578 }
579 }
580
581 if (f == f_dst) {
582 do {
583 BLI_linklist_prepend(&path, f);
584 } while ((f = faces_prev[BM_elem_index_get(f)]));
585 }
586
587 MEM_delete(faces_prev);
588 MEM_delete(cost);
589 BLI_heapsimple_free(heap, nullptr);
590
591 return path;
592}
593
595
596} // namespace blender
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
#define COST_INIT_MAX
Definition bmesh_path.cc:27
BMesh Iterators.
bool BM_loop_share_edge_check(BMLoop *l_a, BMLoop *l_b)
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static void facetag_add_adjacent(HeapSimple *heap, BMFace *f_a, BMFace **faces_prev, float *cost, const void *const f_endpoints[2], const BMCalcPathParams *params)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
LinkNode * BM_mesh_calc_path_face(BMesh *bm, BMFace *f_src, BMFace *f_dst, const BMCalcPathParams *params, bool(*filter_fn)(BMFace *, void *user_data), void *user_data)
LinkNode * BM_mesh_calc_path_vert(BMesh *bm, BMVert *v_src, BMVert *v_dst, const BMCalcPathParams *params, bool(*filter_fn)(BMVert *, void *user_data), void *user_data)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
static float step_cost_3_v3_ex(const float v1[3], const float v2[3], const float v3[3], bool skip_12, bool skip_23)
Definition bmesh_path.cc:36
static float facetag_cut_cost_vert(BMFace *f_a, BMFace *f_b, BMVert *v, const void *const f_endpoints[2])
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e, const void *const f_endpoints[2])
HeapSimple * BLI_heapsimple_new() ATTR_WARN_UNUSED_RESULT
LinkNode * BM_mesh_calc_path_edge(BMesh *bm, BMEdge *e_src, BMEdge *e_dst, const BMCalcPathParams *params, bool(*filter_fn)(BMEdge *, void *user_data), void *user_data)
MINLINE float normalize_v3(float n[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3])
Definition bmesh_path.cc:53
static float edgetag_cut_cost_face(BMEdge *e_a, BMEdge *e_b, BMFace *f)
static float edgetag_cut_cost_vert(BMEdge *e_a, BMEdge *e_b, BMVert *v)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[3])
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static void edgetag_add_adjacent(HeapSimple *heap, BMEdge *e_a, BMEdge **edges_prev, float *cost, const BMCalcPathParams *params)
int isect_line_line_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3])
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static void verttag_add_adjacent(HeapSimple *heap, BMVert *v_a, BMVert **verts_prev, float *cost, const BMCalcPathParams *params)
Definition bmesh_path.cc:64
#define fabsf
#define sqrtf
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f