Blender  V3.3
BLI_kdopbvh.h
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2006 NaN Holding BV. All rights reserved. */
3 
4 #pragma once
5 
10 #include "BLI_sys_types.h"
11 
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15 
16 struct BVHTree;
18 
19 typedef struct BVHTree BVHTree;
20 #define USE_KDOPBVH_WATERTIGHT
21 
22 typedef struct BVHTreeAxisRange {
23  union {
24  struct {
25  float min, max;
26  };
27  /* alternate access */
28  float range[2];
29  };
31 
32 typedef struct BVHTreeOverlap {
33  int indexA;
34  int indexB;
36 
37 typedef struct BVHTreeNearest {
40  int index;
43  float co[3];
46  float no[3];
48  float dist_sq;
49  int flags;
51 
52 typedef struct BVHTreeRay {
54  float origin[3];
56  float direction[3];
58  float radius;
59 #ifdef USE_KDOPBVH_WATERTIGHT
61 #endif
63 
64 typedef struct BVHTreeRayHit {
66  int index;
68  float co[3];
70  float no[3];
72  float dist;
74 
75 enum {
76  /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
79 };
80 enum {
81  /* Use a priority queue to process nodes in the optimal order (for slow callbacks) */
83 };
84 enum {
85  /* calculate IsectRayPrecalc data */
87 };
88 #define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT)
89 #define BVH_RAYCAST_DIST_MAX (FLT_MAX / 2.0f)
90 
94 typedef void (*BVHTree_NearestPointCallback)(void *userdata,
95  int index,
96  const float co[3],
97  BVHTreeNearest *nearest);
98 
102 typedef void (*BVHTree_RayCastCallback)(void *userdata,
103  int index,
104  const BVHTreeRay *ray,
105  BVHTreeRayHit *hit);
106 
110 typedef bool (*BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread);
111 
115 typedef void (*BVHTree_RangeQuery)(void *userdata, int index, const float co[3], float dist_sq);
116 
120 typedef void (*BVHTree_NearestProjectedCallback)(void *userdata,
121  int index,
122  const struct DistProjectedAABBPrecalc *precalc,
123  const float (*clip_plane)[4],
124  int clip_plane_len,
125  BVHTreeNearest *nearest);
126 
127 /* callbacks to BLI_bvhtree_walk_dfs */
128 
132 typedef bool (*BVHTree_WalkParentCallback)(const BVHTreeAxisRange *bounds, void *userdata);
137  int index,
138  void *userdata);
143  char axis,
144  void *userdata);
145 
149 BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis);
151 
155 void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints);
157 
163  BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints);
168 
175 
183  const BVHTree *tree2,
184  uint *r_overlap_num,
186  void *userdata,
187  uint max_interactions,
188  int flag);
190  const BVHTree *tree2,
191  unsigned int *r_overlap_num,
193  void *userdata);
194 
195 int *BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_num);
196 
201 int BLI_bvhtree_get_len(const BVHTree *tree);
206 float BLI_bvhtree_get_epsilon(const BVHTree *tree);
210 void BLI_bvhtree_get_bounding_box(BVHTree *tree, float r_bb_min[3], float r_bb_max[3]);
211 
218  const float co[3],
219  BVHTreeNearest *nearest,
221  void *userdata,
222  int flag);
224  const float co[3],
225  BVHTreeNearest *nearest,
227  void *userdata);
228 
234  const float co[3],
235  float dist_sq,
237  void *userdata);
238 
240  const float co[3],
241  const float dir[3],
242  float radius,
243  BVHTreeRayHit *hit,
245  void *userdata,
246  int flag);
248  const float co[3],
249  const float dir[3],
250  float radius,
251  BVHTreeRayHit *hit,
253  void *userdata);
254 
265  const float co[3],
266  const float dir[3],
267  float radius,
268  float hit_dist,
270  void *userdata,
271  int flag);
273  const float co[3],
274  const float dir[3],
275  float radius,
276  float hit_dist,
278  void *userdata);
279 
280 float BLI_bvhtree_bb_raycast(const float bv[6],
281  const float light_start[3],
282  const float light_end[3],
283  float pos[3]);
284 
289  BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata);
290 
292  float projmat[4][4],
293  float winsize[2],
294  float mval[2],
295  float clip_planes[6][4],
296  int clip_plane_len,
297  BVHTreeNearest *nearest,
299  void *userdata);
300 
314  BVHTree_WalkParentCallback walk_parent_cb,
315  BVHTree_WalkLeafCallback walk_leaf_cb,
316  BVHTree_WalkOrderCallback walk_order_cb,
317  void *userdata);
318 
322 extern const float bvhtree_kdop_axes[13][3];
323 
324 #ifdef __cplusplus
325 }
326 #endif
327 
328 #ifdef __cplusplus
329 
330 # include "BLI_function_ref.hh"
331 # include "BLI_math_vector.hh"
332 
333 namespace blender {
334 
335 using BVHTree_RayCastCallback_CPP =
336  FunctionRef<void(int index, const BVHTreeRay &ray, BVHTreeRayHit &hit)>;
337 
338 inline void BLI_bvhtree_ray_cast_all_cpp(BVHTree &tree,
339  const float3 co,
340  const float3 dir,
341  float radius,
342  float hit_dist,
343  BVHTree_RayCastCallback_CPP fn)
344 {
346  &tree,
347  co,
348  dir,
349  radius,
350  hit_dist,
351  [](void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) {
352  BVHTree_RayCastCallback_CPP fn = *static_cast<BVHTree_RayCastCallback_CPP *>(userdata);
353  fn(index, *ray, *hit);
354  },
355  &fn);
356 }
357 
358 using BVHTree_RangeQuery_CPP = FunctionRef<void(int index, const float3 &co, float dist_sq)>;
359 
360 inline void BLI_bvhtree_range_query_cpp(BVHTree &tree,
361  const float3 co,
362  float radius,
363  BVHTree_RangeQuery_CPP fn)
364 {
366  &tree,
367  co,
368  radius,
369  [](void *userdata, const int index, const float co[3], const float dist_sq) {
370  BVHTree_RangeQuery_CPP fn = *static_cast<BVHTree_RangeQuery_CPP *>(userdata);
371  fn(index, co, dist_sq);
372  },
373  &fn);
374 }
375 
376 } // namespace blender
377 
378 #endif
typedef float(TangentPoint)[2]
struct BVHTreeNearest BVHTreeNearest
int BLI_bvhtree_range_query(BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
Definition: BLI_kdopbvh.c:2080
@ BVH_OVERLAP_USE_THREADING
Definition: BLI_kdopbvh.h:77
@ BVH_OVERLAP_RETURN_PAIRS
Definition: BLI_kdopbvh.h:78
struct BVHTreeOverlap BVHTreeOverlap
int BLI_bvhtree_get_tree_type(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1039
void BLI_bvhtree_ray_cast_all_ex(BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata, int flag)
Definition: BLI_kdopbvh.c:1981
@ BVH_RAYCAST_WATERTIGHT
Definition: BLI_kdopbvh.h:86
int BLI_bvhtree_find_nearest_ex(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
Definition: BLI_kdopbvh.c:1567
int BLI_bvhtree_find_nearest_first(BVHTree *tree, const float co[3], float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1682
BVHTreeOverlap * BLI_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1363
const float bvhtree_kdop_axes[13][3]
Definition: BLI_kdopbvh.c:170
void BLI_bvhtree_balance(BVHTree *tree)
Definition: BLI_kdopbvh.c:937
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
Definition: BLI_kdopbvh.c:854
void BLI_bvhtree_update_tree(BVHTree *tree)
Definition: BLI_kdopbvh.c:1021
int BLI_bvhtree_ray_cast_ex(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
Definition: BLI_kdopbvh.c:1897
int BLI_bvhtree_find_nearest_projected(BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float clip_planes[6][4], int clip_plane_len, BVHTreeNearest *nearest, BVHTree_NearestProjectedCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:2233
float BLI_bvhtree_bb_raycast(const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
Definition: BLI_kdopbvh.c:1954
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)
Definition: BLI_kdopbvh.c:1263
bool(* BVHTree_WalkLeafCallback)(const BVHTreeAxisRange *bounds, int index, void *userdata)
Definition: BLI_kdopbvh.h:136
void BLI_bvhtree_free(BVHTree *tree)
Definition: BLI_kdopbvh.c:926
bool(* BVHTree_WalkOrderCallback)(const BVHTreeAxisRange *bounds, char axis, void *userdata)
Definition: BLI_kdopbvh.h:142
void(* BVHTree_RayCastCallback)(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
Definition: BLI_kdopbvh.h:102
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
Definition: BLI_kdopbvh.c:979
@ BVH_NEAREST_OPTIMAL_ORDER
Definition: BLI_kdopbvh.h:82
bool BLI_bvhtree_update_node(BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
Definition: BLI_kdopbvh.c:997
void BLI_bvhtree_walk_dfs(BVHTree *tree, BVHTree_WalkParentCallback walk_parent_cb, BVHTree_WalkLeafCallback walk_leaf_cb, BVHTree_WalkOrderCallback walk_order_cb, void *userdata)
Definition: BLI_kdopbvh.c:2347
int BLI_bvhtree_get_len(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1034
bool(* BVHTree_WalkParentCallback)(const BVHTreeAxisRange *bounds, void *userdata)
Definition: BLI_kdopbvh.h:132
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1234
void(* BVHTree_NearestPointCallback)(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
Definition: BLI_kdopbvh.h:94
bool(* BVHTree_OverlapCallback)(void *userdata, int index_a, int index_b, int thread)
Definition: BLI_kdopbvh.h:110
int * BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_num)
Definition: BLI_kdopbvh.c:1420
struct BVHTreeAxisRange BVHTreeAxisRange
struct BVHTreeRayHit BVHTreeRayHit
float BLI_bvhtree_get_epsilon(const BVHTree *tree)
Definition: BLI_kdopbvh.c:1044
struct BVHTreeRay BVHTreeRay
void BLI_bvhtree_get_bounding_box(BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
Definition: BLI_kdopbvh.c:1049
void BLI_bvhtree_ray_cast_all(BVHTree *tree, const float co[3], const float dir[3], float radius, float hit_dist, BVHTree_RayCastCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:2015
int BLI_bvhtree_ray_cast(BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1942
void(* BVHTree_RangeQuery)(void *userdata, int index, const float co[3], float dist_sq)
Definition: BLI_kdopbvh.h:115
void(* BVHTree_NearestProjectedCallback)(void *userdata, int index, const struct DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest)
Definition: BLI_kdopbvh.h:120
int BLI_bvhtree_find_nearest(BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
Definition: BLI_kdopbvh.c:1616
unsigned int uint
Definition: BLI_sys_types.h:67
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:299
Definition: thread.h:34
DEGForeachIDComponentCallback callback
SyclQueue void void size_t num_bytes void
void * tree
uint pos
static double epsilon
float range[2]
Definition: BLI_kdopbvh.h:28
float co[3]
Definition: BLI_kdopbvh.h:43
float no[3]
Definition: BLI_kdopbvh.h:46
float co[3]
Definition: BLI_kdopbvh.h:68
float no[3]
Definition: BLI_kdopbvh.h:70
float origin[3]
Definition: BLI_kdopbvh.h:54
struct IsectRayPrecalc * isect_precalc
Definition: BLI_kdopbvh.h:60
float direction[3]
Definition: BLI_kdopbvh.h:56
float radius
Definition: BLI_kdopbvh.h:58