Blender V5.3
bmo_join_triangles.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
13
14#include <algorithm>
15
16#include "MEM_guardedalloc.h"
17
18#include "BLI_heap.hh"
19#include "BLI_math_base_c.hh"
20#include "BLI_math_geom_c.hh"
22#include "BLI_math_vector_c.hh"
23
24#include "BKE_customdata.hh"
25
26#include "bmesh.hh"
27
28#include "intern/bmesh_operators_private.hh" /* own include */
29
30namespace blender {
31
35#define ASSERT_VALID_ERROR_METRIC(val) BLI_assert(isfinite(val) && (val) >= 0 && (val) <= 2 * M_PI)
36
37#if 0
80# define USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
81#endif
82
83#define FACE_OUT (1 << 0)
84#define FACE_INPUT (1 << 2)
85
94constexpr float maximum_improvement = 0.99f;
95
96/* -------------------------------------------------------------------- */
100
104
110
113
116
119
120#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
122 BMesh *debug_bm;
123
128 int debug_merge_limit;
129
131 int debug_merge_count;
132
140 int debug_neighbor;
141
146 int debug_neighbor_global_count;
147
153 bool debug_this_step;
154#endif
155};
156
158/* -------------------------------------------------------------------- */
159
173static float quad_calc_error(const float v1[3],
174 const float v2[3],
175 const float v3[3],
176 const float v4[3])
177{
178 float error = 0.0f;
179
180 /* Normal difference: a perfectly flat planar face adds a difference of zero. */
181 {
182 float n1[3], n2[3];
183 float angle_a, angle_b;
184 float diff;
185
186 normal_tri_v3(n1, v1, v2, v3);
187 normal_tri_v3(n2, v1, v3, v4);
188 angle_a = compare_v3v3(n1, n2, FLT_EPSILON) ? 0.0f : angle_normalized_v3v3(n1, n2);
189
190 normal_tri_v3(n1, v2, v3, v4);
191 normal_tri_v3(n2, v4, v1, v2);
192 angle_b = compare_v3v3(n1, n2, FLT_EPSILON) ? 0.0f : angle_normalized_v3v3(n1, n2);
193
194 diff = (angle_a + angle_b) / float(M_PI * 2);
195
197
198 error += diff;
199 }
200
201 /* Co-linearity: a face with four right angle corners adds a difference of zero. */
202 {
203 float edge_vecs[4][3];
204 float diff;
205
206 sub_v3_v3v3(edge_vecs[0], v1, v2);
207 sub_v3_v3v3(edge_vecs[1], v2, v3);
208 sub_v3_v3v3(edge_vecs[2], v3, v4);
209 sub_v3_v3v3(edge_vecs[3], v4, v1);
210
211 normalize_v3(edge_vecs[0]);
212 normalize_v3(edge_vecs[1]);
213 normalize_v3(edge_vecs[2]);
214 normalize_v3(edge_vecs[3]);
215
216 /* A completely skinny face is 'pi' after halving. */
217 diff = (fabsf(angle_normalized_v3v3(edge_vecs[0], edge_vecs[1]) - float(M_PI_2)) +
218 fabsf(angle_normalized_v3v3(edge_vecs[1], edge_vecs[2]) - float(M_PI_2)) +
219 fabsf(angle_normalized_v3v3(edge_vecs[2], edge_vecs[3]) - float(M_PI_2)) +
220 fabsf(angle_normalized_v3v3(edge_vecs[3], edge_vecs[0]) - float(M_PI_2))) /
221 float(M_PI * 2);
222
224
225 error += diff;
226 }
227
228 /* Concavity: a face with no concavity adds an error of 0. */
229 {
230 float area_min, area_max, area_a, area_b;
231 float diff;
232
233 area_a = area_tri_v3(v1, v2, v3) + area_tri_v3(v1, v3, v4);
234 area_b = area_tri_v3(v2, v3, v4) + area_tri_v3(v4, v1, v2);
235
236 area_min = min_ff(area_a, area_b);
237 area_max = max_ff(area_a, area_b);
238
239 /* Note use of ternary operator to guard against divide by zero. */
240 diff = area_max ? (1.0f - (area_min / area_max)) : 1.0f;
241
243
244 error += diff;
245 }
246
248
249 return error;
250}
251
258static void bm_edge_to_quad_verts(const BMEdge *e, const BMVert *r_v_quad[4])
259{
261 BLI_assert(e->l->f->len == 3 && e->l->radial_next->f->len == 3);
262 r_v_quad[0] = e->l->v;
263 r_v_quad[1] = e->l->radial_next->prev->v;
264 r_v_quad[2] = e->l->next->v;
265 r_v_quad[3] = e->l->prev->v;
266}
267
268/* -------------------------------------------------------------------- */
271
273
274namespace {
275
276struct DelimitData_CD {
277 int cd_type;
278 int cd_size;
279 int cd_offset;
280 int cd_offset_end;
281};
282
283struct DelimitData {
284 uint do_seam : 1;
285 uint do_sharp : 1;
286 uint do_mat : 1;
287 uint do_angle_face : 1;
288 uint do_angle_shape : 1;
289
290 float angle_face;
291 float angle_face__cos;
292
293 float angle_shape;
294
295 DelimitData_CD cdata[4];
296 int cdata_len;
297};
298
299} // namespace
300
302static bool bm_edge_is_contiguous_loop_cd_all(const BMEdge *e, const DelimitData_CD *delimit_data)
303{
304 int cd_offset;
305 for (cd_offset = delimit_data->cd_offset; cd_offset < delimit_data->cd_offset_end;
306 cd_offset += delimit_data->cd_size)
307 {
308 if (BM_edge_is_contiguous_loop_cd(e, delimit_data->cd_type, cd_offset) == false) {
309 return false;
310 }
311 }
312
313 return true;
314}
315
318 eCustomDataType type,
319 DelimitData_CD *r_delim_cd)
320{
321 const int layer_len = CustomData_number_of_layers(ldata, type);
322 r_delim_cd->cd_type = type;
323 r_delim_cd->cd_size = CustomData_sizeof(eCustomDataType(r_delim_cd->cd_type));
324 r_delim_cd->cd_offset = CustomData_get_n_offset(ldata, type, 0);
325 r_delim_cd->cd_offset_end = r_delim_cd->cd_offset + (r_delim_cd->cd_size * layer_len);
326 return (r_delim_cd->cd_offset != -1);
327}
328
336{
337 DelimitData delimit_data = {0};
338 delimit_data.do_seam = BMO_slot_bool_get(op->slots_in, "cmp_seam");
339 delimit_data.do_sharp = BMO_slot_bool_get(op->slots_in, "cmp_sharp");
340 delimit_data.do_mat = BMO_slot_bool_get(op->slots_in, "cmp_materials");
341
342 /* Determine if angle face processing occurs and its parameters. */
343 float angle_face = BMO_slot_float_get(op->slots_in, "angle_face_threshold");
344 if (angle_face < DEG2RADF(180.0f)) {
345 delimit_data.angle_face = angle_face;
346 delimit_data.angle_face__cos = cosf(angle_face);
347 delimit_data.do_angle_face = true;
348 }
349 else {
350 delimit_data.do_angle_face = false;
351 }
352
353 /* Determine if angle shape processing occurs and its parameters. */
354 float angle_shape = BMO_slot_float_get(op->slots_in, "angle_shape_threshold");
355 if (angle_shape < DEG2RADF(180.0f)) {
356 delimit_data.angle_shape = angle_shape;
357 delimit_data.do_angle_shape = true;
358 }
359 else {
360 delimit_data.do_angle_shape = false;
361 }
362
363 if (BMO_slot_bool_get(op->slots_in, "cmp_uvs") &&
365 &bm->ldata, CD_PROP_FLOAT2, &delimit_data.cdata[delimit_data.cdata_len]))
366 {
367 delimit_data.cdata_len += 1;
368 }
369
370 delimit_data.cdata[delimit_data.cdata_len].cd_offset = -1;
371 if (BMO_slot_bool_get(op->slots_in, "cmp_vcols") &&
373 &bm->ldata, CD_PROP_BYTE_COLOR, &delimit_data.cdata[delimit_data.cdata_len]))
374 {
375 delimit_data.cdata_len += 1;
376 }
377 delimit_data.cdata[delimit_data.cdata_len].cd_offset = -1;
378 if (BMO_slot_bool_get(op->slots_in, "cmp_vcols") &&
380 &bm->ldata, CD_PROP_COLOR, &delimit_data.cdata[delimit_data.cdata_len]))
381 {
382 delimit_data.cdata_len += 1;
383 }
384
385 return delimit_data;
386}
387
395static bool bm_edge_is_delimit(const BMEdge *e, const DelimitData *delimit_data)
396{
397 BMFace *f_a = e->l->f, *f_b = e->l->radial_next->f;
398#if 0
399 const bool is_contig = BM_edge_is_contiguous(e);
400 float angle;
401#endif
402
403 if (delimit_data->do_seam && BM_elem_flag_test(e, BM_ELEM_SEAM)) {
404 return true;
405 }
406
407 if (delimit_data->do_sharp && (BM_elem_flag_test(e, BM_ELEM_SMOOTH) == 0)) {
408 return true;
409 }
410
411 if (delimit_data->do_mat && (f_a->mat_nr != f_b->mat_nr)) {
412 return true;
413 }
414
415 if (delimit_data->do_angle_face) {
416 if (dot_v3v3(f_a->no, f_b->no) < delimit_data->angle_face__cos) {
417 return true;
418 }
419 }
420
421 if (delimit_data->do_angle_shape) {
422 const BMVert *verts[4];
423 bm_edge_to_quad_verts(e, verts);
424
425 /* if we're checking the shape at all, a flipped face is out of the question */
426 if (is_quad_flip_v3(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co)) {
427 return true;
428 }
429
430 float edge_vecs[4][3];
431
432 sub_v3_v3v3(edge_vecs[0], verts[0]->co, verts[1]->co);
433 sub_v3_v3v3(edge_vecs[1], verts[1]->co, verts[2]->co);
434 sub_v3_v3v3(edge_vecs[2], verts[2]->co, verts[3]->co);
435 sub_v3_v3v3(edge_vecs[3], verts[3]->co, verts[0]->co);
436
437 normalize_v3(edge_vecs[0]);
438 normalize_v3(edge_vecs[1]);
439 normalize_v3(edge_vecs[2]);
440 normalize_v3(edge_vecs[3]);
441
442 if ((fabsf(angle_normalized_v3v3(edge_vecs[0], edge_vecs[1]) - float(M_PI_2)) >
443 delimit_data->angle_shape) ||
444 (fabsf(angle_normalized_v3v3(edge_vecs[1], edge_vecs[2]) - float(M_PI_2)) >
445 delimit_data->angle_shape) ||
446 (fabsf(angle_normalized_v3v3(edge_vecs[2], edge_vecs[3]) - float(M_PI_2)) >
447 delimit_data->angle_shape) ||
448 (fabsf(angle_normalized_v3v3(edge_vecs[3], edge_vecs[0]) - float(M_PI_2)) >
449 delimit_data->angle_shape))
450 {
451 return true;
452 }
453 }
454
455 if (delimit_data->cdata_len) {
456 int i;
457 for (i = 0; i < delimit_data->cdata_len; i++) {
458 if (!bm_edge_is_contiguous_loop_cd_all(e, &delimit_data->cdata[i])) {
459 return true;
460 }
461 }
462 }
463
464 return false;
465}
466
468
473
486
499{
500 BLI_assert(neighbor_info.items_num < ARRAY_SIZE(neighbor_info.items));
501
502 /* Don't add null pointers. Another safeguard which cannot happen. */
503 BLI_assert(e != nullptr);
504
505 /* Don't add duplicates. */
506 for (uint index = 0; index < neighbor_info.items_num; index++) {
507 if (neighbor_info.items[neighbor_info.items_num].e == e) {
508 return;
509 }
510 }
511
512 /* Add the edge and increase the count by 1. */
513 JoinEdgesNeighborItem *item = &neighbor_info.items[neighbor_info.items_num++];
514 item->e = e;
515 item->l = l;
516}
517
524static void add_neighbors(JoinEdgesNeighborInfo &neighbor_info, BMLoop *l_in_quad)
525{
526 /* If the edge is not manifold, there is no neighboring face to process. */
527 if (!BM_edge_is_manifold(l_in_quad->e)) {
528 /* No new edges added. */
529 return;
530 }
531
532 BMLoop *l_in_neighbor = l_in_quad->radial_next;
533
534 /* If the neighboring face is not a triangle, don't process it. */
535 if (l_in_neighbor->f->len != 3) {
536 /* No new edges added. */
537 return;
538 }
539
540#ifndef NDEBUG
541 const int items_num_prev = neighbor_info.items_num;
542#endif
543
544 /* Get the other two loops of the neighboring triangle. */
545 BMLoop *l_other_arr[2] = {l_in_neighbor->prev, l_in_neighbor->next};
546 for (int i = 0; i < ARRAY_SIZE(l_other_arr); i++) {
547 BMLoop *l_other = l_other_arr[i];
548
549 /* If `l_other` is manifold, and the adjacent face is also a triangle,
550 * mark it for potential improvement. */
551 if (BM_edge_is_manifold(l_other->e) && l_other->radial_next->f->len == 3) {
552 add_without_duplicates(neighbor_info, l_other->e, l_in_neighbor);
553 }
554 }
555
556 /* Added either 0, 1, or 2 edges. */
557#ifndef NDEBUG
558 BLI_assert(neighbor_info.items_num - items_num_prev < 3);
559#endif
560}
561
572static void rotate_to_plane(const JoinEdgesState &s,
573 const BMVert *quad_verts[4],
574 const BMLoop *l_shared,
575 const float plane_normal[3],
576 float r_quad_coordinates[4][3])
577{
578#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
579 if (s.debug_this_step) {
580 printf("angle");
581 }
582#else
583 UNUSED_VARS(s);
584#endif
585
586 float rotation_axis[3];
587 sub_v3_v3v3(rotation_axis, l_shared->v->co, l_shared->next->v->co);
588 normalize_v3(rotation_axis);
589
590 float quad_normal[3] = {0};
592 quad_normal, quad_verts[0]->co, quad_verts[1]->co, quad_verts[2]->co, quad_verts[3]->co);
593
594 float angle = angle_signed_on_axis_v3v3_v3(plane_normal, quad_normal, rotation_axis);
595
596#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
597 if (s.debug_this_step) {
598 printf(" %f, ", RAD2DEGF(angle));
599 }
600#endif
601
602 for (int i = 0; i < 4; i++) {
603 if (ELEM(quad_verts[i], l_shared->v, l_shared->next->v)) {
604 /* Two coordinates of the quad match the vector that defines the axis of rotation, so they
605 * don't change. */
606 copy_v3_v3(r_quad_coordinates[i], quad_verts[i]->co);
607 }
608 else {
609 /* The other two coordinates get rotated around the axis, and so they change. */
610 float local_coordinate[3];
611 sub_v3_v3v3(local_coordinate, quad_verts[i]->co, l_shared->v->co);
612 rotate_normalized_v3_v3v3fl(r_quad_coordinates[i], local_coordinate, rotation_axis, angle);
613 add_v3_v3(r_quad_coordinates[i], l_shared->v->co);
614 }
615 }
616}
617
649static float compute_alignment(const JoinEdgesState &s,
650 const float quad_a_vecs[4][3],
651 const BMVert *quad_b_verts[4],
652 const BMLoop *l_shared,
653 const float plane_normal[3])
654{
655 /* Many meshes have lots of curvature or sharp edges. Pairs of quads shouldn't be penalized
656 * *worse* because they represent a curved surface or define an edge. So we rotate quad_b around
657 * its common edge with quad_a until both are, as much as possible, in the same plane.
658 * This ensures the best possible chance to align. */
659 float quad_b_coordinates[4][3];
660 rotate_to_plane(s, quad_b_verts, l_shared, plane_normal, quad_b_coordinates);
661
662#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
663 if (s.debug_this_step) {
664 /* For visualization purposes *only*, rotate the face being considered.
665 * The const_cast here is purposeful. We want to specify `const BMVert` deliberately
666 * to show that we're not *supposed* to be moving verts around.
667 * But only for debug visualization, we do. This alters the mesh to visualize the
668 * effect of rotating the face into the plane for alignment testing. */
669 copy_v3_v3(const_cast<BMVert *>(quad_b_verts[0])->co, quad_b_coordinates[0]);
670 copy_v3_v3(const_cast<BMVert *>(quad_b_verts[1])->co, quad_b_coordinates[1]);
671 copy_v3_v3(const_cast<BMVert *>(quad_b_verts[2])->co, quad_b_coordinates[2]);
672 copy_v3_v3(const_cast<BMVert *>(quad_b_verts[3])->co, quad_b_coordinates[3]);
673 }
674#endif
675
676 /* compute the four unit vectors of the quad b edges. */
677 float quad_b_vecs[4][3];
678 sub_v3_v3v3(quad_b_vecs[0], quad_b_coordinates[0], quad_b_coordinates[1]);
679 sub_v3_v3v3(quad_b_vecs[1], quad_b_coordinates[1], quad_b_coordinates[2]);
680 sub_v3_v3v3(quad_b_vecs[2], quad_b_coordinates[2], quad_b_coordinates[3]);
681 sub_v3_v3v3(quad_b_vecs[3], quad_b_coordinates[3], quad_b_coordinates[0]);
682 normalize_v3(quad_b_vecs[0]);
683 normalize_v3(quad_b_vecs[1]);
684 normalize_v3(quad_b_vecs[2]);
685 normalize_v3(quad_b_vecs[3]);
686
687 /* Given that we're not certain of how the first loop of the quad and the first loop
688 * of the proposed merge quad relate to each other, there are four possible combinations
689 * to check, to test that the neighbor face and the merged face have good alignment.
690 *
691 * In theory, a very nuanced analysis involving l_shared, loop pointers, vertex pointers,
692 * etc, would allow determining which sets of vectors are the right matches sets to compare.
693 *
694 * Do not meddle in the affairs of algorithms, for they are subtle and quick to anger.
695 *
696 * Instead, this code does the math twice, then it just flips each component by 180 degrees to
697 * pick up the other two cases. Four extra angle tests aren't that much worse than optimal.
698 * Brute forcing the math and ending up with clear and understandable code is better. */
699
700 float error[4] = {0.0f};
701 for (int i = 0; i < ARRAY_SIZE(error); i++) {
702 const float angle_a = fabsf(angle_normalized_v3v3(quad_a_vecs[i], quad_b_vecs[i]));
703 const float angle_b = fabsf(angle_normalized_v3v3(quad_a_vecs[i], quad_b_vecs[(i + 1) % 4]));
704
705 /* Compute the case if the quads are aligned. */
706 error[0] += angle_a;
707 /* Compute the case if the quads are 90 degrees rotated. */
708 error[1] += angle_b;
709
710 /* Compute the case if the quads are 180 degrees rotated.
711 * This is `error[0]` except each error component is individually rotated 180 degrees. */
712 error[2] += M_PI - angle_a;
713
714 /* Compute the case if the quads are 270 degrees rotated.
715 * This is `error[1]` except each error component is individually rotated 180 degrees. */
716 error[3] += M_PI - angle_b;
717 }
718
719 /* Pick the best option and average the four components. */
720 const float best_error = std::min({error[0], error[1], error[2], error[3]}) / 4.0f;
721
722 ASSERT_VALID_ERROR_METRIC(best_error);
723
724 /* Based on the best error, we scale how aligned we are to the range 0...1
725 * `M_PI / 4` is used here because the worst case is a quad with all four edges
726 * at 45 degree angles. */
727 float alignment = 1.0f - (best_error / (M_PI / 4.0f));
728
729 /* if alignment is *truly* awful, then do nothing. Don't make a join worse. */
730 alignment = std::max(alignment, 0.0f);
731
732 ASSERT_VALID_ERROR_METRIC(alignment);
733
734 return alignment;
735}
736
767 BMEdge *e_merge,
768 BMLoop *l_shared,
769 float neighbor_quad_vecs[4][3],
770 const float neighbor_quad_error,
771 const float neighbor_quad_normal[3])
772{
773 ASSERT_VALID_ERROR_METRIC(neighbor_quad_error);
774
775 /* If the edge wasn't found, (delimit, non-manifold, etc) then return.
776 * Nothing to do here. */
777 BLI_assert(BM_elem_index_get(e_merge) >= 0);
779 if (node == nullptr) {
780 return;
781 }
782
783 float join_error_curr = BLI_heap_node_value(node);
784
785 ASSERT_VALID_ERROR_METRIC(join_error_curr);
786
787 /* Never make a join *worse* because of topology around it.
788 * Because we are sorted during the join phase of the algorithm, this should *only* happen when
789 * processing any pre-existing quads in the input mesh during setup. They might have high error.
790 * If they do, ignore them. */
791 if (neighbor_quad_error > join_error_curr) {
792
793#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
794 /* This should only happen during setup.
795 * Indicates an error, if it happens once we've started merging. */
796 BLI_assert(s.debug_merge_count == 0);
797#endif
798
799 return;
800 }
801
802#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
803 if (s.debug_this_step) {
804 printf("Edge improved from ");
805 }
806#endif
807
808 /* Get the four corners of the quad that would result if we merged. */
809 const BMVert *quad_verts_merge[4];
810 bm_edge_to_quad_verts(e_merge, quad_verts_merge);
811
812 /* Now compute the alignment.
813 * Regular grids of rectangles or trapezoids have high alignment
814 * Mismatched combinations of rectangles diamonds and trapezoids have low alignment. */
815 const float alignment = compute_alignment(
816 s, neighbor_quad_vecs, quad_verts_merge, l_shared, neighbor_quad_normal);
817
818 /* Compute how much the neighbor is better than the candidate.
819 * Since the neighbor quad error is smaller, Improvement is always represented as negative. */
820 const float improvement = (neighbor_quad_error - join_error_curr);
821
822 ASSERT_VALID_ERROR_METRIC(-improvement);
823
824 /* Compute the scale factor for how much of that possible improvement we should apply to this
825 * edge. This combines... topology_influence, which is an operator setting... and alignment,
826 * which is computed. Faces which are diagonal have an alignment of 0% - perfect rectangular
827 * grids have an alignment of 100% Neither topology_influence nor alignment can be negative;
828 * therefore the multiplier *never* makes error worse. once combined, 0 means no improvement, 1
829 * means improve all the way to exactly match the quality of the contributing neighbor.
830 * topology_influence is allowed to exceed 1.0, which lets it cancel out some of the alignment
831 * penalty. */
832 float multiplier = s.topo_influnce * alignment;
833
834 /* However, the combined multiplier shouldn't ever be allowed to exceed 1.0 because permitting
835 * that would cause exponential growth when alignment is very good, and when that happens, the
836 * algorithm becomes crazy.
837 *
838 * Further, if we allow a multiplier of exactly 1.0, then all eight edges around the neighbor
839 * quad would end up with a quality that is *exactly* equal to the neighbor - and each other;
840 * losing valuable information about their relative sorting.
841 * In order to preserve that, the multiplier is capped at 99%.
842 * The last 1% that is left uncorrected is enough to preserve relative ordering.
843 *
844 * This especially helps in quads that touch 3-poles and 5-poles. Since those quads naturally
845 * have diamond shapes, their initial error values tend to be higher and they sort to the end of
846 * the priority queue. Limiting improvement at 99% ensures those quads tend to retain their bad
847 * sort, meaning they end up surrounded by quads that define a good grid,
848 * then they merge last, which tends to produce better results. */
849 multiplier = std::min(multiplier, maximum_improvement);
850
851 ASSERT_VALID_ERROR_METRIC(multiplier);
852
853 /* improvement is always represented as a negative number (that will reduce error)
854 * Based on that convention, `+` is correct here. */
855 float join_error_next = join_error_curr + (improvement * multiplier);
856
857 ASSERT_VALID_ERROR_METRIC(join_error_next);
858
859#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
860 if (s.debug_this_step) {
861 printf("%f to %f with alignment of %f.\n", join_error_curr, join_error_next, alignment);
862 BMO_face_flag_enable(s.debug_bm, e_merge->l->f, FACE_OUT);
863 BMO_face_flag_enable(s.debug_bm, e_merge->l->radial_next->f, FACE_OUT);
864 }
865#endif
866
867 /* Now, update the node value in the heap, which may cause the node
868 * to be moved toward the head of the priority queue. */
869 BLI_heap_node_value_update(s.edge_queue, node, join_error_next);
870}
871
879static void reprioritize_face_neighbors(JoinEdgesState &s, BMFace *f, float f_error)
880{
881 BLI_assert(f->len == 4);
882
883 /* Identify any mergeable edges of any neighbor triangles that face us.
884 * - Some of our four edges... might not be manifold.
885 * - Some of our neighbor faces... might not be triangles.
886 * - Some of our neighbor triangles... might have other non-manifold (unmergeable) edges.
887 * - Some of our neighbor triangles' manifold edges... might have non-triangle neighbors.
888 * Therefore, there can be have up to eight mergeable edges, although there are often fewer. */
889 JoinEdgesNeighborInfo neighbor_info = {};
890
891 /* Get the four loops around the face. */
892 BMLoop *l_quad[4];
894
895 /* Add the mergeable neighbors for each of those loops. */
896 for (int i = 0; i < ARRAY_SIZE(l_quad); i++) {
897 add_neighbors(neighbor_info, l_quad[i]);
898 }
899
900 /* Return if there is nothing to do. */
901 if (neighbor_info.items_num == 0) {
902 return;
903 }
904
905 /* Compute the four unit vectors around this quad. */
906 float quad_vecs[4][3];
907 for (int i_next = 0, i = ARRAY_SIZE(l_quad) - 1; i_next < ARRAY_SIZE(l_quad); i = i_next++) {
908 sub_v3_v3v3(quad_vecs[i], l_quad[i]->v->co, l_quad[i_next]->v->co);
909 normalize_v3(quad_vecs[i]);
910 }
911
912 /* Re-prioritize each neighbor. */
913 for (int i = 0; i < neighbor_info.items_num; i++) {
914#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
915 s.debug_this_step = (s.debug_merge_limit > 0 && s.debug_merge_count == s.debug_merge_limit &&
916 i + 1 == s.debug_neighbor) ||
917 (++s.debug_neighbor_global_count == s.debug_neighbor &&
918 s.debug_merge_limit == 0);
919#endif
920 const JoinEdgesNeighborItem *item = &neighbor_info.items[i];
921 reprioritize_join(s, item->e, item->l, quad_vecs, f_error, f->no);
922 }
923}
924
932 BMEdge *e
933#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
934 ,
936#endif
937)
938{
939 /* Non-manifold edges can't be merged. */
941
942 /* Identify the loops on either side of the edge which may be joined. */
943 BMLoop *l_a = e->l;
944 BMLoop *l_b = e->l->radial_next;
945
946 /* If previous face merges have created quads, which now make this edge unmergeable,
947 * then skip it and move on. This happens frequently and that's ok.
948 * It's much easier and more efficient to just skip these edges when we encounter them,
949 * than it is to try to search the heap for them and remove them preemptively. */
950 if ((l_a->f->len != 3) || (l_b->f->len != 3)) {
951 return nullptr;
952 }
953
954#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
955 /* Stop doing merges in the middle of processing if we reached a user limit.
956 * This is allowed so a developer can check steps in the process of the algorithm. */
957 if (++s.debug_merge_count > s.debug_merge_limit && s.debug_merge_limit != -1) {
958 return nullptr;
959 }
960#endif
961
962 /* NOTE(@ideasman42): there isn't a great option here.
963 * - Join triangles shouldn't replace faces that haven't been selected (may be hidden).
964 * (with the principle of only manipulating out inputs).
965 * - The inputs could be deleted - but this is likely not what users want/expect.
966 *
967 * Seeing as there are often other combinations that can be joined,
968 * opt for rejecting the join entirely - allow other pairs to be joined instead.
969 *
970 * See #BM_faces_join note on `r_double`. The corners match #bm_edge_to_quad_verts winding. */
971 BMVert *v_quad[4] = {l_a->v, l_b->prev->v, l_a->next->v, l_a->prev->v};
972 if (BM_face_exists(v_quad, 4) != nullptr) [[unlikely]] {
973 return nullptr;
974 }
975
976 /* Join the edge and identify the face. */
977 return BM_faces_join_pair(bm, l_a, l_b, true, nullptr);
978}
979
982{
983 BMIter iter;
984 BMOIter siter;
985 BMFace *f;
986 BMEdge *e;
987
988 DelimitData delimit_data = bm_edge_delmimit_data_from_op(bm, op);
989
990 /* Initial setup of state. */
991 JoinEdgesState s = {nullptr};
992 s.topo_influnce = BMO_slot_float_get(op->slots_in, "topology_influence");
993 s.use_topo_influence = (s.topo_influnce != 0.0f);
995 s.select_tris_only = BMO_slot_bool_get(op->slots_in, "deselect_joined");
996 if (s.use_topo_influence) {
998 }
999
1000#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1001 s.debug_bm = bm;
1002 s.debug_merge_limit = BMO_slot_int_get(op->slots_in, "merge_limit") - 1;
1003 s.debug_neighbor = BMO_slot_int_get(op->slots_in, "neighbor_debug");
1004 s.debug_merge_count = 0;
1005 s.debug_neighbor_global_count = 0;
1006#endif
1007
1008 /* Go through every face in the input slot. Mark triangles for processing. */
1009 BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
1010 if (f->len == 3) {
1012
1013 /* And setup the initial selection. */
1014 if (s.select_tris_only) {
1016 }
1017 }
1018 }
1019
1020 /* Go through every edge in the mesh, mark edges that can be merged. */
1021 int i = 0;
1022 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
1023 BM_elem_index_set(e, i); /* set_inline */
1024
1025 /* If the edge is manifold, has a tagged input triangle on both sides,
1026 * and is *not* delimited, then it's a candidate to merge. */
1027 BMFace *f_a, *f_b;
1028 if (BM_edge_face_pair(e, &f_a, &f_b) && BMO_face_flag_test(bm, f_a, FACE_INPUT) &&
1029 BMO_face_flag_test(bm, f_b, FACE_INPUT) && !bm_edge_is_delimit(e, &delimit_data))
1030 {
1031 /* Compute the error that would result from a merge. */
1032 const BMVert *e_verts[4];
1033 bm_edge_to_quad_verts(e, e_verts);
1034 const float merge_error = quad_calc_error(
1035 e_verts[0]->co, e_verts[1]->co, e_verts[2]->co, e_verts[3]->co);
1036
1037 /* Record the candidate merge in both the heap, and the heap index. */
1038 HeapNode *node = BLI_heap_insert(s.edge_queue, merge_error, e);
1039 if (s.use_topo_influence) {
1040 s.edge_queue_nodes[i] = node;
1041 }
1042 }
1043 else {
1044 if (s.use_topo_influence) {
1045 s.edge_queue_nodes[i] = nullptr;
1046 }
1047 }
1048 }
1049
1050 /* Go through all the faces of the input slot, this time to find quads.
1051 * Improve the candidates around any preexisting quads in the mesh.
1052 *
1053 * NOTE: This unfortunately misses any quads which are not selected, but
1054 * which neighbor the selection. The only alternate would be to iterate the
1055 * whole mesh, which might be expensive for very large meshes with small selections. */
1056 if (s.use_topo_influence && (BLI_heap_is_empty(s.edge_queue) == false)) {
1057 BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
1058 if (f->len == 4) {
1059 BMVert *f_verts[4];
1060 BM_face_as_array_vert_quad(f, f_verts);
1061
1062 /* Flat quads with right angle corners and no concavity have lower error. */
1063 float f_error = quad_calc_error(
1064 f_verts[0]->co, f_verts[1]->co, f_verts[2]->co, f_verts[3]->co);
1065
1066 /* Apply the compensated error.
1067 * Since we're early in the process we over-prioritize any already existing quads to
1068 * allow them to have an especially strong influence on the resulting mesh.
1069 * At a topology influence of 200%, they're considered to be *almost perfect* quads
1070 * regardless of their actual error. Either way, the multiplier is never completely
1071 * allowed to reach zero. Instead, 1% of the original error is preserved...
1072 * which is enough to maintain the relative priority sorting between existing quads. */
1073 f_error *= (2.0f - (s.topo_influnce * maximum_improvement));
1074
1075 reprioritize_face_neighbors(s, f, f_error);
1076 }
1077 }
1078 }
1079
1080 /* Process all possible merges. */
1081 while (!BLI_heap_is_empty(s.edge_queue)) {
1082
1083 /* Get the best merge from the priority queue.
1084 * Remove it from the priority queue. */
1085 const float f_error = BLI_heap_top_value(s.edge_queue);
1086 BMEdge *e = reinterpret_cast<BMEdge *>(BLI_heap_pop_min(s.edge_queue));
1087
1088 /* Attempt the merge. */
1090 e
1091#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1092 ,
1093 s
1094#endif
1095 );
1096
1097#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1098 /* If stopping partway through, clear the selection entirely, and instead
1099 * highlight the faces being considered in the step the user is checking. */
1100 if (s.debug_merge_limit != -1 && s.debug_merge_count == s.debug_merge_limit) {
1101 BMEdge *f;
1102 BMIter iter;
1103 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1105 }
1106 }
1107#endif
1108
1109 if (f_new) {
1110
1111 /* Tag the face so the selection can be extended to include the new face. */
1112 if (s.select_tris_only == false) {
1114 }
1115
1116 /* Improve the neighbors on success. */
1117 if (s.use_topo_influence) {
1118 reprioritize_face_neighbors(s, f_new, f_error);
1119 }
1120 }
1121
1122#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1123 /* If we're supposed to stop partway though, do that.
1124 * This allows a developer to inspect the mesh at intermediate stages of processing. */
1125 if (s.debug_merge_limit != -1 && s.debug_merge_count >= s.debug_merge_limit) {
1126 break;
1127 }
1128#endif
1129 }
1130
1131#ifdef USE_JOIN_TRIANGLE_INTERACTIVE_TESTING
1132 /* Expect a full processing to have occurred, *only* if we didn't stop partway through. */
1133 if (!(s.debug_merge_limit != -1 && s.debug_merge_count >= s.debug_merge_limit))
1134#endif
1135 {
1136 /* Expect a full processing to have occurred. */
1138 }
1139
1140 /* Clean up. */
1141 BLI_heap_free(s.edge_queue, nullptr);
1142 if (s.use_topo_influence) {
1143 MEM_delete(s.edge_queue_nodes);
1144 }
1145
1146 /* Return the selection results. */
1148}
1149
1150} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
A min-heap / priority queue ADT.
#define DEG2RADF(_deg)
#define M_PI_2
#define RAD2DEGF(_rad)
#define M_PI
Read Blender memory allocation and freeing.
#define UNUSED_VARS(...)
#define ELEM(...)
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define BMO_face_flag_disable(bm, e, oflag)
#define BMO_face_flag_test(bm, e, oflag)
#define FACE_OUT
Definition bmo_bridge.cc:30
#define ASSERT_VALID_ERROR_METRIC(val)
#define FACE_INPUT
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
IMETHOD Vector diff(const Vector &a, const Vector &b, double dt)
Definition frames.inl:1166
#define FLT_EPSILON
BMesh Iterators.
MINLINE float min_ff(float a, float b)
static BMFace * bm_faces_join_pair_by_edge(BMesh *bm, BMEdge *e)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:271
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
int BMO_slot_int_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void rotate_normalized_v3_v3v3fl(float out[3], const float p[3], const float axis[3], float angle)
void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4])
int CustomData_number_of_layers(const CustomData *data, eCustomDataType type)
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
void bmo_join_triangles_exec(BMesh *bm, BMOperator *op)
int CustomData_get_n_offset(const CustomData *data, eCustomDataType type, int n)
static void rotate_to_plane(const JoinEdgesState &s, const BMVert *quad_verts[4], const BMLoop *l_shared, const float plane_normal[3], float r_quad_coordinates[4][3])
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
int CustomData_sizeof(eCustomDataType type)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static bool bm_edge_is_contiguous_loop_cd_all(const BMEdge *e, const DelimitData_CD *delimit_data)
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void add_neighbors(JoinEdgesNeighborInfo &neighbor_info, BMLoop *l_in_quad)
static float quad_calc_error(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
float angle_signed_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
static bool bm_edge_is_delimit(const BMEdge *e, const DelimitData *delimit_data)
static bool bm_edge_delimit_cdata(CustomData *ldata, eCustomDataType type, DelimitData_CD *r_delim_cd)
static float compute_alignment(const JoinEdgesState &s, const float quad_a_vecs[4][3], const BMVert *quad_b_verts[4], const BMLoop *l_shared, const float plane_normal[3])
static void reprioritize_face_neighbors(JoinEdgesState &s, BMFace *f, float f_error)
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 BMO_slot_buffer_from_enabled_flag(BMesh *bm, BMOperator *op, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BLI_INLINE bool BM_edge_is_contiguous(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:286
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
static void bm_edge_to_quad_verts(const BMEdge *e, const BMVert *r_v_quad[4])
static void reprioritize_join(JoinEdgesState &s, BMEdge *e_merge, BMLoop *l_shared, float neighbor_quad_vecs[4][3], const float neighbor_quad_error, const float neighbor_quad_normal[3])
BMFace * BM_face_exists(BMVert *const *varr, int len)
MINLINE float normalize_v3(float n[3])
constexpr float maximum_improvement
MINLINE void add_v3_v3(float r[3], const float a[3])
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE bool compare_v3v3(const float v1[3], const float v2[3], float limit) ATTR_WARN_UNUSED_RESULT
static void add_without_duplicates(JoinEdgesNeighborInfo &neighbor_info, BMEdge *e, BMLoop *l)
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1
Definition BLI_heap.cc:324
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float max_ff(float a, float b)
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:104
Heap * BLI_heap_new() ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:188
BMFace * BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_del, BMFace **r_double)
Faces Join Pair.
int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
static DelimitData bm_edge_delmimit_data_from_op(BMesh *bm, BMOperator *op)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
bool BM_edge_is_contiguous_loop_cd(const BMEdge *e, const int cd_loop_type, const int cd_loop_offset)
void void float BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:349
#define fabsf
#define cosf
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
struct BMLoop * radial_next