Blender  V3.3
bmo_rotate_edges.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_heap.h"
12 #include "BLI_math.h"
13 
14 #include "bmesh.h"
15 
16 #include "intern/bmesh_operators_private.h" /* own include */
17 
18 #define EDGE_OUT 1
19 #define FACE_MARK 1
20 
25  BMOperator *op,
26  const short check_flag,
27  const bool use_ccw)
28 {
29  BMOIter siter;
30  BMEdge *e;
31 
32  BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
36  if (BM_edge_rotate_check(e)) {
37  BMEdge *e_rotate = BM_edge_rotate(bm, e, use_ccw, check_flag);
38  if (e_rotate != NULL) {
39  BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
40  }
41  }
42  }
43 }
44 
50 static float bm_edge_calc_rotate_cost(const BMEdge *e)
51 {
53 }
54 
58 static float bm_edge_rotate_is_boundary(const BMEdge *e)
59 {
60  /* Number of adjacent shared faces. */
61  int count = 0;
62  BMLoop *l_radial_iter = e->l;
63  do {
64  /* Skip this edge. */
65  BMLoop *l_iter = l_radial_iter->next;
66  do {
67  BMEdge *e_iter = l_iter->e;
68  const int e_iter_index = BM_elem_index_get(e_iter);
69  if ((e_iter_index != -1)) {
70  if (count == 1) {
71  return false;
72  }
73  count += 1;
74  break;
75  }
76  } while ((l_iter = l_iter->next) != l_radial_iter);
77  } while ((l_radial_iter = l_radial_iter->radial_next) != e->l);
78  return true;
79 }
80 
86  BMesh *bm, BMOperator *op, short check_flag, const bool use_ccw, const int edges_len)
87 {
88  Heap *heap = BLI_heap_new_ex(edges_len);
89  HeapNode **eheap_table = MEM_mallocN(sizeof(*eheap_table) * edges_len, __func__);
90  int edges_len_rotate = 0;
91 
92  {
93  BMIter iter;
94  BMEdge *e;
95  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
96  BM_elem_index_set(e, -1); /* set_dirty! */
97  }
99  }
100 
101  {
102  BMOIter siter;
103  BMEdge *e;
104  uint i;
105  BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
106  BM_elem_index_set(e, BM_edge_is_manifold(e) ? i : -1); /* set_dirty! */
107  eheap_table[i] = NULL;
108  }
109  }
110 
111  /* First operate on boundary edges, this is often all that's needed,
112  * regions that have no boundaries are handles after. */
113  enum {
114  PASS_TYPE_BOUNDARY = 0,
115  PASS_TYPE_ALL = 1,
116  PASS_TYPE_DONE = 2,
117  };
118  uint pass_type = PASS_TYPE_BOUNDARY;
119 
120  while ((pass_type != PASS_TYPE_DONE) && (edges_len_rotate != edges_len)) {
122  {
123  BMOIter siter;
124  BMEdge *e;
125  uint i;
126  BMO_ITER_INDEX (e, &siter, op->slots_in, "edges", BM_EDGE, i) {
127  BLI_assert(eheap_table[i] == NULL);
128 
129  bool ok = (BM_elem_index_get(e) != -1) && BM_edge_rotate_check(e);
130 
131  if (ok) {
132  if (pass_type == PASS_TYPE_BOUNDARY) {
134  }
135  }
136 
137  if (ok) {
138  float cost = bm_edge_calc_rotate_cost(e);
139  if (pass_type == PASS_TYPE_BOUNDARY) {
140  /* Trick to ensure once started,
141  * non boundaries are handled before other boundary edges.
142  * This means the first longest boundary defines the starting point which is rotated
143  * until all its connected edges are exhausted
144  * and the next boundary is popped off the heap.
145  *
146  * Without this we may rotate from different starting points and meet in the middle
147  * with obviously uneven topology.
148  *
149  * Move from negative to positive value,
150  * inverting so large values are still handled first.
151  */
152  cost = cost != 0.0f ? -1.0f / cost : FLT_MAX;
153  }
154  eheap_table[i] = BLI_heap_insert(heap, cost, e);
155  }
156  }
157  }
158 
159  if (BLI_heap_is_empty(heap)) {
160  pass_type += 1;
161  continue;
162  }
163 
164  const int edges_len_rotate_prev = edges_len_rotate;
165  while (!BLI_heap_is_empty(heap)) {
166  BMEdge *e_best = BLI_heap_pop_min(heap);
167  eheap_table[BM_elem_index_get(e_best)] = NULL;
168 
169  /* No problem if this fails, re-evaluate if faces connected to this edge are touched. */
170  if (BM_edge_rotate_check(e_best)) {
171  BMEdge *e_rotate = BM_edge_rotate(bm, e_best, use_ccw, check_flag);
172  if (e_rotate != NULL) {
173  BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
174 
175  /* invalidate so we don't try touch this again. */
176  BM_elem_index_set(e_rotate, -1); /* set_dirty! */
177 
178  edges_len_rotate += 1;
179 
180  /* NOTE: we could validate all edges which have not been rotated
181  * (not just previously degenerate edges).
182  * However there is no real need -
183  * they can be left until they're popped off the queue. */
184 
185  /* We don't know the exact topology after rotating the edge,
186  * so loop over all faces attached to the new edge,
187  * typically this will only be two faces. */
188  BMLoop *l_radial_iter = e_rotate->l;
189  do {
190  /* Skip this edge. */
191  BMLoop *l_iter = l_radial_iter->next;
192  do {
193  BMEdge *e_iter = l_iter->e;
194  const int e_iter_index = BM_elem_index_get(e_iter);
195  if ((e_iter_index != -1) && (eheap_table[e_iter_index] == NULL)) {
196  if (BM_edge_rotate_check(e_iter)) {
197  /* Previously degenerate, now valid. */
198  float cost = bm_edge_calc_rotate_cost(e_iter);
199  eheap_table[e_iter_index] = BLI_heap_insert(heap, cost, e_iter);
200  }
201  }
202  } while ((l_iter = l_iter->next) != l_radial_iter);
203  } while ((l_radial_iter = l_radial_iter->radial_next) != e_rotate->l);
204  }
205  }
206  }
207 
208  /* If no actions were taken, move onto the next pass. */
209  if (edges_len_rotate == edges_len_rotate_prev) {
210  pass_type += 1;
211  continue;
212  }
213  }
214 
215  BLI_heap_free(heap, NULL);
216  MEM_freeN(eheap_table);
217 }
218 
220 {
221  BMOIter siter;
222  BMEdge *e;
223  const int edges_len = BMO_slot_buffer_len(op->slots_in, "edges");
224  const bool use_ccw = BMO_slot_bool_get(op->slots_in, "use_ccw");
225  const bool is_single = (edges_len == 1);
226  short check_flag = is_single ? BM_EDGEROT_CHECK_EXISTS :
228 
229  bool is_simple = true;
230  if (is_single == false) {
231  BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
232  BMFace *f_pair[2];
233  if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
234  for (uint i = 0; i < ARRAY_SIZE(f_pair); i += 1) {
235  if (BMO_face_flag_test(bm, f_pair[i], FACE_MARK)) {
236  is_simple = false;
237  break;
238  }
239  BMO_face_flag_enable(bm, f_pair[i], FACE_MARK);
240  }
241  if (is_simple == false) {
242  break;
243  }
244  }
245  }
246  }
247 
248  if (is_simple) {
249  bm_rotate_edges_simple(bm, op, check_flag, use_ccw);
250  }
251  else {
252  bm_rotate_edges_shared(bm, op, check_flag, use_ccw, edges_len);
253  }
254 
256 }
#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
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:279
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition: BLI_heap.c:301
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition: BLI_heap.c:182
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition: BLI_heap.c:245
unsigned int uint
Definition: BLI_sys_types.h:67
#define ARRAY_SIZE(arr)
Read Guarded memory(de)allocation.
@ BM_EDGE
Definition: bmesh_class.h:384
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_index_set(ele, index)
Definition: bmesh_inline.h:111
#define BM_ITER_MESH(ele, iter, bm, itype)
@ BM_EDGES_OF_MESH
ATTR_WARN_UNUSED_RESULT BMesh * bm
bool BM_edge_rotate_check(BMEdge *e)
Check if Rotate Edge is OK.
Definition: bmesh_mods.c:661
BMEdge * BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
Rotate Edge.
Definition: bmesh_mods.c:785
@ BM_EDGEROT_CHECK_EXISTS
Definition: bmesh_mods.h:248
@ BM_EDGEROT_CHECK_DEGENERATE
Definition: bmesh_mods.h:252
#define BMO_ITER_INDEX(ele, iter, slot_args, slot_name, restrict_flag, i_)
#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)
int BMO_slot_buffer_len(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
#define BMO_face_flag_test(bm, e, oflag)
bool BMO_slot_bool_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
float BM_edge_calc_length_squared(const BMEdge *e)
Definition: bmesh_query.c:533
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
Definition: bmesh_query.c:538
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
static float bm_edge_calc_rotate_cost(const BMEdge *e)
static void bm_rotate_edges_shared(BMesh *bm, BMOperator *op, short check_flag, const bool use_ccw, const int edges_len)
static void bm_rotate_edges_simple(BMesh *bm, BMOperator *op, const short check_flag, const bool use_ccw)
#define FACE_MARK
#define EDGE_OUT
void bmo_rotate_edges_exec(BMesh *bm, BMOperator *op)
static float bm_edge_rotate_is_boundary(const BMEdge *e)
int count
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
struct BMLoop * l
Definition: bmesh_class.h:128
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * radial_next
Definition: bmesh_class.h:204
struct BMLoop * next
Definition: bmesh_class.h:233
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
char elem_index_dirty
Definition: bmesh_class.h:305
Definition: BLI_heap.c:43