Blender V5.3
BLI_kdopbvh.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2006 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#pragma once
6
10
11#include "BLI_function_ref.hh"
12#include "BLI_hash.hh"
14#include "BLI_sys_types.hh"
15
16namespace blender {
17
18struct BVHTree;
20
21struct BVHTree;
22#define USE_KDOPBVH_WATERTIGHT
23
25 union {
26 struct {
27 float min, max;
28 };
29 /* alternate access */
30 float range[2];
31 };
32};
33
35 int indexA;
36 int indexB;
37
38 uint64_t hash() const
39 {
40 return get_default_hash(this->indexA, this->indexB);
41 }
42
43 friend bool operator==(const BVHTreeOverlap &a, const BVHTreeOverlap &b) = default;
44};
45
51 int index;
56 float co[3];
61 float no[3];
63 float dist_sq;
64 int flags;
65};
66
67struct BVHTreeRay {
69 float origin[3];
71 float direction[3];
73 float radius;
74#ifdef USE_KDOPBVH_WATERTIGHT
76#endif
77};
78
81 int index;
83 float co[3];
85 float no[3];
87 float dist;
88};
89
90enum {
93 /* Use a specialized self-overlap traversal to only test and output every
94 * pair once, rather than twice in different order as usual. */
95 BVH_OVERLAP_SELF = (1 << 2),
96};
97enum {
98 /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
100};
101enum {
102 /* calculate IsectRayPrecalc data */
104};
105#define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT)
106#define BVH_RAYCAST_DIST_MAX (FLT_MAX / 2.0f)
107
111using BVHTree_NearestPointCallback = void (*)(void *userdata,
112 int index,
113 const float co[3],
114 BVHTreeNearest *nearest);
115
119using BVHTree_RayCastCallback = void (*)(void *userdata,
120 int index,
121 const BVHTreeRay *ray,
122 BVHTreeRayHit *hit);
123
127using BVHTree_OverlapCallback = bool (*)(void *userdata, int index_a, int index_b, int thread);
128
132using BVHTree_RangeQuery = void (*)(void *userdata, int index, const float co[3], float dist_sq);
133
137using BVHTree_NearestProjectedCallback = void (*)(void *userdata,
138 int index,
139 const DistProjectedAABBPrecalc *precalc,
140 const float (*clip_plane)[4],
141 int clip_plane_len,
142 BVHTreeNearest *nearest);
143
144void BLI_bvhtree_free(BVHTree *tree);
145
147 public:
148 void operator()(BVHTree *tree)
149 {
150 BLI_bvhtree_free(tree);
151 }
152};
153
157BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
158
162void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints);
163void BLI_bvhtree_balance(BVHTree *tree);
164
170 BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints);
177void BLI_bvhtree_update_tree(BVHTree *tree);
178
184int BLI_bvhtree_overlap_thread_num(const BVHTree *tree);
185
192BVHTreeOverlap *BLI_bvhtree_overlap_ex(const BVHTree *tree1,
193 const BVHTree *tree2,
194 uint *r_overlap_num,
196 void *userdata,
197 uint max_interactions,
198 int flag);
199BVHTreeOverlap *BLI_bvhtree_overlap(const BVHTree *tree1,
200 const BVHTree *tree2,
201 unsigned int *r_overlap_num,
203 void *userdata);
208BVHTreeOverlap *BLI_bvhtree_overlap_self(const BVHTree *tree,
209 unsigned int *r_overlap_num,
211 void *userdata);
212
213int *BLI_bvhtree_intersect_plane(const BVHTree *tree, float plane[4], uint *r_intersect_num);
214
219int BLI_bvhtree_get_len(const BVHTree *tree);
223int BLI_bvhtree_get_tree_type(const BVHTree *tree);
224float BLI_bvhtree_get_epsilon(const BVHTree *tree);
228void BLI_bvhtree_get_bounding_box(const BVHTree *tree, float r_bb_min[3], float r_bb_max[3]);
229
235int BLI_bvhtree_find_nearest_ex(const BVHTree *tree,
236 const float co[3],
237 BVHTreeNearest *nearest,
239 void *userdata,
240 int flag);
241int BLI_bvhtree_find_nearest(const BVHTree *tree,
242 const float co[3],
243 BVHTreeNearest *nearest,
245 void *userdata);
246
251int BLI_bvhtree_find_nearest_first(const BVHTree *tree,
252 const float co[3],
253 float dist_sq,
255 void *userdata);
256
257int BLI_bvhtree_ray_cast_ex(const BVHTree *tree,
258 const float co[3],
259 const float dir[3],
260 float radius,
261 BVHTreeRayHit *hit,
263 void *userdata,
264 int flag);
265int BLI_bvhtree_ray_cast(const BVHTree *tree,
266 const float co[3],
267 const float dir[3],
268 float radius,
269 BVHTreeRayHit *hit,
271 void *userdata);
272
282void BLI_bvhtree_ray_cast_all_ex(const BVHTree *tree,
283 const float co[3],
284 const float dir[3],
285 float radius,
286 float hit_dist,
288 void *userdata,
289 int flag);
290void BLI_bvhtree_ray_cast_all(const BVHTree *tree,
291 const float co[3],
292 const float dir[3],
293 float radius,
294 float hit_dist,
296 void *userdata);
297
298float BLI_bvhtree_bb_raycast(const float bv[6],
299 const float light_start[3],
300 const float light_end[3],
301 float pos[3]);
302
306int BLI_bvhtree_range_query(const BVHTree *tree,
307 const float co[3],
308 float radius,
309 BVHTree_RangeQuery callback,
310 void *userdata);
311
312int BLI_bvhtree_find_nearest_projected(const BVHTree *tree,
313 float projmat[4][4],
314 float winsize[2],
315 float mval[2],
316 float (*clip_planes)[4],
317 int clip_plane_len,
318 BVHTreeNearest *nearest,
320 void *userdata);
321
325extern const float bvhtree_kdop_axes[13][3];
326
328 FunctionRef<void(int index, const BVHTreeRay &ray, BVHTreeRayHit &hit)>;
329
330inline void BLI_bvhtree_ray_cast_all_cpp(const BVHTree &tree,
331 const float3 co,
332 const float3 dir,
333 float radius,
334 float hit_dist,
336{
338 &tree,
339 co,
340 dir,
341 radius,
342 hit_dist,
343 [](void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) {
345 fn(index, *ray, *hit);
346 },
347 &fn);
348}
349
350using BVHTree_RangeQuery_CPP = FunctionRef<void(int index, const float3 &co, float dist_sq)>;
351
352inline void BLI_bvhtree_range_query_cpp(const BVHTree &tree,
353 const float3 co,
354 float radius,
356{
358 &tree,
359 co,
360 radius,
361 [](void *userdata, const int index, const float co[3], const float dist_sq) {
362 BVHTree_RangeQuery_CPP fn = *static_cast<BVHTree_RangeQuery_CPP *>(userdata);
363 fn(index, co, dist_sq);
364 },
365 &fn);
366}
367
368} // namespace blender
void operator()(BVHTree *tree)
#define index(i)
BMesh Iterators.
void(*)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) BVHTree_RayCastCallback
BVHTreeOverlap * BLI_bvhtree_overlap_ex(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
void BLI_bvhtree_get_bounding_box(const BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
unsigned __int64 uint64_t
Definition BKE_text.h:91
const float bvhtree_kdop_axes[13][3]
@ BVH_NEAREST_OPTIMAL_ORDER
void(*)(void *userdata, int index, const float co[3], float dist_sq) BVHTree_RangeQuery
int * BLI_bvhtree_intersect_plane(const BVHTree *tree, float plane[4], uint *r_intersect_num)
unsigned int uint
Definition BKE_text.h:55
int BLI_bvhtree_get_tree_type(const BVHTree *tree)
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
void BLI_bvhtree_free(BVHTree *tree)
int BLI_bvhtree_ray_cast_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
void BLI_bvhtree_balance(BVHTree *tree)
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)
bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
int BLI_bvhtree_find_nearest_ex(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
void BLI_bvhtree_update_tree(BVHTree *tree)
int BLI_bvhtree_range_query(const BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
int BLI_bvhtree_get_len(const BVHTree *tree)
FunctionRef< void(int index, const BVHTreeRay &ray, BVHTreeRayHit &hit)> BVHTree_RayCastCallback_CPP
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
BVHTreeOverlap * BLI_bvhtree_overlap_self(const BVHTree *tree, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
void BLI_bvhtree_range_query_cpp(const BVHTree &tree, const float3 co, float radius, BVHTree_RangeQuery_CPP fn)
@ BVH_OVERLAP_USE_THREADING
@ BVH_OVERLAP_RETURN_PAIRS
@ BVH_OVERLAP_SELF
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)
@ BVH_RAYCAST_WATERTIGHT
void BLI_bvhtree_ray_cast_all_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata, int flag)
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
bool(*)(void *userdata, int index_a, int index_b, int thread) BVHTree_OverlapCallback
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
FunctionRef< void(int index, const float3 &co, float dist_sq)> BVHTree_RangeQuery_CPP
void BLI_bvhtree_ray_cast_all_cpp(const BVHTree &tree, const float3 co, const float3 dir, float radius, float hit_dist, BVHTree_RayCastCallback_CPP fn)
VecBase< float, 3 > float3
void(*)(void *userdata, int index, const DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest) BVHTree_NearestProjectedCallback
constexpr uint64_t get_default_hash(const T &v, const Args &...args)
Definition BLI_hash.hh:252
int BLI_bvhtree_find_nearest_first(const BVHTree *tree, const float co[3], float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
int BLI_bvhtree_find_nearest_projected(const BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float(*clip_planes)[4], int clip_plane_len, BVHTreeNearest *nearest, BVHTree_NearestProjectedCallback callback, void *userdata)
void(*)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest) BVHTree_NearestPointCallback
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
uint64_t hash() const
friend bool operator==(const BVHTreeOverlap &a, const BVHTreeOverlap &b)=default
struct IsectRayPrecalc * isect_precalc