Blender
V3.3
|
#include "BLI_sys_types.h"
Go to the source code of this file.
Classes | |
struct | BVHTreeAxisRange |
struct | BVHTreeOverlap |
struct | BVHTreeNearest |
struct | BVHTreeRay |
struct | BVHTreeRayHit |
Macros | |
#define | USE_KDOPBVH_WATERTIGHT |
#define | BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT) |
#define | BVH_RAYCAST_DIST_MAX (FLT_MAX / 2.0f) |
Typedefs | |
typedef struct BVHTree | BVHTree |
typedef struct BVHTreeAxisRange | BVHTreeAxisRange |
typedef struct BVHTreeOverlap | BVHTreeOverlap |
typedef struct BVHTreeNearest | BVHTreeNearest |
typedef struct BVHTreeRay | BVHTreeRay |
typedef struct BVHTreeRayHit | BVHTreeRayHit |
typedef void(* | BVHTree_NearestPointCallback) (void *userdata, int index, const float co[3], BVHTreeNearest *nearest) |
typedef void(* | BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) |
typedef bool(* | BVHTree_OverlapCallback) (void *userdata, int index_a, int index_b, int thread) |
typedef void(* | BVHTree_RangeQuery) (void *userdata, int index, const float co[3], float dist_sq) |
typedef void(* | BVHTree_NearestProjectedCallback) (void *userdata, int index, const struct DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest) |
typedef bool(* | BVHTree_WalkParentCallback) (const BVHTreeAxisRange *bounds, void *userdata) |
typedef bool(* | BVHTree_WalkLeafCallback) (const BVHTreeAxisRange *bounds, int index, void *userdata) |
typedef bool(* | BVHTree_WalkOrderCallback) (const BVHTreeAxisRange *bounds, char axis, void *userdata) |
Enumerations | |
enum | { BVH_OVERLAP_USE_THREADING = (1 << 0) , BVH_OVERLAP_RETURN_PAIRS = (1 << 1) } |
enum | { BVH_NEAREST_OPTIMAL_ORDER = (1 << 0) } |
enum | { BVH_RAYCAST_WATERTIGHT = (1 << 0) } |
Variables | |
const float | bvhtree_kdop_axes [13][3] |
#define BVH_RAYCAST_DEFAULT (BVH_RAYCAST_WATERTIGHT) |
Definition at line 88 of file BLI_kdopbvh.h.
#define BVH_RAYCAST_DIST_MAX (FLT_MAX / 2.0f) |
Definition at line 89 of file BLI_kdopbvh.h.
#define USE_KDOPBVH_WATERTIGHT |
Definition at line 20 of file BLI_kdopbvh.h.
Definition at line 1 of file BLI_kdopbvh.h.
typedef void(* BVHTree_NearestPointCallback) (void *userdata, int index, const float co[3], BVHTreeNearest *nearest) |
Callback must update nearest in case it finds a nearest result.
Definition at line 94 of file BLI_kdopbvh.h.
typedef void(* BVHTree_NearestProjectedCallback) (void *userdata, int index, const struct DistProjectedAABBPrecalc *precalc, const float(*clip_plane)[4], int clip_plane_len, BVHTreeNearest *nearest) |
Callback to find nearest projected.
Definition at line 120 of file BLI_kdopbvh.h.
Callback to check if 2 nodes overlap (use thread if intersection results need to be stored).
Definition at line 110 of file BLI_kdopbvh.h.
Callback to range search query.
Definition at line 115 of file BLI_kdopbvh.h.
typedef void(* BVHTree_RayCastCallback) (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) |
Callback must update hit in case it finds a nearest successful hit.
Definition at line 102 of file BLI_kdopbvh.h.
typedef bool(* BVHTree_WalkLeafCallback) (const BVHTreeAxisRange *bounds, int index, void *userdata) |
Return true to keep walking, else early-exit the search.
Definition at line 136 of file BLI_kdopbvh.h.
typedef bool(* BVHTree_WalkOrderCallback) (const BVHTreeAxisRange *bounds, char axis, void *userdata) |
Return true to search (min, max) else (max, min).
Definition at line 142 of file BLI_kdopbvh.h.
typedef bool(* BVHTree_WalkParentCallback) (const BVHTreeAxisRange *bounds, void *userdata) |
Return true to traverse into this nodes children, else skip.
Definition at line 132 of file BLI_kdopbvh.h.
typedef struct BVHTreeAxisRange BVHTreeAxisRange |
typedef struct BVHTreeNearest BVHTreeNearest |
typedef struct BVHTreeOverlap BVHTreeOverlap |
typedef struct BVHTreeRay BVHTreeRay |
typedef struct BVHTreeRayHit BVHTreeRayHit |
anonymous enum |
Enumerator | |
---|---|
BVH_OVERLAP_USE_THREADING | |
BVH_OVERLAP_RETURN_PAIRS |
Definition at line 75 of file BLI_kdopbvh.h.
anonymous enum |
Enumerator | |
---|---|
BVH_NEAREST_OPTIMAL_ORDER |
Definition at line 80 of file BLI_kdopbvh.h.
anonymous enum |
Enumerator | |
---|---|
BVH_RAYCAST_WATERTIGHT |
Definition at line 84 of file BLI_kdopbvh.h.
Definition at line 937 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(), BM_face_split_edgenet_connect_islands(), BM_mesh_intersect(), BM_mesh_intersect_edges(), bvhtree_balance(), bvhtree_balance_isolated(), bvhtree_build_from_cloth(), bvhtree_build_from_mvert(), C_BVHTree_FromBMesh(), C_BVHTree_FromObject(), C_BVHTree_FromPolygons(), find_nearest_points_test(), heat_ray_tree_create(), knife_bvh_init(), pointdensity_cache_object(), pointdensity_cache_psys(), TEST(), and uv_select_overlap().
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 1954 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().
int BLI_bvhtree_find_nearest | ( | BVHTree * | tree, |
const float | co[3], | ||
BVHTreeNearest * | nearest, | ||
BVHTree_NearestPointCallback | callback, | ||
void * | userdata | ||
) |
Definition at line 1616 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(), blender::nodes::node_geo_transfer_attribute_cc::get_closest_in_bvhtree(), blender::nodes::node_geo_transfer_attribute_cc::get_closest_pointcloud_points(), mesh_remap_bvhtree_query_nearest(), nearest_world_tree_co(), nearestVert(), 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().
int BLI_bvhtree_find_nearest_ex | ( | 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 1567 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().
int BLI_bvhtree_find_nearest_first | ( | 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 1682 of file BLI_kdopbvh.c.
References callback, data, dfs_find_duplicate_fast_dfs(), and tree.
int BLI_bvhtree_find_nearest_projected | ( | BVHTree * | tree, |
float | projmat[4][4], | ||
float | winsize[2], | ||
float | mval[2], | ||
float | clip_planes[6][4], | ||
int | clip_plane_len, | ||
BVHTreeNearest * | nearest, | ||
BVHTree_NearestProjectedCallback | callback, | ||
void * | userdata | ||
) |
Definition at line 2233 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().
Definition at line 926 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(), SnapData_Mesh::clear(), SnapData_EditMesh::clear(), 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(), knife_bvh_free(), psys_free(), psys_update_particle_bvhtree(), py_bvhtree__tp_dealloc(), TEST(), and uv_select_overlap().
This function returns the bounding box of the BVH tree.
Definition at line 1049 of file BLI_kdopbvh.c.
References BLI_assert, BVHNode::bv, copy_v3_v3(), NULL, tree, and zero_v3().
Definition at line 1044 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 blender::draw::statvis_calc_intersect().
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 1034 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().
int BLI_bvhtree_get_tree_type | ( | const BVHTree * | tree | ) |
Maximum number of children that a node can have.
Definition at line 1039 of file BLI_kdopbvh.c.
References tree.
Referenced by BKE_bvhtree_from_editmesh_get(), and BKE_bvhtree_from_mesh_get().
Construct: first insert points, then call balance.
Definition at line 979 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(), knife_bvh_init(), pointdensity_cache_object(), pointdensity_cache_psys(), psys_update_particle_bvhtree(), TEST(), and uv_select_overlap().
Definition at line 1420 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().
NULL
return. Definition at line 854 of file BLI_kdopbvh.c.
References BLI_assert, BLI_assert_unreachable, 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(), knife_bvh_init(), pointdensity_cache_object(), pointdensity_cache_psys(), psys_update_particle_bvhtree(), TEST(), and uv_select_overlap().
BVHTreeOverlap* BLI_bvhtree_overlap | ( | const BVHTree * | tree1, |
const BVHTree * | tree2, | ||
unsigned int * | r_overlap_num, | ||
BVHTree_OverlapCallback | callback, | ||
void * | userdata | ||
) |
Definition at line 1363 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(), blender::draw::statvis_calc_intersect(), and uv_select_overlap().
BVHTreeOverlap* BLI_bvhtree_overlap_ex | ( | const BVHTree * | tree1, |
const BVHTree * | tree2, | ||
uint * | r_overlap_num, | ||
BVHTree_OverlapCallback | callback, | ||
void * | userdata, | ||
uint | max_interactions, | ||
int | flag | ||
) |
Collision/overlap: check two trees if they overlap, alloc's *overlap with length of the int return value.
callback | optional, to test the overlap before adding (must be thread-safe!). |
Definition at line 1263 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, BVHTree::leaf_num, MEM_mallocN, min_axis(), TaskParallelSettings::min_iter_per_thread, BVHTree::nodes, NULL, BVHTree::start_axis, BVHTree::stop_axis, 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(), and BM_mesh_intersect().
int BLI_bvhtree_overlap_thread_num | ( | const BVHTree * | tree | ) |
Use to check the total number of threads BLI_bvhtree_overlap will use.
Definition at line 1234 of file BLI_kdopbvh.c.
Referenced by BLI_bvhtree_overlap_ex(), and bm_elemxelem_bvhtree_overlap().
int BLI_bvhtree_range_query | ( | BVHTree * | tree, |
const float | co[3], | ||
float | radius, | ||
BVHTree_RangeQuery | callback, | ||
void * | userdata | ||
) |
Range query.
Definition at line 2080 of file BLI_kdopbvh.c.
References calc_nearest_point_squared(), callback, data, dfs_range_query(), BVHNode::index, BVHNode::node_num, NULL, and tree.
Referenced by pointdensity(), py_bvhtree_find_nearest_range(), and sph_evaluate_func().
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 1942 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(), knife_bvh_raycast(), knife_bvh_raycast_filter(), 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(), raycastEditMesh(), 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(), and blender::draw::statvis_calc_thickness().
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 2015 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().
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
Definition at line 1981 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().
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 1897 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().
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.
Definition at line 997 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().
Call BLI_bvhtree_update_node() first for every node/point/triangle.
Definition at line 1021 of file BLI_kdopbvh.c.
References node_join(), and tree.
Referenced by bvhtree_update_from_cloth(), and bvhtree_update_from_mvert().
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.
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 2347 of file BLI_kdopbvh.c.
References BVHNode::bv, bvhtree_walk_dfs_recursive(), NULL, and tree.
|
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 170 of file BLI_kdopbvh.c.
Referenced by BLI_bvhtree_find_nearest_ex(), bvhtree_ray_cast_data_precalc(), and create_kdop_hull().