Blender V4.3
pbvh.cc File Reference
#include "MEM_guardedalloc.h"
#include <climits>
#include "BLI_array_utils.hh"
#include "BLI_bit_span_ops.hh"
#include "BLI_bitmap.h"
#include "BLI_bounds.hh"
#include "BLI_enumerable_thread_specific.hh"
#include "BLI_math_geom.h"
#include "BLI_math_matrix.h"
#include "BLI_math_vector.h"
#include "BLI_math_vector.hh"
#include "BLI_rand.h"
#include "BLI_stack.hh"
#include "BLI_task.h"
#include "BLI_task.hh"
#include "BLI_time.h"
#include "BLI_timeit.hh"
#include "BLI_utildefines.h"
#include "BLI_vector.hh"
#include "BLI_vector_set.hh"
#include "DNA_object_types.h"
#include "BKE_attribute.hh"
#include "BKE_ccg.hh"
#include "BKE_mesh.hh"
#include "BKE_mesh_mapping.hh"
#include "BKE_object.hh"
#include "BKE_paint.hh"
#include "BKE_pbvh_api.hh"
#include "BKE_subdiv_ccg.hh"
#include "DEG_depsgraph_query.hh"
#include "bmesh.hh"
#include "atomic_ops.h"
#include "pbvh_intern.hh"

Go to the source code of this file.

Classes

struct  blender::bke::pbvh::StackItem
 
struct  blender::bke::pbvh::PBVHIter
 
struct  blender::bke::pbvh::node_tree
 
struct  blender::bke::pbvh::BoundsMergeInfo
 
struct  blender::bke::pbvh::RaycastData
 

Namespaces

namespace  blender
 
namespace  blender::bke
 
namespace  blender::bke::pbvh
 

Macros

#define STACK_FIXED_DEPTH   100
 

Enumerations

enum  blender::bke::pbvh::PlaneAABBIsect { blender::bke::pbvh::ISECT_INSIDE , blender::bke::pbvh::ISECT_OUTSIDE , blender::bke::pbvh::ISECT_INTERSECT }
 

Functions

static Bounds< float3blender::bke::pbvh::negative_bounds ()
 
static Bounds< float3blender::bke::pbvh::merge_bounds (const Bounds< float3 > &a, const Bounds< float3 > &b)
 
static int blender::bke::pbvh::partition_along_axis (const Span< float3 > face_centers, MutableSpan< int > faces, const int axis, const float middle)
 
static int blender::bke::pbvh::partition_material_indices (const Span< int > material_indices, MutableSpan< int > faces)
 
static BLI_NOINLINE void blender::bke::pbvh::build_mesh_leaf_nodes (const int verts_num, const OffsetIndices< int > faces, const Span< int > corner_verts, MutableSpan< MeshNode > nodes)
 
static bool blender::bke::pbvh::leaf_needs_material_split (const Span< int > faces, const Span< int > material_indices)
 
static void blender::bke::pbvh::build_nodes_recursive_mesh (const Span< int > material_indices, const int leaf_limit, const int node_index, const std::optional< Bounds< float3 > > &bounds_precalc, const Span< float3 > face_centers, const int depth, MutableSpan< int > faces, Vector< MeshNode > &nodes)
 
Bounds< float3blender::bke::pbvh::calc_face_bounds (const Span< float3 > vert_positions, const Span< int > face_verts)
 
static void blender::bke::pbvh::build_nodes_recursive_grids (const Span< int > material_indices, const int leaf_limit, const int node_index, const std::optional< Bounds< float3 > > &bounds_precalc, const Span< float3 > face_centers, const int depth, MutableSpan< int > faces, Vector< GridsNode > &nodes)
 
static Bounds< float3blender::bke::pbvh::calc_face_grid_bounds (const OffsetIndices< int > faces, const Span< float3 > positions, const CCGKey &key, const int face)
 
static bool blender::bke::pbvh::tree_is_empty (const Tree &pbvh)
 
static Nodeblender::bke::pbvh::first_node (Tree &pbvh)
 
static void blender::bke::pbvh::pbvh_iter_begin (PBVHIter *iter, Tree &pbvh, FunctionRef< bool(Node &)> scb)
 
static Nodeblender::bke::pbvh::pbvh_iter_next (PBVHIter *iter, PBVHNodeFlags leaf_flag)
 
static Nodeblender::bke::pbvh::pbvh_iter_next_occluded (PBVHIter *iter)
 
static void blender::bke::pbvh::node_tree_insert (node_tree *tree, node_tree *new_node)
 
static void blender::bke::pbvh::traverse_tree (node_tree *tree, const FunctionRef< void(Node &node, float *tmin)> hit_fn, float *tmin)
 
static void blender::bke::pbvh::free_tree (node_tree *tree)
 
float BKE_pbvh_node_get_tmin (const blender::bke::pbvh::Node *node)
 
static void blender::bke::pbvh::search_callback_occluded (Tree &pbvh, const FunctionRef< bool(Node &)> scb, const FunctionRef< void(Node &node, float *tmin)> hit_fn)
 
static bool blender::bke::pbvh::mesh_topology_count_matches (const Mesh &a, const Mesh &b)
 
static const SharedCache< Vector< float3 > > & blender::bke::pbvh::vert_normals_cache_eval (const Object &object_orig, const Object &object_eval)
 
static SharedCache< Vector< float3 > > & blender::bke::pbvh::vert_normals_cache_eval_for_write (Object &object_orig, Object &object_eval)
 
static const SharedCache< Vector< float3 > > & blender::bke::pbvh::face_normals_cache_eval (const Object &object_orig, const Object &object_eval)
 
static SharedCache< Vector< float3 > > & blender::bke::pbvh::face_normals_cache_eval_for_write (Object &object_orig, Object &object_eval)
 
static void blender::bke::pbvh::normals_calc_faces (const Span< float3 > positions, const OffsetIndices< int > faces, const Span< int > corner_verts, const Span< int > face_indices, MutableSpan< float3 > face_normals)
 
static void blender::bke::pbvh::calc_boundary_face_normals (const Span< float3 > positions, const OffsetIndices< int > faces, const Span< int > corner_verts, const Span< int > face_indices, MutableSpan< float3 > face_normals)
 
static void blender::bke::pbvh::calc_node_face_normals (const Span< float3 > positions, const OffsetIndices< int > faces, const Span< int > corner_verts, const Span< MeshNode > nodes, const IndexMask &nodes_to_update, MutableSpan< float3 > face_normals)
 
static void blender::bke::pbvh::normals_calc_verts_simple (const GroupedSpan< int > vert_to_face_map, const Span< float3 > face_normals, const Span< int > verts, MutableSpan< float3 > vert_normals)
 
static void blender::bke::pbvh::calc_boundary_vert_normals (const GroupedSpan< int > vert_to_face_map, const Span< float3 > face_normals, const Span< int > verts, MutableSpan< float3 > vert_normals)
 
static void blender::bke::pbvh::calc_node_vert_normals (const GroupedSpan< int > vert_to_face_map, const Span< float3 > face_normals, const Span< MeshNode > nodes, const IndexMask &nodes_to_update, MutableSpan< float3 > vert_normals)
 
static void blender::bke::pbvh::update_normals_mesh (Object &object_orig, Object &object_eval, const Span< MeshNode > nodes, const IndexMask &nodes_to_update)
 
static void blender::bke::pbvh::update_normals (Object &object_orig, Object &object_eval, Tree &pbvh)
 
void blender::bke::pbvh::update_normals (const Depsgraph &depsgraph, Object &object_orig, Tree &pbvh)
 
void blender::bke::pbvh::update_normals_from_eval (Object &object_eval, Tree &pbvh)
 
void blender::bke::pbvh::update_node_bounds_mesh (Span< float3 > positions, MeshNode &node)
 
void blender::bke::pbvh::update_node_bounds_grids (int grid_area, Span< float3 > positions, GridsNode &node)
 
void blender::bke::pbvh::update_node_bounds_bmesh (BMeshNode &node)
 
template<typename NodeT >
static BoundsMergeInfo blender::bke::pbvh::merge_child_bounds (MutableSpan< NodeT > nodes, const BitSpan dirty, const int node_index)
 
void blender::bke::pbvh::flush_bounds_to_parents (Tree &pbvh)
 
void blender::bke::pbvh::update_bounds_mesh (Span< float3 > vert_positions, Tree &pbvh)
 
void blender::bke::pbvh::update_bounds_grids (const CCGKey &key, Span< float3 > positions, Tree &pbvh)
 
void blender::bke::pbvh::update_bounds_bmesh (const BMesh &bm, Tree &pbvh)
 
void blender::bke::pbvh::update_bounds (const Depsgraph &depsgraph, const Object &object, Tree &pbvh)
 
void blender::bke::pbvh::store_bounds_orig (Tree &pbvh)
 
void blender::bke::pbvh::node_update_mask_mesh (Span< float > mask, MeshNode &node)
 
void blender::bke::pbvh::update_mask_mesh (const Mesh &mesh, const IndexMask &node_mask, Tree &pbvh)
 
void blender::bke::pbvh::node_update_mask_grids (const CCGKey &key, Span< float > masks, GridsNode &node)
 
void blender::bke::pbvh::update_mask_grids (const SubdivCCG &subdiv_ccg, const IndexMask &node_mask, Tree &pbvh)
 
void blender::bke::pbvh::node_update_mask_bmesh (int mask_offset, BMeshNode &node)
 
void blender::bke::pbvh::update_mask_bmesh (const BMesh &bm, const IndexMask &node_mask, Tree &pbvh)
 
void blender::bke::pbvh::node_update_visibility_mesh (Span< bool > hide_vert, MeshNode &node)
 
static void blender::bke::pbvh::update_visibility_faces (const Mesh &mesh, const MutableSpan< MeshNode > nodes, const IndexMask &node_mask)
 
void blender::bke::pbvh::node_update_visibility_grids (const BitGroupVector<> &grid_hidden, GridsNode &node)
 
static void blender::bke::pbvh::update_visibility_grids (const SubdivCCG &subdiv_ccg, const MutableSpan< GridsNode > nodes, const IndexMask &node_mask)
 
void blender::bke::pbvh::node_update_visibility_bmesh (BMeshNode &node)
 
static void blender::bke::pbvh::update_visibility_bmesh (const MutableSpan< BMeshNode > nodes, const IndexMask &node_mask)
 
void blender::bke::pbvh::update_visibility (const Object &object, Tree &pbvh)
 
int blender::bke::pbvh::count_grid_quads (const BitGroupVector<> &grid_visibility, Span< int > grid_indices, int gridsize, int display_gridsize)
 
blender::Bounds< blender::float3BKE_pbvh_redraw_BB (const blender::bke::pbvh::Tree &pbvh)
 
IndexMask blender::bke::pbvh::nodes_to_face_selection_grids (const SubdivCCG &subdiv_ccg, Span< GridsNode > nodes, const IndexMask &nodes_mask, IndexMaskMemory &memory)
 
Bounds< float3blender::bke::pbvh::bounds_get (const Tree &pbvh)
 
int BKE_pbvh_get_grid_num_verts (const Object &object)
 
int BKE_pbvh_get_grid_num_faces (const Object &object)
 
void BKE_pbvh_node_mark_update (blender::bke::pbvh::Node &node)
 
void BKE_pbvh_mark_rebuild_pixels (blender::bke::pbvh::Tree &pbvh)
 
void BKE_pbvh_node_fully_hidden_set (blender::bke::pbvh::Node &node, int fully_hidden)
 
bool BKE_pbvh_node_fully_hidden_get (const blender::bke::pbvh::Node &node)
 
void BKE_pbvh_node_fully_masked_set (blender::bke::pbvh::Node &node, int fully_masked)
 
bool BKE_pbvh_node_fully_masked_get (const blender::bke::pbvh::Node &node)
 
void BKE_pbvh_node_fully_unmasked_set (blender::bke::pbvh::Node &node, int fully_masked)
 
bool BKE_pbvh_node_fully_unmasked_get (const blender::bke::pbvh::Node &node)
 
Span< intblender::bke::pbvh::node_face_indices_calc_grids (const SubdivCCG &subdiv_ccg, const GridsNode &node, Vector< int > &faces)
 
Bounds< float3blender::bke::pbvh::node_bounds (const Node &node)
 
blender::Bounds< blender::float3BKE_pbvh_node_get_original_BB (const blender::bke::pbvh::Node *node)
 
void BKE_pbvh_node_get_bm_orco_data (const blender::bke::pbvh::BMeshNode &node, blender::Span< blender::float3 > &r_orig_positions, blender::Span< blender::int3 > &r_orig_tris)
 
static bool blender::bke::pbvh::ray_aabb_intersect (Node &node, const RaycastData &rcd)
 
void blender::bke::pbvh::raycast (Tree &pbvh, const FunctionRef< void(Node &node, float *tmin)> hit_fn, const float3 &ray_start, const float3 &ray_normal, bool original)
 
bool blender::bke::pbvh::ray_face_intersection_quad (const float3 &ray_start, const IsectRayPrecalc *isect_precalc, const float3 &t0, const float3 &t1, const float3 &t2, const float3 &t3, float *depth)
 
bool blender::bke::pbvh::ray_face_intersection_tri (const float3 &ray_start, const IsectRayPrecalc *isect_precalc, const float3 &t0, const float3 &t1, const float3 &t2, float *depth)
 
static float blender::bke::pbvh::dist_squared_ray_to_tri_v3_fast (const float3 &ray_origin, const float3 &ray_direction, const float3 &v0, const float3 &v1, const float3 &v2, float3 &r_point, float *r_depth)
 
bool blender::bke::pbvh::ray_face_nearest_quad (const float3 &ray_start, const float3 &ray_normal, const float3 &t0, const float3 &t1, const float3 &t2, const float3 &t3, float *r_depth, float *dist_sq)
 
bool blender::bke::pbvh::ray_face_nearest_tri (const float3 &ray_start, const float3 &ray_normal, const float3 &t0, const float3 &t1, const float3 &t2, float *r_depth, float *dist_sq)
 
static void blender::bke::pbvh::calc_mesh_intersect_data (const Span< int > corner_verts, const Span< int3 > corner_tris, const float3 &ray_start, const float3 &ray_normal, const int face_index, const int tri_index, const std::array< const float *, 3 > co, const float *depth, int &r_active_vertex, int &r_active_face_index, float3 &r_face_normal)
 
bool blender::bke::pbvh::node_raycast_mesh (const MeshNode &node, Span< float3 > node_positions, Span< float3 > vert_positions, OffsetIndices< int > faces, Span< int > corner_verts, Span< int3 > corner_tris, Span< bool > hide_poly, const float3 &ray_start, const float3 &ray_normal, IsectRayPrecalc *isect_precalc, float *depth, int &r_active_vertex, int &r_active_face_index, float3 &r_face_normal)
 
static void blender::bke::pbvh::calc_grids_intersect_data (const float3 &ray_start, const float3 &ray_normal, const int grid, const short x, const short y, const std::array< const float *, 4 > co, float *depth, SubdivCCGCoord &r_active_vertex, int &r_active_grid_index, float3 &r_face_normal)
 
bool blender::bke::pbvh::node_raycast_grids (const SubdivCCG &subdiv_ccg, GridsNode &node, Span< float3 > node_positions, const float3 &ray_start, const float3 &ray_normal, const IsectRayPrecalc *isect_precalc, float *depth, SubdivCCGCoord &r_active_vertex, int &r_active_grid_index, float3 &r_face_normal)
 
void blender::bke::pbvh::clip_ray_ortho (Tree &pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3])
 
static bool blender::bke::pbvh::nearest_to_ray_aabb_dist_sq (Node *node, const DistRayAABB_Precalc &dist_ray_to_aabb_precalc, const bool original)
 
void blender::bke::pbvh::find_nearest_to_ray (Tree &pbvh, const FunctionRef< void(Node &node, float *tmin)> fn, const float3 &ray_start, const float3 &ray_normal, bool original)
 
static bool blender::bke::pbvh::pbvh_faces_node_nearest_to_ray (const MeshNode &node, const Span< float3 > node_positions, const Span< float3 > vert_positions, const OffsetIndices< int > faces, const Span< int > corner_verts, const Span< int3 > corner_tris, const Span< bool > hide_poly, const float3 &ray_start, const float3 &ray_normal, float *r_depth, float *dist_sq)
 
static bool blender::bke::pbvh::pbvh_grids_node_nearest_to_ray (const SubdivCCG &subdiv_ccg, GridsNode &node, const Span< float3 > node_positions, const float ray_start[3], const float ray_normal[3], float *r_depth, float *dist_sq)
 
bool blender::bke::pbvh::find_nearest_to_ray_node (Tree &pbvh, Node &node, Span< float3 > node_positions, bool use_origco, Span< float3 > vert_positions, const OffsetIndices< int > faces, Span< int > corner_verts, Span< int3 > corner_tris, Span< bool > hide_poly, const SubdivCCG *subdiv_ccg, const float ray_start[3], const float ray_normal[3], float *depth, float *dist_sq)
 
static PlaneAABBIsect blender::bke::pbvh::test_frustum_aabb (const Bounds< float3 > &bounds, const PBVHFrustumPlanes *frustum)
 
bool BKE_pbvh_node_frustum_contain_AABB (const blender::bke::pbvh::Node *node, const PBVHFrustumPlanes *data)
 
bool BKE_pbvh_node_frustum_exclude_AABB (const blender::bke::pbvh::Node *node, const PBVHFrustumPlanes *data)
 
void BKE_pbvh_draw_debug_cb (blender::bke::pbvh::Tree &pbvh, void(*draw_fn)(blender::bke::pbvh::Node *node, void *user_data, const float bmin[3], const float bmax[3], PBVHNodeFlags flag), void *user_data)
 
void BKE_pbvh_vert_coords_apply (blender::bke::pbvh::Tree &pbvh, const blender::Span< blender::float3 > vert_positions)
 
void blender::bke::pbvh::set_frustum_planes (Tree &pbvh, PBVHFrustumPlanes *planes)
 
void blender::bke::pbvh::get_frustum_planes (const Tree &pbvh, PBVHFrustumPlanes *planes)
 
static Span< float3blender::bke::pbvh::vert_positions_eval (const Object &object_orig, const Object &object_eval)
 
static MutableSpan< float3blender::bke::pbvh::vert_positions_eval_for_write (Object &object_orig, Object &object_eval)
 
Span< float3blender::bke::pbvh::vert_positions_eval (const Depsgraph &depsgraph, const Object &object_orig)
 
Span< float3blender::bke::pbvh::vert_positions_eval_from_eval (const Object &object_eval)
 
MutableSpan< float3blender::bke::pbvh::vert_positions_eval_for_write (const Depsgraph &depsgraph, Object &object_orig)
 
Span< float3blender::bke::pbvh::vert_normals_eval (const Depsgraph &depsgraph, const Object &object_orig)
 
Span< float3blender::bke::pbvh::vert_normals_eval_from_eval (const Object &object_eval)
 
Span< float3blender::bke::pbvh::face_normals_eval_from_eval (const Object &object_eval)
 
int BKE_pbvh_debug_draw_gen_get (blender::bke::pbvh::Node &node)
 
void BKE_pbvh_sync_visibility_from_verts (Object &object)
 
IndexMask blender::bke::pbvh::all_leaf_nodes (const Tree &pbvh, IndexMaskMemory &memory)
 
static Vector< Node * > blender::bke::pbvh::search_gather (Tree &pbvh, const FunctionRef< bool(Node &)> scb, PBVHNodeFlags leaf_flag)
 
IndexMask blender::bke::pbvh::search_nodes (const Tree &pbvh, IndexMaskMemory &memory, FunctionRef< bool(const Node &)> filter_fn)
 

Macro Definition Documentation

◆ STACK_FIXED_DEPTH

#define STACK_FIXED_DEPTH   100

Function Documentation

◆ BKE_pbvh_debug_draw_gen_get()

int BKE_pbvh_debug_draw_gen_get ( blender::bke::pbvh::Node & node)

Definition at line 2525 of file pbvh.cc.

Referenced by DRW_sculpt_debug_cb().

◆ BKE_pbvh_draw_debug_cb()

void BKE_pbvh_draw_debug_cb ( blender::bke::pbvh::Tree & pbvh,
void(* draw_fn )(blender::bke::pbvh::Node *node, void *user_data, const float bmin[3], const float bmax[3], PBVHNodeFlags flag),
void * user_data )

◆ BKE_pbvh_get_grid_num_faces()

◆ BKE_pbvh_get_grid_num_verts()

◆ BKE_pbvh_mark_rebuild_pixels()

void BKE_pbvh_mark_rebuild_pixels ( blender::bke::pbvh::Tree & pbvh)

Definition at line 1517 of file pbvh.cc.

References blender::bke::pbvh::Tree::nodes_, PBVH_Leaf, and PBVH_RebuildPixels.

Referenced by sculpt_update_object().

◆ BKE_pbvh_node_frustum_contain_AABB()

bool BKE_pbvh_node_frustum_contain_AABB ( const blender::bke::pbvh::Node * node,
const PBVHFrustumPlanes * frustum )

Test if AABB is at least partially inside the PBVHFrustumPlanes volume.

Definition at line 2354 of file pbvh.cc.

References blender::bke::pbvh::ISECT_OUTSIDE, and blender::bke::pbvh::test_frustum_aabb().

Referenced by drw_sculpt_generate_calls(), and blender::draw::sculpt_batches_get_ex().

◆ BKE_pbvh_node_frustum_exclude_AABB()

bool BKE_pbvh_node_frustum_exclude_AABB ( const blender::bke::pbvh::Node * node,
const PBVHFrustumPlanes * frustum )

Test if AABB is at least partially outside the PBVHFrustumPlanes volume.

Definition at line 2361 of file pbvh.cc.

References blender::bke::pbvh::ISECT_INSIDE, and blender::bke::pbvh::test_frustum_aabb().

◆ BKE_pbvh_node_fully_hidden_get()

◆ BKE_pbvh_node_fully_hidden_set()

◆ BKE_pbvh_node_fully_masked_get()

bool BKE_pbvh_node_fully_masked_get ( const blender::bke::pbvh::Node & node)

Definition at line 1559 of file pbvh.cc.

References PBVH_FullyMasked, and PBVH_Leaf.

Referenced by blender::ed::sculpt_paint::node_fully_masked_or_hidden().

◆ BKE_pbvh_node_fully_masked_set()

void BKE_pbvh_node_fully_masked_set ( blender::bke::pbvh::Node & node,
int fully_masked )

◆ BKE_pbvh_node_fully_unmasked_get()

bool BKE_pbvh_node_fully_unmasked_get ( const blender::bke::pbvh::Node & node)

Definition at line 1576 of file pbvh.cc.

References PBVH_FullyUnmasked, and PBVH_Leaf.

◆ BKE_pbvh_node_fully_unmasked_set()

void BKE_pbvh_node_fully_unmasked_set ( blender::bke::pbvh::Node & node,
int fully_masked )

◆ BKE_pbvh_node_get_bm_orco_data()

void BKE_pbvh_node_get_bm_orco_data ( const blender::bke::pbvh::BMeshNode & node,
blender::Span< blender::float3 > & r_orig_positions,
blender::Span< blender::int3 > & r_orig_tris )

◆ BKE_pbvh_node_get_original_BB()

◆ BKE_pbvh_node_get_tmin()

◆ BKE_pbvh_node_mark_update()

void BKE_pbvh_node_mark_update ( blender::bke::pbvh::Node & node)

Definition at line 1512 of file pbvh.cc.

References PBVH_RebuildPixels.

Referenced by BKE_sculpt_update_object_before_eval().

◆ BKE_pbvh_redraw_BB()

◆ BKE_pbvh_sync_visibility_from_verts()

◆ BKE_pbvh_vert_coords_apply()