Blender V5.3
bvhutils.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
11
12#include "BLI_math_geom_c.hh"
13
14#include "BKE_attribute.hh"
15#include "BKE_bvhutils.hh"
16#include "BKE_editmesh.hh"
17#include "BKE_mesh.hh"
18#include "BKE_pointcloud.hh"
19
20namespace blender {
21
22namespace bke {
23
24/* -------------------------------------------------------------------- */
27
28/* Math stuff for ray casting on mesh faces and for nearest surface */
29
31 const float /*m_dist*/,
32 const float v0[3],
33 const float v1[3],
34 const float v2[3])
35{
36 float dist;
37
38#ifdef USE_KDOPBVH_WATERTIGHT
39 if (isect_ray_tri_watertight_v3(ray->origin, ray->isect_precalc, v0, v1, v2, &dist, nullptr))
40#else
42 ray->origin, ray->direction, v0, v1, v2, &dist, nullptr, FLT_EPSILON))
43#endif
44 {
45 return dist;
46 }
47
48 return FLT_MAX;
49}
50
52 float radius,
53 const float m_dist,
54 const float v0[3],
55 const float v1[3],
56 const float v2[3])
57{
58
59 float idist;
60 float p1[3];
61 float hit_point[3];
62
63 madd_v3_v3v3fl(p1, ray->origin, ray->direction, m_dist);
64 if (isect_sweeping_sphere_tri_v3(ray->origin, p1, radius, v0, v1, v2, &idist, hit_point)) {
65 return idist * m_dist;
66 }
67
68 return FLT_MAX;
69}
70
71/*
72 * BVH from meshes callbacks
73 */
74
81static void mesh_faces_nearest_point(void *userdata,
82 int index,
83 const float co[3],
84 BVHTreeNearest *nearest)
85{
86 const BVHTreeFromMesh *data = static_cast<BVHTreeFromMesh *>(userdata);
87 const MFace *face = data->face + index;
88
89 const float *t0, *t1, *t2, *t3;
90 t0 = data->vert_positions[face->v1];
91 t1 = data->vert_positions[face->v2];
92 t2 = data->vert_positions[face->v3];
93 t3 = face->v4 ? &data->vert_positions[face->v4].x : nullptr;
94
95 do {
96 float nearest_tmp[3], dist_sq;
97
98 closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
99 dist_sq = len_squared_v3v3(co, nearest_tmp);
100
101 if (dist_sq < nearest->dist_sq) {
102 nearest->index = index;
103 nearest->dist_sq = dist_sq;
104 copy_v3_v3(nearest->co, nearest_tmp);
105 normal_tri_v3(nearest->no, t0, t1, t2);
106 }
107
108 t1 = t2;
109 t2 = t3;
110 t3 = nullptr;
111
112 } while (t2);
113}
114/* copy of function above */
115static void mesh_corner_tris_nearest_point(void *userdata,
116 int index,
117 const float co[3],
118 BVHTreeNearest *nearest)
119{
120 const BVHTreeFromMesh *data = static_cast<BVHTreeFromMesh *>(userdata);
121 const int3 &tri = data->corner_tris[index];
122 const float *vtri_co[3] = {
123 data->vert_positions[data->corner_verts[tri[0]]],
124 data->vert_positions[data->corner_verts[tri[1]]],
125 data->vert_positions[data->corner_verts[tri[2]]],
126 };
127 float nearest_tmp[3], dist_sq;
128
129 closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(vtri_co));
130 dist_sq = len_squared_v3v3(co, nearest_tmp);
131
132 if (dist_sq < nearest->dist_sq) {
133 nearest->index = index;
134 nearest->dist_sq = dist_sq;
135 copy_v3_v3(nearest->co, nearest_tmp);
136 normal_tri_v3(nearest->no, UNPACK3(vtri_co));
137 }
138}
139
146static void mesh_faces_spherecast(void *userdata,
147 int index,
148 const BVHTreeRay *ray,
149 BVHTreeRayHit *hit)
150{
151 const BVHTreeFromMesh *data = static_cast<BVHTreeFromMesh *>(userdata);
152 const MFace *face = &data->face[index];
153
154 const float *t0, *t1, *t2, *t3;
155 t0 = data->vert_positions[face->v1];
156 t1 = data->vert_positions[face->v2];
157 t2 = data->vert_positions[face->v3];
158 t3 = face->v4 ? &data->vert_positions[face->v4].x : nullptr;
159
160 do {
161 float dist;
162 if (ray->radius == 0.0f) {
163 dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
164 }
165 else {
166 dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, t0, t1, t2);
167 }
168
169 if (dist >= 0 && dist < hit->dist) {
170 hit->index = index;
171 hit->dist = dist;
172 madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
173
174 normal_tri_v3(hit->no, t0, t1, t2);
175 }
176
177 t1 = t2;
178 t2 = t3;
179 t3 = nullptr;
180
181 } while (t2);
182}
183/* copy of function above */
184static void mesh_corner_tris_spherecast(void *userdata,
185 int index,
186 const BVHTreeRay *ray,
187 BVHTreeRayHit *hit)
188{
189 const BVHTreeFromMesh *data = static_cast<BVHTreeFromMesh *>(userdata);
190 const Span<float3> positions = data->vert_positions;
191 const int3 &tri = data->corner_tris[index];
192 const float *vtri_co[3] = {
193 positions[data->corner_verts[tri[0]]],
194 positions[data->corner_verts[tri[1]]],
195 positions[data->corner_verts[tri[2]]],
196 };
197 float dist;
198
199 if (ray->radius == 0.0f) {
200 dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(vtri_co));
201 }
202 else {
203 dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, UNPACK3(vtri_co));
204 }
205
206 if (dist >= 0 && dist < hit->dist) {
207 hit->index = index;
208 hit->dist = dist;
209 madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
210
211 normal_tri_v3(hit->no, UNPACK3(vtri_co));
212 }
213}
214
221static void mesh_edges_nearest_point(void *userdata,
222 int index,
223 const float co[3],
224 BVHTreeNearest *nearest)
225{
226 const BVHTreeFromMesh *data = static_cast<BVHTreeFromMesh *>(userdata);
227 const Span<float3> positions = data->vert_positions;
228 const int2 edge = data->edges[index];
229 float nearest_tmp[3], dist_sq;
230
231 const float *t0, *t1;
232 t0 = positions[edge[0]];
233 t1 = positions[edge[1]];
234
235 closest_to_line_segment_v3(nearest_tmp, co, t0, t1);
236 dist_sq = len_squared_v3v3(nearest_tmp, co);
237
238 if (dist_sq < nearest->dist_sq) {
239 nearest->index = index;
240 nearest->dist_sq = dist_sq;
241 copy_v3_v3(nearest->co, nearest_tmp);
242 sub_v3_v3v3(nearest->no, t0, t1);
243 normalize_v3(nearest->no);
244 }
245}
246
247/* Helper, does all the point-sphere-cast work actually. */
249 const float v[3],
250 const BVHTreeRay *ray,
251 BVHTreeRayHit *hit)
252{
253 const float *r1;
254 float r2[3], i1[3];
255 r1 = ray->origin;
256 add_v3_v3v3(r2, r1, ray->direction);
257
258 closest_to_line_segment_v3(i1, v, r1, r2);
259
260 /* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */
261 if (dot_v3v3v3(r1, i1, r2) >= 0.0f) {
262 const float dist = len_v3v3(r1, i1);
263 if (dist < hit->dist) {
264 hit->index = index;
265 hit->dist = dist;
266 copy_v3_v3(hit->co, i1);
267 }
268 }
269}
270
277static void mesh_verts_spherecast(void *userdata,
278 int index,
279 const BVHTreeRay *ray,
280 BVHTreeRayHit *hit)
281{
282 const BVHTreeFromMesh *data = static_cast<BVHTreeFromMesh *>(userdata);
283 const float *v = data->vert_positions[index];
284
285 mesh_verts_spherecast_do(index, v, ray, hit);
286}
287
294static void mesh_edges_spherecast(void *userdata,
295 int index,
296 const BVHTreeRay *ray,
297 BVHTreeRayHit *hit)
298{
299 const BVHTreeFromMesh *data = static_cast<BVHTreeFromMesh *>(userdata);
300 const Span<float3> positions = data->vert_positions;
301 const int2 edge = data->edges[index];
302
303 const float radius_sq = square_f(ray->radius);
304 const float *v1, *v2, *r1;
305 float r2[3], i1[3], i2[3];
306 v1 = positions[edge[0]];
307 v2 = positions[edge[1]];
308
309 /* In case we get a zero-length edge, handle it as a point! */
310 if (equals_v3v3(v1, v2)) {
311 mesh_verts_spherecast_do(index, v1, ray, hit);
312 return;
313 }
314
315 r1 = ray->origin;
316 add_v3_v3v3(r2, r1, ray->direction);
317
318 if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) {
319 /* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */
320 if (dot_v3v3v3(r1, i2, r2) >= 0.0f) {
321 const float dist = len_v3v3(r1, i2);
322 if (dist < hit->dist) {
323 const float e_fac = line_point_factor_v3(i1, v1, v2);
324 if (e_fac < 0.0f) {
325 copy_v3_v3(i1, v1);
326 }
327 else if (e_fac > 1.0f) {
328 copy_v3_v3(i1, v2);
329 }
330 /* Ensure ray is really close enough from edge! */
331 if (len_squared_v3v3(i1, i2) <= radius_sq) {
332 hit->index = index;
333 hit->dist = dist;
334 copy_v3_v3(hit->co, i2);
335 }
336 }
337 }
338 }
339}
340
342
343/*
344 * BVH builders
345 */
346
347/* -------------------------------------------------------------------- */
350
351static BVHTreeFromMesh create_verts_tree_data(const BVHTree *tree, const Span<float3> positions)
352{
354 data.tree = tree;
355 data.vert_positions = positions;
356 /* a nullptr nearest callback works fine
357 * remember the min distance to point is the same as the min distance to BV of point */
358 data.nearest_callback = nullptr;
359 data.raycast_callback = mesh_verts_spherecast;
360 return data;
361}
362
363static BVHTreeFromMesh create_verts_tree_data(std::unique_ptr<BVHTree, BVHTreeDeleter> tree,
364 const Span<float3> positions)
365{
366 BVHTreeFromMesh data = create_verts_tree_data(tree.get(), positions);
367 data.owned_tree = std::move(tree);
368 return data;
369}
370
372 const Span<float3> positions,
373 const Span<int2> edges)
374{
376 data.tree = tree;
377 data.vert_positions = positions;
378 data.edges = edges;
379 data.nearest_callback = mesh_edges_nearest_point;
380 data.raycast_callback = mesh_edges_spherecast;
381 return data;
382}
383
384static BVHTreeFromMesh create_edges_tree_data(std::unique_ptr<BVHTree, BVHTreeDeleter> tree,
385 const Span<float3> positions,
386 const Span<int2> edges)
387{
388 BVHTreeFromMesh data = create_edges_tree_data(tree.get(), positions, edges);
389 data.owned_tree = std::move(tree);
390 return data;
391}
392
394 const Span<float3> positions,
395 const MFace *face)
396{
398 data.tree = tree;
399 data.vert_positions = positions;
400 data.face = face;
401 data.nearest_callback = mesh_faces_nearest_point;
402 data.raycast_callback = mesh_faces_spherecast;
403 return data;
404}
405
407 const Span<float3> positions,
408 const Span<int> corner_verts,
409 const Span<int3> corner_tris)
410{
412 data.tree = tree;
413 data.vert_positions = positions;
414 data.corner_verts = corner_verts;
415 data.corner_tris = corner_tris;
416 data.nearest_callback = mesh_corner_tris_nearest_point;
417 data.raycast_callback = mesh_corner_tris_spherecast;
418 return data;
419}
420
421static BVHTreeFromMesh create_tris_tree_data(std::unique_ptr<BVHTree, BVHTreeDeleter> tree,
422 const Span<float3> positions,
423 const Span<int> corner_verts,
424 const Span<int3> corner_tris)
425{
426 BVHTreeFromMesh data = create_tris_tree_data(tree.get(), positions, corner_verts, corner_tris);
427 data.owned_tree = std::move(tree);
428 return data;
429}
430
431static std::unique_ptr<BVHTree, BVHTreeDeleter> bvhtree_new_common(int elems_num)
432{
433 if (elems_num == 0) {
434 return nullptr;
435 }
436 return std::unique_ptr<BVHTree, BVHTreeDeleter>(BLI_bvhtree_new(elems_num, 0.0f, 2, 6));
437}
438
439static std::unique_ptr<BVHTree, BVHTreeDeleter> create_tree_from_verts(
440 const Span<float3> positions, const IndexMask &verts_mask)
441{
442 std::unique_ptr<BVHTree, BVHTreeDeleter> tree = bvhtree_new_common(verts_mask.size());
443 if (!tree) {
444 return nullptr;
445 }
446 verts_mask.foreach_index(
447 [&](const int i) { BLI_bvhtree_insert(tree.get(), i, positions[i], 1); });
448 BLI_bvhtree_balance(tree.get());
449 return tree;
450}
451
453 const IndexMask &verts_mask)
454{
455 return create_verts_tree_data(create_tree_from_verts(vert_positions, verts_mask),
456 vert_positions);
457}
458
459static std::unique_ptr<BVHTree, BVHTreeDeleter> create_tree_from_edges(
460 const Span<float3> positions, const Span<int2> edges, const IndexMask &edges_mask)
461{
462 std::unique_ptr<BVHTree, BVHTreeDeleter> tree = bvhtree_new_common(edges_mask.size());
463 if (!tree) {
464 return nullptr;
465 }
466 edges_mask.foreach_index([&](const int edge_i) {
467 const int2 &edge = edges[edge_i];
468 float co[2][3];
469 copy_v3_v3(co[0], positions[edge[0]]);
470 copy_v3_v3(co[1], positions[edge[1]]);
471 BLI_bvhtree_insert(tree.get(), edge_i, co[0], 2);
472 });
473 BLI_bvhtree_balance(tree.get());
474 return tree;
475}
476
478 const Span<int2> edges,
479 const IndexMask &edges_mask)
480{
482 create_tree_from_edges(vert_positions, edges, edges_mask), vert_positions, edges);
483}
484
485static std::unique_ptr<BVHTree, BVHTreeDeleter> create_tree_from_legacy_faces(
486 const Span<float3> positions, const Span<MFace> faces)
487{
488 std::unique_ptr<BVHTree, BVHTreeDeleter> tree = bvhtree_new_common(faces.size());
489 if (!tree) {
490 return nullptr;
491 }
492 for (const int i : faces.index_range()) {
493 float co[4][3];
494 copy_v3_v3(co[0], positions[faces[i].v1]);
495 copy_v3_v3(co[1], positions[faces[i].v2]);
496 copy_v3_v3(co[2], positions[faces[i].v3]);
497 if (faces[i].v4) {
498 copy_v3_v3(co[3], positions[faces[i].v4]);
499 }
500 BLI_bvhtree_insert(tree.get(), i, co[0], faces[i].v4 ? 4 : 3);
501 }
502 BLI_bvhtree_balance(tree.get());
503 return tree;
504}
505
506static std::unique_ptr<BVHTree, BVHTreeDeleter> create_tree_from_tris(const Span<float3> positions,
507 const Span<int> corner_verts,
508 const Span<int3> corner_tris)
509{
510 std::unique_ptr<BVHTree, BVHTreeDeleter> tree = bvhtree_new_common(corner_tris.size());
511 if (!tree) {
512 return {};
513 }
514 for (const int tri : corner_tris.index_range()) {
515 float co[3][3];
516 copy_v3_v3(co[0], positions[corner_verts[corner_tris[tri][0]]]);
517 copy_v3_v3(co[1], positions[corner_verts[corner_tris[tri][1]]]);
518 copy_v3_v3(co[2], positions[corner_verts[corner_tris[tri][2]]]);
519 BLI_bvhtree_insert(tree.get(), tri, co[0], 3);
520 }
521 BLI_bvhtree_balance(tree.get());
522 return tree;
523}
524
525static std::unique_ptr<BVHTree, BVHTreeDeleter> create_tree_from_tris(
526 const Span<float3> positions,
527 const OffsetIndices<int> faces,
528 const Span<int> corner_verts,
529 const Span<int3> corner_tris,
530 const IndexMask &faces_mask,
531 const bool map_global_indices)
532{
533 if (faces_mask.size() == faces.size()) {
534 /* Avoid accessing face offsets if the selection is full. */
535 return create_tree_from_tris(positions, corner_verts, corner_tris);
536 }
537
538 int tris_num = 0;
539 faces_mask.foreach_index_optimized<int>(
540 [&](const int i) { tris_num += mesh::face_triangles_num(faces[i].size()); });
541
542 std::unique_ptr<BVHTree, BVHTreeDeleter> tree = bvhtree_new_common(tris_num);
543 if (!tree) {
544 return {};
545 }
546 int i = 0;
547 faces_mask.foreach_index([&](const int face) {
548 for (const int tri : mesh::face_triangles_range(faces, face)) {
549 float co[3][3];
550 copy_v3_v3(co[0], positions[corner_verts[corner_tris[tri][0]]]);
551 copy_v3_v3(co[1], positions[corner_verts[corner_tris[tri][1]]]);
552 copy_v3_v3(co[2], positions[corner_verts[corner_tris[tri][2]]]);
553 const int index = map_global_indices ? tri : i;
554 BLI_bvhtree_insert(tree.get(), index, co[0], 3);
555 i++;
556 }
557 });
558 BLI_bvhtree_balance(tree.get());
559 return tree;
560}
561
563 const OffsetIndices<int> faces,
564 const Span<int> corner_verts,
565 const Span<int3> corner_tris,
566 const IndexMask &faces_mask,
567 const bool map_global_indices)
568{
571 vert_positions, faces, corner_verts, corner_tris, faces_mask, map_global_indices),
572 vert_positions,
573 corner_verts,
574 corner_tris);
575}
576
578{
579 int count = mesh.verts_num;
580 BitVector<> verts_mask(count, true);
581
582 const AttributeAccessor attributes = mesh.attributes();
583 const Span<int2> edges = mesh.edges();
584 const VArray<bool> hide_edge = *attributes.lookup_or_default(
585 ".hide_edge", AttrDomain::Edge, false);
586 const VArray<bool> hide_vert = *attributes.lookup_or_default(
587 ".hide_vert", AttrDomain::Point, false);
588
589 for (const int i : edges.index_range()) {
590 if (hide_edge[i]) {
591 continue;
592 }
593 for (const int vert : {edges[i][0], edges[i][1]}) {
594 if (verts_mask[vert]) {
595 verts_mask[vert].reset();
596 count--;
597 }
598 }
599 }
600
601 if (count) {
602 for (const int vert : verts_mask.index_range()) {
603 if (verts_mask[vert] && hide_vert[vert]) {
604 verts_mask[vert].reset();
605 }
606 }
607 }
608
609 return verts_mask;
610}
611
613{
614 int count = mesh.edges_num;
615 BitVector<> edge_mask(count, true);
616
617 const AttributeAccessor attributes = mesh.attributes();
618 const OffsetIndices faces = mesh.faces();
619 const Span<int> corner_edges = mesh.corner_edges();
620 const VArray<bool> hide_poly = *attributes.lookup_or_default(
621 ".hide_poly", AttrDomain::Face, false);
622 const VArray<bool> hide_edge = *attributes.lookup_or_default(
623 ".hide_edge", AttrDomain::Edge, false);
624
625 for (const int i : faces.index_range()) {
626 if (hide_poly[i]) {
627 continue;
628 }
629 for (const int edge : corner_edges.slice(faces[i])) {
630 if (edge_mask[edge]) {
631 edge_mask[edge].reset();
632 count--;
633 }
634 }
635 }
636
637 if (count) {
638 for (const int edge : edge_mask.index_range()) {
639 if (edge_mask[edge] && hide_edge[edge]) {
640 edge_mask[edge].reset();
641 }
642 }
643 }
644
645 return edge_mask;
646}
647
648} // namespace bke
649
650bke::BVHTreeFromMesh Mesh::bvh_loose_verts() const
651{
652 using namespace blender::bke;
653 const Span<float3> positions = this->vert_positions();
654 this->runtime->bvh_cache_loose_verts.ensure([&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
655 data = create_tree_from_verts(positions, this->loose_verts());
656 });
657 return create_verts_tree_data(this->runtime->bvh_cache_loose_verts.data().get(), positions);
658}
659
660bke::BVHTreeFromMesh Mesh::bvh_loose_no_hidden_verts() const
661{
662 using namespace blender::bke;
663 const Span<float3> positions = this->vert_positions();
665 [&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
666 const BitVector<> mask = loose_verts_no_hidden_mask_get(*this);
667 IndexMaskMemory memory;
668 data = create_tree_from_verts(positions, IndexMask::from_bits(mask, memory));
669 });
671 positions);
672}
673
674const bke::bvh::Tree &Mesh::bvh_verts() const
675{
676 using namespace blender::bke;
677 this->runtime->bvh_embree_verts_cache.ensure([&](bvh::Tree &data) {
678 const Span<float3> positions = this->vert_positions();
679 data = bvh::Tree::from_points(positions, positions.index_range());
680 });
681 return this->runtime->bvh_embree_verts_cache.data();
682}
683
684bke::BVHTreeFromMesh Mesh::bvh_loose_edges() const
685{
686 using namespace blender::bke;
687 const Span<float3> positions = this->vert_positions();
688 const Span<int2> edges = this->edges();
689 this->runtime->bvh_cache_loose_edges.ensure([&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
690 data = create_tree_from_edges(positions, edges, this->loose_edges());
691 });
693 this->runtime->bvh_cache_loose_edges.data().get(), positions, edges);
694}
695
696bke::BVHTreeFromMesh Mesh::bvh_loose_no_hidden_edges() const
697{
698 using namespace blender::bke;
699 const Span<float3> positions = this->vert_positions();
700 const Span<int2> edges = this->edges();
702 [&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
703 const BitVector<> mask = loose_edges_no_hidden_mask_get(*this);
704 IndexMaskMemory memory;
705 data = create_tree_from_edges(positions, edges, IndexMask::from_bits(mask, memory));
706 });
708 this->runtime->bvh_cache_loose_edges_no_hidden.data().get(), positions, edges);
709}
710
711const bke::bvh::Tree &Mesh::bvh_edges() const
712{
713 using namespace blender::bke;
714 this->runtime->bvh_embree_edges_cache.ensure([&](bvh::Tree &data) {
715 const Span<int2> edges = this->edges();
716 data = bvh::Tree::from_edges(this->vert_positions(), edges, edges.index_range());
717 });
718 return this->runtime->bvh_embree_edges_cache.data();
719}
720
721bke::BVHTreeFromMesh Mesh::bvh_edges_legacy() const
722{
723 using namespace blender::bke;
724 const Span<float3> positions = this->vert_positions();
725 const Span<int2> edges = this->edges();
726 this->runtime->bvh_cache_edges.ensure([&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
727 data = create_tree_from_edges(positions, edges, edges.index_range());
728 });
729 return create_edges_tree_data(this->runtime->bvh_cache_edges.data().get(), positions, edges);
730}
731
732bke::BVHTreeFromMesh Mesh::bvh_legacy_faces() const
733{
734 using namespace blender::bke;
735 BLI_assert(!(this->totface_legacy == 0 && this->faces_num != 0));
736 Span legacy_faces{
737 static_cast<const MFace *>(CustomData_get_layer(&this->fdata_legacy, CD_MFACE)),
738 this->totface_legacy};
739 const Span<float3> positions = this->vert_positions();
740 this->runtime->bvh_cache_faces.ensure([&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
741 data = create_tree_from_legacy_faces(positions, legacy_faces);
742 });
744 this->runtime->bvh_cache_faces.data().get(), positions, legacy_faces.data());
745}
746
747bke::BVHTreeFromMesh Mesh::bvh_corner_tris_no_hidden() const
748{
749 using namespace blender::bke;
750 const Span<float3> positions = this->vert_positions();
751 const Span<int> corner_verts = this->corner_verts();
752 const Span<int3> corner_tris = this->corner_tris();
753 const AttributeAccessor attributes = this->attributes();
754 const VArray hide_poly = *attributes.lookup<bool>(".hide_poly", AttrDomain::Face);
755 if (!hide_poly) {
756 return this->bvh_corner_tris();
757 }
759 [&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
760 const OffsetIndices<int> faces = this->faces();
761 IndexMaskMemory memory;
762 const IndexMask visible_faces = IndexMask::from_bools_inverse(
763 faces.index_range(), VArraySpan(hide_poly), memory);
765 positions, faces, corner_verts, corner_tris, visible_faces, true);
766 });
768 positions,
769 corner_verts,
770 corner_tris);
771}
772
773bke::BVHTreeFromMesh Mesh::bvh_corner_tris() const
774{
775 using namespace blender::bke;
776 const Span<float3> positions = this->vert_positions();
777 const Span<int> corner_verts = this->corner_verts();
778 const Span<int3> corner_tris = this->corner_tris();
779 this->runtime->bvh_cache_corner_tris.ensure([&](std::unique_ptr<BVHTree, BVHTreeDeleter> &data) {
780 data = create_tree_from_tris(positions, corner_verts, corner_tris);
781 });
783 this->runtime->bvh_cache_corner_tris.data().get(), positions, corner_verts, corner_tris);
784}
785
786const bke::bvh::Tree &Mesh::bvh_tris() const
787{
788 using namespace blender::bke::bvh;
789 this->runtime->bvh_embree_tris_cache.ensure(
790 [&](bke::bvh::Tree &data) { data = bke::bvh::Tree::from_single_mesh(*this); });
791 return this->runtime->bvh_embree_tris_cache.data();
792}
793
795
796/* -------------------------------------------------------------------- */
799
800const bke::bvh::Tree &PointCloud::bvh_tree() const
801{
802 using namespace blender::bke;
803 this->runtime->bvh_cache.ensure([&](bvh::Tree &data) {
804 const Span<float3> positions = this->positions();
805 data = bvh::Tree::from_points(positions, positions.index_range());
806 });
807 return this->runtime->bvh_cache.data();
808}
809
811
812} // namespace blender
General operations for point clouds.
#define BLI_assert(a)
#define UNPACK3(a)
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
static IndexMask from_bits(BitSpan bits, LinearAllocator<> &memory)
static IndexMask from_bools_inverse(Span< bool > bools, LinearAllocator<> &memory)
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
IndexRange index_range() const
GAttributeReader lookup_or_default(StringRef name, AttrDomain domain, AttrType data_type, const void *default_value=nullptr) const
GAttributeReader lookup(const StringRef name) const
static Tree from_single_mesh(const Mesh &mesh)
Definition bvh.cc:352
static Tree from_edges(Span< float3 > positions, Span< int2 > edges, const IndexMask &mask)
Definition bvh.cc:415
static Tree from_points(Span< float3 > positions, const IndexMask &mask)
Definition bvh.cc:391
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define FLT_MAX
#define FLT_EPSILON
int face_triangles_num(const int face_size)
Definition BKE_mesh.hh:350
IndexRange face_triangles_range(OffsetIndices< int > faces, int face_i)
Definition BKE_mesh.hh:359
static std::unique_ptr< BVHTree, BVHTreeDeleter > create_tree_from_legacy_faces(const Span< float3 > positions, const Span< MFace > faces)
Definition bvhutils.cc:485
static void mesh_verts_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition bvhutils.cc:277
BVHTreeFromMesh bvhtree_from_mesh_corner_tris_ex(Span< float3 > vert_positions, OffsetIndices< int > faces, Span< int > corner_verts, Span< int3 > corner_tris, const IndexMask &faces_mask, bool map_global_indices=true)
Definition bvhutils.cc:562
static std::unique_ptr< BVHTree, BVHTreeDeleter > create_tree_from_verts(const Span< float3 > positions, const IndexMask &verts_mask)
Definition bvhutils.cc:439
static BitVector loose_verts_no_hidden_mask_get(const Mesh &mesh)
Definition bvhutils.cc:577
float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray, float radius, float m_dist, const float v0[3], const float v1[3], const float v2[3])
Definition bvhutils.cc:51
static BVHTreeFromMesh create_tris_tree_data(const BVHTree *tree, const Span< float3 > positions, const Span< int > corner_verts, const Span< int3 > corner_tris)
Definition bvhutils.cc:406
static std::unique_ptr< BVHTree, BVHTreeDeleter > bvhtree_new_common(int elems_num)
Definition bvhutils.cc:431
static void mesh_corner_tris_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition bvhutils.cc:184
static BVHTreeFromMesh create_edges_tree_data(const BVHTree *tree, const Span< float3 > positions, const Span< int2 > edges)
Definition bvhutils.cc:371
static BVHTreeFromMesh create_legacy_faces_tree_data(const BVHTree *tree, const Span< float3 > positions, const MFace *face)
Definition bvhutils.cc:393
static std::unique_ptr< BVHTree, BVHTreeDeleter > create_tree_from_tris(const Span< float3 > positions, const Span< int > corner_verts, const Span< int3 > corner_tris)
Definition bvhutils.cc:506
float bvhtree_ray_tri_intersection(const BVHTreeRay *ray, float m_dist, const float v0[3], const float v1[3], const float v2[3])
Definition bvhutils.cc:30
static BVHTreeFromMesh create_verts_tree_data(const BVHTree *tree, const Span< float3 > positions)
Definition bvhutils.cc:351
static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition bvhutils.cc:294
static std::unique_ptr< BVHTree, BVHTreeDeleter > create_tree_from_edges(const Span< float3 > positions, const Span< int2 > edges, const IndexMask &edges_mask)
Definition bvhutils.cc:459
BVHTreeFromMesh bvhtree_from_mesh_edges_ex(Span< float3 > vert_positions, Span< int2 > edges, const IndexMask &edges_mask)
Definition bvhutils.cc:477
static void mesh_corner_tris_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition bvhutils.cc:115
BVHTreeFromMesh bvhtree_from_mesh_verts_ex(Span< float3 > vert_positions, const IndexMask &verts_mask)
Definition bvhutils.cc:452
static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition bvhutils.cc:81
static void mesh_verts_spherecast_do(int index, const float v[3], const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition bvhutils.cc:248
static BitVector loose_edges_no_hidden_mask_get(const Mesh &mesh)
Definition bvhutils.cc:612
static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition bvhutils.cc:221
static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition bvhutils.cc:146
BMesh Iterators.
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
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])
MINLINE float dot_v3v3v3(const float p[3], const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
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])
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_lambda, float r_uv[2])
void BLI_bvhtree_balance(BVHTree *tree)
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.cc:403
ATTR_WARN_UNUSED_RESULT const BMVert * v
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
MINLINE bool equals_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
VecBase< int32_t, 2 > int2
VecBase< int32_t, 3 > int3
BMesh const char void * data
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
const void * CustomData_get_layer(const CustomData *data, eCustomDataType type)
MINLINE float normalize_v3(float n[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
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])
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
MINLINE float square_f(float a)
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)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
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])
void mask(PageMask &srt, TileMaps &tilemaps, const uint3 global_id, const uint local_tile_index)
struct IsectRayPrecalc * isect_precalc
bke::MeshRuntime * runtime
CustomData fdata_legacy
bke::PointCloudRuntime * runtime
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_loose_verts
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_loose_edges_no_hidden
SharedCache< bke::bvh::Tree > bvh_embree_tris_cache
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_corner_tris
SharedCache< bke::bvh::Tree > bvh_embree_edges_cache
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_edges
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_loose_verts_no_hidden
SharedCache< bke::bvh::Tree > bvh_embree_verts_cache
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_loose_edges
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_faces
SharedCache< std::unique_ptr< BVHTree, BVHTreeDeleter > > bvh_cache_corner_tris_no_hidden
SharedCache< bke::bvh::Tree > bvh_cache