49#define STACK_FIXED_DEPTH 100
54 return {
float3(std::numeric_limits<float>::max()),
float3(std::numeric_limits<float>::lowest())};
67 const int *
split = std::partition(faces.
begin(), faces.
end(), [&](
const int face) {
68 return face_centers[face][axis] >= middle;
75 const int first = material_indices[faces.
first()];
76 const int *
split = std::partition(
77 faces.
begin(), faces.
end(), [&](
const int face) { return material_indices[face] == first; });
90 for (const int i : range) {
91 MeshNode &node = nodes[i];
94 int corners_count = 0;
95 for (const int face_index : node.face_indices_) {
96 const IndexRange face = faces[face_index];
97 verts.add_multiple(corner_verts.slice(face));
98 corners_count += face.size();
100 nodes[i].corners_num_ = corners_count;
102 new (&verts_per_node[i]) Array<int>(verts.size());
103 std::copy(verts.begin(), verts.end(), verts_per_node[i].begin());
104 std::ranges::sort(verts_per_node[i]);
111 for (
const int i :
nodes.index_range()) {
115 shared_verts.
clear();
116 for (
const int vert : verts_per_node[i]) {
117 if (vert_used[vert]) {
118 shared_verts.
append(vert);
121 vert_used[vert].set();
125 node.unique_verts_num_ = owned_verts.
size();
126 node.vert_indices_.reserve(owned_verts.
size() + shared_verts.
size());
127 node.vert_indices_.add_multiple(owned_verts);
128 node.vert_indices_.add_multiple(shared_verts);
137 const int first = material_indices[faces.
first()];
139 faces.
begin(), faces.
end(), [&](
const int face) { return material_indices[face] != first; });
144 const int node_index,
145 const int parent_index,
156 node.parent_ = parent_index;
160 if (below_leaf_limit) {
163 node.face_indices_ = faces;
169 nodes[node_index].children_offset_ =
nodes.size();
173 if (!below_leaf_limit) {
175 if (bounds_precalc) {
184 for (
const int face : faces.
slice(range)) {
205 nodes[node_index].children_offset_,
214 nodes[node_index].children_offset_ + 1,
223Tree Tree::from_spatially_organized_mesh(
const Mesh &
mesh)
227 Tree
pbvh(Type::Mesh);
239 pbvh.prim_indices_.reinitialize(
mesh.faces_num);
243 for (const int node_idx : range) {
244 MeshNode &pbvh_node = nodes[node_idx];
245 pbvh_node.parent_ = spatial_groups[node_idx].parent;
247 if (spatial_groups[node_idx].children_offset != 0) {
248 pbvh_node.children_offset_ = spatial_groups[node_idx].children_offset;
251 pbvh_node.children_offset_ = 0;
252 pbvh_node.flag_ = Node::Leaf;
254 const IndexRange face_range = spatial_groups[node_idx].faces;
255 const int face_count = face_range.size();
257 if (face_count > 0) {
258 pbvh_node.face_indices_ = Span<int>(&pbvh.prim_indices_[face_range.start()], face_count);
260 pbvh_node.corners_num_ = spatial_groups[node_idx].corners_count;
262 pbvh_node.unique_verts_num_ = spatial_groups[node_idx].unique_verts.size();
264 pbvh_node.vert_indices_.reserve(spatial_groups[node_idx].unique_verts.size() +
265 spatial_groups[node_idx].shared_verts.size());
267 for (const int i : spatial_groups[node_idx].unique_verts.index_range()) {
268 const int vert_idx = spatial_groups[node_idx].unique_verts.start() + i;
269 pbvh_node.vert_indices_.add(vert_idx);
272 for (const int vert_idx : spatial_groups[node_idx].shared_verts) {
273 pbvh_node.vert_indices_.add(vert_idx);
277 pbvh_node.unique_verts_num_ = 0;
278 pbvh_node.corners_num_ = 0;
285 pbvh.update_bounds_mesh(vert_positions);
286 store_bounds_orig(pbvh);
288 const AttributeAccessor attributes = mesh.attributes();
289 const VArraySpan hide_vert = *attributes.lookup<
bool>(
".hide_vert", AttrDomain::Point);
291 if (!hide_vert.is_empty()) {
293 for (const int i : range) {
294 node_update_visibility_mesh(hide_vert, nodes[i]);
307 if (
mesh.runtime->spatial_groups) {
308 return from_spatially_organized_mesh(
mesh);
319 static_assert(leaf_limit < std::numeric_limits<MeshNode::LocalVertMapIndexT>::max());
328 for (
const int face : range) {
330 corner_verts.
slice(faces[face]));
331 face_centers[face] =
bounds.center();
342 pbvh.prim_indices_.reinitialize(faces.
size());
356 pbvh.update_bounds_mesh(vert_positions);
361 for (const int i : range) {
362 node_update_visibility_mesh(hide_vert, nodes[i]);
374 const int node_index,
375 const int parent_index,
386 node.parent_ = parent_index;
390 if (below_leaf_limit) {
393 node.prim_indices_ = faces;
399 nodes[node_index].children_offset_ =
nodes.size();
403 if (!below_leaf_limit) {
405 if (bounds_precalc) {
414 for (
const int face : faces.
slice(range)) {
435 nodes[node_index].children_offset_,
444 nodes[node_index].children_offset_ + 1,
483 constexpr int base_limit = 800;
493 for (
const int face : range) {
495 face_centers[face] =
bounds.center();
520 for (
const int face :
nodes[i].prim_indices_) {
521 for (
const int corner : faces[face]) {
522 pbvh.prim_indices_[offset] = corner;
532 for (const int i : range) {
533 node_grids_num[i] = offset_indices::sum_group_sizes(faces, nodes[i].prim_indices_);
540 for (const int i : range) {
541 nodes[i].prim_indices_ = pbvh.prim_indices_.as_span().slice(node_grid_offsets[i]);
545 pbvh.tag_positions_changed(
nodes.index_range());
547 pbvh.update_bounds_grids(positions, key.grid_area);
548 store_bounds_orig(
pbvh);
553 for (const int i : range) {
554 node_update_visibility_grids(grid_hidden, nodes[i]);
559 update_mask_grids(subdiv_ccg, nodes.
index_range(), pbvh);
564Tree::Tree(
const Type type) : type_(type)
586 return std::get<Vector<MeshNode>>(this->
nodes_);
590 return std::get<Vector<GridsNode>>(this->
nodes_);
594 return std::get<Vector<BMeshNode>>(this->
nodes_);
598 return std::get<Vector<MeshNode>>(this->
nodes_);
602 return std::get<Vector<GridsNode>>(this->
nodes_);
606 return std::get<Vector<BMeshNode>>(this->
nodes_);
616 bounds_dirty_.resize(std::max(bounds_dirty_.size(), node_mask.
min_array_size()),
false);
617 normals_dirty_.resize(std::max(normals_dirty_.size(), node_mask.
min_array_size()),
false);
621 this->
draw_data->tag_positions_changed(node_mask);
627 visibility_dirty_.resize(std::max(visibility_dirty_.size(), node_mask.
min_array_size()),
false);
628 node_mask.
set_bits(visibility_dirty_);
630 this->
draw_data->tag_visibility_changed(node_mask);
637 this->
draw_data->tag_topology_changed(node_mask);
644 this->
draw_data->tag_face_sets_changed(node_mask);
651 this->
draw_data->tag_masks_changed(node_mask);
658 this->
draw_data->tag_attribute_changed(node_mask, attribute_name);
664 return std::visit([](
const auto &
nodes) {
return nodes.is_empty(); },
pbvh.nodes_);
697 while (!iter->
stack.is_empty()) {
704 if (
node ==
nullptr) {
717 if (
node->flag_ & leaf_flag) {
753 const std::optional node_distance = scb(*
node);
754 if (!node_distance) {
771 std::ranges::stable_sort(hits,
772 [](
const std::pair<float, Node *> &a,
773 const std::pair<float, Node *> &
b) {
return a.first <
b.first; });
779 for (
const auto &[node_distance,
node] : hits) {
813 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.
data);
839 const Object &object_eval)
842 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.
data);
846 switch (
result.cache_source) {
848 return result.mesh_eval->runtime->vert_normals_true_cache;
850 return result.mesh_eval->runtime->vert_normals_true_cache;
867 const Object &object_eval)
870 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.
data);
873 switch (
result.cache_source) {
875 return result.mesh_eval->runtime->face_normals_true_cache;
877 return result.mesh_eval->runtime->face_normals_true_cache;
896 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.
data);
899 switch (
result.cache_source) {
901 return result.mesh_eval->vert_positions();
903 return result.mesh_eval->vert_positions();
907 return mesh_orig.vert_positions();
910 return mesh_orig.vert_positions();
916 Mesh &mesh_orig = *id_cast<Mesh *>(object_orig.
data);
919 switch (
result.cache_source) {
921 return const_cast<Mesh *
>(
result.mesh_eval)->vert_positions_for_write();
923 return const_cast<Mesh *
>(
result.mesh_eval)->vert_positions_for_write();
927 return mesh_orig.vert_positions_for_write();
930 return mesh_orig.vert_positions_for_write();
979 for (
const int i : face_indices) {
1004 for (
const int vert : verts) {
1006 for (
const int face : vert_to_face_map[vert]) {
1007 normal += face_normals[face];
1012 vert_normals[vert] =
float3(0, 0, 1);
1023 normals_calc_verts_simple(vert_to_face_map, face_normals, verts.slice(range), vert_normals);
1047 const int verts_num)
1050 int shared_verts_num = 0;
1052 [&](
const int i) { shared_verts_num +=
nodes[i].shared_verts().size(); });
1056 if (
int64_t(shared_verts_num) * 1024 < verts_num) {
1058 verts.
reserve(shared_verts_num);
1065 verts.
reserve(shared_verts_num);
1068 for (
const int vert :
nodes[i].shared_verts()) {
1070 if (!visited_vert) {
1117 if (face_normals_cache.
is_dirty()) {
1132 if (vert_normals_cache.
is_dirty()) {
1136 positions, faces, corner_verts, vert_to_face_map, face_normals, r_data);
1156 switch (this->type()) {
1167 subdiv_ccg,
nodes, nodes_to_update, memory);
1176 normals_dirty_.clear_and_shrink();
1183 pbvh.update_normals(object_orig, object_eval);
1193 pbvh.update_normals(object_orig, object_eval);
1199 for (
const int vert :
node.all_verts()) {
1208 for (
const int grid :
node.grids()) {
1219 for (
const BMVert *vert :
node.bm_unique_verts_) {
1222 for (
const BMVert *vert :
node.bm_other_verts_) {
1239 if (std::optional<int> parent =
nodes[i].parent()) {
1240 nodes_to_update.
add(*parent);
1244 while (!nodes_to_update.
is_empty()) {
1245 const int node_index = *nodes_to_update.
begin();
1246 nodes_to_update.
remove(node_index);
1255 const std::optional<int> parent =
node.parent();
1256 const bool bounds_changed =
node.bounds_.min != old_bounds.
min ||
1257 node.bounds_.max != old_bounds.
max;
1259 if (bounds_changed && parent) {
1260 nodes_to_update.
add(*parent);
1265 bounds_dirty_.clear_and_shrink();
1312 switch (this->type()) {
1337 for (const int i : range) {
1338 nodes[i].bounds_orig_ = nodes[i].bounds_;
1348 const bool fully_masked = std::all_of(
1349 verts.
begin(), verts.
end(), [&](
const int vert) { return mask[vert] == 1.0f; });
1350 const bool fully_unmasked = std::all_of(
1351 verts.
begin(), verts.
end(), [&](
const int vert) { return mask[vert] <= 0.0f; });
1361 if (
mask.is_empty()) {
1375 bool fully_masked =
true;
1376 bool fully_unmasked =
true;
1377 for (
const int grid :
node.grids()) {
1379 fully_masked &=
mask == 1.0f;
1380 fully_unmasked &=
mask <= 0.0f;
1407 bool fully_masked =
true;
1408 bool fully_unmasked =
true;
1409 for (
const BMVert *vert :
node.bm_unique_verts_) {
1413 for (
const BMVert *vert :
node.bm_other_verts_) {
1441 const bool fully_hidden = std::all_of(
1442 verts.
begin(), verts.
end(), [&](
const int vert) { return hide_vert[vert]; });
1464 const bool fully_hidden = std::none_of(
1465 node.prim_indices_.begin(),
node.prim_indices_.end(), [&](
const int grid) {
1466 return bits::any_bit_unset(grid_hidden[grid]);
1488 const bool unique_hidden = std::all_of(
1489 node.bm_unique_verts_.begin(),
node.bm_unique_verts_.end(), [&](
const BMVert *vert) {
1490 return BM_elem_flag_test(vert, BM_ELEM_HIDDEN);
1492 const bool other_hidden = std::all_of(
1493 node.bm_other_verts_.begin(),
node.bm_other_verts_.end(), [&](
const BMVert *vert) {
1494 return BM_elem_flag_test(vert, BM_ELEM_HIDDEN);
1513 visibility_dirty_.clear_and_shrink();
1514 switch (this->type()) {
1516 const Mesh &
mesh = *id_cast<const Mesh *>(
object.
data);
1535 int display_gridsize)
1537 const int gridarea = (gridsize - 1) * (gridsize - 1);
1539 return gridarea * grid_indices.
size();
1545 int depth1 = int(
log2(
double(gridsize) - 1.0) + DBL_EPSILON);
1546 int depth2 = int(
log2(
double(display_gridsize) - 1.0) + DBL_EPSILON);
1548 int skip = depth2 < depth1 ? 1 << (depth1 - depth2 - 1) : 1;
1551 for (
const int grid : grid_indices) {
1554 for (
int y = 0;
y < gridsize - skip;
y += skip) {
1555 for (
int x = 0;
x < gridsize - skip;
x += skip) {
1582 for (
const int grid :
nodes[i].grids()) {
1583 faces_to_update[grid_to_face_map[grid]] =
true;
1594 if (
nodes.is_empty()) {
1597 return nodes.first().bounds_;
1609 pbvh.pixels_->flags.dirty =
true;
1664namespace bke::pbvh {
1673 for (
const int grid :
node.grids()) {
1674 const int face = grid_to_face_map[grid];
1675 if (face != prev_face) {
1689 r_orig_positions =
node.orig_positions_;
1690 r_orig_tris =
node.orig_tris_;
1695namespace bke::pbvh {
1707 return std::nullopt;
1715 const float3 &ray_normal,
1739 (depth_test < *depth)) ||
1741 (depth_test < *depth)))
1743 *depth = depth_test;
1759 (depth_test < *depth))
1761 *depth = depth_test;
1771 const float3 &ray_direction,
1778 const float *tri[3] = {v0, v1,
v2};
1780 for (
int i = 0, j = 2; i < 3; j = i++) {
1784 ray_origin, ray_direction, tri[i], tri[j], point_test, &depth_test);
1785 if (dist_sq_test < dist_sq_best || i == 0) {
1787 *r_depth = depth_test;
1788 dist_sq_best = dist_sq_test;
1791 return dist_sq_best;
1795 const float3 &ray_normal,
1808 ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)
1810 *dist_sq = dist_sq_test;
1811 *r_depth = depth_test;
1813 ray_start, ray_normal, t0, t2, t3, co, &depth_test)) < *dist_sq)
1815 *dist_sq = dist_sq_test;
1816 *r_depth = depth_test;
1825 const float3 &ray_normal,
1837 ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)
1839 *dist_sq = dist_sq_test;
1840 *r_depth = depth_test;
1850 const float3 &ray_normal,
1851 const int face_index,
1852 const int tri_index,
1853 const std::array<const float *, 3> co,
1855 int &r_active_vertex,
1856 int &r_active_face_index,
1860 float3 nearest_vertex_co(0.0f);
1863 const float3 location = ray_start + ray_normal * depth;
1864 for (
int i = 0; i < co.size(); i++) {
1871 nearest_vertex_co = co[i];
1872 r_active_vertex = corner_verts[corner_tris[tri_index][i]];
1873 r_active_face_index = face_index;
1886 const float3 &ray_normal,
1889 int &r_active_vertex,
1890 int &r_active_face_index,
1898 const int face_i = face_indices[i];
1899 if (!hide_poly.
is_empty() && hide_poly[face_i]) {
1904 const int3 &tri = corner_tris[tri_i];
1905 const std::array<const float *, 3> co{{vert_positions[corner_verts[tri[0]]],
1906 vert_positions[corner_verts[tri[1]]],
1907 vert_positions[corner_verts[tri[2]]]}};
1919 r_active_face_index,
1928 const int face_i = face_indices[i];
1929 if (!hide_poly.
is_empty() && hide_poly[face_i]) {
1934 const int3 &tri = corner_tris[tri_i];
1935 const std::array<const float *, 3> co{
1936 {node_positions[vert_map.
index_of(corner_verts[tri[0]])],
1937 node_positions[vert_map.
index_of(corner_verts[tri[1]])],
1938 node_positions[vert_map.
index_of(corner_verts[tri[2]])]}};
1950 r_active_face_index,
1961 const float3 &ray_normal,
1965 const std::array<const float *, 4> co,
1968 int &r_active_grid_index,
1972 float3 nearest_vertex_co;
1975 const float3 location = ray_start + ray_normal * depth;
1977 constexpr short x_it[4] = {0, 1, 1, 0};
1978 constexpr short y_it[4] = {1, 1, 0, 0};
1980 for (
int i = 0; i < co.size(); i++) {
1988 r_active_vertex =
SubdivCCGCoord{grid, short(
x + x_it[i]), short(
y + y_it[i])};
1991 r_active_grid_index = grid;
1998 const float3 &ray_normal,
2002 int &r_active_grid_index,
2013 for (
const int grid : grids) {
2022 const std::array<const float *, 4> co{
2028 ray_start, isect_precalc, co[0], co[1], co[2], co[3], depth))
2039 r_active_grid_index,
2048 const int grid = grids[i];
2057 const std::array<const float *, 4> co{grid_positions[(
y + 1) * grid_size +
x],
2058 grid_positions[(
y + 1) * grid_size +
x + 1],
2059 grid_positions[
y * grid_size +
x + 1],
2060 grid_positions[
y * grid_size +
x]};
2062 ray_start, isect_precalc, co[0], co[1], co[2], co[3], depth))
2073 r_active_grid_index,
2085 Tree &
pbvh,
bool original,
float ray_start[3],
float ray_end[3],
float ray_normal[3])
2090 float rootmin_start, rootmin_end;
2092 float bb_center[3], bb_diff[3];
2094 float ray_normal_inv[3];
2095 float offset = 1.0f + 1e-3f;
2096 const float offset_vec[3] = {1e-3f, 1e-3f, 1e-3f};
2126 float dist =
max[2] -
min[2];
2159 float epsilon = (std::nextafter(rootmin_start, rootmin_start + 1000.0f) - rootmin_start) *
2162 if (rootmin_start == rootmin_end) {
2163 rootmin_start -= epsilon;
2164 rootmin_end += epsilon;
2178 float co_dummy[3], depth;
2180 &dist_ray_to_aabb_precalc,
bounds.min,
bounds.max, co_dummy, &depth);
2182 if (depth <= 0.0f) {
2183 return std::nullopt;
2191 const float3 &ray_normal,
2192 const bool original)
2213 const float3 &ray_normal,
2222 const int face_i = face_indices[i];
2223 if (!hide_poly.
is_empty() && hide_poly[face_i]) {
2228 const int3 &corner_tri = corner_tris[tri_i];
2231 vert_positions[corner_verts[corner_tri[0]]],
2232 vert_positions[corner_verts[corner_tri[1]]],
2233 vert_positions[corner_verts[corner_tri[2]]],
2242 const int face_i = face_indices[i];
2243 if (!hide_poly.
is_empty() && hide_poly[face_i]) {
2248 const int3 &corner_tri = corner_tris[tri_i];
2251 node_positions[vert_map.
index_of(corner_verts[corner_tri[0]])],
2252 node_positions[vert_map.
index_of(corner_verts[corner_tri[1]])],
2253 node_positions[vert_map.
index_of(corner_verts[corner_tri[2]])],
2266 const float ray_start[3],
2267 const float ray_normal[3],
2279 for (
const int grid : grids) {
2303 const int grid = grids[i];
2314 grid_positions[
y * grid_size +
x],
2315 grid_positions[
y * grid_size +
x + 1],
2316 grid_positions[(
y + 1) * grid_size +
x + 1],
2317 grid_positions[(
y + 1) * grid_size +
x],
2338 const float ray_start[3],
2339 const float ray_normal[3],
2346 switch (
pbvh.type()) {
2369 static_cast<BMeshNode &
>(
node), ray_start, ray_normal, depth, dist_sq, use_origco);
2391 for (
const int i : frustum_planes.
index_range()) {
2392 float vmin[3], vmax[3];
2394 for (
int axis = 0; axis < 3; axis++) {
2395 if (frustum_planes[i][axis] < 0) {
2396 vmin[axis] =
bounds.min[axis];
2397 vmax[axis] =
bounds.max[axis];
2400 vmin[axis] =
bounds.max[axis];
2401 vmax[axis] =
bounds.min[axis];
2405 if (
dot_v3v3(frustum_planes[i], vmin) + frustum_planes[i][3] < 0) {
2408 if (
dot_v3v3(frustum_planes[i], vmax) + frustum_planes[i][3] <= 0) {
2432 pbvh.update_bounds_mesh(vert_positions);
2438 return node.debug_draw_gen_;
2494 const IndexRange face = faces[i];
2495 return std::any_of(face.begin(), face.end(), [&](const int corner) {
2496 return grid_hidden[corner][key.grid_area - 1];
2503 if (hidden_faces.is_empty()) {
2504 attributes.
remove(
".hide_poly");
2509 hide_poly.
span.fill(
false);
2520namespace bke::pbvh {
2525 [&](
const auto &
nodes) {
2527 return (nodes[i].flag_ & Node::Leaf) != 0;
2548 if (
node->flag_ & leaf_flag) {
2564 [&](
const auto &pbvh_nodes) {
2565 using VectorT = std::decay_t<
decltype(pbvh_nodes)>;
2566 for (
const int i :
nodes.index_range()) {
2567 indices[i] =
static_cast<typename VectorT::value_type *
>(
nodes[i]) - pbvh_nodes.data();
2571 std::ranges::sort(indices);
General operations, lookup, etc. for blender objects.
A BVH for high poly meshes.
Object is a sort of wrapper for general info.
#define PRF_scope_with_name(ui_name, category)
#define PRF_scope(category)
#define STACK_FIXED_DEPTH
#define BLI_assert_unreachable()
#define SET_FLAG_FROM_TEST(value, test, flag)
#define BM_ELEM_CD_GET_FLOAT(ele, offset)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
DBVT_INLINE bool Intersect(const btDbvtAabbMm &a, const btDbvtAabbMm &b)
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
static IndexMask from_bits(BitSpan bits, LinearAllocator<> &memory)
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr IndexRange()=default
constexpr int64_t size() const
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
constexpr MutableSpan drop_front(const int64_t n) const
constexpr T * end() const
constexpr T & first() const
constexpr T * begin() const
constexpr IndexRange index_range() const
constexpr MutableSpan take_front(const int64_t n) const
void reserve(const int64_t n)
bool remove(const Key &key)
void update(FunctionRef< void(T &data)> compute_cache)
void ensure(FunctionRef< void(T &data)> compute_cache)
constexpr Span slice(int64_t start, int64_t size) const
constexpr const T & first() const
constexpr int64_t size() const
constexpr const T * end() const
constexpr IndexRange index_range() const
constexpr const T * begin() const
constexpr bool is_empty() const
void push(const T &value)
void reserve(const int64_t n)
void add_multiple(Span< Key > keys)
int64_t index_of(const Key &key) const
void append(const T &value)
IndexRange index_range() const
void resize(const int64_t new_size)
void append_unchecked(const T &value)
void reserve(const int64_t min_capacity)
Span< T > as_span() const
GAttributeReader lookup(const StringRef name) const
GSpanAttributeWriter lookup_or_add_for_write_span(StringRef name, AttrDomain domain, AttrType data_type, const AttributeInit &initializer=AttributeInitDefaultValue())
bool remove(const StringRef name)
const Bounds< float3 > & bounds() const
const Bounds< float3 > & bounds_orig() const
void update_normals(Object &object_orig, Object &object_eval)
void tag_attribute_changed(const IndexMask &node_mask, StringRef attribute_name)
Tree(const Tree &other)=delete
void tag_positions_changed(const IndexMask &node_mask)
Span< NodeT > nodes() const
void update_bounds(const Depsgraph &depsgraph, const Object &object)
void update_bounds_grids(Span< float3 > positions, int grid_area)
void tag_face_sets_changed(const IndexMask &node_mask)
void tag_masks_changed(const IndexMask &node_mask)
std::unique_ptr< DrawCache > draw_data
void tag_visibility_changed(const IndexMask &node_mask)
void update_visibility(const Object &object)
static Tree from_grids(const Mesh &base_mesh, const SubdivCCG &subdiv_ccg)
static Tree from_mesh(const Mesh &mesh)
void tag_topology_changed(const IndexMask &node_mask)
void update_bounds_mesh(Span< float3 > vert_positions)
void update_bounds_bmesh(const BMesh &bm)
std::variant< Vector< MeshNode >, Vector< GridsNode >, Vector< BMeshNode > > nodes_
void flush_bounds_to_parents()
constexpr bool is_empty() const
int64_t min_array_size() const
void set_bits(MutableBitSpan r_bits, int64_t offset=0) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexRange index_range() const
float distance(float, float) RET
float length(VecOp< float, D >) RET
void fill_index_range(MutableSpan< T > span, const T start=0)
IndexRange face_range(const OffsetIndices< int > faces, const int grid_area, const int face)
IndexRange grid_range(const int grid_area, const int grid)
float3 face_normal_calc(Span< float3 > vert_positions, Span< int > face_verts)
IndexRange face_triangles_range(OffsetIndices< int > faces, int face_i)
void normals_calc_verts(Span< float3 > vert_positions, OffsetIndices< int > faces, Span< int > corner_verts, GroupedSpan< int > vert_to_face_map, Span< float3 > face_normals, MutableSpan< float3 > vert_normals)
void normals_calc_faces(Span< float3 > vert_positions, OffsetIndices< int > faces, Span< int > corner_verts, MutableSpan< float3 > face_normals)
pbvh::Tree * pbvh_get(Object &object)
void raycast(Tree &pbvh, FunctionRef< void(Node &node, float *tmin)> hit_fn, const float3 &ray_start, const float3 &ray_normal, bool original)
static std::optional< float > nearest_to_ray_aabb_dist_sq(const Node &node, const DistRayAABB_Precalc &dist_ray_to_aabb_precalc, const bool original)
static void update_visibility_grids(const SubdivCCG &subdiv_ccg, const MutableSpan< GridsNode > nodes, const IndexMask &node_mask)
IndexMask search_nodes(const Tree &pbvh, IndexMaskMemory &memory, FunctionRef< bool(const Node &)> filter_fn)
static PlaneAABBIsect test_frustum_aabb(const Bounds< float3 > &bounds, const Span< float4 > frustum_planes)
static Vector< int > gather_shared_verts(const Span< MeshNode > nodes, const IndexMask &nodes_to_update, const int verts_num)
bool bmesh_node_nearest_to_ray(BMeshNode &node, const float3 &ray_start, const float3 &ray_normal, float *r_depth, float *dist_sq, const bool use_original)
static Vector< Node * > search_gather(Tree &pbvh, const FunctionRef< bool(Node &)> scb, Node::Flags leaf_flag)
static void 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 const SharedCache< Vector< float3 > > & vert_normals_cache_eval(const Object &object_orig, const Object &object_eval)
Bounds< float3 > calc_face_bounds(const Span< float3 > vert_positions, const Span< int > face_verts)
static void build_nodes_recursive_grids(const Span< int > material_indices, const int leaf_limit, const int node_index, const int parent_index, const std::optional< Bounds< float3 > > &bounds_precalc, const Span< float3 > face_centers, const int depth, MutableSpan< int > faces, Vector< GridsNode > &nodes)
void update_mask_bmesh(const BMesh &bm, const IndexMask &node_mask, Tree &pbvh)
void update_normals(const Depsgraph &depsgraph, Object &object_orig, Tree &pbvh)
static void calc_shared_vert_normals(const GroupedSpan< int > vert_to_face_map, const Span< float3 > face_normals, const Span< int > verts, MutableSpan< float3 > vert_normals)
static BLI_NOINLINE void build_mesh_leaf_nodes(const int verts_num, const OffsetIndices< int > faces, const Span< int > corner_verts, MutableSpan< MeshNode > nodes)
static Bounds< float3 > calc_face_grid_bounds(const OffsetIndices< int > faces, const Span< float3 > positions, const CCGKey &key, const int face)
void update_mask_mesh(const Mesh &mesh, const IndexMask &node_mask, Tree &pbvh)
Span< float3 > vert_normals_eval_from_eval(const Object &object_eval)
IndexMask all_leaf_nodes(const Tree &pbvh, IndexMaskMemory &memory)
static void 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)
void clip_ray_ortho(Tree &pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3])
static bool 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)
int count_grid_quads(const BitGroupVector<> &grid_hidden, Span< int > grid_indices, int gridsize, int display_gridsize)
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)
void update_node_bounds_bmesh(BMeshNode &node)
int partition_along_axis(const Span< float3 > face_centers, MutableSpan< int > faces, const int axis, const float middle)
static void update_visibility_faces(const Mesh &mesh, const MutableSpan< MeshNode > nodes, const IndexMask &node_mask)
static void pbvh_iter_begin(PBVHIter *iter, Tree &pbvh, FunctionRef< bool(Node &)> scb)
static float 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)
static std::optional< float > ray_aabb_intersect(const Node &node, const RaycastData &rcd)
bool 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 normals_calc_verts_simple(const GroupedSpan< int > vert_to_face_map, const Span< float3 > face_normals, const Span< int > verts, MutableSpan< float3 > vert_normals)
bool node_frustum_exclude_aabb(const Node &node, Span< float4 > frustum_planes)
Span< float3 > vert_positions_eval_from_eval(const Object &object_eval)
static bool tree_is_empty(const Tree &pbvh)
void node_update_mask_bmesh(int mask_offset, BMeshNode &node)
void node_update_mask_mesh(Span< float > mask, MeshNode &node)
void node_update_visibility_grids(const BitGroupVector<> &grid_hidden, GridsNode &node)
void bmesh_normals_update(Tree &pbvh, const IndexMask &nodes_to_update)
static void 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 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)
static Node * pbvh_iter_next(PBVHIter *iter, Node::Flags leaf_flag)
static Node & first_node(Tree &pbvh)
void node_update_mask_grids(const CCGKey &key, Span< float > masks, GridsNode &node)
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)
static Bounds< float3 > negative_bounds()
void update_node_bounds_mesh(Span< float3 > positions, MeshNode &node)
void node_update_visibility_bmesh(BMeshNode &node)
static SharedCache< Vector< float3 > > & vert_normals_cache_eval_for_write(Object &object_orig, Object &object_eval)
Bounds< float3 > bounds_get(const Tree &pbvh)
void update_normals_from_eval(Object &object_eval, Tree &pbvh)
void pixels_free(bke::pbvh::Tree *pbvh)
Span< float3 > vert_normals_eval(const Depsgraph &depsgraph, const Object &object_orig)
IndexMask nodes_to_face_selection_grids(const SubdivCCG &subdiv_ccg, Span< GridsNode > nodes, const IndexMask &nodes_mask, IndexMaskMemory &memory)
static void build_nodes_recursive_mesh(const Span< int > material_indices, const int leaf_limit, const int node_index, const int parent_index, const std::optional< Bounds< float3 > > &bounds_precalc, const Span< float3 > face_centers, const int depth, MutableSpan< int > faces, Vector< MeshNode > &nodes)
static SharedCache< Vector< float3 > > & face_normals_cache_eval_for_write(Object &object_orig, Object &object_eval)
void update_mask_grids(const SubdivCCG &subdiv_ccg, const IndexMask &node_mask, Tree &pbvh)
MutableSpan< float3 > vert_positions_eval_for_write(const Depsgraph &depsgraph, Object &object_orig)
static bool 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)
bool 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)
static Bounds< float3 > merge_bounds(const Bounds< float3 > &a, const Bounds< float3 > &b)
static const SharedCache< Vector< float3 > > & face_normals_cache_eval(const Object &object_orig, const Object &object_eval)
bool leaf_needs_material_split(const Span< int > faces, const Span< int > material_indices)
static void 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, const float depth, SubdivCCGCoord &r_active_vertex, int &r_active_grid_index, float3 &r_face_normal)
int partition_material_indices(const Span< int > material_indices, MutableSpan< int > faces)
Span< float3 > face_normals_eval_from_eval(const Object &object_eval)
static void update_visibility_bmesh(const MutableSpan< BMeshNode > nodes, const IndexMask &node_mask)
bool ray_face_intersection_tri(const float3 &ray_start, const IsectRayPrecalc *isect_precalc, const float3 &t0, const float3 &t1, const float3 &t2, float *depth)
void update_node_bounds_grids(int grid_area, Span< float3 > positions, GridsNode &node)
bool node_frustum_contain_aabb(const Node &node, Span< float4 > frustum_planes)
static void update_normals_mesh(Object &object_orig, Object &object_eval, const Span< MeshNode > nodes, const IndexMask &nodes_to_update)
static void search_callback_occluded(Tree &pbvh, const FunctionRef< std::optional< float >(const Node &)> scb, const FunctionRef< void(Node &node, float *distance)> hit_fn)
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)
void store_bounds_orig(Tree &pbvh)
static bool mesh_topology_count_matches(const Mesh &a, const Mesh &b)
Span< int > node_face_indices_calc_grids(const SubdivCCG &subdiv_ccg, const GridsNode &node, Vector< int > &faces)
Span< float3 > vert_positions_eval(const Depsgraph &depsgraph, const Object &object_orig)
static PositionSourceResult cache_source_get(const Object &object_orig, const Object &object_eval)
void node_update_visibility_mesh(Span< bool > hide_vert, MeshNode &node)
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)
static void 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)
void mesh_hide_vert_flush(Mesh &mesh)
void mesh_hide_face_flush(Mesh &mesh)
Bounds< T > merge(const Bounds< T > &a, const Bounds< T > &b)
constexpr ParallelGrainSize grain_size(int grain_size)
void masked_fill(MutableSpan< T > data, const T &value, const IndexMask &mask)
void split(const std::string &s, const char delim, std::vector< std::string > &tokens)
QuaternionBase< T > normalize_and_get_length(const QuaternionBase< T > &q, T &out_length)
T midpoint(const T &a, const T &b)
void min_max(const T &value, T &min, T &max)
int dominant_axis(const VecBase< T, 3 > &a)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
void parallel_invoke(Functions &&...functions)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void mul_m3_v3(const float M[3][3], float r[3])
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
bool isect_ray_aabb_v3(const struct IsectRayAABB_Precalc *data, const float bb_min[3], const float bb_max[3], float *r_tmin)
void BKE_pbvh_mark_rebuild_pixels(bke::pbvh::Tree &pbvh)
MINLINE void copy_v3_v3(float r[3], const float a[3])
void BKE_pbvh_node_fully_hidden_set(bke::pbvh::Node &node, int fully_hidden)
void minmax_v3v3_v3(float min[3], float max[3], const float vec[3])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
bool isect_ray_tri_watertight_v3(const float ray_origin[3], const struct IsectRayPrecalc *isect_precalc, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
int BKE_pbvh_debug_draw_gen_get(bke::pbvh::Node &node)
struct DistRayAABB_Precalc dist_squared_ray_to_aabb_v3_precalc(const float ray_origin[3], const float ray_direction[3])
void BKE_pbvh_vert_coords_apply(bke::pbvh::Tree &pbvh, Span< float3 > vert_positions)
ATTR_WARN_UNUSED_RESULT const BMVert * v
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
void BKE_pbvh_node_fully_masked_set(bke::pbvh::Node &node, int fully_masked)
bool BKE_paint_is_grid_face_hidden(BoundedBitSpan grid_hidden, int gridsize, int x, int y)
CCGKey BKE_subdiv_ccg_key_top_level(const SubdivCCG &subdiv_ccg)
bool DEG_is_original(const T *id)
void BKE_pbvh_sync_visibility_from_verts(Object &object)
VecBase< int32_t, 3 > int3
BMesh const char void * data
T * DEG_get_evaluated(const Depsgraph *depsgraph, T *id)
float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
void BKE_pbvh_node_fully_unmasked_set(bke::pbvh::Node &node, int fully_masked)
int CustomData_get_offset_named(const CustomData *data, eCustomDataType type, StringRef name)
void BKE_subdiv_ccg_update_normals(SubdivCCG &subdiv_ccg, const IndexMask &face_mask)
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
int CCG_grid_xy_to_index(const int grid_size, const int x, const int y)
MINLINE void mul_v3_v3fl(float r[3], const float a[3], float f)
MINLINE void add_v3_v3(float r[3], const float a[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
T * DEG_get_original(T *id)
bool BKE_pbvh_node_fully_masked_get(const bke::pbvh::Node &node)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
bool BKE_pbvh_node_fully_hidden_get(const bke::pbvh::Node &node)
float dist_squared_ray_to_seg_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], float r_point[3], float *r_depth)
VecBase< float, 3 > float3
void BKE_pbvh_node_get_bm_orco_data(const bke::pbvh::BMeshNode &node, Span< float3 > &r_orig_positions, Span< int3 > &r_orig_tris)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
Mesh * BKE_object_get_evaluated_mesh_no_subsurf(const Object *object_eval)
void isect_ray_aabb_v3_precalc(struct IsectRayAABB_Precalc *data, const float ray_origin[3], const float ray_direction[3])
bool BKE_pbvh_node_fully_unmasked_get(const bke::pbvh::Node &node)
float dist_squared_ray_to_aabb_v3(const struct DistRayAABB_Precalc *data, const float bb_min[3], const float bb_max[3], float r_point[3], float *r_depth)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
const Mesh * BKE_object_get_mesh_deform_eval(const Object *object)
bke::MeshRuntime * runtime
bke::ObjectRuntime * runtime
Array< float3, 0 > deform_cos
SharedCache< Vector< float3 > > vert_normals_deform
SharedCache< Vector< float3 > > face_normals_deform
Array< float3 > positions
OffsetIndices< int > faces
BitGroupVector grid_hidden
Span< int > grid_to_face_map
SharedCache< Vector< float3 > > face_normals_true_cache
SharedCache< Vector< float3 > > vert_normals_true_cache
SculptSession * sculpt_session
MutableVArraySpan< T > span
VectorSet< int, 0, DefaultProbingStrategy, DefaultHash< int >, DefaultEquality< int >, SimpleVectorSetSlot< int, LocalVertMapIndexT >, GuardedAllocator > LocalVertMap
FunctionRef< bool(Node &)> scb
Stack< StackItem, 100 > stack
PositionSource cache_source