BKE_paint_bvh.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */
 
#pragma once

 
#include <variant>
 
#include "BLI_array.hh"
#include "BLI_bit_group_vector.hh"
#include "BLI_bit_vector.hh"
#include "BLI_bounds_types.hh"
#include "BLI_function_ref.hh"
#include "BLI_index_mask_fwd.hh"
#include "BLI_math_vector.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_utility_mixins.hh"
#include "BLI_vector.hh"
#include "BLI_vector_set.hh"
 
struct BMFace;
struct BMLog;
struct BMesh;
struct BMVert;
struct CCGKey;
struct Depsgraph;
struct IsectRayPrecalc;
struct Mesh;
struct SubdivCCG;
struct SubdivCCGCoord;
struct Image;
struct ImageUser;
struct Object;
 
namespace blender::bke::pbvh {
class Node;
class Tree;
namespace pixels {
struct PBVHData;
struct NodeData;
}  // namespace pixels
}  // namespace blender::bke::pbvh
 
namespace blender::bke::pbvh {
 
class Tree;

class Node : NonCopyable {
  friend Tree;
 
 public:
  enum Flags : uint32_t {
    None = 0,
    Leaf = 1 << 0,
 
    FullyHidden = 1 << 10,
    FullyMasked = 1 << 11,
    FullyUnmasked = 1 << 12,
 
    UpdateTopology = 1 << 13,
    RebuildPixels = 1 << 15,
    TexLeaf = 1 << 16,
    TopologyUpdated = 1 << 17,
  };
 
  /* Index of the parent node. A value of -1 indicates that the node is the root node. */
  int parent_ = -1;

  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. */
  Flags flag_ = None;

  float tmin_ = 0.0f;

  int debug_draw_gen_ = 0;

  pixels::NodeData *pixels_ = nullptr;
 
  std::optional<int> parent() const;
  const Bounds<float3> &bounds() const;
  const Bounds<float3> &bounds_orig() const;
};
 
ENUM_OPERATORS(Node::Flags, Node::Flags::TopologyUpdated);
 
struct MeshNode : public Node {
  using LocalVertMapIndexT = int16_t;
  using LocalVertMap = VectorSet<int,
                                 0,
                                 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<BMFace *, 0> bm_faces_;
  Set<BMVert *, 0> bm_unique_verts_;
  Set<BMVert *, 0> bm_other_verts_;

  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;
};
 
enum class Type {
  Mesh,
  Grids,
  BMesh,
};

class Tree {
  friend Node;
  Type type_;

  Array<int, 0> prim_indices_;

  BitVector<> bounds_dirty_;

  BitVector<> normals_dirty_;

  BitVector<> visibility_dirty_;
 
 public:
  std::variant<Vector<MeshNode>, Vector<GridsNode>, Vector<BMeshNode>> nodes_;
 
  pixels::PBVHData *pixels_ = nullptr;
 
  std::unique_ptr<DrawCache> draw_data;
 
  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;

  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);

  void flush_bounds_to_parents();

  void update_bounds(const Depsgraph &depsgraph, const Object &object);
  void update_bounds_mesh(Span<float3> vert_positions);
  void update_bounds_grids(Span<float3> positions, int grid_area);
  void update_bounds_bmesh(const BMesh &bm);
 
  void update_normals(Object &object_orig, Object &object_eval);
 
  void update_visibility(const Object &object);
 
 private:
  explicit Tree(Type type);
  static Tree from_spatially_organized_mesh(const Mesh &mesh);
};
 
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)> hit_fn,
             const float3 &ray_start,
             const float3 &ray_normal,
             bool original);
 
inline Bounds<float3> calc_face_bounds(const Span<float3> vert_positions,
                                       const Span<int> face_verts)
{
  Bounds<float3> bounds{vert_positions[face_verts.first()]};
  for (const int vert : face_verts.slice(1, face_verts.size() - 1)) {
    math::min_max(vert_positions[vert], bounds.min, bounds.max);
  }
  return bounds;
}
 
int partition_along_axis(const Span<float3> face_centers,
                         MutableSpan<int> faces,
                         const int axis,
                         const float middle);
 
int partition_material_indices(const Span<int> material_indices, MutableSpan<int> faces);
 
bool leaf_needs_material_split(const Span<int> faces, const Span<int> material_indices);
 
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,
                        const IsectRayPrecalc *isect_precalc,
                        float *depth,
                        bool use_original,
                        BMVert **r_active_vertex,
                        float3 &r_face_normal);
 
bool raycast_node_detail_bmesh(const BMeshNode &node,
                               const float3 &ray_start,
                               const 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);

Bounds<float3> bounds_get(const Tree &pbvh);

bool node_frustum_contain_aabb(const Node &node, Span<float4> frustum_planes);

bool node_frustum_exclude_aabb(const Node &node, Span<float4> frustum_planes);
 
}  // namespace blender::bke::pbvh
 
void BKE_pbvh_sync_visibility_from_verts(Object &object);
 
namespace blender::bke::pbvh {

int count_grid_quads(const BitGroupVector<> &grid_hidden,
                     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 float3 &center,
                           const std::optional<float3> &view_normal,
                           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);
 
}  // namespace blender::bke::pbvh
 
float BKE_pbvh_node_get_tmin(const blender::bke::pbvh::Node *node);
 
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 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_normals(const Depsgraph &depsgraph, Object &object_orig, Tree &pbvh);
void update_normals_from_eval(Object &object_eval, Tree &pbvh);
 
}  // namespace blender::bke::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);
 
inline std::optional<int> Node::parent() const
{
  if (parent_ == -1) {
    return std::nullopt;
  }
 
  return parent_;
}
 
inline const Bounds<float3> &Node::bounds() const
{
  return bounds_;
}
 
inline const Bounds<float3> &Node::bounds_orig() const
{
  return bounds_orig_;
}
 
inline Span<int> MeshNode::faces() const
{
  return face_indices_;
}
inline Span<int> MeshNode::verts() const
{
  return vert_indices_.as_span().slice(0, unique_verts_num_);
}
inline Span<int> MeshNode::all_verts() const
{
  return vert_indices_;
}
inline int MeshNode::corners_num() const
{
  return corners_num_;
}
 
inline Span<int> GridsNode::grids() const
{
  return prim_indices_;
}
 
inline Type Tree::type() const
{
  return type_;
}
 
}  // namespace blender::bke::pbvh