Cleanup: comments (long lines) in blenkernel
[blender.git] / source / blender / blenkernel / intern / editmesh_bvh.c
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_math.h"
27 #include "BLI_kdopbvh.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
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
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 i;
70   int tottri;
71
72   /* avoid testing every tri */
73   BMFace *f_test, *f_test_prev;
74   bool test_fn_ret;
75
76   /* BKE_editmesh_tessface_calc() must be called already */
77   BLI_assert(looptris_tot != 0 || bm->totface == 0);
78
79   if (cos_cage) {
80     BM_mesh_elem_index_ensure(bm, BM_VERT);
81   }
82
83   bmtree->looptris = looptris;
84   bmtree->looptris_tot = looptris_tot;
85   bmtree->bm = bm;
86   bmtree->cos_cage = cos_cage;
87   bmtree->cos_cage_free = cos_cage_free;
88   bmtree->flag = flag;
89
90   if (test_fn) {
91     /* callback must do... */
92     BLI_assert(!(flag & (BMBVH_RESPECT_SELECT | BMBVH_RESPECT_HIDDEN)));
93
94     f_test_prev = NULL;
95     test_fn_ret = false;
96
97     tottri = 0;
98     for (i = 0; i < looptris_tot; i++) {
99       f_test = looptris[i][0]->f;
100       if (f_test != f_test_prev) {
101         test_fn_ret = test_fn(f_test, user_data);
102         f_test_prev = f_test;
103       }
104
105       if (test_fn_ret) {
106         tottri++;
107       }
108     }
109   }
110   else {
111     tottri = looptris_tot;
112   }
113
114   bmtree->tree = BLI_bvhtree_new(tottri, epsilon, 8, 8);
115
116   f_test_prev = NULL;
117   test_fn_ret = false;
118
119   for (i = 0; i < looptris_tot; i++) {
120     if (test_fn) {
121       /* note, the arrays wont align now! take care */
122       f_test = looptris[i][0]->f;
123       if (f_test != f_test_prev) {
124         test_fn_ret = test_fn(f_test, user_data);
125         f_test_prev = f_test;
126       }
127
128       if (!test_fn_ret) {
129         continue;
130       }
131     }
132
133     if (cos_cage) {
134       copy_v3_v3(cos[0], cos_cage[BM_elem_index_get(looptris[i][0]->v)]);
135       copy_v3_v3(cos[1], cos_cage[BM_elem_index_get(looptris[i][1]->v)]);
136       copy_v3_v3(cos[2], cos_cage[BM_elem_index_get(looptris[i][2]->v)]);
137     }
138     else {
139       copy_v3_v3(cos[0], looptris[i][0]->v->co);
140       copy_v3_v3(cos[1], looptris[i][1]->v->co);
141       copy_v3_v3(cos[2], looptris[i][2]->v->co);
142     }
143
144     BLI_bvhtree_insert(bmtree->tree, i, (float *)cos, 3);
145   }
146
147   BLI_bvhtree_balance(bmtree->tree);
148
149   return bmtree;
150 }
151
152 static bool bm_face_is_select(BMFace *f, void *UNUSED(user_data))
153 {
154   return (BM_elem_flag_test(f, BM_ELEM_SELECT) != 0);
155 }
156
157 static bool bm_face_is_not_hidden(BMFace *f, void *UNUSED(user_data))
158 {
159   return (BM_elem_flag_test(f, BM_ELEM_HIDDEN) == 0);
160 }
161
162 BMBVHTree *BKE_bmbvh_new(BMesh *bm,
163                          BMLoop *(*looptris)[3],
164                          int looptris_tot,
165                          int flag,
166                          const float (*cos_cage)[3],
167                          const bool cos_cage_free)
168 {
169   bool (*test_fn)(BMFace *, void *user_data);
170
171   if (flag & BMBVH_RESPECT_SELECT) {
172     test_fn = bm_face_is_select;
173   }
174   else if (flag & BMBVH_RESPECT_HIDDEN) {
175     test_fn = bm_face_is_not_hidden;
176   }
177   else {
178     test_fn = NULL;
179   }
180
181   flag &= ~(BMBVH_RESPECT_SELECT | BMBVH_RESPECT_HIDDEN);
182
183   return BKE_bmbvh_new_ex(
184       bm, looptris, looptris_tot, flag, cos_cage, cos_cage_free, test_fn, NULL);
185 }
186
187 void BKE_bmbvh_free(BMBVHTree *bmtree)
188 {
189   BLI_bvhtree_free(bmtree->tree);
190
191   if (bmtree->cos_cage && bmtree->cos_cage_free) {
192     MEM_freeN((void *)bmtree->cos_cage);
193   }
194
195   MEM_freeN(bmtree);
196 }
197
198 BVHTree *BKE_bmbvh_tree_get(BMBVHTree *bmtree)
199 {
200   return bmtree->tree;
201 }
202
203 /* -------------------------------------------------------------------- */
204 /* Utility BMesh cast/intersect functions */
205
206 /**
207  * Return the coords from a triangle.
208  */
209 static void bmbvh_tri_from_face(const float *cos[3],
210                                 const BMLoop **ltri,
211                                 const float (*cos_cage)[3])
212 {
213   if (cos_cage == NULL) {
214     cos[0] = ltri[0]->v->co;
215     cos[1] = ltri[1]->v->co;
216     cos[2] = ltri[2]->v->co;
217   }
218   else {
219     cos[0] = cos_cage[BM_elem_index_get(ltri[0]->v)];
220     cos[1] = cos_cage[BM_elem_index_get(ltri[1]->v)];
221     cos[2] = cos_cage[BM_elem_index_get(ltri[2]->v)];
222   }
223 }
224
225 /* taken from bvhutils.c */
226
227 /* -------------------------------------------------------------------- */
228 /* BKE_bmbvh_ray_cast */
229
230 struct RayCastUserData {
231   /* from the bmtree */
232   const BMLoop *(*looptris)[3];
233   const float (*cos_cage)[3];
234
235   /* from the hit */
236   float uv[2];
237 };
238
239 static BMFace *bmbvh_ray_cast_handle_hit(BMBVHTree *bmtree,
240                                          struct RayCastUserData *bmcb_data,
241                                          const BVHTreeRayHit *hit,
242                                          float *r_dist,
243                                          float r_hitout[3],
244                                          float r_cagehit[3])
245 {
246   if (r_hitout) {
247     if (bmtree->flag & BMBVH_RETURN_ORIG) {
248       BMLoop **ltri = bmtree->looptris[hit->index];
249       interp_v3_v3v3v3_uv(r_hitout, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co, bmcb_data->uv);
250     }
251     else {
252       copy_v3_v3(r_hitout, hit->co);
253     }
254
255     if (r_cagehit) {
256       copy_v3_v3(r_cagehit, hit->co);
257     }
258   }
259
260   if (r_dist) {
261     *r_dist = hit->dist;
262   }
263
264   return bmtree->looptris[hit->index][0]->f;
265 }
266
267 static void bmbvh_ray_cast_cb(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
268 {
269   struct RayCastUserData *bmcb_data = userdata;
270   const BMLoop **ltri = bmcb_data->looptris[index];
271   float dist, uv[2];
272   const float *tri_cos[3];
273   bool isect;
274
275   bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
276
277   isect =
278       (ray->radius > 0.0f ?
279            isect_ray_tri_epsilon_v3(ray->origin,
280                                     ray->direction,
281                                     tri_cos[0],
282                                     tri_cos[1],
283                                     tri_cos[2],
284                                     &dist,
285                                     uv,
286                                     ray->radius) :
287 #ifdef USE_KDOPBVH_WATERTIGHT
288            isect_ray_tri_watertight_v3(
289                ray->origin, ray->isect_precalc, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
290 #else
291            isect_ray_tri_v3(
292                ray->origin, ray->direction, tri_cos[0], tri_cos[1], tri_cos[2], &dist, uv));
293 #endif
294
295   if (isect && dist < hit->dist) {
296     hit->dist = dist;
297     hit->index = index;
298
299     copy_v3_v3(hit->no, ltri[0]->f->no);
300
301     madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
302
303     copy_v2_v2(bmcb_data->uv, uv);
304   }
305 }
306
307 BMFace *BKE_bmbvh_ray_cast(BMBVHTree *bmtree,
308                            const float co[3],
309                            const float dir[3],
310                            const float radius,
311                            float *r_dist,
312                            float r_hitout[3],
313                            float r_cagehit[3])
314 {
315   BVHTreeRayHit hit;
316   struct RayCastUserData bmcb_data;
317   const float dist = r_dist ? *r_dist : FLT_MAX;
318
319   if (bmtree->cos_cage) {
320     BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
321   }
322
323   hit.dist = dist;
324   hit.index = -1;
325
326   /* ok to leave 'uv' uninitialized */
327   bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
328   bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
329
330   BLI_bvhtree_ray_cast(bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb, &bmcb_data);
331
332   if (hit.index != -1 && hit.dist != dist) {
333     return bmbvh_ray_cast_handle_hit(bmtree, &bmcb_data, &hit, r_dist, r_hitout, r_cagehit);
334   }
335
336   return NULL;
337 }
338
339 /* -------------------------------------------------------------------- */
340 /* bmbvh_ray_cast_cb_filter */
341
342 /* Same as BKE_bmbvh_ray_cast but takes a callback to filter out faces.
343  */
344
345 struct RayCastUserData_Filter {
346   struct RayCastUserData bmcb_data;
347
348   BMBVHTree_FaceFilter filter_cb;
349   void *filter_userdata;
350 };
351
352 static void bmbvh_ray_cast_cb_filter(void *userdata,
353                                      int index,
354                                      const BVHTreeRay *ray,
355                                      BVHTreeRayHit *hit)
356 {
357   struct RayCastUserData_Filter *bmcb_data_filter = userdata;
358   struct RayCastUserData *bmcb_data = &bmcb_data_filter->bmcb_data;
359   const BMLoop **ltri = bmcb_data->looptris[index];
360   if (bmcb_data_filter->filter_cb(ltri[0]->f, bmcb_data_filter->filter_userdata)) {
361     bmbvh_ray_cast_cb(bmcb_data, index, ray, hit);
362   }
363 }
364
365 BMFace *BKE_bmbvh_ray_cast_filter(BMBVHTree *bmtree,
366                                   const float co[3],
367                                   const float dir[3],
368                                   const float radius,
369                                   float *r_dist,
370                                   float r_hitout[3],
371                                   float r_cagehit[3],
372                                   BMBVHTree_FaceFilter filter_cb,
373                                   void *filter_userdata)
374 {
375   BVHTreeRayHit hit;
376   struct RayCastUserData_Filter bmcb_data_filter;
377   struct RayCastUserData *bmcb_data = &bmcb_data_filter.bmcb_data;
378
379   const float dist = r_dist ? *r_dist : FLT_MAX;
380
381   bmcb_data_filter.filter_cb = filter_cb;
382   bmcb_data_filter.filter_userdata = filter_userdata;
383
384   if (bmtree->cos_cage) {
385     BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
386   }
387
388   hit.dist = dist;
389   hit.index = -1;
390
391   /* ok to leave 'uv' uninitialized */
392   bmcb_data->looptris = (const BMLoop *(*)[3])bmtree->looptris;
393   bmcb_data->cos_cage = (const float(*)[3])bmtree->cos_cage;
394
395   BLI_bvhtree_ray_cast(
396       bmtree->tree, co, dir, radius, &hit, bmbvh_ray_cast_cb_filter, &bmcb_data_filter);
397   if (hit.index != -1 && hit.dist != dist) {
398     return bmbvh_ray_cast_handle_hit(bmtree, bmcb_data, &hit, r_dist, r_hitout, r_cagehit);
399   }
400
401   return NULL;
402 }
403
404 /* -------------------------------------------------------------------- */
405 /* BKE_bmbvh_find_vert_closest */
406
407 struct VertSearchUserData {
408   /* from the bmtree */
409   const BMLoop *(*looptris)[3];
410   const float (*cos_cage)[3];
411
412   /* from the hit */
413   float dist_max_sq;
414   int index_tri;
415 };
416
417 static void bmbvh_find_vert_closest_cb(void *userdata,
418                                        int index,
419                                        const float co[3],
420                                        BVHTreeNearest *hit)
421 {
422   struct VertSearchUserData *bmcb_data = userdata;
423   const BMLoop **ltri = bmcb_data->looptris[index];
424   const float dist_max_sq = bmcb_data->dist_max_sq;
425   int i;
426
427   const float *tri_cos[3];
428
429   bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
430
431   for (i = 0; i < 3; i++) {
432     const float dist_sq = len_squared_v3v3(co, tri_cos[i]);
433     if (dist_sq < hit->dist_sq && dist_sq < dist_max_sq) {
434       copy_v3_v3(hit->co, tri_cos[i]);
435       /* XXX, normal ignores cage */
436       copy_v3_v3(hit->no, ltri[i]->v->no);
437       hit->dist_sq = dist_sq;
438       hit->index = index;
439       bmcb_data->index_tri = i;
440     }
441   }
442 }
443
444 BMVert *BKE_bmbvh_find_vert_closest(BMBVHTree *bmtree, const float co[3], const float dist_max)
445 {
446   BVHTreeNearest hit;
447   struct VertSearchUserData bmcb_data;
448   const float dist_max_sq = dist_max * dist_max;
449
450   if (bmtree->cos_cage) {
451     BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
452   }
453
454   hit.dist_sq = dist_max_sq;
455   hit.index = -1;
456
457   bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
458   bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
459   bmcb_data.dist_max_sq = dist_max_sq;
460
461   BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_vert_closest_cb, &bmcb_data);
462   if (hit.index != -1) {
463     BMLoop **ltri = bmtree->looptris[hit.index];
464     return ltri[bmcb_data.index_tri]->v;
465   }
466
467   return NULL;
468 }
469
470 struct FaceSearchUserData {
471   /* from the bmtree */
472   const BMLoop *(*looptris)[3];
473   const float (*cos_cage)[3];
474
475   /* from the hit */
476   float dist_max_sq;
477 };
478
479 static void bmbvh_find_face_closest_cb(void *userdata,
480                                        int index,
481                                        const float co[3],
482                                        BVHTreeNearest *hit)
483 {
484   struct FaceSearchUserData *bmcb_data = userdata;
485   const BMLoop **ltri = bmcb_data->looptris[index];
486   const float dist_max_sq = bmcb_data->dist_max_sq;
487
488   const float *tri_cos[3];
489
490   bmbvh_tri_from_face(tri_cos, ltri, bmcb_data->cos_cage);
491
492   float co_close[3];
493   closest_on_tri_to_point_v3(co_close, co, UNPACK3(tri_cos));
494   const float dist_sq = len_squared_v3v3(co, co_close);
495   if (dist_sq < hit->dist_sq && dist_sq < dist_max_sq) {
496     /* XXX, normal ignores cage */
497     copy_v3_v3(hit->no, ltri[0]->f->no);
498     hit->dist_sq = dist_sq;
499     hit->index = index;
500   }
501 }
502
503 struct BMFace *BKE_bmbvh_find_face_closest(BMBVHTree *bmtree,
504                                            const float co[3],
505                                            const float dist_max)
506 {
507   BVHTreeNearest hit;
508   struct FaceSearchUserData bmcb_data;
509   const float dist_max_sq = dist_max * dist_max;
510
511   if (bmtree->cos_cage) {
512     BLI_assert(!(bmtree->bm->elem_index_dirty & BM_VERT));
513   }
514
515   hit.dist_sq = dist_max_sq;
516   hit.index = -1;
517
518   bmcb_data.looptris = (const BMLoop *(*)[3])bmtree->looptris;
519   bmcb_data.cos_cage = (const float(*)[3])bmtree->cos_cage;
520   bmcb_data.dist_max_sq = dist_max_sq;
521
522   BLI_bvhtree_find_nearest(bmtree->tree, co, &hit, bmbvh_find_face_closest_cb, &bmcb_data);
523   if (hit.index != -1) {
524     BMLoop **ltri = bmtree->looptris[hit.index];
525     return ltri[0]->f;
526   }
527
528   return NULL;
529 }
530
531 /* -------------------------------------------------------------------- */
532 /* BKE_bmbvh_overlap */
533
534 struct BMBVHTree_OverlapData {
535   const BMBVHTree *tree_pair[2];
536   float epsilon;
537 };
538
539 static bool bmbvh_overlap_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
540 {
541   struct BMBVHTree_OverlapData *data = userdata;
542   const BMBVHTree *bmtree_a = data->tree_pair[0];
543   const BMBVHTree *bmtree_b = data->tree_pair[1];
544
545   BMLoop **tri_a = bmtree_a->looptris[index_a];
546   BMLoop **tri_b = bmtree_b->looptris[index_b];
547   const float *tri_a_co[3] = {tri_a[0]->v->co, tri_a[1]->v->co, tri_a[2]->v->co};
548   const float *tri_b_co[3] = {tri_b[0]->v->co, tri_b[1]->v->co, tri_b[2]->v->co};
549   float ix_pair[2][3];
550   int verts_shared = 0;
551
552   if (bmtree_a->looptris == bmtree_b->looptris) {
553     if (UNLIKELY(tri_a[0]->f == tri_b[0]->f)) {
554       return false;
555     }
556
557     verts_shared = (ELEM(tri_a_co[0], UNPACK3(tri_b_co)) + ELEM(tri_a_co[1], UNPACK3(tri_b_co)) +
558                     ELEM(tri_a_co[2], UNPACK3(tri_b_co)));
559
560     /* if 2 points are shared, bail out */
561     if (verts_shared >= 2) {
562       return false;
563     }
564   }
565
566   return (isect_tri_tri_epsilon_v3(
567               UNPACK3(tri_a_co), UNPACK3(tri_b_co), ix_pair[0], ix_pair[1], data->epsilon) &&
568           /* if we share a vertex, check the intersection isn't a 'point' */
569           ((verts_shared == 0) || (len_squared_v3v3(ix_pair[0], ix_pair[1]) > data->epsilon)));
570 }
571
572 /**
573  * Overlap indices reference the looptri's
574  */
575 BVHTreeOverlap *BKE_bmbvh_overlap(const BMBVHTree *bmtree_a,
576                                   const BMBVHTree *bmtree_b,
577                                   unsigned int *r_overlap_tot)
578 {
579   struct BMBVHTree_OverlapData data;
580
581   data.tree_pair[0] = bmtree_a;
582   data.tree_pair[1] = bmtree_b;
583   data.epsilon = max_ff(BLI_bvhtree_get_epsilon(bmtree_a->tree),
584                         BLI_bvhtree_get_epsilon(bmtree_b->tree));
585
586   return BLI_bvhtree_overlap(
587       bmtree_a->tree, bmtree_b->tree, r_overlap_tot, bmbvh_overlap_cb, &data);
588 }