Blender  V3.3
bmo_connect_concave.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
17 #include "MEM_guardedalloc.h"
18 
19 #include "BLI_alloca.h"
20 #include "BLI_heap.h"
21 #include "BLI_linklist.h"
22 #include "BLI_math.h"
23 #include "BLI_memarena.h"
24 #include "BLI_polyfill_2d.h"
26 #include "BLI_utildefines.h"
27 
28 #include "bmesh.h"
29 
30 #include "intern/bmesh_operators_private.h" /* own include */
31 
32 #define EDGE_OUT (1 << 0)
33 #define FACE_OUT (1 << 1)
34 
35 static int bm_edge_length_cmp(const void *a_, const void *b_)
36 {
37  const BMEdge *e_a = *(const void **)a_;
38  const BMEdge *e_b = *(const void **)b_;
39 
40  int e_a_concave = (BM_elem_flag_test(e_a->v1, BM_ELEM_TAG) &&
42  int e_b_concave = (BM_elem_flag_test(e_b->v1, BM_ELEM_TAG) &&
44 
45  /* merge edges between concave edges last since these
46  * are most likely to remain and be the main dividers */
47  if (e_a_concave < e_b_concave) {
48  return -1;
49  }
50  if (e_a_concave > e_b_concave) {
51  return 1;
52  }
53 
54  /* otherwise shortest edges last */
55  const float e_a_len = BM_edge_calc_length_squared(e_a);
56  const float e_b_len = BM_edge_calc_length_squared(e_b);
57  if (e_a_len < e_b_len) {
58  return 1;
59  }
60  if (e_a_len > e_b_len) {
61  return -1;
62  }
63  return 0;
64 }
65 
67  BMFace *f_base,
68  const float eps,
69 
70  MemArena *pf_arena,
71  struct Heap *pf_heap)
72 {
73  const int f_base_len = f_base->len;
74  int faces_array_tot = f_base_len - 3;
75  int edges_array_tot = f_base_len - 3;
76  BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
77  BMEdge **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
78  const int quad_method = 0, ngon_method = 0; /* beauty */
79  LinkNode *faces_double = NULL;
80 
81  float normal[3];
82  BLI_assert(f_base->len > 3);
83 
84  copy_v3_v3(normal, f_base->no);
85 
87  f_base,
88  faces_array,
89  &faces_array_tot,
90  edges_array,
91  &edges_array_tot,
92  &faces_double,
93  quad_method,
94  ngon_method,
95  false,
96  pf_arena,
97  pf_heap);
98 
99  BLI_assert(edges_array_tot <= f_base_len - 3);
100 
101  if (faces_array_tot) {
102  int i;
103  for (i = 0; i < faces_array_tot; i++) {
104  BMFace *f = faces_array[i];
106  }
107  }
108  BMO_face_flag_enable(bm, f_base, FACE_OUT);
109 
110  if (edges_array_tot) {
111  int i;
112 
113  qsort(edges_array, edges_array_tot, sizeof(*edges_array), bm_edge_length_cmp);
114 
115  for (i = 0; i < edges_array_tot; i++) {
116  BMLoop *l_pair[2];
117  BMEdge *e = edges_array[i];
119 
120  if (BM_edge_is_contiguous(e) && BM_edge_loop_pair(e, &l_pair[0], &l_pair[1])) {
121  bool ok = true;
122  int j;
123  for (j = 0; j < 2; j++) {
124  BMLoop *l = l_pair[j];
125 
126  /* check that merging the edge (on this side)
127  * wouldn't result in a convex face-loop.
128  *
129  * This is the (l->next, l->prev) we would have once joined.
130  */
131  float cross[3];
132  cross_tri_v3(cross, l->v->co, l->radial_next->next->next->v->co, l->prev->v->co);
133 
134  if (dot_v3v3(cross, normal) <= eps) {
135  ok = false;
136  break;
137  }
138  }
139 
140  if (ok) {
141  BMFace *f_new, *f_pair[2] = {l_pair[0]->f, l_pair[1]->f};
142  f_new = BM_faces_join(bm, f_pair, 2, true);
143  if (f_new) {
145  }
146  }
147  }
148  }
149  }
150 
151  BLI_heap_clear(pf_heap, NULL);
152 
153  while (faces_double) {
154  LinkNode *next = faces_double->next;
155  BM_face_kill(bm, faces_double->link);
156  MEM_freeN(faces_double);
157  faces_double = next;
158  }
159 
160  return true;
161 }
162 
164 {
165  bool is_concave = false;
166  if (f->len > 3) {
167  const BMLoop *l_iter, *l_first;
168 
169  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
170  do {
171  if (BM_loop_is_convex(l_iter) == false) {
172  is_concave = true;
174  }
175  else {
177  }
178  } while ((l_iter = l_iter->next) != l_first);
179  }
180  return is_concave;
181 }
182 
184 {
185  BMOIter siter;
186  BMFace *f;
187  bool changed = false;
188 
189  MemArena *pf_arena;
190  Heap *pf_heap;
191 
192  pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
194 
195  BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
196  if (f->len > 3 && bm_face_convex_tag_verts(f)) {
197  if (bm_face_split_by_concave(bm, f, FLT_EPSILON, pf_arena, pf_heap)) {
198  changed = true;
199  }
200  }
201  }
202 
203  if (changed) {
206  }
207 
208  BLI_memarena_free(pf_arena);
209  BLI_heap_free(pf_heap, NULL);
210 }
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
A min-heap / priority queue ADT.
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:202
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:182
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:224
void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:18
MINLINE void copy_v3_v3(float r[3], const float a[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:94
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
Definition: BLI_memarena.c:64
#define BLI_POLYFILL_ARENA_SIZE
#define BLI_POLYFILL_ALLOC_NGON_RESERVE
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
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
BMFace * BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del)
Join Connected Faces.
Definition: bmesh_core.c:1123
void BM_face_kill(BMesh *bm, BMFace *f)
Definition: bmesh_core.c:828
#define BM_elem_flag_disable(ele, hflag)
Definition: bmesh_inline.h:15
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_elem_flag_enable(ele, hflag)
Definition: bmesh_inline.h:14
ATTR_WARN_UNUSED_RESULT BMesh * bm
#define BMO_edge_flag_enable(bm, e, oflag)
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_triangulate(BMesh *bm, BMFace *f, BMFace **r_faces_new, int *r_faces_new_tot, BMEdge **r_edges_new, int *r_edges_new_tot, LinkNode **r_faces_double, const int quad_method, const int ngon_method, const bool use_tag, MemArena *pf_arena, struct Heap *pf_heap)
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
Definition: bmesh_query.c:553
float BM_edge_calc_length_squared(const BMEdge *e)
Definition: bmesh_query.c:533
bool BM_loop_is_convex(const BMLoop *l)
Definition: bmesh_query.c:1180
BLI_INLINE bool BM_edge_is_contiguous(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static bool bm_face_convex_tag_verts(BMFace *f)
#define FACE_OUT
#define EDGE_OUT
void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op)
static bool bm_face_split_by_concave(BMesh *bm, BMFace *f_base, const float eps, MemArena *pf_arena, struct Heap *pf_heap)
static int bm_edge_length_cmp(const void *a_, const void *b_)
IconTextureDrawCall normal
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
static ulong * next
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
const btScalar eps
Definition: poly34.cpp:11
BMVert * v1
Definition: bmesh_class.h:122
BMVert * v2
Definition: bmesh_class.h:122
int len
Definition: bmesh_class.h:267
float no[3]
Definition: bmesh_class.h:271
struct BMVert * v
Definition: bmesh_class.h:153
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_out[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
float co[3]
Definition: bmesh_class.h:87
Definition: BLI_heap.c:43
void * link
Definition: BLI_linklist.h:24
struct LinkNode * next
Definition: BLI_linklist.h:23