Blender V5.3
bmo_normals.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 "MEM_guardedalloc.h"
12
13#include "BLI_linklist_stack.hh"
14#include "BLI_math_vector_c.hh"
15
16#include "bmesh.hh"
17
18#include "intern/bmesh_operators_private.hh" /* own include */
19
20namespace blender {
21
22/********* Right-hand faces implementation ****** */
23
24#define FACE_FLAG (1 << 0)
25#define FACE_FLIP (1 << 1)
26#define FACE_TEMP (1 << 2)
27
28static bool bmo_recalc_normal_loop_filter_cb(const BMLoop *l, void * /*user_data*/)
29{
30 return BM_edge_is_manifold(l->e);
31}
32
59
65 BMFace **faces,
66 const int faces_len,
67 bool *r_is_flip)
68{
69 const float eps = FLT_EPSILON;
70 float cent_area_accum = 0.0f;
71 float cent[3];
72 const float cent_fac = 1.0f / float(faces_len);
73
74 bool is_flip = false;
75 int f_start_index;
76 int i;
77
79 struct {
85 float dist_sq;
90 float edge_dot;
95 float loop_dot;
96 } best, test;
97
99
100 zero_v3(cent);
101
102 /* first calculate the center */
103 for (i = 0; i < faces_len; i++) {
104 float f_cent[3];
105 const float f_area = BM_face_calc_area(faces[i]);
106 BM_face_calc_center_median_weighted(faces[i], f_cent);
107 madd_v3_v3fl(cent, f_cent, cent_fac * f_area);
108 cent_area_accum += f_area;
109
110 BLI_assert(BMO_face_flag_test(bm, faces[i], FACE_TEMP) == 0);
112 }
113
114 if (cent_area_accum != 0.0f) {
115 mul_v3_fl(cent, 1.0f / cent_area_accum);
116 }
117
118 /* Distances must start above zero,
119 * or we can't do meaningful calculations based on the direction to the center */
120 best.dist_sq = eps;
121 best.edge_dot = best.loop_dot = -FLT_MAX;
122
123 /* used in degenerate cases only */
124 f_start_index = 0;
125
134 for (i = 0; i < faces_len; i++) {
135 BMLoop *l_iter, *l_first;
136
137 l_iter = l_first = BM_FACE_FIRST_LOOP(faces[i]);
138 do {
139 bool is_best_dist_sq;
140 float dir[3];
141 sub_v3_v3v3(dir, l_iter->v->co, cent);
142 test.dist_sq = len_squared_v3(dir);
143 is_best_dist_sq = (test.dist_sq > best.dist_sq);
144 if (is_best_dist_sq || (test.dist_sq == best.dist_sq)) {
145 float edge_dir_pair[2][3];
146 mul_v3_fl(dir, 1.0f / sqrtf(test.dist_sq));
147
148 sub_v3_v3v3(edge_dir_pair[0], l_iter->next->v->co, l_iter->v->co);
149 sub_v3_v3v3(edge_dir_pair[1], l_iter->prev->v->co, l_iter->v->co);
150
151 if ((normalize_v3(edge_dir_pair[0]) > eps) && (normalize_v3(edge_dir_pair[1]) > eps)) {
152 bool is_best_edge_dot;
153 test.edge_dot = max_ff(dot_v3v3(dir, edge_dir_pair[0]), dot_v3v3(dir, edge_dir_pair[1]));
154 is_best_edge_dot = (test.edge_dot > best.edge_dot);
155 if (is_best_dist_sq || is_best_edge_dot || (test.edge_dot == best.edge_dot)) {
156 float loop_dir[3];
157 cross_v3_v3v3(loop_dir, edge_dir_pair[0], edge_dir_pair[1]);
158 if (normalize_v3(loop_dir) > eps) {
159 float loop_dir_dot;
160 /* Highly unlikely the furthest loop is also the concave part of an ngon,
161 * but it can be contrived with _very_ non-planar faces - so better check. */
162 if (dot_v3v3(loop_dir, l_iter->f->no) < 0.0f) [[unlikely]] {
163 negate_v3(loop_dir);
164 }
165 loop_dir_dot = dot_v3v3(dir, loop_dir);
166 test.loop_dot = fabsf(loop_dir_dot);
167 if (is_best_dist_sq || is_best_edge_dot || (test.loop_dot > best.loop_dot)) {
168 best = test;
169 f_start_index = i;
170 is_flip = (loop_dir_dot < 0.0f);
171 }
172 }
173 }
174 }
175 }
176 } while ((l_iter = l_iter->next) != l_first);
177 }
178
179 *r_is_flip = is_flip;
180 return f_start_index;
181}
182
193 BMFace **faces,
194 const int faces_len,
195 const short oflag)
196{
197 int i, f_start_index;
198 const short oflag_flip = oflag | FACE_FLIP;
199 bool is_flip;
200
201 BMFace *f;
202
203 BLI_LINKSTACK_DECLARE(fstack, BMFace *);
204
205 f_start_index = recalc_face_normals_find_index(bm, faces, faces_len, &is_flip);
206
207 if (is_flip) {
208 BMO_face_flag_enable(bm, faces[f_start_index], FACE_FLIP);
209 }
210
211 /* now that we've found our starting face, make all connected faces
212 * have the same winding. this is done recursively, using a manual
213 * stack (if we use simple function recursion, we'd end up overloading
214 * the stack on large meshes). */
215 BLI_LINKSTACK_INIT(fstack);
216
217 BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
218 BMO_face_flag_enable(bm, faces[f_start_index], FACE_TEMP);
219
220 while ((f = BLI_LINKSTACK_POP(fstack))) {
221 const bool flip_state = BMO_face_flag_test_bool(bm, f, FACE_FLIP);
222 BMLoop *l_iter, *l_first;
223
224 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
225 do {
226 BMLoop *l_other = l_iter->radial_next;
227
228 if ((l_other != l_iter) && bmo_recalc_normal_loop_filter_cb(l_iter, nullptr)) {
229 if (!BMO_face_flag_test(bm, l_other->f, FACE_TEMP)) {
231 BMO_face_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
232 BLI_LINKSTACK_PUSH(fstack, l_other->f);
233 }
234 }
235 } while ((l_iter = l_iter->next) != l_first);
236 }
237
238 BLI_LINKSTACK_FREE(fstack);
239
240 /* apply flipping to oflag'd faces */
241 for (i = 0; i < faces_len; i++) {
242 if (BMO_face_flag_test(bm, faces[i], oflag_flip) == oflag_flip) {
243 BM_face_normal_flip(bm, faces[i]);
244 }
246 }
247}
248
257
259{
260 int *groups_array = MEM_new_array_uninitialized<int>(bm->totface, __func__);
261 BMFace **faces_grp = MEM_new_array_uninitialized<BMFace *>(bm->totface, __func__);
262
263 int (*group_index)[2];
264 const int group_tot = BM_mesh_calc_face_groups(bm,
265 groups_array,
266 &group_index,
268 nullptr,
269 nullptr,
270 0,
271 BM_EDGE);
272 int i;
273
275
277
278 for (i = 0; i < group_tot; i++) {
279 const int fg_sta = group_index[i][0];
280 const int fg_len = group_index[i][1];
281 int j;
282 bool is_calc = false;
283
284 for (j = 0; j < fg_len; j++) {
285 faces_grp[j] = BM_face_at_index(bm, groups_array[fg_sta + j]);
286
287 if (is_calc == false) {
288 is_calc = BMO_face_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
289 }
290 }
291
292 if (is_calc) {
293 bmo_recalc_face_normals_array(bm, faces_grp, fg_len, FACE_FLAG);
294 }
295 }
296
297 MEM_delete(faces_grp);
298
299 MEM_delete(groups_array);
300 MEM_delete(group_index);
301}
302
303} // namespace blender
Read Blender memory allocation and freeing.
#define UNUSED_VARS_NDEBUG(...)
#define BM_FACE_FIRST_LOOP(p)
#define BMO_face_flag_test_bool(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BMO_face_flag_set(bm, e, oflag, val)
#define BMO_face_flag_disable(bm, e, oflag)
#define BMO_face_flag_test(bm, e, oflag)
#define FACE_FLAG
#define FACE_TEMP
#define FACE_FLIP
#define FLT_MAX
#define FLT_EPSILON
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BM_face_normal_flip(BMesh *bm, BMFace *f)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
void BMO_slot_buffer_flag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMO_FLAG_BUFFER.
void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
float BM_face_calc_area(const BMFace *f)
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
static bool bmo_recalc_normal_loop_filter_cb(const BMLoop *l, void *)
MINLINE void negate_v3(float r[3])
MINLINE void zero_v3(float r[3])
MINLINE float normalize_v3(float n[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int(**r_group_index)[2], BMLoopFilterFunc filter_fn, BMLoopPairFilterFunc filter_pair_fn, void *user_data, const char hflag_test, const char htype_step)
MINLINE float max_ff(float a, float b)
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
BLI_INLINE BMFace * BM_face_at_index(BMesh *bm, const int index)
bool BM_face_is_normal_valid(const BMFace *f)
ATTR_WARN_UNUSED_RESULT const BMFlagLayer const short oflag
static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[3])
static int recalc_face_normals_find_index(BMesh *bm, BMFace **faces, const int faces_len, bool *r_is_flip)
const btScalar eps
Definition poly34.cpp:11
#define fabsf
#define sqrtf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct BMLoop * next
struct BMLoop * prev
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]