Blender V5.3
bmo_connect_nonplanar.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
10
11#include "BLI_array.hh"
12#include "BLI_linklist_stack.hh"
13#include "BLI_math_geom_c.hh"
14
15#include "bmesh.hh"
16
17#include "intern/bmesh_operators_private.hh" /* own include */
18
19namespace blender {
20
21#define EDGE_OUT (1 << 0)
22#define FACE_OUT (1 << 1)
23
27static float bm_face_subset_calc_planar(BMLoop *l_first, BMLoop *l_last, const float no[3])
28{
29 float axis_mat[3][3];
30 float z_prev;
31 float delta_z = 0.0f;
32
33 /* Newell's Method */
34 BMLoop *l_iter = l_first;
35 BMLoop *l_term = l_last->next;
36
37 axis_dominant_v3_to_m3(axis_mat, no);
38
39 z_prev = dot_m3_v3_row_z(axis_mat, l_last->v->co);
40 do {
41 const float z_curr = dot_m3_v3_row_z(axis_mat, l_iter->v->co);
42 delta_z += fabsf(z_curr - z_prev);
43 z_prev = z_curr;
44 } while ((l_iter = l_iter->next) != l_term);
45
46 return delta_z;
47}
48
49static bool bm_face_split_find(BMesh *bm, BMFace *f, BMLoop *l_pair[2], float *r_angle_cos)
50{
51 BMLoop *l_iter, *l_first;
53 const uint f_len = f->len;
54 uint i_a, i_b;
55 bool found = false;
56
57 /* angle finding */
58 float err_best = FLT_MAX;
59 float angle_best_cos = -FLT_MAX;
60
61 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
62 i_a = 0;
63 do {
64 l_arr[i_a++] = l_iter;
65 } while ((l_iter = l_iter->next) != l_first);
66
67 /* now for the big search, O(N^2), however faces normally aren't so large */
68 for (i_a = 0; i_a < f_len; i_a++) {
69 BMLoop *l_a = l_arr[i_a];
70 for (i_b = i_a + 2; i_b < f_len; i_b++) {
71 BMLoop *l_b = l_arr[i_b];
72 /* check these are not touching
73 * (we could be smarter here) */
74 if (!BM_loop_is_adjacent(l_a, l_b)) {
75 /* first calculate normals */
76 float no_a[3], no_b[3];
77
78 if (BM_face_calc_normal_subset(l_a, l_b, no_a) != 0.0f &&
79 BM_face_calc_normal_subset(l_b, l_a, no_b) != 0.0f)
80 {
81 const float err_a = bm_face_subset_calc_planar(l_a, l_b, no_a);
82 const float err_b = bm_face_subset_calc_planar(l_b, l_a, no_b);
83 const float err_test = err_a + err_b;
84
85 if (err_test < err_best) {
86 /* check we're legal (we could batch this) */
87 BMLoop *l_split[2] = {l_a, l_b};
88 BM_face_splits_check_legal(bm, f, &l_split, 1);
89 if (l_split[0]) {
90 err_best = err_test;
91 l_pair[0] = l_a;
92 l_pair[1] = l_b;
93
94 angle_best_cos = dot_v3v3(no_a, no_b);
95 found = true;
96 }
97 }
98 }
99 }
100 }
101 }
102
103 *r_angle_cos = angle_best_cos;
104
105 return found;
106}
107
109 BMFace *f,
110 BMFace *r_f_pair[2],
111 const float angle_limit_cos)
112{
113 BMLoop *l_pair[2];
114 float angle_cos;
115
116 if (bm_face_split_find(bm, f, l_pair, &angle_cos) && (angle_cos < angle_limit_cos)) {
117 BMFace *f_new;
118 BMLoop *l_new;
119
120 f_new = BM_face_split(bm, f, l_pair[0], l_pair[1], &l_new, nullptr, false);
121 if (f_new) {
122 r_f_pair[0] = f;
123 r_f_pair[1] = f_new;
124
128 return true;
129 }
130 }
131
132 return false;
133}
134
136{
137 BMOIter siter;
138 BMFace *f;
139 bool changed = false;
140 BLI_LINKSTACK_DECLARE(fstack, BMFace *);
141
142 const float angle_limit_cos = cosf(BMO_slot_float_get(op->slots_in, "angle_limit"));
143
144 BLI_LINKSTACK_INIT(fstack);
145
146 BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
147 if (f->len > 3) {
148 BLI_LINKSTACK_PUSH(fstack, f);
149 }
150 }
151
152 while ((f = BLI_LINKSTACK_POP(fstack))) {
153 BMFace *f_pair[2];
154 if (bm_face_split_by_angle(bm, f, f_pair, angle_limit_cos)) {
155 int j;
156 for (j = 0; j < 2; j++) {
157 BM_face_normal_update(f_pair[j]);
158 if (f_pair[j]->len > 3) {
159 BLI_LINKSTACK_PUSH(fstack, f_pair[j]);
160 }
161 }
162 changed = true;
163 }
164 }
165
166 BLI_LINKSTACK_FREE(fstack);
167
168 if (changed) {
171 }
172}
173
174} // namespace blender
#define BM_FACE_FIRST_LOOP(p)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_ITER(ele, iter, slot_args, slot_name, restrict_flag)
#define FACE_OUT
Definition bmo_bridge.cc:30
#define EDGE_OUT
Definition bmo_bridge.cc:29
#define FLT_MAX
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
MINLINE float dot_m3_v3_row_z(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3])
BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
unsigned int uint
Definition BKE_text.h:55
float BMO_slot_float_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
static bool bm_face_split_by_angle(BMesh *bm, BMFace *f, BMFace *r_f_pair[2], const float angle_limit_cos)
void BM_face_normal_update(BMFace *f)
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)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
static bool bm_face_split_find(BMesh *bm, BMFace *f, BMLoop *l_pair[2], float *r_angle_cos)
BMFace * BM_face_split(BMesh *bm, BMFace *f, BMLoop *l_a, BMLoop *l_b, BMLoop **r_l, BMEdge *example, const bool no_double)
Face Split.
void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len)
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
static float bm_face_subset_calc_planar(BMLoop *l_first, BMLoop *l_last, const float no[3])
#define fabsf
#define cosf
struct BMLoop * next
struct BMEdge * e
struct BMVert * v
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]