BVH-tree implementation. More...

#include <algorithm>
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_heap_simple.h"
#include "BLI_kdopbvh.hh"
#include "BLI_math_geom.h"
#include "BLI_math_vector_types.hh"
#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)
Balance Utility Functions
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)
static void	non_recursive_bvh_div_nodes (const BVHTree tree, BVHNode branches_array, BVHNode **leafs_array, int leafs_num)
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)
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_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	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)
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
using	axis_t = uchar
	BLI_STATIC_ASSERT ((sizeof(void )==8 &&sizeof(BVHTree)<=48)\|\|(sizeof(void )==4 &&sizeof(BVHTree)<=32), "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

Definition at line 54 of file BLI_kdopbvh.cc.

Referenced by BLI_bvhtree_overlap_ex(), and non_recursive_bvh_div_nodes().

◆ MAX_TREETYPE

#define MAX_TREETYPE 32

Definition at line 50 of file BLI_kdopbvh.cc.

Referenced by BLI_bvhtree_new(), and non_recursive_bvh_div_nodes_task_cb().

Typedef Documentation

◆ axis_t

using axis_t = uchar

Definition at line 63 of file BLI_kdopbvh.cc.

Function Documentation

◆ BLI_bvhtree_balance()

void BLI_bvhtree_balance ( BVHTree * tree )

Definition at line 932 of file BLI_kdopbvh.cc.

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

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_balance_isolated(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), blender::bke::create_tree_from_edges(), blender::bke::create_tree_from_legacy_faces(), blender::bke::create_tree_from_tris(), blender::bke::create_tree_from_tris(), blender::bke::create_tree_from_verts(), find_nearest_points_test(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), heat_ray_tree_create(), knife_bvh_init(), 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 2021 of file BLI_kdopbvh.cc.

References BVH_RAYCAST_DIST_MAX, copy_v3_v3(), data, 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 1688 of file BLI_kdopbvh.cc.

References BLI_bvhtree_find_nearest_ex(), 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(), blender::ed::transform::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 1639 of file BLI_kdopbvh.cc.

References BVH_NEAREST_OPTIMAL_ORDER, bvhtree_kdop_axes, 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 1755 of file BLI_kdopbvh.cc.

References 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 2307 of file BLI_kdopbvh.cc.

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

Referenced by blender::ed::transform::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 1044 of file BLI_kdopbvh.cc.

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

◆ BLI_bvhtree_get_epsilon()

float BLI_bvhtree_get_epsilon ( const BVHTree * tree )

Definition at line 1039 of file BLI_kdopbvh.cc.

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 1029 of file BLI_kdopbvh.cc.

References tree.

Referenced by 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 1034 of file BLI_kdopbvh.cc.

References tree.

◆ 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 974 of file BLI_kdopbvh.cc.

References BLI_assert, bvhtree_node_inflate(), create_kdop_hull(), BVHNode::index, MEM_allocN_len, and tree.

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(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), blender::bke::create_tree_from_edges(), blender::bke::create_tree_from_legacy_faces(), blender::bke::create_tree_from_tris(), blender::bke::create_tree_from_tris(), blender::bke::create_tree_from_verts(), find_nearest_points_test(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), heat_ray_tree_create(), knife_bvh_init(), 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 1493 of file BLI_kdopbvh.cc.

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_malloc_arrayN(), 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 850 of file BLI_kdopbvh.cc.

References BLI_assert, BLI_assert_unreachable, BLI_bvhtree_free(), i, implicit_needed_branches(), max_ff(), MAX_TREETYPE, MEM_calloc_arrayN(), MEM_callocN(), 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(), blender::bke::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(), 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 1419 of file BLI_kdopbvh.cc.

References BLI_bvhtree_overlap_ex(), BVH_OVERLAP_RETURN_PAIRS, and BVH_OVERLAP_USE_THREADING.

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, allocates *overlap with length of the int return value.

Parameters

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

Definition at line 1315 of file BLI_kdopbvh.cc.

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, bvhtree_overlap_task_cb(), count, data, flag, KDOPBVH_THREAD_LEAF_THRESHOLD, BVHTree::leaf_num, MEM_malloc_arrayN(), min_axis(), TaskParallelSettings::min_iter_per_thread, BVHTree::nodes, 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 1436 of file BLI_kdopbvh.cc.

References BLI_bvhtree_overlap_ex(), BVH_OVERLAP_RETURN_PAIRS, BVH_OVERLAP_SELF, BVH_OVERLAP_USE_THREADING, 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 1286 of file BLI_kdopbvh.cc.

References 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 2147 of file BLI_kdopbvh.cc.

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

Referenced by blender::BLI_bvhtree_range_query_cpp(), 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 2009 of file BLI_kdopbvh.cc.

References BLI_bvhtree_ray_cast_ex(), BVH_RAYCAST_DEFAULT, 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(), blender::ed::transform::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 2082 of file BLI_kdopbvh.cc.

References BLI_bvhtree_ray_cast_all_ex(), BVH_RAYCAST_DEFAULT, and tree.

Referenced by blender::BLI_bvhtree_ray_cast_all_cpp(), blender::ed::transform::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 2048 of file BLI_kdopbvh.cc.

References BLI_assert, BLI_ASSERT_UNIT_V3, bvhtree_ray_cast_data_precalc(), copy_v3_v3(), data, dfs_raycast_all(), flag, 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 1964 of file BLI_kdopbvh.cc.

References BLI_ASSERT_UNIT_V3, BVH_RAYCAST_DIST_MAX, bvhtree_ray_cast_data_precalc(), 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 992 of file BLI_kdopbvh.cc.

References bvhtree_node_inflate(), create_kdop_hull(), 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 1016 of file BLI_kdopbvh.cc.

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 92 of file BLI_kdopbvh.cc.

◆ build_implicit_tree_helper()

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

static

Definition at line 566 of file BLI_kdopbvh.cc.

References data, and tree.

Referenced by non_recursive_bvh_div_nodes().

◆ bvh_insertionsort()

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

static

Insertion sort algorithm

Definition at line 246 of file BLI_kdopbvh.cc.

References BVHNode::bv, and i.

Referenced by partition_nth_element().

◆ bvh_medianof3()

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

static

Definition at line 281 of file BLI_kdopbvh.cc.

Referenced by partition_nth_element().

◆ bvh_partition()

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

static

Definition at line 261 of file BLI_kdopbvh.cc.

References BVHNode::bv, i, SWAP, and x.

Referenced by partition_nth_element().

◆ bvhtree_intersect_plane_dfs_recursive()

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

static

Definition at line 1474 of file BLI_kdopbvh.cc.

References BLI_stack_push_r(), BVHNode::bv, bvhtree_intersect_plane_dfs_recursive(), BVHNode::children, data, BVHNode::index, intersect(), BVHNode::node_num, and tree_intersect_plane_test().

Referenced by BLI_bvhtree_intersect_plane(), and bvhtree_intersect_plane_dfs_recursive().

◆ bvhtree_nearest_projected_dfs_recursive()

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

static

Definition at line 2188 of file BLI_kdopbvh.cc.

References BVHNode::bv, bvhtree_nearest_projected_dfs_recursive(), BVHNode::children, data, dist_squared_to_projected_aabb(), i, BVHNode::index, BVHNode::main_axis, and BVHNode::node_num.

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

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

static

Definition at line 2235 of file BLI_kdopbvh.cc.

References BVHNode::bv, bvhtree_nearest_projected_dfs_recursive(), bvhtree_nearest_projected_with_clipplane_test_dfs_recursive(), BVHNode::children, data, dist_squared_to_projected_aabb(), i, BVHNode::index, ISECT_AABB_PLANE_BEHIND_ANY, ISECT_AABB_PLANE_CROSS_ANY, isect_aabb_planes_v3(), BVHNode::main_axis, and BVHNode::node_num.

Referenced by BLI_bvhtree_find_nearest_projected(), and bvhtree_nearest_projected_with_clipplane_test_dfs_recursive().

◆ bvhtree_node_inflate()

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

static

Definition at line 964 of file BLI_kdopbvh.cc.

References BVHNode::bv, bvhtree_kdop_axes_length, and tree.

Referenced by BLI_bvhtree_insert(), and BLI_bvhtree_update_node().

◆ bvhtree_overlap_task_cb()

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

static

Definition at line 1291 of file BLI_kdopbvh.cc.

References BVHNode::children, data, BVHNode::node_num, tree_overlap_invoke_traverse(), and tree_overlap_invoke_traverse_self().

Referenced by BLI_bvhtree_overlap_ex().

◆ bvhtree_ray_cast_data_precalc()

void bvhtree_ray_cast_data_precalc	(	BVHRayCastData *	data,
		int	flag )

static

Definition at line 1929 of file BLI_kdopbvh.cc.

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

Referenced by BLI_bvhtree_ray_cast_all_ex(), and BLI_bvhtree_ray_cast_ex().

◆ calc_nearest_point_squared()

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

static

Definition at line 1526 of file BLI_kdopbvh.cc.

References BVHNode::bv, i, and 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()

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

References BVHNode::bv, 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()

bool dfs_find_duplicate_fast_dfs	(	BVHNearestData *	data,
		BVHNode *	node )

static

Definition at line 1716 of file BLI_kdopbvh.cc.

References BVHNode::bv, BVHNode::children, data, dfs_find_duplicate_fast_dfs(), i, BVHNode::index, isect_aabb_v3(), BVHNode::main_axis, and BVHNode::node_num.

Referenced by BLI_bvhtree_find_nearest_first(), and dfs_find_duplicate_fast_dfs().

◆ dfs_find_nearest_begin()

void dfs_find_nearest_begin	(	BVHNearestData *	data,
		BVHNode *	node )

static

Definition at line 1583 of file BLI_kdopbvh.cc.

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

Referenced by BLI_bvhtree_find_nearest_ex().

◆ dfs_find_nearest_dfs()

void dfs_find_nearest_dfs	(	BVHNearestData *	data,
		BVHNode *	node )

static

Definition at line 1543 of file BLI_kdopbvh.cc.

References BVHNode::bv, calc_nearest_point_squared(), BVHNode::children, data, dfs_find_nearest_dfs(), i, BVHNode::index, BVHNode::main_axis, and BVHNode::node_num.

Referenced by dfs_find_nearest_begin(), and dfs_find_nearest_dfs().

◆ dfs_range_query()

void dfs_range_query	(	RangeQueryData *	data,
		BVHNode *	node )

static

Definition at line 2116 of file BLI_kdopbvh.cc.

References BVHNode::bv, calc_nearest_point_squared(), BVHNode::children, data, dfs_range_query(), i, BVHNode::index, and BVHNode::node_num.

Referenced by BLI_bvhtree_range_query(), and dfs_range_query().

◆ dfs_raycast()

void dfs_raycast	(	BVHRayCastData *	data,
		BVHNode *	node )

static

Definition at line 1853 of file BLI_kdopbvh.cc.

References BVHNode::bv, BVHNode::children, data, dfs_raycast(), fast_ray_nearest_hit(), i, BVHNode::index, madd_v3_v3v3fl(), BVHNode::main_axis, BVHNode::node_num, and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_ex(), and dfs_raycast().

◆ dfs_raycast_all()

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 1894 of file BLI_kdopbvh.cc.

References BVHNode::bv, BVHNode::children, data, dfs_raycast_all(), fast_ray_nearest_hit(), i, BVHNode::index, BVHNode::main_axis, BVHNode::node_num, and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_all_ex(), and dfs_raycast_all().

◆ fast_ray_nearest_hit()

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 1833 of file BLI_kdopbvh.cc.

References BVHNode::bv, data, FLT_MAX, and max_fff().

Referenced by dfs_raycast(), and dfs_raycast_all().

◆ get_largest_axis()

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 399 of file BLI_kdopbvh.cc.

Referenced by non_recursive_bvh_div_nodes(), and non_recursive_bvh_div_nodes_task_cb().

◆ heap_find_nearest_begin()

void heap_find_nearest_begin	(	BVHNearestData *	data,
		BVHNode *	root )

static

Definition at line 1618 of file BLI_kdopbvh.cc.

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

Referenced by BLI_bvhtree_find_nearest_ex().

◆ heap_find_nearest_inner()

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

static

Definition at line 1594 of file BLI_kdopbvh.cc.

References BLI_heapsimple_insert(), calc_nearest_point_squared(), BVHNode::children, data, i, BVHNode::index, and BVHNode::node_num.

Referenced by heap_find_nearest_begin().

◆ implicit_leafs_index()

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 597 of file BLI_kdopbvh.cc.

References data.

Referenced by non_recursive_bvh_div_nodes_task_cb().

◆ implicit_needed_branches()

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 math (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 640 of file BLI_kdopbvh.cc.

References max_ii().

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

◆ isect_aabb_v3()

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

static

Definition at line 1703 of file BLI_kdopbvh.cc.

References BVHNode::bv, max, and 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.cc.

References b, and MINLINE.

Referenced by BLI_bvhtree_overlap_ex(), and BM_face_split_edgenet_connect_islands().

◆ node_join()

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 422 of file BLI_kdopbvh.cc.

References BVHNode::bv, BVHNode::children, i, node_minmax_init(), and tree.

Referenced by BLI_bvhtree_update_tree().

◆ node_minmax_init()

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

References BVHNode::bv, float, FLT_MAX, and tree.

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

◆ non_recursive_bvh_div_nodes()

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 nullptr 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 771 of file BLI_kdopbvh.cc.

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

Referenced by BLI_bvhtree_balance().

◆ non_recursive_bvh_div_nodes_task_cb()

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

static

Definition at line 687 of file BLI_kdopbvh.cc.

References BVHNode::bv, BVHNode::children, data, get_largest_axis(), 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()

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

References begin(), bvh_insertionsort(), bvh_medianof3(), and bvh_partition().

Referenced by split_leafs().

◆ ray_nearest_hit()

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

static

Definition at line 1791 of file BLI_kdopbvh.cc.

References data, FLT_MAX, and i.

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

◆ refit_kdop_hull()

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 372 of file BLI_kdopbvh.cc.

References BVHNode::bv, node_minmax_init(), and tree.

Referenced by non_recursive_bvh_div_nodes(), and non_recursive_bvh_div_nodes_task_cb().

◆ split_leafs()

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 657 of file BLI_kdopbvh.cc.

References i, and partition_nth_element().

Referenced by non_recursive_bvh_div_nodes_task_cb().

◆ tree_intersect_plane_test()

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

static

Definition at line 1459 of file BLI_kdopbvh.cc.

References aabb_get_near_far_from_plane(), and plane_point_side_v3().

Referenced by bvhtree_intersect_plane_dfs_recursive().

◆ tree_overlap_invoke_traverse()

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 1231 of file BLI_kdopbvh.cc.

References data, 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()

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

static

Calls the appropriate recursive self-overlap traversal.

Definition at line 1275 of file BLI_kdopbvh.cc.

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

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 1069 of file BLI_kdopbvh.cc.

References BVHNode::bv.

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

◆ tree_overlap_traverse()

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

static

Definition at line 1088 of file BLI_kdopbvh.cc.

References BLI_stack_push_r(), BVHNode::children, data, 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()

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 1132 of file BLI_kdopbvh.cc.

References BLI_stack_push_r(), BVHNode::children, data, 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()

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 1179 of file BLI_kdopbvh.cc.

References BLI_stack_push_r(), BVHNode::children, data, 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()

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

static

Self-overlap traversal without callback.

Definition at line 1261 of file BLI_kdopbvh.cc.

References BVHNode::children, i, BVHNode::node_num, 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()

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

static

Self-overlap traversal with callback.

Definition at line 1247 of file BLI_kdopbvh.cc.

References BVHNode::children, i, BVHNode::node_num, 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

◆ 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.cc.

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

Referenced by bvhtree_node_inflate().

Classes

Macros

Functions

Variables

Struct Definitions

Detailed Description

Macro Definition Documentation

◆ KDOPBVH_THREAD_LEAF_THRESHOLD

◆ MAX_TREETYPE

Typedef Documentation

◆ axis_t

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

◆ ray_nearest_hit()

◆ refit_kdop_hull()

◆ split_leafs()

◆ tree_intersect_plane_test()

◆ tree_overlap_invoke_traverse()

◆ tree_overlap_invoke_traverse_self()

◆ tree_overlap_test()

◆ tree_overlap_traverse()

◆ tree_overlap_traverse_cb()

◆ tree_overlap_traverse_num()

◆ tree_overlap_traverse_self()