Blender  V3.3
bmo_connect_pair.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include "MEM_guardedalloc.h"
10 
11 #include "BLI_heap_simple.h"
12 #include "BLI_math.h"
13 #include "BLI_utildefines.h"
14 
15 #include "bmesh.h"
16 
17 #include "intern/bmesh_operators_private.h" /* own include */
18 
19 #include "BLI_mempool.h"
20 
40 #define CONNECT_EPS 0.0001f
41 #define VERT_OUT 1
42 #define VERT_EXCLUDE 2
43 
44 /* typically hidden faces */
45 #define FACE_EXCLUDE 2
46 
47 /* any element we've walked over (only do it once!) */
48 #define ELE_TOUCHED 4
49 
50 #define FACE_WALK_TEST(f) \
51  (CHECK_TYPE_INLINE(f, BMFace *), BMO_face_flag_test(pc->bm_bmoflag, f, FACE_EXCLUDE) == 0)
52 #define VERT_WALK_TEST(v) \
53  (CHECK_TYPE_INLINE(v, BMVert *), BMO_vert_flag_test(pc->bm_bmoflag, v, VERT_EXCLUDE) == 0)
54 
55 #if 0
56 # define ELE_TOUCH_TEST(e) \
57  (CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *), \
58  BMO_elem_flag_test(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED))
59 #endif
60 #define ELE_TOUCH_MARK(e) \
61  { \
62  CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *); \
63  BMO_elem_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED); \
64  } \
65  ((void)0)
66 
67 #define ELE_TOUCH_TEST_VERT(v) BMO_vert_flag_test(pc->bm_bmoflag, v, ELE_TOUCHED)
68 // #define ELE_TOUCH_MARK_VERT(v) BMO_vert_flag_enable(pc->bm_bmoflag, (BMElemF *)v, ELE_TOUCHED)
69 
70 #define ELE_TOUCH_TEST_EDGE(e) BMO_edge_flag_test(pc->bm_bmoflag, e, ELE_TOUCHED)
71 // #define ELE_TOUCH_MARK_EDGE(e) BMO_edge_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED)
72 
73 // #define ELE_TOUCH_TEST_FACE(f) BMO_face_flag_test(pc->bm_bmoflag, f, ELE_TOUCHED)
74 // #define ELE_TOUCH_MARK_FACE(f) BMO_face_flag_enable(pc->bm_bmoflag, (BMElemF *)f, ELE_TOUCHED)
75 
76 // #define DEBUG_PRINT
77 
78 typedef struct PathContext {
80  float matrix[3][3];
81  float axis_sep;
82 
83  /* only to access BMO flags */
85 
87 
90 
94 typedef struct PathLink {
95  struct PathLink *next;
96  BMElem *ele; /* edge or vert */
97  BMElem *ele_from; /* edge or face we came from (not 'next->ele') */
99 
100 typedef struct PathLinkState {
101  /* chain of links */
103 
104  /* length along links */
105  float dist;
106  float co_prev[3];
108 
109 /* -------------------------------------------------------------------- */
123 typedef struct MinDistDir {
124  /* distance in both directions (FLT_MAX == uninitialized) */
125  float dist_min[2];
126  /* direction of the first intersection found */
127  float dir[3];
129 
130 #define MIN_DIST_DIR_INIT \
131  { \
132  { \
133  FLT_MAX, FLT_MAX \
134  } \
135  }
136 
137 static int min_dist_dir_test(MinDistDir *mddir, const float dist_dir[3], const float dist_sq)
138 {
139 
140  if (mddir->dist_min[0] == FLT_MAX) {
141  return 0;
142  }
143  if (dot_v3v3(dist_dir, mddir->dir) > 0.0f) {
144  if (dist_sq < mddir->dist_min[0]) {
145  return 0;
146  }
147  }
148  else {
149  if (dist_sq < mddir->dist_min[1]) {
150  return 1;
151  }
152  }
153 
154  return -1;
155 }
156 
157 static void min_dist_dir_update(MinDistDir *dist, const float dist_dir[3])
158 {
159  if (dist->dist_min[0] == FLT_MAX) {
160  copy_v3_v3(dist->dir, dist_dir);
161  }
162 }
163 
166 static int state_isect_co_pair(const PathContext *pc, const float co_a[3], const float co_b[3])
167 {
168  const float diff_a = dot_m3_v3_row_x(pc->matrix, co_a) - pc->axis_sep;
169  const float diff_b = dot_m3_v3_row_x(pc->matrix, co_b) - pc->axis_sep;
170 
171  const int test_a = (fabsf(diff_a) < CONNECT_EPS) ? 0 : (diff_a < 0.0f) ? -1 : 1;
172  const int test_b = (fabsf(diff_b) < CONNECT_EPS) ? 0 : (diff_b < 0.0f) ? -1 : 1;
173 
174  if ((test_a && test_b) && (test_a != test_b)) {
175  return 1; /* on either side */
176  }
177  return 0;
178 }
179 
180 static int state_isect_co_exact(const PathContext *pc, const float co[3])
181 {
182  const float diff = dot_m3_v3_row_x(pc->matrix, co) - pc->axis_sep;
183  return (fabsf(diff) <= CONNECT_EPS);
184 }
185 
186 static float state_calc_co_pair_fac(const PathContext *pc,
187  const float co_a[3],
188  const float co_b[3])
189 {
190  float diff_a, diff_b, diff_tot;
191 
192  diff_a = fabsf(dot_m3_v3_row_x(pc->matrix, co_a) - pc->axis_sep);
193  diff_b = fabsf(dot_m3_v3_row_x(pc->matrix, co_b) - pc->axis_sep);
194  diff_tot = (diff_a + diff_b);
195  return (diff_tot > FLT_EPSILON) ? (diff_a / diff_tot) : 0.5f;
196 }
197 
198 static void state_calc_co_pair(const PathContext *pc,
199  const float co_a[3],
200  const float co_b[3],
201  float r_co[3])
202 {
203  const float fac = state_calc_co_pair_fac(pc, co_a, co_b);
204  interp_v3_v3v3(r_co, co_a, co_b, fac);
205 }
206 
207 #ifndef NDEBUG
212 static bool state_link_find(const PathLinkState *state, BMElem *ele)
213 {
214  PathLink *link = state->link_last;
216  if (link) {
217  do {
218  if (link->ele == ele) {
219  return true;
220  }
221  } while ((link = link->next));
222  }
223  return false;
224 }
225 #endif
226 
227 static void state_link_add(PathContext *pc, PathLinkState *state, BMElem *ele, BMElem *ele_from)
228 {
229  PathLink *step_new = BLI_mempool_alloc(pc->link_pool);
230  BLI_assert(ele != ele_from);
231  BLI_assert(state_link_find(state, ele) == false);
232 
233  /* never walk onto this again */
234  ELE_TOUCH_MARK(ele);
235 
236 #ifdef DEBUG_PRINT
237  printf("%s: adding to state %p, %.4f - ", __func__, state, state->dist);
238  if (ele->head.htype == BM_VERT) {
239  printf("vert %d, ", BM_elem_index_get(ele));
240  }
241  else if (ele->head.htype == BM_EDGE) {
242  printf("edge %d, ", BM_elem_index_get(ele));
243  }
244  else {
245  BLI_assert(0);
246  }
247 
248  if (ele_from == NULL) {
249  printf("from NULL\n");
250  }
251  else if (ele_from->head.htype == BM_EDGE) {
252  printf("from edge %d\n", BM_elem_index_get(ele_from));
253  }
254  else if (ele_from->head.htype == BM_FACE) {
255  printf("from face %d\n", BM_elem_index_get(ele_from));
256  }
257  else {
258  BLI_assert(0);
259  }
260 #endif
261 
262  /* track distance */
263  {
264  float co[3];
265  if (ele->head.htype == BM_VERT) {
266  copy_v3_v3(co, ((BMVert *)ele)->co);
267  }
268  else if (ele->head.htype == BM_EDGE) {
269  state_calc_co_pair(pc, ((BMEdge *)ele)->v1->co, ((BMEdge *)ele)->v2->co, co);
270  }
271  else {
272  BLI_assert(0);
273  }
274 
275  /* tally distance */
276  if (ele_from) {
277  state->dist += len_v3v3(state->co_prev, co);
278  }
279  copy_v3_v3(state->co_prev, co);
280  }
281 
282  step_new->ele = ele;
283  step_new->ele_from = ele_from;
284  step_new->next = state->link_last;
285  state->link_last = step_new;
286 }
287 
289 {
290  state = MEM_mallocN(sizeof(*state), __func__);
291  *state = *state_orig;
292  return state;
293 }
294 
297  const PathLinkState *state_orig,
298  BMElem *ele,
299  BMElem *ele_from)
300 {
301  const bool is_new = (state_orig->link_last != state->link_last);
302  if (is_new) {
303  state = state_dupe_add(state, state_orig);
304  }
305 
306  state_link_add(pc, state, ele, ele_from);
307 
308  /* after adding a link so we use the updated 'state->dist' */
309  if (is_new) {
311  }
312 
313  return state;
314 }
315 
316 /* walk around the face edges */
319  const PathLinkState *state_orig,
320  BMLoop *l_iter,
321  BMLoop *l_last,
322  MinDistDir *mddir)
323 {
324 
325  BMLoop *l_iter_best[2] = {NULL, NULL};
326  int i;
327 
328  do {
329  if (state_isect_co_pair(pc, l_iter->v->co, l_iter->next->v->co)) {
330  float dist_test;
331  float co_isect[3];
332  float dist_dir[3];
333  int index;
334 
335  state_calc_co_pair(pc, l_iter->v->co, l_iter->next->v->co, co_isect);
336 
337  sub_v3_v3v3(dist_dir, co_isect, state_orig->co_prev);
338  dist_test = len_squared_v3(dist_dir);
339  if ((index = min_dist_dir_test(mddir, dist_dir, dist_test)) != -1) {
340  BMElem *ele_next = (BMElem *)l_iter->e;
341  BMElem *ele_next_from = (BMElem *)l_iter->f;
342 
343  if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
344  (ELE_TOUCH_TEST_EDGE((BMEdge *)ele_next) == false)) {
345  min_dist_dir_update(mddir, dist_dir);
346  mddir->dist_min[index] = dist_test;
347  l_iter_best[index] = l_iter;
348  }
349  }
350  }
351  } while ((l_iter = l_iter->next) != l_last);
352 
353  for (i = 0; i < 2; i++) {
354  if ((l_iter = l_iter_best[i])) {
355  BMElem *ele_next = (BMElem *)l_iter->e;
356  BMElem *ele_next_from = (BMElem *)l_iter->f;
357  state = state_link_add_test(pc, state, state_orig, ele_next, ele_next_from);
358  }
359  }
360 
361  return state;
362 }
363 
364 /* walk around the face verts */
367  const PathLinkState *state_orig,
368  BMLoop *l_iter,
369  BMLoop *l_last,
370  MinDistDir *mddir)
371 {
372  BMLoop *l_iter_best[2] = {NULL, NULL};
373  int i;
374 
375  do {
376  if (state_isect_co_exact(pc, l_iter->v->co)) {
377  float dist_test;
378  const float *co_isect = l_iter->v->co;
379  float dist_dir[3];
380  int index;
381 
382  sub_v3_v3v3(dist_dir, co_isect, state_orig->co_prev);
383  dist_test = len_squared_v3(dist_dir);
384  if ((index = min_dist_dir_test(mddir, dist_dir, dist_test)) != -1) {
385  BMElem *ele_next = (BMElem *)l_iter->v;
386  BMElem *ele_next_from = (BMElem *)l_iter->f;
387 
388  if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
389  (ELE_TOUCH_TEST_VERT((BMVert *)ele_next) == false)) {
390  min_dist_dir_update(mddir, dist_dir);
391  mddir->dist_min[index] = dist_test;
392  l_iter_best[index] = l_iter;
393  }
394  }
395  }
396  } while ((l_iter = l_iter->next) != l_last);
397 
398  for (i = 0; i < 2; i++) {
399  if ((l_iter = l_iter_best[i])) {
400  BMElem *ele_next = (BMElem *)l_iter->v;
401  BMElem *ele_next_from = (BMElem *)l_iter->f;
402  state = state_link_add_test(pc, state, state_orig, ele_next, ele_next_from);
403  }
404  }
405 
406  return state;
407 }
408 
410 {
411  PathLinkState state_orig = *state;
412  BMElem *ele = state->link_last->ele;
413  const void *ele_from = state->link_last->ele_from;
414 
415  if (ele->head.htype == BM_EDGE) {
416  BMEdge *e = (BMEdge *)ele;
417 
418  BMIter liter;
419  BMLoop *l_start;
420 
421  BM_ITER_ELEM (l_start, &liter, e, BM_LOOPS_OF_EDGE) {
422  if ((l_start->f != ele_from) && FACE_WALK_TEST(l_start->f)) {
424  /* Very similar to block below. */
425  state = state_step__face_edges(pc, state, &state_orig, l_start->next, l_start, &mddir);
427  pc, state, &state_orig, l_start->next->next, l_start, &mddir);
428  }
429  }
430  }
431  else if (ele->head.htype == BM_VERT) {
432  BMVert *v = (BMVert *)ele;
433 
434  /* Vert loops. */
435  {
436  BMIter liter;
437  BMLoop *l_start;
438 
439  BM_ITER_ELEM (l_start, &liter, v, BM_LOOPS_OF_VERT) {
440  if ((l_start->f != ele_from) && FACE_WALK_TEST(l_start->f)) {
442  /* Very similar to block above. */
444  pc, state, &state_orig, l_start->next, l_start->prev, &mddir);
445  if (l_start->f->len > 3) {
446  /* Adjacent verts are handled in #state_step__vert_edges. */
448  pc, state, &state_orig, l_start->next->next, l_start->prev, &mddir);
449  }
450  }
451  }
452  }
453 
454  /* Vert edges. */
455  {
456  BMIter eiter;
457  BMEdge *e;
458  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
459  BMVert *v_other = BM_edge_other_vert(e, v);
460  if (((BMElem *)e != ele_from) && VERT_WALK_TEST(v_other)) {
461  if (state_isect_co_exact(pc, v_other->co)) {
462  BMElem *ele_next = (BMElem *)v_other;
463  BMElem *ele_next_from = (BMElem *)e;
464  if (ELE_TOUCH_TEST_VERT((BMVert *)ele_next) == false) {
465  state = state_link_add_test(pc, state, &state_orig, ele_next, ele_next_from);
466  }
467  }
468  }
469  }
470  }
471  }
472  else {
473  BLI_assert(0);
474  }
475  return (state_orig.link_last != state->link_last);
476 }
477 
481 static void bm_vert_pair_to_matrix(BMVert *v_pair[2], float r_unit_mat[3][3])
482 {
483  const float eps = 1e-8f;
484 
485  float basis_dir[3];
486  float basis_tmp[3];
487  float basis_nor[3];
488 
489  sub_v3_v3v3(basis_dir, v_pair[0]->co, v_pair[1]->co);
490  normalize_v3(basis_dir);
491 
492 #if 0
493  add_v3_v3v3(basis_nor, v_pair[0]->no, v_pair[1]->no);
494  cross_v3_v3v3(basis_tmp, basis_nor, basis_dir);
495  cross_v3_v3v3(basis_nor, basis_tmp, basis_dir);
496 #else
497  /* align both normals to the directions before combining */
498  {
499  float basis_nor_a[3];
500  float basis_nor_b[3];
501 
502  /* align normal to direction */
503  project_plane_normalized_v3_v3v3(basis_nor_a, v_pair[0]->no, basis_dir);
504  project_plane_normalized_v3_v3v3(basis_nor_b, v_pair[1]->no, basis_dir);
505 
506  /* Don't normalize before combining so as normals approach the direction,
507  * they have less effect (T46784). */
508 
509  /* combine the normals */
510  /* for flipped faces */
511  if (dot_v3v3(basis_nor_a, basis_nor_b) < 0.0f) {
512  negate_v3(basis_nor_b);
513  }
514  add_v3_v3v3(basis_nor, basis_nor_a, basis_nor_b);
515  }
516 #endif
517 
518  /* get third axis */
519  normalize_v3(basis_nor);
520  cross_v3_v3v3(basis_tmp, basis_dir, basis_nor);
521 
522  /* Try get the axis from surrounding faces, fallback to 'ortho_v3_v3' */
523  if (UNLIKELY(normalize_v3(basis_tmp) < eps)) {
524  /* vertex normals are directly opposite */
525 
526  /* find the loop with the lowest angle */
527  struct {
528  float nor[3];
529  float angle_cos;
530  } axis_pair[2];
531  int i;
532 
533  for (i = 0; i < 2; i++) {
534  BMIter liter;
535  BMLoop *l;
536 
537  zero_v2(axis_pair[i].nor);
538  axis_pair[i].angle_cos = -FLT_MAX;
539 
540  BM_ITER_ELEM (l, &liter, v_pair[i], BM_LOOPS_OF_VERT) {
541  float basis_dir_proj[3];
542  float angle_cos_test;
543 
544  /* project basis dir onto the normal to find its closest angle */
545  project_plane_normalized_v3_v3v3(basis_dir_proj, basis_dir, l->f->no);
546 
547  if (normalize_v3(basis_dir_proj) > eps) {
548  angle_cos_test = dot_v3v3(basis_dir_proj, basis_dir);
549 
550  if (angle_cos_test > axis_pair[i].angle_cos) {
551  axis_pair[i].angle_cos = angle_cos_test;
552  copy_v3_v3(axis_pair[i].nor, basis_dir_proj);
553  }
554  }
555  }
556  }
557 
558  /* create a new 'basis_nor' from the best direction.
559  * NOTE: we could add the directions,
560  * but this more often gives 45d rotated matrix, so just use the best one. */
561  copy_v3_v3(basis_nor, axis_pair[axis_pair[0].angle_cos < axis_pair[1].angle_cos].nor);
562  project_plane_normalized_v3_v3v3(basis_nor, basis_nor, basis_dir);
563 
564  cross_v3_v3v3(basis_tmp, basis_dir, basis_nor);
565 
566  /* last resort, pick _any_ ortho axis */
567  if (UNLIKELY(normalize_v3(basis_tmp) < eps)) {
568  ortho_v3_v3(basis_nor, basis_dir);
569  normalize_v3(basis_nor);
570  cross_v3_v3v3(basis_tmp, basis_dir, basis_nor);
571  normalize_v3(basis_tmp);
572  }
573  }
574 
575  copy_v3_v3(r_unit_mat[0], basis_tmp);
576  copy_v3_v3(r_unit_mat[1], basis_dir);
577  copy_v3_v3(r_unit_mat[2], basis_nor);
578  if (invert_m3(r_unit_mat) == false) {
579  unit_m3(r_unit_mat);
580  }
581 }
582 
584 {
585  BMOpSlot *op_verts_slot = BMO_slot_get(op->slots_in, "verts");
586 
587  PathContext pc;
588  PathLinkState state_best = {NULL};
589 
590  if (op_verts_slot->len != 2) {
591  /* fail! */
592  return;
593  }
594 
595  pc.bm_bmoflag = bm;
596  pc.v_a = ((BMVert **)op_verts_slot->data.p)[0];
597  pc.v_b = ((BMVert **)op_verts_slot->data.p)[1];
598 
599  /* fail! */
600  if (!(pc.v_a && pc.v_b)) {
601  return;
602  }
603 
604 #ifdef DEBUG_PRINT
605  printf("%s: v_a: %d\n", __func__, BM_elem_index_get(pc.v_a));
606  printf("%s: v_b: %d\n", __func__, BM_elem_index_get(pc.v_b));
607 #endif
608 
609  /* tag so we won't touch ever (typically hidden faces) */
612 
613  /* setup context */
614  {
615  pc.states = BLI_heapsimple_new();
616  pc.link_pool = BLI_mempool_create(sizeof(PathLink), 0, 512, BLI_MEMPOOL_NOP);
617  }
618 
619  /* calculate matrix */
620  {
622  pc.axis_sep = dot_m3_v3_row_x(pc.matrix, pc.v_a->co);
623  }
624 
625  /* add first vertex */
626  {
628  state = MEM_callocN(sizeof(*state), __func__);
629  state_link_add(&pc, state, (BMElem *)pc.v_a, NULL);
631  }
632 
633  while (!BLI_heapsimple_is_empty(pc.states)) {
634 
635 #ifdef DEBUG_PRINT
636  printf("\n%s: stepping %u\n", __func__, BLI_heapsimple_len(pc.states));
637 #endif
638 
639  while (!BLI_heapsimple_is_empty(pc.states)) {
641 
642  /* either we insert this into 'pc.states' or its freed */
643  bool continue_search;
644 
645  if (state->link_last->ele == (BMElem *)pc.v_b) {
646  /* pass, wait until all are found */
647 #ifdef DEBUG_PRINT
648  printf("%s: state %p loop found %.4f\n", __func__, state, state->dist);
649 #endif
650  state_best = *state;
651 
652  /* we're done, exit all loops */
654  continue_search = false;
655  }
656  else if (state_step(&pc, state)) {
657  continue_search = true;
658  }
659  else {
660  /* didn't reach the end, remove it,
661  * links are shared between states so just free the link_pool at the end */
662 
663 #ifdef DEBUG_PRINT
664  printf("%s: state %p removed\n", __func__, state);
665 #endif
666  continue_search = false;
667  }
668 
669  if (continue_search) {
671  }
672  else {
673  MEM_freeN(state);
674  }
675  }
676  }
677 
678  if (state_best.link_last) {
679  PathLink *link;
680 
681  /* find the best state */
682  link = state_best.link_last;
683  do {
684  if (link->ele->head.htype == BM_EDGE) {
685  BMEdge *e = (BMEdge *)link->ele;
686  BMVert *v_new;
687  float e_fac = state_calc_co_pair_fac(&pc, e->v1->co, e->v2->co);
688  v_new = BM_edge_split(bm, e, e->v1, NULL, e_fac);
690  }
691  else if (link->ele->head.htype == BM_VERT) {
692  BMVert *v = (BMVert *)link->ele;
694  }
695  else {
696  BLI_assert(0);
697  }
698  } while ((link = link->next));
699  }
700 
703 
705 
707 
708 #if 1
709  if (state_best.link_last) {
712  &op_sub,
713  0,
714  "connect_verts verts=%fv faces_exclude=%s check_degenerate=%b",
715  VERT_OUT,
716  op,
717  "faces_exclude",
718  true);
719  BMO_op_exec(bm, &op_sub);
720  BMO_slot_copy(&op_sub, slots_out, "edges.out", op, slots_out, "edges.out");
722  }
723 #endif
724 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
A min-heap / priority queue ADT.
void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
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)
uint BLI_heapsimple_len(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
void unit_m3(float m[3][3])
Definition: math_matrix.c:40
bool invert_m3(float R[3][3])
Definition: math_matrix.c:1171
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
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 float dot_m3_v3_row_x(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void copy_v3_v3(float r[3], const float a[3])
void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3])
Definition: math_vector.c:652
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
Definition: math_vector.c:29
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void ortho_v3_v3(float out[3], const float v[3])
Definition: math_vector.c:732
MINLINE void negate_v3(float r[3])
MINLINE void zero_v2(float r[2])
@ BLI_MEMPOOL_NOP
Definition: BLI_mempool.h:99
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
Definition: BLI_mempool.c:253
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
Definition: BLI_mempool.c:319
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:707
#define UNLIKELY(x)
#define ELEM(...)
_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
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_ITER_ELEM(ele, iter, data, itype)
@ BM_LOOPS_OF_VERT
@ BM_LOOPS_OF_EDGE
@ BM_EDGES_OF_VERT
ATTR_WARN_UNUSED_RESULT BMesh * bm
BMVert * BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac)
Edge Split.
Definition: bmesh_mods.c:448
void BMO_slot_buffer_flag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMO_FLAG_BUFFER.
#define BMO_vert_flag_enable(bm, e, oflag)
void BMO_op_exec(BMesh *bm, BMOperator *op)
BMESH OPSTACK EXEC OP.
#define BMO_slot_copy(op_src, slots_src, slot_name_src, op_dst, slots_dst, slot_name_dst)
bool BMO_op_initf(BMesh *bm, BMOperator *op, int flag, const char *fmt,...)
void BMO_op_finish(BMesh *bm, BMOperator *op)
BMESH OPSTACK FINISH OP.
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
#define ELE_TOUCH_TEST_VERT(v)
static int state_isect_co_exact(const PathContext *pc, const float co[3])
#define CONNECT_EPS
struct MinDistDir MinDistDir
#define VERT_EXCLUDE
static PathLinkState * state_dupe_add(PathLinkState *state, const PathLinkState *state_orig)
struct PathContext PathContext
#define FACE_WALK_TEST(f)
static int min_dist_dir_test(MinDistDir *mddir, const float dist_dir[3], const float dist_sq)
static PathLinkState * state_link_add_test(PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMElem *ele, BMElem *ele_from)
#define VERT_OUT
#define VERT_WALK_TEST(v)
#define FACE_EXCLUDE
static bool state_step(PathContext *pc, PathLinkState *state)
static PathLinkState * state_step__face_edges(PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMLoop *l_iter, BMLoop *l_last, MinDistDir *mddir)
void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
struct PathLinkState PathLinkState
static PathLinkState * state_step__face_verts(PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMLoop *l_iter, BMLoop *l_last, MinDistDir *mddir)
static float state_calc_co_pair_fac(const PathContext *pc, const float co_a[3], const float co_b[3])
static void min_dist_dir_update(MinDistDir *dist, const float dist_dir[3])
static bool state_link_find(const PathLinkState *state, BMElem *ele)
#define ELE_TOUCH_MARK(e)
#define ELE_TOUCH_TEST_EDGE(e)
static int state_isect_co_pair(const PathContext *pc, const float co_a[3], const float co_b[3])
struct PathLink PathLink
static void state_link_add(PathContext *pc, PathLinkState *state, BMElem *ele, BMElem *ele_from)
static void bm_vert_pair_to_matrix(BMVert *v_pair[2], float r_unit_mat[3][3])
#define MIN_DIST_DIR_INIT
static void state_calc_co_pair(const PathContext *pc, const float co_a[3], const float co_b[3], float r_co[3])
static double op_sub(double a, double b)
uint nor
const int state
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
IMETHOD Vector diff(const Vector &a, const Vector &b, double dt=1)
const btScalar eps
Definition: poly34.cpp:11
BMHeader head
Definition: bmesh_class.h:243
int len
Definition: bmesh_class.h:267
float no[3]
Definition: bmesh_class.h:271
char htype
Definition: bmesh_class.h:64
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
union BMOpSlot::@145 data
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
float co[3]
Definition: bmesh_class.h:87
float dist_min[2]
BLI_mempool * link_pool
float matrix[3][3]
BMesh * bm_bmoflag
HeapSimple * states
struct PathLink * link_last