BLI_kdopbvh.c File Reference

BVH-tree implementation. More...

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

Go to the source code of this file.

Classes
class	BVHNode
struct	BVHTree
struct	BVHOverlapData_Thread
struct	BVHNearestData
struct	BVHRayCastData
struct	BVHNearestProjectedData
struct	BVHIntersectPlaneData
struct	BVHBuildHelper
struct	BVHDivNodesData
struct	RangeQueryData
struct	BVHTree_WalkData

Macros
#define	MAX_TREETYPE   32
#define	KDOPBVH_THREAD_LEAF_THRESHOLD   1024

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 (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)
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_tot, 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_tot, 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 (BVHTree *tree, float plane[4], uint *r_intersect_tot)
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 (BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
int	BLI_bvhtree_find_nearest (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 (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 (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 (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 (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 (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 (BVHTree *tree, float projmat[4][4], float winsize[2], float mval[2], float clip_plane[6][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 unsigned char	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, 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 num_leafs)

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

BLI_bvhtree_walk_dfs
typedef struct BVHTree_WalkData	BVHTree_WalkData
static bool	bvhtree_walk_dfs_recursive (BVHTree_WalkData *walk_data, const BVHNode *node)
void	BLI_bvhtree_walk_dfs (BVHTree *tree, BVHTree_WalkParentCallback walk_parent_cb, BVHTree_WalkLeafCallback walk_leaf_cb, BVHTree_WalkOrderCallback walk_order_cb, 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   1024

Definition at line 70 of file BLI_kdopbvh.c.

MAX_TREETYPE

#define MAX_TREETYPE   32

Definition at line 62 of file BLI_kdopbvh.c.

Typedef Documentation

axis_t

typedef unsigned char axis_t

Definition at line 77 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

BVHTree_WalkData

typedef struct BVHTree_WalkData BVHTree_WalkData

RangeQueryData

typedef struct RangeQueryData RangeQueryData

Function Documentation

BLI_bvhtree_balance()

void BLI_bvhtree_balance

(

BVHTree *

tree

)

Definition at line 956 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_pointcloud_get(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), bvhtree_from_editmesh_edges_create_tree(), bvhtree_from_editmesh_looptri_create_tree(), bvhtree_from_editmesh_verts_create_tree(), bvhtree_from_mesh_edges_create_tree(), bvhtree_from_mesh_faces_create_tree(), bvhtree_from_mesh_looptri_create_tree(), bvhtree_from_mesh_verts_create_tree(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), find_nearest_points_test(), heat_ray_tree_create(), pointdensity_cache_object(), pointdensity_cache_psys(), psys_update_particle_bvhtree(), 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 1996 of file BLI_kdopbvh.c.

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

Definition at line 1654 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_mesh_remesh_reproject_paint_mask(), BKE_remesh_reproject_sculpt_face_sets(), BKE_remesh_reproject_vertex_paint(), BKE_shrinkwrap_find_nearest_surface(), closest_point_on_surface(), dynamic_paint_paint_mesh_cell_point_cb_ex(), mesh_remap_bvhtree_query_nearest(), nearestVert(), blender::nodes::proximity_calc(), py_bvhtree_find_nearest(), remap_hair_emitter(), shrinkwrap_calc_nearest_vertex_cb_ex(), and vert2geom_task_cb_ex().

BLI_bvhtree_find_nearest_ex()

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

Definition at line 1605 of file BLI_kdopbvh.c.

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

Definition at line 2284 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(), data, dist_squared_to_projected_aabb(), dist_squared_to_projected_aabb_precalc(), isect_aabb_planes_v3(), NULL, planes_from_projmat(), and tree.

Referenced by snapEditMesh(), and snapMesh().

BLI_bvhtree_free()

void BLI_bvhtree_free

(

BVHTree *

tree

)

Definition at line 945 of file BLI_kdopbvh.c.

References MEM_freeN, MEM_SAFE_FREE, and tree.

Referenced by BKE_bmbvh_free(), BKE_texture_pointdensity_free_data(), BLI_bvhtree_new(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), bvhcache_free(), cache_pointdensity(), cloth_free_modifier(), cloth_free_modifier_extern(), deformVerts(), find_nearest_points_test(), free_bvhtree_from_editmesh(), free_bvhtree_from_mesh(), free_bvhtree_from_pointcloud(), free_pointdensity(), freeData(), heat_system_free(), psys_free(), psys_update_particle_bvhtree(), py_bvhtree__tp_dealloc(), snap_object_data_editmesh_clear(), snap_object_data_mesh_clear(), TEST(), and uv_select_overlap().

BLI_bvhtree_get_bounding_box()

void BLI_bvhtree_get_bounding_box	(	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 1082 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 1074 of file BLI_kdopbvh.c.

References tree.

Referenced by BKE_bmbvh_overlap(), BKE_bmbvh_overlap_self(), cloth_collision(), cloth_collision_response_static(), deformVerts(), hair_collision(), and 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 1061 of file BLI_kdopbvh.c.

References tree.

Referenced by BKE_bvhtree_from_pointcloud_get(), bvhtree_from_editmesh_edges_create_tree(), bvhtree_from_editmesh_looptri_create_tree(), bvhtree_from_editmesh_verts_create_tree(), bvhtree_from_mesh_faces_create_tree(), bvhtree_from_mesh_looptri_create_tree(), bvhtree_from_mesh_verts_create_tree(), 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 1069 of file BLI_kdopbvh.c.

References tree.

Referenced by BKE_bvhtree_from_editmesh_get(), and BKE_bvhtree_from_mesh_get().

BLI_bvhtree_insert()

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

Definition at line 998 of file BLI_kdopbvh.c.

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

Referenced by BKE_bmbvh_new_ex(), BKE_bvhtree_from_pointcloud_get(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), bvhtree_from_editmesh_edges_create_tree(), bvhtree_from_editmesh_looptri_create_tree(), bvhtree_from_editmesh_verts_create_tree(), bvhtree_from_mesh_edges_create_tree(), bvhtree_from_mesh_faces_create_tree(), bvhtree_from_mesh_looptri_create_tree(), bvhtree_from_mesh_verts_create_tree(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), find_nearest_points_test(), heat_ray_tree_create(), pointdensity_cache_object(), pointdensity_cache_psys(), psys_update_particle_bvhtree(), TEST(), and uv_select_overlap().

BLI_bvhtree_intersect_plane()

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

Definition at line 1458 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, 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 873 of file BLI_kdopbvh.c.

References BLI_assert, BLI_bvhtree_free(), blender::robust_pred::epsilon, implicit_needed_branches(), max_ff(), MAX_TREETYPE, MEM_callocN, NULL, tree, and UNLIKELY.

Referenced by BKE_bmbvh_new_ex(), BKE_bvhtree_from_pointcloud_get(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), bvhtree_from_editmesh_edges_create_tree(), bvhtree_from_editmesh_looptri_create_tree(), bvhtree_from_editmesh_verts_create_tree(), bvhtree_from_mesh_edges_create_tree(), bvhtree_from_mesh_faces_create_tree(), bvhtree_from_mesh_looptri_create_tree(), bvhtree_from_mesh_verts_create_tree(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), find_nearest_points_test(), heat_ray_tree_create(), pointdensity_cache_object(), pointdensity_cache_psys(), psys_update_particle_bvhtree(), TEST(), and uv_select_overlap().

BLI_bvhtree_overlap()

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

Definition at line 1401 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(), py_bvhtree_overlap(), statvis_calc_intersect(), and uv_select_overlap().

BLI_bvhtree_overlap_ex()

BVHTreeOverlap* BLI_bvhtree_overlap_ex	(	const BVHTree *	tree1,
		const BVHTree *	tree2,
		uint *	r_overlap_tot,
		BVHTree_OverlapCallback	callback,
		void *	userdata,
		const uint	max_interactions,
		const int	flag
	)

Definition at line 1301 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_USE_THREADING, BVHOverlapData_Shared, bvhtree_overlap_task_cb(), callback, count, data, KDOPBVH_THREAD_LEAF_THRESHOLD, MEM_mallocN, min_axis(), TaskParallelSettings::min_iter_per_thread, BVHTree::nodes, NULL, BVHTree::start_axis, BVHTree::stop_axis, BVHTree::totleaf, tree_overlap_test(), tree_overlap_traverse(), tree_overlap_traverse_cb(), tree_overlap_traverse_num(), and UNLIKELY.

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

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

Definition at line 2131 of file BLI_kdopbvh.c.

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

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

BLI_bvhtree_ray_cast()

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

Definition at line 1984 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(), find_internal_spring_target_vertex(), followtrack_project_to_depth_object_if_needed(), heat_ray_source_visible(), isect_bvhtree_point_v3(), mesh_remap_bvhtree_query_raycast(), py_bvhtree_ray_cast(), raycastEditMesh(), raycastMesh(), shape_cut(), and statvis_calc_thickness().

BLI_bvhtree_ray_cast_all()

void BLI_bvhtree_ray_cast_all	(	BVHTree *	tree,
		const float	co[3],
		const float	dir[3],
		float	radius,
		float	hit_dist,
		BVHTree_RayCastCallback	callback,
		void *	userdata
	)

Definition at line 2066 of file BLI_kdopbvh.c.

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

Referenced by raycastEditMesh(), raycastMesh(), and shape_cut_test_point().

BLI_bvhtree_ray_cast_all_ex()

void BLI_bvhtree_ray_cast_all_ex	(	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 2032 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(), NULL, and tree.

Referenced by BLI_bvhtree_ray_cast_all().

BLI_bvhtree_ray_cast_ex()

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

Definition at line 1939 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(), and tree.

Referenced by BLI_bvhtree_ray_cast(), boid_find_ground(), 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
	)

Definition at line 1017 of file BLI_kdopbvh.c.

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

Definition at line 1044 of file BLI_kdopbvh.c.

References node_join(), and tree.

Referenced by bvhtree_update_from_cloth(), and bvhtree_update_from_mvert().

BLI_bvhtree_walk_dfs()

void BLI_bvhtree_walk_dfs	(	BVHTree *	tree,
		BVHTree_WalkParentCallback	walk_parent_cb,
		BVHTree_WalkLeafCallback	walk_leaf_cb,
		BVHTree_WalkOrderCallback	walk_order_cb,
		void *	userdata
	)

This is a generic function to perform a depth first search on the BVHTree where the search order and nodes traversed depend on callbacks passed in.

Parameters

tree	Tree to walk.
walk_parent_cb	Callback on a parents bound-box to test if it should be traversed.
walk_leaf_cb	Callback to test leaf nodes, callback must store its own result, returning false exits early.
walk_order_cb	Callback that indicates which direction to search, either from the node with the lower or higher K-DOP axis value.
userdata	Argument passed to all callbacks.

Definition at line 2410 of file BLI_kdopbvh.c.

References BVHNode::bv, bvhtree_walk_dfs_recursive(), NULL, and tree.

BLI_STATIC_ASSERT()

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

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

References data, 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 261 of file BLI_kdopbvh.c.

References Freestyle::a, and t.

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

References Freestyle::a.

Referenced by partition_nth_element().

bvh_partition()

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

static

Definition at line 276 of file BLI_kdopbvh.c.

References Freestyle::a, SWAP, and x.

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

References BLI_stack_push_r(), data, intersect(), node, and tree_intersect_plane_test().

Referenced by BLI_bvhtree_intersect_plane().

bvhtree_nearest_projected_dfs_recursive()

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

static

Definition at line 2169 of file BLI_kdopbvh.c.

References data, dist_squared_to_projected_aabb(), node, and NULL.

Referenced by BLI_bvhtree_find_nearest_projected(), 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 2214 of file BLI_kdopbvh.c.

References bvhtree_nearest_projected_dfs_recursive(), data, dist_squared_to_projected_aabb(), ISECT_AABB_PLANE_BEHIND_ANY, ISECT_AABB_PLANE_CROSS_ANY, isect_aabb_planes_v3(), and node.

Referenced by BLI_bvhtree_find_nearest_projected().

bvhtree_node_inflate()

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

static

Definition at line 988 of file BLI_kdopbvh.c.

References bvhtree_kdop_axes_length, node, 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 1277 of file BLI_kdopbvh.c.

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

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

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

Referenced by BLI_bvhtree_ray_cast_all_ex(), and BLI_bvhtree_ray_cast_ex().

bvhtree_walk_dfs_recursive()

static bool bvhtree_walk_dfs_recursive ( BVHTree_WalkData *  walk_data, const BVHNode *  node  )

static

Runs first among nodes children of the first node before going to the next node in the same layer.

Returns

false to break out of the search early.

Definition at line 2366 of file BLI_kdopbvh.c.

References node, BVHTree_WalkData::userdata, BVHTree_WalkData::walk_leaf_cb, BVHTree_WalkData::walk_order_cb, and BVHTree_WalkData::walk_parent_cb.

Referenced by BLI_bvhtree_walk_dfs().

calc_nearest_point_squared()

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

static

Definition at line 1491 of file BLI_kdopbvh.c.

References len_squared_v3v3(), and node.

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

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

References data, isect_aabb_v3(), and node.

Referenced by BLI_bvhtree_find_nearest_first().

dfs_find_nearest_begin()

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

static

Definition at line 1550 of file BLI_kdopbvh.c.

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

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

References calc_nearest_point_squared(), data, and node.

Referenced by dfs_find_nearest_begin().

dfs_range_query()

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

static

Definition at line 2100 of file BLI_kdopbvh.c.

References calc_nearest_point_squared(), data, and node.

Referenced by BLI_bvhtree_range_query().

dfs_raycast()

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

static

Definition at line 1828 of file BLI_kdopbvh.c.

References data, fast_ray_nearest_hit(), madd_v3_v3v3fl(), node, and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_ex().

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

References data, fast_ray_nearest_hit(), node, and ray_nearest_hit().

Referenced by BLI_bvhtree_ray_cast_all_ex().

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

References data, max_fff(), and node.

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 420 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 1585 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(), data, heap_find_nearest_inner(), node, 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 1561 of file BLI_kdopbvh.c.

References BLI_heapsimple_insert(), calc_nearest_point_squared(), data, and node.

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

References data.

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

References if(), max, min, and node.

Referenced by dfs_find_duplicate_fast_dfs().

min_axis()

MINLINE axis_t min_axis	(	axis_t	a,
		axis_t	b
	)

Definition at line 223 of file BLI_kdopbvh.c.

References Freestyle::a.

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

References node, 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 241 of file BLI_kdopbvh.c.

References float(), node, 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  num_leafs  )

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 790 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(), non_recursive_bvh_div_nodes_task_cb(), NULL, BVHNode::parent, refit_kdop_hull(), BVHNode::totnode, BVHDivNodesData::tree, tree, and TaskParallelSettings::use_threading.

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

References BVHNode::bv, BVHNode::children, data, get_largest_axis(), implicit_leafs_index(), BVHNode::main_axis, MAX_TREETYPE, BVHNode::parent, refit_kdop_hull(), split_leafs(), and BVHNode::totnode.

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

References Freestyle::a, 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 1760 of file BLI_kdopbvh.c.

References data, and low().

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

References node, 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 676 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 1424 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_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 1107 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 1126 of file BLI_kdopbvh.c.

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

Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_cb().

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

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

Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_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 that break on first true return.

Definition at line 1217 of file BLI_kdopbvh.c.

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

Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_cb().

Variable Documentation

BVHOverlapData_Shared

BVHOverlapData_Shared

Definition at line 118 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 186 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:

= {
    1.0f,
    1.0f,
    1.0f,
    1.7320508075688772f,
    1.7320508075688772f,
    1.7320508075688772f,
    1.7320508075688772f,
    1.4142135623730951f,
    1.4142135623730951f,
    1.4142135623730951f,
    1.4142135623730951f,
    1.4142135623730951f,
    1.4142135623730951f,
}

Definition at line 203 of file BLI_kdopbvh.c.

Referenced by bvhtree_node_inflate().