27#define COST_INIT_MAX FLT_MAX
37 const float v1[3],
const float v2[3],
const float v3[3],
bool skip_12,
bool skip_23)
46 const float cost = ((skip_12 ? 0.0f : cost_12) + (skip_23 ? 0.0f : cost_23));
82 const float cost_new = cost[v_a_index] + cost_cut;
84 if (cost[v_b_index] > cost_new) {
85 cost[v_b_index] = cost_new;
86 verts_prev[v_b_index] = v_a;
108 const float cost_new = cost[v_a_index] + cost_cut;
110 if (cost[v_b_index] > cost_new) {
111 cost[v_b_index] = cost_new;
112 verts_prev[v_b_index] = v_a;
116 }
while ((l_iter = l_iter->
next) !=
l->
prev);
126 bool (*filter_fn)(
BMVert *,
void *user_data),
189 MEM_delete(verts_prev);
211 float e_a_cent[3], e_b_cent[3], f_cent[3];
255 const float cost_new = cost[e_a_index] + cost_cut;
257 if (cost[e_b_index] > cost_new) {
258 cost[e_b_index] = cost_new;
259 edges_prev[e_b_index] = e_a;
269 l_iter = l_first = e_a->
l;
271 BMLoop *l_cycle_iter, *l_cycle_end;
273 l_cycle_iter = l_iter->
next;
274 l_cycle_end = l_iter;
278 if (l_iter->
f->
len > 3) {
279 l_cycle_iter = l_cycle_iter->
next;
280 l_cycle_end = l_cycle_end->
prev;
292 const float cost_new = cost[e_a_index] + cost_cut;
294 if (cost[e_b_index] > cost_new) {
295 cost[e_b_index] = cost_new;
296 edges_prev[e_b_index] = e_a;
300 }
while ((l_cycle_iter = l_cycle_iter->
next) != l_cycle_end);
301 }
while ((l_iter = l_iter->
radial_next) != l_first);
309 bool (*filter_fn)(
BMEdge *,
void *user_data),
386 MEM_delete(edges_prev);
402 const void *
const f_endpoints[2])
415 float ix_e[3], ix_f[3];
421 else if (factor > 1.0f) {
431 f_a_cent, e_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
437 const void *
const f_endpoints[2])
446 f_a_cent,
v->
co, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
453 const void *
const f_endpoints[2],
466 l_iter = l_first = l_a;
475 const float cost_new = cost[f_a_index] + cost_cut;
477 if (cost[f_b_index] > cost_new) {
478 cost[f_b_index] = cost_new;
479 faces_prev[f_b_index] = f_a;
483 }
while ((l_iter = l_iter->
radial_next) != l_first);
503 const float cost_new = cost[f_a_index] + cost_cut;
505 if (cost[f_b_index] > cost_new) {
506 cost[f_b_index] = cost_new;
507 faces_prev[f_b_index] = f_a;
521 bool (*filter_fn)(
BMFace *,
void *user_data),
534 const void *
const f_endpoints[2] = {f_src, f_dst};
587 MEM_delete(faces_prev);
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)
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)
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])
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)
uint use_topology_distance
struct BMLoop * radial_next