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