BVH-tree implementation. More...

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

Classes
class	BVHNode

struct	BVHTree

struct	BVHOverlapData_Thread

struct	BVHNearestData

struct	BVHRayCastData

struct	BVHNearestProjectedData

struct	BVHIntersectPlaneData

struct	BVHBuildHelper

struct	BVHDivNodesData

struct	RangeQueryData

Macros
#define	MAX_TREETYPE 32

#define	KDOPBVH_THREAD_LEAF_THRESHOLD 0

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
BVHTree *	BLI_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 (const 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)

static void	tree_overlap_invoke_traverse (BVHOverlapData_Thread data, const BVHNode node1, const BVHNode *node2)

static void	tree_overlap_traverse_self_cb (BVHOverlapData_Thread data_thread, const BVHNode node)

static void	tree_overlap_traverse_self (BVHOverlapData_Thread data_thread, const BVHNode node)

static void	tree_overlap_invoke_traverse_self (BVHOverlapData_Thread data_thread, const BVHNode node)

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

BVHTreeOverlap *	BLI_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)

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

BVHTreeOverlap *	BLI_bvhtree_overlap_self (const BVHTree tree, 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 (const 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 (const BVHTree tree, const float co[3], BVHTreeNearest nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)

int	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	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 (const 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 (const 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 (const 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 (const 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 (const 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 (const BVHTree tree, float projmat[4][4], float winsize[2], float mval[2], float(clip_plane)[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 uchar	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, const BVHNode x, int axis)

static BVHNode *	bvh_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 (const BVHTree tree, const float co[3], float radius, BVHTree_RangeQuery callback, 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:

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.c.

Macro Definition Documentation

◆ KDOPBVH_THREAD_LEAF_THRESHOLD

#define KDOPBVH_THREAD_LEAF_THRESHOLD 0

Definition at line 53 of file BLI_kdopbvh.c.

Referenced by BLI_bvhtree_overlap_ex(), and non_recursive_bvh_div_nodes().

◆ MAX_TREETYPE

#define MAX_TREETYPE 32

Definition at line 47 of file BLI_kdopbvh.c.

Referenced by BLI_bvhtree_new(), and non_recursive_bvh_div_nodes_task_cb().

Typedef Documentation

◆ axis_t

typedef uchar axis_t

Definition at line 62 of file BLI_kdopbvh.c.

◆ BVHBuildHelper

typedef struct BVHBuildHelper BVHBuildHelper

◆ BVHDivNodesData

typedef struct BVHDivNodesData BVHDivNodesData

◆ BVHIntersectPlaneData

typedef struct BVHIntersectPlaneData BVHIntersectPlaneData

◆ BVHNearestData

typedef struct BVHNearestData BVHNearestData

◆ BVHNearestProjectedData

typedef struct BVHNearestProjectedData BVHNearestProjectedData

◆ BVHNode

typedef struct BVHNode BVHNode

◆ BVHOverlapData_Thread

typedef struct BVHOverlapData_Thread BVHOverlapData_Thread

◆ BVHRayCastData

typedef struct BVHRayCastData BVHRayCastData

◆ RangeQueryData

typedef struct RangeQueryData RangeQueryData

Function Documentation

◆ BLI_bvhtree_balance()

void BLI_bvhtree_balance ( BVHTree * tree )

Definition at line 946 of file BLI_kdopbvh.c.

References BLI_assert, implicit_needed_branches(), non_recursive_bvh_div_nodes(), NULL, and tree.

Referenced by BKE_bmbvh_new_ex(), BKE_bvhtree_from_mesh_edges_init(), BKE_bvhtree_from_mesh_tris_init(), BKE_bvhtree_from_mesh_verts_init(), BKE_bvhtree_from_pointcloud_get(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), blender::ed::greasepencil::build_curves_2d_bvh_from_visible(), bvhtree_balance(), bvhtree_balance_isolated(), bvhtree_balance_isolated(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), find_nearest_points_test(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), heat_ray_tree_create(), knife_bvh_init(), pointdensity_cache_object(), pointdensity_cache_psys(), TEST(), TEST(), and uv_select_overlap().

◆ 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] )

Definition at line 2047 of file BLI_kdopbvh.c.

References BVH_RAYCAST_DIST_MAX, copy_v3_v3(), data, BVHTreeRayHit::dist, BVHRayCastData::hit, madd_v3_v3v3fl(), normalize_v3(), pos, ray_nearest_hit(), and sub_v3_v3v3().

◆ BLI_bvhtree_find_nearest()

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

Definition at line 1706 of file BLI_kdopbvh.c.

References BLI_bvhtree_find_nearest_ex(), callback, and tree.

Referenced by BKE_bmbvh_find_face_closest(), BKE_bmbvh_find_vert_closest(), BKE_shrinkwrap_find_nearest_surface(), blender::nodes::node_geo_proximity_cc::ProximityFunction::call(), blender::nodes::node_geo_sample_nearest_surface_cc::SampleNearestSurfaceFunction::call(), closest_point_on_surface(), dynamic_paint_paint_mesh_cell_point_cb_ex(), blender::bke::find_nearest_tris(), blender::nodes::get_closest_in_bvhtree(), blender::nodes::node_geo_sample_nearest_cc::get_closest_pointcloud_points(), mesh_remap_bvhtree_query_nearest(), nearest_world_tree_co(), nearestVert(), blender::ed::sculpt_paint::PuffOperationExecutor::puff(), py_bvhtree_find_nearest(), remap_hair_emitter(), shrinkwrap_calc_nearest_vertex_cb_ex(), blender::ed::curves::convert_to_particle_system::try_convert_single_object(), and vert2geom_task_cb_ex().

◆ BLI_bvhtree_find_nearest_ex()

int BLI_bvhtree_find_nearest_ex	(	const 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 1657 of file BLI_kdopbvh.c.

References BVH_NEAREST_OPTIMAL_ORDER, bvhtree_kdop_axes, callback, data, dfs_find_nearest_begin(), dot_v3v3(), flag, FLT_MAX, 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	(	const 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 1773 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	(	const BVHTree *	tree,
		float	projmat[4][4],
		float	winsize[2],
		float	mval[2],
		float(*)	clip_plane[4],
		int	clip_plane_len,
		BVHTreeNearest *	nearest,
		BVHTree_NearestProjectedCallback	callback,
		void *	userdata )

Definition at line 2333 of file BLI_kdopbvh.c.

References BVHNode::bv, bvhtree_nearest_projected_dfs_recursive(), bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(), callback, copy_v4_v4(), dist_squared_to_projected_aabb(), dist_squared_to_projected_aabb_precalc(), FLT_MAX, isect_aabb_planes_v3(), max_ii(), NULL, planes_from_projmat(), and tree.

Referenced by snapMesh().

◆ BLI_bvhtree_free()

void BLI_bvhtree_free ( BVHTree * tree )

◆ BLI_bvhtree_get_bounding_box()

void BLI_bvhtree_get_bounding_box	(	const 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 1058 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 )

Definition at line 1053 of file BLI_kdopbvh.c.

References tree.

Referenced by BKE_bmbvh_overlap(), BKE_bmbvh_overlap_self(), cloth_collision(), cloth_collision_response_static(), deform_verts(), hair_collision(), and blender::draw::statvis_calc_intersect().

◆ BLI_bvhtree_get_len()

int BLI_bvhtree_get_len ( const BVHTree * tree )

Number of times BLI_bvhtree_insert has been called. mainly useful for asserts functions to check we added the correct number.

Definition at line 1043 of file BLI_kdopbvh.c.

References tree.

Referenced by bvhtree_from_mesh_corner_tris_create_tree(), bvhtree_from_mesh_faces_create_tree(), bvhtree_from_mesh_verts_create_tree(), TEST(), and TEST().

◆ 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 1048 of file BLI_kdopbvh.c.

References tree.

Referenced by BKE_bvhtree_from_mesh_get().

◆ BLI_bvhtree_insert()

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

Construct: first insert points, then call balance.

Definition at line 988 of file BLI_kdopbvh.c.

References BLI_assert, bvhtree_node_inflate(), create_kdop_hull(), MEM_allocN_len, NULL, and tree.

Referenced by BKE_bmbvh_new_ex(), BKE_bvhtree_from_mesh_edges_init(), BKE_bvhtree_from_mesh_tris_init(), BKE_bvhtree_from_mesh_verts_init(), BKE_bvhtree_from_pointcloud_get(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), blender::ed::greasepencil::build_curves_2d_bvh_from_visible(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), bvhtree_from_mesh_corner_tris_create_tree(), bvhtree_from_mesh_edges_create_tree(), bvhtree_from_mesh_faces_create_tree(), bvhtree_from_mesh_verts_create_tree(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), find_nearest_points_test(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), heat_ray_tree_create(), knife_bvh_init(), pointdensity_cache_object(), pointdensity_cache_psys(), psys_update_particle_bvhtree(), TEST(), and uv_select_overlap().

◆ BLI_bvhtree_intersect_plane()

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

Definition at line 1507 of file BLI_kdopbvh.c.

References BLI_stack_count(), BLI_stack_free(), BLI_stack_new, BLI_stack_pop_n(), bvhtree_intersect_plane_dfs_recursive(), copy_v4_v4(), data, intersect(), MEM_mallocN, NULL, BVHIntersectPlaneData::tree, and tree.

Referenced by knife_find_line_hits().

◆ BLI_bvhtree_new()

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

Note: many callers don't check for NULL return.

Definition at line 863 of file BLI_kdopbvh.c.

References BLI_assert, BLI_assert_unreachable, BLI_bvhtree_free(), implicit_needed_branches(), max_ff(), MAX_TREETYPE, MEM_callocN, NULL, tree, and UNLIKELY.

Referenced by BKE_bmbvh_new_ex(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), blender::ed::greasepencil::build_curves_2d_bvh_from_visible(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), bvhtree_new_common(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), find_nearest_points_test(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), heat_ray_tree_create(), knife_bvh_init(), pointdensity_cache_object(), pointdensity_cache_psys(), psys_update_particle_bvhtree(), TEST(), TEST(), and uv_select_overlap().

◆ BLI_bvhtree_overlap()

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

Definition at line 1433 of file BLI_kdopbvh.c.

References BLI_bvhtree_overlap_ex(), BVH_OVERLAP_RETURN_PAIRS, BVH_OVERLAP_USE_THREADING, and callback.

Referenced by BKE_bmbvh_overlap(), BKE_bmbvh_overlap_self(), cloth_bvh_collision(), and py_bvhtree_overlap().

◆ 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 )

Collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value.

Parameters

callback optional, to test the overlap before adding (must be thread-safe!).

Definition at line 1329 of file BLI_kdopbvh.c.

References BVHTree::axis, BLI_array_alloca, BLI_assert, BLI_bvhtree_overlap_thread_num(), BLI_parallel_range_settings_defaults(), BLI_stack_count(), BLI_stack_free(), BLI_stack_new, BLI_stack_pop_n(), BLI_task_parallel_range(), BVH_OVERLAP_RETURN_PAIRS, BVH_OVERLAP_SELF, BVH_OVERLAP_USE_THREADING, BVHOverlapData_Shared, bvhtree_overlap_task_cb(), callback, count, flag, KDOPBVH_THREAD_LEAF_THRESHOLD, BVHTree::leaf_num, MEM_mallocN, min_axis(), BVHTree::nodes, NULL, BVHTree::start_axis, BVHTree::stop_axis, tree_overlap_invoke_traverse(), tree_overlap_invoke_traverse_self(), tree_overlap_test(), and UNLIKELY.

Referenced by BLI_bvhtree_overlap(), BLI_bvhtree_overlap_self(), bm_elemxelem_bvhtree_overlap(), and BM_mesh_intersect().

◆ BLI_bvhtree_overlap_self()

BVHTreeOverlap * BLI_bvhtree_overlap_self	(	const BVHTree *	tree,
		unsigned int *	r_overlap_num,
		BVHTree_OverlapCallback	callback,
		void *	userdata )

Compute overlaps of the tree with itself. This is faster than BLI_bvhtree_overlap because it only tests and returns each symmetrical pair once.

Definition at line 1450 of file BLI_kdopbvh.c.

References BLI_bvhtree_overlap_ex(), BVH_OVERLAP_RETURN_PAIRS, BVH_OVERLAP_SELF, BVH_OVERLAP_USE_THREADING, callback, and tree.

Referenced by cloth_bvh_collision(), blender::draw::statvis_calc_intersect(), and uv_select_overlap().

◆ 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 1300 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	(	const BVHTree *	tree,
		const float	co[3],
		float	radius,
		BVHTree_RangeQuery	callback,
		void *	userdata )

Range query.

Definition at line 2173 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), callback, data, dfs_range_query(), BVHNode::index, BVHNode::node_num, NULL, RangeQueryData::tree, and tree.

Referenced by pointdensity(), py_bvhtree_find_nearest_range(), and sph_evaluate_func().

◆ BLI_bvhtree_ray_cast()

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

Definition at line 2035 of file BLI_kdopbvh.c.

References BLI_bvhtree_ray_cast_ex(), BVH_RAYCAST_DEFAULT, callback, and tree.

Referenced by BKE_bmbvh_ray_cast(), BKE_bmbvh_ray_cast_filter(), BKE_shrinkwrap_project_normal(), cast_ray_highpoly(), dynamic_paint_paint_mesh_cell_point_cb_ex(), blender::ed::greasepencil::find_curve_intersections(), find_internal_spring_target_vertex(), followtrack_project_to_depth_object_if_needed(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), heat_ray_source_visible(), imapaint_pick_face(), isect_bvhtree_point_v3(), knife_bvh_raycast(), mesh_remap_bvhtree_query_raycast(), blender::ed::sculpt_paint::min_distance_edit::min_distance_edit_invoke(), py_bvhtree_ray_cast(), blender::nodes::node_geo_raycast_cc::raycast_to_mesh(), raycastMesh(), blender::ed::sculpt_paint::sample_curves_3d_brush(), blender::ed::sculpt_paint::sample_curves_surface_3d_brush(), blender::ed::sculpt_paint::AddOperationExecutor::sample_in_center(), blender::bke::mesh_surface_sample::sample_surface_points_projected(), shape_cut(), blender::geometry::curve_constraints::solve_length_and_collision_constraints(), and blender::draw::statvis_calc_thickness().

◆ BLI_bvhtree_ray_cast_all()

void 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 )

Definition at line 2108 of file BLI_kdopbvh.c.

References BLI_bvhtree_ray_cast_all_ex(), BVH_RAYCAST_DEFAULT, callback, and tree.

Referenced by raycastMesh(), and shape_cut_test_point().

◆ BLI_bvhtree_ray_cast_all_ex()

void 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 )

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 2074 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(), flag, NULL, and tree.

Referenced by BLI_bvhtree_ray_cast_all().

◆ BLI_bvhtree_ray_cast_ex()

int 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 )

Definition at line 1990 of file BLI_kdopbvh.c.

References BLI_ASSERT_UNIT_V3, BVH_RAYCAST_DIST_MAX, bvhtree_ray_cast_data_precalc(), callback, copy_v3_v3(), data, dfs_raycast(), flag, and tree.

Referenced by BLI_bvhtree_ray_cast(), boid_find_ground(), blender::ed::sculpt_paint::cloth::cloth_brush_solve_collision(), collision_detect(), eff_calc_visibility(), meshdeform_ray_tree_intersect(), rule_avoid_collision(), test_edges_isect_2d_ray(), and test_edges_isect_2d_vert().

◆ 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 1006 of file BLI_kdopbvh.c.

References bvhtree_node_inflate(), create_kdop_hull(), 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.

Note that this does not rebalance the tree, so if the shape of the mesh changes too much, operations on the tree may become suboptimal.

Definition at line 1030 of file BLI_kdopbvh.c.

References node_join(), and tree.

Referenced by bvhtree_update_from_cloth(), and bvhtree_update_from_mvert().

◆ BLI_STATIC_ASSERT()

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

Definition at line 91 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 578 of file BLI_kdopbvh.c.

References BVHBuildHelper::leafs_num, 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 246 of file BLI_kdopbvh.c.

References BVHNode::bv.

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 281 of file BLI_kdopbvh.c.

Referenced by partition_nth_element().

◆ bvh_partition()

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

static

Definition at line 261 of file BLI_kdopbvh.c.

References SWAP.

Referenced by partition_nth_element().

◆ bvhtree_intersect_plane_dfs_recursive()

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

static

Definition at line 1488 of file BLI_kdopbvh.c.

References BLI_stack_push_r(), bvhtree_intersect_plane_dfs_recursive(), intersect(), and tree_intersect_plane_test().

Referenced by BLI_bvhtree_intersect_plane(), and bvhtree_intersect_plane_dfs_recursive().

◆ bvhtree_nearest_projected_dfs_recursive()

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

static

Definition at line 2214 of file BLI_kdopbvh.c.

References bvhtree_nearest_projected_dfs_recursive(), dist_squared_to_projected_aabb(), and NULL.

Referenced by BLI_bvhtree_find_nearest_projected(), bvhtree_nearest_projected_dfs_recursive(), and bvhtree_nearest_projected_with_clipplane_test_dfs_recursive().

◆ 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

Definition at line 2261 of file BLI_kdopbvh.c.

References bvhtree_nearest_projected_dfs_recursive(), bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(), dist_squared_to_projected_aabb(), ISECT_AABB_PLANE_BEHIND_ANY, ISECT_AABB_PLANE_CROSS_ANY, and isect_aabb_planes_v3().

Referenced by BLI_bvhtree_find_nearest_projected(), and bvhtree_nearest_projected_with_clipplane_test_dfs_recursive().

◆ bvhtree_node_inflate()

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

static

Definition at line 978 of file BLI_kdopbvh.c.

References bvhtree_kdop_axes_length, 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

Definition at line 1305 of file BLI_kdopbvh.c.

References BVHOverlapData_Shared, BVHNode::children, BVHNode::node_num, BVHOverlapData_Thread::shared, tree_overlap_invoke_traverse(), and tree_overlap_invoke_traverse_self().

Referenced by BLI_bvhtree_overlap_ex().

◆ bvhtree_ray_cast_data_precalc()

static void bvhtree_ray_cast_data_precalc	(	BVHRayCastData *	data,
		int	flag )

static

Definition at line 1955 of file BLI_kdopbvh.c.

References BVH_RAYCAST_WATERTIGHT, bvhtree_kdop_axes, dot_v3v3(), fabsf, flag, FLT_MAX, isect_ray_tri_watertight_v3_precalc(), NULL, and UNUSED_VARS.

Referenced by BLI_bvhtree_ray_cast_all_ex(), and BLI_bvhtree_ray_cast_ex().

◆ calc_nearest_point_squared()

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

static

Definition at line 1540 of file BLI_kdopbvh.c.

References len_squared_v3v3().

Referenced by BLI_bvhtree_range_query(), dfs_find_nearest_begin(), dfs_find_nearest_dfs(), dfs_range_query(), heap_find_nearest_begin(), and heap_find_nearest_inner().

◆ create_kdop_hull()

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

static

Definition at line 346 of file BLI_kdopbvh.c.

References bvhtree_kdop_axes, dot_v3v3(), 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 1734 of file BLI_kdopbvh.c.

References dfs_find_duplicate_fast_dfs(), and isect_aabb_v3().

Referenced by BLI_bvhtree_find_nearest_first(), and dfs_find_duplicate_fast_dfs().

◆ dfs_find_nearest_begin()

static void dfs_find_nearest_begin	(	BVHNearestData *	data,
		BVHNode *	node )

static

Definition at line 1601 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), and dfs_find_nearest_dfs().

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 1561 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), and dfs_find_nearest_dfs().

Referenced by dfs_find_nearest_begin(), and dfs_find_nearest_dfs().

◆ dfs_range_query()

static void dfs_range_query	(	RangeQueryData *	data,
		BVHNode *	node )

static

Definition at line 2142 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), and dfs_range_query().

Referenced by BLI_bvhtree_range_query(), and dfs_range_query().

◆ dfs_raycast()

static void dfs_raycast	(	BVHRayCastData *	data,
		BVHNode *	node )

static

Definition at line 1879 of file BLI_kdopbvh.c.

References dfs_raycast(), fast_ray_nearest_hit(), madd_v3_v3v3fl(), and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_ex(), and dfs_raycast().

◆ 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 1920 of file BLI_kdopbvh.c.

References dfs_raycast_all(), fast_ray_nearest_hit(), and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_all_ex(), and dfs_raycast_all().

◆ 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 1859 of file BLI_kdopbvh.c.

References FLT_MAX, and max_fff().

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 407 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

Definition at line 1636 of file BLI_kdopbvh.c.

References BLI_heapsimple_free(), BLI_heapsimple_is_empty(), BLI_heapsimple_new_ex(), BLI_heapsimple_pop_min(), BLI_heapsimple_top_value(), calc_nearest_point_squared(), heap_find_nearest_inner(), and NULL.

Referenced by BLI_bvhtree_find_nearest_ex().

◆ heap_find_nearest_inner()

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

static

Definition at line 1612 of file BLI_kdopbvh.c.

References BLI_heapsimple_insert(), and calc_nearest_point_squared().

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 609 of file BLI_kdopbvh.c.

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 652 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 1721 of file BLI_kdopbvh.c.

References min.

Referenced by dfs_find_duplicate_fast_dfs().

◆ min_axis()

MINLINE axis_t min_axis	(	axis_t	a,
		axis_t	b )

Definition at line 208 of file BLI_kdopbvh.c.

References 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 430 of file BLI_kdopbvh.c.

References 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 226 of file BLI_kdopbvh.c.

References float, FLT_MAX, 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 783 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, and tree.

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

Definition at line 699 of file BLI_kdopbvh.c.

References BVHNode::bv, BVHNode::children, get_largest_axis(), BVHDivNodesData::i, implicit_leafs_index(), BVHNode::main_axis, MAX_TREETYPE, BVHNode::node_num, BVHNode::parent, refit_kdop_hull(), and split_leafs().

Referenced by non_recursive_bvh_div_nodes().

◆ 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 307 of file BLI_kdopbvh.c.

References 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 1809 of file BLI_kdopbvh.c.

References FLT_MAX.

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 376 of file BLI_kdopbvh.c.

References 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 669 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

Definition at line 1473 of file BLI_kdopbvh.c.

References aabb_get_near_far_from_plane(), and plane_point_side_v3().

Referenced by bvhtree_intersect_plane_dfs_recursive().

◆ tree_overlap_invoke_traverse()

static void tree_overlap_invoke_traverse	(	BVHOverlapData_Thread *	data,
		const BVHNode *	node1,
		const BVHNode *	node2 )

static

Calls the appropriate recursive overlap traversal function.

Definition at line 1245 of file BLI_kdopbvh.c.

References tree_overlap_traverse(), tree_overlap_traverse_cb(), and tree_overlap_traverse_num().

Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_cb().

◆ tree_overlap_invoke_traverse_self()

static void tree_overlap_invoke_traverse_self	(	BVHOverlapData_Thread *	data_thread,
		const BVHNode *	node )

static

Calls the appropriate recursive self-overlap traversal.

Definition at line 1289 of file BLI_kdopbvh.c.

References BVHOverlapData_Thread::shared, tree_overlap_traverse_self(), and tree_overlap_traverse_self_cb().

Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_cb().

◆ 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 1083 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

Definition at line 1102 of file BLI_kdopbvh.c.

References BLI_stack_push_r(), BVHOverlapData_Shared, BVHNode::children, BVHNode::index, BVHTreeOverlap::indexA, BVHTreeOverlap::indexB, BVHNode::node_num, BVHOverlapData_Thread::overlap, BVHOverlapData_Thread::shared, tree_overlap_test(), tree_overlap_traverse(), and UNLIKELY.

Referenced by tree_overlap_invoke_traverse(), tree_overlap_traverse(), and tree_overlap_traverse_self().

◆ tree_overlap_traverse_cb()

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

static

a version of tree_overlap_traverse that runs a callback to check if the nodes really intersect.

Definition at line 1146 of file BLI_kdopbvh.c.

References BLI_stack_push_r(), BVHOverlapData_Shared, BVHNode::children, BVHNode::index, BVHTreeOverlap::indexA, BVHTreeOverlap::indexB, BVHNode::node_num, BVHOverlapData_Thread::overlap, BVHOverlapData_Thread::shared, BVHOverlapData_Thread::thread, tree_overlap_test(), tree_overlap_traverse_cb(), and UNLIKELY.

Referenced by tree_overlap_invoke_traverse(), tree_overlap_traverse_cb(), and tree_overlap_traverse_self_cb().

◆ tree_overlap_traverse_num()

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

static

a version of tree_overlap_traverse_cb that break on first true return.

Definition at line 1193 of file BLI_kdopbvh.c.

References BLI_stack_push_r(), BVHOverlapData_Shared, BVHNode::children, BVHNode::index, BVHTreeOverlap::indexA, BVHTreeOverlap::indexB, BVHOverlapData_Thread::max_interactions, BVHNode::node_num, BVHOverlapData_Thread::overlap, BVHOverlapData_Thread::shared, BVHOverlapData_Thread::thread, tree_overlap_test(), tree_overlap_traverse_num(), and UNLIKELY.

Referenced by tree_overlap_invoke_traverse(), and tree_overlap_traverse_num().

◆ tree_overlap_traverse_self()

static void tree_overlap_traverse_self	(	BVHOverlapData_Thread *	data_thread,
		const BVHNode *	node )

static

Self-overlap traversal without callback.

Definition at line 1275 of file BLI_kdopbvh.c.

References tree_overlap_traverse(), and tree_overlap_traverse_self().

Referenced by tree_overlap_invoke_traverse_self(), and tree_overlap_traverse_self().

◆ tree_overlap_traverse_self_cb()

static void tree_overlap_traverse_self_cb	(	BVHOverlapData_Thread *	data_thread,
		const BVHNode *	node )

static

Self-overlap traversal with callback.

Definition at line 1261 of file BLI_kdopbvh.c.

References tree_overlap_traverse_cb(), and tree_overlap_traverse_self_cb().

Referenced by tree_overlap_invoke_traverse_self(), and tree_overlap_traverse_self_cb().

Variable Documentation

◆ BVHOverlapData_Shared

BVHOverlapData_Shared

Definition at line 104 of file BLI_kdopbvh.c.

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

◆ 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 171 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:

= {
0f,
0f,
0f,
7320508075688772f,
7320508075688772f,
7320508075688772f,
7320508075688772f,
4142135623730951f,
4142135623730951f,
4142135623730951f,
4142135623730951f,
4142135623730951f,
4142135623730951f,
}

Definition at line 188 of file BLI_kdopbvh.c.

Referenced by bvhtree_node_inflate().

Classes

Macros

Functions

Variables

Struct Definitions

Balance Utility Functions

BLI_bvhtree_range_query

Detailed Description

Macro Definition Documentation

◆ KDOPBVH_THREAD_LEAF_THRESHOLD

◆ MAX_TREETYPE

Typedef Documentation

◆ axis_t

◆ BVHBuildHelper

◆ BVHDivNodesData

◆ BVHIntersectPlaneData

◆ BVHNearestData

◆ BVHNearestProjectedData

◆ BVHNode

◆ BVHOverlapData_Thread

◆ BVHRayCastData

◆ RangeQueryData

Function Documentation

◆ BLI_bvhtree_balance()

◆ BLI_bvhtree_bb_raycast()

◆ BLI_bvhtree_find_nearest()

◆ BLI_bvhtree_find_nearest_ex()

◆ BLI_bvhtree_find_nearest_first()

◆ BLI_bvhtree_find_nearest_projected()

◆ BLI_bvhtree_free()

◆ BLI_bvhtree_get_bounding_box()

◆ BLI_bvhtree_get_epsilon()

◆ BLI_bvhtree_get_len()

◆ BLI_bvhtree_get_tree_type()

◆ BLI_bvhtree_insert()

◆ BLI_bvhtree_intersect_plane()

◆ BLI_bvhtree_new()

◆ BLI_bvhtree_overlap()

◆ BLI_bvhtree_overlap_ex()

◆ BLI_bvhtree_overlap_self()

◆ BLI_bvhtree_overlap_thread_num()

◆ BLI_bvhtree_range_query()

◆ BLI_bvhtree_ray_cast()

◆ BLI_bvhtree_ray_cast_all()

◆ BLI_bvhtree_ray_cast_all_ex()

◆ BLI_bvhtree_ray_cast_ex()

◆ BLI_bvhtree_update_node()

◆ BLI_bvhtree_update_tree()

◆ BLI_STATIC_ASSERT()

◆ build_implicit_tree_helper()

◆ bvh_insertionsort()

◆ bvh_medianof3()

◆ bvh_partition()

◆ bvhtree_intersect_plane_dfs_recursive()

◆ bvhtree_nearest_projected_dfs_recursive()

◆ bvhtree_nearest_projected_with_clipplane_test_dfs_recursive()

◆ bvhtree_node_inflate()

◆ bvhtree_overlap_task_cb()

◆ bvhtree_ray_cast_data_precalc()

◆ calc_nearest_point_squared()

◆ create_kdop_hull()

◆ dfs_find_duplicate_fast_dfs()

◆ dfs_find_nearest_begin()

◆ dfs_find_nearest_dfs()

◆ dfs_range_query()

◆ dfs_raycast()

◆ dfs_raycast_all()

◆ fast_ray_nearest_hit()

◆ get_largest_axis()

◆ heap_find_nearest_begin()

◆ heap_find_nearest_inner()

◆ implicit_leafs_index()

◆ implicit_needed_branches()

◆ isect_aabb_v3()

◆ min_axis()

◆ node_join()

◆ node_minmax_init()

◆ non_recursive_bvh_div_nodes()

◆ non_recursive_bvh_div_nodes_task_cb()

◆ partition_nth_element()