Blender  V3.3
bmo_join_triangles.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
12 #include "MEM_guardedalloc.h"
13 
14 #include "DNA_meshdata_types.h"
15 
16 #include "BLI_math.h"
17 #include "BLI_sort_utils.h"
18 
19 #include "BKE_customdata.h"
20 
21 #include "bmesh.h"
22 
23 #include "intern/bmesh_operators_private.h" /* own include */
24 
25 /* assumes edges are validated before reaching this poin */
26 static float quad_calc_error(const float v1[3],
27  const float v2[3],
28  const float v3[3],
29  const float v4[3])
30 {
31  /* Gives a 'weight' to a pair of triangles that join an edge
32  * to decide how good a join they would make. */
33  /* NOTE: this is more complicated than it needs to be and should be cleaned up. */
34  float error = 0.0f;
35 
36  /* Normal difference */
37  {
38  float n1[3], n2[3];
39  float angle_a, angle_b;
40  float diff;
41 
42  normal_tri_v3(n1, v1, v2, v3);
43  normal_tri_v3(n2, v1, v3, v4);
44  angle_a = (compare_v3v3(n1, n2, FLT_EPSILON)) ? 0.0f : angle_normalized_v3v3(n1, n2);
45 
46  normal_tri_v3(n1, v2, v3, v4);
47  normal_tri_v3(n2, v4, v1, v2);
48  angle_b = (compare_v3v3(n1, n2, FLT_EPSILON)) ? 0.0f : angle_normalized_v3v3(n1, n2);
49 
50  diff = (angle_a + angle_b) / (float)(M_PI * 2);
51 
52  error += diff;
53  }
54 
55  /* Co-linearity */
56  {
57  float edge_vecs[4][3];
58  float diff;
59 
60  sub_v3_v3v3(edge_vecs[0], v1, v2);
61  sub_v3_v3v3(edge_vecs[1], v2, v3);
62  sub_v3_v3v3(edge_vecs[2], v3, v4);
63  sub_v3_v3v3(edge_vecs[3], v4, v1);
64 
65  normalize_v3(edge_vecs[0]);
66  normalize_v3(edge_vecs[1]);
67  normalize_v3(edge_vecs[2]);
68  normalize_v3(edge_vecs[3]);
69 
70  /* a completely skinny face is 'pi' after halving */
71  diff = (fabsf(angle_normalized_v3v3(edge_vecs[0], edge_vecs[1]) - (float)M_PI_2) +
72  fabsf(angle_normalized_v3v3(edge_vecs[1], edge_vecs[2]) - (float)M_PI_2) +
73  fabsf(angle_normalized_v3v3(edge_vecs[2], edge_vecs[3]) - (float)M_PI_2) +
74  fabsf(angle_normalized_v3v3(edge_vecs[3], edge_vecs[0]) - (float)M_PI_2)) /
75  (float)(M_PI * 2);
76 
77  error += diff;
78  }
79 
80  /* Concavity */
81  {
82  float area_min, area_max, area_a, area_b;
83  float diff;
84 
85  area_a = area_tri_v3(v1, v2, v3) + area_tri_v3(v1, v3, v4);
86  area_b = area_tri_v3(v2, v3, v4) + area_tri_v3(v4, v1, v2);
87 
88  area_min = min_ff(area_a, area_b);
89  area_max = max_ff(area_a, area_b);
90 
91  diff = area_max ? (1.0f - (area_min / area_max)) : 1.0f;
92 
93  error += diff;
94  }
95 
96  return error;
97 }
98 
99 static void bm_edge_to_quad_verts(const BMEdge *e, const BMVert *r_v_quad[4])
100 {
101  BLI_assert(e->l->f->len == 3 && e->l->radial_next->f->len == 3);
103  r_v_quad[0] = e->l->v;
104  r_v_quad[1] = e->l->prev->v;
105  r_v_quad[2] = e->l->next->v;
106  r_v_quad[3] = e->l->radial_next->prev->v;
107 }
108 
109 /* cache customdata delimiters */
111  int cd_type;
112  int cd_size;
115 };
116 
117 struct DelimitData {
123 
124  float angle_face;
126 
127  float angle_shape;
128 
129  struct DelimitData_CD cdata[4];
131 };
132 
134  const struct DelimitData_CD *delimit_data)
135 {
136  int cd_offset;
137  for (cd_offset = delimit_data->cd_offset; cd_offset < delimit_data->cd_offset_end;
138  cd_offset += delimit_data->cd_size) {
139  if (BM_edge_is_contiguous_loop_cd(e, delimit_data->cd_type, cd_offset) == false) {
140  return false;
141  }
142  }
143 
144  return true;
145 }
146 
149  struct DelimitData_CD *r_delim_cd)
150 {
151  const int layer_len = CustomData_number_of_layers(ldata, type);
152  r_delim_cd->cd_type = type;
153  r_delim_cd->cd_size = CustomData_sizeof(r_delim_cd->cd_type);
154  r_delim_cd->cd_offset = CustomData_get_n_offset(ldata, type, 0);
155  r_delim_cd->cd_offset_end = r_delim_cd->cd_offset + (r_delim_cd->cd_size * layer_len);
156  return (r_delim_cd->cd_offset != -1);
157 }
158 
159 static float bm_edge_is_delimit(const BMEdge *e, const struct DelimitData *delimit_data)
160 {
161  BMFace *f_a = e->l->f, *f_b = e->l->radial_next->f;
162 #if 0
163  const bool is_contig = BM_edge_is_contiguous(e);
164  float angle;
165 #endif
166 
167  if ((delimit_data->do_seam) && (BM_elem_flag_test(e, BM_ELEM_SEAM))) {
168  goto fail;
169  }
170 
171  if ((delimit_data->do_sharp) && (BM_elem_flag_test(e, BM_ELEM_SMOOTH) == 0)) {
172  goto fail;
173  }
174 
175  if ((delimit_data->do_mat) && (f_a->mat_nr != f_b->mat_nr)) {
176  goto fail;
177  }
178 
179  if (delimit_data->do_angle_face) {
180  if (dot_v3v3(f_a->no, f_b->no) < delimit_data->angle_face__cos) {
181  goto fail;
182  }
183  }
184 
185  if (delimit_data->do_angle_shape) {
186  const BMVert *verts[4];
188 
189  /* if we're checking the shape at all, a flipped face is out of the question */
190  if (is_quad_flip_v3(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co)) {
191  goto fail;
192  }
193  else {
194  float edge_vecs[4][3];
195 
196  sub_v3_v3v3(edge_vecs[0], verts[0]->co, verts[1]->co);
197  sub_v3_v3v3(edge_vecs[1], verts[1]->co, verts[2]->co);
198  sub_v3_v3v3(edge_vecs[2], verts[2]->co, verts[3]->co);
199  sub_v3_v3v3(edge_vecs[3], verts[3]->co, verts[0]->co);
200 
201  normalize_v3(edge_vecs[0]);
202  normalize_v3(edge_vecs[1]);
203  normalize_v3(edge_vecs[2]);
204  normalize_v3(edge_vecs[3]);
205 
206  if ((fabsf(angle_normalized_v3v3(edge_vecs[0], edge_vecs[1]) - (float)M_PI_2) >
207  delimit_data->angle_shape) ||
208  (fabsf(angle_normalized_v3v3(edge_vecs[1], edge_vecs[2]) - (float)M_PI_2) >
209  delimit_data->angle_shape) ||
210  (fabsf(angle_normalized_v3v3(edge_vecs[2], edge_vecs[3]) - (float)M_PI_2) >
211  delimit_data->angle_shape) ||
212  (fabsf(angle_normalized_v3v3(edge_vecs[3], edge_vecs[0]) - (float)M_PI_2) >
213  delimit_data->angle_shape)) {
214  goto fail;
215  }
216  }
217  }
218 
219  if (delimit_data->cdata_len) {
220  int i;
221  for (i = 0; i < delimit_data->cdata_len; i++) {
222  if (!bm_edge_is_contiguous_loop_cd_all(e, &delimit_data->cdata[i])) {
223  goto fail;
224  }
225  }
226  }
227 
228  return false;
229 
230 fail:
231  return true;
232 }
233 
234 #define EDGE_MARK (1 << 0)
235 
236 #define FACE_OUT (1 << 0)
237 #define FACE_INPUT (1 << 2)
238 
240 {
241  float angle_face, angle_shape;
242 
243  BMIter iter;
244  BMOIter siter;
245  BMFace *f;
246  BMEdge *e;
247  /* data: edge-to-join, sort_value: error weight */
248  struct SortPtrByFloat *jedges;
249  uint i, totedge;
250  uint totedge_tag = 0;
251 
252  struct DelimitData delimit_data = {0};
253 
254  delimit_data.do_seam = BMO_slot_bool_get(op->slots_in, "cmp_seam");
255  delimit_data.do_sharp = BMO_slot_bool_get(op->slots_in, "cmp_sharp");
256  delimit_data.do_mat = BMO_slot_bool_get(op->slots_in, "cmp_materials");
257 
258  angle_face = BMO_slot_float_get(op->slots_in, "angle_face_threshold");
259  if (angle_face < DEG2RADF(180.0f)) {
260  delimit_data.angle_face = angle_face;
261  delimit_data.angle_face__cos = cosf(angle_face);
262  delimit_data.do_angle_face = true;
263  }
264  else {
265  delimit_data.do_angle_face = false;
266  }
267 
268  angle_shape = BMO_slot_float_get(op->slots_in, "angle_shape_threshold");
269  if (angle_shape < DEG2RADF(180.0f)) {
270  delimit_data.angle_shape = angle_shape;
271  delimit_data.do_angle_shape = true;
272  }
273  else {
274  delimit_data.do_angle_shape = false;
275  }
276 
277  if (BMO_slot_bool_get(op->slots_in, "cmp_uvs") &&
278  bm_edge_delimit_cdata(&bm->ldata, CD_MLOOPUV, &delimit_data.cdata[delimit_data.cdata_len])) {
279  delimit_data.cdata_len += 1;
280  }
281 
282  delimit_data.cdata[delimit_data.cdata_len].cd_offset = -1;
283  if (BMO_slot_bool_get(op->slots_in, "cmp_vcols") &&
285  &bm->ldata, CD_PROP_BYTE_COLOR, &delimit_data.cdata[delimit_data.cdata_len])) {
286  delimit_data.cdata_len += 1;
287  }
288 
289  /* flag all edges of all input face */
290  BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
291  if (f->len == 3) {
293  }
294  }
295 
296  /* flag edges surrounded by 2 flagged triangles */
297  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
298  BMFace *f_a, *f_b;
299  if (BM_edge_face_pair(e, &f_a, &f_b) &&
301  if (!bm_edge_is_delimit(e, &delimit_data)) {
303  totedge_tag++;
304  }
305  }
306  }
307 
308  if (totedge_tag == 0) {
309  return;
310  }
311 
312  /* over alloc, some of the edges will be delimited */
313  jedges = MEM_mallocN(sizeof(*jedges) * totedge_tag, __func__);
314 
315  i = 0;
316  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
317  const BMVert *verts[4];
318  float error;
319 
320  if (!BMO_edge_flag_test(bm, e, EDGE_MARK)) {
321  continue;
322  }
323 
325 
326  error = quad_calc_error(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co);
327 
328  jedges[i].data = e;
329  jedges[i].sort_value = error;
330  i++;
331  }
332 
333  totedge = i;
334  qsort(jedges, totedge, sizeof(*jedges), BLI_sortutil_cmp_float);
335 
336  for (i = 0; i < totedge; i++) {
337  BMLoop *l_a, *l_b;
338 
339  e = jedges[i].data;
340  l_a = e->l;
341  l_b = e->l->radial_next;
342 
343  /* check if another edge already claimed this face */
344  if ((l_a->f->len == 3) && (l_b->f->len == 3)) {
345  BMFace *f_new;
346  f_new = BM_faces_join_pair(bm, l_a, l_b, true);
347  if (f_new) {
349  }
350  }
351  }
352 
353  MEM_freeN(jedges);
354 
356 }
CustomData interface, see also DNA_customdata_types.h.
int CustomData_number_of_layers(const struct CustomData *data, int type)
int CustomData_sizeof(int type)
Definition: customdata.cc:4268
int CustomData_get_n_offset(const struct CustomData *data, int type, int n)
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE float max_ff(float a, float b)
MINLINE float min_ff(float a, float b)
#define M_PI_2
Definition: BLI_math_base.h:23
#define M_PI
Definition: BLI_math_base.h:20
int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_geom.c:5845
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:92
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:33
#define DEG2RADF(_deg)
MINLINE bool compare_v3v3(const float a[3], const float b[3], float limit) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:445
int BLI_sortutil_cmp_float(const void *a_, const void *b_)
Definition: sort_utils.c:24
unsigned int uint
Definition: BLI_sys_types.h:67
eCustomDataType
@ CD_PROP_BYTE_COLOR
@ CD_MLOOPUV
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_ELEM_SEAM
Definition: bmesh_class.h:473
@ BM_ELEM_SMOOTH
Definition: bmesh_class.h:477
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_ITER_MESH(ele, iter, bm, itype)
@ BM_EDGES_OF_MESH
ATTR_WARN_UNUSED_RESULT BMesh * bm
BMFace * BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_del)
Faces Join Pair.
Definition: bmesh_mods.c:166
#define BMO_edge_flag_test(bm, e, oflag)
#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)
#define BMO_face_flag_test(bm, e, oflag)
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
bool BM_edge_is_contiguous_loop_cd(const BMEdge *e, const int cd_loop_type, const int cd_loop_offset)
Definition: bmesh_query.c:875
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
Definition: bmesh_query.c:538
BLI_INLINE bool BM_edge_is_contiguous(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
#define FACE_OUT
void bmo_join_triangles_exec(BMesh *bm, BMOperator *op)
static void bm_edge_to_quad_verts(const BMEdge *e, const BMVert *r_v_quad[4])
static bool bm_edge_delimit_cdata(CustomData *ldata, eCustomDataType type, struct DelimitData_CD *r_delim_cd)
static bool bm_edge_is_contiguous_loop_cd_all(const BMEdge *e, const struct DelimitData_CD *delimit_data)
#define EDGE_MARK
#define FACE_INPUT
static float quad_calc_error(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
static float bm_edge_is_delimit(const BMEdge *e, const struct DelimitData *delimit_data)
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition: btVector3.h:356
#define cosf(x)
Definition: cuda/compat.h:101
static float verts[][3]
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static void error(const char *str)
Definition: meshlaplacian.c:51
#define fabsf(x)
Definition: metal/compat.h:219
IMETHOD Vector diff(const Vector &a, const Vector &b, double dt=1)
short mat_nr
Definition: bmesh_class.h:281
int len
Definition: bmesh_class.h:267
float no[3]
Definition: bmesh_class.h:271
struct BMFace * f
Definition: bmesh_class.h:171
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
CustomData ldata
Definition: bmesh_class.h:337
struct DelimitData_CD cdata[4]