28# include <embree4/rtcore.h>
43 elem_type_ = other.elem_type_;
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_);
50 fallback_tree_ = std::move(other.fallback_tree_);
58 new (
this)
Tree(std::move(other));
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();
73 this->fallback_tree_.reset();
79static void rtc_error_func(
void * , RTCError ,
const char * ) {}
81static bool rtc_memory_monitor_func(
void * ,
const ssize_t ,
const bool)
86static bool rtc_progress_func(
void * ,
const double )
96static float3 bary_coord_embree_to_blender(
const float u,
const float v)
105struct BvhBuildContext {
108 RTCBuildQuality build_quality;
112static BvhBuildContext build_context_create()
114 RTCDevice device = rtcNewDevice(
"verbose=0");
115 rtcSetDeviceErrorFunction(device, rtc_error_func,
nullptr);
116 rtcSetDeviceMemoryMonitorFunction(device, rtc_memory_monitor_func,
nullptr);
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);
125 return BvhBuildContext{device, scene, build_quality};
128static void build_context_commit(
const BvhBuildContext &ctx)
130 rtcSetSceneProgressMonitorFunction(ctx.scene, rtc_progress_func,
nullptr);
131 rtcCommitScene(ctx.scene);
134static bool all_faces_are_triangles(
const Mesh &mesh)
136 return mesh.corners_num == mesh.faces_num * 3;
139static void add_positions(
const Span<float3> positions, RTCGeometry geom_id)
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);
148static void add_mesh_faces(
const BvhBuildContext &ctx,
const int id,
const Mesh &mesh)
150 RTCGeometry geom_id = rtcNewGeometry(ctx.device, RTC_GEOMETRY_TYPE_TRIANGLE);
151 rtcSetGeometryBuildQuality(geom_id, ctx.build_quality);
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,
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()));
172 add_positions(positions, geom_id);
174 rtcCommitGeometry(geom_id);
175 rtcAttachGeometryByID(ctx.scene, geom_id,
id);
176 rtcReleaseGeometry(geom_id);
179static void add_mesh_faces(
const BvhBuildContext &ctx,
180 Vector<Array<int, 0>, 1> &index_map_by_geom,
183 const IndexMask &face_mask,
184 const bool map_global_indices)
186 RTCGeometry geom_id = rtcNewGeometry(ctx.device, RTC_GEOMETRY_TYPE_TRIANGLE);
187 rtcSetGeometryBuildQuality(geom_id, ctx.build_quality);
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();
198 DefaultEquality<int>,
199 SimpleVectorSetSlot<int, int>,
202 used_verts.reserve(faces.size());
203 face_mask.foreach_index(
204 [&](
const int face) { used_verts.add_multiple(corner_verts.
slice(faces[face])); });
206 Array<int, 128> masked_face_offset_data(face_mask.size() + 1);
208 faces, face_mask, masked_face_offset_data);
210 const int tris_num =
poly_to_tri_count(face_mask.size(), mask_faces.total_size());
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) {
219 for (
const int i : src_tris.index_range()) {
220 global_index_map[dst_tris[i]] = src_tris[i];
225 index_map_by_geom.append(std::move(global_index_map));
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) {
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]]));
245 float3 *positions_ptr =
static_cast<float3 *
>(rtcSetNewGeometryBuffer(
246 geom_id, RTC_BUFFER_TYPE_VERTEX, 0, RTC_FORMAT_FLOAT3,
sizeof(
float3), used_verts.size()));
249 rtcCommitGeometry(geom_id);
250 rtcAttachGeometryByID(ctx.scene, geom_id,
id);
251 rtcReleaseGeometry(geom_id);
254static void points_bounds_func(
const RTCBoundsFunctionArguments *args)
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;
266static void edges_bounds_func(
const RTCBoundsFunctionArguments *args)
269 const int2 edge =
data.edges[
data.element(args->primID)];
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;
287static void add_user_geometry(
const BvhBuildContext &ctx,
289 const int elements_num,
291 const RTCBoundsFunction bounds_func)
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));
297 rtcSetGeometryBoundsFunction(geom_id, bounds_func,
nullptr);
299 rtcCommitGeometry(geom_id);
300 rtcAttachGeometryByID(ctx.scene, geom_id,
id);
301 rtcReleaseGeometry(geom_id);
327 if (face_mask.
size() ==
mesh.faces_num) {
332 const BvhBuildContext ctx = build_context_create();
333 tree.rtc_device_ = ctx.device;
334 tree.rtc_scene_ = ctx.scene;
336 add_mesh_faces(ctx, tree.index_map_by_geom_, 0,
mesh, face_mask, map_global_indices);
338 build_context_commit(ctx);
340 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
346 map_global_indices));
356 const BvhBuildContext ctx = build_context_create();
357 tree.rtc_device_ = ctx.device;
358 tree.rtc_scene_ = ctx.scene;
360 add_mesh_faces(ctx, 0,
mesh);
361 tree.index_map_by_geom_.append({});
363 build_context_commit(ctx);
365 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
382 if (
mask.size() != elements_num) {
384 mask.to_indices<
int>(index_map);
396 const BvhBuildContext ctx = build_context_create();
397 tree.rtc_device_ = ctx.device;
398 tree.rtc_scene_ = ctx.scene;
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>(
404 add_user_geometry(ctx, 0,
mask.size(), *tree.user_data_by_geom_.last(), points_bounds_func);
406 build_context_commit(ctx);
408 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
420 const BvhBuildContext ctx = build_context_create();
421 tree.rtc_device_ = ctx.device;
422 tree.rtc_scene_ = ctx.scene;
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>(
428 add_user_geometry(ctx, 0,
mask.size(), *tree.user_data_by_geom_.last(), edges_bounds_func);
430 build_context_commit(ctx);
432 tree.fallback_tree_ = std::make_unique<MeshFallbackTree>(
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;
451 rtc_hit.ray.tnear = 0.0f;
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)
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];
484 if (bvh_hit.
index == -1) {
493 data->vert_positions,
505 struct AllHitsContext {
506 RTCRayQueryContext rtc_context;
514 rtcInitRayQueryContext(&ctx.rtc_context);
516 ctx.index_map_by_geom = index_map_by_geom_;
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;
527 rtc_hit.ray.tnear = 0.0f;
529 rtc_hit.ray.time = 0.0f;
530 rtc_hit.ray.mask = 0xffffffff;
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;
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);
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];
556 filter_args->valid[0] = 0;
559 rtcIntersect1(this->rtc_scene_, &rtc_hit, &args);
566 struct AllHitsContext {
571 AllHitsContext ctx{ray,
data,
fn};
580 AllHitsContext &ctx = *static_cast<AllHitsContext *>(userdata);
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) {
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));
608struct ClosestPointUserData {
610 Tree::ElemType elem_type;
611 ClosestPointResult &
result;
618 bool has_result =
false;
627static float radius_for_distance_sq(
const float distance_sq)
629 float radius = std::sqrt(distance_sq);
630 while (radius * radius < distance_sq) {
631 radius = std::nextafter(radius, std::numeric_limits<float>::infinity());
636static bool closest_point_fn(RTCPointQueryFunctionArguments *args)
638 auto &user_data = *
static_cast<ClosestPointUserData *
>(args->userPtr);
639 const RTCScene scene = user_data.rtc_scene;
640 RTCGeometry geom = rtcGetGeometry(scene, args->geomID);
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)];
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)];
657 geom_data.positions[edge[0]],
658 geom_data.positions[edge[1]]);
661 case Tree::ElemType::Tris: {
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];
679 if (distance_sq > user_data.distance_sq) {
682 if (distance_sq == user_data.distance_sq) {
683 if (!user_data.has_result) {
690 if (args->geomID > user_data.result.geomID) {
693 if (args->geomID == user_data.result.geomID && args->primID >= user_data.result.index) {
697 user_data.distance_sq = distance_sq;
698 args->query->radius = radius_for_distance_sq(distance_sq);
699 user_data.result.position = nearest_position;
701 user_data.result.index = args->primID;
702 user_data.result.geomID = args->geomID;
703 user_data.has_result =
true;
710 const float radius)
const
713 RTCPointQuery query{};
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)) {
726 if (!index_map_by_geom_[
result.geomID].is_empty()) {
738 nearest.
dist_sq = radius * radius;
740 if (nearest.
index == -1) {
748 data->vert_positions,
765 RTCPointQuery query{};
770 query.radius = radius;
771 RTCPointQueryContext context{};
772 rtcInitPointQueryContext(&context);
782 [](RTCPointQueryFunctionArguments *args) ->
bool {
784 int index = args->primID;
785 if (!
data->index_map_by_geom[args->geomID].is_empty()) {
803 [&](
const int index,
const float3 & ,
const float ) {
Span< NewT > constexpr cast() const
constexpr Span slice(int64_t start, int64_t size) const
constexpr const T * data() const
constexpr int64_t size() const
void reinitialize(const int64_t new_size)
constexpr MutableSpan()=default
constexpr int64_t size() const
std::optional< RayHit > ray_intersect(const Ray &ray) const
static Tree from_single_mesh(const Mesh &mesh)
std::optional< ClosestPointResult > closest_point(const float3 &point, float radius=std::numeric_limits< float >::max()) const
static Tree from_edges(Span< float3 > positions, Span< int2 > edges, const IndexMask &mask)
static Tree from_points(Span< float3 > positions, const IndexMask &mask)
Tree & operator=(const Tree &)=delete
void ray_intersect_all(const Ray &ray, FunctionRef< void(const RayHit &)> fn) const
void range_query(const float3 &point, const float radius, FunctionRef< bool(int)> fn) const
static Tree from_tris(const Mesh &mesh, const IndexMask &mask, bool map_global_indices)
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)
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)
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)
BVHTreeFromMesh bvhtree_from_mesh_edges_ex(Span< float3 > vert_positions, Span< int2 > edges, const IndexMask &edges_mask)
BVHTreeFromMesh bvhtree_from_mesh_verts_ex(Span< float3 > vert_positions, const IndexMask &verts_mask)
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])
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)
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
MeshFallbackTree(BVHTreeFromMesh bvh_from_mesh)
~MeshFallbackTree() override=default
BVHTreeFromMesh bvh_from_mesh
float3 position(const Ray &ray) const