Blender V5.3
pbvh.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10#include <cfloat>
11#include <utility>
12
13#include "BLI_array_utils.hh"
14#include "BLI_bit_span_ops.hh"
15#include "BLI_bounds.hh"
16#include "BLI_math_geom_c.hh"
17#include "BLI_math_matrix_c.hh"
18#include "BLI_math_vector.hh"
19#include "BLI_math_vector_c.hh"
20#include "BLI_stack.hh"
21#include "BLI_task.hh"
22#include "BLI_utildefines.hh"
23#include "BLI_vector.hh"
24#include "BLI_vector_set.hh"
25
26#include "DNA_object_types.h"
27
28#include "BKE_attribute.hh"
29#include "BKE_ccg.hh"
30#include "BKE_mesh.hh"
31#include "BKE_object.hh"
32#include "BKE_paint.hh"
33#include "BKE_paint_bvh.hh"
35#include "BKE_subdiv_ccg.hh"
36
38
39#include "PRF_profile.hh"
40
41#include "bmesh.hh"
42
43#include "pbvh_intern.hh"
44
45namespace blender {
46
47namespace bke::pbvh {
48
49#define STACK_FIXED_DEPTH 100
50
53{
54 return {float3(std::numeric_limits<float>::max()), float3(std::numeric_limits<float>::lowest())};
55}
56
58{
59 return bounds::merge(a, b);
60}
61
62int partition_along_axis(const Span<float3> face_centers,
63 MutableSpan<int> faces,
64 const int axis,
65 const float middle)
66{
67 const int *split = std::partition(faces.begin(), faces.end(), [&](const int face) {
68 return face_centers[face][axis] >= middle;
69 });
70 return split - faces.begin();
71}
72
73int partition_material_indices(const Span<int> material_indices, MutableSpan<int> faces)
74{
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; });
78 return split - faces.begin();
79}
80
81BLI_NOINLINE static void build_mesh_leaf_nodes(const int verts_num,
82 const OffsetIndices<int> faces,
83 const Span<int> corner_verts,
85{
87 Array<Array<int>> verts_per_node(nodes.size(), NoInitialization());
88 threading::parallel_for(nodes.index_range(), 8, [&](const IndexRange range) {
89 Set<int> verts;
90 for (const int i : range) {
91 MeshNode &node = nodes[i];
92
93 verts.clear();
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();
99 }
100 nodes[i].corners_num_ = corners_count;
101
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]);
105 }
106 });
107
108 Vector<int> owned_verts;
109 Vector<int> shared_verts;
110 BitVector<> vert_used(verts_num);
111 for (const int i : nodes.index_range()) {
112 MeshNode &node = nodes[i];
113
114 owned_verts.clear();
115 shared_verts.clear();
116 for (const int vert : verts_per_node[i]) {
117 if (vert_used[vert]) {
118 shared_verts.append(vert);
119 }
120 else {
121 vert_used[vert].set();
122 owned_verts.append(vert);
123 }
124 }
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);
129 }
130}
131
132bool leaf_needs_material_split(const Span<int> faces, const Span<int> material_indices)
133{
134 if (material_indices.is_empty()) {
135 return false;
136 }
137 const int first = material_indices[faces.first()];
138 return std::any_of(
139 faces.begin(), faces.end(), [&](const int face) { return material_indices[face] != first; });
140}
141
142static void build_nodes_recursive_mesh(const Span<int> material_indices,
143 const int leaf_limit,
144 const int node_index,
145 const int parent_index,
146 const std::optional<Bounds<float3>> &bounds_precalc,
147 const Span<float3> face_centers,
148 const int depth,
149 MutableSpan<int> faces,
151{
153 BLI_assert(parent_index >= -1);
154
155 MeshNode &node = nodes[node_index];
156 node.parent_ = parent_index;
157
158 /* Decide whether this is a leaf or not */
159 const bool below_leaf_limit = faces.size() <= leaf_limit || depth >= STACK_FIXED_DEPTH - 1;
160 if (below_leaf_limit) {
161 if (!leaf_needs_material_split(faces, material_indices)) {
162 node.flag_ |= Node::Leaf;
163 node.face_indices_ = faces;
164 return;
165 }
166 }
167
168 /* Add two child nodes */
169 nodes[node_index].children_offset_ = nodes.size();
170 nodes.resize(nodes.size() + 2);
171
172 int split;
173 if (!below_leaf_limit) {
175 if (bounds_precalc) {
176 bounds = *bounds_precalc;
177 }
178 else {
180 faces.index_range(),
181 1024,
183 [&](const IndexRange range, Bounds<float3> value) {
184 for (const int face : faces.slice(range)) {
185 math::min_max(face_centers[face], value.min, value.max);
186 }
187 return value;
188 },
190 }
191 const int axis = math::dominant_axis(bounds.max - bounds.min);
192
193 /* Partition primitives along that axis */
195 face_centers, faces, axis, math::midpoint(bounds.min[axis], bounds.max[axis]));
196 }
197 else {
198 /* Partition primitives by material */
199 split = partition_material_indices(material_indices, faces);
200 }
201
202 /* Build children */
203 build_nodes_recursive_mesh(material_indices,
205 nodes[node_index].children_offset_,
206 node_index,
207 std::nullopt,
208 face_centers,
209 depth + 1,
210 faces.take_front(split),
211 nodes);
212 build_nodes_recursive_mesh(material_indices,
214 nodes[node_index].children_offset_ + 1,
215 node_index,
216 std::nullopt,
217 face_centers,
218 depth + 1,
219 faces.drop_front(split),
220 nodes);
221}
222
223Tree Tree::from_spatially_organized_mesh(const Mesh &mesh)
224{
226
227 Tree pbvh(Type::Mesh);
228 const Span<float3> vert_positions = mesh.vert_positions();
229
230 const Span<MeshGroup> &spatial_groups = *mesh.runtime->spatial_groups;
231
232 if (spatial_groups.is_empty()) {
233 return pbvh;
234 }
235
236 Vector<MeshNode> &nodes = std::get<Vector<MeshNode>>(pbvh.nodes_);
237 nodes.resize(spatial_groups.size());
238
239 pbvh.prim_indices_.reinitialize(mesh.faces_num);
241
242 threading::parallel_for(nodes.index_range(), 8, [&](const IndexRange range) {
243 for (const int node_idx : range) {
244 MeshNode &pbvh_node = nodes[node_idx];
245 pbvh_node.parent_ = spatial_groups[node_idx].parent;
246
247 if (spatial_groups[node_idx].children_offset != 0) {
248 pbvh_node.children_offset_ = spatial_groups[node_idx].children_offset;
249 }
250 else {
251 pbvh_node.children_offset_ = 0;
252 pbvh_node.flag_ = Node::Leaf;
253
254 const IndexRange face_range = spatial_groups[node_idx].faces;
255 const int face_count = face_range.size();
256
257 if (face_count > 0) {
258 pbvh_node.face_indices_ = Span<int>(&pbvh.prim_indices_[face_range.start()], face_count);
259
260 pbvh_node.corners_num_ = spatial_groups[node_idx].corners_count;
261
262 pbvh_node.unique_verts_num_ = spatial_groups[node_idx].unique_verts.size();
263
264 pbvh_node.vert_indices_.reserve(spatial_groups[node_idx].unique_verts.size() +
265 spatial_groups[node_idx].shared_verts.size());
266
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);
270 }
271
272 for (const int vert_idx : spatial_groups[node_idx].shared_verts) {
273 pbvh_node.vert_indices_.add(vert_idx);
274 }
275 }
276 else {
277 pbvh_node.unique_verts_num_ = 0;
278 pbvh_node.corners_num_ = 0;
279 }
280 }
281 }
282 });
283
284 pbvh.tag_positions_changed(nodes.index_range());
285 pbvh.update_bounds_mesh(vert_positions);
286 store_bounds_orig(pbvh);
287
288 const AttributeAccessor attributes = mesh.attributes();
289 const VArraySpan hide_vert = *attributes.lookup<bool>(".hide_vert", AttrDomain::Point);
290
291 if (!hide_vert.is_empty()) {
292 threading::parallel_for(nodes.index_range(), 8, [&](const IndexRange range) {
293 for (const int i : range) {
294 node_update_visibility_mesh(hide_vert, nodes[i]);
295 }
296 });
297 }
298
299 update_mask_mesh(mesh, nodes.index_range(), pbvh);
300
301 return pbvh;
302}
303
305{
307 if (mesh.runtime->spatial_groups) {
308 return from_spatially_organized_mesh(mesh);
309 }
311 const Span<float3> vert_positions = mesh.vert_positions();
312 const OffsetIndices<int> faces = mesh.faces();
313 const Span<int> corner_verts = mesh.corner_verts();
314 if (faces.is_empty()) {
315 return pbvh;
316 }
317
318 constexpr int leaf_limit = MESH_LEAF_LIMIT;
319 static_assert(leaf_limit < std::numeric_limits<MeshNode::LocalVertMapIndexT>::max());
320
321 Array<float3> face_centers(faces.size());
323 faces.index_range(),
324 1024,
326 [&](const IndexRange range, const Bounds<float3> &init) {
327 Bounds<float3> current = init;
328 for (const int face : range) {
329 const Bounds<float3> bounds = calc_face_bounds(vert_positions,
330 corner_verts.slice(faces[face]));
331 face_centers[face] = bounds.center();
332 current = bounds::merge(current, bounds);
333 }
334 return current;
335 },
337
338 const AttributeAccessor attributes = mesh.attributes();
339 const VArraySpan hide_vert = *attributes.lookup<bool>(".hide_vert", AttrDomain::Point);
340 const VArraySpan material_index = *attributes.lookup<int>("material_index", AttrDomain::Face);
341
342 pbvh.prim_indices_.reinitialize(faces.size());
344
345 Vector<MeshNode> &nodes = std::get<Vector<MeshNode>>(pbvh.nodes_);
346 nodes.resize(1);
347 {
349 material_index, leaf_limit, 0, -1, bounds, face_centers, 0, pbvh.prim_indices_, nodes);
350 }
351
352 build_mesh_leaf_nodes(mesh.verts_num, faces, corner_verts, nodes);
353
354 pbvh.tag_positions_changed(nodes.index_range());
355
356 pbvh.update_bounds_mesh(vert_positions);
358
359 if (!hide_vert.is_empty()) {
360 threading::parallel_for(nodes.index_range(), 8, [&](const IndexRange range) {
361 for (const int i : range) {
362 node_update_visibility_mesh(hide_vert, nodes[i]);
363 }
364 });
365 }
366
367 update_mask_mesh(mesh, nodes.index_range(), pbvh);
368
369 return pbvh;
370}
371
372static void build_nodes_recursive_grids(const Span<int> material_indices,
373 const int leaf_limit,
374 const int node_index,
375 const int parent_index,
376 const std::optional<Bounds<float3>> &bounds_precalc,
377 const Span<float3> face_centers,
378 const int depth,
379 MutableSpan<int> faces,
381{
383 BLI_assert(parent_index >= -1);
384
385 GridsNode &node = nodes[node_index];
386 node.parent_ = parent_index;
387
388 /* Decide whether this is a leaf or not */
389 const bool below_leaf_limit = faces.size() <= leaf_limit || depth >= STACK_FIXED_DEPTH - 1;
390 if (below_leaf_limit) {
391 if (!leaf_needs_material_split(faces, material_indices)) {
392 node.flag_ |= Node::Leaf;
393 node.prim_indices_ = faces;
394 return;
395 }
396 }
397
398 /* Add two child nodes */
399 nodes[node_index].children_offset_ = nodes.size();
400 nodes.resize(nodes.size() + 2);
401
402 int split;
403 if (!below_leaf_limit) {
405 if (bounds_precalc) {
406 bounds = *bounds_precalc;
407 }
408 else {
410 faces.index_range(),
411 1024,
413 [&](const IndexRange range, Bounds<float3> value) {
414 for (const int face : faces.slice(range)) {
415 math::min_max(face_centers[face], value.min, value.max);
416 }
417 return value;
418 },
420 }
421 const int axis = math::dominant_axis(bounds.max - bounds.min);
422
423 /* Partition primitives along that axis */
425 face_centers, faces, axis, math::midpoint(bounds.min[axis], bounds.max[axis]));
426 }
427 else {
428 /* Partition primitives by material */
429 split = partition_material_indices(material_indices, faces);
430 }
431
432 /* Build children */
433 build_nodes_recursive_grids(material_indices,
435 nodes[node_index].children_offset_,
436 node_index,
437 std::nullopt,
438 face_centers,
439 depth + 1,
440 faces.take_front(split),
441 nodes);
442 build_nodes_recursive_grids(material_indices,
444 nodes[node_index].children_offset_ + 1,
445 node_index,
446 std::nullopt,
447 face_centers,
448 depth + 1,
449 faces.drop_front(split),
450 nodes);
451}
452
454 const Span<float3> positions,
455 const CCGKey &key,
456 const int face)
457{
459 for (const float3 &position : positions.slice(ccg::face_range(faces, key, face))) {
461 }
462 return bounds;
463}
464
465Tree Tree::from_grids(const Mesh &base_mesh, const SubdivCCG &subdiv_ccg)
466{
469 const OffsetIndices faces = base_mesh.faces();
470 if (faces.is_empty()) {
471 return pbvh;
472 }
473
474 const CCGKey key = BKE_subdiv_ccg_key_top_level(subdiv_ccg);
475 const Span<float3> positions = subdiv_ccg.positions;
476 if (positions.is_empty()) {
477 return pbvh;
478 }
479
480 /* We use a lower value here compared to regular mesh sculpting because the number of elements is
481 * on average 4x as many due to the prim_indices_ being associated with face corners, not faces.
482 */
483 constexpr int base_limit = 800;
484 const int leaf_limit = std::max(base_limit / key.grid_area, 1);
485
486 Array<float3> face_centers(faces.size());
488 faces.index_range(),
491 [&](const IndexRange range, const Bounds<float3> &init) {
492 Bounds<float3> current = init;
493 for (const int face : range) {
494 const Bounds<float3> bounds = calc_face_grid_bounds(faces, positions, key, face);
495 face_centers[face] = bounds.center();
496 current = bounds::merge(current, bounds);
497 }
498 return current;
499 },
501
502 const AttributeAccessor attributes = base_mesh.attributes();
503 const VArraySpan material_index = *attributes.lookup<int>("material_index", AttrDomain::Face);
504
505 Array<int> face_indices(faces.size());
507
508 Vector<GridsNode> &nodes = std::get<Vector<GridsNode>>(pbvh.nodes_);
509 nodes.resize(1);
510 {
512 material_index, leaf_limit, 0, -1, bounds, face_centers, 0, face_indices, nodes);
513 }
514
515 /* Convert face indices into grid indices. */
516 pbvh.prim_indices_.reinitialize(faces.total_size());
517 {
518 int offset = 0;
519 for (const int i : nodes.index_range()) {
520 for (const int face : nodes[i].prim_indices_) {
521 for (const int corner : faces[face]) {
522 pbvh.prim_indices_[offset] = corner;
523 offset++;
524 }
525 }
526 }
527 }
528
529 /* Change the nodes to reference the BVH prim_indices array instead of the local face indices. */
530 Array<int> node_grids_num(nodes.size() + 1);
531 threading::parallel_for(nodes.index_range(), 16, [&](const IndexRange range) {
532 for (const int i : range) {
533 node_grids_num[i] = offset_indices::sum_group_sizes(faces, nodes[i].prim_indices_);
534 }
535 });
537 node_grids_num);
538
539 threading::parallel_for(nodes.index_range(), 512, [&](const IndexRange range) {
540 for (const int i : range) {
541 nodes[i].prim_indices_ = pbvh.prim_indices_.as_span().slice(node_grid_offsets[i]);
542 }
543 });
544
545 pbvh.tag_positions_changed(nodes.index_range());
546
547 pbvh.update_bounds_grids(positions, key.grid_area);
548 store_bounds_orig(pbvh);
549
550 const BitGroupVector<> &grid_hidden = subdiv_ccg.grid_hidden;
551 if (!grid_hidden.is_empty()) {
552 threading::parallel_for(nodes.index_range(), 8, [&](const IndexRange range) {
553 for (const int i : range) {
554 node_update_visibility_grids(grid_hidden, nodes[i]);
555 }
556 });
557 }
558
559 update_mask_grids(subdiv_ccg, nodes.index_range(), pbvh);
560
561 return pbvh;
562}
563
564Tree::Tree(const Type type) : type_(type)
565{
566 switch (type) {
569 break;
572 break;
575 break;
576 }
577}
578
580{
581 return std::visit([](const auto &nodes) { return nodes.size(); }, this->nodes_);
582}
583
584template<> Span<MeshNode> Tree::nodes() const
585{
586 return std::get<Vector<MeshNode>>(this->nodes_);
587}
588template<> Span<GridsNode> Tree::nodes() const
589{
590 return std::get<Vector<GridsNode>>(this->nodes_);
591}
592template<> Span<BMeshNode> Tree::nodes() const
593{
594 return std::get<Vector<BMeshNode>>(this->nodes_);
595}
597{
598 return std::get<Vector<MeshNode>>(this->nodes_);
599}
601{
602 return std::get<Vector<GridsNode>>(this->nodes_);
603}
605{
606 return std::get<Vector<BMeshNode>>(this->nodes_);
607}
608
610{
611 pixels_free(this);
612}
613
615{
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);
618 node_mask.set_bits(bounds_dirty_);
619 node_mask.set_bits(normals_dirty_);
620 if (this->draw_data) {
621 this->draw_data->tag_positions_changed(node_mask);
622 }
623}
624
626{
627 visibility_dirty_.resize(std::max(visibility_dirty_.size(), node_mask.min_array_size()), false);
628 node_mask.set_bits(visibility_dirty_);
629 if (this->draw_data) {
630 this->draw_data->tag_visibility_changed(node_mask);
631 }
632}
633
635{
636 if (this->draw_data) {
637 this->draw_data->tag_topology_changed(node_mask);
638 }
639}
640
642{
643 if (this->draw_data) {
644 this->draw_data->tag_face_sets_changed(node_mask);
645 }
646}
647
648void Tree::tag_masks_changed(const IndexMask &node_mask)
649{
650 if (this->draw_data) {
651 this->draw_data->tag_masks_changed(node_mask);
652 }
653}
654
655void Tree::tag_attribute_changed(const IndexMask &node_mask, const StringRef attribute_name)
656{
657 if (this->draw_data) {
658 this->draw_data->tag_attribute_changed(node_mask, attribute_name);
659 }
660}
661
662static bool tree_is_empty(const Tree &pbvh)
663{
664 return std::visit([](const auto &nodes) { return nodes.is_empty(); }, pbvh.nodes_);
665}
666
668{
670 return std::visit([](auto &nodes) -> Node & { return nodes.first(); }, pbvh.nodes_);
671}
672
673struct StackItem {
676};
677
684
685static void pbvh_iter_begin(PBVHIter *iter, Tree &pbvh, FunctionRef<bool(Node &)> scb)
686{
687 iter->pbvh = &pbvh;
688 iter->scb = scb;
689 iter->stack.push({&first_node(pbvh), false});
690}
691
692static Node *pbvh_iter_next(PBVHIter *iter, Node::Flags leaf_flag)
693{
694 /* purpose here is to traverse tree, visiting child nodes before their
695 * parents, this order is necessary for example computing bounding boxes */
696
697 while (!iter->stack.is_empty()) {
698 StackItem item = iter->stack.pop();
699 Node *node = item.node;
700 bool revisiting = item.revisiting;
701
702 /* on a mesh with no faces this can happen
703 * can remove this check if we know meshes have at least 1 face */
704 if (node == nullptr) {
705 return nullptr;
706 }
707
708 /* revisiting node already checked */
709 if (revisiting) {
710 return node;
711 }
712
713 if (iter->scb && !iter->scb(*node)) {
714 continue; /* don't traverse, outside of search zone */
715 }
716
717 if (node->flag_ & leaf_flag) {
718 /* immediately hit leaf node */
719 return node;
720 }
721
722 /* come back later when children are done */
723 iter->stack.push({node, true});
724
725 /* push two child nodes on the stack */
726 std::visit(
727 [&](auto &nodes) {
728 iter->stack.push({&nodes[node->children_offset_ + 1], false});
729 iter->stack.push({&nodes[node->children_offset_], false});
730 },
731 iter->pbvh->nodes_);
732 }
733
734 return nullptr;
735}
736
739 const FunctionRef<std::optional<float>(const Node &)> scb,
740 const FunctionRef<void(Node &node, float *distance)> hit_fn)
741{
742 if (tree_is_empty(pbvh)) {
743 return;
744 }
745
746 /* Gather leaf nodes intersecting the ray along with the distance from the ray to the bounds. */
748 Stack<Node *, 100> stack;
749 stack.push(&first_node(pbvh));
750 while (!stack.is_empty()) {
751 Node *node = stack.pop();
752
753 const std::optional node_distance = scb(*node);
754 if (!node_distance) {
755 continue; /* don't traverse, outside of search zone */
756 }
757
758 if (node->flag_ & Node::Leaf) {
759 hits.append({*node_distance, node});
760 continue;
761 }
762
763 std::visit(
764 [&](auto &nodes) {
765 stack.push(&nodes[node->children_offset_ + 1]);
766 stack.push(&nodes[node->children_offset_]);
767 },
768 pbvh.nodes_);
769 }
770
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; });
774
775 /* Visit the nodes nearest to farthest. #hit_fn narrows #distance whenever it finds a closer hit,
776 * so once a node's bounds start further away than the closest hit so far, neither it nor any
777 * later node will contribute. */
778 float distance = FLT_MAX;
779 for (const auto &[node_distance, node] : hits) {
780 if (node_distance >= distance) {
781 break;
782 }
783 hit_fn(*node, &distance);
784 }
785}
786
792static bool mesh_topology_count_matches(const Mesh &a, const Mesh &b)
793{
794 return a.faces_num == b.faces_num && a.corners_num == b.corners_num &&
795 a.verts_num == b.verts_num;
796}
797
804
809
810static PositionSourceResult cache_source_get(const Object &object_orig, const Object &object_eval)
811{
812 const SculptSession &ss = *object_orig.runtime->sculpt_session;
813 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.data);
814 BLI_assert(bke::object::pbvh_get(object_orig)->type() == Type::Mesh);
815 if (object_orig.mode & (OB_MODE_VERTEX_PAINT | OB_MODE_WEIGHT_PAINT)) {
816 if (const Mesh *mesh_eval = BKE_object_get_evaluated_mesh_no_subsurf(&object_eval)) {
817 if (mesh_topology_count_matches(*mesh_eval, mesh_orig)) {
818 return {PositionSource::Eval, mesh_eval};
819 }
820 }
821 if (!ss.deform_cos.is_empty()) {
822 BLI_assert(ss.deform_cos.size() == mesh_orig.verts_num);
823 return {PositionSource::RuntimeDeform, nullptr};
824 }
825 if (const Mesh *mesh_eval = BKE_object_get_mesh_deform_eval(&object_eval)) {
826 return {PositionSource::EvalDeform, mesh_eval};
827 }
828 }
829
830 if (!ss.deform_cos.is_empty()) {
831 BLI_assert(ss.deform_cos.size() == mesh_orig.verts_num);
832 return {PositionSource::RuntimeDeform, nullptr};
833 }
834
835 return {PositionSource::Orig, nullptr};
836}
837
839 const Object &object_eval)
840{
841 const SculptSession &ss = *object_orig.runtime->sculpt_session;
842 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.data);
843 BLI_assert(bke::object::pbvh_get(object_orig)->type() == Type::Mesh);
844
845 const PositionSourceResult result = cache_source_get(object_orig, object_eval);
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;
852 return ss.vert_normals_deform;
854 return mesh_orig.runtime->vert_normals_true_cache;
855 }
857 return mesh_orig.runtime->vert_normals_true_cache;
858}
860 Object &object_eval)
861{
862 return const_cast<SharedCache<Vector<float3>> &>(
863 vert_normals_cache_eval(object_orig, object_eval));
864}
865
867 const Object &object_eval)
868{
869 const SculptSession &ss = *object_orig.runtime->sculpt_session;
870 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.data);
871 BLI_assert(bke::object::pbvh_get(object_orig)->type() == Type::Mesh);
872 const PositionSourceResult result = cache_source_get(object_orig, object_eval);
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;
879 return ss.face_normals_deform;
881 return mesh_orig.runtime->face_normals_true_cache;
882 }
884 return mesh_orig.runtime->face_normals_true_cache;
885}
887 Object &object_eval)
888{
889 return const_cast<SharedCache<Vector<float3>> &>(
890 face_normals_cache_eval(object_orig, object_eval));
891}
892
893static Span<float3> vert_positions_eval(const Object &object_orig, const Object &object_eval)
894{
895 const SculptSession &ss = *object_orig.runtime->sculpt_session;
896 const Mesh &mesh_orig = *id_cast<const Mesh *>(object_orig.data);
897 BLI_assert(bke::object::pbvh_get(object_orig)->type() == Type::Mesh);
898 const PositionSourceResult result = cache_source_get(object_orig, object_eval);
899 switch (result.cache_source) {
901 return result.mesh_eval->vert_positions();
903 return result.mesh_eval->vert_positions();
905 return ss.deform_cos;
907 return mesh_orig.vert_positions();
908 }
910 return mesh_orig.vert_positions();
911}
912
914{
915 SculptSession &ss = *object_orig.runtime->sculpt_session;
916 Mesh &mesh_orig = *id_cast<Mesh *>(object_orig.data);
917 BLI_assert(bke::object::pbvh_get(object_orig)->type() == Type::Mesh);
918 const PositionSourceResult result = cache_source_get(object_orig, object_eval);
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();
925 return ss.deform_cos;
927 return mesh_orig.vert_positions_for_write();
928 }
930 return mesh_orig.vert_positions_for_write();
931}
932
933Span<float3> vert_positions_eval(const Depsgraph &depsgraph, const Object &object_orig)
934{
935 const Object &object_eval = *DEG_get_evaluated(&depsgraph, &const_cast<Object &>(object_orig));
936 return vert_positions_eval(object_orig, object_eval);
937}
938
940{
941 BLI_assert(!DEG_is_original(&object_eval));
942 const Object &object_orig = *DEG_get_original(&object_eval);
943 return vert_positions_eval(object_orig, object_eval);
944}
945
946MutableSpan<float3> vert_positions_eval_for_write(const Depsgraph &depsgraph, Object &object_orig)
947{
948 Object &object_eval = *DEG_get_evaluated(&depsgraph, &object_orig);
949 return vert_positions_eval_for_write(object_orig, object_eval);
950}
951
952Span<float3> vert_normals_eval(const Depsgraph &depsgraph, const Object &object_orig)
953{
954 const Object &object_eval = *DEG_get_evaluated(&depsgraph, &object_orig);
955 return vert_normals_cache_eval(object_orig, object_eval).data();
956}
957
959{
960 BLI_assert(!DEG_is_original(&object_eval));
961 const Object &object_orig = *DEG_get_original(&object_eval);
962 return vert_normals_cache_eval(object_orig, object_eval).data();
963}
964
966{
967 BLI_assert(!DEG_is_original(&object_eval));
968 const Object &object_orig = *DEG_get_original(&object_eval);
969 return face_normals_cache_eval(object_orig, object_eval).data();
970}
971
972static void normals_calc_faces(const Span<float3> positions,
973 const OffsetIndices<int> faces,
974 const Span<int> corner_verts,
975 const Span<int> face_indices,
976 MutableSpan<float3> face_normals)
977{
979 for (const int i : face_indices) {
980 face_normals[i] = mesh::face_normal_calc(positions, corner_verts.slice(faces[i]));
981 }
982}
983
984static void calc_node_face_normals(const Span<float3> positions,
985 const OffsetIndices<int> faces,
986 const Span<int> corner_verts,
987 const Span<MeshNode> nodes,
988 const IndexMask &nodes_to_update,
989 MutableSpan<float3> face_normals)
990{
991 nodes_to_update.foreach_index(
992 [&](const int i) {
993 normals_calc_faces(positions, faces, corner_verts, nodes[i].faces(), face_normals);
994 },
996}
997
998static void normals_calc_verts_simple(const GroupedSpan<int> vert_to_face_map,
999 const Span<float3> face_normals,
1000 const Span<int> verts,
1001 MutableSpan<float3> vert_normals)
1002{
1004 for (const int vert : verts) {
1005 float3 normal(0.0f);
1006 for (const int face : vert_to_face_map[vert]) {
1007 normal += face_normals[face];
1008 }
1009 float length;
1010 vert_normals[vert] = math::normalize_and_get_length(normal, length);
1011 if (length == 0.0f) {
1012 vert_normals[vert] = float3(0, 0, 1);
1013 }
1014 }
1015}
1016
1017static void calc_shared_vert_normals(const GroupedSpan<int> vert_to_face_map,
1018 const Span<float3> face_normals,
1019 const Span<int> verts,
1020 MutableSpan<float3> vert_normals)
1021{
1022 threading::parallel_for(verts.index_range(), 1024, [&](const IndexRange range) {
1023 normals_calc_verts_simple(vert_to_face_map, face_normals, verts.slice(range), vert_normals);
1024 });
1025}
1026
1027static void calc_node_vert_normals(const GroupedSpan<int> vert_to_face_map,
1028 const Span<float3> face_normals,
1029 const Span<MeshNode> nodes,
1030 const IndexMask &nodes_to_update,
1031 MutableSpan<float3> vert_normals)
1032{
1033 nodes_to_update.foreach_index(
1034 [&](const int i) {
1035 normals_calc_verts_simple(vert_to_face_map, face_normals, nodes[i].verts(), vert_normals);
1036 },
1038}
1039
1046 const IndexMask &nodes_to_update,
1047 const int verts_num)
1048{
1050 int shared_verts_num = 0;
1051 nodes_to_update.foreach_index(
1052 [&](const int i) { shared_verts_num += nodes[i].shared_verts().size(); });
1053
1054 /* Avoid the overhead of a mesh-sized BitVector when the final number of indices is very small.
1055 * Though that overhead is quite low, so our threshold to use a BitVector instead is low. */
1056 if (int64_t(shared_verts_num) * 1024 < verts_num) {
1057 VectorSet<int> verts;
1058 verts.reserve(shared_verts_num);
1059 nodes_to_update.foreach_index(
1060 [&](const int i) { verts.add_multiple(nodes[i].shared_verts()); });
1061 return verts.extract_vector();
1062 }
1063
1064 Vector<int> verts;
1065 verts.reserve(shared_verts_num);
1066 BitVector<> visited(verts_num);
1067 nodes_to_update.foreach_index([&](const int i) {
1068 for (const int vert : nodes[i].shared_verts()) {
1069 MutableBitRef visited_vert = visited[vert];
1070 if (!visited_vert) {
1071 visited_vert.set();
1072 verts.append_unchecked(vert);
1073 }
1074 }
1075 });
1076 return verts;
1077}
1078
1079static void update_normals_mesh(Object &object_orig,
1080 Object &object_eval,
1081 const Span<MeshNode> nodes,
1082 const IndexMask &nodes_to_update)
1083{
1085 /* Position changes are tracked on a per-node level, so all the vertex and face normals for every
1086 * affected node are recalculated.
1087 *
1088 * Node bounds are built from #MeshNode::all_verts(), and nodes are tagged whenever their bounds
1089 * intersect the changed region. Therefore every face touching a moved vertex is inside a tagged
1090 * node. Callers that tag nodes without a bounds intersection test must uphold the same
1091 * guarantee.
1092 *
1093 * A face normal only depends on the positions of its own vertices, so the faces of the tagged
1094 * nodes are exactly the faces with changed normals.
1095 *
1096 * A vertex normal depends on the normals of the surrounding faces though, so every vertex of
1097 * those faces changes, including vertices that didn't move themselves. Such a vertex is still
1098 * part of the tagged node containing the changed face, but only #MeshNode::verts() is
1099 * recalculated for each node, which skips the vertices owned by a different node. That owner may
1100 * not be tagged, since it doesn't necessarily contain a face touching a moved vertex. So the
1101 * shared vertices of the tagged nodes are gathered and updated separately. */
1102 Mesh &mesh = *id_cast<Mesh *>(object_orig.data);
1103 const Span<float3> positions = bke::pbvh::vert_positions_eval_from_eval(object_eval);
1104 const OffsetIndices faces = mesh.faces();
1105 const Span<int> corner_verts = mesh.corner_verts();
1106 const GroupedSpan<int> vert_to_face_map = mesh.vert_to_face_map();
1107
1108 SharedCache<Vector<float3>> &vert_normals_cache = vert_normals_cache_eval_for_write(object_orig,
1109 object_eval);
1110 SharedCache<Vector<float3>> &face_normals_cache = face_normals_cache_eval_for_write(object_orig,
1111 object_eval);
1112
1113 Vector<int> shared_verts;
1114
1116 [&]() {
1117 if (face_normals_cache.is_dirty()) {
1118 face_normals_cache.ensure([&](Vector<float3> &r_data) {
1119 r_data.resize(faces.size());
1120 bke::mesh::normals_calc_faces(positions, faces, corner_verts, r_data);
1121 });
1122 }
1123 else {
1124 face_normals_cache.update([&](Vector<float3> &r_data) {
1125 calc_node_face_normals(positions, faces, corner_verts, nodes, nodes_to_update, r_data);
1126 });
1127 }
1128 },
1129 [&]() { shared_verts = gather_shared_verts(nodes, nodes_to_update, positions.size()); });
1130 const Span<float3> face_normals = face_normals_cache.data();
1131
1132 if (vert_normals_cache.is_dirty()) {
1133 vert_normals_cache.ensure([&](Vector<float3> &r_data) {
1134 r_data.resize(positions.size());
1136 positions, faces, corner_verts, vert_to_face_map, face_normals, r_data);
1137 });
1138 }
1139 else {
1140 vert_normals_cache.update([&](Vector<float3> &r_data) {
1141 calc_node_vert_normals(vert_to_face_map, face_normals, nodes, nodes_to_update, r_data);
1142 /* Calculated after the node vertices on purpose: a shared vertex may also be owned by
1143 * another tagged node, in which case its normal is calculated twice rather than from two
1144 * threads at the same time. */
1145 calc_shared_vert_normals(vert_to_face_map, face_normals, shared_verts, r_data);
1146 });
1147 }
1148}
1149
1150void Tree::update_normals(Object &object_orig, Object &object_eval)
1151{
1153 IndexMaskMemory memory;
1154 const IndexMask nodes_to_update = IndexMask::from_bits(normals_dirty_, memory);
1155
1156 switch (this->type()) {
1157 case Type::Mesh: {
1158 update_normals_mesh(object_orig, object_eval, this->nodes<MeshNode>(), nodes_to_update);
1159 break;
1160 }
1161 case Type::Grids: {
1162 SculptSession &ss = *object_orig.runtime->sculpt_session;
1163 SubdivCCG &subdiv_ccg = *ss.subdiv_ccg;
1165 IndexMaskMemory memory;
1166 const IndexMask faces_to_update = nodes_to_face_selection_grids(
1167 subdiv_ccg, nodes, nodes_to_update, memory);
1168 BKE_subdiv_ccg_update_normals(subdiv_ccg, faces_to_update);
1169 break;
1170 }
1171 case Type::BMesh: {
1172 bmesh_normals_update(*this, nodes_to_update);
1173 break;
1174 }
1175 }
1176 normals_dirty_.clear_and_shrink();
1177}
1178
1179void update_normals(const Depsgraph &depsgraph, Object &object_orig, Tree &pbvh)
1180{
1181 BLI_assert(DEG_is_original(&object_orig));
1182 Object &object_eval = *DEG_get_evaluated(&depsgraph, &object_orig);
1183 pbvh.update_normals(object_orig, object_eval);
1184}
1185
1187{
1188 /* Updating the original object's mesh normals caches is necessary because we skip dependency
1189 * graph updates for sculpt deformations in some cases (so the evaluated object doesn't contain
1190 * their result), and also because (currently) sculpt deformations skip tagging the mesh normals
1191 * caches dirty. */
1192 Object &object_orig = *DEG_get_original(&object_eval);
1193 pbvh.update_normals(object_orig, object_eval);
1194}
1195
1197{
1199 for (const int vert : node.all_verts()) {
1200 math::min_max(positions[vert], bounds.min, bounds.max);
1201 }
1202 node.bounds_ = bounds;
1203}
1204
1205void update_node_bounds_grids(const int grid_area, const Span<float3> positions, GridsNode &node)
1206{
1208 for (const int grid : node.grids()) {
1209 for (const float3 &position : positions.slice(bke::ccg::grid_range(grid_area, grid))) {
1211 }
1212 }
1213 node.bounds_ = bounds;
1214}
1215
1217{
1219 for (const BMVert *vert : node.bm_unique_verts_) {
1220 math::min_max(float3(vert->co), bounds.min, bounds.max);
1221 }
1222 for (const BMVert *vert : node.bm_other_verts_) {
1223 math::min_max(float3(vert->co), bounds.min, bounds.max);
1224 }
1225 node.bounds_ = bounds;
1226}
1227
1229{
1230 IndexMaskMemory memory;
1231 const IndexMask node_mask = IndexMask::from_bits(bounds_dirty_, memory);
1232
1233 std::visit(
1234 [&](auto &nodes) {
1235 Set<int> nodes_to_update;
1236 nodes_to_update.reserve(node_mask.size());
1237
1238 node_mask.foreach_index([&](int i) {
1239 if (std::optional<int> parent = nodes[i].parent()) {
1240 nodes_to_update.add(*parent);
1241 }
1242 });
1243
1244 while (!nodes_to_update.is_empty()) {
1245 const int node_index = *nodes_to_update.begin();
1246 nodes_to_update.remove(node_index);
1247
1248 auto &node = nodes[node_index];
1249 const Bounds<float3> old_bounds = node.bounds_;
1250
1251 const Bounds<float3> bounds1 = nodes[node.children_offset_].bounds_;
1252 const Bounds<float3> bounds2 = nodes[node.children_offset_ + 1].bounds_;
1253 node.bounds_ = bounds::merge(bounds1, bounds2);
1254
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;
1258
1259 if (bounds_changed && parent) {
1260 nodes_to_update.add(*parent);
1261 }
1262 }
1263 },
1264 this->nodes_);
1265 bounds_dirty_.clear_and_shrink();
1266}
1267
1268void Tree::update_bounds_mesh(const Span<float3> vert_positions)
1269{
1270 IndexMaskMemory memory;
1271 const IndexMask nodes_to_update = IndexMask::from_bits(bounds_dirty_, memory);
1272 if (nodes_to_update.is_empty()) {
1273 return;
1274 }
1276 nodes_to_update.foreach_index(
1277 [&](const int i) { update_node_bounds_mesh(vert_positions, nodes[i]); },
1280}
1281
1282void Tree::update_bounds_grids(const Span<float3> positions, const int grid_area)
1283{
1284 IndexMaskMemory memory;
1285 const IndexMask nodes_to_update = IndexMask::from_bits(bounds_dirty_, memory);
1286 if (nodes_to_update.is_empty()) {
1287 return;
1288 }
1290 nodes_to_update.foreach_index(
1291 [&](const int i) { update_node_bounds_grids(grid_area, positions, nodes[i]); },
1294}
1295
1297{
1298 IndexMaskMemory memory;
1299 const IndexMask nodes_to_update = IndexMask::from_bits(bounds_dirty_, memory);
1300 if (nodes_to_update.is_empty()) {
1301 return;
1302 }
1304 nodes_to_update.foreach_index([&](const int i) { update_node_bounds_bmesh(nodes[i]); },
1307}
1308
1309void Tree::update_bounds(const Depsgraph &depsgraph, const Object &object)
1310{
1312 switch (this->type()) {
1313 case Type::Mesh: {
1314 const Span<float3> positions = bke::pbvh::vert_positions_eval(depsgraph, object);
1315 this->update_bounds_mesh(positions);
1316 break;
1317 }
1318 case Type::Grids: {
1319 const SculptSession &ss = *object.runtime->sculpt_session;
1320 const SubdivCCG &subdiv_ccg = *ss.subdiv_ccg;
1321 this->update_bounds_grids(subdiv_ccg.positions, subdiv_ccg.grid_area);
1322 break;
1323 }
1324 case Type::BMesh: {
1325 const SculptSession &ss = *object.runtime->sculpt_session;
1326 this->update_bounds_bmesh(*ss.bm);
1327 break;
1328 }
1329 }
1330}
1331
1333{
1334 std::visit(
1335 [](auto &nodes) {
1336 threading::parallel_for(nodes.index_range(), 256, [&](const IndexRange range) {
1337 for (const int i : range) {
1338 nodes[i].bounds_orig_ = nodes[i].bounds_;
1339 }
1340 });
1341 },
1342 pbvh.nodes_);
1343}
1344
1346{
1347 const Span<int> verts = node.all_verts();
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; });
1352 SET_FLAG_FROM_TEST(node.flag_, fully_masked, Node::FullyMasked);
1353 SET_FLAG_FROM_TEST(node.flag_, fully_unmasked, Node::FullyUnmasked);
1354}
1355
1356void update_mask_mesh(const Mesh &mesh, const IndexMask &node_mask, Tree &pbvh)
1357{
1358 const MutableSpan<MeshNode> nodes = pbvh.nodes<MeshNode>();
1359 const AttributeAccessor attributes = mesh.attributes();
1360 const VArraySpan<float> mask = *attributes.lookup<float>(".sculpt_mask", AttrDomain::Point);
1361 if (mask.is_empty()) {
1362 node_mask.foreach_index([&](const int i) {
1363 nodes[i].flag_ &= ~Node::FullyMasked;
1364 nodes[i].flag_ |= Node::FullyUnmasked;
1365 });
1366 return;
1367 }
1368
1369 node_mask.foreach_index([&](const int i) { node_update_mask_mesh(mask, nodes[i]); },
1371}
1372
1374{
1375 bool fully_masked = true;
1376 bool fully_unmasked = true;
1377 for (const int grid : node.grids()) {
1378 for (const float mask : masks.slice(bke::ccg::grid_range(key, grid))) {
1379 fully_masked &= mask == 1.0f;
1380 fully_unmasked &= mask <= 0.0f;
1381 }
1382 }
1383 SET_FLAG_FROM_TEST(node.flag_, fully_masked, Node::FullyMasked);
1384 SET_FLAG_FROM_TEST(node.flag_, fully_unmasked, Node::FullyUnmasked);
1385}
1386
1387void update_mask_grids(const SubdivCCG &subdiv_ccg, const IndexMask &node_mask, Tree &pbvh)
1388{
1389 const MutableSpan<GridsNode> nodes = pbvh.nodes<GridsNode>();
1390 const CCGKey key = BKE_subdiv_ccg_key_top_level(subdiv_ccg);
1391 if (subdiv_ccg.masks.is_empty()) {
1392 node_mask.foreach_index([&](const int i) {
1393 nodes[i].flag_ &= ~Node::FullyMasked;
1394 nodes[i].flag_ |= Node::FullyUnmasked;
1395 });
1396 return;
1397 }
1398
1399 node_mask.foreach_index(
1400 [&](const int i) { node_update_mask_grids(key, subdiv_ccg.masks, nodes[i]); },
1402}
1403
1404void node_update_mask_bmesh(const int mask_offset, BMeshNode &node)
1405{
1406 BLI_assert(mask_offset != -1);
1407 bool fully_masked = true;
1408 bool fully_unmasked = true;
1409 for (const BMVert *vert : node.bm_unique_verts_) {
1410 fully_masked &= BM_ELEM_CD_GET_FLOAT(vert, mask_offset) == 1.0f;
1411 fully_unmasked &= BM_ELEM_CD_GET_FLOAT(vert, mask_offset) <= 0.0f;
1412 }
1413 for (const BMVert *vert : node.bm_other_verts_) {
1414 fully_masked &= BM_ELEM_CD_GET_FLOAT(vert, mask_offset) == 1.0f;
1415 fully_unmasked &= BM_ELEM_CD_GET_FLOAT(vert, mask_offset) <= 0.0f;
1416 }
1417 SET_FLAG_FROM_TEST(node.flag_, fully_masked, Node::FullyMasked);
1418 SET_FLAG_FROM_TEST(node.flag_, fully_unmasked, Node::FullyUnmasked);
1419}
1420
1421void update_mask_bmesh(const BMesh &bm, const IndexMask &node_mask, Tree &pbvh)
1422{
1423 const MutableSpan<BMeshNode> nodes = pbvh.nodes<BMeshNode>();
1424 const int offset = CustomData_get_offset_named(&bm.vdata, CD_PROP_FLOAT, ".sculpt_mask");
1425 if (offset == -1) {
1426 node_mask.foreach_index([&](const int i) {
1427 nodes[i].flag_ &= ~Node::FullyMasked;
1428 nodes[i].flag_ |= Node::FullyUnmasked;
1429 });
1430 return;
1431 }
1432
1433 node_mask.foreach_index([&](const int i) { node_update_mask_bmesh(offset, nodes[i]); },
1435}
1436
1438{
1439 BLI_assert(!hide_vert.is_empty());
1440 const Span<int> verts = node.all_verts();
1441 const bool fully_hidden = std::all_of(
1442 verts.begin(), verts.end(), [&](const int vert) { return hide_vert[vert]; });
1443 SET_FLAG_FROM_TEST(node.flag_, fully_hidden, Node::FullyHidden);
1444}
1445
1448 const IndexMask &node_mask)
1449{
1450 const AttributeAccessor attributes = mesh.attributes();
1451 const VArraySpan<bool> hide_vert = *attributes.lookup<bool>(".hide_vert", AttrDomain::Point);
1452 if (hide_vert.is_empty()) {
1453 node_mask.foreach_index([&](const int i) { nodes[i].flag_ &= ~Node::FullyHidden; });
1454 return;
1455 }
1456
1457 node_mask.foreach_index([&](const int i) { node_update_visibility_mesh(hide_vert, nodes[i]); },
1459}
1460
1462{
1463 BLI_assert(!grid_hidden.is_empty());
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]);
1467 });
1468 SET_FLAG_FROM_TEST(node.flag_, fully_hidden, Node::FullyHidden);
1469}
1470
1471static void update_visibility_grids(const SubdivCCG &subdiv_ccg,
1473 const IndexMask &node_mask)
1474{
1475 const BitGroupVector<> &grid_hidden = subdiv_ccg.grid_hidden;
1476 if (grid_hidden.is_empty()) {
1477 node_mask.foreach_index([&](const int i) { nodes[i].flag_ &= ~Node::FullyHidden; });
1478 return;
1479 }
1480
1481 node_mask.foreach_index(
1482 [&](const int i) { node_update_visibility_grids(grid_hidden, nodes[i]); },
1484}
1485
1487{
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);
1491 });
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);
1495 });
1496 SET_FLAG_FROM_TEST(node.flag_, unique_hidden && other_hidden, Node::FullyHidden);
1497}
1498
1500{
1501 node_mask.foreach_index([&](const int i) { node_update_visibility_bmesh(nodes[i]); },
1503}
1504
1506{
1508 IndexMaskMemory memory;
1509 const IndexMask node_mask = IndexMask::from_bits(visibility_dirty_, memory);
1510 if (node_mask.is_empty()) {
1511 return;
1512 }
1513 visibility_dirty_.clear_and_shrink();
1514 switch (this->type()) {
1515 case Type::Mesh: {
1516 const Mesh &mesh = *id_cast<const Mesh *>(object.data);
1517 update_visibility_faces(mesh, this->nodes<MeshNode>(), node_mask);
1518 break;
1519 }
1520 case Type::Grids: {
1521 const SculptSession &ss = *object.runtime->sculpt_session;
1522 update_visibility_grids(*ss.subdiv_ccg, this->nodes<GridsNode>(), node_mask);
1523 break;
1524 }
1525 case Type::BMesh: {
1526 update_visibility_bmesh(this->nodes<BMeshNode>(), node_mask);
1527 break;
1528 }
1529 }
1530}
1531
1532int count_grid_quads(const BitGroupVector<> &grid_hidden,
1533 const Span<int> grid_indices,
1534 int gridsize,
1535 int display_gridsize)
1536{
1537 const int gridarea = (gridsize - 1) * (gridsize - 1);
1538 if (grid_hidden.is_empty()) {
1539 return gridarea * grid_indices.size();
1540 }
1541
1542 /* grid hidden layer is present, so have to check each grid for
1543 * visibility */
1544
1545 int depth1 = int(log2(double(gridsize) - 1.0) + DBL_EPSILON);
1546 int depth2 = int(log2(double(display_gridsize) - 1.0) + DBL_EPSILON);
1547
1548 int skip = depth2 < depth1 ? 1 << (depth1 - depth2 - 1) : 1;
1549
1550 int totquad = 0;
1551 for (const int grid : grid_indices) {
1552 const BoundedBitSpan gh = grid_hidden[grid];
1553 /* grid hidden are present, have to check each element */
1554 for (int y = 0; y < gridsize - skip; y += skip) {
1555 for (int x = 0; x < gridsize - skip; x += skip) {
1556 if (!BKE_paint_is_grid_face_hidden(gh, gridsize, x, y)) {
1557 totquad++;
1558 }
1559 }
1560 }
1561 }
1562
1563 return totquad;
1564}
1565
1566} // namespace bke::pbvh
1567
1568namespace bke::pbvh {
1569
1571 const Span<GridsNode> nodes,
1572 const IndexMask &nodes_mask,
1573 IndexMaskMemory &memory)
1574{
1575 const Span<int> grid_to_face_map = subdiv_ccg.grid_to_face_map;
1576 /* Using a #VectorSet for index deduplication would also work, but the performance gets much
1577 * worse with large selections since the loop would be single-threaded. A boolean array has an
1578 * overhead regardless of selection size, but that is small. */
1579 Array<bool> faces_to_update(subdiv_ccg.faces.size(), false);
1580 nodes_mask.foreach_index(
1581 [&](const int i) {
1582 for (const int grid : nodes[i].grids()) {
1583 faces_to_update[grid_to_face_map[grid]] = true;
1584 }
1585 },
1587 return IndexMask::from_bools(faces_to_update, memory);
1588}
1589
1591{
1592 return std::visit(
1593 [](auto &nodes) -> Bounds<float3> {
1594 if (nodes.is_empty()) {
1595 return Bounds<float3>(float3(0));
1596 }
1597 return nodes.first().bounds_;
1598 },
1599 pbvh.nodes_);
1600}
1601
1602} // namespace bke::pbvh
1603
1604/***************************** Node Access ***********************************/
1605
1607{
1608 if (pbvh.pixels_) {
1609 pbvh.pixels_->flags.dirty = true;
1610 }
1611}
1612
1614{
1616
1617 if (fully_hidden) {
1619 }
1620 else {
1622 }
1623}
1624
1629
1631{
1633
1634 if (fully_masked) {
1636 }
1637 else {
1639 }
1640}
1641
1646
1648{
1650
1651 if (fully_masked) {
1653 }
1654 else {
1656 }
1657}
1658
1663
1664namespace bke::pbvh {
1665
1667 const GridsNode &node,
1668 Vector<int> &faces)
1669{
1670 faces.clear();
1671 const Span<int> grid_to_face_map = subdiv_ccg.grid_to_face_map;
1672 int prev_face = -1;
1673 for (const int grid : node.grids()) {
1674 const int face = grid_to_face_map[grid];
1675 if (face != prev_face) {
1676 faces.append(face);
1677 prev_face = face;
1678 }
1679 }
1680 return faces.as_span();
1681}
1682
1683} // namespace bke::pbvh
1684
1686 Span<float3> &r_orig_positions,
1687 Span<int3> &r_orig_tris)
1688{
1689 r_orig_positions = node.orig_positions_;
1690 r_orig_tris = node.orig_tris_;
1691}
1692
1693/********************************* Ray-cast ***********************************/
1694
1695namespace bke::pbvh {
1696
1701
1702static std::optional<float> ray_aabb_intersect(const Node &node, const RaycastData &rcd)
1703{
1704 const Bounds<float3> &bounds = rcd.original ? node.bounds_orig_ : node.bounds_;
1705 float distance;
1706 if (!isect_ray_aabb_v3(&rcd.ray, bounds.min, bounds.max, &distance)) {
1707 return std::nullopt;
1708 }
1709 return distance;
1710}
1711
1713 const FunctionRef<void(Node &node, float *distance)> hit_fn,
1714 const float3 &ray_start,
1715 const float3 &ray_normal,
1716 bool original)
1717{
1719 RaycastData rcd;
1720
1721 isect_ray_aabb_v3_precalc(&rcd.ray, ray_start, ray_normal);
1722 rcd.original = original;
1723
1725 pbvh, [&](const Node &node) { return ray_aabb_intersect(node, rcd); }, hit_fn);
1726}
1727
1729 const IsectRayPrecalc *isect_precalc,
1730 const float3 &t0,
1731 const float3 &t1,
1732 const float3 &t2,
1733 const float3 &t3,
1734 float *depth)
1735{
1736 float depth_test;
1737
1738 if ((isect_ray_tri_watertight_v3(ray_start, isect_precalc, t0, t1, t2, &depth_test, nullptr) &&
1739 (depth_test < *depth)) ||
1740 (isect_ray_tri_watertight_v3(ray_start, isect_precalc, t0, t2, t3, &depth_test, nullptr) &&
1741 (depth_test < *depth)))
1742 {
1743 *depth = depth_test;
1744 return true;
1745 }
1746
1747 return false;
1748}
1749
1750bool ray_face_intersection_tri(const float3 &ray_start,
1751 const IsectRayPrecalc *isect_precalc,
1752 const float3 &t0,
1753 const float3 &t1,
1754 const float3 &t2,
1755 float *depth)
1756{
1757 float depth_test;
1758 if (isect_ray_tri_watertight_v3(ray_start, isect_precalc, t0, t1, t2, &depth_test, nullptr) &&
1759 (depth_test < *depth))
1760 {
1761 *depth = depth_test;
1762 return true;
1763 }
1764
1765 return false;
1766}
1767
1768/* Take advantage of the fact we know this won't be an intersection.
1769 * Just handle ray-tri edges. */
1770static float dist_squared_ray_to_tri_v3_fast(const float3 &ray_origin,
1771 const float3 &ray_direction,
1772 const float3 &v0,
1773 const float3 &v1,
1774 const float3 &v2,
1775 float3 &r_point,
1776 float *r_depth)
1777{
1778 const float *tri[3] = {v0, v1, v2};
1779 float dist_sq_best = FLT_MAX;
1780 for (int i = 0, j = 2; i < 3; j = i++) {
1781 float3 point_test;
1782 float depth_test = FLT_MAX;
1783 const float dist_sq_test = dist_squared_ray_to_seg_v3(
1784 ray_origin, ray_direction, tri[i], tri[j], point_test, &depth_test);
1785 if (dist_sq_test < dist_sq_best || i == 0) {
1786 copy_v3_v3(r_point, point_test);
1787 *r_depth = depth_test;
1788 dist_sq_best = dist_sq_test;
1789 }
1790 }
1791 return dist_sq_best;
1792}
1793
1794bool ray_face_nearest_quad(const float3 &ray_start,
1795 const float3 &ray_normal,
1796 const float3 &t0,
1797 const float3 &t1,
1798 const float3 &t2,
1799 const float3 &t3,
1800 float *r_depth,
1801 float *dist_sq)
1802{
1803 float dist_sq_test;
1804 float3 co;
1805 float depth_test;
1806
1807 if ((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
1808 ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)
1809 {
1810 *dist_sq = dist_sq_test;
1811 *r_depth = depth_test;
1812 if ((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
1813 ray_start, ray_normal, t0, t2, t3, co, &depth_test)) < *dist_sq)
1814 {
1815 *dist_sq = dist_sq_test;
1816 *r_depth = depth_test;
1817 }
1818 return true;
1819 }
1820
1821 return false;
1822}
1823
1824bool ray_face_nearest_tri(const float3 &ray_start,
1825 const float3 &ray_normal,
1826 const float3 &t0,
1827 const float3 &t1,
1828 const float3 &t2,
1829 float *r_depth,
1830 float *dist_sq)
1831{
1832 float dist_sq_test;
1833 float3 co;
1834 float depth_test;
1835
1836 if ((dist_sq_test = dist_squared_ray_to_tri_v3_fast(
1837 ray_start, ray_normal, t0, t1, t2, co, &depth_test)) < *dist_sq)
1838 {
1839 *dist_sq = dist_sq_test;
1840 *r_depth = depth_test;
1841 return true;
1842 }
1843
1844 return false;
1845}
1846
1847static void calc_mesh_intersect_data(const Span<int> corner_verts,
1848 const Span<int3> corner_tris,
1849 const float3 &ray_start,
1850 const float3 &ray_normal,
1851 const int face_index,
1852 const int tri_index,
1853 const std::array<const float *, 3> co,
1854 const float depth,
1855 int &r_active_vertex,
1856 int &r_active_face_index,
1857 float3 &r_face_normal)
1858
1859{
1860 float3 nearest_vertex_co(0.0f);
1861 normal_tri_v3(r_face_normal, co[0], co[1], co[2]);
1862
1863 const float3 location = ray_start + ray_normal * depth;
1864 for (int i = 0; i < co.size(); i++) {
1865 /* Always assign nearest_vertex_co in the first iteration to avoid comparison against
1866 * uninitialized values. This stores the closest vertex in the current intersecting
1867 * triangle. */
1868 if (i == 0 ||
1869 len_squared_v3v3(location, co[i]) < len_squared_v3v3(location, nearest_vertex_co))
1870 {
1871 nearest_vertex_co = co[i];
1872 r_active_vertex = corner_verts[corner_tris[tri_index][i]];
1873 r_active_face_index = face_index;
1874 }
1875 }
1876}
1877
1879 const Span<float3> node_positions,
1880 const Span<float3> vert_positions,
1881 const OffsetIndices<int> faces,
1882 const Span<int> corner_verts,
1883 const Span<int3> corner_tris,
1884 const Span<bool> hide_poly,
1885 const float3 &ray_start,
1886 const float3 &ray_normal,
1887 IsectRayPrecalc *isect_precalc,
1888 float *depth,
1889 int &r_active_vertex,
1890 int &r_active_face_index,
1891 float3 &r_face_normal)
1892{
1893 const Span<int> face_indices = node.faces();
1894
1895 bool hit = false;
1896 if (node_positions.is_empty()) {
1897 for (const int i : face_indices.index_range()) {
1898 const int face_i = face_indices[i];
1899 if (!hide_poly.is_empty() && hide_poly[face_i]) {
1900 continue;
1901 }
1902
1903 for (const int tri_i : bke::mesh::face_triangles_range(faces, 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]]]}};
1908 if (ray_face_intersection_tri(ray_start, isect_precalc, co[0], co[1], co[2], depth)) {
1909 hit = true;
1910 calc_mesh_intersect_data(corner_verts,
1911 corner_tris,
1912 ray_start,
1913 ray_normal,
1914 face_i,
1915 tri_i,
1916 co,
1917 *depth,
1918 r_active_vertex,
1919 r_active_face_index,
1920 r_face_normal);
1921 }
1922 }
1923 }
1924 }
1925 else {
1926 const MeshNode::LocalVertMap &vert_map = node.vert_indices_;
1927 for (const int i : face_indices.index_range()) {
1928 const int face_i = face_indices[i];
1929 if (!hide_poly.is_empty() && hide_poly[face_i]) {
1930 continue;
1931 }
1932
1933 for (const int tri_i : bke::mesh::face_triangles_range(faces, 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]])]}};
1939 if (ray_face_intersection_tri(ray_start, isect_precalc, co[0], co[1], co[2], depth)) {
1940 hit = true;
1941 calc_mesh_intersect_data(corner_verts,
1942 corner_tris,
1943 ray_start,
1944 ray_normal,
1945 face_i,
1946 tri_i,
1947 co,
1948 *depth,
1949 r_active_vertex,
1950 r_active_face_index,
1951 r_face_normal);
1952 }
1953 }
1954 }
1955 }
1956
1957 return hit;
1958}
1959
1960static void calc_grids_intersect_data(const float3 &ray_start,
1961 const float3 &ray_normal,
1962 const int grid,
1963 const short x,
1964 const short y,
1965 const std::array<const float *, 4> co,
1966 const float depth,
1967 SubdivCCGCoord &r_active_vertex,
1968 int &r_active_grid_index,
1969 float3 &r_face_normal)
1970
1971{
1972 float3 nearest_vertex_co;
1973 normal_quad_v3(r_face_normal, co[0], co[1], co[2], co[3]);
1974
1975 const float3 location = ray_start + ray_normal * depth;
1976
1977 constexpr short x_it[4] = {0, 1, 1, 0};
1978 constexpr short y_it[4] = {1, 1, 0, 0};
1979
1980 for (int i = 0; i < co.size(); i++) {
1981 /* Always assign nearest_vertex_co in the first iteration to avoid comparison against
1982 * uninitialized values. This stores the closest vertex in the current intersecting
1983 * quad. */
1984 if (i == 0 ||
1985 len_squared_v3v3(location, co[i]) < len_squared_v3v3(location, nearest_vertex_co))
1986 {
1987 copy_v3_v3(nearest_vertex_co, co[i]);
1988 r_active_vertex = SubdivCCGCoord{grid, short(x + x_it[i]), short(y + y_it[i])};
1989 }
1990 }
1991 r_active_grid_index = grid;
1992}
1993
1994bool node_raycast_grids(const SubdivCCG &subdiv_ccg,
1995 GridsNode &node,
1996 const Span<float3> node_positions,
1997 const float3 &ray_start,
1998 const float3 &ray_normal,
1999 const IsectRayPrecalc *isect_precalc,
2000 float *depth,
2001 SubdivCCGCoord &r_active_vertex,
2002 int &r_active_grid_index,
2003 float3 &r_face_normal)
2004{
2005 const CCGKey key = BKE_subdiv_ccg_key_top_level(subdiv_ccg);
2006 const Span<int> grids = node.grids();
2007 const int grid_size = key.grid_size;
2008 bool hit = false;
2009 const BitGroupVector<> &grid_hidden = subdiv_ccg.grid_hidden;
2010 const Span<float3> positions = subdiv_ccg.positions;
2011
2012 if (node_positions.is_empty()) {
2013 for (const int grid : grids) {
2014 const Span<float3> grid_positions = positions.slice(bke::ccg::grid_range(key, grid));
2015 for (const short y : IndexRange(grid_size - 1)) {
2016 for (const short x : IndexRange(grid_size - 1)) {
2017 if (!grid_hidden.is_empty()) {
2018 if (BKE_paint_is_grid_face_hidden(grid_hidden[grid], grid_size, x, y)) {
2019 continue;
2020 }
2021 }
2022 const std::array<const float *, 4> co{
2023 {grid_positions[CCG_grid_xy_to_index(grid_size, x, y + 1)],
2024 grid_positions[CCG_grid_xy_to_index(grid_size, x + 1, y + 1)],
2025 grid_positions[CCG_grid_xy_to_index(grid_size, x + 1, y)],
2026 grid_positions[CCG_grid_xy_to_index(grid_size, x, y)]}};
2028 ray_start, isect_precalc, co[0], co[1], co[2], co[3], depth))
2029 {
2030 hit = true;
2031 calc_grids_intersect_data(ray_start,
2032 ray_normal,
2033 grid,
2034 x,
2035 y,
2036 co,
2037 *depth,
2038 r_active_vertex,
2039 r_active_grid_index,
2040 r_face_normal);
2041 }
2042 }
2043 }
2044 }
2045 }
2046 else {
2047 for (const int i : grids.index_range()) {
2048 const int grid = grids[i];
2049 const Span<float3> grid_positions = node_positions.slice(bke::ccg::grid_range(key, i));
2050 for (const short y : IndexRange(grid_size - 1)) {
2051 for (const short x : IndexRange(grid_size - 1)) {
2052 if (!grid_hidden.is_empty()) {
2053 if (BKE_paint_is_grid_face_hidden(grid_hidden[grid], grid_size, x, y)) {
2054 continue;
2055 }
2056 }
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))
2063 {
2064 hit = true;
2065 calc_grids_intersect_data(ray_start,
2066 ray_normal,
2067 grid,
2068 x,
2069 y,
2070 co,
2071 *depth,
2072 r_active_vertex,
2073 r_active_grid_index,
2074 r_face_normal);
2075 }
2076 }
2077 }
2078 }
2079 }
2080
2081 return hit;
2082}
2083
2085 Tree &pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3])
2086{
2087 if (tree_is_empty(pbvh)) {
2088 return;
2089 }
2090 float rootmin_start, rootmin_end;
2091 Bounds<float3> bb_root;
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};
2097
2098 if (original) {
2099 bb_root = first_node(pbvh).bounds_orig();
2100 }
2101 else {
2102 bb_root = first_node(pbvh).bounds();
2103 }
2104
2105 /* Calc rough clipping to avoid overflow later. See #109555. */
2106 float mat[3][3];
2107 axis_dominant_v3_to_m3(mat, ray_normal);
2108 float a[3], b[3], min[3] = {FLT_MAX, FLT_MAX, FLT_MAX}, max[3] = {FLT_MIN, FLT_MIN, FLT_MIN};
2109
2110 /* Compute AABB bounds rotated along ray_normal. */
2111 copy_v3_v3(a, bb_root.min);
2112 copy_v3_v3(b, bb_root.max);
2113 mul_m3_v3(mat, a);
2114 mul_m3_v3(mat, b);
2115 minmax_v3v3_v3(min, max, a);
2117
2118 float cent[3];
2119
2120 /* Find midpoint of aabb on ray. */
2121 mid_v3_v3v3(cent, bb_root.min, bb_root.max);
2122 float t = line_point_factor_v3(cent, ray_start, ray_end);
2123 interp_v3_v3v3(cent, ray_start, ray_end, t);
2124
2125 /* Compute rough interval. */
2126 float dist = max[2] - min[2];
2127 madd_v3_v3v3fl(ray_start, cent, ray_normal, -dist);
2128 madd_v3_v3v3fl(ray_end, cent, ray_normal, dist);
2129
2130 /* Slightly offset min and max in case we have a zero width node
2131 * (due to a plane mesh for instance), or faces very close to the bounding box boundary. */
2132 mid_v3_v3v3(bb_center, bb_root.max, bb_root.min);
2133 /* Diff should be same for both min/max since it's calculated from center. */
2134 sub_v3_v3v3(bb_diff, bb_root.max, bb_center);
2135 /* Handles case of zero width bb. */
2136 add_v3_v3(bb_diff, offset_vec);
2137 madd_v3_v3v3fl(bb_root.max, bb_center, bb_diff, offset);
2138 madd_v3_v3v3fl(bb_root.min, bb_center, bb_diff, -offset);
2139
2140 /* Final projection of start ray. */
2141 isect_ray_aabb_v3_precalc(&ray, ray_start, ray_normal);
2142 if (!isect_ray_aabb_v3(&ray, bb_root.min, bb_root.max, &rootmin_start)) {
2143 return;
2144 }
2145
2146 /* Final projection of end ray. */
2147 mul_v3_v3fl(ray_normal_inv, ray_normal, -1.0);
2148 isect_ray_aabb_v3_precalc(&ray, ray_end, ray_normal_inv);
2149 /* Unlikely to fail exiting if entering succeeded, still keep this here. */
2150 if (!isect_ray_aabb_v3(&ray, bb_root.min, bb_root.max, &rootmin_end)) {
2151 return;
2152 }
2153
2154 /*
2155 * As a last-ditch effort to correct floating point overflow compute
2156 * and add an epsilon if rootmin_start == rootmin_end.
2157 */
2158
2159 float epsilon = (std::nextafter(rootmin_start, rootmin_start + 1000.0f) - rootmin_start) *
2160 5000.0f;
2161
2162 if (rootmin_start == rootmin_end) {
2163 rootmin_start -= epsilon;
2164 rootmin_end += epsilon;
2165 }
2166
2167 madd_v3_v3v3fl(ray_start, ray_start, ray_normal, rootmin_start);
2168 madd_v3_v3v3fl(ray_end, ray_end, ray_normal_inv, rootmin_end);
2169}
2170
2171/* -------------------------------------------------------------------- */
2172
2173static std::optional<float> nearest_to_ray_aabb_dist_sq(
2174 const Node &node, const DistRayAABB_Precalc &dist_ray_to_aabb_precalc, const bool original)
2175{
2176 const Bounds<float3> &bounds = original ? node.bounds_orig_ : node.bounds_;
2177
2178 float co_dummy[3], depth;
2180 &dist_ray_to_aabb_precalc, bounds.min, bounds.max, co_dummy, &depth);
2181 /* Ideally we would skip distances outside the range. */
2182 if (depth <= 0.0f) {
2183 return std::nullopt;
2184 }
2185 return distance;
2186}
2187
2189 const FunctionRef<void(Node &node, float *distance)> fn,
2190 const float3 &ray_start,
2191 const float3 &ray_normal,
2192 const bool original)
2193{
2194 const DistRayAABB_Precalc ray_dist_precalc = dist_squared_ray_to_aabb_v3_precalc(ray_start,
2195 ray_normal);
2196
2198 pbvh,
2199 [&](const Node &node) {
2200 return nearest_to_ray_aabb_dist_sq(node, ray_dist_precalc, original);
2201 },
2202 fn);
2203}
2204
2206 const Span<float3> node_positions,
2207 const Span<float3> vert_positions,
2208 const OffsetIndices<int> faces,
2209 const Span<int> corner_verts,
2210 const Span<int3> corner_tris,
2211 const Span<bool> hide_poly,
2212 const float3 &ray_start,
2213 const float3 &ray_normal,
2214 float *r_depth,
2215 float *dist_sq)
2216{
2217 const Span<int> face_indices = node.faces();
2218
2219 bool hit = false;
2220 if (node_positions.is_empty()) {
2221 for (const int i : face_indices.index_range()) {
2222 const int face_i = face_indices[i];
2223 if (!hide_poly.is_empty() && hide_poly[face_i]) {
2224 continue;
2225 }
2226
2227 for (const int tri_i : bke::mesh::face_triangles_range(faces, face_i)) {
2228 const int3 &corner_tri = corner_tris[tri_i];
2229 hit |= ray_face_nearest_tri(ray_start,
2230 ray_normal,
2231 vert_positions[corner_verts[corner_tri[0]]],
2232 vert_positions[corner_verts[corner_tri[1]]],
2233 vert_positions[corner_verts[corner_tri[2]]],
2234 r_depth,
2235 dist_sq);
2236 }
2237 }
2238 }
2239 else {
2240 const MeshNode::LocalVertMap &vert_map = node.vert_indices_;
2241 for (const int i : face_indices.index_range()) {
2242 const int face_i = face_indices[i];
2243 if (!hide_poly.is_empty() && hide_poly[face_i]) {
2244 continue;
2245 }
2246
2247 for (const int tri_i : bke::mesh::face_triangles_range(faces, face_i)) {
2248 const int3 &corner_tri = corner_tris[tri_i];
2249 hit |= ray_face_nearest_tri(ray_start,
2250 ray_normal,
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]])],
2254 r_depth,
2255 dist_sq);
2256 }
2257 }
2258 }
2259
2260 return hit;
2261}
2262
2263static bool pbvh_grids_node_nearest_to_ray(const SubdivCCG &subdiv_ccg,
2264 GridsNode &node,
2265 const Span<float3> node_positions,
2266 const float ray_start[3],
2267 const float ray_normal[3],
2268 float *r_depth,
2269 float *dist_sq)
2270{
2271 const CCGKey key = BKE_subdiv_ccg_key_top_level(subdiv_ccg);
2272 const Span<int> grids = node.grids();
2273 const int grid_size = key.grid_size;
2274 const BitGroupVector<> &grid_hidden = subdiv_ccg.grid_hidden;
2275 const Span<float3> positions = subdiv_ccg.positions;
2276
2277 bool hit = false;
2278 if (node_positions.is_empty()) {
2279 for (const int grid : grids) {
2280 const Span<float3> grid_positions = positions.slice(bke::ccg::grid_range(key, grid));
2281 for (const short y : IndexRange(grid_size - 1)) {
2282 for (const short x : IndexRange(grid_size - 1)) {
2283 if (!grid_hidden.is_empty()) {
2284 if (BKE_paint_is_grid_face_hidden(grid_hidden[grid], grid_size, x, y)) {
2285 continue;
2286 }
2287 }
2288 hit |= ray_face_nearest_quad(
2289 ray_start,
2290 ray_normal,
2291 grid_positions[CCG_grid_xy_to_index(grid_size, x, y)],
2292 grid_positions[CCG_grid_xy_to_index(grid_size, x + 1, y)],
2293 grid_positions[CCG_grid_xy_to_index(grid_size, x + 1, y + 1)],
2294 grid_positions[CCG_grid_xy_to_index(grid_size, x, y + 1)],
2295 r_depth,
2296 dist_sq);
2297 }
2298 }
2299 }
2300 }
2301 else {
2302 for (const int i : grids.index_range()) {
2303 const int grid = grids[i];
2304 const Span<float3> grid_positions = node_positions.slice(bke::ccg::grid_range(key, i));
2305 for (const short y : IndexRange(grid_size - 1)) {
2306 for (const short x : IndexRange(grid_size - 1)) {
2307 if (!grid_hidden.is_empty()) {
2308 if (BKE_paint_is_grid_face_hidden(grid_hidden[grid], grid_size, x, y)) {
2309 continue;
2310 }
2311 }
2312 hit |= ray_face_nearest_quad(ray_start,
2313 ray_normal,
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],
2318 r_depth,
2319 dist_sq);
2320 }
2321 }
2322 }
2323 }
2324
2325 return hit;
2326}
2327
2329 Node &node,
2330 const Span<float3> node_positions,
2331 bool use_origco,
2332 const Span<float3> vert_positions,
2333 const OffsetIndices<int> faces,
2334 const Span<int> corner_verts,
2335 const Span<int3> corner_tris,
2336 const Span<bool> hide_poly,
2337 const SubdivCCG *subdiv_ccg,
2338 const float ray_start[3],
2339 const float ray_normal[3],
2340 float *depth,
2341 float *dist_sq)
2342{
2343 if (node.flag_ & Node::FullyHidden) {
2344 return false;
2345 }
2346 switch (pbvh.type()) {
2347 case Type::Mesh:
2348 return pbvh_faces_node_nearest_to_ray(static_cast<MeshNode &>(node),
2349 node_positions,
2350 vert_positions,
2351 faces,
2352 corner_verts,
2353 corner_tris,
2354 hide_poly,
2355 ray_start,
2356 ray_normal,
2357 depth,
2358 dist_sq);
2359 case Type::Grids:
2360 return pbvh_grids_node_nearest_to_ray(*subdiv_ccg,
2361 static_cast<GridsNode &>(node),
2362 node_positions,
2363 ray_start,
2364 ray_normal,
2365 depth,
2366 dist_sq);
2367 case Type::BMesh:
2369 static_cast<BMeshNode &>(node), ray_start, ray_normal, depth, dist_sq, use_origco);
2370 }
2372 return false;
2373}
2374
2380
2381/* Adapted from:
2382 * http://www.gamedev.net/community/forums/topic.asp?topic_id=512123
2383 * Returns true if the AABB is at least partially within the frustum
2384 * (ok, not a real frustum), false otherwise.
2385 */
2387 const Span<float4> frustum_planes)
2388{
2390
2391 for (const int i : frustum_planes.index_range()) {
2392 float vmin[3], vmax[3];
2393
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];
2398 }
2399 else {
2400 vmin[axis] = bounds.max[axis];
2401 vmax[axis] = bounds.min[axis];
2402 }
2403 }
2404
2405 if (dot_v3v3(frustum_planes[i], vmin) + frustum_planes[i][3] < 0) {
2407 }
2408 if (dot_v3v3(frustum_planes[i], vmax) + frustum_planes[i][3] <= 0) {
2410 }
2411 }
2412
2413 return ret;
2414}
2415
2416bool node_frustum_contain_aabb(const Node &node, const Span<float4> frustum_planes)
2417{
2418 return test_frustum_aabb(node.bounds_, frustum_planes) != PlaneAABBIsect::Outside;
2419}
2420
2421bool node_frustum_exclude_aabb(const Node &node, const Span<float4> frustum_planes)
2422{
2423 return test_frustum_aabb(node.bounds_, frustum_planes) != PlaneAABBIsect::Inside;
2424}
2425
2426} // namespace bke::pbvh
2427
2429{
2430 using namespace blender::bke::pbvh;
2431 pbvh.tag_positions_changed(IndexRange(pbvh.nodes_num()));
2432 pbvh.update_bounds_mesh(vert_positions);
2434}
2435
2437{
2438 return node.debug_draw_gen_;
2439}
2440
2442{
2443 using namespace blender::bke;
2444 const SculptSession &ss = *object.runtime->sculpt_session;
2445 switch (object::pbvh_get(object)->type()) {
2446 case bke::pbvh::Type::Mesh: {
2447 Mesh &mesh = *id_cast<Mesh *>(object.data);
2449 break;
2450 }
2452 BMesh &bm = *ss.bm;
2453 BMIter iter;
2454 BMVert *v;
2455 BMEdge *e;
2456 BMFace *f;
2457
2458 BM_ITER_MESH (f, &iter, &bm, BM_FACES_OF_MESH) {
2460 }
2461
2462 BM_ITER_MESH (e, &iter, &bm, BM_EDGES_OF_MESH) {
2464 }
2465
2466 BM_ITER_MESH (v, &iter, &bm, BM_VERTS_OF_MESH) {
2468 continue;
2469 }
2470 BMIter iter_l;
2471 BMLoop *l;
2472
2473 BM_ITER_ELEM (l, &iter_l, v, BM_LOOPS_OF_VERT) {
2476 }
2477 }
2478 break;
2479 }
2481 Mesh &mesh = *id_cast<Mesh *>(object.data);
2482 const SubdivCCG &subdiv_ccg = *ss.subdiv_ccg;
2483 const BitGroupVector<> &grid_hidden = subdiv_ccg.grid_hidden;
2484 const CCGKey key = BKE_subdiv_ccg_key_top_level(subdiv_ccg);
2485 const OffsetIndices faces = mesh.faces();
2486
2487 IndexMaskMemory memory;
2488 const IndexMask hidden_faces =
2489 !grid_hidden.is_empty() ?
2491 faces.index_range(),
2492 memory,
2493 [&](const int i) {
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];
2497 });
2498 },
2499 exec_mode::grain_size(1024)) :
2500 IndexMask();
2501
2502 MutableAttributeAccessor attributes = mesh.attributes_for_write();
2503 if (hidden_faces.is_empty()) {
2504 attributes.remove(".hide_poly");
2505 }
2506 else {
2507 SpanAttributeWriter<bool> hide_poly = attributes.lookup_or_add_for_write_span<bool>(
2508 ".hide_poly", AttrDomain::Face, AttributeInitConstruct());
2509 hide_poly.span.fill(false);
2510 index_mask::masked_fill(hide_poly.span, true, hidden_faces);
2511 hide_poly.finish();
2512 }
2513
2515 break;
2516 }
2517 }
2518}
2519
2520namespace bke::pbvh {
2521
2523{
2524 return std::visit(
2525 [&](const auto &nodes) {
2526 return IndexMask::from_predicate(nodes.index_range(), memory, [&](const int i) {
2527 return (nodes[i].flag_ & Node::Leaf) != 0;
2528 });
2529 },
2530 pbvh.nodes_);
2531}
2532
2534 const FunctionRef<bool(Node &)> scb,
2535 Node::Flags leaf_flag)
2536{
2537 if (tree_is_empty(pbvh)) {
2538 return {};
2539 }
2540
2541 PBVHIter iter;
2543
2544 pbvh_iter_begin(&iter, pbvh, scb);
2545
2546 Node *node;
2547 while ((node = pbvh_iter_next(&iter, leaf_flag))) {
2548 if (node->flag_ & leaf_flag) {
2549 nodes.append(node);
2550 }
2551 }
2552
2553 return nodes;
2554}
2555
2557 IndexMaskMemory &memory,
2558 FunctionRef<bool(const Node &)> filter_fn)
2559{
2561 const_cast<Tree &>(pbvh), [&](Node &node) { return filter_fn(node); }, Node::Leaf);
2562 Array<int> indices(nodes.size());
2563 std::visit(
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();
2568 }
2569 },
2570 pbvh.nodes_);
2571 std::ranges::sort(indices);
2572 return IndexMask::from_indices(indices.as_span(), memory);
2573}
2574
2575} // namespace bke::pbvh
2576} // namespace blender
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 BLI_NOINLINE
#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)
Definition btDbvt.h:621
btScalar max
bool is_empty() const
Definition BLI_array.hh:275
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
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr MutableSpan drop_front(const int64_t n) const
Definition BLI_span.hh:613
constexpr T * end() const
Definition BLI_span.hh:554
constexpr T & first() const
Definition BLI_span.hh:685
constexpr T * begin() const
Definition BLI_span.hh:550
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
constexpr MutableSpan take_front(const int64_t n) const
Definition BLI_span.hh:635
Iterator begin() const
Definition BLI_set.hh:499
void reserve(const int64_t n)
Definition BLI_set.hh:656
bool add(const Key &key)
Definition BLI_set.hh:248
bool is_empty() const
Definition BLI_set.hh:614
bool remove(const Key &key)
Definition BLI_set.hh:404
void update(FunctionRef< void(T &data)> compute_cache)
void ensure(FunctionRef< void(T &data)> compute_cache)
const T & data() const
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T & first() const
Definition BLI_span.hh:319
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr const T * end() const
Definition BLI_span.hh:228
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr const T * begin() const
Definition BLI_span.hh:224
constexpr bool is_empty() const
Definition BLI_span.hh:264
bool is_empty() const
Definition BLI_stack.hh:310
void push(const T &value)
Definition BLI_stack.hh:215
void reserve(const int64_t n)
void add_multiple(Span< Key > keys)
int64_t index_of(const Key &key) const
int64_t size() const
void append(const T &value)
friend class Vector
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())
const Bounds< float3 > & bounds() const
const Bounds< float3 > & bounds_orig() const
void update_normals(Object &object_orig, Object &object_eval)
Definition pbvh.cc:1150
void tag_attribute_changed(const IndexMask &node_mask, StringRef attribute_name)
Definition pbvh.cc:655
Tree(const Tree &other)=delete
void tag_positions_changed(const IndexMask &node_mask)
Definition pbvh.cc:614
Span< NodeT > nodes() const
void update_bounds(const Depsgraph &depsgraph, const Object &object)
Definition pbvh.cc:1309
int nodes_num() const
Definition pbvh.cc:579
void update_bounds_grids(Span< float3 > positions, int grid_area)
Definition pbvh.cc:1282
void tag_face_sets_changed(const IndexMask &node_mask)
Definition pbvh.cc:641
void tag_masks_changed(const IndexMask &node_mask)
Definition pbvh.cc:648
std::unique_ptr< DrawCache > draw_data
void tag_visibility_changed(const IndexMask &node_mask)
Definition pbvh.cc:625
void update_visibility(const Object &object)
Definition pbvh.cc:1505
static Tree from_grids(const Mesh &base_mesh, const SubdivCCG &subdiv_ccg)
Definition pbvh.cc:465
static Tree from_mesh(const Mesh &mesh)
Definition pbvh.cc:304
void tag_topology_changed(const IndexMask &node_mask)
Definition pbvh.cc:634
void update_bounds_mesh(Span< float3 > vert_positions)
Definition pbvh.cc:1268
void update_bounds_bmesh(const BMesh &bm)
Definition pbvh.cc:1296
std::variant< Vector< MeshNode >, Vector< GridsNode >, Vector< BMeshNode > > nodes_
void flush_bounds_to_parents()
Definition pbvh.cc:1228
constexpr bool is_empty() const
void set_bits(MutableBitSpan r_bits, int64_t offset=0) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define FLT_MAX
#define FLT_MIN
#define position
#define log2
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)
Definition BKE_mesh.hh:359
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)
Definition pbvh.cc:2173
static void update_visibility_grids(const SubdivCCG &subdiv_ccg, const MutableSpan< GridsNode > nodes, const IndexMask &node_mask)
Definition pbvh.cc:1471
IndexMask search_nodes(const Tree &pbvh, IndexMaskMemory &memory, FunctionRef< bool(const Node &)> filter_fn)
Definition pbvh.cc:2556
static PlaneAABBIsect test_frustum_aabb(const Bounds< float3 > &bounds, const Span< float4 > frustum_planes)
Definition pbvh.cc:2386
static Vector< int > gather_shared_verts(const Span< MeshNode > nodes, const IndexMask &nodes_to_update, const int verts_num)
Definition pbvh.cc:1045
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)
Definition pbvh.cc:2533
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)
Definition pbvh.cc:972
static const SharedCache< Vector< float3 > > & vert_normals_cache_eval(const Object &object_orig, const Object &object_eval)
Definition pbvh.cc:838
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)
Definition pbvh.cc:372
void update_mask_bmesh(const BMesh &bm, const IndexMask &node_mask, Tree &pbvh)
Definition pbvh.cc:1421
void update_normals(const Depsgraph &depsgraph, Object &object_orig, Tree &pbvh)
Definition pbvh.cc:1179
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)
Definition pbvh.cc:1017
static BLI_NOINLINE void build_mesh_leaf_nodes(const int verts_num, const OffsetIndices< int > faces, const Span< int > corner_verts, MutableSpan< MeshNode > nodes)
Definition pbvh.cc:81
static Bounds< float3 > calc_face_grid_bounds(const OffsetIndices< int > faces, const Span< float3 > positions, const CCGKey &key, const int face)
Definition pbvh.cc:453
void update_mask_mesh(const Mesh &mesh, const IndexMask &node_mask, Tree &pbvh)
Definition pbvh.cc:1356
Span< float3 > vert_normals_eval_from_eval(const Object &object_eval)
Definition pbvh.cc:958
IndexMask all_leaf_nodes(const Tree &pbvh, IndexMaskMemory &memory)
Definition pbvh.cc:2522
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)
Definition pbvh.cc:1027
void clip_ray_ortho(Tree &pbvh, bool original, float ray_start[3], float ray_end[3], float ray_normal[3])
Definition pbvh.cc:2084
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)
Definition pbvh.cc:2263
int count_grid_quads(const BitGroupVector<> &grid_hidden, Span< int > grid_indices, int gridsize, int display_gridsize)
Definition pbvh.cc:1532
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)
Definition pbvh.cc:1878
void update_node_bounds_bmesh(BMeshNode &node)
Definition pbvh.cc:1216
int partition_along_axis(const Span< float3 > face_centers, MutableSpan< int > faces, const int axis, const float middle)
Definition pbvh.cc:62
static void update_visibility_faces(const Mesh &mesh, const MutableSpan< MeshNode > nodes, const IndexMask &node_mask)
Definition pbvh.cc:1446
static void pbvh_iter_begin(PBVHIter *iter, Tree &pbvh, FunctionRef< bool(Node &)> scb)
Definition pbvh.cc:685
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)
Definition pbvh.cc:1770
static std::optional< float > ray_aabb_intersect(const Node &node, const RaycastData &rcd)
Definition pbvh.cc:1702
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)
Definition pbvh.cc:1824
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)
Definition pbvh.cc:998
bool node_frustum_exclude_aabb(const Node &node, Span< float4 > frustum_planes)
Definition pbvh.cc:2421
Span< float3 > vert_positions_eval_from_eval(const Object &object_eval)
Definition pbvh.cc:939
static bool tree_is_empty(const Tree &pbvh)
Definition pbvh.cc:662
void node_update_mask_bmesh(int mask_offset, BMeshNode &node)
Definition pbvh.cc:1404
void node_update_mask_mesh(Span< float > mask, MeshNode &node)
Definition pbvh.cc:1345
void node_update_visibility_grids(const BitGroupVector<> &grid_hidden, GridsNode &node)
Definition pbvh.cc:1461
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)
Definition pbvh.cc:1847
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)
Definition pbvh.cc:1794
static Node * pbvh_iter_next(PBVHIter *iter, Node::Flags leaf_flag)
Definition pbvh.cc:692
static Node & first_node(Tree &pbvh)
Definition pbvh.cc:667
void node_update_mask_grids(const CCGKey &key, Span< float > masks, GridsNode &node)
Definition pbvh.cc:1373
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)
Definition pbvh.cc:1994
static Bounds< float3 > negative_bounds()
Definition pbvh.cc:52
void update_node_bounds_mesh(Span< float3 > positions, MeshNode &node)
Definition pbvh.cc:1196
void node_update_visibility_bmesh(BMeshNode &node)
Definition pbvh.cc:1486
static SharedCache< Vector< float3 > > & vert_normals_cache_eval_for_write(Object &object_orig, Object &object_eval)
Definition pbvh.cc:859
Bounds< float3 > bounds_get(const Tree &pbvh)
Definition pbvh.cc:1590
void update_normals_from_eval(Object &object_eval, Tree &pbvh)
Definition pbvh.cc:1186
void pixels_free(bke::pbvh::Tree *pbvh)
Span< float3 > vert_normals_eval(const Depsgraph &depsgraph, const Object &object_orig)
Definition pbvh.cc:952
IndexMask nodes_to_face_selection_grids(const SubdivCCG &subdiv_ccg, Span< GridsNode > nodes, const IndexMask &nodes_mask, IndexMaskMemory &memory)
Definition pbvh.cc:1570
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)
Definition pbvh.cc:142
static SharedCache< Vector< float3 > > & face_normals_cache_eval_for_write(Object &object_orig, Object &object_eval)
Definition pbvh.cc:886
void update_mask_grids(const SubdivCCG &subdiv_ccg, const IndexMask &node_mask, Tree &pbvh)
Definition pbvh.cc:1387
MutableSpan< float3 > vert_positions_eval_for_write(const Depsgraph &depsgraph, Object &object_orig)
Definition pbvh.cc:946
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)
Definition pbvh.cc:2205
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)
Definition pbvh.cc:1728
static Bounds< float3 > merge_bounds(const Bounds< float3 > &a, const Bounds< float3 > &b)
Definition pbvh.cc:57
static const SharedCache< Vector< float3 > > & face_normals_cache_eval(const Object &object_orig, const Object &object_eval)
Definition pbvh.cc:866
bool leaf_needs_material_split(const Span< int > faces, const Span< int > material_indices)
Definition pbvh.cc:132
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)
Definition pbvh.cc:1960
int partition_material_indices(const Span< int > material_indices, MutableSpan< int > faces)
Definition pbvh.cc:73
Span< float3 > face_normals_eval_from_eval(const Object &object_eval)
Definition pbvh.cc:965
static void update_visibility_bmesh(const MutableSpan< BMeshNode > nodes, const IndexMask &node_mask)
Definition pbvh.cc:1499
bool ray_face_intersection_tri(const float3 &ray_start, const IsectRayPrecalc *isect_precalc, const float3 &t0, const float3 &t1, const float3 &t2, float *depth)
Definition pbvh.cc:1750
void update_node_bounds_grids(int grid_area, Span< float3 > positions, GridsNode &node)
Definition pbvh.cc:1205
bool node_frustum_contain_aabb(const Node &node, Span< float4 > frustum_planes)
Definition pbvh.cc:2416
static void update_normals_mesh(Object &object_orig, Object &object_eval, const Span< MeshNode > nodes, const IndexMask &nodes_to_update)
Definition pbvh.cc:1079
static void search_callback_occluded(Tree &pbvh, const FunctionRef< std::optional< float >(const Node &)> scb, const FunctionRef< void(Node &node, float *distance)> hit_fn)
Definition pbvh.cc:738
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)
Definition pbvh.cc:2328
void store_bounds_orig(Tree &pbvh)
Definition pbvh.cc:1332
constexpr int leaf_limit
Definition pbvh_bmesh.cc:37
static bool mesh_topology_count_matches(const Mesh &a, const Mesh &b)
Definition pbvh.cc:792
Span< int > node_face_indices_calc_grids(const SubdivCCG &subdiv_ccg, const GridsNode &node, Vector< int > &faces)
Definition pbvh.cc:1666
Span< float3 > vert_positions_eval(const Depsgraph &depsgraph, const Object &object_orig)
Definition pbvh.cc:933
static PositionSourceResult cache_source_get(const Object &object_orig, const Object &object_eval)
Definition pbvh.cc:810
void node_update_visibility_mesh(Span< bool > hide_vert, MeshNode &node)
Definition pbvh.cc:1437
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)
Definition pbvh.cc:984
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)
Definition BLI_bounds.hh:27
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)
Definition abc_util.cc:68
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)
Definition BLI_task.hh:197
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
Value parallel_reduce(IndexRange range, int64_t grain_size, const Value &identity, const Function &function, const Reduction &reduction)
Definition BLI_task.hh:127
BMesh Iterators.
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])
__int64 int64_t
Definition BKE_text.h:90
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)
Definition pbvh.cc:1606
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)
Definition pbvh.cc:1613
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)
Definition pbvh.cc:2436
struct DistRayAABB_Precalc dist_squared_ray_to_aabb_v3_precalc(const float ray_origin[3], const float ray_direction[3])
Definition math_geom.cc:703
void BKE_pbvh_vert_coords_apply(bke::pbvh::Tree &pbvh, Span< float3 > vert_positions)
Definition pbvh.cc:2428
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])
Definition math_geom.cc:45
void BKE_pbvh_node_fully_masked_set(bke::pbvh::Node &node, int fully_masked)
Definition pbvh.cc:1630
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)
Definition pbvh.cc:2441
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])
Definition math_geom.cc:62
void BKE_pbvh_node_fully_unmasked_set(bke::pbvh::Node &node, int fully_masked)
Definition pbvh.cc:1647
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)
Definition BKE_ccg.hh:75
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)
Definition pbvh.cc:1642
ATTR_WARN_UNUSED_RESULT const BMVert * v2
bool BKE_pbvh_node_fully_hidden_get(const bke::pbvh::Node &node)
Definition pbvh.cc:1625
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)
Definition math_geom.cc:629
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)
Definition pbvh.cc:1685
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)
Definition object.cc:4419
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)
Definition pbvh.cc:1659
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
signed char int8_t
Definition BKE_text.h:76
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)
Definition object.cc:4519
#define min(a, b)
Definition sort.cc:38
struct BMEdge * e
struct BMFace * f
CustomData vdata
bke::MeshRuntime * runtime
bke::ObjectRuntime * runtime
Array< float3, 0 > deform_cos
Definition BKE_paint.hh:395
SharedCache< Vector< float3 > > vert_normals_deform
Definition BKE_paint.hh:403
SharedCache< Vector< float3 > > face_normals_deform
Definition BKE_paint.hh:404
Array< float3 > positions
OffsetIndices< int > faces
BitGroupVector grid_hidden
Array< float > masks
Span< int > grid_to_face_map
SharedCache< Vector< float3 > > face_normals_true_cache
SharedCache< Vector< float3 > > vert_normals_true_cache
VectorSet< int, 0, DefaultProbingStrategy, DefaultHash< int >, DefaultEquality< int >, SimpleVectorSetSlot< int, LocalVertMapIndexT >, GuardedAllocator > LocalVertMap
FunctionRef< bool(Node &)> scb
Definition pbvh.cc:680
Stack< StackItem, 100 > stack
Definition pbvh.cc:682
IsectRayAABB_Precalc ray
Definition pbvh.cc:1698