BKE_pbvh_api.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#pragma once
 
#include <optional>
#include <string>
#include <variant>
 
#include "BLI_array.hh"
#include "BLI_bit_group_vector.hh"
#include "BLI_bit_vector.hh"
#include "BLI_bounds_types.hh"
#include "BLI_compiler_compat.h"
#include "BLI_function_ref.hh"
#include "BLI_generic_span.hh"
#include "BLI_index_mask_fwd.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_offset_indices.hh"
#include "BLI_set.hh"
#include "BLI_span.hh"
#include "BLI_string_ref.hh"
#include "BLI_utildefines.h"
#include "BLI_vector.hh"
 
#include "DNA_customdata_types.h"
 
/* For embedding CCGKey in iterator. */
#include "BKE_ccg.hh"
#include "BKE_pbvh.hh"
 
#include "bmesh.hh"
 
struct BMLog;
struct BMesh;
struct CCGKey;
struct Depsgraph;
struct IsectRayPrecalc;
struct Mesh;
struct SubdivCCG;
struct SubdivCCGCoord;
struct Image;
struct ImageUser;
struct Object;
namespace blender {
namespace bke::pbvh {
class Node;
class Tree;
namespace pixels {
struct PBVHData;
struct NodeData;
}  // namespace pixels
}  // namespace bke::pbvh
}  // namespace blender
 
namespace blender::bke::pbvh {
 
class Tree;
 
class Node {
  friend Tree;
 
 public:
  Bounds<float3> bounds_ = {};
  Bounds<float3> bounds_orig_ = {};
 
  /* For internal nodes, the offset of the children in the blender::bke::pbvh::Tree
   * 'nodes' array. */
  int children_offset_ = 0;
 
  /* Indicates whether this node is a leaf or not; also used for
   * marking various updates that need to be applied. */
  PBVHNodeFlags flag_ = PBVH_UpdateRedraw;
 
  float tmin_ = 0.0f;
 
  int debug_draw_gen_ = 0;
 
  pixels::NodeData *pixels_ = nullptr;
};
 
struct MeshNode : public Node {
  using LocalVertMapIndexT = int16_t;
  using LocalVertMap = VectorSet<int,
                                 DefaultProbingStrategy,
                                 DefaultHash<int>,
                                 DefaultEquality<int>,
                                 SimpleVectorSetSlot<int, LocalVertMapIndexT>,
                                 GuardedAllocator>;
 
  Span<int> face_indices_;
 
  LocalVertMap vert_indices_;
  int unique_verts_num_ = 0;
  int corners_num_;
 
  Span<int> faces() const;
  Span<int> verts() const;
  Span<int> all_verts() const;
 
  int corners_num() const;
};
 
struct GridsNode : public Node {
  Span<int> prim_indices_;
 
  Span<int> grids() const;
};
 
struct BMeshNode : public Node {
  /* Set of pointers to the BMFaces used by this node.
   * NOTE: Type::BMesh only. Faces are always triangles
   * (dynamic topology forcibly triangulates the mesh).
   */
  Set<BMFace *, 0> bm_faces_;
  Set<BMVert *, 0> bm_unique_verts_;
  Set<BMVert *, 0> bm_other_verts_;
 
  /* Stores original coordinates of triangles. */
  Array<float3, 0> orig_positions_;
  Array<int3, 0> orig_tris_;
  Array<BMVert *, 0> orig_verts_;
};
 
class DrawCache {
 public:
  virtual ~DrawCache() = default;
  virtual void tag_positions_changed(const IndexMask &node_mask) = 0;
  virtual void tag_visibility_changed(const IndexMask &node_mask) = 0;
  virtual void tag_topology_changed(const IndexMask &node_mask) = 0;
  virtual void tag_face_sets_changed(const IndexMask &node_mask) = 0;
  virtual void tag_masks_changed(const IndexMask &node_mask) = 0;
  virtual void tag_attribute_changed(const IndexMask &node_mask, StringRef attribute_name) = 0;
};
 
class Tree {
  friend Node;
  Type type_;
 
  Array<int, 0> prim_indices_;
 
 public:
  std::variant<Vector<MeshNode>, Vector<GridsNode>, Vector<BMeshNode>> nodes_;
 
  BitVector<> bounds_dirty_;
 
  BitVector<> normals_dirty_;
 
  BitVector<> visibility_dirty_;
 
  float planes_[6][4];
  int num_planes_;
 
  pixels::PBVHData *pixels_ = nullptr;
 
  std::unique_ptr<DrawCache> draw_data;
 
 public:
  Tree(const Tree &other) = delete;
  Tree(Tree &&other) = default;
  Tree &operator=(const Tree &other) = delete;
  Tree &operator=(Tree &&other) = default;
  ~Tree();
 
  static Tree from_mesh(const Mesh &mesh);
  static Tree from_grids(const Mesh &base_mesh, const SubdivCCG &subdiv_ccg);
  static Tree from_bmesh(BMesh &bm);
 
  int nodes_num() const;
  template<typename NodeT> Span<NodeT> nodes() const;
  template<typename NodeT> MutableSpan<NodeT> nodes();
 
  Type type() const
  {
    return this->type_;
  }
 
  void tag_positions_changed(const IndexMask &node_mask);
 
  void tag_visibility_changed(const IndexMask &node_mask);
 
  void tag_topology_changed(const IndexMask &node_mask);
 
  void tag_face_sets_changed(const IndexMask &node_mask);
 
  void tag_masks_changed(const IndexMask &node_mask);
 
  void tag_attribute_changed(const IndexMask &node_mask, StringRef attribute_name);
 
 private:
  explicit Tree(Type type);
};
 
}  // namespace blender::bke::pbvh
 
struct PBVHFrustumPlanes {
  float (*planes)[4];
  int num_planes;
};
 
/* Callbacks */
 
namespace blender::bke::pbvh {
 
void build_pixels(const Depsgraph &depsgraph, Object &object, Image &image, ImageUser &image_user);
 
/* Ray-cast
 * the hit callback is called for all leaf nodes intersecting the ray;
 * it's up to the callback to find the primitive within the leaves that is
 * hit first */
 
void raycast(Tree &pbvh,
             FunctionRef<void(Node &node, float *tmin)> cb,
             const float3 &ray_start,
             const float3 &ray_normal,
             bool original);
 
bool 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);
 
bool 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);
 
bool node_raycast_bmesh(BMeshNode &node,
                        const float3 &ray_start,
                        const float3 &ray_normal,
                        IsectRayPrecalc *isect_precalc,
                        float *depth,
                        bool use_original,
                        BMVert **r_active_vertex,
                        float3 &r_face_normal);
 
bool raycast_node_detail_bmesh(BMeshNode &node,
                               const float3 &ray_start,
                               IsectRayPrecalc *isect_precalc,
                               float *depth,
                               float *r_edge_length);
 
void clip_ray_ortho(
    Tree &pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3]);
 
void find_nearest_to_ray(Tree &pbvh,
                         const FunctionRef<void(Node &node, float *tmin)> fn,
                         const float3 &ray_start,
                         const float3 &ray_normal,
                         bool original);
 
bool 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);
 
/* Drawing */
void set_frustum_planes(Tree &pbvh, PBVHFrustumPlanes *planes);
void get_frustum_planes(const Tree &pbvh, PBVHFrustumPlanes *planes);
 
Bounds<float3> bounds_get(const Tree &pbvh);
 
}  // namespace blender::bke::pbvh
 
void BKE_pbvh_sync_visibility_from_verts(Object &object);
 
namespace blender::bke::pbvh {
 
int count_grid_quads(const BitGroupVector<> &grid_visibility,
                     Span<int> grid_indices,
                     int gridsize,
                     int display_gridsize);
 
}  // namespace blender::bke::pbvh
 
int BKE_pbvh_get_grid_num_verts(const Object &object);
int BKE_pbvh_get_grid_num_faces(const Object &object);
 
enum PBVHTopologyUpdateMode {
  PBVH_Subdivide = 1,
  PBVH_Collapse = 2,
};
ENUM_OPERATORS(PBVHTopologyUpdateMode, PBVH_Collapse);
 
namespace blender::bke::pbvh {
 
bool bmesh_update_topology(BMesh &bm,
                           Tree &pbvh,
                           BMLog &bm_log,
                           PBVHTopologyUpdateMode mode,
                           float min_edge_len,
                           float max_edge_len,
                           const float center[3],
                           const float view_normal[3],
                           float radius,
                           bool use_frontface,
                           bool use_projected);
 
}  // namespace blender::bke::pbvh
 
/* Node Access */
 
void BKE_pbvh_node_mark_update(blender::bke::pbvh::Node &node);
void BKE_pbvh_node_mark_topology_update(blender::bke::pbvh::Node &node);
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);
 
void BKE_pbvh_mark_rebuild_pixels(blender::bke::pbvh::Tree &pbvh);
 
namespace blender::bke::pbvh {
 
Span<int> node_face_indices_calc_grids(const SubdivCCG &subdiv_ccg,
                                       const GridsNode &node,
                                       Vector<int> &faces);
 
Bounds<float3> node_bounds(const Node &node);
 
}  // namespace blender::bke::pbvh
 
blender::Bounds<blender::float3> BKE_pbvh_node_get_original_BB(
    const blender::bke::pbvh::Node *node);
 
float BKE_pbvh_node_get_tmin(const blender::bke::pbvh::Node *node);
 
bool BKE_pbvh_node_frustum_contain_AABB(const blender::bke::pbvh::Node *node,
                                        const PBVHFrustumPlanes *frustum);
bool BKE_pbvh_node_frustum_exclude_AABB(const blender::bke::pbvh::Node *node,
                                        const PBVHFrustumPlanes *frustum);
 
const blender::Set<BMVert *, 0> &BKE_pbvh_bmesh_node_unique_verts(
    blender::bke::pbvh::BMeshNode *node);
const blender::Set<BMVert *, 0> &BKE_pbvh_bmesh_node_other_verts(
    blender::bke::pbvh::BMeshNode *node);
const blender::Set<BMFace *, 0> &BKE_pbvh_bmesh_node_faces(blender::bke::pbvh::BMeshNode *node);
 
void BKE_pbvh_bmesh_node_save_orig(BMesh *bm,
                                   BMLog *log,
                                   blender::bke::pbvh::BMeshNode *node,
                                   bool use_original);
void BKE_pbvh_bmesh_after_stroke(BMesh &bm, blender::bke::pbvh::Tree &pbvh);
 
namespace blender::bke::pbvh {
 
void update_bounds(const Depsgraph &depsgraph, const Object &object, Tree &pbvh);
void update_bounds_mesh(Span<float3> vert_positions, Tree &pbvh);
void update_bounds_grids(const CCGKey &key, Span<float3> positions, Tree &pbvh);
void update_bounds_bmesh(const BMesh &bm, Tree &pbvh);
 
void store_bounds_orig(Tree &pbvh);
 
void update_mask_mesh(const Mesh &mesh, const IndexMask &node_mask, Tree &pbvh);
void update_mask_grids(const SubdivCCG &subdiv_ccg, const IndexMask &node_mask, Tree &pbvh);
void update_mask_bmesh(const BMesh &bm, const IndexMask &node_mask, Tree &pbvh);
 
void update_visibility(const Object &object, Tree &pbvh);
void update_normals(const Depsgraph &depsgraph, Object &object_orig, Tree &pbvh);
void update_normals_from_eval(Object &object_eval, Tree &pbvh);
 
}  // namespace blender::bke::pbvh
 
blender::Bounds<blender::float3> BKE_pbvh_redraw_BB(const blender::bke::pbvh::Tree &pbvh);
namespace blender::bke::pbvh {
IndexMask nodes_to_face_selection_grids(const SubdivCCG &subdiv_ccg,
                                        Span<GridsNode> nodes,
                                        const IndexMask &nodes_mask,
                                        IndexMaskMemory &memory);
}
 
void BKE_pbvh_vert_coords_apply(blender::bke::pbvh::Tree &pbvh,
                                blender::Span<blender::float3> vert_positions);
 
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);
 
namespace blender::bke::pbvh {
 
Span<float3> vert_positions_eval(const Depsgraph &depsgraph, const Object &object_orig);
Span<float3> vert_positions_eval_from_eval(const Object &object_eval);
 
MutableSpan<float3> vert_positions_eval_for_write(const Depsgraph &depsgraph, Object &object_orig);
 
Span<float3> vert_normals_eval(const Depsgraph &depsgraph, const Object &object_orig);
Span<float3> vert_normals_eval_from_eval(const Object &object_eval);
 
Span<float3> face_normals_eval_from_eval(const Object &object_eval);
 
}  // namespace blender::bke::pbvh
 
int BKE_pbvh_debug_draw_gen_get(blender::bke::pbvh::Node &node);
 
namespace blender::bke::pbvh {
 
IndexMask all_leaf_nodes(const Tree &pbvh, IndexMaskMemory &memory);
 
IndexMask search_nodes(const Tree &pbvh,
                       IndexMaskMemory &memory,
                       FunctionRef<bool(const Node &)> filter_fn);
 
void node_update_mask_mesh(Span<float> mask, MeshNode &node);
void node_update_mask_grids(const CCGKey &key, Span<float> masks, GridsNode &node);
void node_update_mask_bmesh(int mask_offset, BMeshNode &node);
 
void node_update_visibility_mesh(Span<bool> hide_vert, MeshNode &node);
void node_update_visibility_grids(const BitGroupVector<> &grid_hidden, GridsNode &node);
void node_update_visibility_bmesh(BMeshNode &node);
 
void update_node_bounds_mesh(Span<float3> positions, MeshNode &node);
void update_node_bounds_grids(int grid_area, Span<float3> positions, GridsNode &node);
void update_node_bounds_bmesh(BMeshNode &node);
 
void flush_bounds_to_parents(Tree &pbvh);
 
inline Span<int> MeshNode::faces() const
{
  return this->face_indices_;
}
inline Span<int> MeshNode::verts() const
{
  return this->vert_indices_.as_span().slice(0, this->unique_verts_num_);
}
inline Span<int> MeshNode::all_verts() const
{
  return this->vert_indices_;
}
inline int MeshNode::corners_num() const
{
  return corners_num_;
}
 
inline Span<int> GridsNode::grids() const
{
  return this->prim_indices_;
}
 
}  // namespace blender::bke::pbvh