Blender V5.3
BLI_kdopbvh.cc File Reference

BVH-tree implementation. More...

#include <algorithm>
#include "MEM_guardedalloc.h"
#include "BLI_alloca.hh"
#include "BLI_heap_simple.hh"
#include "BLI_kdopbvh.hh"
#include "BLI_math_geom_c.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_stack_c.hh"
#include "BLI_task_c.hh"
#include "BLI_utildefines.hh"
#include "BLI_strict_flags.hh"

Go to the source code of this file.

Classes

struct  blender::BVHNode
struct  blender::BVHTree
struct  blender::BVHOverlapData_Thread
struct  blender::BVHNearestData
struct  blender::BVHRayCastData
struct  blender::BVHNearestProjectedData
struct  blender::BVHIntersectPlaneData
struct  blender::BVHBuildHelper
struct  blender::BVHDivNodesData
struct  blender::RangeQueryData

Namespaces

namespace  blender
 BMesh Iterators.

Macros

#define MAX_TREETYPE   32
#define KDOPBVH_THREAD_LEAF_THRESHOLD   0

Functions

Utility Functions
MINLINE axis_t blender::min_axis (axis_t a, axis_t b)
static void blender::node_minmax_init (const BVHTree *tree, BVHNode *node)
Balance Utility Functions
static void blender::bvh_insertionsort (BVHNode **a, int lo, int hi, int axis)
static int blender::bvh_partition (BVHNode **a, int lo, int hi, const BVHNode *x, int axis)
static BVHNode * blender::bvh_medianof3 (BVHNode **a, int lo, int mid, int hi, int axis)
static void blender::partition_nth_element (BVHNode **a, int begin, int end, const int n, const int axis)
static void blender::create_kdop_hull (const BVHTree *tree, BVHNode *node, const float *co, int numpoints, int moving)
static void blender::refit_kdop_hull (const BVHTree *tree, BVHNode *node, int start, int end)
static char blender::get_largest_axis (const float *bv)
static void blender::node_join (BVHTree *tree, BVHNode *node)
Implicit Tree Construction
static void blender::build_implicit_tree_helper (const BVHTree *tree, BVHBuildHelper *data)
static int blender::implicit_leafs_index (const BVHBuildHelper *data, const int depth, const int child_index)
static int blender::implicit_needed_branches (int tree_type, int leafs)
static void blender::split_leafs (BVHNode **leafs_array, const int nth[], const int partitions, const int split_axis)
static void blender::non_recursive_bvh_div_nodes_task_cb (void *__restrict userdata, const int j, const TaskParallelTLS *__restrict)
static void blender::non_recursive_bvh_div_nodes (const BVHTree *tree, BVHNode *branches_array, BVHNode **leafs_array, int leafs_num)
BLI_bvhtree API
BVHTree * blender::BLI_bvhtree_new (int maxsize, float epsilon, char tree_type, char axis)
void blender::BLI_bvhtree_free (BVHTree *tree)
void blender::BLI_bvhtree_balance (BVHTree *tree)
static void blender::bvhtree_node_inflate (const BVHTree *tree, BVHNode *node, const float dist)
void blender::BLI_bvhtree_insert (BVHTree *tree, int index, const float co[3], int numpoints)
bool blender::BLI_bvhtree_update_node (BVHTree *tree, int index, const float co[3], const float co_moving[3], int numpoints)
void blender::BLI_bvhtree_update_tree (BVHTree *tree)
int blender::BLI_bvhtree_get_len (const BVHTree *tree)
int blender::BLI_bvhtree_get_tree_type (const BVHTree *tree)
float blender::BLI_bvhtree_get_epsilon (const BVHTree *tree)
void blender::BLI_bvhtree_get_bounding_box (const BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
BLI_bvhtree_overlap
static bool blender::tree_overlap_test (const BVHNode *node1, const BVHNode *node2, axis_t start_axis, axis_t stop_axis)
static void blender::tree_overlap_traverse (BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
static void blender::tree_overlap_traverse_cb (BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
static bool blender::tree_overlap_traverse_num (BVHOverlapData_Thread *data_thread, const BVHNode *node1, const BVHNode *node2)
static void blender::tree_overlap_invoke_traverse (BVHOverlapData_Thread *data, const BVHNode *node1, const BVHNode *node2)
static void blender::tree_overlap_traverse_self_cb (BVHOverlapData_Thread *data_thread, const BVHNode *node)
static void blender::tree_overlap_traverse_self (BVHOverlapData_Thread *data_thread, const BVHNode *node)
static void blender::tree_overlap_invoke_traverse_self (BVHOverlapData_Thread *data_thread, const BVHNode *node)
int blender::BLI_bvhtree_overlap_thread_num (const BVHTree *tree)
static void blender::bvhtree_overlap_task_cb (void *__restrict userdata, const int j, const TaskParallelTLS *__restrict)
BVHTreeOverlap * blender::BLI_bvhtree_overlap_ex (const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
BVHTreeOverlap * blender::BLI_bvhtree_overlap (const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
BVHTreeOverlap * blender::BLI_bvhtree_overlap_self (const BVHTree *tree, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
BLI_bvhtree_intersect_plane
static bool blender::tree_intersect_plane_test (const float *bv, const float plane[4])
static void blender::bvhtree_intersect_plane_dfs_recursive (BVHIntersectPlaneData *__restrict data, const BVHNode *node)
int * blender::BLI_bvhtree_intersect_plane (const BVHTree *tree, float plane[4], uint *r_intersect_num)
BLI_bvhtree_find_nearest
static float blender::calc_nearest_point_squared (const float proj[3], BVHNode *node, float nearest[3])
static void blender::dfs_find_nearest_dfs (BVHNearestData *data, BVHNode *node)
static void blender::dfs_find_nearest_begin (BVHNearestData *data, BVHNode *node)
static void blender::heap_find_nearest_inner (BVHNearestData *data, HeapSimple *heap, BVHNode *node)
static void blender::heap_find_nearest_begin (BVHNearestData *data, BVHNode *root)
int blender::BLI_bvhtree_find_nearest_ex (const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
int blender::BLI_bvhtree_find_nearest (const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
BLI_bvhtree_find_nearest_first
static bool blender::isect_aabb_v3 (BVHNode *node, const float co[3])
static bool blender::dfs_find_duplicate_fast_dfs (BVHNearestData *data, BVHNode *node)
int blender::BLI_bvhtree_find_nearest_first (const BVHTree *tree, const float co[3], 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 blender::ray_nearest_hit (const BVHRayCastData *data, const float bv[6])
static float blender::fast_ray_nearest_hit (const BVHRayCastData *data, const BVHNode *node)
static void blender::dfs_raycast (BVHRayCastData *data, BVHNode *node)
static void blender::dfs_raycast_all (BVHRayCastData *data, BVHNode *node)
static void blender::bvhtree_ray_cast_data_precalc (BVHRayCastData *data, int flag)
int blender::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)
int blender::BLI_bvhtree_ray_cast (const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
float blender::BLI_bvhtree_bb_raycast (const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
void blender::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)
void blender::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)
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.

static void blender::dfs_range_query (RangeQueryData *data, BVHNode *node)
int blender::BLI_bvhtree_range_query (const BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
BLI_bvhtree_nearest_projected
static void blender::bvhtree_nearest_projected_dfs_recursive (BVHNearestProjectedData *__restrict data, const BVHNode *node)
static void blender::bvhtree_nearest_projected_with_clipplane_test_dfs_recursive (BVHNearestProjectedData *__restrict data, const BVHNode *node)
int blender::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)

Variables

static const float blender::bvhtree_kdop_axes_length [13]

Struct Definitions

using blender::axis_t = uchar
 blender::BLI_STATIC_ASSERT ((sizeof(void *)==8 &&sizeof(BVHTree)<=56)||(sizeof(void *)==4 &&sizeof(BVHTree)<=36), "over sized") struct BVHOverlapData_Shared

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:

  • Ray-cast: #BLI_bvhtree_ray_cast, #BVHRayCastData
  • Nearest point on surface: #BLI_bvhtree_find_nearest, #BVHNearestData
  • Overlapping 2 trees: #BLI_bvhtree_overlap, #BVHOverlapData_Shared, #BVHOverlapData_Thread
  • Range Query: #BLI_bvhtree_range_query

Definition in file BLI_kdopbvh.cc.

Macro Definition Documentation

◆ KDOPBVH_THREAD_LEAF_THRESHOLD

#define KDOPBVH_THREAD_LEAF_THRESHOLD   0

◆ MAX_TREETYPE

#define MAX_TREETYPE   32