Blender  V3.3
bvhutils.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright Blender Foundation. All rights reserved. */
3 
8 #include <cmath>
9 #include <cstdio>
10 #include <cstring>
11 
12 #include "DNA_mesh_types.h"
13 #include "DNA_meshdata_types.h"
14 #include "DNA_pointcloud_types.h"
15 
16 #include "BLI_linklist.h"
17 #include "BLI_math.h"
18 #include "BLI_task.h"
19 #include "BLI_threads.h"
20 #include "BLI_utildefines.h"
21 
22 #include "BKE_attribute.hh"
23 #include "BKE_bvhutils.h"
24 #include "BKE_editmesh.h"
25 #include "BKE_mesh.h"
26 #include "BKE_mesh_runtime.h"
27 
28 #include "MEM_guardedalloc.h"
29 
30 /* -------------------------------------------------------------------- */
34 struct BVHCacheItem {
35  bool is_filled;
37 };
38 
39 struct BVHCache {
42 };
43 
52 static bool bvhcache_find(BVHCache **bvh_cache_p,
54  BVHTree **r_tree,
55  bool *r_locked,
56  ThreadMutex *mesh_eval_mutex)
57 {
58  bool do_lock = r_locked;
59  if (r_locked) {
60  *r_locked = false;
61  }
62  if (*bvh_cache_p == nullptr) {
63  if (!do_lock) {
64  /* Cache does not exist and no lock is requested. */
65  return false;
66  }
67  /* Lazy initialization of the bvh_cache using the `mesh_eval_mutex`. */
68  BLI_mutex_lock(mesh_eval_mutex);
69  if (*bvh_cache_p == nullptr) {
70  *bvh_cache_p = bvhcache_init();
71  }
72  BLI_mutex_unlock(mesh_eval_mutex);
73  }
74  BVHCache *bvh_cache = *bvh_cache_p;
75 
76  if (bvh_cache->items[type].is_filled) {
77  *r_tree = bvh_cache->items[type].tree;
78  return true;
79  }
80  if (do_lock) {
81  BLI_mutex_lock(&bvh_cache->mutex);
82  bool in_cache = bvhcache_find(bvh_cache_p, type, r_tree, nullptr, nullptr);
83  if (in_cache) {
84  BLI_mutex_unlock(&bvh_cache->mutex);
85  return in_cache;
86  }
87  *r_locked = true;
88  }
89  return false;
90 }
91 
92 static void bvhcache_unlock(BVHCache *bvh_cache, bool lock_started)
93 {
94  if (lock_started) {
95  BLI_mutex_unlock(&bvh_cache->mutex);
96  }
97 }
98 
99 bool bvhcache_has_tree(const BVHCache *bvh_cache, const BVHTree *tree)
100 {
101  if (bvh_cache == nullptr) {
102  return false;
103  }
104 
105  for (int i = 0; i < BVHTREE_MAX_ITEM; i++) {
106  if (bvh_cache->items[i].tree == tree) {
107  return true;
108  }
109  }
110  return false;
111 }
112 
114 {
115  BVHCache *cache = MEM_cnew<BVHCache>(__func__);
116  BLI_mutex_init(&cache->mutex);
117  return cache;
118 }
128 {
129  BVHCacheItem *item = &bvh_cache->items[type];
130  BLI_assert(!item->is_filled);
131  item->tree = tree;
132  item->is_filled = true;
133 }
134 
135 void bvhcache_free(BVHCache *bvh_cache)
136 {
137  for (int index = 0; index < BVHTREE_MAX_ITEM; index++) {
138  BVHCacheItem *item = &bvh_cache->items[index];
139  BLI_bvhtree_free(item->tree);
140  item->tree = nullptr;
141  }
142  BLI_mutex_end(&bvh_cache->mutex);
143  MEM_freeN(bvh_cache);
144 }
145 
151 static void bvhtree_balance_isolated(void *userdata)
152 {
153  BLI_bvhtree_balance((BVHTree *)userdata);
154 }
155 
156 static void bvhtree_balance(BVHTree *tree, const bool isolate)
157 {
158  if (tree) {
159  if (isolate) {
161  }
162  else {
164  }
165  }
166 }
167 
170 /* -------------------------------------------------------------------- */
174 /* Math stuff for ray casting on mesh faces and for nearest surface */
175 
177  const float UNUSED(m_dist),
178  const float v0[3],
179  const float v1[3],
180  const float v2[3])
181 {
182  float dist;
183 
184 #ifdef USE_KDOPBVH_WATERTIGHT
185  if (isect_ray_tri_watertight_v3(ray->origin, ray->isect_precalc, v0, v1, v2, &dist, nullptr))
186 #else
188  ray->origin, ray->direction, v0, v1, v2, &dist, nullptr, FLT_EPSILON))
189 #endif
190  {
191  return dist;
192  }
193 
194  return FLT_MAX;
195 }
196 
198  float radius,
199  const float m_dist,
200  const float v0[3],
201  const float v1[3],
202  const float v2[3])
203 {
204 
205  float idist;
206  float p1[3];
207  float hit_point[3];
208 
209  madd_v3_v3v3fl(p1, ray->origin, ray->direction, m_dist);
210  if (isect_sweeping_sphere_tri_v3(ray->origin, p1, radius, v0, v1, v2, &idist, hit_point)) {
211  return idist * m_dist;
212  }
213 
214  return FLT_MAX;
215 }
216 
217 /*
218  * BVH from meshes callbacks
219  */
220 
227 static void mesh_faces_nearest_point(void *userdata,
228  int index,
229  const float co[3],
230  BVHTreeNearest *nearest)
231 {
232  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
233  const MVert *vert = data->vert;
234  const MFace *face = data->face + index;
235 
236  const float *t0, *t1, *t2, *t3;
237  t0 = vert[face->v1].co;
238  t1 = vert[face->v2].co;
239  t2 = vert[face->v3].co;
240  t3 = face->v4 ? vert[face->v4].co : nullptr;
241 
242  do {
243  float nearest_tmp[3], dist_sq;
244 
245  closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
246  dist_sq = len_squared_v3v3(co, nearest_tmp);
247 
248  if (dist_sq < nearest->dist_sq) {
249  nearest->index = index;
250  nearest->dist_sq = dist_sq;
251  copy_v3_v3(nearest->co, nearest_tmp);
252  normal_tri_v3(nearest->no, t0, t1, t2);
253  }
254 
255  t1 = t2;
256  t2 = t3;
257  t3 = nullptr;
258 
259  } while (t2);
260 }
261 /* copy of function above */
262 static void mesh_looptri_nearest_point(void *userdata,
263  int index,
264  const float co[3],
265  BVHTreeNearest *nearest)
266 {
267  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
268  const MVert *vert = data->vert;
269  const MLoopTri *lt = &data->looptri[index];
270  const float *vtri_co[3] = {
271  vert[data->loop[lt->tri[0]].v].co,
272  vert[data->loop[lt->tri[1]].v].co,
273  vert[data->loop[lt->tri[2]].v].co,
274  };
275  float nearest_tmp[3], dist_sq;
276 
277  closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(vtri_co));
278  dist_sq = len_squared_v3v3(co, nearest_tmp);
279 
280  if (dist_sq < nearest->dist_sq) {
281  nearest->index = index;
282  nearest->dist_sq = dist_sq;
283  copy_v3_v3(nearest->co, nearest_tmp);
284  normal_tri_v3(nearest->no, UNPACK3(vtri_co));
285  }
286 }
287 /* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
288 static void editmesh_looptri_nearest_point(void *userdata,
289  int index,
290  const float co[3],
291  BVHTreeNearest *nearest)
292 {
293  const BVHTreeFromEditMesh *data = (const BVHTreeFromEditMesh *)userdata;
294  BMEditMesh *em = data->em;
295  const BMLoop **ltri = (const BMLoop **)em->looptris[index];
296 
297  const float *t0, *t1, *t2;
298  t0 = ltri[0]->v->co;
299  t1 = ltri[1]->v->co;
300  t2 = ltri[2]->v->co;
301 
302  {
303  float nearest_tmp[3], dist_sq;
304 
305  closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
306  dist_sq = len_squared_v3v3(co, nearest_tmp);
307 
308  if (dist_sq < nearest->dist_sq) {
309  nearest->index = index;
310  nearest->dist_sq = dist_sq;
311  copy_v3_v3(nearest->co, nearest_tmp);
312  normal_tri_v3(nearest->no, t0, t1, t2);
313  }
314  }
315 }
316 
323 static void mesh_faces_spherecast(void *userdata,
324  int index,
325  const BVHTreeRay *ray,
326  BVHTreeRayHit *hit)
327 {
328  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
329  const MVert *vert = data->vert;
330  const MFace *face = &data->face[index];
331 
332  const float *t0, *t1, *t2, *t3;
333  t0 = vert[face->v1].co;
334  t1 = vert[face->v2].co;
335  t2 = vert[face->v3].co;
336  t3 = face->v4 ? vert[face->v4].co : nullptr;
337 
338  do {
339  float dist;
340  if (ray->radius == 0.0f) {
341  dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
342  }
343  else {
344  dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, t0, t1, t2);
345  }
346 
347  if (dist >= 0 && dist < hit->dist) {
348  hit->index = index;
349  hit->dist = dist;
350  madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
351 
352  normal_tri_v3(hit->no, t0, t1, t2);
353  }
354 
355  t1 = t2;
356  t2 = t3;
357  t3 = nullptr;
358 
359  } while (t2);
360 }
361 /* copy of function above */
362 static void mesh_looptri_spherecast(void *userdata,
363  int index,
364  const BVHTreeRay *ray,
365  BVHTreeRayHit *hit)
366 {
367  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
368  const MVert *vert = data->vert;
369  const MLoopTri *lt = &data->looptri[index];
370  const float *vtri_co[3] = {
371  vert[data->loop[lt->tri[0]].v].co,
372  vert[data->loop[lt->tri[1]].v].co,
373  vert[data->loop[lt->tri[2]].v].co,
374  };
375  float dist;
376 
377  if (ray->radius == 0.0f) {
378  dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(vtri_co));
379  }
380  else {
381  dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, UNPACK3(vtri_co));
382  }
383 
384  if (dist >= 0 && dist < hit->dist) {
385  hit->index = index;
386  hit->dist = dist;
387  madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
388 
389  normal_tri_v3(hit->no, UNPACK3(vtri_co));
390  }
391 }
392 /* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
393 static void editmesh_looptri_spherecast(void *userdata,
394  int index,
395  const BVHTreeRay *ray,
396  BVHTreeRayHit *hit)
397 {
398  const BVHTreeFromEditMesh *data = (BVHTreeFromEditMesh *)userdata;
399  BMEditMesh *em = data->em;
400  const BMLoop **ltri = (const BMLoop **)em->looptris[index];
401 
402  const float *t0, *t1, *t2;
403  t0 = ltri[0]->v->co;
404  t1 = ltri[1]->v->co;
405  t2 = ltri[2]->v->co;
406 
407  {
408  float dist;
409  if (ray->radius == 0.0f) {
410  dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
411  }
412  else {
413  dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, t0, t1, t2);
414  }
415 
416  if (dist >= 0 && dist < hit->dist) {
417  hit->index = index;
418  hit->dist = dist;
419  madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
420 
421  normal_tri_v3(hit->no, t0, t1, t2);
422  }
423  }
424 }
425 
432 static void mesh_edges_nearest_point(void *userdata,
433  int index,
434  const float co[3],
435  BVHTreeNearest *nearest)
436 {
437  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
438  const MVert *vert = data->vert;
439  const MEdge *edge = data->edge + index;
440  float nearest_tmp[3], dist_sq;
441 
442  const float *t0, *t1;
443  t0 = vert[edge->v1].co;
444  t1 = vert[edge->v2].co;
445 
446  closest_to_line_segment_v3(nearest_tmp, co, t0, t1);
447  dist_sq = len_squared_v3v3(nearest_tmp, co);
448 
449  if (dist_sq < nearest->dist_sq) {
450  nearest->index = index;
451  nearest->dist_sq = dist_sq;
452  copy_v3_v3(nearest->co, nearest_tmp);
453  sub_v3_v3v3(nearest->no, t0, t1);
454  normalize_v3(nearest->no);
455  }
456 }
457 
458 /* Helper, does all the point-sphere-cast work actually. */
459 static void mesh_verts_spherecast_do(int index,
460  const float v[3],
461  const BVHTreeRay *ray,
462  BVHTreeRayHit *hit)
463 {
464  float dist;
465  const float *r1;
466  float r2[3], i1[3];
467  r1 = ray->origin;
468  add_v3_v3v3(r2, r1, ray->direction);
469 
470  closest_to_line_segment_v3(i1, v, r1, r2);
471 
472  /* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */
473  if ((dot_v3v3v3(r1, i1, r2) >= 0.0f) && ((dist = len_v3v3(r1, i1)) < hit->dist)) {
474  hit->index = index;
475  hit->dist = dist;
476  copy_v3_v3(hit->co, i1);
477  }
478 }
479 
480 static void editmesh_verts_spherecast(void *userdata,
481  int index,
482  const BVHTreeRay *ray,
483  BVHTreeRayHit *hit)
484 {
485  const BVHTreeFromEditMesh *data = (const BVHTreeFromEditMesh *)userdata;
486  BMVert *eve = BM_vert_at_index(data->em->bm, index);
487 
488  mesh_verts_spherecast_do(index, eve->co, ray, hit);
489 }
490 
497 static void mesh_verts_spherecast(void *userdata,
498  int index,
499  const BVHTreeRay *ray,
500  BVHTreeRayHit *hit)
501 {
502  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
503  const float *v = data->vert[index].co;
504 
505  mesh_verts_spherecast_do(index, v, ray, hit);
506 }
507 
514 static void mesh_edges_spherecast(void *userdata,
515  int index,
516  const BVHTreeRay *ray,
517  BVHTreeRayHit *hit)
518 {
519  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
520  const MVert *vert = data->vert;
521  const MEdge *edge = &data->edge[index];
522 
523  const float radius_sq = square_f(ray->radius);
524  float dist;
525  const float *v1, *v2, *r1;
526  float r2[3], i1[3], i2[3];
527  v1 = vert[edge->v1].co;
528  v2 = vert[edge->v2].co;
529 
530  /* In case we get a zero-length edge, handle it as a point! */
531  if (equals_v3v3(v1, v2)) {
532  mesh_verts_spherecast_do(index, v1, ray, hit);
533  return;
534  }
535 
536  r1 = ray->origin;
537  add_v3_v3v3(r2, r1, ray->direction);
538 
539  if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) {
540  /* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */
541  if ((dot_v3v3v3(r1, i2, r2) >= 0.0f) && ((dist = len_v3v3(r1, i2)) < hit->dist)) {
542  const float e_fac = line_point_factor_v3(i1, v1, v2);
543  if (e_fac < 0.0f) {
544  copy_v3_v3(i1, v1);
545  }
546  else if (e_fac > 1.0f) {
547  copy_v3_v3(i1, v2);
548  }
549  /* Ensure ray is really close enough from edge! */
550  if (len_squared_v3v3(i1, i2) <= radius_sq) {
551  hit->index = index;
552  hit->dist = dist;
553  copy_v3_v3(hit->co, i2);
554  }
555  }
556  }
557 }
558 
561 /*
562  * BVH builders
563  */
564 
565 /* -------------------------------------------------------------------- */
570  const BVHCacheType bvh_cache_type,
571  const MVert *vert,
572  const MEdge *edge,
573  const MFace *face,
574  const MLoop *loop,
575  const MLoopTri *looptri,
576  const float (*vert_normals)[3],
577  BVHTreeFromMesh *r_data)
578 {
579  memset(r_data, 0, sizeof(*r_data));
580 
581  r_data->tree = tree;
582 
583  r_data->vert = vert;
584  r_data->edge = edge;
585  r_data->face = face;
586  r_data->loop = loop;
587  r_data->looptri = looptri;
588  r_data->vert_normals = vert_normals;
589 
590  switch (bvh_cache_type) {
591  case BVHTREE_FROM_VERTS:
593  /* a nullptr nearest callback works fine
594  * remember the min distance to point is the same as the min distance to BV of point */
595  r_data->nearest_callback = nullptr;
597  break;
598 
599  case BVHTREE_FROM_EDGES:
603  break;
604  case BVHTREE_FROM_FACES:
607  break;
612  break;
616  case BVHTREE_MAX_ITEM:
617  BLI_assert(false);
618  break;
619  }
620 }
621 
623  const BVHCacheType bvh_cache_type,
624  struct BMEditMesh *em,
625  BVHTreeFromEditMesh *r_data)
626 {
627  memset(r_data, 0, sizeof(*r_data));
628 
629  r_data->tree = tree;
630 
631  r_data->em = em;
632 
633  switch (bvh_cache_type) {
635  r_data->nearest_callback = nullptr;
637  break;
639  r_data->nearest_callback = nullptr; /* TODO */
640  r_data->raycast_callback = nullptr; /* TODO */
641  break;
645  break;
646 
647  case BVHTREE_FROM_VERTS:
649  case BVHTREE_FROM_EDGES:
651  case BVHTREE_FROM_FACES:
654  case BVHTREE_MAX_ITEM:
655  BLI_assert(false);
656  break;
657  }
658 }
659 
662 /* -------------------------------------------------------------------- */
667  int tree_type,
668  int axis,
669  BMEditMesh *em,
670  const BLI_bitmap *verts_mask,
671  int verts_num_active)
672 {
674  const int verts_num = em->bm->totvert;
675  if (verts_mask) {
676  BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num));
677  }
678  else {
679  verts_num_active = verts_num;
680  }
681 
682  BVHTree *tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis);
683 
684  if (tree) {
685  for (int i = 0; i < verts_num; i++) {
686  if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
687  continue;
688  }
689  BMVert *eve = BM_vert_at_index(em->bm, i);
690  BLI_bvhtree_insert(tree, i, eve->co, 1);
691  }
692  BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);
693  }
694 
695  return tree;
696 }
697 
699  int tree_type,
700  int axis,
701  const MVert *vert,
702  const int verts_num,
703  const BLI_bitmap *verts_mask,
704  int verts_num_active)
705 {
706  BVHTree *tree = nullptr;
707 
708  if (verts_mask) {
709  BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num));
710  }
711  else {
712  verts_num_active = verts_num;
713  }
714 
715  if (verts_num_active) {
716  tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis);
717 
718  if (tree) {
719  for (int i = 0; i < verts_num; i++) {
720  if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
721  continue;
722  }
723  BLI_bvhtree_insert(tree, i, vert[i].co, 1);
724  }
725  BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);
726  }
727  }
728 
729  return tree;
730 }
731 
733  BMEditMesh *em,
734  const BLI_bitmap *verts_mask,
735  int verts_num_active,
736  float epsilon,
737  int tree_type,
738  int axis)
739 {
740  BVHTree *tree = nullptr;
742  epsilon, tree_type, axis, em, verts_mask, verts_num_active);
743 
744  bvhtree_balance(tree, false);
745 
746  if (data) {
748  }
749 
750  return tree;
751 }
752 
754  BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
755 {
756  return bvhtree_from_editmesh_verts_ex(data, em, nullptr, -1, epsilon, tree_type, axis);
757 }
758 
760  const MVert *vert,
761  const int verts_num,
762  const BLI_bitmap *verts_mask,
763  int verts_num_active,
764  float epsilon,
765  int tree_type,
766  int axis)
767 {
768  BVHTree *tree = nullptr;
770  epsilon, tree_type, axis, vert, verts_num, verts_mask, verts_num_active);
771 
772  bvhtree_balance(tree, false);
773 
774  if (data) {
775  /* Setup BVHTreeFromMesh */
777  tree, BVHTREE_FROM_VERTS, vert, nullptr, nullptr, nullptr, nullptr, nullptr, data);
778  }
779 
780  return tree;
781 }
782 
785 /* -------------------------------------------------------------------- */
790  int tree_type,
791  int axis,
792  BMEditMesh *em,
793  const BLI_bitmap *edges_mask,
794  int edges_num_active)
795 {
797  const int edges_num = em->bm->totedge;
798 
799  if (edges_mask) {
800  BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edges_num));
801  }
802  else {
803  edges_num_active = edges_num;
804  }
805 
806  BVHTree *tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
807 
808  if (tree) {
809  int i;
810  BMIter iter;
811  BMEdge *eed;
812  BM_ITER_MESH_INDEX (eed, &iter, em->bm, BM_EDGES_OF_MESH, i) {
813  if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
814  continue;
815  }
816  float co[2][3];
817  copy_v3_v3(co[0], eed->v1->co);
818  copy_v3_v3(co[1], eed->v2->co);
819 
820  BLI_bvhtree_insert(tree, i, co[0], 2);
821  }
822  BLI_assert(BLI_bvhtree_get_len(tree) == edges_num_active);
823  }
824 
825  return tree;
826 }
827 
829  const MEdge *edge,
830  const int edge_num,
831  const BLI_bitmap *edges_mask,
832  int edges_num_active,
833  float epsilon,
834  int tree_type,
835  int axis)
836 {
837  BVHTree *tree = nullptr;
838 
839  if (edges_mask) {
840  BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edge_num));
841  }
842  else {
843  edges_num_active = edge_num;
844  }
845 
846  if (edges_num_active) {
847  /* Create a BVH-tree of the given target */
848  tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
849  if (tree) {
850  for (int i = 0; i < edge_num; i++) {
851  if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
852  continue;
853  }
854  float co[2][3];
855  copy_v3_v3(co[0], vert[edge[i].v1].co);
856  copy_v3_v3(co[1], vert[edge[i].v2].co);
857 
858  BLI_bvhtree_insert(tree, i, co[0], 2);
859  }
860  }
861  }
862 
863  return tree;
864 }
865 
867  BMEditMesh *em,
868  const BLI_bitmap *edges_mask,
869  int edges_num_active,
870  float epsilon,
871  int tree_type,
872  int axis)
873 {
874  BVHTree *tree = nullptr;
876  epsilon, tree_type, axis, em, edges_mask, edges_num_active);
877 
878  bvhtree_balance(tree, false);
879 
880  if (data) {
882  }
883 
884  return tree;
885 }
886 
888  BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
889 {
890  return bvhtree_from_editmesh_edges_ex(data, em, nullptr, -1, epsilon, tree_type, axis);
891 }
892 
894  const MVert *vert,
895  const MEdge *edge,
896  const int edges_num,
897  const BLI_bitmap *edges_mask,
898  int edges_num_active,
899  float epsilon,
900  int tree_type,
901  int axis)
902 {
903  BVHTree *tree = nullptr;
905  vert, edge, edges_num, edges_mask, edges_num_active, epsilon, tree_type, axis);
906 
907  bvhtree_balance(tree, false);
908 
909  if (data) {
910  /* Setup BVHTreeFromMesh */
912  tree, BVHTREE_FROM_EDGES, vert, edge, nullptr, nullptr, nullptr, nullptr, data);
913  }
914 
915  return tree;
916 }
917 
920 /* -------------------------------------------------------------------- */
925  int tree_type,
926  int axis,
927  const MVert *vert,
928  const MFace *face,
929  const int faces_num,
930  const BLI_bitmap *faces_mask,
931  int faces_num_active)
932 {
933  BVHTree *tree = nullptr;
934 
935  if (faces_num) {
936  if (faces_mask) {
937  BLI_assert(IN_RANGE_INCL(faces_num_active, 0, faces_num));
938  }
939  else {
940  faces_num_active = faces_num;
941  }
942 
943  /* Create a BVH-tree of the given target. */
944  // printf("%s: building BVH, total=%d\n", __func__, numFaces);
945  tree = BLI_bvhtree_new(faces_num_active, epsilon, tree_type, axis);
946  if (tree) {
947  if (vert && face) {
948  for (int i = 0; i < faces_num; i++) {
949  float co[4][3];
950  if (faces_mask && !BLI_BITMAP_TEST_BOOL(faces_mask, i)) {
951  continue;
952  }
953 
954  copy_v3_v3(co[0], vert[face[i].v1].co);
955  copy_v3_v3(co[1], vert[face[i].v2].co);
956  copy_v3_v3(co[2], vert[face[i].v3].co);
957  if (face[i].v4) {
958  copy_v3_v3(co[3], vert[face[i].v4].co);
959  }
960 
961  BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
962  }
963  }
964  BLI_assert(BLI_bvhtree_get_len(tree) == faces_num_active);
965  }
966  }
967 
968  return tree;
969 }
970 
973 /* -------------------------------------------------------------------- */
978  int tree_type,
979  int axis,
980  BMEditMesh *em,
981  const BLI_bitmap *looptri_mask,
982  int looptri_num_active)
983 {
984  BVHTree *tree = nullptr;
985  const int looptri_num = em->tottri;
986 
987  if (looptri_num) {
988  if (looptri_mask) {
989  BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
990  }
991  else {
992  looptri_num_active = looptri_num;
993  }
994 
995  /* Create a BVH-tree of the given target */
996  // printf("%s: building BVH, total=%d\n", __func__, numFaces);
997  tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
998  if (tree) {
999  const BMLoop *(*looptris)[3] = (const BMLoop *(*)[3])em->looptris;
1000 
1001  /* Insert BMesh-tessellation triangles into the BVH-tree, unless they are hidden
1002  * and/or selected. Even if the faces themselves are not selected for the snapped
1003  * transform, having a vertex selected means the face (and thus it's tessellated
1004  * triangles) will be moving and will not be a good snap targets. */
1005  for (int i = 0; i < looptri_num; i++) {
1006  const BMLoop **ltri = looptris[i];
1007  bool insert = looptri_mask ? BLI_BITMAP_TEST_BOOL(looptri_mask, i) : true;
1008 
1009  if (insert) {
1010  /* No reason found to block hit-testing the triangle for snap, so insert it now. */
1011  float co[3][3];
1012  copy_v3_v3(co[0], ltri[0]->v->co);
1013  copy_v3_v3(co[1], ltri[1]->v->co);
1014  copy_v3_v3(co[2], ltri[2]->v->co);
1015 
1016  BLI_bvhtree_insert(tree, i, co[0], 3);
1017  }
1018  }
1019  BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
1020  }
1021  }
1022 
1023  return tree;
1024 }
1025 
1027  int tree_type,
1028  int axis,
1029  const MVert *vert,
1030  const MLoop *mloop,
1031  const MLoopTri *looptri,
1032  const int looptri_num,
1033  const BLI_bitmap *looptri_mask,
1034  int looptri_num_active)
1035 {
1036  BVHTree *tree = nullptr;
1037 
1038  if (looptri_mask) {
1039  BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
1040  }
1041  else {
1042  looptri_num_active = looptri_num;
1043  }
1044 
1045  if (looptri_num_active) {
1046  /* Create a BVH-tree of the given target */
1047  // printf("%s: building BVH, total=%d\n", __func__, numFaces);
1048  tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
1049  if (tree) {
1050  if (vert && looptri) {
1051  for (int i = 0; i < looptri_num; i++) {
1052  float co[3][3];
1053  if (looptri_mask && !BLI_BITMAP_TEST_BOOL(looptri_mask, i)) {
1054  continue;
1055  }
1056 
1057  copy_v3_v3(co[0], vert[mloop[looptri[i].tri[0]].v].co);
1058  copy_v3_v3(co[1], vert[mloop[looptri[i].tri[1]].v].co);
1059  copy_v3_v3(co[2], vert[mloop[looptri[i].tri[2]].v].co);
1060 
1061  BLI_bvhtree_insert(tree, i, co[0], 3);
1062  }
1063  }
1064  BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
1065  }
1066  }
1067 
1068  return tree;
1069 }
1070 
1072  BMEditMesh *em,
1073  const BLI_bitmap *looptri_mask,
1074  int looptri_num_active,
1075  float epsilon,
1076  int tree_type,
1077  int axis)
1078 {
1079  /* BMESH specific check that we have tessfaces,
1080  * we _could_ tessellate here but rather not - campbell */
1081 
1082  BVHTree *tree = nullptr;
1084  epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);
1085 
1086  bvhtree_balance(tree, false);
1087 
1088  if (data) {
1090  }
1091  return tree;
1092 }
1093 
1095  BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
1096 {
1097  return bvhtree_from_editmesh_looptri_ex(data, em, nullptr, -1, epsilon, tree_type, axis);
1098 }
1099 
1101  const struct MVert *vert,
1102  const struct MLoop *mloop,
1103  const struct MLoopTri *looptri,
1104  const int looptri_num,
1105  const BLI_bitmap *looptri_mask,
1106  int looptri_num_active,
1107  float epsilon,
1108  int tree_type,
1109  int axis)
1110 {
1111  BVHTree *tree = nullptr;
1113  tree_type,
1114  axis,
1115  vert,
1116  mloop,
1117  looptri,
1118  looptri_num,
1119  looptri_mask,
1120  looptri_num_active);
1121 
1122  bvhtree_balance(tree, false);
1123 
1124  if (data) {
1125  /* Setup BVHTreeFromMesh */
1127  tree, BVHTREE_FROM_LOOPTRI, vert, nullptr, nullptr, mloop, looptri, nullptr, data);
1128  }
1129 
1130  return tree;
1131 }
1132 
1133 static BLI_bitmap *loose_verts_map_get(const MEdge *medge,
1134  int edges_num,
1135  const MVert *UNUSED(mvert),
1136  int verts_num,
1137  int *r_loose_vert_num)
1138 {
1139  BLI_bitmap *loose_verts_mask = BLI_BITMAP_NEW(verts_num, __func__);
1140  BLI_bitmap_set_all(loose_verts_mask, true, verts_num);
1141 
1142  const MEdge *e = medge;
1143  int num_linked_verts = 0;
1144  for (; edges_num--; e++) {
1145  if (BLI_BITMAP_TEST(loose_verts_mask, e->v1)) {
1146  BLI_BITMAP_DISABLE(loose_verts_mask, e->v1);
1147  num_linked_verts++;
1148  }
1149  if (BLI_BITMAP_TEST(loose_verts_mask, e->v2)) {
1150  BLI_BITMAP_DISABLE(loose_verts_mask, e->v2);
1151  num_linked_verts++;
1152  }
1153  }
1154 
1155  *r_loose_vert_num = verts_num - num_linked_verts;
1156 
1157  return loose_verts_mask;
1158 }
1159 
1160 static BLI_bitmap *loose_edges_map_get(const MEdge *medge,
1161  const int edges_len,
1162  int *r_loose_edge_len)
1163 {
1164  BLI_bitmap *loose_edges_mask = BLI_BITMAP_NEW(edges_len, __func__);
1165 
1166  int loose_edges_len = 0;
1167  const MEdge *e = medge;
1168  for (int i = 0; i < edges_len; i++, e++) {
1169  if (e->flag & ME_LOOSEEDGE) {
1170  BLI_BITMAP_ENABLE(loose_edges_mask, i);
1171  loose_edges_len++;
1172  }
1173  else {
1174  BLI_BITMAP_DISABLE(loose_edges_mask, i);
1175  }
1176  }
1177 
1178  *r_loose_edge_len = loose_edges_len;
1179 
1180  return loose_edges_mask;
1181 }
1182 
1184  const int looptri_len,
1185  int *r_looptri_active_len)
1186 {
1187  BLI_bitmap *looptri_mask = BLI_BITMAP_NEW(looptri_len, __func__);
1188 
1189  int looptri_no_hidden_len = 0;
1190  int looptri_iter = 0;
1191  int i_poly = 0;
1192  while (looptri_iter != looptri_len) {
1193  int mp_totlooptri = mpoly[i_poly].totloop - 2;
1194  const MPoly &mp = mpoly[i_poly];
1195  if (mp.flag & ME_HIDE) {
1196  looptri_iter += mp_totlooptri;
1197  }
1198  else {
1199  while (mp_totlooptri--) {
1200  BLI_BITMAP_ENABLE(looptri_mask, looptri_iter);
1201  looptri_iter++;
1202  looptri_no_hidden_len++;
1203  }
1204  }
1205  i_poly++;
1206  }
1207 
1208  *r_looptri_active_len = looptri_no_hidden_len;
1209 
1210  return looptri_mask;
1211 }
1212 
1214  const struct Mesh *mesh,
1215  const BVHCacheType bvh_cache_type,
1216  const int tree_type)
1217 {
1218  BVHCache **bvh_cache_p = (BVHCache **)&mesh->runtime.bvh_cache;
1219  ThreadMutex *mesh_eval_mutex = (ThreadMutex *)mesh->runtime.eval_mutex;
1220 
1221  const MLoopTri *looptri = nullptr;
1222  int looptri_len = 0;
1225  looptri_len = BKE_mesh_runtime_looptri_len(mesh);
1226  }
1227 
1228  /* Setup BVHTreeFromMesh */
1230  bvh_cache_type,
1231  mesh->mvert,
1232  mesh->medge,
1233  mesh->mface,
1234  mesh->mloop,
1235  looptri,
1237  data);
1238 
1239  bool lock_started = false;
1240  data->cached = bvhcache_find(
1241  bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);
1242 
1243  if (data->cached) {
1244  BLI_assert(lock_started == false);
1245 
1246  /* NOTE: #data->tree can be nullptr. */
1247  return data->tree;
1248  }
1249 
1250  /* Create BVHTree. */
1251 
1252  BLI_bitmap *mask = nullptr;
1253  int mask_bits_act_len = -1;
1254 
1255  switch (bvh_cache_type) {
1258  mesh->medge, mesh->totedge, mesh->mvert, mesh->totvert, &mask_bits_act_len);
1260  case BVHTREE_FROM_VERTS:
1262  0.0f, tree_type, 6, mesh->mvert, mesh->totvert, mask, mask_bits_act_len);
1263  break;
1264 
1266  mask = loose_edges_map_get(mesh->medge, mesh->totedge, &mask_bits_act_len);
1268  case BVHTREE_FROM_EDGES:
1270  mesh->mvert, mesh->medge, mesh->totedge, mask, mask_bits_act_len, 0.0f, tree_type, 6);
1271  break;
1272 
1273  case BVHTREE_FROM_FACES:
1274  BLI_assert(!(mesh->totface == 0 && mesh->totpoly != 0));
1276  0.0f, tree_type, 6, mesh->mvert, mesh->mface, mesh->totface, nullptr, -1);
1277  break;
1278 
1280  mask = looptri_no_hidden_map_get(mesh->mpoly, looptri_len, &mask_bits_act_len);
1282  case BVHTREE_FROM_LOOPTRI:
1284  tree_type,
1285  6,
1286  mesh->mvert,
1287  mesh->mloop,
1288  looptri,
1289  looptri_len,
1290  mask,
1291  mask_bits_act_len);
1292  break;
1293  case BVHTREE_FROM_EM_VERTS:
1294  case BVHTREE_FROM_EM_EDGES:
1296  case BVHTREE_MAX_ITEM:
1297  BLI_assert(false);
1298  break;
1299  }
1300 
1301  if (mask != nullptr) {
1302  MEM_freeN(mask);
1303  }
1304 
1305  bvhtree_balance(data->tree, lock_started);
1306 
1307  /* Save on cache for later use */
1308  // printf("BVHTree built and saved on cache\n");
1309  BLI_assert(data->cached == false);
1310  data->cached = true;
1311  bvhcache_insert(*bvh_cache_p, data->tree, bvh_cache_type);
1312  bvhcache_unlock(*bvh_cache_p, lock_started);
1313 
1314 #ifdef DEBUG
1315  if (data->tree != nullptr) {
1316  if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {
1317  printf("tree_type %d obtained instead of %d\n",
1319  tree_type);
1320  }
1321  }
1322 #endif
1323 
1324  return data->tree;
1325 }
1326 
1328  struct BMEditMesh *em,
1329  const int tree_type,
1330  const BVHCacheType bvh_cache_type,
1331  BVHCache **bvh_cache_p,
1332  ThreadMutex *mesh_eval_mutex)
1333 {
1334  bool lock_started = false;
1335 
1336  bvhtree_from_editmesh_setup_data(nullptr, bvh_cache_type, em, data);
1337 
1338  if (bvh_cache_p) {
1339  data->cached = bvhcache_find(
1340  bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);
1341 
1342  if (data->cached) {
1343  BLI_assert(lock_started == false);
1344  return data->tree;
1345  }
1346  }
1347 
1348  switch (bvh_cache_type) {
1349  case BVHTREE_FROM_EM_VERTS:
1350  data->tree = bvhtree_from_editmesh_verts_create_tree(0.0f, tree_type, 6, em, nullptr, -1);
1351  break;
1352  case BVHTREE_FROM_EM_EDGES:
1353  data->tree = bvhtree_from_editmesh_edges_create_tree(0.0f, tree_type, 6, em, nullptr, -1);
1354  break;
1356  data->tree = bvhtree_from_editmesh_looptri_create_tree(0.0f, tree_type, 6, em, nullptr, -1);
1357  break;
1358  case BVHTREE_FROM_VERTS:
1359  case BVHTREE_FROM_EDGES:
1360  case BVHTREE_FROM_FACES:
1361  case BVHTREE_FROM_LOOPTRI:
1365  case BVHTREE_MAX_ITEM:
1366  BLI_assert(false);
1367  break;
1368  }
1369 
1370  bvhtree_balance(data->tree, lock_started);
1371 
1372  if (bvh_cache_p) {
1373  /* Save on cache for later use */
1374  // printf("BVHTree built and saved on cache\n");
1375  BLI_assert(data->cached == false);
1376  data->cached = true;
1377  bvhcache_insert(*bvh_cache_p, data->tree, bvh_cache_type);
1378  bvhcache_unlock(*bvh_cache_p, lock_started);
1379  }
1380 
1381 #ifdef DEBUG
1382  if (data->tree != nullptr) {
1383  if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {
1384  printf("tree_type %d obtained instead of %d\n",
1386  tree_type);
1387  }
1388  }
1389 #endif
1390 
1391  return data->tree;
1392 }
1393 
1396 /* -------------------------------------------------------------------- */
1401 {
1402  if (data->tree) {
1403  if (!data->cached) {
1404  BLI_bvhtree_free(data->tree);
1405  }
1406  memset(data, 0, sizeof(*data));
1407  }
1408 }
1409 
1411 {
1412  if (data->tree && !data->cached) {
1413  BLI_bvhtree_free(data->tree);
1414  }
1415 
1416  memset(data, 0, sizeof(*data));
1417 }
1418 
1421 /* -------------------------------------------------------------------- */
1426  const PointCloud *pointcloud,
1427  const int tree_type)
1428 {
1429  BVHTree *tree = BLI_bvhtree_new(pointcloud->totpoint, 0.0f, tree_type, 6);
1430  if (!tree) {
1431  return nullptr;
1432  }
1433 
1436  "position", ATTR_DOMAIN_POINT, blender::float3(0));
1437 
1438  for (const int i : positions.index_range()) {
1439  BLI_bvhtree_insert(tree, i, positions[i], 1);
1440  }
1441  BLI_assert(BLI_bvhtree_get_len(tree) == pointcloud->totpoint);
1442  bvhtree_balance(tree, false);
1443 
1444  data->coords = (const float(*)[3])positions.data();
1445  data->tree = tree;
1446  data->nearest_callback = nullptr;
1447 
1448  return tree;
1449 }
1450 
1452 {
1453  if (data->tree) {
1454  BLI_bvhtree_free(data->tree);
1455  }
1456  memset(data, 0, sizeof(*data));
1457 }
1458 
typedef float(TangentPoint)[2]
@ ATTR_DOMAIN_POINT
Definition: BKE_attribute.h:27
BVHCacheType
Definition: BKE_bvhutils.h:69
@ BVHTREE_FROM_EDGES
Definition: BKE_bvhutils.h:71
@ BVHTREE_FROM_EM_EDGES
Definition: BKE_bvhutils.h:80
@ BVHTREE_FROM_FACES
Definition: BKE_bvhutils.h:72
@ BVHTREE_FROM_LOOPTRI
Definition: BKE_bvhutils.h:73
@ BVHTREE_FROM_LOOSEEDGES
Definition: BKE_bvhutils.h:77
@ BVHTREE_FROM_EM_VERTS
Definition: BKE_bvhutils.h:79
@ BVHTREE_FROM_LOOSEVERTS
Definition: BKE_bvhutils.h:76
@ BVHTREE_FROM_EM_LOOPTRI
Definition: BKE_bvhutils.h:81
@ BVHTREE_FROM_LOOPTRI_NO_HIDDEN
Definition: BKE_bvhutils.h:74
@ BVHTREE_MAX_ITEM
Definition: BKE_bvhutils.h:84
@ BVHTREE_FROM_VERTS
Definition: BKE_bvhutils.h:70
const float(* BKE_mesh_vertex_normals_ensure(const struct Mesh *mesh))[3]
const struct MLoopTri * BKE_mesh_runtime_looptri_ensure(const struct Mesh *mesh)
int BKE_mesh_runtime_looptri_len(const struct Mesh *mesh)
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition: BLI_bitmap.h:40
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition: BLI_bitmap.h:64
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition: BLI_bitmap.h:81
#define BLI_BITMAP_DISABLE(_bitmap, _index)
Definition: BLI_bitmap.h:88
#define BLI_BITMAP_TEST_BOOL(_bitmap, _index)
Definition: BLI_bitmap.h:74
void BLI_bitmap_set_all(BLI_bitmap *bitmap, bool set, size_t bits)
Definition: bitmap.c:17
unsigned int BLI_bitmap
Definition: BLI_bitmap.h:16
#define ATTR_FALLTHROUGH
int BLI_bvhtree_get_tree_type(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1039
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
int BLI_bvhtree_get_len(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1034
MINLINE float square_f(float a)
int isect_line_line_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3])
Definition: math_geom.c:2935
float closest_to_line_segment_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
Definition: math_geom.c:379
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_sweeping_sphere_tri_v3(const float p1[3], const float p2[3], float radius, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float ipoint[3])
Definition: math_geom.c:2626
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
Definition: math_geom.c:3254
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:33
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_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE float dot_v3v3v3(const float p[3], const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE bool equals_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
void BLI_task_isolate(void(*func)(void *userdata), void *userdata)
void BLI_mutex_end(ThreadMutex *mutex)
Definition: threads.cc:388
void BLI_mutex_init(ThreadMutex *mutex)
Definition: threads.cc:368
void BLI_mutex_lock(ThreadMutex *mutex)
Definition: threads.cc:373
void BLI_mutex_unlock(ThreadMutex *mutex)
Definition: threads.cc:378
pthread_mutex_t ThreadMutex
Definition: BLI_threads.h:82
#define UNUSED(x)
#define UNPACK3(a)
#define ELEM(...)
#define IN_RANGE_INCL(a, b, c)
@ ME_HIDE
@ ME_LOOSEEDGE
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint i1
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_EDGE
Definition: bmesh_class.h:384
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
@ BM_EDGES_OF_MESH
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:558
BLI_INLINE BMVert * BM_vert_at_index(BMesh *bm, const int index)
Definition: bmesh_mesh.h:103
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
BVHTree * bvhtree_from_mesh_edges_ex(BVHTreeFromMesh *data, const MVert *vert, const MEdge *edge, const int edges_num, const BLI_bitmap *edges_mask, int edges_num_active, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:893
BVHTree * bvhtree_from_editmesh_looptri(BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:1094
BVHTree * bvhtree_from_mesh_verts_ex(BVHTreeFromMesh *data, const MVert *vert, const int verts_num, const BLI_bitmap *verts_mask, int verts_num_active, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:759
bool bvhcache_has_tree(const BVHCache *bvh_cache, const BVHTree *tree)
Definition: bvhutils.cc:99
static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: bvhutils.cc:323
static BLI_bitmap * loose_edges_map_get(const MEdge *medge, const int edges_len, int *r_loose_edge_len)
Definition: bvhutils.cc:1160
static BVHTree * bvhtree_from_mesh_faces_create_tree(float epsilon, int tree_type, int axis, const MVert *vert, const MFace *face, const int faces_num, const BLI_bitmap *faces_mask, int faces_num_active)
Definition: bvhutils.cc:924
static void mesh_looptri_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition: bvhutils.cc:262
static BVHTree * bvhtree_from_mesh_verts_create_tree(float epsilon, int tree_type, int axis, const MVert *vert, const int verts_num, const BLI_bitmap *verts_mask, int verts_num_active)
Definition: bvhutils.cc:698
static BVHTree * bvhtree_from_mesh_looptri_create_tree(float epsilon, int tree_type, int axis, const MVert *vert, const MLoop *mloop, const MLoopTri *looptri, const int looptri_num, const BLI_bitmap *looptri_mask, int looptri_num_active)
Definition: bvhutils.cc:1026
BVHTree * BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data, struct BMEditMesh *em, const int tree_type, const BVHCacheType bvh_cache_type, BVHCache **bvh_cache_p, ThreadMutex *mesh_eval_mutex)
Definition: bvhutils.cc:1327
BVHTree * bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data, BMEditMesh *em, const BLI_bitmap *verts_mask, int verts_num_active, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:732
void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
Definition: bvhutils.cc:1410
void free_bvhtree_from_pointcloud(BVHTreeFromPointCloud *data)
Definition: bvhutils.cc:1451
static void bvhtree_from_editmesh_setup_data(BVHTree *tree, const BVHCacheType bvh_cache_type, struct BMEditMesh *em, BVHTreeFromEditMesh *r_data)
Definition: bvhutils.cc:622
BVHTree * bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data, BMEditMesh *em, const BLI_bitmap *looptri_mask, int looptri_num_active, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:1071
static void mesh_looptri_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: bvhutils.cc:362
BVHTree * BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data, const struct Mesh *mesh, const BVHCacheType bvh_cache_type, const int tree_type)
Definition: bvhutils.cc:1213
static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition: bvhutils.cc:227
static void bvhtree_balance_isolated(void *userdata)
Definition: bvhutils.cc:151
static BVHTree * bvhtree_from_editmesh_looptri_create_tree(float epsilon, int tree_type, int axis, BMEditMesh *em, const BLI_bitmap *looptri_mask, int looptri_num_active)
Definition: bvhutils.cc:977
static void bvhcache_insert(BVHCache *bvh_cache, BVHTree *tree, BVHCacheType type)
Definition: bvhutils.cc:127
static void mesh_verts_spherecast_do(int index, const float v[3], const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: bvhutils.cc:459
BVHTree * BKE_bvhtree_from_pointcloud_get(BVHTreeFromPointCloud *data, const PointCloud *pointcloud, const int tree_type)
Definition: bvhutils.cc:1425
float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_dist), const float v0[3], const float v1[3], const float v2[3])
Definition: bvhutils.cc:176
BVHTree * bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data, const struct MVert *vert, const struct MLoop *mloop, const struct MLoopTri *looptri, const int looptri_num, const BLI_bitmap *looptri_mask, int looptri_num_active, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:1100
static BLI_bitmap * looptri_no_hidden_map_get(const MPoly *mpoly, const int looptri_len, int *r_looptri_active_len)
Definition: bvhutils.cc:1183
static BVHTree * bvhtree_from_editmesh_verts_create_tree(float epsilon, int tree_type, int axis, BMEditMesh *em, const BLI_bitmap *verts_mask, int verts_num_active)
Definition: bvhutils.cc:666
static void editmesh_looptri_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: bvhutils.cc:393
static void bvhtree_from_mesh_setup_data(BVHTree *tree, const BVHCacheType bvh_cache_type, const MVert *vert, const MEdge *edge, const MFace *face, const MLoop *loop, const MLoopTri *looptri, const float(*vert_normals)[3], BVHTreeFromMesh *r_data)
Definition: bvhutils.cc:569
static BVHTree * bvhtree_from_editmesh_edges_create_tree(float epsilon, int tree_type, int axis, BMEditMesh *em, const BLI_bitmap *edges_mask, int edges_num_active)
Definition: bvhutils.cc:789
static void bvhtree_balance(BVHTree *tree, const bool isolate)
Definition: bvhutils.cc:156
BVHCache * bvhcache_init()
Definition: bvhutils.cc:113
BVHTree * bvhtree_from_editmesh_edges(BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:887
static void editmesh_verts_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: bvhutils.cc:480
BVHTree * bvhtree_from_editmesh_verts(BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:753
static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: bvhutils.cc:514
static bool bvhcache_find(BVHCache **bvh_cache_p, BVHCacheType type, BVHTree **r_tree, bool *r_locked, ThreadMutex *mesh_eval_mutex)
Definition: bvhutils.cc:52
static BVHTree * bvhtree_from_mesh_edges_create_tree(const MVert *vert, const MEdge *edge, const int edge_num, const BLI_bitmap *edges_mask, int edges_num_active, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:828
static void bvhcache_unlock(BVHCache *bvh_cache, bool lock_started)
Definition: bvhutils.cc:92
BVHTree * bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data, BMEditMesh *em, const BLI_bitmap *edges_mask, int edges_num_active, float epsilon, int tree_type, int axis)
Definition: bvhutils.cc:866
void free_bvhtree_from_editmesh(struct BVHTreeFromEditMesh *data)
Definition: bvhutils.cc:1400
static BLI_bitmap * loose_verts_map_get(const MEdge *medge, int edges_num, const MVert *UNUSED(mvert), int verts_num, int *r_loose_vert_num)
Definition: bvhutils.cc:1133
static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition: bvhutils.cc:432
void bvhcache_free(BVHCache *bvh_cache)
Definition: bvhutils.cc:135
static void mesh_verts_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: bvhutils.cc:497
static void editmesh_looptri_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition: bvhutils.cc:288
float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray, float radius, const float m_dist, const float v0[3], const float v1[3], const float v2[3])
Definition: bvhutils.cc:197
GVArray lookup_or_default(const AttributeIDRef &attribute_id, const eAttrDomain domain, const eCustomDataType data_type, const void *default_value=nullptr) const
void * tree
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
ccl_device_inline float4 mask(const int4 &mask, const float4 &a)
Definition: math_float4.h:513
Insertion insert(const float3 &point_prev, const float3 &handle_prev, const float3 &handle_next, const float3 &point_next, float parameter)
Definition: curve_bezier.cc:61
AttributeAccessor pointcloud_attributes(const PointCloud &pointcloud)
static double epsilon
vec_base< float, 3 > float3
MutableSpan< float3 > positions
BMVert * v1
Definition: bmesh_class.h:122
BMVert * v2
Definition: bmesh_class.h:122
struct BMLoop *(* looptris)[3]
Definition: BKE_editmesh.h:48
struct BMesh * bm
Definition: BKE_editmesh.h:40
struct BMVert * v
Definition: bmesh_class.h:153
float co[3]
Definition: bmesh_class.h:87
int totvert
Definition: bmesh_class.h:297
int totedge
Definition: bmesh_class.h:297
bool is_filled
Definition: bvhutils.cc:35
BVHTree * tree
Definition: bvhutils.cc:36
ThreadMutex mutex
Definition: bvhutils.cc:41
BVHCacheItem items[BVHTREE_MAX_ITEM]
Definition: bvhutils.cc:40
struct BVHTree * tree
Definition: BKE_bvhutils.h:33
struct BMEditMesh * em
Definition: BKE_bvhutils.h:39
BVHTree_NearestPointCallback nearest_callback
Definition: BKE_bvhutils.h:36
BVHTree_RayCastCallback raycast_callback
Definition: BKE_bvhutils.h:37
BVHTree_RayCastCallback raycast_callback
Definition: BKE_bvhutils.h:54
const struct MFace * face
Definition: BKE_bvhutils.h:60
const struct MEdge * edge
Definition: BKE_bvhutils.h:59
const float(* vert_normals)[3]
Definition: BKE_bvhutils.h:58
const struct MLoop * loop
Definition: BKE_bvhutils.h:61
struct BVHTree * tree
Definition: BKE_bvhutils.h:50
const struct MVert * vert
Definition: BKE_bvhutils.h:57
BVHTree_NearestPointCallback nearest_callback
Definition: BKE_bvhutils.h:53
const struct MLoopTri * looptri
Definition: BKE_bvhutils.h:62
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
unsigned int v2
unsigned int v1
unsigned int v4
unsigned int v3
unsigned int tri[3]
float co[3]
struct BVHCache * bvh_cache
void * eval_mutex
struct MEdge * medge
struct MVert * mvert
int totedge
int totvert
struct MLoop * mloop
int totface
Mesh_Runtime runtime
int totpoly
struct MFace * mface
struct MPoly * mpoly