|
Blender V5.3
|
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 | |
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.cc.
| #define KDOPBVH_THREAD_LEAF_THRESHOLD 0 |
Definition at line 56 of file BLI_kdopbvh.cc.
Referenced by blender::BLI_bvhtree_overlap_ex(), and blender::non_recursive_bvh_div_nodes().
| #define MAX_TREETYPE 32 |
Definition at line 52 of file BLI_kdopbvh.cc.
Referenced by blender::BLI_bvhtree_new(), and blender::non_recursive_bvh_div_nodes_task_cb().