20 #define COST_INIT_MAX FLT_MAX
30 const float v1[3],
const float v2[3],
const float v3[3],
bool skip_12,
bool skip_23)
39 const float cost = ((skip_12 ? 0.0f : cost_12) + (skip_23 ? 0.0f : cost_23));
74 const float cost_cut =
params->use_topology_distance ? 1.0f :
len_v3v3(v_a->
co, v_b->
co);
75 const float cost_new = cost[v_a_index] + cost_cut;
77 if (cost[v_b_index] > cost_new) {
78 cost[v_b_index] = cost_new;
79 verts_prev[v_b_index] = v_a;
86 if (
params->use_step_face) {
99 const float cost_cut =
params->use_topology_distance ? 1.0f :
101 const float cost_new = cost[v_a_index] + cost_cut;
103 if (cost[v_b_index] > cost_new) {
104 cost[v_b_index] = cost_new;
105 verts_prev[v_b_index] = v_a;
109 }
while ((l_iter = l_iter->
next) !=
l->
prev);
142 verts_prev =
MEM_callocN(
sizeof(*verts_prev) * totvert, __func__);
143 cost =
MEM_mallocN(
sizeof(*cost) * totvert, __func__);
204 float e_a_cent[3], e_b_cent[3], f_cent[3];
224 if (
params->use_step_face ==
false || e_a->
l ==
NULL) {
234 if ((edges_prev[e_a_index]) && (
BM_vert_in_edge(edges_prev[e_a_index],
v))) {
242 const float cost_cut =
params->use_topology_distance ?
245 const float cost_new = cost[e_a_index] + cost_cut;
247 if (cost[e_b_index] > cost_new) {
248 cost[e_b_index] = cost_new;
249 edges_prev[e_b_index] = e_a;
259 l_iter = l_first = e_a->
l;
261 BMLoop *l_cycle_iter, *l_cycle_end;
263 l_cycle_iter = l_iter->
next;
264 l_cycle_end = l_iter;
268 if (l_iter->
f->
len > 3) {
269 l_cycle_iter = l_cycle_iter->
next;
270 l_cycle_end = l_cycle_end->
prev;
279 const float cost_cut =
params->use_topology_distance ?
282 const float cost_new = cost[e_a_index] + cost_cut;
284 if (cost[e_b_index] > cost_new) {
285 cost[e_b_index] = cost_new;
286 edges_prev[e_b_index] = e_a;
290 }
while ((l_cycle_iter = l_cycle_iter->
next) != l_cycle_end);
291 }
while ((l_iter = l_iter->
radial_next) != l_first);
322 edges_prev =
MEM_callocN(
sizeof(*edges_prev) * totedge, __func__);
323 cost =
MEM_mallocN(
sizeof(*cost) * totedge, __func__);
378 const void *
const f_endpoints[2])
391 float ix_e[3], ix_f[3];
397 else if (factor > 1.0f) {
407 f_a_cent, e_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
413 const void *
const f_endpoints[2])
422 f_a_cent,
v->
co, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
429 const void *
const f_endpoints[2],
442 l_iter = l_first = l_a;
448 const float cost_cut =
params->use_topology_distance ?
451 const float cost_new = cost[f_a_index] + cost_cut;
453 if (cost[f_b_index] > cost_new) {
454 cost[f_b_index] = cost_new;
455 faces_prev[f_b_index] = f_a;
459 }
while ((l_iter = l_iter->
radial_next) != l_first);
463 if (
params->use_step_face) {
476 const float cost_cut =
params->use_topology_distance ?
479 const float cost_new = cost[f_a_index] + cost_cut;
481 if (cost[f_b_index] > cost_new) {
482 cost[f_b_index] = cost_new;
483 faces_prev[f_b_index] = f_a;
510 const void *
const f_endpoints[2] = {f_src, f_dst};
523 faces_prev =
MEM_callocN(
sizeof(*faces_prev) * totface, __func__);
524 cost =
MEM_mallocN(
sizeof(*cost) * totface, __func__);
A min-heap / priority queue ADT.
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
HeapSimple * BLI_heapsimple_new(void) ATTR_WARN_UNUSED_RESULT
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
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])
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
void copy_vn_fl(float *array_tar, int size, float val)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
#define BM_elem_index_get(ele)
#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)
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
LinkNode * BM_mesh_calc_path_vert(BMesh *bm, BMVert *v_src, BMVert *v_dst, const struct BMCalcPathParams *params, bool(*filter_fn)(BMVert *, void *user_data), void *user_data)
static float edgetag_cut_cost_face(BMEdge *e_a, BMEdge *e_b, BMFace *f)
static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, BMEdge *e, const void *const f_endpoints[2])
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)
LinkNode * BM_mesh_calc_path_edge(BMesh *bm, BMEdge *e_src, BMEdge *e_dst, const struct BMCalcPathParams *params, bool(*filter_fn)(BMEdge *, void *user_data), void *user_data)
static void edgetag_add_adjacent(HeapSimple *heap, BMEdge *e_a, BMEdge **edges_prev, float *cost, const struct BMCalcPathParams *params)
static void facetag_add_adjacent(HeapSimple *heap, BMFace *f_a, BMFace **faces_prev, float *cost, const void *const f_endpoints[2], const struct BMCalcPathParams *params)
static float edgetag_cut_cost_vert(BMEdge *e_a, BMEdge *e_b, BMVert *v)
LinkNode * BM_mesh_calc_path_face(BMesh *bm, BMFace *f_src, BMFace *f_dst, const struct BMCalcPathParams *params, bool(*filter_fn)(BMFace *, void *user_data), void *user_data)
static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3])
static float facetag_cut_cost_vert(BMFace *f_a, BMFace *f_b, BMVert *v, const void *const f_endpoints[2])
static void verttag_add_adjacent(HeapSimple *heap, BMVert *v_a, BMVert **verts_prev, float *cost, const struct BMCalcPathParams *params)
void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[3])
bool BM_loop_share_edge_check(BMLoop *l_a, BMLoop *l_b)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
ATTR_WARN_UNUSED_RESULT const BMVert * v
void(* MEM_freeN)(void *vmemh)
void *(* MEM_callocN)(size_t len, const char *str)
void *(* MEM_mallocN)(size_t len, const char *str)
struct BMLoop * radial_next