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