Blender V5.3
BKE_bvh.hh
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#pragma once
10
11#include "BLI_array.hh"
12#include "BLI_function_ref.hh"
13#include "BLI_index_mask_fwd.hh"
15
16#include <limits>
17#include <optional>
18
19struct RTCDeviceTy;
20struct RTCSceneTy;
21
22namespace blender {
23
24struct Mesh;
25
26namespace bke::bvh {
27
28struct Ray {
30 /* The ray direction does not have to be normalized. */
32 /* Scale factor for the ray direction (the ray length if the direction is normalized). */
33 float dist_max = std::numeric_limits<float>::max();
34
35 Ray() = default;
37 Ray(const float3 &origin, const float3 &direction, const float radius)
39 {
40 }
41};
42
43struct RayHit {
44 /* Ng. Not normalized. */
49 int index;
50 float distance;
51 float3 position(const Ray &ray) const
52 {
53 return ray.origin + ray.direction * distance;
54 }
55};
56
67
73class Tree {
74 public:
75 /* Type erased non Embree implementation to avoid extra includes. */
76 struct FallbackTree {
77 virtual ~FallbackTree() = default;
78 };
79
81 enum class ElemType : int8_t {
84 Edges,
85 };
86
98
100 int element(const uint32_t prim_id) const
101 {
102 return index_map.is_empty() ? int(prim_id) : index_map[prim_id];
103 }
104 };
105
106 private:
113 ElemType elem_type_ = ElemType::Tris;
115 [[maybe_unused]] RTCDeviceTy *rtc_device_ = nullptr;
116 [[maybe_unused]] RTCSceneTy *rtc_scene_ = nullptr;
121 Vector<Array<int, 0>, 1> index_map_by_geom_;
126 Vector<std::unique_ptr<UserGeometryData>, 1> user_data_by_geom_;
127
129 std::unique_ptr<FallbackTree> fallback_tree_;
130
131 public:
133 Tree(const Tree &) = delete;
134 Tree &operator=(const Tree &) = delete;
135 Tree(Tree &&);
136 Tree &operator=(Tree &&);
137 ~Tree();
138
145 static Tree from_tris(const Mesh &mesh, const IndexMask &mask, bool map_global_indices);
147 static Tree from_single_mesh(const Mesh &mesh);
153 static Tree from_points(Span<float3> positions, const IndexMask &mask);
159 static Tree from_edges(Span<float3> positions, Span<int2> edges, const IndexMask &mask);
160
162 std::optional<RayHit> ray_intersect(const Ray &ray) const;
163
165 void ray_intersect_all(const Ray &ray, FunctionRef<void(const RayHit &)> fn) const;
166
171 std::optional<ClosestPointResult> closest_point(
172 const float3 &point, float radius = std::numeric_limits<float>::max()) const;
173
175 void range_query(const float3 &point, const float radius, FunctionRef<bool(int)> fn) const;
176};
177
178} // namespace bke::bvh
179} // namespace blender
constexpr bool is_empty() const
Definition BLI_span.hh:264
std::optional< RayHit > ray_intersect(const Ray &ray) const
Definition bvh.cc:439
Tree(const Tree &)=delete
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
BMesh Iterators.
unsigned int uint32_t
Definition BKE_text.h:81
VecBase< float, 3 > float3
signed char int8_t
Definition BKE_text.h:76
float3 position(const Ray &ray) const
Definition BKE_bvh.hh:51
Ray(const float3 &origin, const float3 &direction, const float radius)
Definition BKE_bvh.hh:37
Ray(const float3 &origin, const float3 &direction)
Definition BKE_bvh.hh:36
int element(const uint32_t prim_id) const
Definition BKE_bvh.hh:100