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