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