Blender  V3.3
editmesh_bvh.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2010 Blender Foundation. All rights reserved. */
3 
8 #include "MEM_guardedalloc.h"
9 
10 #include "BLI_kdopbvh.h"
11 #include "BLI_math.h"
12 
13 #include "BKE_editmesh.h"
14 
15 #include "BKE_editmesh_bvh.h" /* own include */
16 
17 struct BMBVHTree {
19 
20  BMLoop *(*looptris)[3];
22 
24 
25  const float (*cos_cage)[3];
27 
28  int flag;
29 };
30 
32  int flag,
33  const float (*cos_cage)[3],
34  const bool cos_cage_free)
35 {
36  return BKE_bmbvh_new(em->bm, em->looptris, em->tottri, flag, cos_cage, cos_cage_free);
37 }
38 
40  BMLoop *(*looptris)[3],
41  int looptris_tot,
42  int flag,
43  const float (*cos_cage)[3],
44  const bool cos_cage_free,
45  bool (*test_fn)(BMFace *, void *user_data),
46  void *user_data)
47 {
48  /* could become argument */
49  const float epsilon = FLT_EPSILON * 2.0f;
50 
51  BMBVHTree *bmtree = MEM_callocN(sizeof(*bmtree), "BMBVHTree");
52  float cos[3][3];
53  int tottri;
54 
55  /* avoid testing every tri */
56  BMFace *f_test, *f_test_prev;
57  bool test_fn_ret;
58 
59  /* BKE_editmesh_looptri_calc() must be called already */
60  BLI_assert(looptris_tot != 0 || bm->totface == 0);
61 
62  if (cos_cage) {
64  }
65 
66  bmtree->looptris = looptris;
67  bmtree->looptris_tot = looptris_tot;
68  bmtree->bm = bm;
69  bmtree->cos_cage = cos_cage;
70  bmtree->cos_cage_free = cos_cage_free;
71  bmtree->flag = flag;
72 
73  if (test_fn) {
74  /* callback must do... */
76 
77  f_test_prev = NULL;
78  test_fn_ret = false;
79 
80  tottri = 0;
81  for (int i = 0; i < looptris_tot; i++) {
82  f_test = looptris[i][0]->f;
83  if (f_test != f_test_prev) {
84  test_fn_ret = test_fn(f_test, user_data);
85  f_test_prev = f_test;
86  }
87 
88  if (test_fn_ret) {
89  tottri++;
90  }
91  }
92  }
93  else {
94  tottri = looptris_tot;
95  }
96 
97  bmtree->tree = BLI_bvhtree_new(tottri, epsilon, 8, 8);
98 
99  f_test_prev = NULL;
100  test_fn_ret = false;
101 
102  for (int i = 0; i < looptris_tot; i++) {
103  if (test_fn) {
104  /* NOTE: the arrays won't align now! Take care. */
105  f_test = looptris[i][0]->f;
106  if (f_test != f_test_prev) {
107  test_fn_ret = test_fn(f_test, user_data);
108  f_test_prev = f_test;
109  }
110 
111  if (!test_fn_ret) {
112  continue;
113  }
114  }
115 
116  if (cos_cage) {
117  copy_v3_v3(cos[0], cos_cage[BM_elem_index_get(looptris[i][0]->v)]);
118  copy_v3_v3(cos[1], cos_cage[BM_elem_index_get(looptris[i][1]->v)]);
119  copy_v3_v3(cos[2], cos_cage[BM_elem_index_get(looptris[i][2]->v)]);
120  }
121  else {
122  copy_v3_v3(cos[0], looptris[i][0]->v->co);
123  copy_v3_v3(cos[1], looptris[i][1]->v->co);
124  copy_v3_v3(cos[2], looptris[i][2]->v->co);
125  }
126 
127  BLI_bvhtree_insert(bmtree->tree, i, (float *)cos, 3);
128  }
129 
130  BLI_bvhtree_balance(bmtree->tree);
131 
132  return bmtree;
133 }
134 
135 static bool bm_face_is_select(BMFace *f, void *UNUSED(user_data))
136 {
137  return (BM_elem_flag_test(f, BM_ELEM_SELECT) != 0);
138 }
139 
141 {
142  return (BM_elem_flag_test(f, BM_ELEM_HIDDEN) == 0);
143 }
144 
146  BMLoop *(*looptris)[3],
147  int looptris_tot,
148  int flag,
149  const float (*cos_cage)[3],
150  const bool cos_cage_free)
151 {
152  bool (*test_fn)(BMFace *, void *user_data);
153 
154  if (flag & BMBVH_RESPECT_SELECT) {
155  test_fn = bm_face_is_select;
156  }
157  else if (flag & BMBVH_RESPECT_HIDDEN) {
158  test_fn = bm_face_is_not_hidden;
159  }
160  else {
161  test_fn = NULL;
162  }
163 
165 
166  return BKE_bmbvh_new_ex(
167  bm, looptris, looptris_tot, flag, cos_cage, cos_cage_free, test_fn, NULL);
168 }
169 
171 {
172  BLI_bvhtree_free(bmtree->tree);
173 
174  if (bmtree->cos_cage && bmtree->cos_cage_free) {
175  MEM_freeN((void *)bmtree->cos_cage);
176  }
177 
178  MEM_freeN(bmtree);
179 }
180 
182 {
183  return bmtree->tree;
184 }
185 
186 /* -------------------------------------------------------------------- */
187 /* Utility BMesh cast/intersect functions */
188 
192 static void bmbvh_tri_from_face(const float *cos[3],
193  const BMLoop **ltri,
194  const float (*cos_cage)[3])
195 {
196  if (cos_cage == NULL) {
197  cos[0] = ltri[0]->v->co;
198  cos[1] = ltri[1]->v->co;
199  cos[2] = ltri[2]->v->co;
200  }
201  else {
202  cos[0] = cos_cage[BM_elem_index_get(ltri[0]->v)];
203  cos[1] = cos_cage[BM_elem_index_get(ltri[1]->v)];
204  cos[2] = cos_cage[BM_elem_index_get(ltri[2]->v)];
205  }
206 }
207 
208 /* Taken from `bvhutils.c`. */
209 
210 /* -------------------------------------------------------------------- */
211 /* BKE_bmbvh_ray_cast */
212 
214  /* from the bmtree */
215  const BMLoop *(*looptris)[3];
216  const float (*cos_cage)[3];
217 
218  /* from the hit */
219  float uv[2];
220 };
221 
223  struct RayCastUserData *bmcb_data,
224  const BVHTreeRayHit *hit,
225  float *r_dist,
226  float r_hitout[3],
227  float r_cagehit[3])
228 {
229  if (r_hitout) {
230  if (bmtree->flag & BMBVH_RETURN_ORIG) {
231  BMLoop **ltri = bmtree->looptris[hit->index];
232  interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, bmcb_data->uv);
233  }
234  else {
235  copy_v3_v3(r_hitout, hit->co);
236  }
237 
238  if (r_cagehit) {
239  copy_v3_v3(r_cagehit, hit->co);
240  }
241  }
242 
243  if (r_dist) {
244  *r_dist = hit->dist;
245  }
246 
247  return bmtree->looptris[hit->index][0]->f;
248 }
249 
250 static void bmbvh_ray_cast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
251 {
252  struct RayCastUserData *bmcb_data = userdata;
253  const BMLoop **ltri = bmcb_data->looptris[index];
254  float dist, uv[2];
255  const float *tri_cos[3];
256  bool isect;
257 
258  bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
259 
260  isect =
261  (ray->radius > 0.0f ?
263  ray->direction,
264  tri_cos[0],
265  tri_cos[1],
266  tri_cos[2],
267  &dist,
268  uv,
269  ray->radius) :
270 #ifdef USE_KDOPBVH_WATERTIGHT
272  ray->origin, ray->isect_precalc, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
273 #else
275  ray->origin, ray->direction, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
276 #endif
277 
278  if (isect && dist < hit->dist) {
279  hit->dist = dist;
280  hit->index = index;
281 
282  copy_v3_v3(hit->no, ltri[0]->f->no);
283 
284  madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
285 
286  copy_v2_v2(bmcb_data->uv, uv);
287  }
288 }
289 
291  const float co[3],
292  const float dir[3],
293  const float radius,
294  float *r_dist,
295  float r_hitout[3],
296  float r_cagehit[3])
297 {
298  BVHTreeRayHit hit;
299  struct RayCastUserData bmcb_data;
300  const float dist = r_dist ? *r_dist : FLT_MAX;
301 
302  if (bmtree->cos_cage) {
303  BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
304  }
305 
306  hit.dist = dist;
307  hit.index = -1;
308 
309  /* ok to leave 'uv' uninitialized */
310  bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
311  bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
312 
313  BLI_bvhtree_ray_cast(bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb, &bmcb_data);
314 
315  if (hit.index != -1 && hit.dist != dist) {
316  return bmbvh_ray_cast_handle_hit(bmtree, &bmcb_data, &hit, r_dist, r_hitout, r_cagehit);
317  }
318 
319  return NULL;
320 }
321 
322 /* -------------------------------------------------------------------- */
323 /* bmbvh_ray_cast_cb_filter */
324 
325 /* Same as BKE_bmbvh_ray_cast but takes a callback to filter out faces.
326  */
327 
329  struct RayCastUserData bmcb_data;
330 
333 };
334 
335 static void bmbvh_ray_cast_cb_filter(void *userdata,
336  int index,
337  const BVHTreeRay *ray,
338  BVHTreeRayHit *hit)
339 {
340  struct RayCastUserData_Filter *bmcb_data_filter = userdata;
341  struct RayCastUserData *bmcb_data = &bmcb_data_filter->bmcb_data;
342  const BMLoop **ltri = bmcb_data->looptris[index];
343  if (bmcb_data_filter->filter_cb(ltri[0]->f, bmcb_data_filter->filter_userdata)) {
344  bmbvh_ray_cast_cb(bmcb_data, index, ray, hit);
345  }
346 }
347 
349  const float co[3],
350  const float dir[3],
351  const float radius,
352  float *r_dist,
353  float r_hitout[3],
354  float r_cagehit[3],
355  BMBVHTree_FaceFilter filter_cb,
356  void *filter_userdata)
357 {
358  BVHTreeRayHit hit;
359  struct RayCastUserData_Filter bmcb_data_filter;
360  struct RayCastUserData *bmcb_data = &bmcb_data_filter.bmcb_data;
361 
362  const float dist = r_dist ? *r_dist : FLT_MAX;
363 
364  bmcb_data_filter.filter_cb = filter_cb;
365  bmcb_data_filter.filter_userdata = filter_userdata;
366 
367  if (bmtree->cos_cage) {
368  BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
369  }
370 
371  hit.dist = dist;
372  hit.index = -1;
373 
374  /* ok to leave 'uv' uninitialized */
375  bmcb_data->looptris = (const BMLoop *(*)[3])bmtree->looptris;
376  bmcb_data->cos_cage = (const float(*)[3])bmtree->cos_cage;
377 
379  bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb_filter, &bmcb_data_filter);
380  if (hit.index != -1 && hit.dist != dist) {
381  return bmbvh_ray_cast_handle_hit(bmtree, bmcb_data, &hit, r_dist, r_hitout, r_cagehit);
382  }
383 
384  return NULL;
385 }
386 
387 /* -------------------------------------------------------------------- */
388 /* BKE_bmbvh_find_vert_closest */
389 
391  /* from the bmtree */
392  const BMLoop *(*looptris)[3];
393  const float (*cos_cage)[3];
394 
395  /* from the hit */
396  float dist_max_sq;
398 };
399 
400 static void bmbvh_find_vert_closest_cb(void *userdata,
401  int index,
402  const float co[3],
403  BVHTreeNearest *hit)
404 {
405  struct VertSearchUserData *bmcb_data = userdata;
406  const BMLoop **ltri = bmcb_data->looptris[index];
407  const float dist_max_sq = bmcb_data->dist_max_sq;
408 
409  const float *tri_cos[3];
410  bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
411 
412  for (int i = 0; i < 3; i++) {
413  const float dist_sq = len_squared_v3v3(co, tri_cos[i]);
414  if (dist_sq < hit->dist_sq && dist_sq < dist_max_sq) {
415  copy_v3_v3(hit->co, tri_cos[i]);
416  /* XXX, normal ignores cage */
417  copy_v3_v3(hit->no, ltri[i]->v->no);
418  hit->dist_sq = dist_sq;
419  hit->index = index;
420  bmcb_data->index_tri = i;
421  }
422  }
423 }
424 
425 BMVert *BKE_bmbvh_find_vert_closest(BMBVHTree *bmtree, const float co[3], const float dist_max)
426 {
427  BVHTreeNearest hit;
428  struct VertSearchUserData bmcb_data;
429  const float dist_max_sq = dist_max * dist_max;
430 
431  if (bmtree->cos_cage) {
432  BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
433  }
434 
435  hit.dist_sq = dist_max_sq;
436  hit.index = -1;
437 
438  bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
439  bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
440  bmcb_data.dist_max_sq = dist_max_sq;
441 
442  BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_vert_closest_cb, &bmcb_data);
443  if (hit.index != -1) {
444  BMLoop **ltri = bmtree->looptris[hit.index];
445  return ltri[bmcb_data.index_tri]->v;
446  }
447 
448  return NULL;
449 }
450 
452  /* from the bmtree */
453  const BMLoop *(*looptris)[3];
454  const float (*cos_cage)[3];
455 
456  /* from the hit */
457  float dist_max_sq;
458 };
459 
460 static void bmbvh_find_face_closest_cb(void *userdata,
461  int index,
462  const float co[3],
463  BVHTreeNearest *hit)
464 {
465  struct FaceSearchUserData *bmcb_data = userdata;
466  const BMLoop **ltri = bmcb_data->looptris[index];
467  const float dist_max_sq = bmcb_data->dist_max_sq;
468 
469  const float *tri_cos[3];
470 
471  bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
472 
473  float co_close[3];
474  closest_on_tri_to_point_v3(co_close, co, UNPACK3(tri_cos));
475  const float dist_sq = len_squared_v3v3(co, co_close);
476  if (dist_sq < hit->dist_sq && dist_sq < dist_max_sq) {
477  /* XXX, normal ignores cage */
478  copy_v3_v3(hit->no, ltri[0]->f->no);
479  hit->dist_sq = dist_sq;
480  hit->index = index;
481  }
482 }
483 
485  const float co[3],
486  const float dist_max)
487 {
488  BVHTreeNearest hit;
489  struct FaceSearchUserData bmcb_data;
490  const float dist_max_sq = dist_max * dist_max;
491 
492  if (bmtree->cos_cage) {
493  BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
494  }
495 
496  hit.dist_sq = dist_max_sq;
497  hit.index = -1;
498 
499  bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
500  bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
501  bmcb_data.dist_max_sq = dist_max_sq;
502 
503  BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_face_closest_cb, &bmcb_data);
504  if (hit.index != -1) {
505  BMLoop **ltri = bmtree->looptris[hit.index];
506  return ltri[0]->f;
507  }
508 
509  return NULL;
510 }
511 
512 /* -------------------------------------------------------------------- */
513 /* BKE_bmbvh_overlap */
514 
516  const BMBVHTree *tree_pair[2];
517  float epsilon;
518 };
519 
520 static bool bmbvh_overlap_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
521 {
522  struct BMBVHTree_OverlapData *data = userdata;
523  const BMBVHTree *bmtree_a = data->tree_pair[0];
524  const BMBVHTree *bmtree_b = data->tree_pair[1];
525 
526  BMLoop **tri_a = bmtree_a->looptris[index_a];
527  BMLoop **tri_b = bmtree_b->looptris[index_b];
528  const float *tri_a_co[3] = {tri_a[0]->v->co, tri_a[1]->v->co, tri_a[2]->v->co};
529  const float *tri_b_co[3] = {tri_b[0]->v->co, tri_b[1]->v->co, tri_b[2]->v->co};
530  float ix_pair[2][3];
531  int verts_shared = 0;
532 
533  if (bmtree_a->looptris == bmtree_b->looptris) {
534  if (UNLIKELY(tri_a[0]->f == tri_b[0]->f)) {
535  return false;
536  }
537 
538  verts_shared = (ELEM(tri_a_co[0], UNPACK3(tri_b_co)) + ELEM(tri_a_co[1], UNPACK3(tri_b_co)) +
539  ELEM(tri_a_co[2], UNPACK3(tri_b_co)));
540 
541  /* if 2 points are shared, bail out */
542  if (verts_shared >= 2) {
543  return false;
544  }
545  }
546 
547  return (isect_tri_tri_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1]) &&
548  /* if we share a vertex, check the intersection isn't a 'point' */
549  ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon)));
550 }
551 
553  const BMBVHTree *bmtree_b,
554  unsigned int *r_overlap_tot)
555 {
557 
558  data.tree_pair[0] = bmtree_a;
559  data.tree_pair[1] = bmtree_b;
560  data.epsilon = max_ff(BLI_bvhtree_get_epsilon(bmtree_a->tree),
561  BLI_bvhtree_get_epsilon(bmtree_b->tree));
562 
563  return BLI_bvhtree_overlap(
564  bmtree_a->tree, bmtree_b->tree, r_overlap_tot, bmbvh_overlap_cb, &data);
565 }
566 
567 static bool bmbvh_overlap_self_cb(void *userdata, int index_a, int index_b, int thread)
568 {
569  if (index_a < index_b) {
570  return bmbvh_overlap_cb(userdata, index_a, index_b, thread);
571  }
572  return false;
573 }
574 
575 BVHTreeOverlap *BKE_bmbvh_overlap_self(const BMBVHTree *bmtree, unsigned int *r_overlap_tot)
576 {
578 
579  data.tree_pair[0] = bmtree;
580  data.tree_pair[1] = bmtree;
581  data.epsilon = BLI_bvhtree_get_epsilon(bmtree->tree);
582 
583  return BLI_bvhtree_overlap(
584  bmtree->tree, bmtree->tree, r_overlap_tot, bmbvh_overlap_self_cb, &data);
585 }
typedef float(TangentPoint)[2]
bool(* BMBVHTree_FaceFilter)(struct BMFace *f, void *userdata)
@ BMBVH_RETURN_ORIG
@ BMBVH_RESPECT_HIDDEN
@ BMBVH_RESPECT_SELECT
#define BLI_assert(a)
Definition: BLI_assert.h:46
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1363
void BLI_bvhtree_balance(BVHTree *tree)
Definition: BLI_kdopbvh.c:937
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
Definition: BLI_kdopbvh.c:854
void BLI_bvhtree_free(BVHTree *tree)
Definition: BLI_kdopbvh.c:926
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
Definition: BLI_kdopbvh.c:979
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1044
int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1942
int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1616
MINLINE float max_ff(float a, float b)
bool isect_ray_tri_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
Definition: math_geom.c:1662
bool isect_ray_tri_watertight_v3(const float ray_origin[3], const struct IsectRayPrecalc *isect_precalc, const float v0[3], const float v1[3], const float v2[3], float *r_dist, float r_uv[2])
Definition: math_geom.c:1811
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:980
bool isect_tri_tri_v3(const float t_a0[3], const float t_a1[3], const float t_a2[3], const float t_b0[3], const float t_b1[3], const float t_b2[3], float r_i1[3], float r_i2[3])
Definition: math_geom.c:2367
bool isect_ray_tri_epsilon_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float epsilon)
Definition: math_geom.c:1735
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void copy_v2_v2(float r[2], const float a[2])
MINLINE void copy_v3_v3(float r[3], const float a[3])
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
void interp_v3_v3v3v3_uv(float p[3], const float v1[3], const float v2[3], const float v3[3], const float uv[2])
Definition: math_vector.c:202
#define UNUSED(x)
#define UNPACK3(a)
#define UNLIKELY(x)
#define ELEM(...)
Read Guarded memory(de)allocation.
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_ELEM_HIDDEN
Definition: bmesh_class.h:472
@ BM_ELEM_SELECT
Definition: bmesh_class.h:471
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:446
ATTR_WARN_UNUSED_RESULT const BMVert * v
Definition: thread.h:34
void * user_data
void BKE_bmbvh_free(BMBVHTree *bmtree)
Definition: editmesh_bvh.c:170
BVHTreeOverlap * BKE_bmbvh_overlap_self(const BMBVHTree *bmtree, unsigned int *r_overlap_tot)
Definition: editmesh_bvh.c:575
static bool bmbvh_overlap_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
Definition: editmesh_bvh.c:520
BMBVHTree * BKE_bmbvh_new(BMesh *bm, BMLoop *(*looptris)[3], int looptris_tot, int flag, const float(*cos_cage)[3], const bool cos_cage_free)
Definition: editmesh_bvh.c:145
BVHTreeOverlap * BKE_bmbvh_overlap(const BMBVHTree *bmtree_a, const BMBVHTree *bmtree_b, unsigned int *r_overlap_tot)
Definition: editmesh_bvh.c:552
static void bmbvh_ray_cast_cb_filter(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: editmesh_bvh.c:335
BMFace * BKE_bmbvh_ray_cast(BMBVHTree *bmtree, const float co[3], const float dir[3], const float radius, float *r_dist, float r_hitout[3], float r_cagehit[3])
Definition: editmesh_bvh.c:290
static bool bm_face_is_select(BMFace *f, void *UNUSED(user_data))
Definition: editmesh_bvh.c:135
static bool bm_face_is_not_hidden(BMFace *f, void *UNUSED(user_data))
Definition: editmesh_bvh.c:140
static bool bmbvh_overlap_self_cb(void *userdata, int index_a, int index_b, int thread)
Definition: editmesh_bvh.c:567
BMBVHTree * BKE_bmbvh_new_from_editmesh(BMEditMesh *em, int flag, const float(*cos_cage)[3], const bool cos_cage_free)
Definition: editmesh_bvh.c:31
BVHTree * BKE_bmbvh_tree_get(BMBVHTree *bmtree)
Definition: editmesh_bvh.c:181
BMBVHTree * BKE_bmbvh_new_ex(BMesh *bm, BMLoop *(*looptris)[3], int looptris_tot, int flag, const float(*cos_cage)[3], const bool cos_cage_free, bool(*test_fn)(BMFace *, void *user_data), void *user_data)
Definition: editmesh_bvh.c:39
BMVert * BKE_bmbvh_find_vert_closest(BMBVHTree *bmtree, const float co[3], const float dist_max)
Definition: editmesh_bvh.c:425
static void bmbvh_ray_cast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: editmesh_bvh.c:250
struct BMFace * BKE_bmbvh_find_face_closest(BMBVHTree *bmtree, const float co[3], const float dist_max)
Definition: editmesh_bvh.c:484
static BMFace * bmbvh_ray_cast_handle_hit(BMBVHTree *bmtree, struct RayCastUserData *bmcb_data, const BVHTreeRayHit *hit, float *r_dist, float r_hitout[3], float r_cagehit[3])
Definition: editmesh_bvh.c:222
static void bmbvh_tri_from_face(const float *cos[3], const BMLoop **ltri, const float(*cos_cage)[3])
Definition: editmesh_bvh.c:192
static void bmbvh_find_face_closest_cb(void *userdata, int index, const float co[3], BVHTreeNearest *hit)
Definition: editmesh_bvh.c:460
BMFace * BKE_bmbvh_ray_cast_filter(BMBVHTree *bmtree, const float co[3], const float dir[3], const float radius, float *r_dist, float r_hitout[3], float r_cagehit[3], BMBVHTree_FaceFilter filter_cb, void *filter_userdata)
Definition: editmesh_bvh.c:348
static void bmbvh_find_vert_closest_cb(void *userdata, int index, const float co[3], BVHTreeNearest *hit)
Definition: editmesh_bvh.c:400
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
INLINE Rall1d< T, V, S > cos(const Rall1d< T, V, S > &arg)
Definition: rall1d.h:319
static double epsilon
const BMBVHTree * tree_pair[2]
Definition: editmesh_bvh.c:516
BMLoop *(* looptris)[3]
Definition: editmesh_bvh.c:20
bool cos_cage_free
Definition: editmesh_bvh.c:26
BMesh * bm
Definition: editmesh_bvh.c:23
BVHTree * tree
Definition: editmesh_bvh.c:18
int looptris_tot
Definition: editmesh_bvh.c:21
const float(* cos_cage)[3]
Definition: editmesh_bvh.c:25
struct BMLoop *(* looptris)[3]
Definition: BKE_editmesh.h:48
struct BMesh * bm
Definition: BKE_editmesh.h:40
float no[3]
Definition: bmesh_class.h:271
struct BMVert * v
Definition: bmesh_class.h:153
struct BMFace * f
Definition: bmesh_class.h:171
float co[3]
Definition: bmesh_class.h:87
float no[3]
Definition: bmesh_class.h:88
char elem_index_dirty
Definition: bmesh_class.h:305
int totface
Definition: bmesh_class.h:297
float co[3]
Definition: BLI_kdopbvh.h:43
float no[3]
Definition: BLI_kdopbvh.h:46
float co[3]
Definition: BLI_kdopbvh.h:68
float no[3]
Definition: BLI_kdopbvh.h:70
float origin[3]
Definition: BLI_kdopbvh.h:54
struct IsectRayPrecalc * isect_precalc
Definition: BLI_kdopbvh.h:60
float direction[3]
Definition: BLI_kdopbvh.h:56
float radius
Definition: BLI_kdopbvh.h:58
const BMLoop *(* looptris)[3]
Definition: editmesh_bvh.c:453
const float(* cos_cage)[3]
Definition: editmesh_bvh.c:454
struct RayCastUserData bmcb_data
Definition: editmesh_bvh.c:329
BMBVHTree_FaceFilter filter_cb
Definition: editmesh_bvh.c:331
const float(* cos_cage)[3]
Definition: editmesh_bvh.c:216
const BMLoop *(* looptris)[3]
Definition: editmesh_bvh.c:215
const float(* cos_cage)[3]
Definition: editmesh_bvh.c:393
const BMLoop *(* looptris)[3]
Definition: editmesh_bvh.c:392