Blender  V3.3
Classes | Macros | Variables
BLI_kdopbvh.c File Reference

BVH-tree implementation. More...

#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_heap_simple.h"
#include "BLI_kdopbvh.h"
#include "BLI_math.h"
#include "BLI_stack.h"
#include "BLI_task.h"
#include "BLI_utildefines.h"
#include "BLI_strict_flags.h"

Go to the source code of this file.

Classes

class  BVHNode
 
struct  BVHTree
 
struct  BVHOverlapData_Thread
 
struct  BVHNearestData
 
struct  BVHRayCastData
 
struct  BVHNearestProjectedData
 
struct  BVHIntersectPlaneData
 
struct  BVHBuildHelper
 
struct  BVHDivNodesData
 
struct  RangeQueryData
 
struct  BVHTree_WalkData
 

Macros

#define MAX_TREETYPE   32
 
#define KDOPBVH_THREAD_LEAF_THRESHOLD   1024
 

Functions

Utility Functions
MINLINE axis_t min_axis (axis_t a, axis_t b)
 
static void node_minmax_init (const BVHTree *tree, BVHNode *node)
 
BLI_bvhtree API
BVHTreeBLI_bvhtree_new (int maxsize, float epsilon, char tree_type, char axis)
 
void BLI_bvhtree_free (BVHTree *tree)
 
void BLI_bvhtree_balance (BVHTree *tree)
 
static void bvhtree_node_inflate (const BVHTree *tree, BVHNode *node, const float dist)
 
void BLI_bvhtree_insert (BVHTree *tree, int index, const float co[3], int numpoints)
 
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_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])
 
BLI_bvhtree_overlap
static bool tree_overlap_test (const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis)
 
static void tree_overlap_traverse (BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
 
static void tree_overlap_traverse_cb (BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
 
static bool tree_overlap_traverse_num (BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
 
int BLI_bvhtree_overlap_thread_num (const BVHTree *tree)
 
static void bvhtree_overlap_task_cb (void *__restrict userdata, const int j, const TaskParallelTLS *__restrict UNUSED(tls))
 
BVHTreeOverlapBLI_bvhtree_overlap_ex (const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, const uint max_interactions, const int flag)
 
BVHTreeOverlapBLI_bvhtree_overlap (const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
 
BLI_bvhtree_intersect_plane
static bool tree_intersect_plane_test (const float *bv, const float plane[4])
 
static void bvhtree_intersect_plane_dfs_recursive (BVHIntersectPlaneData *__restrict data, const BVHNode *node)
 
int * BLI_bvhtree_intersect_plane (BVHTree *tree, float plane[4], uint *r_intersect_num)
 
BLI_bvhtree_find_nearest
static float calc_nearest_point_squared (const float proj[3], BVHNode *node, float nearest[3])
 
static void dfs_find_nearest_dfs (BVHNearestData *data, BVHNode *node)
 
static void dfs_find_nearest_begin (BVHNearestData *data, BVHNode *node)
 
static void heap_find_nearest_inner (BVHNearestData *data, HeapSimple *heap, BVHNode *node)
 
static void heap_find_nearest_begin (BVHNearestData *data, BVHNode *root)
 
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)
 
BLI_bvhtree_find_nearest_first
static bool isect_aabb_v3 (BVHNode *node, const float co[3])
 
static bool dfs_find_duplicate_fast_dfs (BVHNearestData *data, BVHNode *node)
 
int BLI_bvhtree_find_nearest_first (BVHTree *tree, const float co[3], const float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
 
BLI_bvhtree_ray_cast

raycast is done by performing a DFS on the BVHTree and saving the closest hit.

static float ray_nearest_hit (const BVHRayCastData *data, const float bv[6])
 
static float fast_ray_nearest_hit (const BVHRayCastData *data, const BVHNode *node)
 
static void dfs_raycast (BVHRayCastData *data, BVHNode *node)
 
static void dfs_raycast_all (BVHRayCastData *data, BVHNode *node)
 
static void bvhtree_ray_cast_data_precalc (BVHRayCastData *data, int flag)
 
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)
 
float BLI_bvhtree_bb_raycast (const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
 
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)
 
BLI_bvhtree_nearest_projected
static void bvhtree_nearest_projected_dfs_recursive (BVHNearestProjectedData *__restrict data, const BVHNode *node)
 
static void bvhtree_nearest_projected_with_clipplane_test_dfs_recursive (BVHNearestProjectedData *__restrict data, const BVHNode *node)
 
int BLI_bvhtree_find_nearest_projected (BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float clip_plane[6][4], int clip_plane_len, BVHTreeNearest *nearest, BVHTree_NearestProjectedCallback callback, void *userdata)
 

Variables

const float bvhtree_kdop_axes [13][3]
 
static const float bvhtree_kdop_axes_length [13]
 

Struct Definitions

typedef unsigned char axis_t
 
typedef struct BVHNode BVHNode
 
typedef struct BVHOverlapData_Thread BVHOverlapData_Thread
 
typedef struct BVHNearestData BVHNearestData
 
typedef struct BVHRayCastData BVHRayCastData
 
typedef struct BVHNearestProjectedData BVHNearestProjectedData
 
typedef struct BVHIntersectPlaneData BVHIntersectPlaneData
 
 BVHOverlapData_Shared
 
 BLI_STATIC_ASSERT ((sizeof(void *)==8 &&sizeof(BVHTree)<=48)||(sizeof(void *)==4 &&sizeof(BVHTree)<=32), "over sized")
 

Balance Utility Functions

typedef struct BVHBuildHelper BVHBuildHelper
 
typedef struct BVHDivNodesData BVHDivNodesData
 
static void bvh_insertionsort (BVHNode **a, int lo, int hi, int axis)
 
static int bvh_partition (BVHNode **a, int lo, int hi, BVHNode *x, int axis)
 
static BVHNodebvh_medianof3 (BVHNode **a, int lo, int mid, int hi, int axis)
 
static void partition_nth_element (BVHNode **a, int begin, int end, const int n, const int axis)
 
static void create_kdop_hull (const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
 
static void refit_kdop_hull (const BVHTree *tree, BVHNode *node, int start, int end)
 
static char get_largest_axis (const float *bv)
 
static void node_join (BVHTree *tree, BVHNode *node)
 
static void build_implicit_tree_helper (const BVHTree *tree, BVHBuildHelper *data)
 
static int implicit_leafs_index (const BVHBuildHelper *data, const int depth, const int child_index)
 
static int implicit_needed_branches (int tree_type, int leafs)
 
static void split_leafs (BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis)
 
static void non_recursive_bvh_div_nodes_task_cb (void *__restrict userdata, const int j, const TaskParallelTLS *__restrict UNUSED(tls))
 
static void non_recursive_bvh_div_nodes (const BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int leafs_num)
 

BLI_bvhtree_range_query

Allocates and fills an array with the indices of node that are on the given spherical range (center, radius). Returns the size of the array.

typedef struct RangeQueryData RangeQueryData
 
static void dfs_range_query (RangeQueryData *data, BVHNode *node)
 
int BLI_bvhtree_range_query (BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
 

BLI_bvhtree_walk_dfs

typedef struct BVHTree_WalkData BVHTree_WalkData
 
static bool bvhtree_walk_dfs_recursive (BVHTree_WalkData *walk_data, const BVHNode *node)
 
void BLI_bvhtree_walk_dfs (BVHTree *tree, BVHTree_WalkParentCallback walk_parent_cb, BVHTree_WalkLeafCallback walk_leaf_cb, BVHTree_WalkOrderCallback walk_order_cb, void *userdata)
 

Detailed Description

BVH-tree implementation.

k-DOP BVH (Discrete Oriented Polytope, Bounding Volume Hierarchy). A k-DOP is represented as k/2 pairs of min, max values for k/2 directions (intervals, "slabs").

See: http://www.gris.uni-tuebingen.de/people/staff/jmezger/papers/bvh.pdf

implements a BVH-tree structure with support for:

Definition in file BLI_kdopbvh.c.

Macro Definition Documentation

◆ KDOPBVH_THREAD_LEAF_THRESHOLD

#define KDOPBVH_THREAD_LEAF_THRESHOLD   1024

Definition at line 54 of file BLI_kdopbvh.c.

◆ MAX_TREETYPE

#define MAX_TREETYPE   32

Definition at line 46 of file BLI_kdopbvh.c.

Typedef Documentation

◆ axis_t

typedef unsigned char axis_t

Definition at line 61 of file BLI_kdopbvh.c.

◆ BVHBuildHelper

◆ BVHDivNodesData

◆ BVHIntersectPlaneData

◆ BVHNearestData

◆ BVHNearestProjectedData

◆ BVHNode

typedef struct BVHNode BVHNode

◆ BVHOverlapData_Thread

◆ BVHRayCastData

◆ BVHTree_WalkData

◆ RangeQueryData

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_plane[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,
uint 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.

◆ BLI_STATIC_ASSERT()

BLI_STATIC_ASSERT ( (sizeof(void *)==8 &&sizeof(BVHTree)<=48)||(sizeof(void *)==4 &&sizeof(BVHTree)<=32)  ,
"over sized"   
)

Definition at line 90 of file BLI_kdopbvh.c.

References callback.

◆ build_implicit_tree_helper()

static void build_implicit_tree_helper ( const BVHTree tree,
BVHBuildHelper data 
)
static

Definition at line 570 of file BLI_kdopbvh.c.

References data, and tree.

Referenced by non_recursive_bvh_div_nodes().

◆ bvh_insertionsort()

static void bvh_insertionsort ( BVHNode **  a,
int  lo,
int  hi,
int  axis 
)
static

Insertion sort algorithm

Definition at line 245 of file BLI_kdopbvh.c.

References Freestyle::a, and t.

Referenced by partition_nth_element().

◆ bvh_medianof3()

static BVHNode* bvh_medianof3 ( BVHNode **  a,
int  lo,
int  mid,
int  hi,
int  axis 
)
static

Definition at line 280 of file BLI_kdopbvh.c.

References Freestyle::a.

Referenced by partition_nth_element().

◆ bvh_partition()

static int bvh_partition ( BVHNode **  a,
int  lo,
int  hi,
BVHNode x,
int  axis 
)
static

Definition at line 260 of file BLI_kdopbvh.c.

References Freestyle::a, SWAP, and x.

Referenced by partition_nth_element().

◆ bvhtree_intersect_plane_dfs_recursive()

static void bvhtree_intersect_plane_dfs_recursive ( BVHIntersectPlaneData *__restrict  data,
const BVHNode node 
)
static

◆ bvhtree_nearest_projected_dfs_recursive()

static void bvhtree_nearest_projected_dfs_recursive ( BVHNearestProjectedData *__restrict  data,
const BVHNode node 
)
static

◆ bvhtree_nearest_projected_with_clipplane_test_dfs_recursive()

static void bvhtree_nearest_projected_with_clipplane_test_dfs_recursive ( BVHNearestProjectedData *__restrict  data,
const BVHNode node 
)
static

◆ bvhtree_node_inflate()

static void bvhtree_node_inflate ( const BVHTree tree,
BVHNode node,
const float  dist 
)
static

Definition at line 969 of file BLI_kdopbvh.c.

References bvhtree_kdop_axes_length, node, and tree.

Referenced by BLI_bvhtree_insert(), and BLI_bvhtree_update_node().

◆ bvhtree_overlap_task_cb()

static void bvhtree_overlap_task_cb ( void *__restrict  userdata,
const int  j,
const TaskParallelTLS *__restrict   UNUSEDtls 
)
static

◆ bvhtree_ray_cast_data_precalc()

static void bvhtree_ray_cast_data_precalc ( BVHRayCastData data,
int  flag 
)
static

◆ bvhtree_walk_dfs_recursive()

static bool bvhtree_walk_dfs_recursive ( BVHTree_WalkData walk_data,
const BVHNode node 
)
static

Runs first among nodes children of the first node before going to the next node in the same layer.

Returns
false to break out of the search early.

Definition at line 2315 of file BLI_kdopbvh.c.

References node, BVHTree_WalkData::userdata, BVHTree_WalkData::walk_leaf_cb, BVHTree_WalkData::walk_order_cb, and BVHTree_WalkData::walk_parent_cb.

Referenced by BLI_bvhtree_walk_dfs().

◆ calc_nearest_point_squared()

static float calc_nearest_point_squared ( const float  proj[3],
BVHNode node,
float  nearest[3] 
)
static

◆ create_kdop_hull()

static void create_kdop_hull ( const BVHTree tree,
BVHNode node,
const float co,
int  numpoints,
int  moving 
)
static

Definition at line 344 of file BLI_kdopbvh.c.

References bvhtree_kdop_axes, dot_v3v3(), node, node_minmax_init(), and tree.

Referenced by BLI_bvhtree_insert(), and BLI_bvhtree_update_node().

◆ dfs_find_duplicate_fast_dfs()

static bool dfs_find_duplicate_fast_dfs ( BVHNearestData data,
BVHNode node 
)
static

Definition at line 1643 of file BLI_kdopbvh.c.

References data, isect_aabb_v3(), and node.

Referenced by BLI_bvhtree_find_nearest_first().

◆ dfs_find_nearest_begin()

static void dfs_find_nearest_begin ( BVHNearestData data,
BVHNode node 
)
static

Definition at line 1512 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), data, dfs_find_nearest_dfs(), and node.

Referenced by BLI_bvhtree_find_nearest_ex().

◆ dfs_find_nearest_dfs()

static void dfs_find_nearest_dfs ( BVHNearestData data,
BVHNode node 
)
static

Definition at line 1474 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), data, and node.

Referenced by dfs_find_nearest_begin().

◆ dfs_range_query()

static void dfs_range_query ( RangeQueryData data,
BVHNode node 
)
static

Definition at line 2049 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), data, and node.

Referenced by BLI_bvhtree_range_query().

◆ dfs_raycast()

static void dfs_raycast ( BVHRayCastData data,
BVHNode node 
)
static

Definition at line 1786 of file BLI_kdopbvh.c.

References data, fast_ray_nearest_hit(), madd_v3_v3v3fl(), node, and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_ex().

◆ dfs_raycast_all()

static void dfs_raycast_all ( BVHRayCastData data,
BVHNode node 
)
static

A version of dfs_raycast with minor changes to reset the index & dist each ray cast.

Definition at line 1827 of file BLI_kdopbvh.c.

References data, fast_ray_nearest_hit(), node, and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_all_ex().

◆ fast_ray_nearest_hit()

static float fast_ray_nearest_hit ( const BVHRayCastData data,
const BVHNode node 
)
static

Determines the distance that the ray must travel to hit the bounding volume of the given node Based on Tactical Optimization of Ray/Box Intersection, by Graham Fyffe [http://tog.acm.org/resources/RTNews/html/rtnv21n1.html#art9]

TODO: this doesn't take data->ray.radius into consideration.

Definition at line 1767 of file BLI_kdopbvh.c.

References data, max_fff(), and node.

Referenced by dfs_raycast(), and dfs_raycast_all().

◆ get_largest_axis()

static char get_largest_axis ( const float bv)
static

only supports x,y,z axis in the moment but we should use a plain and simple function here for speed sake

Definition at line 404 of file BLI_kdopbvh.c.

Referenced by non_recursive_bvh_div_nodes(), and non_recursive_bvh_div_nodes_task_cb().

◆ heap_find_nearest_begin()

static void heap_find_nearest_begin ( BVHNearestData data,
BVHNode root 
)
static

◆ heap_find_nearest_inner()

static void heap_find_nearest_inner ( BVHNearestData data,
HeapSimple heap,
BVHNode node 
)
static

Definition at line 1523 of file BLI_kdopbvh.c.

References BLI_heapsimple_insert(), calc_nearest_point_squared(), data, and node.

Referenced by heap_find_nearest_begin().

◆ implicit_leafs_index()

static int implicit_leafs_index ( const BVHBuildHelper data,
const int  depth,
const int  child_index 
)
static

Return the min index of all the leafs achievable with the given branch.

Definition at line 600 of file BLI_kdopbvh.c.

References data.

Referenced by non_recursive_bvh_div_nodes_task_cb().

◆ implicit_needed_branches()

static int implicit_needed_branches ( int  tree_type,
int  leafs 
)
static

Generalized implicit tree build

An implicit tree is a tree where its structure is implied, thus there is no need to store child pointers or indexes. It's possible to find the position of the child or the parent with simple maths (multiplication and addition). This type of tree is for example used on heaps.. where node N has its child at indices N*2 and N*2+1.

Although in this case the tree type is general.. and not know until run-time. tree_type stands for the maximum number of children that a tree node can have. All tree types >= 2 are supported.

Advantages of the used trees include:

  • No need to store child/parent relations (they are implicit);
  • Any node child always has an index greater than the parent;
  • Brother nodes are sequential in memory; Some math relations derived for general implicit trees:

    K = tree_type, ( 2 <= K ) ROOT = 1 N child of node A = A * K + (2 - K) + N, (0 <= N < K)

Util methods: TODO... (looping elements, knowing if its a leaf or not.. etc...)

Definition at line 643 of file BLI_kdopbvh.c.

References max_ii().

Referenced by BLI_bvhtree_balance(), BLI_bvhtree_new(), and non_recursive_bvh_div_nodes().

◆ isect_aabb_v3()

static bool isect_aabb_v3 ( BVHNode node,
const float  co[3] 
)
static

Definition at line 1631 of file BLI_kdopbvh.c.

References if(), max, min, and node.

Referenced by dfs_find_duplicate_fast_dfs().

◆ min_axis()

MINLINE axis_t min_axis ( axis_t  a,
axis_t  b 
)

Definition at line 207 of file BLI_kdopbvh.c.

References Freestyle::a, and usdtokens::b().

Referenced by BLI_bvhtree_overlap_ex(), and BM_face_split_edgenet_connect_islands().

◆ node_join()

static void node_join ( BVHTree tree,
BVHNode node 
)
static

bottom-up update of bvh node BV join the children on the parent BV

Definition at line 426 of file BLI_kdopbvh.c.

References node, node_minmax_init(), and tree.

Referenced by BLI_bvhtree_update_tree().

◆ node_minmax_init()

static void node_minmax_init ( const BVHTree tree,
BVHNode node 
)
static

Intro-sort with permission deriving from the following Java code: http://ralphunden.net/content/tutorials/a-guide-to-introsort/ and he derived it from the SUN STL

Definition at line 225 of file BLI_kdopbvh.c.

References float(), node, and tree.

Referenced by create_kdop_hull(), node_join(), and refit_kdop_hull().

◆ non_recursive_bvh_div_nodes()

static void non_recursive_bvh_div_nodes ( const BVHTree tree,
BVHNode branches_array,
BVHNode **  leafs_array,
int  leafs_num 
)
static

This functions builds an optimal implicit tree from the given leafs. Where optimal stands for:

  • The resulting tree will have the smallest number of branches;
  • At most only one branch will have NULL children;
  • All leafs will be stored at level N or N+1.

This function creates an implicit tree on branches_array, the leafs are given on the leafs_array.

The tree is built per depth levels. First branches at depth 1.. then branches at depth 2.. etc.. The reason is that we can build level N+1 from level N without any data dependencies.. thus it allows to use multi-thread building.

To archive this is necessary to find how much leafs are accessible from a certain branch, BVHBuildHelper, implicit_needed_branches and implicit_leafs_index are auxiliary functions to solve that "optimal-split".

Definition at line 774 of file BLI_kdopbvh.c.

References BLI_parallel_range_settings_defaults(), BLI_task_parallel_range(), build_implicit_tree_helper(), BVHNode::bv, BVHNode::children, data, BVHDivNodesData::depth, BVHDivNodesData::first_of_next_level, get_largest_axis(), BVHDivNodesData::i, implicit_needed_branches(), KDOPBVH_THREAD_LEAF_THRESHOLD, BVHNode::main_axis, min_ii(), BVHNode::node_num, non_recursive_bvh_div_nodes_task_cb(), NULL, BVHNode::parent, refit_kdop_hull(), BVHDivNodesData::tree, tree, and TaskParallelSettings::use_threading.

Referenced by BLI_bvhtree_balance().

◆ non_recursive_bvh_div_nodes_task_cb()

static void non_recursive_bvh_div_nodes_task_cb ( void *__restrict  userdata,
const int  j,
const TaskParallelTLS *__restrict   UNUSEDtls 
)
static

◆ partition_nth_element()

static void partition_nth_element ( BVHNode **  a,
int  begin,
int  end,
const int  n,
const int  axis 
)
static
Note
after a call to this function you can expect one of:
  • every node to left of a[n] are smaller or equal to it
  • every node to the right of a[n] are greater or equal to it

Definition at line 305 of file BLI_kdopbvh.c.

References Freestyle::a, bvh_insertionsort(), bvh_medianof3(), and bvh_partition().

Referenced by split_leafs().

◆ ray_nearest_hit()

static float ray_nearest_hit ( const BVHRayCastData data,
const float  bv[6] 
)
static

Definition at line 1718 of file BLI_kdopbvh.c.

References data, and low().

Referenced by BLI_bvhtree_bb_raycast(), dfs_raycast(), and dfs_raycast_all().

◆ refit_kdop_hull()

static void refit_kdop_hull ( const BVHTree tree,
BVHNode node,
int  start,
int  end 
)
static
Note
depends on the fact that the BVH's for each face is already built

Definition at line 374 of file BLI_kdopbvh.c.

References node, node_minmax_init(), and tree.

Referenced by non_recursive_bvh_div_nodes(), and non_recursive_bvh_div_nodes_task_cb().

◆ split_leafs()

static void split_leafs ( BVHNode **  leafs_array,
const int  nth[],
const int  partitions,
const int  split_axis 
)
static

This function handles the problem of "sorting" the leafs (along the split_axis).

It arranges the elements in the given partitions such that:

  • any element in partition N is less or equal to any element in partition N+1.
  • if all elements are different all partition will get the same subset of elements as if the array was sorted.

partition P is described as the elements in the range ( nth[P], nth[P+1] ]

TODO: This can be optimized a bit by doing a specialized nth_element instead of K nth_elements

Definition at line 660 of file BLI_kdopbvh.c.

References partition_nth_element().

Referenced by non_recursive_bvh_div_nodes_task_cb().

◆ tree_intersect_plane_test()

static bool tree_intersect_plane_test ( const float bv,
const float  plane[4] 
)
static

◆ tree_overlap_test()

static bool tree_overlap_test ( const BVHNode node1,
const BVHNode node2,
axis_t  start_axis,
axis_t  stop_axis 
)
static

overlap - is it possible for 2 bv's to collide ?

Definition at line 1074 of file BLI_kdopbvh.c.

References BVHNode::bv.

Referenced by BLI_bvhtree_overlap_ex(), tree_overlap_traverse(), tree_overlap_traverse_cb(), and tree_overlap_traverse_num().

◆ tree_overlap_traverse()

static void tree_overlap_traverse ( BVHOverlapData_Thread data_thread,
const BVHNode node1,
const BVHNode node2 
)
static

◆ tree_overlap_traverse_cb()

static void tree_overlap_traverse_cb ( BVHOverlapData_Thread data_thread,
const BVHNode node1,
const BVHNode node2 
)
static

◆ tree_overlap_traverse_num()

static bool tree_overlap_traverse_num ( BVHOverlapData_Thread data_thread,
const BVHNode node1,
const BVHNode node2 
)
static

Variable Documentation

◆ BVHOverlapData_Shared

BVHOverlapData_Shared

◆ bvhtree_kdop_axes

const float bvhtree_kdop_axes[13][3]
Initial value:
= {
{1.0, 0, 0},
{0, 1.0, 0},
{0, 0, 1.0},
{1.0, 1.0, 1.0},
{1.0, -1.0, 1.0},
{1.0, 1.0, -1.0},
{1.0, -1.0, -1.0},
{1.0, 1.0, 0},
{1.0, 0, 1.0},
{0, 1.0, 1.0},
{1.0, -1.0, 0},
{1.0, 0, -1.0},
{0, 1.0, -1.0},
}

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().

◆ bvhtree_kdop_axes_length

const float bvhtree_kdop_axes_length[13]
static
Initial value:
= {
1.0f,
1.0f,
1.0f,
1.7320508075688772f,
1.7320508075688772f,
1.7320508075688772f,
1.7320508075688772f,
1.4142135623730951f,
1.4142135623730951f,
1.4142135623730951f,
1.4142135623730951f,
1.4142135623730951f,
1.4142135623730951f,
}

Definition at line 187 of file BLI_kdopbvh.c.

Referenced by bvhtree_node_inflate().