Blender V5.3
bvh.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <cmath>
10#include <limits>
11
12#include "BLI_array_utils.hh"
13#include "BLI_index_mask.hh"
14#include "BLI_kdopbvh.hh"
15#include "BLI_math_geom_c.hh"
16#include "BLI_math_vector.hh"
17
18#include "DNA_mesh_types.h"
19
20#include "BKE_bvh.hh"
21#include "BKE_bvhutils.hh"
22#include "BKE_mesh.hh"
23#include "BKE_mesh_runtime.hh"
24#include "BKE_mesh_sample.hh"
25
26#ifdef WITH_EMBREE
27
28# include <embree4/rtcore.h>
29
30#endif /* WITH_EMBREE */
31
36
37namespace blender::bke::bvh {
38
39Tree::Tree() = default;
40
42{
43 elem_type_ = other.elem_type_;
44#ifdef WITH_EMBREE
45 rtc_device_ = std::exchange(other.rtc_device_, nullptr);
46 rtc_scene_ = std::exchange(other.rtc_scene_, nullptr);
47 index_map_by_geom_ = std::move(other.index_map_by_geom_);
48 user_data_by_geom_ = std::move(other.user_data_by_geom_);
49#else /* WITH_EMBREE */
50 fallback_tree_ = std::move(other.fallback_tree_);
51#endif
52}
53
55{
56 if (this != &other) {
57 this->~Tree();
58 new (this) Tree(std::move(other));
59 }
60 return *this;
61}
62
64{
65#ifdef WITH_EMBREE
66 rtcReleaseScene(this->rtc_scene_);
67 this->rtc_scene_ = nullptr;
68 rtcReleaseDevice(this->rtc_device_);
69 this->rtc_device_ = nullptr;
70 index_map_by_geom_.clear_and_shrink();
71 user_data_by_geom_.clear_and_shrink();
72#else /* WITH_EMBREE */
73 this->fallback_tree_.reset();
74#endif
75}
76
77#ifdef WITH_EMBREE
78
79static void rtc_error_func(void * /*userPtr*/, RTCError /*error*/, const char * /*str*/) {}
80
81static bool rtc_memory_monitor_func(void * /*userPtr*/, const ssize_t /*bytes*/, const bool)
82{
83 return true;
84}
85
86static bool rtc_progress_func(void * /*user_ptr*/, const double /*n*/)
87{
88 return true;
89}
90
96static float3 bary_coord_embree_to_blender(const float u, const float v)
97{
98 return float3(1.0f - u - v, u, v);
99}
100
101#endif /* WITH_EMBREE */
102
103#ifdef WITH_EMBREE
104
105struct BvhBuildContext {
106 RTCDevice device;
107 RTCScene scene;
108 RTCBuildQuality build_quality;
109};
110
112static BvhBuildContext build_context_create()
113{
114 RTCDevice device = rtcNewDevice("verbose=0");
115 rtcSetDeviceErrorFunction(device, rtc_error_func, nullptr);
116 rtcSetDeviceMemoryMonitorFunction(device, rtc_memory_monitor_func, nullptr);
117
118 RTCScene scene = rtcNewScene(device);
119 const RTCSceneFlags scene_flags = RTCSceneFlags(RTC_SCENE_FLAG_ROBUST |
120 RTC_SCENE_FLAG_FILTER_FUNCTION_IN_ARGUMENTS);
121 rtcSetSceneFlags(scene, scene_flags);
122 const RTCBuildQuality build_quality = RTC_BUILD_QUALITY_MEDIUM;
123 rtcSetSceneBuildQuality(scene, build_quality);
124
125 return BvhBuildContext{device, scene, build_quality};
126}
127
128static void build_context_commit(const BvhBuildContext &ctx)
129{
130 rtcSetSceneProgressMonitorFunction(ctx.scene, rtc_progress_func, nullptr);
131 rtcCommitScene(ctx.scene);
132}
133
134static bool all_faces_are_triangles(const Mesh &mesh)
135{
136 return mesh.corners_num == mesh.faces_num * 3;
137}
138
139static void add_positions(const Span<float3> positions, RTCGeometry geom_id)
140{
141 /* Unfortunately #rtcSetSharedGeometryBuffer cannot be used here because Embree must load past
142 * the end of the buffer for SIMD loads. */
143 float3 *positions_ptr = static_cast<float3 *>(rtcSetNewGeometryBuffer(
144 geom_id, RTC_BUFFER_TYPE_VERTEX, 0, RTC_FORMAT_FLOAT3, sizeof(float3), positions.size()));
145 std::copy_n(positions.data(), positions.size(), positions_ptr);
146}
147
148static void add_mesh_faces(const BvhBuildContext &ctx, const int id, const Mesh &mesh)
149{
150 RTCGeometry geom_id = rtcNewGeometry(ctx.device, RTC_GEOMETRY_TYPE_TRIANGLE);
151 rtcSetGeometryBuildQuality(geom_id, ctx.build_quality);
152
153 const Span<float3> positions = mesh.vert_positions();
154 const Span<int> corner_verts = mesh.corner_verts();
155 if (all_faces_are_triangles(mesh)) {
156 rtcSetSharedGeometryBuffer(geom_id,
157 RTC_BUFFER_TYPE_INDEX,
158 0,
159 RTC_FORMAT_UINT3,
160 corner_verts.data(),
161 0,
162 sizeof(int3),
163 corner_verts.cast<int3>().size());
164 }
165 else {
166 const Span<int3> corner_tris = mesh.corner_tris();
167 uint3 *rtc_indices = static_cast<uint3 *>(rtcSetNewGeometryBuffer(
168 geom_id, RTC_BUFFER_TYPE_INDEX, 0, RTC_FORMAT_UINT3, sizeof(int3), corner_tris.size()));
170 corner_verts, corner_tris, MutableSpan(rtc_indices, corner_tris.size()).cast<int3>());
171 }
172 add_positions(positions, geom_id);
173
174 rtcCommitGeometry(geom_id);
175 rtcAttachGeometryByID(ctx.scene, geom_id, id);
176 rtcReleaseGeometry(geom_id);
177}
178
179static void add_mesh_faces(const BvhBuildContext &ctx,
180 Vector<Array<int, 0>, 1> &index_map_by_geom,
181 const int id,
182 const Mesh &mesh,
183 const IndexMask &face_mask,
184 const bool map_global_indices)
185{
186 RTCGeometry geom_id = rtcNewGeometry(ctx.device, RTC_GEOMETRY_TYPE_TRIANGLE);
187 rtcSetGeometryBuildQuality(geom_id, ctx.build_quality);
188
189 const Span<float3> positions = mesh.vert_positions();
190 const OffsetIndices faces = mesh.faces();
191 const Span<int> corner_verts = mesh.corner_verts();
192 const Span<int3> corner_tris = mesh.corner_tris();
193 /* Use #int instead of the default #int64_t for internal indices. */
194 VectorSet<int,
195 128,
197 DefaultHash<int>,
198 DefaultEquality<int>,
199 SimpleVectorSetSlot<int, int>,
200 GuardedAllocator>
201 used_verts;
202 used_verts.reserve(faces.size());
203 face_mask.foreach_index(
204 [&](const int face) { used_verts.add_multiple(corner_verts.slice(faces[face])); });
205
206 Array<int, 128> masked_face_offset_data(face_mask.size() + 1);
207 const OffsetIndices<int> mask_faces = offset_indices::gather_selected_offsets(
208 faces, face_mask, masked_face_offset_data);
209
210 const int tris_num = poly_to_tri_count(face_mask.size(), mask_faces.total_size());
211
212 Array<int, 0> global_index_map;
213 if (map_global_indices) {
214 global_index_map.reinitialize(tris_num);
215 face_mask.foreach_index_optimized<int>(
216 [&](const int face, const int pos) {
217 const IndexRange src_tris = mesh::face_triangles_range(faces, face);
218 const IndexRange dst_tris = mesh::face_triangles_range(mask_faces, pos);
219 for (const int i : src_tris.index_range()) {
220 global_index_map[dst_tris[i]] = src_tris[i];
221 }
222 },
224 }
225 index_map_by_geom.append(std::move(global_index_map));
226
227 uint3 *rtc_indices = static_cast<uint3 *>(rtcSetNewGeometryBuffer(
228 geom_id, RTC_BUFFER_TYPE_INDEX, 0, RTC_FORMAT_UINT3, sizeof(int3), tris_num));
229 face_mask.foreach_index_optimized<int>(
230 [&](const int face, const int pos) {
231 const IndexRange src_tris = mesh::face_triangles_range(faces, face);
232 const IndexRange dst_tris = mesh::face_triangles_range(mask_faces, pos);
233 for (const int i : src_tris.index_range()) {
234 const int3 &tri = corner_tris[src_tris[i]];
235 rtc_indices[dst_tris[i]] = uint3(used_verts.index_of(corner_verts[tri[0]]),
236 used_verts.index_of(corner_verts[tri[1]]),
237 used_verts.index_of(corner_verts[tri[2]]));
238 }
239 },
241
242 /* If #rtcSetSharedGeometryBuffer could be used, remapping to avoid copying unnecessary
243 * vertex positions could be unnecessary. Sharing the buffer currently doesn't work because
244 * Embree must load past the end of the buffer for SIMD loads. */
245 float3 *positions_ptr = static_cast<float3 *>(rtcSetNewGeometryBuffer(
246 geom_id, RTC_BUFFER_TYPE_VERTEX, 0, RTC_FORMAT_FLOAT3, sizeof(float3), used_verts.size()));
247 array_utils::gather<float3>(positions, used_verts.as_span(), {positions_ptr, used_verts.size()});
248
249 rtcCommitGeometry(geom_id);
250 rtcAttachGeometryByID(ctx.scene, geom_id, id);
251 rtcReleaseGeometry(geom_id);
252}
253
254static void points_bounds_func(const RTCBoundsFunctionArguments *args)
255{
256 const auto &data = *static_cast<const Tree::UserGeometryData *>(args->geometryUserPtr);
257 const float3 &position = data.positions[data.element(args->primID)];
258 args->bounds_o->lower_x = position.x;
259 args->bounds_o->lower_y = position.y;
260 args->bounds_o->lower_z = position.z;
261 args->bounds_o->upper_x = position.x;
262 args->bounds_o->upper_y = position.y;
263 args->bounds_o->upper_z = position.z;
264}
265
266static void edges_bounds_func(const RTCBoundsFunctionArguments *args)
267{
268 const auto &data = *static_cast<const Tree::UserGeometryData *>(args->geometryUserPtr);
269 const int2 edge = data.edges[data.element(args->primID)];
270 const float3 min = math::min(data.positions[edge[0]], data.positions[edge[1]]);
271 const float3 max = math::max(data.positions[edge[0]], data.positions[edge[1]]);
272 args->bounds_o->lower_x = min.x;
273 args->bounds_o->lower_y = min.y;
274 args->bounds_o->lower_z = min.z;
275 args->bounds_o->upper_x = max.x;
276 args->bounds_o->upper_y = max.y;
277 args->bounds_o->upper_z = max.z;
278}
279
287static void add_user_geometry(const BvhBuildContext &ctx,
288 const int id,
289 const int elements_num,
290 const Tree::UserGeometryData &user_data,
291 const RTCBoundsFunction bounds_func)
292{
293 RTCGeometry geom_id = rtcNewGeometry(ctx.device, RTC_GEOMETRY_TYPE_USER);
294 rtcSetGeometryBuildQuality(geom_id, ctx.build_quality);
295 rtcSetGeometryUserPrimitiveCount(geom_id, uint32_t(elements_num));
296 rtcSetGeometryUserData(geom_id, const_cast<Tree::UserGeometryData *>(&user_data));
297 rtcSetGeometryBoundsFunction(geom_id, bounds_func, nullptr);
298
299 rtcCommitGeometry(geom_id);
300 rtcAttachGeometryByID(ctx.scene, geom_id, id);
301 rtcReleaseGeometry(geom_id);
302}
303
304#else /* WITH_EMBREE */
305
312
318{
319 const MeshFallbackTree &mesh_tree = static_cast<const MeshFallbackTree &>(fallback_tree);
320 return const_cast<BVHTreeFromMesh *>(&mesh_tree.bvh_from_mesh);
321}
322
323#endif
324
325Tree Tree::from_tris(const Mesh &mesh, const IndexMask &face_mask, const bool map_global_indices)
326{
327 if (face_mask.size() == mesh.faces_num) {
328 return from_single_mesh(mesh);
329 }
330 Tree tree;
331#ifdef WITH_EMBREE
332 const BvhBuildContext ctx = build_context_create();
333 tree.rtc_device_ = ctx.device;
334 tree.rtc_scene_ = ctx.scene;
335
336 add_mesh_faces(ctx, tree.index_map_by_geom_, 0, mesh, face_mask, map_global_indices);
337
338 build_context_commit(ctx);
339#else /* WITH_EMBREE */
340 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
341 bvhtree_from_mesh_corner_tris_ex(mesh.vert_positions(),
342 mesh.faces(),
343 mesh.corner_verts(),
344 mesh.corner_tris(),
345 face_mask,
346 map_global_indices));
347#endif /* WITH_EMBREE */
348
349 return tree;
350}
351
353{
354 Tree tree;
355#ifdef WITH_EMBREE
356 const BvhBuildContext ctx = build_context_create();
357 tree.rtc_device_ = ctx.device;
358 tree.rtc_scene_ = ctx.scene;
359
360 add_mesh_faces(ctx, 0, mesh);
361 tree.index_map_by_geom_.append({});
362
363 build_context_commit(ctx);
364#else /* WITH_EMBREE */
365 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
366 bvhtree_from_mesh_corner_tris_ex(mesh.vert_positions(),
367 mesh.faces(),
368 mesh.corner_verts(),
369 mesh.corner_tris(),
370 IndexMask(mesh.faces_num),
371 true));
372#endif /* WITH_EMBREE */
373
374 return tree;
375}
376
377#ifdef WITH_EMBREE
378
379static Array<int, 0> global_index_map_create(const IndexMask &mask, const int elements_num)
380{
381 Array<int, 0> index_map;
382 if (mask.size() != elements_num) {
383 index_map.reinitialize(mask.size());
384 mask.to_indices<int>(index_map);
385 }
386 return index_map;
387}
388
389#endif /* WITH_EMBREE */
390
392{
393 Tree tree;
394 tree.elem_type_ = ElemType::Points;
395#ifdef WITH_EMBREE
396 const BvhBuildContext ctx = build_context_create();
397 tree.rtc_device_ = ctx.device;
398 tree.rtc_scene_ = ctx.scene;
399
400 tree.index_map_by_geom_.append(global_index_map_create(mask, positions.size()));
401 tree.user_data_by_geom_.append(std::make_unique<UserGeometryData>(
402 UserGeometryData{positions, {}, tree.index_map_by_geom_.last()}));
403
404 add_user_geometry(ctx, 0, mask.size(), *tree.user_data_by_geom_.last(), points_bounds_func);
405
406 build_context_commit(ctx);
407#else /* WITH_EMBREE */
408 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
409 bvhtree_from_mesh_verts_ex(positions, mask));
410#endif /* WITH_EMBREE */
411
412 return tree;
413}
414
415Tree Tree::from_edges(const Span<float3> positions, const Span<int2> edges, const IndexMask &mask)
416{
417 Tree tree;
418 tree.elem_type_ = ElemType::Edges;
419#ifdef WITH_EMBREE
420 const BvhBuildContext ctx = build_context_create();
421 tree.rtc_device_ = ctx.device;
422 tree.rtc_scene_ = ctx.scene;
423
424 tree.index_map_by_geom_.append(global_index_map_create(mask, edges.size()));
425 tree.user_data_by_geom_.append(std::make_unique<UserGeometryData>(
426 UserGeometryData{positions, edges, tree.index_map_by_geom_.last()}));
427
428 add_user_geometry(ctx, 0, mask.size(), *tree.user_data_by_geom_.last(), edges_bounds_func);
429
430 build_context_commit(ctx);
431#else /* WITH_EMBREE */
432 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
433 bvhtree_from_mesh_edges_ex(positions, edges, mask));
434#endif /* WITH_EMBREE */
435
436 return tree;
437}
438
439std::optional<RayHit> Tree::ray_intersect(const Ray &ray) const
440{
441 BLI_assert(elem_type_ == ElemType::Tris);
442#ifdef WITH_EMBREE
443 RTCRayHit rtc_hit;
444 rtc_hit.ray.org_x = ray.origin.x;
445 rtc_hit.ray.org_y = ray.origin.y;
446 rtc_hit.ray.org_z = ray.origin.z;
447 rtc_hit.ray.dir_x = ray.direction.x;
448 rtc_hit.ray.dir_y = ray.direction.y;
449 rtc_hit.ray.dir_z = ray.direction.z;
450 /* TODO: BLI_kdopbvh fallback does not support a minimum distance. */
451 rtc_hit.ray.tnear = 0.0f;
452 rtc_hit.ray.tfar = ray.dist_max;
453 rtc_hit.ray.time = 0.0f;
454 rtc_hit.ray.mask = 0xffffffff;
455 rtc_hit.hit.geomID = RTC_INVALID_GEOMETRY_ID;
456 rtc_hit.hit.instID[0] = RTC_INVALID_GEOMETRY_ID;
457 rtcIntersect1(rtc_scene_, &rtc_hit);
458 if (rtc_hit.hit.geomID == RTC_INVALID_GEOMETRY_ID ||
459 rtc_hit.hit.primID == RTC_INVALID_GEOMETRY_ID)
460 {
461 return std::nullopt;
462 }
463
464 RayHit hit;
465 hit.normal = float3(rtc_hit.hit.Ng_x, rtc_hit.hit.Ng_y, rtc_hit.hit.Ng_z);
466 hit.bary_coord = bary_coord_embree_to_blender(rtc_hit.hit.u, rtc_hit.hit.v);
467 hit.index = rtc_hit.hit.primID;
468 if (!index_map_by_geom_[rtc_hit.hit.geomID].is_empty()) {
469 hit.index = index_map_by_geom_[rtc_hit.hit.geomID][hit.index];
470 }
471 hit.distance = rtc_hit.ray.tfar;
472 return hit;
473#else /* WITH_EMBREE */
474 BVHTreeFromMesh *data = fallback_mesh_data(*this->fallback_tree_);
475 if (!data->tree) {
476 return std::nullopt;
477 }
478
479 BVHTreeRayHit bvh_hit;
480 bvh_hit.index = -1;
481 bvh_hit.dist = ray.dist_max;
483 data->tree, ray.origin, ray.direction, 0.0f, &bvh_hit, data->raycast_callback, data);
484 if (bvh_hit.index == -1) {
485 return std::nullopt;
486 }
487
488 RayHit hit;
489 hit.normal = float3(bvh_hit.no);
490 hit.index = bvh_hit.index;
491 hit.distance = bvh_hit.dist;
493 data->vert_positions,
494 data->corner_verts,
495 data->corner_tris[bvh_hit.index],
496 hit.position(ray));
497 return hit;
498#endif
499}
500
501void Tree::ray_intersect_all(const Ray &ray, FunctionRef<void(const RayHit &)> fn) const
502{
503 BLI_assert(elem_type_ == ElemType::Tris);
504#ifdef WITH_EMBREE
505 struct AllHitsContext {
506 RTCRayQueryContext rtc_context;
507 FunctionRef<void(const RayHit &)> *fn;
508 Span<Array<int, 0>> index_map_by_geom;
509 float3 origin;
510 float3 direction;
511 };
512
513 AllHitsContext ctx;
514 rtcInitRayQueryContext(&ctx.rtc_context);
515 ctx.fn = &fn;
516 ctx.index_map_by_geom = index_map_by_geom_;
517 ctx.origin = ray.origin;
518 ctx.direction = ray.direction;
519
520 RTCRayHit rtc_hit;
521 rtc_hit.ray.org_x = ray.origin.x;
522 rtc_hit.ray.org_y = ray.origin.y;
523 rtc_hit.ray.org_z = ray.origin.z;
524 rtc_hit.ray.dir_x = ray.direction.x;
525 rtc_hit.ray.dir_y = ray.direction.y;
526 rtc_hit.ray.dir_z = ray.direction.z;
527 rtc_hit.ray.tnear = 0.0f;
528 rtc_hit.ray.tfar = ray.dist_max;
529 rtc_hit.ray.time = 0.0f;
530 rtc_hit.ray.mask = 0xffffffff;
531 rtc_hit.ray.id = 0;
532 rtc_hit.ray.flags = 0;
533 rtc_hit.hit.geomID = RTC_INVALID_GEOMETRY_ID;
534 rtc_hit.hit.instID[0] = RTC_INVALID_GEOMETRY_ID;
535
536 RTCIntersectArguments args;
537 rtcInitIntersectArguments(&args);
538 args.flags = RTCRayQueryFlags(args.flags | RTC_RAY_QUERY_FLAG_INVOKE_ARGUMENT_FILTER);
539 args.context = &ctx.rtc_context;
540 args.filter = [](const RTCFilterFunctionNArguments *filter_args) {
541 AllHitsContext *ctx = reinterpret_cast<AllHitsContext *>(filter_args->context);
542 const RTCHit rtc_hit = rtcGetHitFromHitN(filter_args->hit, filter_args->N, 0);
543 const RTCRay rtc_ray = rtcGetRayFromRayN(filter_args->ray, filter_args->N, 0);
544
545 RayHit hit;
546 hit.normal = float3(rtc_hit.Ng_x, rtc_hit.Ng_y, rtc_hit.Ng_z);
547 hit.bary_coord = bary_coord_embree_to_blender(rtc_hit.u, rtc_hit.v);
548 hit.index = int(rtc_hit.primID);
549 if (!ctx->index_map_by_geom[rtc_hit.geomID].is_empty()) {
550 hit.index = ctx->index_map_by_geom[rtc_hit.geomID][hit.index];
551 }
552 hit.distance = rtc_ray.tfar;
553 (*ctx->fn)(hit);
554
555 /* Reject hit to continue traversal for all remaining intersections. */
556 filter_args->valid[0] = 0;
557 };
558
559 rtcIntersect1(this->rtc_scene_, &rtc_hit, &args);
560#else /* WITH_EMBREE */
561 BVHTreeFromMesh *data = fallback_mesh_data(*this->fallback_tree_);
562 if (!data->tree) {
563 return;
564 }
565
566 struct AllHitsContext {
567 Ray ray;
568 const BVHTreeFromMesh *data;
569 FunctionRef<void(const RayHit &)> fn;
570 };
571 AllHitsContext ctx{ray, data, fn};
572
574 data->tree,
575 ray.origin,
576 ray.direction,
577 0.0f,
578 ray.dist_max,
579 [](void *userdata, const int index, const BVHTreeRay *bvh_ray, BVHTreeRayHit *hit) {
580 AllHitsContext &ctx = *static_cast<AllHitsContext *>(userdata);
581 /* Run the intersection test into a local hit so the traversal distance stays at its
582 * maximum and every intersection is reported rather than only the closest one. */
583 BVHTreeRayHit local_hit;
584 local_hit.index = -1;
585 local_hit.dist = hit->dist;
586 ctx.data->raycast_callback(
587 const_cast<BVHTreeFromMesh *>(ctx.data), index, bvh_ray, &local_hit);
588 if (local_hit.index == -1) {
589 return;
590 }
592 result.normal = float3(local_hit.no);
593 result.index = local_hit.index;
594 result.distance = local_hit.dist;
596 ctx.data->vert_positions,
597 ctx.data->corner_verts,
598 ctx.data->corner_tris[local_hit.index],
599 result.position(ctx.ray));
600 ctx.fn(result);
601 },
602 &ctx);
603#endif
604}
605
606#ifdef WITH_EMBREE
607
608struct ClosestPointUserData {
609 RTCScene rtc_scene;
610 Tree::ElemType elem_type;
611 ClosestPointResult &result;
617 float distance_sq;
618 bool has_result = false;
619};
620
627static float radius_for_distance_sq(const float distance_sq)
628{
629 float radius = std::sqrt(distance_sq);
630 while (radius * radius < distance_sq) {
631 radius = std::nextafter(radius, std::numeric_limits<float>::infinity());
632 }
633 return radius;
634}
635
636static bool closest_point_fn(RTCPointQueryFunctionArguments *args)
637{
638 auto &user_data = *static_cast<ClosestPointUserData *>(args->userPtr);
639 const RTCScene scene = user_data.rtc_scene;
640 RTCGeometry geom = rtcGetGeometry(scene, args->geomID);
641
642 float3 nearest_position;
643 float3 bary_coord(0.0f);
644 switch (user_data.elem_type) {
645 case Tree::ElemType::Points: {
646 const auto &geom_data = *static_cast<const Tree::UserGeometryData *>(
647 rtcGetGeometryUserData(geom));
648 nearest_position = geom_data.positions[geom_data.element(args->primID)];
649 break;
650 }
651 case Tree::ElemType::Edges: {
652 const auto &geom_data = *static_cast<const Tree::UserGeometryData *>(
653 rtcGetGeometryUserData(geom));
654 const int2 edge = geom_data.edges[geom_data.element(args->primID)];
655 closest_to_line_segment_v3(nearest_position,
656 &args->query->x,
657 geom_data.positions[edge[0]],
658 geom_data.positions[edge[1]]);
659 break;
660 }
661 case Tree::ElemType::Tris: {
662 const float3 *positions = static_cast<const float3 *>(
663 rtcGetGeometryBufferData(geom, RTC_BUFFER_TYPE_VERTEX, 0));
664 const uint3 *indices = static_cast<const uint3 *>(
665 rtcGetGeometryBufferData(geom, RTC_BUFFER_TYPE_INDEX, 0));
666 const uint3 tri = indices[args->primID];
667
668 closest_on_tri_to_point_v3(nearest_position,
670 &args->query->x,
671 positions[tri[0]],
672 positions[tri[1]],
673 positions[tri[2]]);
674 break;
675 }
676 }
677
678 const float distance_sq = math::distance_squared(float3(&args->query->x), nearest_position);
679 if (distance_sq > user_data.distance_sq) {
680 return false;
681 }
682 if (distance_sq == user_data.distance_sq) {
683 if (!user_data.has_result) {
684 /* The initial search radius is exclusive. */
685 return false;
686 }
687 /* Multiple primitives can be exactly the same distance from the query point. The order can be
688 * platform dependent. Break the tie by primitive so that the result is the same on every
689 * platform. */
690 if (args->geomID > user_data.result.geomID) {
691 return false;
692 }
693 if (args->geomID == user_data.result.geomID && args->primID >= user_data.result.index) {
694 return false;
695 }
696 }
697 user_data.distance_sq = distance_sq;
698 args->query->radius = radius_for_distance_sq(distance_sq);
699 user_data.result.position = nearest_position;
700 user_data.result.bary_coord = bary_coord;
701 user_data.result.index = args->primID;
702 user_data.result.geomID = args->geomID;
703 user_data.has_result = true;
704 return true;
705}
706
707#endif /* WITH_EMBREE */
708
709std::optional<ClosestPointResult> Tree::closest_point(const float3 &point,
710 const float radius) const
711{
712#ifdef WITH_EMBREE
713 RTCPointQuery query{};
714 query.x = point.x;
715 query.y = point.y;
716 query.z = point.z;
717 query.time = 0.0f;
718 query.radius = radius;
719 RTCPointQueryContext context{};
720 rtcInitPointQueryContext(&context);
722 ClosestPointUserData user_data(this->rtc_scene_, elem_type_, result, radius * radius);
723 if (!rtcPointQuery(this->rtc_scene_, &query, &context, closest_point_fn, &user_data)) {
724 return std::nullopt;
725 }
726 if (!index_map_by_geom_[result.geomID].is_empty()) {
727 result.index = index_map_by_geom_[result.geomID][result.index];
728 }
729 return result;
730#else /* WITH_EMBREE */
731 BVHTreeFromMesh *data = fallback_mesh_data(*this->fallback_tree_);
732 if (!data->tree) {
733 return std::nullopt;
734 }
735
736 BVHTreeNearest nearest;
737 nearest.index = -1;
738 nearest.dist_sq = radius * radius;
739 BLI_bvhtree_find_nearest(data->tree, point, &nearest, data->nearest_callback, data);
740 if (nearest.index == -1) {
741 return std::nullopt;
742 }
743
745 result.position = float3(nearest.co);
746 if (elem_type_ == ElemType::Tris) {
748 data->vert_positions,
749 data->corner_verts,
750 data->corner_tris[nearest.index],
751 result.position);
752 }
753 else {
754 result.bary_coord = float3(0.0f);
755 }
756 result.index = nearest.index;
757 result.geomID = 0;
758 return result;
759#endif
760}
761
762void Tree::range_query(const float3 &point, const float radius, FunctionRef<bool(int)> fn) const
763{
764#ifdef WITH_EMBREE
765 RTCPointQuery query{};
766 query.x = point.x;
767 query.y = point.y;
768 query.z = point.z;
769 query.time = 0.0f;
770 query.radius = radius;
771 RTCPointQueryContext context{};
772 rtcInitPointQueryContext(&context);
773 struct UserData {
774 const FunctionRef<bool(int)> &fn;
775 Span<Array<int, 0>> index_map_by_geom;
776 };
777 UserData data{fn, index_map_by_geom_};
778 rtcPointQuery(
779 this->rtc_scene_,
780 &query,
781 &context,
782 [](RTCPointQueryFunctionArguments *args) -> bool {
783 UserData *data = static_cast<UserData *>(args->userPtr);
784 int index = args->primID;
785 if (!data->index_map_by_geom[args->geomID].is_empty()) {
786 index = data->index_map_by_geom[args->geomID][index];
787 }
788 return data->fn(index);
789 },
790 &data);
791#else /* WITH_EMBREE */
792 BVHTreeFromMesh *data = fallback_mesh_data(*this->fallback_tree_);
793 if (!data->tree) {
794 return;
795 }
796 /* The kdop range query cannot stop traversal early, so once #fn requests termination by
797 * returning false, skip calling it for the remaining indices to match Embree's behavior. */
798 bool stop = false;
800 *data->tree,
801 point,
802 radius,
803 [&](const int index, const float3 & /*co*/, const float /*dist_sq*/) {
804 if (stop) {
805 return;
806 }
807 stop = !fn(index);
808 });
809#endif
810}
811
812} // namespace blender::bke::bvh
btScalar max
Span< NewT > constexpr cast() const
Definition BLI_span.hh:422
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
constexpr MutableSpan()=default
constexpr int64_t size() const
Definition BLI_span.hh:256
std::optional< RayHit > ray_intersect(const Ray &ray) const
Definition bvh.cc:439
static Tree from_single_mesh(const Mesh &mesh)
Definition bvh.cc:352
std::optional< ClosestPointResult > closest_point(const float3 &point, float radius=std::numeric_limits< float >::max()) const
Definition bvh.cc:709
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
Tree & operator=(const Tree &)=delete
void ray_intersect_all(const Ray &ray, FunctionRef< void(const RayHit &)> fn) const
Definition bvh.cc:501
void range_query(const float3 &point, const float radius, FunctionRef< bool(int)> fn) const
Definition bvh.cc:762
static Tree from_tris(const Mesh &mesh, const IndexMask &mask, bool map_global_indices)
Definition bvh.cc:325
#define position
#define bary_coord
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
static BVHTreeFromMesh * fallback_mesh_data(const Tree::FallbackTree &fallback_tree)
Definition bvh.cc:317
float3 compute_bary_coord_in_triangle(Span< float3 > vert_positions, Span< int > corner_verts, const int3 &corner_tri, const float3 &position)
void vert_tris_from_corner_tris(Span< int > corner_verts, Span< int3 > corner_tris, MutableSpan< int3 > vert_tris)
IndexRange face_triangles_range(OffsetIndices< int > faces, int face_i)
Definition BKE_mesh.hh:359
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
BVHTreeFromMesh bvhtree_from_mesh_edges_ex(Span< float3 > vert_positions, Span< int2 > edges, const IndexMask &edges_mask)
Definition bvhutils.cc:477
BVHTreeFromMesh bvhtree_from_mesh_verts_ex(Span< float3 > vert_positions, const IndexMask &verts_mask)
Definition bvhutils.cc:452
constexpr ParallelGrainSize grain_size(int grain_size)
T min(const T &a, const T &b)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
T max(const T &a, const T &b)
OffsetIndices< int > gather_selected_offsets(OffsetIndices< int > src_offsets, const IndexMask &selection, int start_offset, MutableSpan< int > dst_offsets)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
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
VecBase< uint32_t, 3 > uint3
ATTR_WARN_UNUSED_RESULT const BMVert * v
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
unsigned int uint32_t
Definition BKE_text.h:81
VecBase< int32_t, 2 > int2
VecBase< int32_t, 3 > int3
BMesh const char void * data
void BLI_bvhtree_range_query_cpp(const BVHTree &tree, const float3 co, float radius, BVHTree_RangeQuery_CPP fn)
void BLI_bvhtree_ray_cast_all(const BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata)
MINLINE int poly_to_tri_count(int poly_count, int corner_count)
PythonProbingStrategy<> DefaultProbingStrategy
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])
VecBase< float, 3 > float3
#define min(a, b)
Definition sort.cc:38
MeshFallbackTree(BVHTreeFromMesh bvh_from_mesh)
Definition bvh.cc:309
~MeshFallbackTree() override=default
BVHTreeFromMesh bvh_from_mesh
Definition bvh.cc:307
float3 position(const Ray &ray) const
Definition BKE_bvh.hh:51
float x
Definition sky_math.h:136