Blender V5.3
bmo_rotate_edges.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <cfloat>
12
13#include "MEM_guardedalloc.h"
14
15#include "BLI_heap.hh"
16
17#include "bmesh.hh"
18
19#include "intern/bmesh_operators_private.hh" /* own include */
20
21namespace blender {
22
23#define EDGE_OUT 1
24#define FACE_MARK 1
25
30 BMOperator *op,
31 const short check_flag,
32 const bool use_ccw)
33{
34 BMOIter siter;
35 BMEdge *e;
36
37 BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
38 /* This ends up being called twice, could add option to not to call check in
39 * #BM_edge_rotate to get some extra speed. */
41 BMEdge *e_rotate = BM_edge_rotate(bm, e, use_ccw, check_flag);
42 if (e_rotate != nullptr) {
44 }
45 }
46 }
47}
48
54static float bm_edge_calc_rotate_cost(const BMEdge *e)
55{
57}
58
63{
64 /* Number of adjacent shared faces. */
65 int count = 0;
66 BMLoop *l_radial_iter = e->l;
67 do {
68 /* Skip this edge. */
69 BMLoop *l_iter = l_radial_iter->next;
70 do {
71 BMEdge *e_iter = l_iter->e;
72 const int e_iter_index = BM_elem_index_get(e_iter);
73 if (e_iter_index != -1) {
74 if (count == 1) {
75 return false;
76 }
77 count += 1;
78 break;
79 }
80 } while ((l_iter = l_iter->next) != l_radial_iter);
81 } while ((l_radial_iter = l_radial_iter->radial_next) != e->l);
82 return true;
83}
84
90 BMesh *bm, BMOperator *op, short check_flag, const bool use_ccw, const int edges_len)
91{
92 Heap *heap = BLI_heap_new_ex(edges_len);
93 HeapNode **eheap_table = MEM_new_array_uninitialized<HeapNode *>(edges_len, __func__);
94
95 BMEdge **edges = reinterpret_cast<BMEdge **>(
97 int edges_len_rotate = 0;
98
99 /* Never read edges with this value in the `eheap_table` since they have been freed. */
100 HeapNode *edge_free_id = reinterpret_cast<HeapNode *>(uintptr_t(-1));
101
102 {
103 BMIter iter;
104 BMEdge *e;
105 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
106 BM_elem_index_set(e, -1); /* set_dirty! */
107 }
109 }
110
111 for (int i = 0; i < edges_len; i++) {
112 BMEdge *e = edges[i];
113 BM_elem_index_set(e, BM_edge_is_manifold(e) ? i : -1); /* set_dirty! */
114 eheap_table[i] = nullptr;
115 }
116
117 /* First operate on boundary edges, this is often all that's needed,
118 * regions that have no boundaries are handles after. */
119 enum {
120 PASS_TYPE_BOUNDARY = 0,
121 PASS_TYPE_ALL = 1,
122 PASS_TYPE_DONE = 2,
123 };
124 uint pass_type = PASS_TYPE_BOUNDARY;
125
126 while ((pass_type != PASS_TYPE_DONE) && (edges_len_rotate != edges_len)) {
128 {
129 for (int i = 0; i < edges_len; i++) {
130 if (eheap_table[i] == edge_free_id) {
131 /* `e` is freed. */
132 continue;
133 }
134 BMEdge *e = edges[i];
135 BLI_assert(eheap_table[i] == nullptr);
136
137 bool ok = (BM_elem_index_get(e) != -1) && BM_edge_rotate_check(e);
138
139 if (ok) {
140 if (pass_type == PASS_TYPE_BOUNDARY) {
142 }
143 }
144
145 if (ok) {
146 float cost = bm_edge_calc_rotate_cost(e);
147 if (pass_type == PASS_TYPE_BOUNDARY) {
148 /* Trick to ensure once started,
149 * non boundaries are handled before other boundary edges.
150 * This means the first longest boundary defines the starting point which is rotated
151 * until all its connected edges are exhausted
152 * and the next boundary is popped off the heap.
153 *
154 * Without this we may rotate from different starting points and meet in the middle
155 * with obviously uneven topology.
156 *
157 * Move from negative to positive value,
158 * inverting so large values are still handled first.
159 */
160 cost = cost != 0.0f ? -1.0f / cost : FLT_MAX;
161 }
162 eheap_table[i] = BLI_heap_insert(heap, cost, e);
163 }
164 }
165 }
166
167 if (BLI_heap_is_empty(heap)) {
168 pass_type += 1;
169 continue;
170 }
171
172 const int edges_len_rotate_prev = edges_len_rotate;
173 while (!BLI_heap_is_empty(heap)) {
174 BMEdge *e_best = static_cast<BMEdge *>(BLI_heap_pop_min(heap));
175 const int e_best_index = BM_elem_index_get(e_best);
176 eheap_table[e_best_index] = nullptr;
177
178 /* No problem if this fails, re-evaluate if faces connected to this edge are touched. */
179 if (BM_edge_rotate_check(e_best)) {
180 BMEdge *e_rotate = BM_edge_rotate(bm, e_best, use_ccw, check_flag);
181 if (e_rotate != nullptr) {
182 BMO_edge_flag_enable(bm, e_rotate, EDGE_OUT);
183
184 /* invalidate so we don't try touch this again. */
185 BM_elem_index_set(e_rotate, -1); /* set_dirty! */
186 /* If rotate succeeds, the edge has been freed. */
187 eheap_table[e_best_index] = edge_free_id;
188
189 edges_len_rotate += 1;
190
191 /* NOTE: we could validate all edges which have not been rotated
192 * (not just previously degenerate edges).
193 * However there is no real need -
194 * they can be left until they're popped off the queue. */
195
196 /* We don't know the exact topology after rotating the edge,
197 * so loop over all faces attached to the new edge,
198 * typically this will only be two faces. */
199 BMLoop *l_radial_iter = e_rotate->l;
200 do {
201 /* Skip this edge. */
202 BMLoop *l_iter = l_radial_iter->next;
203 do {
204 BMEdge *e_iter = l_iter->e;
205 const int e_iter_index = BM_elem_index_get(e_iter);
206 if ((e_iter_index != -1) && (eheap_table[e_iter_index] == nullptr)) {
207 /* Once freed, they cannot be accessed via connected geometry. */
208 BLI_assert(eheap_table[e_iter_index] != edge_free_id);
209 if (BM_edge_rotate_check(e_iter)) {
210 /* Previously degenerate, now valid. */
211 float cost = bm_edge_calc_rotate_cost(e_iter);
212 eheap_table[e_iter_index] = BLI_heap_insert(heap, cost, e_iter);
213 }
214 }
215 } while ((l_iter = l_iter->next) != l_radial_iter);
216 } while ((l_radial_iter = l_radial_iter->radial_next) != e_rotate->l);
217 }
218 }
219 }
220
221 /* If no actions were taken, move onto the next pass. */
222 if (edges_len_rotate == edges_len_rotate_prev) {
223 pass_type += 1;
224 continue;
225 }
226 }
227
228 BLI_heap_free(heap, nullptr);
229 MEM_delete(eheap_table);
230}
231
233{
234 BMOIter siter;
235 BMEdge *e;
236 const int edges_len = BMO_slot_buffer_len(op->slots_in, "edges");
237 const bool use_ccw = BMO_slot_bool_get(op->slots_in, "use_ccw");
238 const bool is_single = (edges_len == 1);
239 short check_flag = is_single ? BM_EDGEROT_CHECK_EXISTS :
241
242 bool is_simple = true;
243 if (is_single == false) {
244 BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
245 BMFace *f_pair[2];
246 if (BM_edge_face_pair(e, &f_pair[0], &f_pair[1])) {
247 for (uint i = 0; i < ARRAY_SIZE(f_pair); i += 1) {
248 if (BMO_face_flag_test(bm, f_pair[i], FACE_MARK)) {
249 is_simple = false;
250 break;
251 }
252 BMO_face_flag_enable(bm, f_pair[i], FACE_MARK);
253 }
254 if (is_simple == false) {
255 break;
256 }
257 }
258 }
259 }
260
261 if (is_simple) {
262 bm_rotate_edges_simple(bm, op, check_flag, use_ccw);
263 }
264 else {
265 bm_rotate_edges_shared(bm, op, check_flag, use_ccw, edges_len);
266 }
267
269}
270
271} // namespace blender
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_SLOT_AS_BUFFER(slot)
#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)
#define FACE_MARK
#define EDGE_OUT
Definition bmo_bridge.cc:29
#define FLT_MAX
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:271
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
int BMO_slot_buffer_len(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name)
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
@ BM_EDGEROT_CHECK_EXISTS
@ BM_EDGEROT_CHECK_DEGENERATE
static void bm_rotate_edges_shared(BMesh *bm, BMOperator *op, short check_flag, const bool use_ccw, const int edges_len)
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
static void bm_rotate_edges_simple(BMesh *bm, BMOperator *op, const short check_flag, const bool use_ccw)
BMEdge * BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
Rotate Edge.
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)
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
void bmo_rotate_edges_exec(BMesh *bm, BMOperator *op)
_W64 unsigned int uintptr_t
Definition BKE_text.h:120
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
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)
bool BM_edge_rotate_check(BMEdge *e)
Check if Rotate Edge is OK.
static float bm_edge_calc_rotate_cost(const BMEdge *e)
static bool bm_edge_rotate_is_boundary(const BMEdge *e)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
struct BMLoop * l
struct BMLoop * next
struct BMEdge * e
struct BMLoop * radial_next
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]
struct BMOpSlot slots_out[BMO_OP_MAX_SLOTS]