Blender  V3.3
Classes | Macros | Typedefs | Enumerations | Functions | Variables
BLI_kdopbvh.h File Reference
#include "BLI_sys_types.h"

Go to the source code of this file.

Classes

struct  BVHTreeAxisRange
 
struct  BVHTreeOverlap
 
struct  BVHTreeNearest
 
struct  BVHTreeRay
 
struct  BVHTreeRayHit
 

Macros

#define USE_KDOPBVH_WATERTIGHT
 
#define BVH_RAYCAST_DEFAULT   (BVH_RAYCAST_WATERTIGHT)
 
#define BVH_RAYCAST_DIST_MAX   (FLT_MAX / 2.0f)
 

Typedefs

typedef struct BVHTree BVHTree
 
typedef struct BVHTreeAxisRange BVHTreeAxisRange
 
typedef struct BVHTreeOverlap BVHTreeOverlap
 
typedef struct BVHTreeNearest BVHTreeNearest
 
typedef struct BVHTreeRay BVHTreeRay
 
typedef struct BVHTreeRayHit BVHTreeRayHit
 
typedef void(* BVHTree_NearestPointCallback) (void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
 
typedef void(* BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
 
typedef bool(* BVHTree_OverlapCallback) (void *userdata, int index_a, int index_b, int thread)
 
typedef void(* BVHTree_RangeQuery) (void *userdata, int index, const float co[3], float dist_sq)
 
typedef void(* BVHTree_NearestProjectedCallback) (void *userdata, int index, const struct DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest)
 
typedef bool(* BVHTree_WalkParentCallback) (const BVHTreeAxisRange *bounds, void *userdata)
 
typedef bool(* BVHTree_WalkLeafCallback) (const BVHTreeAxisRange *bounds, int index, void *userdata)
 
typedef bool(* BVHTree_WalkOrderCallback) (const BVHTreeAxisRange *bounds, char axis, void *userdata)
 

Enumerations

enum  { BVH_OVERLAP_USE_THREADING = (1 << 0) , BVH_OVERLAP_RETURN_PAIRS = (1 << 1) }
 
enum  { BVH_NEAREST_OPTIMAL_ORDER = (1 << 0) }
 
enum  { BVH_RAYCAST_WATERTIGHT = (1 << 0) }
 

Functions

BVHTreeBLI_bvhtree_new (int maxsize, float epsilon, char tree_type, char axis)
 
void BLI_bvhtree_free (BVHTree *tree)
 
void BLI_bvhtree_insert (BVHTree *tree, int index, const float co[3], int numpoints)
 
void BLI_bvhtree_balance (BVHTree *tree)
 
bool BLI_bvhtree_update_node (BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
 
void BLI_bvhtree_update_tree (BVHTree *tree)
 
int BLI_bvhtree_overlap_thread_num (const BVHTree *tree)
 
BVHTreeOverlapBLI_bvhtree_overlap_ex (const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
 
BVHTreeOverlapBLI_bvhtree_overlap (const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
 
int * BLI_bvhtree_intersect_plane (BVHTree *tree, float plane[4], uint *r_intersect_num)
 
int BLI_bvhtree_get_len (const BVHTree *tree)
 
int BLI_bvhtree_get_tree_type (const BVHTree *tree)
 
float BLI_bvhtree_get_epsilon (const BVHTree *tree)
 
void BLI_bvhtree_get_bounding_box (BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
 
int BLI_bvhtree_find_nearest_ex (BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
 
int BLI_bvhtree_find_nearest (BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
 
int BLI_bvhtree_find_nearest_first (BVHTree *tree, const float co[3], float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
 
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)
 
int BLI_bvhtree_ray_cast (BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
 
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)
 
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)
 
float BLI_bvhtree_bb_raycast (const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
 
int BLI_bvhtree_range_query (BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
 
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)
 
void BLI_bvhtree_walk_dfs (BVHTree *tree, BVHTree_WalkParentCallback walk_parent_cb, BVHTree_WalkLeafCallback walk_leaf_cb, BVHTree_WalkOrderCallback walk_order_cb, void *userdata)
 

Variables

const float bvhtree_kdop_axes [13][3]
 

Macro Definition Documentation

◆ BVH_RAYCAST_DEFAULT

#define BVH_RAYCAST_DEFAULT   (BVH_RAYCAST_WATERTIGHT)

Definition at line 88 of file BLI_kdopbvh.h.

◆ BVH_RAYCAST_DIST_MAX

#define BVH_RAYCAST_DIST_MAX   (FLT_MAX / 2.0f)

Definition at line 89 of file BLI_kdopbvh.h.

◆ USE_KDOPBVH_WATERTIGHT

#define USE_KDOPBVH_WATERTIGHT

Definition at line 20 of file BLI_kdopbvh.h.

Typedef Documentation

◆ BVHTree

typedef struct BVHTree BVHTree

Definition at line 1 of file BLI_kdopbvh.h.

◆ BVHTree_NearestPointCallback

typedef void(* BVHTree_NearestPointCallback) (void *userdata, int index, const float co[3], BVHTreeNearest *nearest)

Callback must update nearest in case it finds a nearest result.

Definition at line 94 of file BLI_kdopbvh.h.

◆ BVHTree_NearestProjectedCallback

typedef void(* BVHTree_NearestProjectedCallback) (void *userdata, int index, const struct DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest)

Callback to find nearest projected.

Definition at line 120 of file BLI_kdopbvh.h.

◆ BVHTree_OverlapCallback

typedef bool(* BVHTree_OverlapCallback) (void *userdata, int index_a, int index_b, int thread)

Callback to check if 2 nodes overlap (use thread if intersection results need to be stored).

Definition at line 110 of file BLI_kdopbvh.h.

◆ BVHTree_RangeQuery

typedef void(* BVHTree_RangeQuery) (void *userdata, int index, const float co[3], float dist_sq)

Callback to range search query.

Definition at line 115 of file BLI_kdopbvh.h.

◆ BVHTree_RayCastCallback

typedef void(* BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)

Callback must update hit in case it finds a nearest successful hit.

Definition at line 102 of file BLI_kdopbvh.h.

◆ BVHTree_WalkLeafCallback

typedef bool(* BVHTree_WalkLeafCallback) (const BVHTreeAxisRange *bounds, int index, void *userdata)

Return true to keep walking, else early-exit the search.

Definition at line 136 of file BLI_kdopbvh.h.

◆ BVHTree_WalkOrderCallback

typedef bool(* BVHTree_WalkOrderCallback) (const BVHTreeAxisRange *bounds, char axis, void *userdata)

Return true to search (min, max) else (max, min).

Definition at line 142 of file BLI_kdopbvh.h.

◆ BVHTree_WalkParentCallback

typedef bool(* BVHTree_WalkParentCallback) (const BVHTreeAxisRange *bounds, void *userdata)

Return true to traverse into this nodes children, else skip.

Definition at line 132 of file BLI_kdopbvh.h.

◆ BVHTreeAxisRange

◆ BVHTreeNearest

◆ BVHTreeOverlap

◆ BVHTreeRay

typedef struct BVHTreeRay BVHTreeRay

◆ BVHTreeRayHit

typedef struct BVHTreeRayHit BVHTreeRayHit

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
BVH_OVERLAP_USE_THREADING 
BVH_OVERLAP_RETURN_PAIRS 

Definition at line 75 of file BLI_kdopbvh.h.

◆ anonymous enum

anonymous enum
Enumerator
BVH_NEAREST_OPTIMAL_ORDER 

Definition at line 80 of file BLI_kdopbvh.h.

◆ anonymous enum

anonymous enum
Enumerator
BVH_RAYCAST_WATERTIGHT 

Definition at line 84 of file BLI_kdopbvh.h.

Function Documentation

◆ BLI_bvhtree_balance()

void BLI_bvhtree_balance ( BVHTree tree)

◆ BLI_bvhtree_bb_raycast()

float BLI_bvhtree_bb_raycast ( const float  bv[6],
const float  light_start[3],
const float  light_end[3],
float  pos[3] 
)

◆ BLI_bvhtree_find_nearest()

int BLI_bvhtree_find_nearest ( BVHTree tree,
const float  co[3],
BVHTreeNearest nearest,
BVHTree_NearestPointCallback  callback,
void userdata 
)

◆ BLI_bvhtree_find_nearest_ex()

int BLI_bvhtree_find_nearest_ex ( BVHTree tree,
const float  co[3],
BVHTreeNearest nearest,
BVHTree_NearestPointCallback  callback,
void userdata,
int  flag 
)

Find nearest node to the given coordinates (if nearest is given it will only search nodes where square distance is smaller than nearest->dist).

Definition at line 1567 of file BLI_kdopbvh.c.

References BVH_NEAREST_OPTIMAL_ORDER, bvhtree_kdop_axes, callback, data, dfs_find_nearest_begin(), dot_v3v3(), heap_find_nearest_begin(), and tree.

Referenced by BKE_shrinkwrap_find_nearest_surface(), BLI_bvhtree_find_nearest(), and find_nearest_points_test().

◆ BLI_bvhtree_find_nearest_first()

int BLI_bvhtree_find_nearest_first ( BVHTree tree,
const float  co[3],
float  dist_sq,
BVHTree_NearestPointCallback  callback,
void userdata 
)

Find the first node nearby. Favors speed over quality since it doesn't find the best target node.

Definition at line 1682 of file BLI_kdopbvh.c.

References callback, data, dfs_find_duplicate_fast_dfs(), and tree.

◆ BLI_bvhtree_find_nearest_projected()

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 
)

◆ BLI_bvhtree_free()

void BLI_bvhtree_free ( BVHTree tree)

◆ BLI_bvhtree_get_bounding_box()

void BLI_bvhtree_get_bounding_box ( BVHTree tree,
float  r_bb_min[3],
float  r_bb_max[3] 
)

This function returns the bounding box of the BVH tree.

Definition at line 1049 of file BLI_kdopbvh.c.

References BLI_assert, BVHNode::bv, copy_v3_v3(), NULL, tree, and zero_v3().

◆ BLI_bvhtree_get_epsilon()

float BLI_bvhtree_get_epsilon ( const BVHTree tree)

◆ BLI_bvhtree_get_len()

int BLI_bvhtree_get_len ( const BVHTree tree)

◆ BLI_bvhtree_get_tree_type()

int BLI_bvhtree_get_tree_type ( const BVHTree tree)

Maximum number of children that a node can have.

Definition at line 1039 of file BLI_kdopbvh.c.

References tree.

Referenced by BKE_bvhtree_from_editmesh_get(), and BKE_bvhtree_from_mesh_get().

◆ BLI_bvhtree_insert()

void BLI_bvhtree_insert ( BVHTree tree,
int  index,
const float  co[3],
int  numpoints 
)

◆ BLI_bvhtree_intersect_plane()

int* BLI_bvhtree_intersect_plane ( BVHTree tree,
float  plane[4],
uint r_intersect_num 
)

◆ BLI_bvhtree_new()

BVHTree* BLI_bvhtree_new ( int  maxsize,
float  epsilon,
char  tree_type,
char  axis 
)

◆ BLI_bvhtree_overlap()

BVHTreeOverlap* BLI_bvhtree_overlap ( const BVHTree tree1,
const BVHTree tree2,
unsigned int *  r_overlap_num,
BVHTree_OverlapCallback  callback,
void userdata 
)

◆ BLI_bvhtree_overlap_ex()

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 
)

◆ BLI_bvhtree_overlap_thread_num()

int BLI_bvhtree_overlap_thread_num ( const BVHTree tree)

Use to check the total number of threads BLI_bvhtree_overlap will use.

Warning
Must be the first tree passed to BLI_bvhtree_overlap!

Definition at line 1234 of file BLI_kdopbvh.c.

References MIN2, and tree.

Referenced by BLI_bvhtree_overlap_ex(), and bm_elemxelem_bvhtree_overlap().

◆ BLI_bvhtree_range_query()

int BLI_bvhtree_range_query ( BVHTree tree,
const float  co[3],
float  radius,
BVHTree_RangeQuery  callback,
void userdata 
)

◆ BLI_bvhtree_ray_cast()

int BLI_bvhtree_ray_cast ( BVHTree tree,
const float  co[3],
const float  dir[3],
float  radius,
BVHTreeRayHit hit,
BVHTree_RayCastCallback  callback,
void userdata 
)

◆ BLI_bvhtree_ray_cast_all()

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 
)

◆ BLI_bvhtree_ray_cast_all_ex()

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 
)

Calls the callback for every ray intersection

Note
Using a callback which resets or never sets the BVHTreeRayHit index & dist works too, however using this function means existing generic callbacks can be used from custom callbacks without having to handle resetting the hit beforehand. It also avoid redundant argument and return value which aren't meaningful when collecting multiple hits.

Definition at line 1981 of file BLI_kdopbvh.c.

References BLI_assert, BLI_ASSERT_UNIT_V3, bvhtree_ray_cast_data_precalc(), callback, copy_v3_v3(), data, dfs_raycast_all(), NULL, and tree.

Referenced by BLI_bvhtree_ray_cast_all().

◆ BLI_bvhtree_ray_cast_ex()

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 
)

◆ BLI_bvhtree_update_node()

bool BLI_bvhtree_update_node ( BVHTree tree,
int  index,
const float  co[3],
const float  co_moving[3],
int  numpoints 
)

Update: first update points/nodes, then call update_tree to refit the bounding volumes.

Note
call before BLI_bvhtree_update_tree().

Definition at line 997 of file BLI_kdopbvh.c.

References bvhtree_node_inflate(), create_kdop_hull(), node, NULL, and tree.

Referenced by bvhtree_update_from_cloth(), and bvhtree_update_from_mvert().

◆ BLI_bvhtree_update_tree()

void BLI_bvhtree_update_tree ( BVHTree tree)

Call BLI_bvhtree_update_node() first for every node/point/triangle.

Definition at line 1021 of file BLI_kdopbvh.c.

References node_join(), and tree.

Referenced by bvhtree_update_from_cloth(), and bvhtree_update_from_mvert().

◆ BLI_bvhtree_walk_dfs()

void BLI_bvhtree_walk_dfs ( BVHTree tree,
BVHTree_WalkParentCallback  walk_parent_cb,
BVHTree_WalkLeafCallback  walk_leaf_cb,
BVHTree_WalkOrderCallback  walk_order_cb,
void userdata 
)

This is a generic function to perform a depth first search on the BVHTree where the search order and nodes traversed depend on callbacks passed in.

Parameters
treeTree to walk.
walk_parent_cbCallback on a parents bound-box to test if it should be traversed.
walk_leaf_cbCallback to test leaf nodes, callback must store its own result, returning false exits early.
walk_order_cbCallback that indicates which direction to search, either from the node with the lower or higher K-DOP axis value.
userdataArgument passed to all callbacks.

Definition at line 2347 of file BLI_kdopbvh.c.

References BVHNode::bv, bvhtree_walk_dfs_recursive(), NULL, and tree.

Variable Documentation

◆ bvhtree_kdop_axes

const float bvhtree_kdop_axes[13][3]
extern

Expose for BVH callbacks to use.

Bounding Volume Hierarchy Definition

Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below Notes: You have to choose the type at compile time ITM Notes: You can choose the tree type --> binary, quad, octree, choose below

Definition at line 170 of file BLI_kdopbvh.c.

Referenced by BLI_bvhtree_find_nearest_ex(), bvhtree_ray_cast_data_precalc(), and create_kdop_hull().