Blender  V3.3
bmo_normals.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include "MEM_guardedalloc.h"
10 
11 #include "BLI_linklist_stack.h"
12 #include "BLI_math.h"
13 
14 #include "bmesh.h"
15 
16 #include "intern/bmesh_operators_private.h" /* own include */
17 
18 /********* Right-hand faces implementation ****** */
19 
20 #define FACE_FLAG (1 << 0)
21 #define FACE_FLIP (1 << 1)
22 #define FACE_TEMP (1 << 2)
23 
25 {
26  return BM_edge_is_manifold(l->e);
27 }
28 
61  BMFace **faces,
62  const int faces_len,
63  bool *r_is_flip)
64 {
65  const float eps = FLT_EPSILON;
66  float cent_area_accum = 0.0f;
67  float cent[3];
68  const float cent_fac = 1.0f / (float)faces_len;
69 
70  bool is_flip = false;
71  int f_start_index;
72  int i;
73 
75  struct {
81  float dist_sq;
86  float edge_dot;
91  float loop_dot;
92  } best, test;
93 
95 
96  zero_v3(cent);
97 
98  /* first calculate the center */
99  for (i = 0; i < faces_len; i++) {
100  float f_cent[3];
101  const float f_area = BM_face_calc_area(faces[i]);
103  madd_v3_v3fl(cent, f_cent, cent_fac * f_area);
104  cent_area_accum += f_area;
105 
108  }
109 
110  if (cent_area_accum != 0.0f) {
111  mul_v3_fl(cent, 1.0f / cent_area_accum);
112  }
113 
114  /* Distances must start above zero,
115  * or we can't do meaningful calculations based on the direction to the center */
116  best.dist_sq = eps;
117  best.edge_dot = best.loop_dot = -FLT_MAX;
118 
119  /* used in degenerate cases only */
120  f_start_index = 0;
121 
130  for (i = 0; i < faces_len; i++) {
131  BMLoop *l_iter, *l_first;
132 
133  l_iter = l_first = BM_FACE_FIRST_LOOP(faces[i]);
134  do {
135  bool is_best_dist_sq;
136  float dir[3];
137  sub_v3_v3v3(dir, l_iter->v->co, cent);
138  test.dist_sq = len_squared_v3(dir);
139  is_best_dist_sq = (test.dist_sq > best.dist_sq);
140  if (is_best_dist_sq || (test.dist_sq == best.dist_sq)) {
141  float edge_dir_pair[2][3];
142  mul_v3_fl(dir, 1.0f / sqrtf(test.dist_sq));
143 
144  sub_v3_v3v3(edge_dir_pair[0], l_iter->next->v->co, l_iter->v->co);
145  sub_v3_v3v3(edge_dir_pair[1], l_iter->prev->v->co, l_iter->v->co);
146 
147  if ((normalize_v3(edge_dir_pair[0]) > eps) && (normalize_v3(edge_dir_pair[1]) > eps)) {
148  bool is_best_edge_dot;
149  test.edge_dot = max_ff(dot_v3v3(dir, edge_dir_pair[0]), dot_v3v3(dir, edge_dir_pair[1]));
150  is_best_edge_dot = (test.edge_dot > best.edge_dot);
151  if (is_best_dist_sq || is_best_edge_dot || (test.edge_dot == best.edge_dot)) {
152  float loop_dir[3];
153  cross_v3_v3v3(loop_dir, edge_dir_pair[0], edge_dir_pair[1]);
154  if (normalize_v3(loop_dir) > eps) {
155  float loop_dir_dot;
156  /* Highly unlikely the furthest loop is also the concave part of an ngon,
157  * but it can be contrived with _very_ non-planar faces - so better check. */
158  if (UNLIKELY(dot_v3v3(loop_dir, l_iter->f->no) < 0.0f)) {
159  negate_v3(loop_dir);
160  }
161  loop_dir_dot = dot_v3v3(dir, loop_dir);
162  test.loop_dot = fabsf(loop_dir_dot);
163  if (is_best_dist_sq || is_best_edge_dot || (test.loop_dot > best.loop_dot)) {
164  best = test;
165  f_start_index = i;
166  is_flip = (loop_dir_dot < 0.0f);
167  }
168  }
169  }
170  }
171  }
172  } while ((l_iter = l_iter->next) != l_first);
173  }
174 
175  *r_is_flip = is_flip;
176  return f_start_index;
177 }
178 
189  BMFace **faces,
190  const int faces_len,
191  const short oflag)
192 {
193  int i, f_start_index;
194  const short oflag_flip = oflag | FACE_FLIP;
195  bool is_flip;
196 
197  BMFace *f;
198 
199  BLI_LINKSTACK_DECLARE(fstack, BMFace *);
200 
201  f_start_index = recalc_face_normals_find_index(bm, faces, faces_len, &is_flip);
202 
203  if (is_flip) {
204  BMO_face_flag_enable(bm, faces[f_start_index], FACE_FLIP);
205  }
206 
207  /* now that we've found our starting face, make all connected faces
208  * have the same winding. this is done recursively, using a manual
209  * stack (if we use simple function recursion, we'd end up overloading
210  * the stack on large meshes). */
211  BLI_LINKSTACK_INIT(fstack);
212 
213  BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
214  BMO_face_flag_enable(bm, faces[f_start_index], FACE_TEMP);
215 
216  while ((f = BLI_LINKSTACK_POP(fstack))) {
217  const bool flip_state = BMO_face_flag_test_bool(bm, f, FACE_FLIP);
218  BMLoop *l_iter, *l_first;
219 
220  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
221  do {
222  BMLoop *l_other = l_iter->radial_next;
223 
224  if ((l_other != l_iter) && bmo_recalc_normal_loop_filter_cb(l_iter, NULL)) {
225  if (!BMO_face_flag_test(bm, l_other->f, FACE_TEMP)) {
226  BMO_face_flag_enable(bm, l_other->f, FACE_TEMP);
227  BMO_face_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
228  BLI_LINKSTACK_PUSH(fstack, l_other->f);
229  }
230  }
231  } while ((l_iter = l_iter->next) != l_first);
232  }
233 
234  BLI_LINKSTACK_FREE(fstack);
235 
236  /* apply flipping to oflag'd faces */
237  for (i = 0; i < faces_len; i++) {
238  if (BMO_face_flag_test(bm, faces[i], oflag_flip) == oflag_flip) {
240  }
242  }
243 }
244 
255 {
256  int *groups_array = MEM_mallocN(sizeof(*groups_array) * bm->totface, __func__);
257  BMFace **faces_grp = MEM_mallocN(sizeof(*faces_grp) * bm->totface, __func__);
258 
259  int(*group_index)[2];
260  const int group_tot = BM_mesh_calc_face_groups(
261  bm, groups_array, &group_index, bmo_recalc_normal_loop_filter_cb, NULL, NULL, 0, BM_EDGE);
262  int i;
263 
265 
267 
268  for (i = 0; i < group_tot; i++) {
269  const int fg_sta = group_index[i][0];
270  const int fg_len = group_index[i][1];
271  int j;
272  bool is_calc = false;
273 
274  for (j = 0; j < fg_len; j++) {
275  faces_grp[j] = BM_face_at_index(bm, groups_array[fg_sta + j]);
276 
277  if (is_calc == false) {
278  is_calc = BMO_face_flag_test_bool(bm, faces_grp[j], FACE_FLAG);
279  }
280  }
281 
282  if (is_calc) {
283  bmo_recalc_face_normals_array(bm, faces_grp, fg_len, FACE_FLAG);
284  }
285  }
286 
287  MEM_freeN(faces_grp);
288 
289  MEM_freeN(groups_array);
290  MEM_freeN(group_index);
291 }
typedef float(TangentPoint)[2]
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE float max_ff(float a, float b)
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
MINLINE float normalize_v3(float r[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void negate_v3(float r[3])
MINLINE void zero_v3(float r[3])
#define UNUSED_VARS_NDEBUG(...)
#define UNUSED(x)
#define UNLIKELY(x)
Read Guarded memory(de)allocation.
#define BM_FACE_FIRST_LOOP(p)
Definition: bmesh_class.h:622
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_EDGE
Definition: bmesh_class.h:384
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:558
BLI_INLINE BMFace * BM_face_at_index(BMesh *bm, const int index)
Definition: bmesh_mesh.h:115
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.
#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)
ATTR_WARN_UNUSED_RESULT const BMFlagLayer const short oflag
void BM_face_normal_flip(BMesh *bm, BMFace *f)
float BM_face_calc_area(const BMFace *f)
void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[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)
Definition: bmesh_query.c:2094
bool BM_face_is_normal_valid(const BMFace *f)
Definition: bmesh_query.c:2033
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMLoop * l
#define FACE_FLAG
Definition: bmo_normals.c:20
#define FACE_TEMP
Definition: bmo_normals.c:22
static bool bmo_recalc_normal_loop_filter_cb(const BMLoop *l, void *UNUSED(user_data))
Definition: bmo_normals.c:24
static int recalc_face_normals_find_index(BMesh *bm, BMFace **faces, const int faces_len, bool *r_is_flip)
Definition: bmo_normals.c:60
static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag)
Definition: bmo_normals.c:188
void bmo_recalc_face_normals_exec(BMesh *bm, BMOperator *op)
Definition: bmo_normals.c:254
#define FACE_FLIP
Definition: bmo_normals.c:21
void * user_data
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static char faces[256]
#define fabsf(x)
Definition: metal/compat.h:219
#define sqrtf(x)
Definition: metal/compat.h:243
const btScalar eps
Definition: poly34.cpp:11
float no[3]
Definition: bmesh_class.h:271
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * radial_next
Definition: bmesh_class.h:204
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
float co[3]
Definition: bmesh_class.h:87
int totface
Definition: bmesh_class.h:297