1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 *
16 * The Original Code is Copyright (C) 2010 by Blender Foundation.
17 * All rights reserved.
18 */
19
20 /** \file
21 * \ingroup bke
22 */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_kdopbvh.h"
27 #include "BLI_math.h"
28
29 #include "BKE_editmesh.h"
30
31 #include "BKE_editmesh_bvh.h" /* own include */
32
33 struct BMBVHTree {
34 BVHTree *tree;
35
36 BMLoop *(*looptris)[3];
37 int looptris_tot;
38
39 BMesh *bm;
40
41 const float (*cos_cage)[3];
42 bool cos_cage_free;
43
44 int flag;
45 };
46
BKE_bmbvh_new_from_editmesh(BMEditMesh * em,int flag,const float (* cos_cage)[3],const bool cos_cage_free)47 BMBVHTree *BKE_bmbvh_new_from_editmesh(BMEditMesh *em,
48 int flag,
49 const float (*cos_cage)[3],
50 const bool cos_cage_free)
51 {
52 return BKE_bmbvh_new(em->bm, em->looptris, em->tottri, flag, cos_cage, cos_cage_free);
53 }
54
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)55 BMBVHTree *BKE_bmbvh_new_ex(BMesh *bm,
56 BMLoop *(*looptris)[3],
57 int looptris_tot,
58 int flag,
59 const float (*cos_cage)[3],
60 const bool cos_cage_free,
61 bool (*test_fn)(BMFace *, void *user_data),
62 void *user_data)
63 {
64 /* could become argument */
65 const float epsilon = FLT_EPSILON * 2.0f;
66
67 BMBVHTree *bmtree = MEM_callocN(sizeof(*bmtree), "BMBVHTree");
68 float cos[3][3];
69 int tottri;
70
71 /* avoid testing every tri */
72 BMFace *f_test, *f_test_prev;
73 bool test_fn_ret;
74
75 /* BKE_editmesh_looptri_calc() must be called already */
76 BLI_assert(looptris_tot != 0 || bm->totface == 0);
77
78 if (cos_cage) {
79 BM_mesh_elem_index_ensure(bm, BM_VERT);
80 }
81
82 bmtree->looptris = looptris;
83 bmtree->looptris_tot = looptris_tot;
84 bmtree->bm = bm;
85 bmtree->cos_cage = cos_cage;
86 bmtree->cos_cage_free = cos_cage_free;
87 bmtree->flag = flag;
88
89 if (test_fn) {
90 /* callback must do... */
91 BLI_assert(!(flag & (BMBVH_RESPECT_SELECT | BMBVH_RESPECT_HIDDEN)));
92
93 f_test_prev = NULL;
94 test_fn_ret = false;
95
96 tottri = 0;
97 for (int i = 0; i < looptris_tot; i++) {
98 f_test = looptris[i][0]->f;
99 if (f_test != f_test_prev) {
100 test_fn_ret = test_fn(f_test, user_data);
101 f_test_prev = f_test;
102 }
103
104 if (test_fn_ret) {
105 tottri++;
106 }
107 }
108 }
109 else {
110 tottri = looptris_tot;
111 }
112
113 bmtree->tree = BLI_bvhtree_new(tottri, epsilon, 8, 8);
114
115 f_test_prev = NULL;
116 test_fn_ret = false;
117
118 for (int i = 0; i < looptris_tot; i++) {
119 if (test_fn) {
120 /* note, the arrays wont align now! take care */
121 f_test = looptris[i][0]->f;
122 if (f_test != f_test_prev) {
123 test_fn_ret = test_fn(f_test, user_data);
124 f_test_prev = f_test;
125 }
126
127 if (!test_fn_ret) {
128 continue;
129 }
130 }
131
132 if (cos_cage) {
133 copy_v3_v3(cos[0], cos_cage[BM_elem_index_get(looptris[i][0]->v)]);
134 copy_v3_v3(cos[1], cos_cage[BM_elem_index_get(looptris[i][1]->v)]);
135 copy_v3_v3(cos[2], cos_cage[BM_elem_index_get(looptris[i][2]->v)]);
136 }
137 else {
138 copy_v3_v3(cos[0], looptris[i][0]->v->co);
139 copy_v3_v3(cos[1], looptris[i][1]->v->co);
140 copy_v3_v3(cos[2], looptris[i][2]->v->co);
141 }
142
143 BLI_bvhtree_insert(bmtree->tree, i, (float *)cos, 3);
144 }
145
146 BLI_bvhtree_balance(bmtree->tree);
147
148 return bmtree;
149 }
150
bm_face_is_select(BMFace * f,void * UNUSED (user_data))151 static bool bm_face_is_select(BMFace *f, void *UNUSED(user_data))
152 {
153 return (BM_elem_flag_test(f, BM_ELEM_SELECT) != 0);
154 }
155
bm_face_is_not_hidden(BMFace * f,void * UNUSED (user_data))156 static bool bm_face_is_not_hidden(BMFace *f, void *UNUSED(user_data))
157 {
158 return (BM_elem_flag_test(f, BM_ELEM_HIDDEN) == 0);
159 }
160
BKE_bmbvh_new(BMesh * bm,BMLoop * (* looptris)[3],int looptris_tot,int flag,const float (* cos_cage)[3],const bool cos_cage_free)161 BMBVHTree *BKE_bmbvh_new(BMesh *bm,
162 BMLoop *(*looptris)[3],
163 int looptris_tot,
164 int flag,
165 const float (*cos_cage)[3],
166 const bool cos_cage_free)
167 {
168 bool (*test_fn)(BMFace *, void *user_data);
169
170 if (flag & BMBVH_RESPECT_SELECT) {
171 test_fn = bm_face_is_select;
172 }
173 else if (flag & BMBVH_RESPECT_HIDDEN) {
174 test_fn = bm_face_is_not_hidden;
175 }
176 else {
177 test_fn = NULL;
178 }
179
180 flag &= ~(BMBVH_RESPECT_SELECT | BMBVH_RESPECT_HIDDEN);
181
182 return BKE_bmbvh_new_ex(
183 bm, looptris, looptris_tot, flag, cos_cage, cos_cage_free, test_fn, NULL);
184 }
185
BKE_bmbvh_free(BMBVHTree * bmtree)186 void BKE_bmbvh_free(BMBVHTree *bmtree)
187 {
188 BLI_bvhtree_free(bmtree->tree);
189
190 if (bmtree->cos_cage && bmtree->cos_cage_free) {
191 MEM_freeN((void *)bmtree->cos_cage);
192 }
193
194 MEM_freeN(bmtree);
195 }
196
BKE_bmbvh_tree_get(BMBVHTree * bmtree)197 BVHTree *BKE_bmbvh_tree_get(BMBVHTree *bmtree)
198 {
199 return bmtree->tree;
200 }
201
202 /* -------------------------------------------------------------------- */
203 /* Utility BMesh cast/intersect functions */
204
205 /**
206 * Return the coords from a triangle.
207 */
bmbvh_tri_from_face(const float * cos[3],const BMLoop ** ltri,const float (* cos_cage)[3])208 static void bmbvh_tri_from_face(const float *cos[3],
209 const BMLoop **ltri,
210 const float (*cos_cage)[3])
211 {
212 if (cos_cage == NULL) {
213 cos[0] = ltri[0]->v->co;
214 cos[1] = ltri[1]->v->co;
215 cos[2] = ltri[2]->v->co;
216 }
217 else {
218 cos[0] = cos_cage[BM_elem_index_get(ltri[0]->v)];
219 cos[1] = cos_cage[BM_elem_index_get(ltri[1]->v)];
220 cos[2] = cos_cage[BM_elem_index_get(ltri[2]->v)];
221 }
222 }
223
224 /* taken from bvhutils.c */
225
226 /* -------------------------------------------------------------------- */
227 /* BKE_bmbvh_ray_cast */
228
229 struct RayCastUserData {
230 /* from the bmtree */
231 const BMLoop *(*looptris)[3];
232 const float (*cos_cage)[3];
233
234 /* from the hit */
235 float uv[2];
236 };
237
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])238 static BMFace *bmbvh_ray_cast_handle_hit(BMBVHTree *bmtree,
239 struct RayCastUserData *bmcb_data,
240 const BVHTreeRayHit *hit,
241 float *r_dist,
242 float r_hitout[3],
243 float r_cagehit[3])
244 {
245 if (r_hitout) {
246 if (bmtree->flag & BMBVH_RETURN_ORIG) {
247 BMLoop **ltri = bmtree->looptris[hit->index];
248 interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, bmcb_data->uv);
249 }
250 else {
251 copy_v3_v3(r_hitout, hit->co);
252 }
253
254 if (r_cagehit) {
255 copy_v3_v3(r_cagehit, hit->co);
256 }
257 }
258
259 if (r_dist) {
260 *r_dist = hit->dist;
261 }
262
263 return bmtree->looptris[hit->index][0]->f;
264 }
265
bmbvh_ray_cast_cb(void * userdata,int index,const BVHTreeRay * ray,BVHTreeRayHit * hit)266 static void bmbvh_ray_cast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
267 {
268 struct RayCastUserData *bmcb_data = userdata;
269 const BMLoop **ltri = bmcb_data->looptris[index];
270 float dist, uv[2];
271 const float *tri_cos[3];
272 bool isect;
273
274 bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
275
276 isect =
277 (ray->radius > 0.0f ?
278 isect_ray_tri_epsilon_v3(ray->origin,
279 ray->direction,
280 tri_cos[0],
281 tri_cos[1],
282 tri_cos[2],
283 &dist,
284 uv,
285 ray->radius) :
286 #ifdef USE_KDOPBVH_WATERTIGHT
287 isect_ray_tri_watertight_v3(
288 ray->origin, ray->isect_precalc, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
289 #else
290 isect_ray_tri_v3(
291 ray->origin, ray->direction, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
292 #endif
293
294 if (isect && dist < hit->dist) {
295 hit->dist = dist;
296 hit->index = index;
297
298 copy_v3_v3(hit->no, ltri[0]->f->no);
299
300 madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
301
302 copy_v2_v2(bmcb_data->uv, uv);
303 }
304 }
305
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])306 BMFace *BKE_bmbvh_ray_cast(BMBVHTree *bmtree,
307 const float co[3],
308 const float dir[3],
309 const float radius,
310 float *r_dist,
311 float r_hitout[3],
312 float r_cagehit[3])
313 {
314 BVHTreeRayHit hit;
315 struct RayCastUserData bmcb_data;
316 const float dist = r_dist ? *r_dist : FLT_MAX;
317
318 if (bmtree->cos_cage) {
319 BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
320 }
321
322 hit.dist = dist;
323 hit.index = -1;
324
325 /* ok to leave 'uv' uninitialized */
326 bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
327 bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
328
329 BLI_bvhtree_ray_cast(bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb, &bmcb_data);
330
331 if (hit.index != -1 && hit.dist != dist) {
332 return bmbvh_ray_cast_handle_hit(bmtree, &bmcb_data, &hit, r_dist, r_hitout, r_cagehit);
333 }
334
335 return NULL;
336 }
337
338 /* -------------------------------------------------------------------- */
339 /* bmbvh_ray_cast_cb_filter */
340
341 /* Same as BKE_bmbvh_ray_cast but takes a callback to filter out faces.
342 */
343
344 struct RayCastUserData_Filter {
345 struct RayCastUserData bmcb_data;
346
347 BMBVHTree_FaceFilter filter_cb;
348 void *filter_userdata;
349 };
350
bmbvh_ray_cast_cb_filter(void * userdata,int index,const BVHTreeRay * ray,BVHTreeRayHit * hit)351 static void bmbvh_ray_cast_cb_filter(void *userdata,
352 int index,
353 const BVHTreeRay *ray,
354 BVHTreeRayHit *hit)
355 {
356 struct RayCastUserData_Filter *bmcb_data_filter = userdata;
357 struct RayCastUserData *bmcb_data = &bmcb_data_filter->bmcb_data;
358 const BMLoop **ltri = bmcb_data->looptris[index];
359 if (bmcb_data_filter->filter_cb(ltri[0]->f, bmcb_data_filter->filter_userdata)) {
360 bmbvh_ray_cast_cb(bmcb_data, index, ray, hit);
361 }
362 }
363
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)364 BMFace *BKE_bmbvh_ray_cast_filter(BMBVHTree *bmtree,
365 const float co[3],
366 const float dir[3],
367 const float radius,
368 float *r_dist,
369 float r_hitout[3],
370 float r_cagehit[3],
371 BMBVHTree_FaceFilter filter_cb,
372 void *filter_userdata)
373 {
374 BVHTreeRayHit hit;
375 struct RayCastUserData_Filter bmcb_data_filter;
376 struct RayCastUserData *bmcb_data = &bmcb_data_filter.bmcb_data;
377
378 const float dist = r_dist ? *r_dist : FLT_MAX;
379
380 bmcb_data_filter.filter_cb = filter_cb;
381 bmcb_data_filter.filter_userdata = filter_userdata;
382
383 if (bmtree->cos_cage) {
384 BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
385 }
386
387 hit.dist = dist;
388 hit.index = -1;
389
390 /* ok to leave 'uv' uninitialized */
391 bmcb_data->looptris = (const BMLoop *(*)[3])bmtree->looptris;
392 bmcb_data->cos_cage = (const float(*)[3])bmtree->cos_cage;
393
394 BLI_bvhtree_ray_cast(
395 bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb_filter, &bmcb_data_filter);
396 if (hit.index != -1 && hit.dist != dist) {
397 return bmbvh_ray_cast_handle_hit(bmtree, bmcb_data, &hit, r_dist, r_hitout, r_cagehit);
398 }
399
400 return NULL;
401 }
402
403 /* -------------------------------------------------------------------- */
404 /* BKE_bmbvh_find_vert_closest */
405
406 struct VertSearchUserData {
407 /* from the bmtree */
408 const BMLoop *(*looptris)[3];
409 const float (*cos_cage)[3];
410
411 /* from the hit */
412 float dist_max_sq;
413 int index_tri;
414 };
415
bmbvh_find_vert_closest_cb(void * userdata,int index,const float co[3],BVHTreeNearest * hit)416 static void bmbvh_find_vert_closest_cb(void *userdata,
417 int index,
418 const float co[3],
419 BVHTreeNearest *hit)
420 {
421 struct VertSearchUserData *bmcb_data = userdata;
422 const BMLoop **ltri = bmcb_data->looptris[index];
423 const float dist_max_sq = bmcb_data->dist_max_sq;
424
425 const float *tri_cos[3];
426 bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
427
428 for (int i = 0; i < 3; i++) {
429 const float dist_sq = len_squared_v3v3(co, tri_cos[i]);
430 if (dist_sq < hit->dist_sq && dist_sq < dist_max_sq) {
431 copy_v3_v3(hit->co, tri_cos[i]);
432 /* XXX, normal ignores cage */
433 copy_v3_v3(hit->no, ltri[i]->v->no);
434 hit->dist_sq = dist_sq;
435 hit->index = index;
436 bmcb_data->index_tri = i;
437 }
438 }
439 }
440
BKE_bmbvh_find_vert_closest(BMBVHTree * bmtree,const float co[3],const float dist_max)441 BMVert *BKE_bmbvh_find_vert_closest(BMBVHTree *bmtree, const float co[3], const float dist_max)
442 {
443 BVHTreeNearest hit;
444 struct VertSearchUserData bmcb_data;
445 const float dist_max_sq = dist_max * dist_max;
446
447 if (bmtree->cos_cage) {
448 BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
449 }
450
451 hit.dist_sq = dist_max_sq;
452 hit.index = -1;
453
454 bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
455 bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
456 bmcb_data.dist_max_sq = dist_max_sq;
457
458 BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_vert_closest_cb, &bmcb_data);
459 if (hit.index != -1) {
460 BMLoop **ltri = bmtree->looptris[hit.index];
461 return ltri[bmcb_data.index_tri]->v;
462 }
463
464 return NULL;
465 }
466
467 struct FaceSearchUserData {
468 /* from the bmtree */
469 const BMLoop *(*looptris)[3];
470 const float (*cos_cage)[3];
471
472 /* from the hit */
473 float dist_max_sq;
474 };
475
bmbvh_find_face_closest_cb(void * userdata,int index,const float co[3],BVHTreeNearest * hit)476 static void bmbvh_find_face_closest_cb(void *userdata,
477 int index,
478 const float co[3],
479 BVHTreeNearest *hit)
480 {
481 struct FaceSearchUserData *bmcb_data = userdata;
482 const BMLoop **ltri = bmcb_data->looptris[index];
483 const float dist_max_sq = bmcb_data->dist_max_sq;
484
485 const float *tri_cos[3];
486
487 bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
488
489 float co_close[3];
490 closest_on_tri_to_point_v3(co_close, co, UNPACK3(tri_cos));
491 const float dist_sq = len_squared_v3v3(co, co_close);
492 if (dist_sq < hit->dist_sq && dist_sq < dist_max_sq) {
493 /* XXX, normal ignores cage */
494 copy_v3_v3(hit->no, ltri[0]->f->no);
495 hit->dist_sq = dist_sq;
496 hit->index = index;
497 }
498 }
499
BKE_bmbvh_find_face_closest(BMBVHTree * bmtree,const float co[3],const float dist_max)500 struct BMFace *BKE_bmbvh_find_face_closest(BMBVHTree *bmtree,
501 const float co[3],
502 const float dist_max)
503 {
504 BVHTreeNearest hit;
505 struct FaceSearchUserData bmcb_data;
506 const float dist_max_sq = dist_max * dist_max;
507
508 if (bmtree->cos_cage) {
509 BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
510 }
511
512 hit.dist_sq = dist_max_sq;
513 hit.index = -1;
514
515 bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
516 bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
517 bmcb_data.dist_max_sq = dist_max_sq;
518
519 BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_face_closest_cb, &bmcb_data);
520 if (hit.index != -1) {
521 BMLoop **ltri = bmtree->looptris[hit.index];
522 return ltri[0]->f;
523 }
524
525 return NULL;
526 }
527
528 /* -------------------------------------------------------------------- */
529 /* BKE_bmbvh_overlap */
530
531 struct BMBVHTree_OverlapData {
532 const BMBVHTree *tree_pair[2];
533 float epsilon;
534 };
535
bmbvh_overlap_cb(void * userdata,int index_a,int index_b,int UNUSED (thread))536 static bool bmbvh_overlap_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
537 {
538 struct BMBVHTree_OverlapData *data = userdata;
539 const BMBVHTree *bmtree_a = data->tree_pair[0];
540 const BMBVHTree *bmtree_b = data->tree_pair[1];
541
542 BMLoop **tri_a = bmtree_a->looptris[index_a];
543 BMLoop **tri_b = bmtree_b->looptris[index_b];
544 const float *tri_a_co[3] = {tri_a[0]->v->co, tri_a[1]->v->co, tri_a[2]->v->co};
545 const float *tri_b_co[3] = {tri_b[0]->v->co, tri_b[1]->v->co, tri_b[2]->v->co};
546 float ix_pair[2][3];
547 int verts_shared = 0;
548
549 if (bmtree_a->looptris == bmtree_b->looptris) {
550 if (UNLIKELY(tri_a[0]->f == tri_b[0]->f)) {
551 return false;
552 }
553
554 verts_shared = (ELEM(tri_a_co[0], UNPACK3(tri_b_co)) + ELEM(tri_a_co[1], UNPACK3(tri_b_co)) +
555 ELEM(tri_a_co[2], UNPACK3(tri_b_co)));
556
557 /* if 2 points are shared, bail out */
558 if (verts_shared >= 2) {
559 return false;
560 }
561 }
562
563 return (isect_tri_tri_v3(UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1]) &&
564 /* if we share a vertex, check the intersection isn't a 'point' */
565 ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon)));
566 }
567
568 /**
569 * Overlap indices reference the looptri's
570 */
BKE_bmbvh_overlap(const BMBVHTree * bmtree_a,const BMBVHTree * bmtree_b,unsigned int * r_overlap_tot)571 BVHTreeOverlap *BKE_bmbvh_overlap(const BMBVHTree *bmtree_a,
572 const BMBVHTree *bmtree_b,
573 unsigned int *r_overlap_tot)
574 {
575 struct BMBVHTree_OverlapData data;
576
577 data.tree_pair[0] = bmtree_a;
578 data.tree_pair[1] = bmtree_b;
579 data.epsilon = max_ff(BLI_bvhtree_get_epsilon(bmtree_a->tree),
580 BLI_bvhtree_get_epsilon(bmtree_b->tree));
581
582 return BLI_bvhtree_overlap(
583 bmtree_a->tree, bmtree_b->tree, r_overlap_tot, bmbvh_overlap_cb, &data);
584 }
585
bmbvh_overlap_self_cb(void * userdata,int index_a,int index_b,int thread)586 static bool bmbvh_overlap_self_cb(void *userdata, int index_a, int index_b, int thread)
587 {
588 if (index_a < index_b) {
589 return bmbvh_overlap_cb(userdata, index_a, index_b, thread);
590 }
591 return false;
592 }
593
594 /**
595 * Overlap indices reference the looptri's
596 */
BKE_bmbvh_overlap_self(const BMBVHTree * bmtree,unsigned int * r_overlap_tot)597 BVHTreeOverlap *BKE_bmbvh_overlap_self(const BMBVHTree *bmtree, unsigned int *r_overlap_tot)
598 {
599 struct BMBVHTree_OverlapData data;
600
601 data.tree_pair[0] = bmtree;
602 data.tree_pair[1] = bmtree;
603 data.epsilon = BLI_bvhtree_get_epsilon(bmtree->tree);
604
605 return BLI_bvhtree_overlap(
606 bmtree->tree, bmtree->tree, r_overlap_tot, bmbvh_overlap_self_cb, &data);
607 }
608