Blender V5.3
pbvh_bmesh.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 "BLI_bounds.hh"
10#include "BLI_heap_simple.hh"
11#include "BLI_map.hh"
12#include "BLI_math_geom_c.hh"
13#include "BLI_math_vector.hh"
14#include "BLI_math_vector_c.hh"
15#include "BLI_memarena.hh"
16#include "BLI_span.hh"
17#include "BLI_time.hh"
18#include "BLI_utildefines.hh"
19
20#include "BKE_global.hh"
21#include "BKE_paint_bvh.hh"
22
23#include "PRF_profile.hh"
24
25#include "bmesh.hh"
26#include "pbvh_intern.hh"
27
28#include "CLG_log.h"
29
30namespace blender {
31
32static CLG_LogRef LOG = {"sculpt.bmesh"};
33
34namespace bke::pbvh {
35
36/* TODO: choose leaf limit better. */
37constexpr int leaf_limit = 400;
38
39static constexpr int dyntopo_node_none = -1;
40
41/* -------------------------------------------------------------------- */
46
53
54#define BM_LOOPS_OF_VERT_ITER_BEGIN(l_iter_radial_, v_) \
55 { \
56 struct { \
57 BMVert *v; \
58 BMEdge *e_iter, *e_first; \
59 BMLoop *l_iter_radial; \
60 } _iter; \
61 _iter.v = v_; \
62 if (_iter.v->e) { \
63 _iter.e_iter = _iter.e_first = _iter.v->e; \
64 do { \
65 if (_iter.e_iter->l) { \
66 _iter.l_iter_radial = _iter.e_iter->l; \
67 do { \
68 if (_iter.l_iter_radial->v == _iter.v) { \
69 l_iter_radial_ = _iter.l_iter_radial;
70
71#define BM_LOOPS_OF_VERT_ITER_END \
72 } \
73 } \
74 while ((_iter.l_iter_radial = _iter.l_iter_radial->radial_next) != _iter.e_iter->l) \
75 ; \
76 } \
77 } \
78 while ((_iter.e_iter = BM_DISK_EDGE_NEXT(_iter.e_iter, _iter.v)) != _iter.e_first) \
79 ; \
80 } \
81 } \
82 ((void)0)
83
84#define BM_FACES_OF_VERT_ITER_BEGIN(f_iter_, v_) \
85 { \
86 BMLoop *l_iter_radial_; \
87 BM_LOOPS_OF_VERT_ITER_BEGIN (l_iter_radial_, v_) { \
88 f_iter_ = l_iter_radial_->f;
89
90#define BM_FACES_OF_VERT_ITER_END \
91 } \
92 BM_LOOPS_OF_VERT_ITER_END; \
93 } \
94 ((void)0)
95
97{
98 return {float3(std::numeric_limits<float>::max()), float3(std::numeric_limits<float>::lowest())};
99}
100
101static std::array<BMEdge *, 3> bm_edges_from_tri(BMesh &bm, const Span<BMVert *> v_tri)
102{
103 return {
104 BM_edge_create(&bm, v_tri[0], v_tri[1], nullptr, BM_CREATE_NO_DOUBLE),
105 BM_edge_create(&bm, v_tri[1], v_tri[2], nullptr, BM_CREATE_NO_DOUBLE),
106 BM_edge_create(&bm, v_tri[2], v_tri[0], nullptr, BM_CREATE_NO_DOUBLE),
107 };
108}
109
110BLI_INLINE std::array<BMVert *, 3> bm_face_as_array(const BMFace &f)
111{
112 const BMLoop *l = BM_FACE_FIRST_LOOP(&f);
113
114 BLI_assert(f.len == 3);
115
116 std::array<BMVert *, 3> result;
117 result[0] = l->v;
118 l = l->next;
119 result[1] = l->v;
120 l = l->next;
121 result[2] = l->v;
122 return result;
123}
124
142static BMFace *bm_face_exists_tri_from_loop_vert(const BMLoop *l_radial_first,
143 const BMVert *v_opposite)
144{
146 !ELEM(v_opposite, l_radial_first->v, l_radial_first->next->v, l_radial_first->prev->v));
147 if (l_radial_first->radial_next != l_radial_first) {
148 BMLoop *l_radial_iter = l_radial_first->radial_next;
149 do {
150 BLI_assert(l_radial_iter->f->len == 3);
151 if (l_radial_iter->prev->v == v_opposite) {
152 return l_radial_iter->f;
153 }
154 } while ((l_radial_iter = l_radial_iter->radial_next) != l_radial_first);
155 }
156 return nullptr;
157}
158
164{
165 while (true) {
166 BMVert **v_next_p = deleted_verts.lookup_ptr(v);
167 if (v_next_p == nullptr) {
168 /* Not remapped. */
169 return v;
170 }
171 if (*v_next_p == nullptr) {
172 /* Removed and not remapped. */
173 return nullptr;
174 }
175
176 /* Remapped. */
177 v = *v_next_p;
178 }
179}
180
182
183/****************************** Building ******************************/
184
187 const int node_index,
188 const int cd_vert_node_offset,
189 const int cd_face_node_offset)
190{
191 bool has_visible = false;
192
194
195 for (BMFace *f : n.bm_faces_) {
196 /* Update ownership of faces. */
197 BM_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
198
199 /* Update vertices. */
200 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
201 const BMLoop *l_iter = l_first;
202
203 do {
204 BMVert *v = l_iter->v;
205 if (!n.bm_unique_verts_.contains(v)) {
206 if (BM_ELEM_CD_GET_INT(v, cd_vert_node_offset) != dyntopo_node_none) {
207 n.bm_other_verts_.add(v);
208 }
209 else {
210 n.bm_unique_verts_.add(v);
211 BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
212 }
213 }
214 /* Update node bounding box. */
215 math::min_max(float3(v->co), n.bounds_.min, n.bounds_.max);
216 } while ((l_iter = l_iter->next) != l_first);
217
219 has_visible = true;
220 }
221 }
222
223 BLI_assert(n.bounds_.min[0] <= n.bounds_.max[0] && n.bounds_.min[1] <= n.bounds_.max[1] &&
224 n.bounds_.min[2] <= n.bounds_.max[2]);
225
226 n.bounds_orig_ = n.bounds_;
227
228 BKE_pbvh_node_fully_hidden_set(n, !has_visible);
229}
230
233 Vector<bool> &node_changed,
234 const int cd_vert_node_offset,
235 const int cd_face_node_offset,
236 const Span<Bounds<float3>> face_bounds,
237 const int node_index)
238{
239 if (nodes[node_index].bm_faces_.size() <= leaf_limit) {
240 /* Node limit not exceeded. */
242 nodes[node_index], node_index, cd_vert_node_offset, cd_face_node_offset);
243 return;
244 }
245
246 /* Calculate bounding box around primitive centroids. */
248 for (const BMFace *f : nodes[node_index].bm_faces_) {
249 const int i = BM_elem_index_get(f);
250 const float3 center = math::midpoint(face_bounds[i].min, face_bounds[i].max);
251 math::min_max(center, cb.min, cb.max);
252 }
253
254 /* Find widest axis and its midpoint. */
255 const int axis = math::dominant_axis(cb.max - cb.min);
256 const float mid = math::midpoint(cb.max[axis], cb.min[axis]);
257
258 /* Add two new child nodes. */
259 const int children = nodes.size();
260 nodes[node_index].children_offset_ = children;
261 nodes.resize(nodes.size() + 2);
262 node_changed.resize(node_changed.size() + 2, true);
263
264 /* Initialize children */
265 BMeshNode *c1 = &nodes[children], *c2 = &nodes[children + 1];
266 c1->flag_ |= Node::Leaf;
267 c2->flag_ |= Node::Leaf;
268 c1->parent_ = node_index;
269 c2->parent_ = node_index;
270 c1->bm_faces_.reserve(nodes[node_index].bm_faces_.size() / 2);
271 c2->bm_faces_.reserve(nodes[node_index].bm_faces_.size() / 2);
272
273 /* Partition the parent node's faces between the two children. */
274 for (BMFace *f : nodes[node_index].bm_faces_) {
275 const int i = BM_elem_index_get(f);
276 if (math::midpoint(face_bounds[i].min[axis], face_bounds[i].max[axis]) < mid) {
277 c1->bm_faces_.add(f);
278 }
279 else {
280 c2->bm_faces_.add(f);
281 }
282 }
283
284 /* Enforce at least one primitive in each node */
285 Set<BMFace *, 0> *empty = nullptr;
286 Set<BMFace *, 0> *other = nullptr;
287 if (c1->bm_faces_.is_empty()) {
288 empty = &c1->bm_faces_;
289 other = &c2->bm_faces_;
290 }
291 else if (c2->bm_faces_.is_empty()) {
292 empty = &c2->bm_faces_;
293 other = &c1->bm_faces_;
294 }
295 if (empty) {
296 for (BMFace *f : *other) {
297 empty->add(f);
298 other->remove(f);
299 break;
300 }
301 }
302
303 /* Clear this node */
304
305 /* Mark this node's unique verts as unclaimed. */
306 for (BMVert *v : nodes[node_index].bm_unique_verts_) {
307 BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, dyntopo_node_none);
308 }
309
310 /* Unclaim faces. */
311 for (BMFace *f : nodes[node_index].bm_faces_) {
312 BM_ELEM_CD_SET_INT(f, cd_face_node_offset, dyntopo_node_none);
313 }
314 nodes[node_index].bm_faces_.clear();
315
316 nodes[node_index].flag_ &= ~Node::Leaf;
317 node_changed[node_index] = true;
318
319 /* Recurse. */
321 nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, face_bounds, children);
323 nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, face_bounds, children + 1);
324
325 /* Update bounding box. */
326 nodes[node_index].bounds_ = bounds::merge(nodes[nodes[node_index].children_offset_].bounds_,
327 nodes[nodes[node_index].children_offset_ + 1].bounds_);
328 nodes[node_index].bounds_orig_ = nodes[node_index].bounds_;
329}
330
334 Vector<bool> &node_changed,
335 const int cd_vert_node_offset,
336 const int cd_face_node_offset,
337 const int node_index)
338{
339 const int faces_num = nodes[node_index].bm_faces_.size();
340 if (faces_num <= leaf_limit) {
341 /* Node limit not exceeded */
342 return false;
343 }
344
345 /* For each BMFace, store the AABB and AABB centroid. */
346 Array<Bounds<float3>> face_bounds(faces_num);
347
348 int i = 0;
349 for (BMFace *f : nodes[node_index].bm_faces_) {
350 face_bounds[i] = negative_bounds();
351
352 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
353 BMLoop *l_iter = l_first;
354 do {
355 math::min_max(float3(l_iter->v->co), face_bounds[i].min, face_bounds[i].max);
356 } while ((l_iter = l_iter->next) != l_first);
357
358 /* So we can do direct lookups on 'face_bounds'. */
359 BM_elem_index_set(f, i); /* set_dirty! */
360 i++;
361 }
362
363 /* Likely this is already dirty. */
365
367 nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, face_bounds, node_index);
368
369 return true;
370}
371
372/**********************************************************************/
373
374BLI_INLINE int pbvh_bmesh_node_index_from_vert(const int cd_vert_node_offset, const BMVert *key)
375{
376 const int node_index = BM_ELEM_CD_GET_INT(reinterpret_cast<const BMElem *>(key),
377 cd_vert_node_offset);
378 BLI_assert(node_index != dyntopo_node_none);
379 return node_index;
380}
381
382BLI_INLINE int pbvh_bmesh_node_index_from_face(const int cd_face_node_offset, const BMFace *key)
383{
384 const int node_index = BM_ELEM_CD_GET_INT(reinterpret_cast<const BMElem *>(key),
385 cd_face_node_offset);
386 BLI_assert(node_index != dyntopo_node_none);
387 return node_index;
388}
389
391 const int cd_vert_node_offset,
392 const BMVert *key)
393{
394 return &nodes[pbvh_bmesh_node_index_from_vert(cd_vert_node_offset, key)];
395}
396
398 const int cd_face_node_offset,
399 const BMFace *key)
400{
401 return &nodes[pbvh_bmesh_node_index_from_face(cd_face_node_offset, key)];
402}
403
406 MutableSpan<bool> node_changed,
407 BMLog &bm_log,
408 const BMVert *v1,
409 const BMVert *v2,
410 const int node_index,
411 const float3 &co,
412 const float3 &no,
413 const int cd_vert_node_offset,
414 const int cd_vert_mask_offset)
415{
416 BMeshNode &node = nodes[node_index];
417
418 BLI_assert((nodes.size() == 1 || node_index) && node_index <= nodes.size());
419
420 /* Avoid initializing custom-data because its quite involved. */
421 BMVert *v = BM_vert_create(&bm, co, nullptr, BM_CREATE_NOP);
422
423 BM_data_interp_from_verts(&bm, v1, v2, v, 0.5f);
424
425 /* This value is logged below. */
426 copy_v3_v3(v->no, no);
427
428 node.bm_unique_verts_.add(v);
429 BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
430
432 node_changed[node_index] = true;
433
434 /* Log the new vertex. */
435 BM_log_vert_added(&bm_log, v, cd_vert_mask_offset);
436
437 return v;
438}
439
445 MutableSpan<bool> node_changed,
446 const int cd_face_node_offset,
447 BMLog &bm_log,
448 const int node_index,
449 const Span<BMVert *> v_tri,
450 const Span<BMEdge *> e_tri,
451 const BMFace *f_example)
452{
453 BMeshNode &node = nodes[node_index];
454
455 /* Ensure we never add existing face. */
456 BLI_assert(!BM_face_exists(v_tri.data(), 3));
457
458 BMFace *f = BM_face_create(&bm, v_tri.data(), e_tri.data(), 3, f_example, BM_CREATE_NOP);
459 f->head.hflag = f_example->head.hflag;
460
461 node.bm_faces_.add(f);
462 BM_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
463
465 node_changed[node_index] = true;
466 node.flag_ &= ~Node::FullyHidden;
467
468 /* Log the new face. */
469 BM_log_face_added(&bm_log, f);
470
471 return f;
472}
473
474#define pbvh_bmesh_node_vert_use_count_is_equal(nodes, cd_face_node_offset, node, v, n) \
475 (pbvh_bmesh_node_vert_use_count_at_most(nodes, cd_face_node_offset, node, v, (n) + 1) == n)
476
478 const int cd_face_node_offset,
479 const BMeshNode *node,
480 BMVert *v,
481 const int count_max)
482{
483 int count = 0;
484 BMFace *f;
485
487 BMeshNode *f_node = pbvh_bmesh_node_from_face(nodes, cd_face_node_offset, f);
488 if (f_node == node) {
489 count++;
490 if (count == count_max) {
491 return count;
492 }
493 }
494 }
496
497 return count;
498}
499
501static std::optional<int> pbvh_bmesh_vert_other_node_find(const int cd_vert_node_offset,
502 const int cd_face_node_offset,
503 BMVert *v)
504{
505 const int current_node = pbvh_bmesh_node_index_from_vert(cd_vert_node_offset, v);
506 BMFace *f;
507
509 const int f_node = pbvh_bmesh_node_index_from_face(cd_face_node_offset, f);
510
511 if (f_node != current_node) {
512 return f_node;
513 }
514 }
516
517 return std::nullopt;
518}
519
521 MutableSpan<bool> node_changed,
522 const int cd_vert_node_offset,
523 const int new_owner_index,
524 BMVert *v)
525{
526 const int current_owner_index = pbvh_bmesh_node_index_from_vert(cd_vert_node_offset, v);
527 BMeshNode *current_owner = &nodes[current_owner_index];
528 current_owner->flag_ |= Node::TopologyUpdated;
529 node_changed[new_owner_index] = true;
530
531 BMeshNode *new_owner = &nodes[new_owner_index];
532
533 BLI_assert(current_owner != new_owner);
534
535 /* Remove current ownership. */
536 current_owner->bm_unique_verts_.remove(v);
537
538 /* Set new ownership */
539 BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, new_owner_index);
540 new_owner->bm_unique_verts_.add(v);
541 new_owner->bm_other_verts_.remove(v);
542 BLI_assert(!new_owner->bm_other_verts_.contains(v));
543
544 new_owner->flag_ |= Node::TopologyUpdated;
545 node_changed[new_owner_index] = true;
546}
547
549 MutableSpan<bool> node_changed,
550 const int cd_vert_node_offset,
551 const int cd_face_node_offset,
552 BMVert *v)
553{
554 /* Never match for first time. */
555 int f_node_index_prev = dyntopo_node_none;
556
557 BMeshNode *v_node = pbvh_bmesh_node_from_vert(nodes, cd_vert_node_offset, v);
558 v_node->bm_unique_verts_.remove(v);
559 BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, dyntopo_node_none);
560
561 /* Have to check each neighboring face's node. */
562 BMFace *f;
564 const int f_node_index = pbvh_bmesh_node_index_from_face(cd_face_node_offset, f);
565
566 /* Faces often share the same node, quick check to avoid redundant #BLI_gset_remove calls. */
567 if (f_node_index_prev != f_node_index) {
568 f_node_index_prev = f_node_index;
569
570 BMeshNode *f_node = &nodes[f_node_index];
571 f_node->flag_ |= Node::TopologyUpdated;
572 node_changed[f_node_index] = true;
573
574 /* Remove current ownership. */
575 f_node->bm_other_verts_.remove(v);
576
577 BLI_assert(!f_node->bm_unique_verts_.contains(v));
578 BLI_assert(!f_node->bm_other_verts_.contains(v));
579 }
580 }
582}
583
585 MutableSpan<bool> node_changed,
586 const int cd_vert_node_offset,
587 const int cd_face_node_offset,
588 BMLog &bm_log,
589 BMFace *f)
590{
591 const int node_index = pbvh_bmesh_node_index_from_face(cd_face_node_offset, f);
592 BMeshNode *f_node = &nodes[node_index];
593
594 /* Check if any of this face's vertices need to be removed from the node. */
595 const BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
596 const BMLoop *l_iter = l_first;
597 do {
598 BMVert *v = l_iter->v;
599 if (pbvh_bmesh_node_vert_use_count_is_equal(nodes, cd_face_node_offset, f_node, v, 1)) {
600 if (f_node->bm_unique_verts_.contains(v)) {
601 /* Find a different node that uses 'v'. */
602
603 const std::optional<int> new_node = pbvh_bmesh_vert_other_node_find(
604 cd_vert_node_offset, cd_face_node_offset, v);
606
607 if (new_node) {
609 nodes, node_changed, cd_vert_node_offset, *new_node, v);
610 }
611 }
612 else {
613 /* Remove from other verts. */
614 f_node->bm_other_verts_.remove(v);
615 }
616 }
617 } while ((l_iter = l_iter->next) != l_first);
618
619 /* Remove face from node and top level. */
620 f_node->bm_faces_.remove(f);
621 BM_ELEM_CD_SET_INT(f, cd_face_node_offset, dyntopo_node_none);
622
623 /* Log removed face. */
624 BM_log_face_removed(&bm_log, f);
625
626 /* Mark node for update. */
627 f_node->flag_ |= Node::TopologyUpdated;
628 node_changed[node_index] = true;
629}
630
632{
633 /* Fast-path for most common case where an edge has 2 faces no need to iterate twice. */
634 std::array<BMLoop *, 2> manifold_loops;
635 if (BM_edge_loop_pair(e, manifold_loops.data(), manifold_loops.data() + 1)) [[likely]] {
636 return Array<BMLoop *>(Span(manifold_loops));
637 }
640 nullptr, BM_LOOPS_OF_EDGE, e, reinterpret_cast<void **>(loops.data()), loops.size());
641 return loops;
642}
643
645{
646 node->orig_positions_ = {};
647 node->orig_tris_ = {};
648 node->orig_verts_ = {};
649}
650
651/****************************** EdgeQueue *****************************/
652
653struct EdgeQueue {
656 /* For when we use projected coords */
661
663
664 std::optional<float3> view_normal;
666};
667
676
677/* Only tagged edges are in the queue. */
678#define EDGE_QUEUE_TEST(e) BM_elem_flag_test((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)
679#define EDGE_QUEUE_ENABLE(e) BM_elem_flag_enable((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)
680#define EDGE_QUEUE_DISABLE(e) \
681 BM_elem_flag_disable((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)
682
683static bool edge_queue_tri_in_sphere(const EdgeQueue *queue, BMFace *f)
684{
685 std::array<BMVert *, 3> v_tri;
686
687 /* Get closest point in triangle to sphere center. */
688 BM_face_as_array_vert_tri(f, v_tri.data());
689
690 float3 c;
691 closest_on_tri_to_point_v3(c, queue->center, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co);
692
693 /* Check if triangle intersects the sphere. */
694 return math::distance_squared(queue->center, c) <= queue->radius_squared;
695}
696
697static bool edge_queue_tri_in_circle(const EdgeQueue *queue, BMFace *f)
698{
699 BLI_assert_msg(queue->view_normal, "Must have view normal to be able to project triangle");
700
701 std::array<BMVert *, 3> v_tri;
702
703 /* Get closest point in triangle to sphere center. */
704 BM_face_as_array_vert_tri(f, v_tri.data());
705
706 std::array<float3, 3> tri_proj;
707 project_plane_normalized_v3_v3v3(tri_proj[0], v_tri[0]->co, *queue->view_normal);
708 project_plane_normalized_v3_v3v3(tri_proj[1], v_tri[1]->co, *queue->view_normal);
709 project_plane_normalized_v3_v3v3(tri_proj[2], v_tri[2]->co, *queue->view_normal);
710
711 float3 c;
712 closest_on_tri_to_point_v3(c, queue->center_proj, tri_proj[0], tri_proj[1], tri_proj[2]);
713
714 /* Check if triangle intersects the sphere. */
715 return math::distance_squared(queue->center_proj, c) <= queue->radius_squared;
716}
717
719static bool check_mask(const EdgeQueueContext *eq_ctx, const BMVert *v)
720{
721 return BM_ELEM_CD_GET_FLOAT(v, eq_ctx->cd_vert_mask_offset) < 1.0f;
722}
723
724static void edge_queue_insert(const EdgeQueueContext *eq_ctx, BMEdge *e, const float priority)
725{
726 /* Don't let topology update affect fully masked vertices. This used to
727 * have a 50% mask cutoff, with the reasoning that you can't do a 50%
728 * topology update. But this gives an ugly border in the mesh. The mask
729 * should already make the brush move the vertices only 50%, which means
730 * that topology updates will also happen less frequent, that should be
731 * enough. */
732 if ((eq_ctx->cd_vert_mask_offset == -1 ||
733 (check_mask(eq_ctx, e->v1) || check_mask(eq_ctx, e->v2))) &&
736 {
737 BMVert **pair = static_cast<BMVert **>(BLI_mempool_alloc(eq_ctx->pool));
738 pair[0] = e->v1;
739 pair[1] = e->v2;
740 BLI_heapsimple_insert(eq_ctx->queue->heap, priority, pair);
741 BLI_assert(EDGE_QUEUE_TEST(e) == false);
743 }
744}
745
747static bool is_boundary_edge(const BMEdge &edge)
748{
749 if (edge.head.hflag & BM_ELEM_SEAM) {
750 return true;
751 }
752 if ((edge.head.hflag & BM_ELEM_SMOOTH) == 0) {
753 return true;
754 }
755 if (!BM_edge_is_manifold(&edge)) {
756 return true;
757 }
758
759 /* TODO(@sergey): Other boundaries? For example, edges between two different face sets. */
760
761 return false;
762}
763
764/* Return true if the vertex is adjacent to a boundary edge. */
765static bool is_boundary_vert(const BMVert &vertex)
766{
767 BMEdge *edge = vertex.e;
768 const BMEdge *first_edge = edge;
769 if (first_edge == nullptr) {
770 return false;
771 }
772 do {
773 if (is_boundary_edge(*edge)) {
774 return true;
775 }
776 } while ((edge = BM_DISK_EDGE_NEXT(edge, &vertex)) != first_edge);
777
778 return false;
779}
780
782static bool is_edge_adjacent_to_boundary(const BMEdge &edge)
783{
784 return is_boundary_vert(*edge.v1) || is_boundary_vert(*edge.v2);
785}
786
787/* Notes on edge priority.
788 *
789 * The priority is used to control the order in which edges are handled for both splitting of long
790 * edges and collapsing of short edges. For long edges we start by splitting the longest edge and
791 * for collapsing we start with the shortest.
792 *
793 * A heap-like data structure is used to accelerate such ordering. A bit confusingly, this data
794 * structure gives the higher priorities to elements with lower numbers.
795 *
796 * When edges do not belong to and are not adjacent to boundaries, their length is used as the
797 * priority directly. Prefer to handle those edges first. Modifying those edges leads to no
798 * distortion to the boundary.
799 *
800 * Edges adjacent to a boundary with one vertex are handled next, and the vertex which is
801 * on the boundary does not change position as part of the edge collapse algorithm.
802 *
803 * And last, the boundary edges are handled. While subdivision of boundary edges does not change
804 * the shape of the boundary, collapsing boundary edges distorts the boundary. Hence they are
805 * handled last. */
806
807static float long_edge_queue_priority(const BMEdge &edge)
808{
809 return -BM_edge_calc_length_squared(&edge);
810}
811
812static float short_edge_queue_priority(const BMEdge &edge)
813{
814 float priority = BM_edge_calc_length_squared(&edge);
815
816 if (is_boundary_edge(edge)) {
817 priority *= 1.5f;
818 }
819 else if (is_edge_adjacent_to_boundary(edge)) {
820 priority *= 1.25f;
821 }
822
823 return priority;
824}
825
827{
828 if (!EDGE_QUEUE_TEST(e)) {
831 }
832 }
833}
834
836 const BMLoop *l_edge,
837 const BMLoop *l_end,
838 const float len_sq,
839 const float limit_len)
840{
841 BLI_assert(len_sq > square_f(limit_len));
842
843 if (eq_ctx->queue->use_front_face) {
844 if (dot_v3v3(l_edge->f->no, *eq_ctx->queue->view_normal) < 0.0f) {
845 return;
846 }
847 }
848
849 if (!EDGE_QUEUE_TEST(l_edge->e)) {
850 edge_queue_insert(eq_ctx, l_edge->e, long_edge_queue_priority(*l_edge->e));
851 }
852
853 /* temp support previous behavior! */
854 if (G.debug_value == 1234) [[unlikely]] {
855 return;
856 }
857
858 if (l_edge->radial_next != l_edge) {
859 /* How much longer we need to be to consider for subdividing
860 * (avoids subdividing faces which are only *slightly* skinny). */
861 static constexpr float even_edgelen_threshold = 1.2f;
862 /* How much the limit increases per recursion
863 * (avoids performing subdivisions too far away). */
864 static constexpr float even_generation_scale = 1.6f;
865
866 const float len_sq_cmp = len_sq * even_edgelen_threshold;
867
868 const float new_limit_len = limit_len * even_generation_scale;
869 const float new_limit_len_sq = square_f(new_limit_len);
870
871 const BMLoop *l_iter = l_edge;
872 do {
873 std::array<BMLoop *, 2> l_adjacent = {l_iter->next, l_iter->prev};
874 for (int i = 0; i < l_adjacent.size(); i++) {
875 const float len_sq_other = BM_edge_calc_length_squared(l_adjacent[i]->e);
876 if (len_sq_other > max_ff(len_sq_cmp, new_limit_len_sq)) {
877 // edge_queue_insert(eq_ctx, l_adjacent[i]->e, -len_sq_other);
879 eq_ctx, l_adjacent[i]->radial_next, l_adjacent[i], len_sq_other, new_limit_len);
880 }
881 }
882 } while ((l_iter = l_iter->radial_next) != l_end);
883 }
884}
885
887{
888 if (!EDGE_QUEUE_TEST(e)) {
891 }
892 }
893}
894
896{
897 if (eq_ctx->queue->use_front_face) {
898 if (dot_v3v3(f->no, *eq_ctx->queue->view_normal) < 0.0f) {
899 return;
900 }
901 }
902
903 if (eq_ctx->queue->edge_queue_tri_in_range(eq_ctx->queue, f)) {
904 /* Check each edge of the face. */
905 const BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
906 const BMLoop *l_iter = l_first;
907 do {
908 const float len_sq = BM_edge_calc_length_squared(l_iter->e);
909 if (len_sq > eq_ctx->queue->limit_len_squared) {
911 eq_ctx, l_iter->radial_next, l_iter, len_sq, eq_ctx->queue->limit_len);
912 }
913 } while ((l_iter = l_iter->next) != l_first);
914 }
915}
916
918{
919 if (eq_ctx->queue->use_front_face) {
920 if (dot_v3v3(f->no, *eq_ctx->queue->view_normal) < 0.0f) {
921 return;
922 }
923 }
924
925 if (eq_ctx->queue->edge_queue_tri_in_range(eq_ctx->queue, f)) {
926 /* Check each edge of the face. */
927 const BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
928 const BMLoop *l_iter = l_first;
929 do {
930 short_edge_queue_edge_add(eq_ctx, l_iter->e);
931 } while ((l_iter = l_iter->next) != l_first);
932 }
933}
934
945static void long_edge_queue_create(const EdgeQueueContext *eq_ctx,
946 const float max_edge_len,
948 const float3 &center,
949 const std::optional<float3> view_normal,
950 const float radius,
951 const bool use_frontface,
952 const bool use_projected)
953{
955 view_normal || (!use_frontface && !use_projected),
956 "If either use_frontface or use_projected is specified, view_normal must be non-empty");
957
958 eq_ctx->queue->heap = BLI_heapsimple_new();
959 eq_ctx->queue->center = center;
960 eq_ctx->queue->radius_squared = radius * radius;
961 eq_ctx->queue->limit_len_squared = max_edge_len * max_edge_len;
962 eq_ctx->queue->limit_len = max_edge_len;
963
964 eq_ctx->queue->view_normal = view_normal;
965
966 eq_ctx->queue->use_front_face = use_frontface;
967
968 if (use_projected && view_normal) {
970 project_plane_normalized_v3_v3v3(eq_ctx->queue->center_proj, center, *view_normal);
971 }
972 else {
974 }
975
976 for (BMeshNode &node : nodes) {
977 /* Check leaf nodes marked for topology update. */
978 if ((node.flag_ & Node::Leaf) && (node.flag_ & Node::UpdateTopology) &&
979 !(node.flag_ & Node::FullyHidden))
980 {
981 for (BMFace *f : node.bm_faces_) {
982 long_edge_queue_face_add(eq_ctx, f);
983 }
984 }
985 }
986}
987
999 const float min_edge_len,
1001 const float3 &center,
1002 const std::optional<float3> view_normal,
1003 const float radius,
1004 const bool use_frontface,
1005 const bool use_projected)
1006{
1008 view_normal || (!use_frontface && !use_projected),
1009 "If either use_frontface or use_projected is specified, view_normal must be non-empty");
1010
1011 eq_ctx->queue->heap = BLI_heapsimple_new();
1012 eq_ctx->queue->center = center;
1013 eq_ctx->queue->radius_squared = radius * radius;
1014 eq_ctx->queue->limit_len_squared = min_edge_len * min_edge_len;
1015 eq_ctx->queue->limit_len = min_edge_len;
1016
1017 eq_ctx->queue->view_normal = view_normal;
1018
1019 eq_ctx->queue->use_front_face = use_frontface;
1020
1021 if (use_projected && view_normal) {
1023 project_plane_normalized_v3_v3v3(eq_ctx->queue->center_proj, center, *view_normal);
1024 }
1025 else {
1027 }
1028
1029 for (BMeshNode &node : nodes) {
1030 /* Check leaf nodes marked for topology update */
1031 if ((node.flag_ & Node::Leaf) && (node.flag_ & Node::UpdateTopology) &&
1032 !(node.flag_ & Node::FullyHidden))
1033 {
1034 for (BMFace *f : node.bm_faces_) {
1035 short_edge_queue_face_add(eq_ctx, f);
1036 }
1037 }
1038 }
1039}
1040
1041/*************************** Topology update **************************/
1042
1049static void copy_edge_data(BMesh &bm, BMEdge &dst, const BMEdge &src)
1050{
1051 dst.head.hflag = src.head.hflag & ~BM_ELEM_TAG;
1053}
1054
1055/* Merge edge custom data from src to dst. */
1056static void merge_edge_data(BMesh &bm, BMEdge &dst, const BMEdge &src)
1057{
1058 dst.head.hflag |= (src.head.hflag & ~(BM_ELEM_TAG | BM_ELEM_SMOOTH));
1059
1060 /* If either of the src or dst is sharp the result is sharp. */
1061 if ((src.head.hflag & BM_ELEM_SMOOTH) == 0) {
1062 dst.head.hflag &= ~BM_ELEM_SMOOTH;
1063 }
1064
1065 BM_data_interp_from_edges(&bm, &src, &dst, &dst, 0.5f);
1066}
1067
1068static void pbvh_bmesh_split_edge(const EdgeQueueContext *eq_ctx,
1069 BMesh &bm,
1071 MutableSpan<bool> node_changed,
1072 const int cd_vert_node_offset,
1073 const int cd_face_node_offset,
1074 BMLog &bm_log,
1075 BMEdge *e)
1076{
1077 /* Get all faces adjacent to the edge. */
1079
1080 /* Create a new vertex in current node at the edge's midpoint. */
1081 const float3 midpoint_co = math::midpoint<float3>(e->v1->co, e->v2->co);
1082 const float3 midpoint_no = math::normalize(math::midpoint<float3>(e->v1->no, e->v2->no));
1083
1084 int node_index = BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset);
1086 nodes,
1087 node_changed,
1088 bm_log,
1089 e->v1,
1090 e->v2,
1091 node_index,
1092 midpoint_co,
1093 midpoint_no,
1094 cd_vert_node_offset,
1095 eq_ctx->cd_vert_mask_offset);
1096
1097 /* For each face, add two new triangles and delete the original. */
1098 for (const int i : edge_loops.index_range()) {
1099 const BMLoop *l_adj = edge_loops[i];
1100 BMFace *f_adj = l_adj->f;
1101
1102 BLI_assert(f_adj->len == 3);
1103 const int ni = BM_ELEM_CD_GET_INT(f_adj, eq_ctx->cd_face_node_offset);
1104
1105 /* Find the vertex not in the edge. */
1106 BMVert *v_opp = l_adj->prev->v;
1107
1108 /* Get e->v1 and e->v2 in the order they appear in the existing face so that the new faces'
1109 * winding orders match. */
1110 BMVert *v1 = l_adj->v;
1111 BMVert *v2 = l_adj->next->v;
1112
1113 if (ni != node_index && i == 0) {
1114 pbvh_bmesh_vert_ownership_transfer(nodes, node_changed, cd_vert_node_offset, ni, v_new);
1115 }
1116
1117 /* The 2 new faces created and assigned to `f_new` have their
1118 * verts & edges shuffled around.
1119 *
1120 * - faces wind anticlockwise in this example.
1121 * - original edge is `(v1, v2)`
1122 * - original face is `(v1, v2, v3)`
1123 *
1124 * <pre>
1125 * + v_opp
1126 * /|\
1127 * / | \
1128 * / | \
1129 * e4/ | \ e3
1130 * / |e5 \
1131 * / | \
1132 * / e1 | e2 \
1133 * +-------+-------+
1134 * v1 v_new v2
1135 * (first) (second)
1136 * </pre>
1137 *
1138 * - f_new (first): `v_tri=(v1, v_new, v_opp), e_tri=(e1, e5, e4)`
1139 * - f_new (second): `v_tri=(v_new, v2, v_opp), e_tri=(e2, e3, e5)`
1140 */
1141
1142 /* Create first face (v1, v_new, v_opp). */
1143 const std::array<BMVert *, 3> first_tri({v1, v_new, v_opp});
1144 const std::array<BMEdge *, 3> first_edges = bm_edges_from_tri(bm, first_tri);
1145 copy_edge_data(bm, *first_edges[0], *e);
1146
1147 BMFace *f_new_first = pbvh_bmesh_face_create(
1148 bm, nodes, node_changed, cd_face_node_offset, bm_log, ni, first_tri, first_edges, f_adj);
1149 long_edge_queue_face_add(eq_ctx, f_new_first);
1150
1151 /* Create second face (v_new, v2, v_opp). */
1152 const std::array<BMVert *, 3> second_tri({v_new, v2, v_opp});
1153 const std::array<BMEdge *, 3> second_edges{
1154 BM_edge_create(&bm, second_tri[0], second_tri[1], nullptr, BM_CREATE_NO_DOUBLE),
1155 BM_edge_create(&bm, second_tri[1], second_tri[2], nullptr, BM_CREATE_NO_DOUBLE),
1156 first_edges[1],
1157 };
1158 copy_edge_data(bm, *second_edges[0], *e);
1159
1160 BMFace *f_new_second = pbvh_bmesh_face_create(
1161 bm, nodes, node_changed, cd_face_node_offset, bm_log, ni, second_tri, second_edges, f_adj);
1162 long_edge_queue_face_add(eq_ctx, f_new_second);
1163
1164 /* Delete original */
1166 nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, bm_log, f_adj);
1167 BM_face_kill(&bm, f_adj);
1168
1169 /* Ensure new vertex is in the node */
1170 if (!nodes[ni].bm_unique_verts_.contains(v_new)) {
1171 nodes[ni].bm_other_verts_.add(v_new);
1172 }
1173
1174 if (BM_vert_edge_count_is_over(v_opp, 8)) {
1175 BMIter bm_iter;
1176 BMEdge *e2;
1177 BM_ITER_ELEM (e2, &bm_iter, v_opp, BM_EDGES_OF_VERT) {
1178 long_edge_queue_edge_add(eq_ctx, e2);
1179 }
1180 }
1181 }
1182
1183 BM_edge_kill(&bm, e);
1184}
1185
1187 BMesh &bm,
1189 MutableSpan<bool> node_changed,
1190 const int cd_vert_node_offset,
1191 const int cd_face_node_offset,
1192 BMLog &bm_log)
1193{
1194 const double start_time = BLI_time_now_seconds();
1195
1196 bool any_subdivided = false;
1197
1198 while (!BLI_heapsimple_is_empty(eq_ctx->queue->heap)) {
1199 BMVert **pair = static_cast<BMVert **>(BLI_heapsimple_pop_min(eq_ctx->queue->heap));
1200 BMVert *v1 = pair[0];
1201 BMVert *v2 = pair[1];
1202
1203 BLI_mempool_free(eq_ctx->pool, pair);
1204 pair = nullptr;
1205
1206 /* Check that the edge still exists */
1207 BMEdge *e = BM_edge_exists(v1, v2);
1208 if (!e) {
1209 continue;
1210 }
1212
1214
1215 /* Check that the edge's vertices are still in the Tree. It's
1216 * possible that an edge collapse has deleted adjacent faces
1217 * and the node has been split, thus leaving wire edges and
1218 * associated vertices. */
1221 {
1222 continue;
1223 }
1224
1225 any_subdivided = true;
1226
1228 eq_ctx, bm, nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, bm_log, e);
1229 }
1230
1231 CLOG_DEBUG(&LOG, "Long edge subdivision took %f seconds.", BLI_time_now_seconds() - start_time);
1232
1233 return any_subdivided;
1234}
1235
1238{
1239 BMIter bm_iter;
1240 BMFace *face;
1241 BM_ITER_ELEM (face, &bm_iter, &edge, BM_FACES_OF_EDGE) {
1242 if (BM_vert_in_face(&vert, face)) {
1243 return true;
1244 }
1245 }
1246 return false;
1247}
1248
1266 const BMFace *del_face,
1267 const BMFace *flap_face,
1268 BMEdge *e,
1269 BMVert *v_del,
1270 const BMLoop *l_del,
1271 BMVert *v_conn)
1272{
1273 /*
1274 * v_del
1275 * +
1276 * del_face . / |
1277 * . / |
1278 * . / |
1279 * v1 +---------------------+ v2 |
1280 * . \ |
1281 * . \ |
1282 * . \ |
1283 * flap_face +
1284 * v_conn
1285 *
1286 *
1287 */
1288
1289 UNUSED_VARS_NDEBUG(del_face, flap_face);
1290
1291 /* Faces around `e` (which connects `v_del` to `v_conn`) are to the handled separately from this
1292 * function. Help troubleshooting cases where these faces are mistakenly considered flaps. */
1293 BLI_assert(!BM_edge_in_face(e, del_face));
1294 BLI_assert(!BM_edge_in_face(e, flap_face));
1295
1296 /* The `l_del->next->v` and `l_del->prev->v` are v1 and v2, but in an unknown order. */
1297 BMEdge *edge_v1_v2 = BM_edge_exists(l_del->next->v, l_del->prev->v);
1298 if (!edge_v1_v2) {
1299 CLOG_WARN(&LOG, "Unable to find edge shared between deleting and flap faces");
1300 return;
1301 }
1302
1303 BLI_assert(BM_edge_in_face(edge_v1_v2, del_face));
1304 BLI_assert(BM_edge_in_face(edge_v1_v2, flap_face));
1305
1306 /* Disambiguate v1 from v2: the v2 is adjacent to a face around #e. */
1307 BMVert *v2 = vert_in_face_adjacent_to_edge(*edge_v1_v2->v1, *e) ? edge_v1_v2->v1 :
1308 edge_v1_v2->v2;
1309 BMVert *v1 = BM_edge_other_vert(edge_v1_v2, v2);
1310
1311 /* Merge attributes into an edge (v1, v_conn). */
1312 BMEdge *dst_edge = BM_edge_exists(v1, v_conn);
1313
1314 const std::array<const BMEdge *, 4> source_edges{
1315 /* Edges of the `flap_face`.
1316 * The face will be deleted, effectively being "collapsed" into an edge. */
1317 edge_v1_v2,
1318 BM_edge_exists(v2, v_conn),
1319
1320 /* Edges of the `del_face`.
1321 * These edges are implicitly merged with the ones from the `flap_face` upon collapsing edge
1322 * `e`. */
1323 BM_edge_exists(v1, v_del),
1324 BM_edge_exists(v2, v_del),
1325 };
1326
1327 for (const BMEdge *src_edge : source_edges) {
1328 if (!src_edge) {
1329 CLOG_WARN(&LOG, "Unable to find source edge for flap attributes merge");
1330 continue;
1331 }
1332
1333 merge_edge_data(bm, *dst_edge, *src_edge);
1334 }
1335}
1336
1343{
1344 BMVert *flap_vert = nullptr;
1345
1346 BMIter bm_iter;
1347 BMVert *vert;
1348 BM_ITER_ELEM (vert, &bm_iter, &face, BM_VERTS_OF_FACE) {
1349 if (BM_vert_face_count_at_most(vert, 2) == 1) {
1350 if (flap_vert) {
1351 /* There are multiple vertices which become loose on removing the face and its edges. */
1352 return nullptr;
1353 }
1354 flap_vert = vert;
1355 }
1356 }
1357
1358 return flap_vert;
1359}
1360
1369{
1370 /*
1371 * v1 v2
1372 * ... ------ + ----------------- + ------ ...
1373 * \ /
1374 * \ /
1375 * \ /
1376 * \ /
1377 * \ /
1378 * + v_flap
1379 */
1380
1381 BMVert *v_flap = find_outer_flap_vert(face);
1382 if (!v_flap) {
1383 return;
1384 }
1385
1386 const BMLoop *l_flap = BM_vert_find_first_loop(v_flap);
1387 BLI_assert(l_flap->v == v_flap);
1388
1389 /* Edges which are adjacent ot the v_flap. */
1390 const BMEdge *edge_1 = l_flap->prev->e;
1391 const BMEdge *edge_2 = l_flap->e;
1392
1393 BLI_assert(BM_edge_face_count(edge_1) == 1);
1394 BLI_assert(BM_edge_face_count(edge_2) == 1);
1395
1396 BMEdge *edge_v1_v2 = l_flap->next->e;
1397
1398 merge_edge_data(bm, *edge_v1_v2, *edge_1);
1399 merge_edge_data(bm, *edge_v1_v2, *edge_2);
1400}
1401
1417 BMFace * /*del_face*/,
1418 BMFace *new_face,
1419 BMVert *v_del,
1420 const BMLoop *l_del,
1421 const BMVert *v_conn)
1422{
1423 /* When collapsing an edge (v_conn, v_del) a face (v_conn, v2, v_del) is to be deleted and the
1424 * v_del reference in the face (v_del, v2, v1) is to be replaced with v_conn. Doing vertex
1425 * reference replacement in BMesh is not trivial. so for the simplicity the
1426 * #pbvh_bmesh_collapse_edge deletes both original faces and creates new one (c_conn, v2, v1).
1427 *
1428 * When doing such re-creating attributes from old edges are to be merged into the new ones:
1429 * - Attributes of (v_del, v1) needs to be merged into (v_conn, v1),
1430 * - Attributes of (v_del, v2) needs to be merged into (v_conn, v2),
1431 *
1432 * <pre>
1433 *
1434 * v2
1435 * +
1436 * /|\
1437 * / | \
1438 * / | \
1439 * / | \
1440 * / | \
1441 * / | \
1442 * / | \
1443 * +-------+-------+
1444 * v_conn v_del v1
1445 *
1446 * </pre>
1447 */
1448
1449 /* The l_del->next->v and l_del->prev->v are v1 and v2, but in an unknown order. */
1450 BMEdge *edge_v1_v2 = BM_edge_exists(l_del->next->v, l_del->prev->v);
1451 if (!edge_v1_v2) {
1452 CLOG_WARN(&LOG, "Unable to find edge shared between old and new faces");
1453 return;
1454 }
1455
1456 BMIter bm_iter;
1457 BMEdge *dst_edge;
1458 BM_ITER_ELEM (dst_edge, &bm_iter, new_face, BM_EDGES_OF_FACE) {
1459 if (dst_edge == edge_v1_v2) {
1460 continue;
1461 }
1462
1463 BLI_assert(BM_vert_in_edge(dst_edge, v_conn));
1464
1465 /* Depending on an edge v_other will be v1 or v2. */
1466 BMVert *v_other = BM_edge_other_vert(dst_edge, v_conn);
1467
1468 const BMEdge *src_edge = BM_edge_exists(v_del, v_other);
1469 BLI_assert(src_edge);
1470
1471 if (src_edge) {
1472 merge_edge_data(bm, *dst_edge, *src_edge);
1473 }
1474 else {
1475 CLOG_WARN(&LOG, "Unable to find edge to merge attributes from");
1476 }
1477 }
1478}
1479
1482 MutableSpan<bool> node_changed,
1483 const int cd_vert_node_offset,
1484 const int cd_face_node_offset,
1485 BMLog &bm_log,
1486 BMEdge *e,
1487 BMVert *v1,
1488 BMVert *v2,
1489 Map<BMVert *, BMVert *> &deleted_verts,
1490 const EdgeQueueContext *eq_ctx)
1491{
1492 const bool v1_on_boundary = is_boundary_vert(*v1);
1493 const bool v2_on_boundary = is_boundary_vert(*v2);
1494
1495 BMVert *v_del;
1496 BMVert *v_conn;
1497 if (v1_on_boundary || v2_on_boundary) {
1498 /* Boundary edges can be collapsed with minimal distortion. For those it does not
1499 * matter too much which vertex to keep and which one to remove.
1500 *
1501 * For edges which are adjacent to boundaries, keep the vertex which is on boundary and
1502 * dissolve the other one. */
1503 if (v1_on_boundary) {
1504 v_del = v2;
1505 v_conn = v1;
1506 }
1507 else {
1508 v_del = v1;
1509 v_conn = v2;
1510 }
1511 }
1512 else if (BM_ELEM_CD_GET_FLOAT(v1, eq_ctx->cd_vert_mask_offset) <
1514 {
1515 /* Prefer deleting the vertex that is less masked. */
1516 v_del = v1;
1517 v_conn = v2;
1518 }
1519 else {
1520 v_del = v2;
1521 v_conn = v1;
1522 }
1523
1524 /* Remove the merge vertex from the Tree. */
1525 pbvh_bmesh_vert_remove(nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, v_del);
1526
1527 /* For all remaining faces of v_del, create a new face that is the
1528 * same except it uses v_conn instead of v_del */
1529 /* NOTE: this could be done with BM_vert_splice(), but that requires handling other issues like
1530 * duplicate edges, so it wouldn't really buy anything. */
1531 Vector<BMFace *, 16> deleted_faces;
1532
1533 BMLoop *l;
1535 BMFace *f_del = l->f;
1536
1537 /* Ignore faces around `e`: they will be deleted explicitly later on.
1538 * Without ignoring these faces the #bm_face_exists_tri_from_loop_vert() triggers an assert. */
1539 if (BM_edge_in_face(e, f_del)) {
1540 continue;
1541 }
1542
1543 /* Schedule the faces adjacent to the v_del for deletion first.
1544 * This way we know that it will be #existing_face which is deleted last when deleting faces
1545 * which forms a flap. */
1546 deleted_faces.append(f_del);
1547
1548 /* Check if a face using these vertices already exists. If so, skip adding this face and mark
1549 * the existing one for deletion as well. Prevents extraneous "flaps" from being created.
1550 * Check is similar to #BM_face_exists. */
1551 if (BMFace *existing_face = bm_face_exists_tri_from_loop_vert(l->next, v_conn)) {
1552 merge_flap_edge_data(bm, f_del, existing_face, e, v_del, l, v_conn);
1553
1554 deleted_faces.append(existing_face);
1555 }
1556 }
1558
1559 /* Remove all faces adjacent to the edge. */
1560 BMLoop *l_adj;
1561 while ((l_adj = e->l)) {
1562 BMFace *f_adj = l_adj->f;
1563
1565 nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, bm_log, f_adj);
1566 BM_face_kill(&bm, f_adj);
1567 }
1568
1569 /* Kill the edge. */
1571 BM_edge_kill(&bm, e);
1572
1574 /* Get vertices, replace use of v_del with v_conn */
1575 BMFace *f = l->f;
1576
1578 /* This case is handled above. */
1579 }
1580 else {
1581 const std::array<BMVert *, 3> v_tri{v_conn, l->next->v, l->prev->v};
1582
1583 BLI_assert(!BM_face_exists(v_tri.data(), 3));
1584 BMeshNode *n = pbvh_bmesh_node_from_face(nodes, cd_face_node_offset, f);
1585 const int ni = n - nodes.data();
1586 const std::array<BMEdge *, 3> e_tri = bm_edges_from_tri(bm, v_tri);
1587 BMFace *new_face = pbvh_bmesh_face_create(
1588 bm, nodes, node_changed, cd_face_node_offset, bm_log, ni, v_tri, e_tri, f);
1589
1590 merge_face_edge_data(bm, f, new_face, v_del, l, v_conn);
1591
1592 /* Ensure that v_conn is in the new face's node */
1593 if (!n->bm_unique_verts_.contains(v_conn)) {
1594 n->bm_other_verts_.add(v_conn);
1595 }
1596 }
1597 }
1599
1600 /* Delete the tagged faces. */
1601 for (BMFace *f_del : deleted_faces) {
1602 /* Get vertices and edges of face. */
1603 BLI_assert(f_del->len == 3);
1604 const BMLoop *l_iter = BM_FACE_FIRST_LOOP(f_del);
1605 const std::array<BMVert *, 3> v_tri{l_iter->v, l_iter->next->v, l_iter->next->next->v};
1606 const std::array<BMEdge *, 3> e_tri{l_iter->e, l_iter->next->e, l_iter->next->next->e};
1607
1608 /* if its sa flap face merge its "outer" edge data into "base", so that boundary is propagated
1609 * from edges which are about to be deleted to the base of the triangle and will stay attached
1610 * to the mesh. */
1612
1613 /* Remove the face */
1615 nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, bm_log, f_del);
1616 BM_face_kill(&bm, f_del);
1617
1618 /* Check if any of the face's edges are now unused by any
1619 * face, if so delete them */
1620 for (const int j : IndexRange(3)) {
1621 if (BM_edge_is_wire(e_tri[j])) {
1622 BM_edge_kill(&bm, e_tri[j]);
1623 }
1624 }
1625
1626 /* Check if any of the face's vertices are now unused, if so
1627 * remove them from the Tree */
1628 for (const int j : IndexRange(3)) {
1629 if ((v_tri[j] != v_del) && (v_tri[j]->e == nullptr)) {
1631 nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, v_tri[j]);
1632
1633 BM_log_vert_removed(&bm_log, v_tri[j], eq_ctx->cd_vert_mask_offset);
1634
1635 if (v_tri[j] == v_conn) {
1636 v_conn = nullptr;
1637 }
1638 deleted_verts.add_new(v_tri[j], nullptr);
1639 BM_vert_kill(&bm, v_tri[j]);
1640 }
1641 }
1642 }
1643
1644 /* If the v_conn was not removed above move it to the midpoint of v_conn and v_del. Doing so
1645 * helps avoiding long stretched and degenerated triangles.
1646 *
1647 * However, if the vertex is on a boundary, do not move it to preserve the shape of the
1648 * boundary. */
1649 if (v_conn != nullptr && !is_boundary_vert(*v_conn)) {
1650 BM_log_vert_before_modified(&bm_log, v_conn, eq_ctx->cd_vert_mask_offset);
1651 mid_v3_v3v3(v_conn->co, v_conn->co, v_del->co);
1652 add_v3_v3(v_conn->no, v_del->no);
1653 normalize_v3(v_conn->no);
1654 }
1655
1656 if (v_conn != nullptr) {
1657 /* Update bounding boxes attached to the connected vertex.
1658 * Note that we can often get-away without this but causes #48779. */
1659 BM_LOOPS_OF_VERT_ITER_BEGIN (l, v_conn) {
1660 const int f_node = pbvh_bmesh_node_index_from_face(cd_face_node_offset, l->f);
1661 node_changed[f_node] = true;
1662 }
1664 }
1665
1666 /* Delete v_del */
1668 BM_log_vert_removed(&bm_log, v_del, eq_ctx->cd_vert_mask_offset);
1669 /* v_conn == nullptr is OK */
1670 deleted_verts.add_new(v_del, v_conn);
1671 BM_vert_kill(&bm, v_del);
1672}
1673
1675 const float min_edge_len,
1676 BMesh &bm,
1678 MutableSpan<bool> node_changed,
1679 const int cd_vert_node_offset,
1680 const int cd_face_node_offset,
1681 BMLog &bm_log)
1682{
1683 const double start_time = BLI_time_now_seconds();
1684
1685 const float min_len_squared = min_edge_len * min_edge_len;
1686 bool any_collapsed = false;
1687 /* Deleted verts point to vertices they were merged into, or nullptr when removed. */
1688 Map<BMVert *, BMVert *> deleted_verts;
1689
1690 while (!BLI_heapsimple_is_empty(eq_ctx->queue->heap)) {
1691 BMVert **pair = static_cast<BMVert **>(BLI_heapsimple_pop_min(eq_ctx->queue->heap));
1692 BMVert *v1 = pair[0];
1693 BMVert *v2 = pair[1];
1694 BLI_mempool_free(eq_ctx->pool, pair);
1695 pair = nullptr;
1696
1697 /* Check the verts still exists. */
1698 v1 = bm_vert_hash_lookup_chain(deleted_verts, v1);
1699 v2 = bm_vert_hash_lookup_chain(deleted_verts, v2);
1700 if (!v1 || !v2 || (v1 == v2)) {
1701 continue;
1702 }
1703
1704 /* Check that the edge still exists. */
1705 BMEdge *e = BM_edge_exists(v1, v2);
1706 if (!e) {
1707 continue;
1708 }
1710
1711 if (len_squared_v3v3(v1->co, v2->co) >= min_len_squared) {
1712 continue;
1713 }
1714
1715 /* Check that the edge's vertices are still in the Tree. It's possible that
1716 * an edge collapse has deleted adjacent faces and the node has been split, thus leaving wire
1717 * edges and associated vertices. */
1720 {
1721 continue;
1722 }
1723
1724 any_collapsed = true;
1725
1727 nodes,
1728 node_changed,
1729 cd_vert_node_offset,
1730 cd_face_node_offset,
1731 bm_log,
1732 e,
1733 v1,
1734 v2,
1735 deleted_verts,
1736 eq_ctx);
1737 }
1738
1739 CLOG_DEBUG(&LOG, "Short edge collapse took %f seconds.", BLI_time_now_seconds() - start_time);
1740
1741 return any_collapsed;
1742}
1743
1744/************************* Called from pbvh.cc *************************/
1745
1747 const float3 &ray_start,
1748 const float3 &ray_normal,
1749 const IsectRayPrecalc *isect_precalc,
1750 float *depth,
1751 bool use_original,
1752 BMVert **r_active_vertex,
1753 float3 &r_face_normal)
1754{
1755 bool hit = false;
1756 float3 nearest_vertex_co(0.0f);
1757
1758 use_original = use_original && !node.orig_tris_.is_empty();
1759
1760 if (use_original) {
1761 for (const int tri_idx : node.orig_tris_.index_range()) {
1762 const std::array<float3, 3> positions = {node.orig_positions_[node.orig_tris_[tri_idx][0]],
1763 node.orig_positions_[node.orig_tris_[tri_idx][1]],
1764 node.orig_positions_[node.orig_tris_[tri_idx][2]]};
1765
1767 ray_start, isect_precalc, positions[0], positions[1], positions[2], depth))
1768 {
1769 hit = true;
1770
1771 r_face_normal = math::normal_tri(positions[0], positions[1], positions[2]);
1772
1773 if (r_active_vertex) {
1774 const float3 location = ray_start + ray_normal * *depth;
1775 for (int i = 0; i < positions.size(); i++) {
1776 if (i == 0 || math::distance_squared(location, positions[i]) <
1777 math::distance_squared(location, nearest_vertex_co))
1778 {
1779 nearest_vertex_co = positions[i];
1780 *r_active_vertex = node.orig_verts_[node.orig_tris_[tri_idx][i]];
1781 }
1782 }
1783 }
1784 }
1785 }
1786 }
1787 else {
1788 for (BMFace *f : node.bm_faces_) {
1789 BLI_assert(f->len == 3);
1790
1792 std::array<BMVert *, 3> v_tri;
1793 BM_face_as_array_vert_tri(f, v_tri.data());
1794
1795 std::array<float3, 3> positions = {v_tri[0]->co, v_tri[1]->co, v_tri[2]->co};
1796
1798 ray_start, isect_precalc, positions[0], positions[1], positions[2], depth))
1799 {
1800 hit = true;
1801
1802 r_face_normal = math::normal_tri(positions[0], positions[1], positions[2]);
1803
1804 if (r_active_vertex) {
1805 const float3 location = ray_start + ray_normal * *depth;
1806 for (int i = 0; i < positions.size(); i++) {
1807 if (i == 0 || math::distance_squared(location, positions[i]) <
1808 math::distance_squared(location, nearest_vertex_co))
1809 {
1810 nearest_vertex_co = positions[i];
1811 *r_active_vertex = v_tri[i];
1812 }
1813 }
1814 }
1815 }
1816 }
1817 }
1818 }
1819
1820 return hit;
1821}
1822
1824 const float3 &ray_start,
1825 const IsectRayPrecalc *isect_precalc,
1826 float *depth,
1827 float *r_edge_length)
1828{
1829 if (node.flag_ & Node::FullyHidden) {
1830 return false;
1831 }
1832
1833 bool hit = false;
1834 BMFace *f_hit = nullptr;
1835
1836 for (BMFace *f : node.bm_faces_) {
1837 BLI_assert(f->len == 3);
1839 std::array<BMVert *, 3> v_tri;
1840 BM_face_as_array_vert_tri(f, v_tri.data());
1842 ray_start, isect_precalc, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co, depth))
1843 {
1844 f_hit = f;
1845 hit = true;
1846 }
1847 }
1848 }
1849
1850 if (hit) {
1851 std::array<BMVert *, 3> v_tri;
1852 BM_face_as_array_vert_tri(f_hit, v_tri.data());
1853
1854 const float len1 = len_squared_v3v3(v_tri[0]->co, v_tri[1]->co);
1855 const float len2 = len_squared_v3v3(v_tri[1]->co, v_tri[2]->co);
1856 const float len3 = len_squared_v3v3(v_tri[2]->co, v_tri[0]->co);
1857
1858 /* Detail returned will be set to the maximum allowed size, so take max here. */
1859 *r_edge_length = sqrtf(std::max({len1, len2, len3}));
1860 }
1861
1862 return hit;
1863}
1864
1866 const float3 &ray_start,
1867 const float3 &ray_normal,
1868 float *r_depth,
1869 float *dist_sq,
1870 const bool use_original)
1871{
1872 bool hit = false;
1873
1874 if (use_original && !node.orig_tris_.is_empty()) {
1875 for (const int i : node.orig_tris_.index_range()) {
1876 const int *t = node.orig_tris_[i];
1877 hit |= ray_face_nearest_tri(ray_start,
1878 ray_normal,
1879 node.orig_positions_[t[0]],
1880 node.orig_positions_[t[1]],
1881 node.orig_positions_[t[2]],
1882 r_depth,
1883 dist_sq);
1884 }
1885 }
1886 else {
1887 for (BMFace *f : node.bm_faces_) {
1888 BLI_assert(f->len == 3);
1890 std::array<BMVert *, 3> v_tri;
1891 BM_face_as_array_vert_tri(f, v_tri.data());
1892
1893 hit |= ray_face_nearest_tri(
1894 ray_start, ray_normal, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co, r_depth, dist_sq);
1895 }
1896 }
1897 }
1898
1899 return hit;
1900}
1901
1902void bmesh_normals_update(Tree &pbvh, const IndexMask &nodes_to_update)
1903{
1904 const MutableSpan<BMeshNode> nodes = pbvh.nodes<BMeshNode>();
1905 nodes_to_update.foreach_index([&](const int i) {
1906 BMeshNode &node = nodes[i];
1907 for (BMFace *face : node.bm_faces_) {
1909 }
1910 for (BMVert *vert : node.bm_unique_verts_) {
1912 }
1913 for (BMVert *vert : node.bm_other_verts_) {
1915 }
1916 });
1917}
1918
1920 int totface; /* Number of faces. */
1921 int start; /* Start of faces in array. */
1924};
1925
1932 const Span<Bounds<float3>> face_bounds,
1934 MemArena *arena)
1935{
1936 if (node->totface <= leaf_limit) {
1937 return;
1938 }
1939
1940 /* Calculate bounding box around primitive centroids. */
1942 for (int i = 0; i < node->totface; i++) {
1943 const BMFace *f = nodeinfo[i + node->start];
1944 const int face_index = BM_elem_index_get(f);
1945 const float3 center = math::midpoint(face_bounds[face_index].min, face_bounds[face_index].max);
1946 math::min_max(center, cb.min, cb.max);
1947 }
1948
1949 /* Find widest axis and its midpoint. */
1950 const int axis = math::dominant_axis(cb.max - cb.min);
1951 const float mid = math::midpoint(cb.max[axis], cb.min[axis]);
1952
1953 int num_child1 = 0;
1954 int num_child2 = 0;
1955
1956 /* Split vertices along the middle line. */
1957 const int end = node->start + node->totface;
1958 for (int i = node->start; i < end - num_child2; i++) {
1959 const BMFace *f = nodeinfo[i];
1960 const int face_i = BM_elem_index_get(f);
1961
1962 if (math::midpoint(face_bounds[face_i].min[axis], face_bounds[face_i].max[axis]) > mid) {
1963 int i_iter = end - num_child2 - 1;
1964 int candidate = -1;
1965 /* Found a face that should be part of another node, look for a face to substitute with. */
1966
1967 for (; i_iter > i; i_iter--) {
1968 const BMFace *f_iter = nodeinfo[i_iter];
1969 const int face_iter_i = BM_elem_index_get(f_iter);
1970 if (math::midpoint(face_bounds[face_iter_i].min[axis],
1971 face_bounds[face_iter_i].max[axis]) <= mid)
1972 {
1973 candidate = i_iter;
1974 break;
1975 }
1976
1977 num_child2++;
1978 }
1979
1980 if (candidate != -1) {
1981 BMFace *tmp = nodeinfo[i];
1982 nodeinfo[i] = nodeinfo[candidate];
1983 nodeinfo[candidate] = tmp;
1984 /* Increase both counts. */
1985 num_child1++;
1986 num_child2++;
1987 }
1988 else {
1989 /* Not finding candidate means second half of array part is full of
1990 * second node parts, just increase the number of child nodes for it. */
1991 num_child2++;
1992 }
1993 }
1994 else {
1995 num_child1++;
1996 }
1997 }
1998
1999 /* Ensure at least one child in each node. */
2000 if (num_child2 == 0) {
2001 num_child2++;
2002 num_child1--;
2003 }
2004 else if (num_child1 == 0) {
2005 num_child1++;
2006 num_child2--;
2007 }
2008
2009 /* At this point, faces should have been split along the array range sequentially,
2010 * each sequential part belonging to one node only. */
2011 BLI_assert((num_child1 + num_child2) == node->totface);
2012
2013 /* Initialize the children. */
2014 FastNodeBuildInfo *child1 = static_cast<FastNodeBuildInfo *>(
2015 BLI_memarena_alloc(arena, sizeof(FastNodeBuildInfo)));
2016 FastNodeBuildInfo *child2 = static_cast<FastNodeBuildInfo *>(
2017 BLI_memarena_alloc(arena, sizeof(FastNodeBuildInfo)));
2018
2019 node->child1 = child1;
2020 node->child2 = child2;
2021
2022 child1->totface = num_child1;
2023 child1->start = node->start;
2024 child1->child1 = nullptr;
2025 child1->child2 = nullptr;
2026
2027 child2->totface = num_child2;
2028 child2->start = node->start + num_child1;
2029 child2->child1 = nullptr;
2030 child2->child2 = nullptr;
2031
2032 pbvh_bmesh_node_limit_ensure_fast(nodeinfo, face_bounds, child1, arena);
2033 pbvh_bmesh_node_limit_ensure_fast(nodeinfo, face_bounds, child2, arena);
2034}
2035
2037 const int cd_vert_node_offset,
2038 const int cd_face_node_offset,
2039 const Span<BMFace *> nodeinfo,
2040 const Span<Bounds<float3>> face_bounds,
2041 const FastNodeBuildInfo *node,
2042 const int node_index,
2043 const int parent_index)
2044{
2045 BLI_assert(parent_index >= -1);
2046 nodes[node_index].parent_ = parent_index;
2047
2048 /* Two cases, node does not have children or does have children. */
2049 if (node->child1) {
2050 int children_offset_ = nodes.size();
2051
2052 nodes[node_index].children_offset_ = children_offset_;
2053 nodes.resize(nodes.size() + 2);
2055 cd_vert_node_offset,
2056 cd_face_node_offset,
2057 nodeinfo,
2058 face_bounds,
2059 node->child1,
2060 children_offset_,
2061 node_index);
2063 cd_vert_node_offset,
2064 cd_face_node_offset,
2065 nodeinfo,
2066 face_bounds,
2067 node->child2,
2068 children_offset_ + 1,
2069 node_index);
2070 }
2071 else {
2072 /* Node does not have children so it's a leaf node, populate with faces and tag accordingly
2073 * this is an expensive part but it's not so easily thread-able due to vertex node indices. */
2074
2075 nodes[node_index].flag_ |= Node::Leaf;
2076 nodes[node_index].bm_faces_.reserve(node->totface);
2077
2078 const int end = node->start + node->totface;
2079
2080 for (int i = node->start; i < end; i++) {
2081 BMFace *f = nodeinfo[i];
2082
2083 /* Update ownership of faces. */
2084 nodes[node_index].bm_faces_.add_new(f);
2085 BM_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
2086
2087 /* Update vertices. */
2088 const BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
2089 const BMLoop *l_iter = l_first;
2090 do {
2091 BMVert *v = l_iter->v;
2092 if (!nodes[node_index].bm_unique_verts_.contains(v)) {
2093 if (BM_ELEM_CD_GET_INT(v, cd_vert_node_offset) != dyntopo_node_none) {
2094 nodes[node_index].bm_other_verts_.add(v);
2095 }
2096 else {
2097 nodes[node_index].bm_unique_verts_.add(v);
2098 BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
2099 }
2100 }
2101 } while ((l_iter = l_iter->next) != l_first);
2102 }
2103 }
2104}
2105
2106/***************************** Public API *****************************/
2107
2109{
2112 if (bm.totface == 0) {
2113 return pbvh;
2114 }
2115
2116 const int cd_vert_node_offset = CustomData_get_offset_named(
2117 &bm.vdata, CD_PROP_INT32, ".sculpt_dyntopo_node_id_vertex");
2118 const int cd_face_node_offset = CustomData_get_offset_named(
2119 &bm.pdata, CD_PROP_INT32, ".sculpt_dyntopo_node_id_face");
2120
2121 /* bounding box array of all faces, no need to recalculate every time. */
2122 Array<Bounds<float3>> face_bounds(bm.totface);
2123 Array<BMFace *> nodeinfo(bm.totface);
2124 MemArena *arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "fast Tree node storage");
2125
2126 BMIter iter;
2127 BMFace *f;
2128 int i;
2129 BM_ITER_MESH_INDEX (f, &iter, &bm, BM_FACES_OF_MESH, i) {
2130 face_bounds[i] = negative_bounds();
2131
2132 const BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
2133 const BMLoop *l_iter = l_first;
2134 do {
2135 math::min_max(float3(l_iter->v->co), face_bounds[i].min, face_bounds[i].max);
2136 } while ((l_iter = l_iter->next) != l_first);
2137
2138 /* so we can do direct lookups on 'face_bounds' */
2139 BM_elem_index_set(f, i); /* set_dirty! */
2140 nodeinfo[i] = f;
2141 BM_ELEM_CD_SET_INT(f, cd_face_node_offset, dyntopo_node_none);
2142 }
2143 /* Likely this is already dirty. */
2145
2146 BMVert *v;
2147 BM_ITER_MESH (v, &iter, &bm, BM_VERTS_OF_MESH) {
2148 BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, dyntopo_node_none);
2149 }
2150
2151 /* Set up root node. */
2152 FastNodeBuildInfo rootnode = {0};
2153 rootnode.totface = bm.totface;
2154
2155 /* Start recursion, assign faces to nodes accordingly. */
2156 pbvh_bmesh_node_limit_ensure_fast(nodeinfo, face_bounds, &rootnode, arena);
2157
2158 /* We now have all faces assigned to a node,
2159 * next we need to assign those to the gsets of the nodes. */
2160
2161 /* Start with all faces in the root node. */
2162 /* Take root node and visit and populate children recursively. */
2163 Vector<BMeshNode> &nodes = std::get<Vector<BMeshNode>>(pbvh.nodes_);
2164 nodes.resize(1);
2166 nodes, cd_vert_node_offset, cd_face_node_offset, nodeinfo, face_bounds, &rootnode, 0, -1);
2167
2168 pbvh.tag_positions_changed(nodes.index_range());
2169 pbvh.update_bounds_bmesh(bm);
2171
2172 threading::parallel_for(nodes.index_range(), 8, [&](const IndexRange range) {
2173 for (const int i : range) {
2174 const Set<BMFace *, 0> &faces = BKE_pbvh_bmesh_node_faces(&nodes[i]);
2175 if (std::all_of(faces.begin(),
2176 faces.end(),
2177 [&](const BMFace *face) { return BM_elem_flag_test(face, BM_ELEM_HIDDEN); }))
2178 {
2179 nodes[i].flag_ |= Node::FullyHidden;
2180 }
2181 }
2182 });
2183
2184 update_mask_bmesh(bm, nodes.index_range(), pbvh);
2185
2186 BLI_memarena_free(arena);
2187 return pbvh;
2188}
2189
2191 Tree &pbvh,
2192 BMLog &bm_log,
2194 const float min_edge_len,
2195 const float max_edge_len,
2196 const float3 &center,
2197 const std::optional<float3> &view_normal,
2198 float radius,
2199 const bool use_frontface,
2200 const bool use_projected)
2201{
2202 const int cd_vert_node_offset = CustomData_get_offset_named(
2203 &bm.vdata, CD_PROP_INT32, ".sculpt_dyntopo_node_id_vertex");
2204 const int cd_face_node_offset = CustomData_get_offset_named(
2205 &bm.pdata, CD_PROP_INT32, ".sculpt_dyntopo_node_id_face");
2206 const int cd_vert_mask_offset = CustomData_get_offset_named(
2207 &bm.vdata, CD_PROP_FLOAT, ".sculpt_mask");
2208
2209 bool modified = false;
2210
2211 BLI_assert_msg(!view_normal || math::length_squared(*view_normal) > 0.0f,
2212 "View normal must be non-zero length if provided");
2213
2215 Array<bool> node_changed(nodes.size(), false);
2216
2217 if (mode & PBVH_Collapse) {
2218 EdgeQueue queue;
2219 BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *) * 2, 0, 128, BLI_MEMPOOL_NOP);
2220 EdgeQueueContext eq_ctx = {
2221 &queue,
2222 queue_pool,
2223 &bm,
2224 cd_vert_mask_offset,
2225 cd_vert_node_offset,
2226 cd_face_node_offset,
2227 };
2228
2230 &eq_ctx, min_edge_len, nodes, center, view_normal, radius, use_frontface, use_projected);
2231 modified |= pbvh_bmesh_collapse_short_edges(&eq_ctx,
2232 min_edge_len,
2233 bm,
2234 nodes,
2235 node_changed,
2236 cd_vert_node_offset,
2237 cd_face_node_offset,
2238 bm_log);
2239 BLI_heapsimple_free(queue.heap, nullptr);
2240 BLI_mempool_destroy(queue_pool);
2241 }
2242
2243 if (mode & PBVH_Subdivide) {
2244 EdgeQueue q;
2245 BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *) * 2, 0, 128, BLI_MEMPOOL_NOP);
2246 EdgeQueueContext eq_ctx = {
2247 &q,
2248 queue_pool,
2249 &bm,
2250 cd_vert_mask_offset,
2251 cd_vert_node_offset,
2252 cd_face_node_offset,
2253 };
2254
2256 &eq_ctx, max_edge_len, nodes, center, view_normal, radius, use_frontface, use_projected);
2258 &eq_ctx, bm, nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, bm_log);
2259 BLI_heapsimple_free(q.heap, nullptr);
2260 BLI_mempool_destroy(queue_pool);
2261 }
2262
2263 IndexMaskMemory memory;
2264 const IndexMask node_mask = IndexMask::from_bools(node_changed, memory);
2265 pbvh.tag_positions_changed(node_mask);
2266 pbvh.tag_topology_changed(node_mask);
2267
2268 /* Unmark nodes. */
2269 for (Node &node : nodes) {
2270 if (node.flag_ & Node::Leaf && node.flag_ & Node::UpdateTopology) {
2271 node.flag_ &= ~Node::UpdateTopology;
2272 }
2273 }
2274
2275 /* Go over all changed nodes and check if anything needs to be updated. */
2276 for (BMeshNode &node : nodes) {
2277 if (node.flag_ & Node::Leaf && node.flag_ & Node::TopologyUpdated) {
2278 node.flag_ &= ~Node::TopologyUpdated;
2279
2280 if (!node.orig_tris_.is_empty()) {
2281 /* Reallocate original triangle data. */
2283 BKE_pbvh_bmesh_node_save_orig(&bm, &bm_log, &node, true);
2284 }
2285 }
2286 }
2287
2288 return modified;
2289}
2290
2291/* Updates a given Tree Node with the original coordinates of the corresponding
2292 * BMesh vertex. Attempts to retrieve the value from the BMLog, falls back to the vertex's current
2293 * coordinates if it is either not found in the log or not requested. */
2294static void copy_original_vert(BMLog *log, BMeshNode *node, BMVert *v, int i, bool use_original)
2295{
2296 if (!use_original) {
2297 node->orig_positions_[i] = v->co;
2298 }
2299 else {
2300 const float *origco = BM_log_find_original_vert_co(log, v);
2301 if (origco) {
2302 node->orig_positions_[i] = origco;
2303 }
2304 else {
2305 node->orig_positions_[i] = v->co;
2306 }
2307 }
2308
2309 node->orig_verts_[i] = v;
2310}
2311
2312} // namespace bke::pbvh
2313
2315 BMLog *log,
2317 bool use_original)
2318{
2319 /* Skip if original coords/triangles are already saved. */
2320 if (!node->orig_tris_.is_empty()) {
2321 return;
2322 }
2323
2324 const int totvert = node->bm_unique_verts_.size() + node->bm_other_verts_.size();
2325
2326 node->orig_positions_.reinitialize(totvert);
2327 node->orig_verts_.reinitialize(totvert);
2328
2329 VectorSet<BMVert *> vert_map;
2330 vert_map.reserve(totvert);
2331
2332 /* Copy out the vertices and assign a temporary index. */
2333 int i = 0;
2334 for (BMVert *v : node->bm_unique_verts_) {
2335 bke::pbvh::copy_original_vert(log, node, v, i, use_original);
2336 vert_map.add(v);
2337 i++;
2338 }
2339 for (BMVert *v : node->bm_other_verts_) {
2340 bke::pbvh::copy_original_vert(log, node, v, i, use_original);
2341 vert_map.add(v);
2342 i++;
2343 }
2344 /* Likely this is already dirty. */
2346
2347 /* Copy the triangles */
2348 const int tris_num = std::count_if(
2349 node->bm_faces_.begin(), node->bm_faces_.end(), [&](const BMFace *face) {
2350 return !BM_elem_flag_test_bool(face, BM_ELEM_HIDDEN);
2351 });
2352 node->orig_tris_.reinitialize(tris_num);
2353 i = 0;
2354 for (BMFace *f : node->bm_faces_) {
2356 continue;
2357 }
2358 const std::array<BMVert *, 3> verts = bke::pbvh::bm_face_as_array(*f);
2359 node->orig_tris_[i] = int3(
2360 vert_map.index_of(verts[0]), vert_map.index_of(verts[1]), vert_map.index_of(verts[2]));
2361 i++;
2362 }
2363}
2364
2366{
2367 const int cd_vert_node_offset = CustomData_get_offset_named(
2368 &bm.vdata, CD_PROP_INT32, ".sculpt_dyntopo_node_id_vertex");
2369 const int cd_face_node_offset = CustomData_get_offset_named(
2370 &bm.pdata, CD_PROP_INT32, ".sculpt_dyntopo_node_id_face");
2371
2372 Vector<bke::pbvh::BMeshNode> &nodes = std::get<Vector<bke::pbvh::BMeshNode>>(pbvh.nodes_);
2373 Vector<bool> node_changed(nodes.size(), false);
2374 const IndexRange orig_range = nodes.index_range();
2375 for (const int i : orig_range) {
2376 bke::pbvh::BMeshNode *n = &nodes[i];
2377 if (n->flag_ & bke::pbvh::Node::Leaf) {
2378 /* Free `orco` / `ortri` data. */
2379 pbvh_bmesh_node_drop_orig(n);
2380
2381 /* Recursively split nodes that have gotten too many elements. */
2382 pbvh_bmesh_node_limit_ensure(
2383 bm, nodes, node_changed, cd_vert_node_offset, cd_face_node_offset, i);
2384 }
2385 }
2386
2387 IndexMaskMemory memory;
2388 const IndexMask node_mask = IndexMask::from_bools(node_changed, memory);
2389 pbvh.tag_positions_changed(node_mask);
2390 pbvh.tag_topology_changed(node_mask);
2391 update_mask_bmesh(bm, node_mask, pbvh);
2392}
2393
2398
2400{
2401 return node->bm_unique_verts_;
2402}
2403
2405{
2406 return node->bm_other_verts_;
2407}
2408
2410{
2411 return node->bm_faces_;
2412}
2413
2414} // namespace blender
A BVH for high poly meshes.
A min-heap / priority queue ADT.
#define BLI_MEMARENA_STD_BUFSIZE
Platform independent time functions.
#define CLOG_DEBUG(clg_ref,...)
Definition CLG_log.h:191
#define CLOG_WARN(clg_ref,...)
Definition CLG_log.h:189
#define PRF_scope(category)
#define UNUSED_VARS_NDEBUG(...)
#define BLI_INLINE
#define ELEM(...)
#define BLI_assert_msg(a, msg)
#define BM_ELEM_CD_GET_FLOAT(ele, offset)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_ELEM_CD_GET_INT(ele, offset)
#define BM_ELEM_CD_SET_INT(ele, offset, f)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_test_bool(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
#define BM_vert_face_count_is_equal(v, n)
#define BM_vert_edge_count_is_over(v, n)
btScalar max
int64_t size() const
Definition BLI_array.hh:267
Array(Allocator allocator={}) noexcept
Definition BLI_array.hh:78
const T * data() const
Definition BLI_array.hh:323
IndexRange index_range() const
Definition BLI_array.hh:371
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
constexpr IndexRange()=default
const Value * lookup_ptr(const Key &key) const
Definition BLI_map.hh:508
void add_new(const Key &key, const Value &value)
Definition BLI_map.hh:265
bool add(const Key &key)
Definition BLI_set.hh:248
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr Span()=default
bool add(const Key &key)
void reserve(const int64_t n)
int64_t index_of(const Key &key) const
int64_t size() const
void append(const T &value)
IndexRange index_range() const
void resize(const int64_t new_size)
Bounds< float3 > bounds_
Bounds< float3 > bounds_orig_
Tree(const Tree &other)=delete
static Tree from_bmesh(BMesh &bm)
Span< NodeT > nodes() const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define vertex
#define log
static void edge_queue_insert(const EdgeQueueContext *eq_ctx, BMEdge *e, const float priority)
static BMFace * pbvh_bmesh_face_create(BMesh &bm, MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_face_node_offset, BMLog &bm_log, const int node_index, const Span< BMVert * > v_tri, const Span< BMEdge * > e_tri, const BMFace *f_example)
static void long_edge_queue_edge_add_recursive(const EdgeQueueContext *eq_ctx, const BMLoop *l_edge, const BMLoop *l_end, const float len_sq, const float limit_len)
static std::array< BMEdge *, 3 > bm_edges_from_tri(BMesh &bm, const Span< BMVert * > v_tri)
static void long_edge_queue_face_add(const EdgeQueueContext *eq_ctx, BMFace *f)
static bool check_mask(const EdgeQueueContext *eq_ctx, const BMVert *v)
static void pbvh_bmesh_vert_remove(MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, BMVert *v)
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 void long_edge_queue_create(const EdgeQueueContext *eq_ctx, const float max_edge_len, MutableSpan< BMeshNode > nodes, const float3 &center, const std::optional< float3 > view_normal, const float radius, const bool use_frontface, const bool use_projected)
static void pbvh_bmesh_node_split(Vector< BMeshNode > &nodes, Vector< bool > &node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, const Span< Bounds< float3 > > face_bounds, const int node_index)
void update_mask_bmesh(const BMesh &bm, const IndexMask &node_mask, Tree &pbvh)
Definition pbvh.cc:1421
static void pbvh_bmesh_vert_ownership_transfer(MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_vert_node_offset, const int new_owner_index, BMVert *v)
static void pbvh_bmesh_collapse_edge(BMesh &bm, MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, BMLog &bm_log, BMEdge *e, BMVert *v1, BMVert *v2, Map< BMVert *, BMVert * > &deleted_verts, const EdgeQueueContext *eq_ctx)
static BMVert * pbvh_bmesh_vert_create(BMesh &bm, MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, BMLog &bm_log, const BMVert *v1, const BMVert *v2, const int node_index, const float3 &co, const float3 &no, const int cd_vert_node_offset, const int cd_vert_mask_offset)
static void pbvh_bmesh_create_nodes_fast_recursive(Vector< BMeshNode > &nodes, const int cd_vert_node_offset, const int cd_face_node_offset, const Span< BMFace * > nodeinfo, const Span< Bounds< float3 > > face_bounds, const FastNodeBuildInfo *node, const int node_index, const int parent_index)
BLI_INLINE int pbvh_bmesh_node_index_from_face(const int cd_face_node_offset, const BMFace *key)
static BMVert * bm_vert_hash_lookup_chain(Map< BMVert *, BMVert * > &deleted_verts, BMVert *v)
static void copy_original_vert(BMLog *log, BMeshNode *node, BMVert *v, int i, bool use_original)
BLI_INLINE std::array< BMVert *, 3 > bm_face_as_array(const BMFace &f)
static BMVert * find_outer_flap_vert(BMFace &face)
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 bool pbvh_bmesh_node_limit_ensure(BMesh &bm, Vector< BMeshNode > &nodes, Vector< bool > &node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, const int node_index)
void bmesh_normals_update(Tree &pbvh, const IndexMask &nodes_to_update)
static void short_edge_queue_create(const EdgeQueueContext *eq_ctx, const float min_edge_len, MutableSpan< BMeshNode > nodes, const float3 &center, const std::optional< float3 > view_normal, const float radius, const bool use_frontface, const bool use_projected)
static bool pbvh_bmesh_subdivide_long_edges(const EdgeQueueContext *eq_ctx, BMesh &bm, MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, BMLog &bm_log)
bool node_raycast_bmesh(BMeshNode &node, const float3 &ray_start, const float3 &ray_normal, const IsectRayPrecalc *isect_precalc, float *depth, bool use_original, BMVert **r_active_vertex, float3 &r_face_normal)
static bool pbvh_bmesh_collapse_short_edges(const EdgeQueueContext *eq_ctx, const float min_edge_len, BMesh &bm, MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, BMLog &bm_log)
static Bounds< float3 > negative_bounds()
Definition pbvh.cc:52
static bool is_boundary_edge(const BMEdge &edge)
static void pbvh_bmesh_split_edge(const EdgeQueueContext *eq_ctx, BMesh &bm, MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, BMLog &bm_log, BMEdge *e)
static BMFace * bm_face_exists_tri_from_loop_vert(const BMLoop *l_radial_first, const BMVert *v_opposite)
static bool edge_queue_tri_in_sphere(const EdgeQueue *queue, BMFace *f)
static void merge_edge_data(BMesh &bm, BMEdge &dst, const BMEdge &src)
static constexpr int dyntopo_node_none
Definition pbvh_bmesh.cc:39
static void short_edge_queue_edge_add(const EdgeQueueContext *eq_ctx, BMEdge *e)
static void try_merge_flap_edge_data_before_dissolve(BMesh &bm, BMFace &face)
static std::optional< int > pbvh_bmesh_vert_other_node_find(const int cd_vert_node_offset, const int cd_face_node_offset, BMVert *v)
BLI_INLINE BMeshNode * pbvh_bmesh_node_from_vert(MutableSpan< BMeshNode > nodes, const int cd_vert_node_offset, const BMVert *key)
bool bmesh_update_topology(BMesh &bm, Tree &pbvh, BMLog &bm_log, PBVHTopologyUpdateMode mode, float min_edge_len, float max_edge_len, const float3 &center, const std::optional< float3 > &view_normal, float radius, bool use_frontface, bool use_projected)
static void merge_flap_edge_data(BMesh &bm, const BMFace *del_face, const BMFace *flap_face, BMEdge *e, BMVert *v_del, const BMLoop *l_del, BMVert *v_conn)
bool raycast_node_detail_bmesh(const BMeshNode &node, const float3 &ray_start, const IsectRayPrecalc *isect_precalc, float *depth, float *r_edge_length)
static void merge_face_edge_data(BMesh &bm, BMFace *, BMFace *new_face, BMVert *v_del, const BMLoop *l_del, const BMVert *v_conn)
static void pbvh_bmesh_node_drop_orig(BMeshNode *node)
static void copy_edge_data(BMesh &bm, BMEdge &dst, const BMEdge &src)
static void pbvh_bmesh_node_limit_ensure_fast(const MutableSpan< BMFace * > nodeinfo, const Span< Bounds< float3 > > face_bounds, FastNodeBuildInfo *node, MemArena *arena)
static void pbvh_bmesh_node_finalize(BMeshNode &n, const int node_index, const int cd_vert_node_offset, const int cd_face_node_offset)
BLI_INLINE int pbvh_bmesh_node_index_from_vert(const int cd_vert_node_offset, const BMVert *key)
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
static void short_edge_queue_face_add(const EdgeQueueContext *eq_ctx, BMFace *f)
BLI_INLINE BMeshNode * pbvh_bmesh_node_from_face(MutableSpan< BMeshNode > nodes, const int cd_face_node_offset, const BMFace *key)
static bool vert_in_face_adjacent_to_edge(BMVert &vert, BMEdge &edge)
static float long_edge_queue_priority(const BMEdge &edge)
static bool is_boundary_vert(const BMVert &vertex)
static float short_edge_queue_priority(const BMEdge &edge)
void store_bounds_orig(Tree &pbvh)
Definition pbvh.cc:1332
constexpr int leaf_limit
Definition pbvh_bmesh.cc:37
static void pbvh_bmesh_face_remove(MutableSpan< BMeshNode > nodes, MutableSpan< bool > node_changed, const int cd_vert_node_offset, const int cd_face_node_offset, BMLog &bm_log, BMFace *f)
static Array< BMLoop * > pbvh_bmesh_edge_loops(BMEdge *e)
static bool is_edge_adjacent_to_boundary(const BMEdge &edge)
static void long_edge_queue_edge_add(const EdgeQueueContext *eq_ctx, BMEdge *e)
static int pbvh_bmesh_node_vert_use_count_at_most(MutableSpan< BMeshNode > nodes, const int cd_face_node_offset, const BMeshNode *node, BMVert *v, const int count_max)
static bool edge_queue_tri_in_circle(const EdgeQueue *queue, BMFace *f)
Bounds< T > merge(const Bounds< T > &a, const Bounds< T > &b)
Definition BLI_bounds.hh:27
T length_squared(const VecBase< T, Size > &a)
VecBase< T, 3 > normal_tri(const VecBase< T, 3 > &v1, const VecBase< T, 3 > &v2, const VecBase< T, 3 > &v3)
T midpoint(const T &a, const T &b)
void min_max(const T &value, T &min, T &max)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
int dominant_axis(const VecBase< T, 3 > &a)
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
BMesh Iterators.
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
int BM_edge_face_count(const BMEdge *e)
void BM_log_face_added(BMLog *log, BMFace *f)
Definition bmesh_log.cc:688
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
const Set< BMFace *, 0 > & BKE_pbvh_bmesh_node_faces(bke::pbvh::BMeshNode *node)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
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
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_vert_kill(BMesh *bm, BMVert *v)
void BM_log_vert_added(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
Definition bmesh_log.cc:671
void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v
void CustomData_bmesh_copy_block(CustomData &data, void *src_block, void **dst_block)
BMVert * BM_vert_create(BMesh *bm, const float co[3], const BMVert *v_example, const eBMCreateFlag create_flag)
Main function for creating a new vertex.
void BM_data_interp_from_edges(BMesh *bm, const BMEdge *e_src_1, const BMEdge *e_src_2, BMEdge *e_dst, const float fac)
Data, Interpolate From Edges.
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BMFace * BM_face_create(BMesh *bm, BMVert *const *verts, BMEdge *const *edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BM_log_vert_removed(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
Definition bmesh_log.cc:700
void BM_vert_normal_update(BMVert *v)
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
Global G
Definition blender.cc:57
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
void BKE_pbvh_bmesh_node_save_orig(BMesh *bm, BMLog *log, bke::pbvh::BMeshNode *node, bool use_original)
VecBase< int32_t, 3 > int3
@ BM_CREATE_NO_DOUBLE
Definition bmesh_core.hh:36
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
void BM_face_normal_update(BMFace *f)
void BM_edge_kill(BMesh *bm, BMEdge *e)
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
int CustomData_get_offset_named(const CustomData *data, eCustomDataType type, StringRef name)
BMLoop * BM_vert_find_first_loop(BMVert *v)
void BKE_pbvh_bmesh_after_stroke(BMesh &bm, bke::pbvh::Tree &pbvh)
bool BM_vert_in_face(BMVert *v, BMFace *f)
const Set< BMVert *, 0 > & BKE_pbvh_bmesh_node_other_verts(bke::pbvh::BMeshNode *node)
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
int BM_vert_face_count_at_most(const BMVert *v, int count_max)
HeapSimple * BLI_heapsimple_new() ATTR_WARN_UNUSED_RESULT
BMFace * BM_face_exists(BMVert *const *varr, int len)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
MINLINE float normalize_v3(float n[3])
void BM_face_as_array_vert_tri(BMFace *f, BMVert *r_verts[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
float BM_edge_calc_length_squared(const BMEdge *e)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
void BM_log_face_removed(BMLog *log, BMFace *f)
Definition bmesh_log.cc:724
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void BM_face_kill(BMesh *bm, BMFace *f)
@ BLI_MEMPOOL_NOP
MINLINE float max_ff(float a, float b)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
MINLINE float square_f(float a)
static CLG_LogRef LOG
Definition logging.cpp:12
double BLI_time_now_seconds()
Definition time.cc:30
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
void BM_data_interp_from_verts(BMesh *bm, const BMVert *v_src_1, const BMVert *v_src_2, BMVert *v_dst, const float fac)
Data, Interpolate From Verts.
VecBase< float, 3 > float3
void BKE_pbvh_node_mark_topology_update(bke::pbvh::Node &node)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BM_log_vert_before_modified(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
Definition bmesh_log.cc:656
const float * BM_log_find_original_vert_co(BMLog *log, BMVert *v)
Definition bmesh_log.cc:788
const Set< BMVert *, 0 > & BKE_pbvh_bmesh_node_unique_verts(bke::pbvh::BMeshNode *node)
BMEdge * BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
Main function for creating a new edge.
int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, const int len)
Iterator as Array.
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
bool BM_vert_face_check(const BMVert *v)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
#define BM_LOOPS_OF_VERT_ITER_END
Definition pbvh_bmesh.cc:71
#define BM_FACES_OF_VERT_ITER_BEGIN(f_iter_, v_)
Definition pbvh_bmesh.cc:84
#define pbvh_bmesh_node_vert_use_count_is_equal(nodes, cd_face_node_offset, node, v, n)
#define BM_LOOPS_OF_VERT_ITER_BEGIN(l_iter_radial_, v_)
Definition pbvh_bmesh.cc:54
#define BM_FACES_OF_VERT_ITER_END
Definition pbvh_bmesh.cc:90
#define EDGE_QUEUE_DISABLE(e)
#define EDGE_QUEUE_ENABLE(e)
#define EDGE_QUEUE_TEST(e)
#define sqrtf
#define min(a, b)
Definition sort.cc:38
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
CustomData pdata
CustomData vdata
CustomData edata
Set< BMVert *, 0 > bm_unique_verts_
Set< BMVert *, 0 > bm_other_verts_
std::optional< float3 > view_normal
bool(*) edge_queue_tri_in_range(const EdgeQueue *q, BMFace *f)