BLI_kdopbvh.hh File Reference

#include "BLI_function_ref.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_sys_types.h"

Go to the source code of this file.

Classes
struct	BVHTreeAxisRange
struct	BVHTreeOverlap
struct	BVHTreeNearest
struct	BVHTreeRay
struct	BVHTreeRayHit
class	BVHTreeDeleter

Namespaces
namespace	blender

Macros
#define	USE_KDOPBVH_WATERTIGHT
#define	BVH_RAYCAST_DEFAULT   (BVH_RAYCAST_WATERTIGHT)
#define	BVH_RAYCAST_DIST_MAX   (FLT_MAX / 2.0f)

Typedefs
using	BVHTree_NearestPointCallback
using	BVHTree_RayCastCallback
using	BVHTree_OverlapCallback = bool (*)(void *userdata, int index_a, int index_b, int thread)
using	BVHTree_RangeQuery = void (*)(void *userdata, int index, const float co[3], float dist_sq)
using	BVHTree_NearestProjectedCallback
using	blender::BVHTree_RayCastCallback_CPP
using	blender::BVHTree_RangeQuery_CPP = FunctionRef<void(int index, const float3 &co, float dist_sq)>

Enumerations
enum	{ BVH_OVERLAP_USE_THREADING = (1 << 0) , BVH_OVERLAP_RETURN_PAIRS = (1 << 1) , BVH_OVERLAP_SELF = (1 << 2) }
enum	{ BVH_NEAREST_OPTIMAL_ORDER = (1 << 0) }
enum	{ BVH_RAYCAST_WATERTIGHT = (1 << 0) }

Functions
void	BLI_bvhtree_free (BVHTree *tree)
BVHTree *	BLI_bvhtree_new (int maxsize, float epsilon, char tree_type, char axis)
void	BLI_bvhtree_insert (BVHTree *tree, int index, const float co[3], int numpoints)
void	BLI_bvhtree_balance (BVHTree *tree)
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_overlap_thread_num (const BVHTree *tree)
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)
BVHTreeOverlap *	BLI_bvhtree_overlap (const BVHTree *tree1, const BVHTree *tree2, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
BVHTreeOverlap *	BLI_bvhtree_overlap_self (const BVHTree *tree, unsigned int *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata)
int *	BLI_bvhtree_intersect_plane (const BVHTree *tree, float plane[4], uint *r_intersect_num)
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])
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)
int	BLI_bvhtree_find_nearest_first (const BVHTree *tree, const float co[3], float dist_sq, BVHTree_NearestPointCallback callback, void *userdata)
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)
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)
float	BLI_bvhtree_bb_raycast (const float bv[6], const float light_start[3], const float light_end[3], float pos[3])
int	BLI_bvhtree_range_query (const BVHTree *tree, const float co[3], float radius, BVHTree_RangeQuery callback, void *userdata)
int	BLI_bvhtree_find_nearest_projected (const BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float(*clip_planes)[4], int clip_plane_len, BVHTreeNearest *nearest, BVHTree_NearestProjectedCallback callback, void *userdata)
void	blender::BLI_bvhtree_ray_cast_all_cpp (const BVHTree &tree, const float3 co, const float3 dir, float radius, float hit_dist, BVHTree_RayCastCallback_CPP fn)
void	blender::BLI_bvhtree_range_query_cpp (const BVHTree &tree, const float3 co, float radius, BVHTree_RangeQuery_CPP fn)

Variables
const float	bvhtree_kdop_axes [13][3]

Macro Definition Documentation

BVH_RAYCAST_DEFAULT

#define BVH_RAYCAST_DEFAULT   (BVH_RAYCAST_WATERTIGHT)

Definition at line 89 of file BLI_kdopbvh.hh.

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

BVH_RAYCAST_DIST_MAX

#define BVH_RAYCAST_DIST_MAX   (FLT_MAX / 2.0f)

Definition at line 90 of file BLI_kdopbvh.hh.

Referenced by BLI_bvhtree_bb_raycast(), BLI_bvhtree_ray_cast_ex(), cast_ray_highpoly(), dynamic_paint_paint_mesh_cell_point_cb_ex(), followtrack_project_to_depth_object_if_needed(), isect_bvhtree_point_v3(), meshdeform_ray_tree_intersect(), blender::ed::transform::raycastMesh(), RNA_api_object(), RNA_api_scene(), shape_cut_test_point(), shrinkwrap_calc_normal_projection_cb_ex(), shrinkwrap_get_tarmat(), blender::ed::transform::snap_object_project_ray_all(), blender::ed::transform::snap_object_project_ray_ex(), blender::ed::transform::snap_object_project_view3d_ex(), test_edges_isect_2d_ray(), walk_floor_distance_get(), walk_ray_cast(), and WM_OT_xr_navigation_teleport().

USE_KDOPBVH_WATERTIGHT

#define USE_KDOPBVH_WATERTIGHT

Definition at line 19 of file BLI_kdopbvh.hh.

Referenced by raycast_callback().

Typedef Documentation

BVHTree_NearestPointCallback

using BVHTree_NearestPointCallback

Initial value:

void (*)(void *userdata,
                                             int index,
                                             const float co[3],
                                             BVHTreeNearest *nearest)

Callback must update nearest in case it finds a nearest result.

Definition at line 95 of file BLI_kdopbvh.hh.

BVHTree_NearestProjectedCallback

using BVHTree_NearestProjectedCallback

Initial value:

void (*)(void *userdata,
                                                 int index,
                                                 const DistProjectedAABBPrecalc *precalc,
                                                 const float (*clip_plane)[4],
                                                 int clip_plane_len,
                                                 BVHTreeNearest *nearest)

Callback to find nearest projected.

Definition at line 121 of file BLI_kdopbvh.hh.

BVHTree_OverlapCallback

using BVHTree_OverlapCallback = bool (*)(void *userdata, int index_a, int index_b, int thread)

Callback to check if 2 nodes overlap (use thread if intersection results need to be stored).

Definition at line 111 of file BLI_kdopbvh.hh.

BVHTree_RangeQuery

using BVHTree_RangeQuery = void (*)(void *userdata, int index, const float co[3], float dist_sq)

Callback to range search query.

Definition at line 116 of file BLI_kdopbvh.hh.

BVHTree_RayCastCallback

using BVHTree_RayCastCallback

Initial value:

void (*)(void *userdata,
                                        int index,
                                        const BVHTreeRay *ray,
                                        BVHTreeRayHit *hit)

Callback must update hit in case it finds a nearest successful hit.

Definition at line 103 of file BLI_kdopbvh.hh.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
BVH_RAYCAST_WATERTIGHT

Definition at line 85 of file BLI_kdopbvh.hh.

anonymous enum

anonymous enum

Enumerator
BVH_NEAREST_OPTIMAL_ORDER

Definition at line 81 of file BLI_kdopbvh.hh.

anonymous enum

anonymous enum

Enumerator
BVH_OVERLAP_USE_THREADING
BVH_OVERLAP_RETURN_PAIRS
BVH_OVERLAP_SELF

Definition at line 74 of file BLI_kdopbvh.hh.

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_planes[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

)

Definition at line 921 of file BLI_kdopbvh.cc.

References MEM_freeN(), MEM_SAFE_FREE, and tree.

Referenced by BKE_bmbvh_free(), BLI_bvhtree_new(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), cloth_free_modifier(), cloth_free_modifier_extern(), deform_verts(), find_nearest_points_test(), blender::ed::greasepencil::free_curves_2d_bvh_data(), free_data(), blender::ed::sculpt_paint::grease_pencil_fill_extension_cut(), heat_system_free(), knife_bvh_free(), BVHTreeDeleter::operator()(), psys_free(), psys_update_particle_bvhtree(), py_bvhtree__tp_dealloc(), TEST(), TEST(), and uv_select_overlap().

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,
		unsigned int *	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().

Variable Documentation

bvhtree_kdop_axes

const float bvhtree_kdop_axes[13][3]

extern

Expose for BVH callbacks to use.

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