Blender
V3.3
|
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 |
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 leafs_num) |
BLI_bvhtree_range_query | |
Allocates and fills an array with the indices of node that are on the given spherical range (center, radius). Returns the size of the array. | |
typedef struct RangeQueryData | RangeQueryData |
static void | dfs_range_query (RangeQueryData *data, BVHNode *node) |
int | BLI_bvhtree_range_query (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) |
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:
Definition in file BLI_kdopbvh.c.
#define KDOPBVH_THREAD_LEAF_THRESHOLD 1024 |
Definition at line 54 of file BLI_kdopbvh.c.
#define MAX_TREETYPE 32 |
Definition at line 46 of file BLI_kdopbvh.c.
typedef unsigned char axis_t |
Definition at line 61 of file BLI_kdopbvh.c.
typedef struct BVHBuildHelper BVHBuildHelper |
typedef struct BVHDivNodesData BVHDivNodesData |
typedef struct BVHIntersectPlaneData BVHIntersectPlaneData |
typedef struct BVHNearestData BVHNearestData |
typedef struct BVHNearestProjectedData BVHNearestProjectedData |
typedef struct BVHOverlapData_Thread BVHOverlapData_Thread |
typedef struct BVHRayCastData BVHRayCastData |
typedef struct BVHTree_WalkData BVHTree_WalkData |
typedef struct RangeQueryData RangeQueryData |
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_plane[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, | ||
uint * | 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.
BLI_STATIC_ASSERT | ( | (sizeof(void *)==8 &&sizeof(BVHTree)<=48)||(sizeof(void *)==4 &&sizeof(BVHTree)<=32) | , |
"over sized" | |||
) |
Definition at line 90 of file BLI_kdopbvh.c.
References callback.
|
static |
Definition at line 570 of file BLI_kdopbvh.c.
Referenced by non_recursive_bvh_div_nodes().
Insertion sort algorithm
Definition at line 245 of file BLI_kdopbvh.c.
References Freestyle::a, and t.
Referenced by partition_nth_element().
Definition at line 280 of file BLI_kdopbvh.c.
References Freestyle::a.
Referenced by partition_nth_element().
Definition at line 260 of file BLI_kdopbvh.c.
References Freestyle::a, SWAP, and x.
Referenced by partition_nth_element().
|
static |
Definition at line 1401 of file BLI_kdopbvh.c.
References BLI_stack_push_r(), data, intersect(), node, and tree_intersect_plane_test().
Referenced by BLI_bvhtree_intersect_plane().
|
static |
Definition at line 2118 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().
|
static |
Definition at line 2163 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().
Definition at line 969 of file BLI_kdopbvh.c.
References bvhtree_kdop_axes_length, node, and tree.
Referenced by BLI_bvhtree_insert(), and BLI_bvhtree_update_node().
|
static |
Definition at line 1239 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().
|
static |
Definition at line 1862 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().
|
static |
Runs first among nodes children of the first node before going to the next node in the same layer.
Definition at line 2315 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().
|
static |
Definition at line 1453 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().
|
static |
Definition at line 344 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().
|
static |
Definition at line 1643 of file BLI_kdopbvh.c.
References data, isect_aabb_v3(), and node.
Referenced by BLI_bvhtree_find_nearest_first().
|
static |
Definition at line 1512 of file BLI_kdopbvh.c.
References calc_nearest_point_squared(), data, dfs_find_nearest_dfs(), and node.
Referenced by BLI_bvhtree_find_nearest_ex().
|
static |
Definition at line 1474 of file BLI_kdopbvh.c.
References calc_nearest_point_squared(), data, and node.
Referenced by dfs_find_nearest_begin().
|
static |
Definition at line 2049 of file BLI_kdopbvh.c.
References calc_nearest_point_squared(), data, and node.
Referenced by BLI_bvhtree_range_query().
|
static |
Definition at line 1786 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().
|
static |
A version of dfs_raycast with minor changes to reset the index & dist each ray cast.
Definition at line 1827 of file BLI_kdopbvh.c.
References data, fast_ray_nearest_hit(), node, and ray_nearest_hit().
Referenced by BLI_bvhtree_ray_cast_all_ex().
|
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 1767 of file BLI_kdopbvh.c.
References data, max_fff(), and node.
Referenced by dfs_raycast(), and dfs_raycast_all().
|
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 404 of file BLI_kdopbvh.c.
Referenced by non_recursive_bvh_div_nodes(), and non_recursive_bvh_div_nodes_task_cb().
|
static |
Definition at line 1547 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().
|
static |
Definition at line 1523 of file BLI_kdopbvh.c.
References BLI_heapsimple_insert(), calc_nearest_point_squared(), data, and node.
Referenced by heap_find_nearest_begin().
|
static |
Return the min index of all the leafs achievable with the given branch.
Definition at line 600 of file BLI_kdopbvh.c.
References data.
Referenced by non_recursive_bvh_div_nodes_task_cb().
|
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:
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 643 of file BLI_kdopbvh.c.
References max_ii().
Referenced by BLI_bvhtree_balance(), BLI_bvhtree_new(), and non_recursive_bvh_div_nodes().
Definition at line 1631 of file BLI_kdopbvh.c.
References if(), max, min, and node.
Referenced by dfs_find_duplicate_fast_dfs().
Definition at line 207 of file BLI_kdopbvh.c.
References Freestyle::a, and usdtokens::b().
Referenced by BLI_bvhtree_overlap_ex(), and BM_face_split_edgenet_connect_islands().
bottom-up update of bvh node BV join the children on the parent BV
Definition at line 426 of file BLI_kdopbvh.c.
References node, node_minmax_init(), and tree.
Referenced by BLI_bvhtree_update_tree().
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 225 of file BLI_kdopbvh.c.
References float(), node, and tree.
Referenced by create_kdop_hull(), node_join(), and refit_kdop_hull().
|
static |
This functions builds an optimal implicit tree from the given leafs. Where optimal stands for:
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 774 of file BLI_kdopbvh.c.
References BLI_parallel_range_settings_defaults(), BLI_task_parallel_range(), build_implicit_tree_helper(), BVHNode::bv, BVHNode::children, data, BVHDivNodesData::depth, BVHDivNodesData::first_of_next_level, get_largest_axis(), BVHDivNodesData::i, implicit_needed_branches(), KDOPBVH_THREAD_LEAF_THRESHOLD, BVHNode::main_axis, min_ii(), BVHNode::node_num, non_recursive_bvh_div_nodes_task_cb(), NULL, BVHNode::parent, refit_kdop_hull(), BVHDivNodesData::tree, tree, and TaskParallelSettings::use_threading.
Referenced by BLI_bvhtree_balance().
|
static |
Definition at line 690 of file BLI_kdopbvh.c.
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().
|
static |
Definition at line 305 of file BLI_kdopbvh.c.
References Freestyle::a, bvh_insertionsort(), bvh_medianof3(), and bvh_partition().
Referenced by split_leafs().
|
static |
Definition at line 1718 of file BLI_kdopbvh.c.
Referenced by BLI_bvhtree_bb_raycast(), dfs_raycast(), and dfs_raycast_all().
Definition at line 374 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().
|
static |
This function handles the problem of "sorting" the leafs (along the split_axis).
It arranges the elements in the given partitions such that:
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 660 of file BLI_kdopbvh.c.
References partition_nth_element().
Referenced by non_recursive_bvh_div_nodes_task_cb().
Definition at line 1386 of file BLI_kdopbvh.c.
References aabb_get_near_far_from_plane(), and plane_point_side_v3().
Referenced by bvhtree_intersect_plane_dfs_recursive().
|
static |
overlap - is it possible for 2 bv's to collide ?
Definition at line 1074 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().
|
static |
Definition at line 1093 of file BLI_kdopbvh.c.
References BLI_stack_push_r(), BVHOverlapData_Shared, BVHNode::children, data, BVHNode::index, BVHTreeOverlap::indexA, BVHTreeOverlap::indexB, BVHNode::node_num, BVHOverlapData_Thread::overlap, BVHOverlapData_Thread::shared, tree_overlap_test(), and UNLIKELY.
Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_cb().
|
static |
a version of tree_overlap_traverse that runs a callback to check if the nodes really intersect.
Definition at line 1137 of file BLI_kdopbvh.c.
References BLI_stack_push_r(), BVHOverlapData_Shared, BVHNode::children, data, BVHNode::index, BVHTreeOverlap::indexA, BVHTreeOverlap::indexB, BVHNode::node_num, BVHOverlapData_Thread::overlap, BVHOverlapData_Thread::shared, BVHOverlapData_Thread::thread, tree_overlap_test(), and UNLIKELY.
Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_cb().
|
static |
a version of tree_overlap_traverse_cb that break on first true return.
Definition at line 1184 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, BVHNode::node_num, BVHOverlapData_Thread::overlap, BVHOverlapData_Thread::shared, BVHOverlapData_Thread::thread, tree_overlap_test(), and UNLIKELY.
Referenced by BLI_bvhtree_overlap_ex(), and bvhtree_overlap_task_cb().
BVHOverlapData_Shared |
Definition at line 102 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().
const float bvhtree_kdop_axes[13][3] |
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().
|
static |
Definition at line 187 of file BLI_kdopbvh.c.
Referenced by bvhtree_node_inflate().