Blender V5.3
bmesh_beautify.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
19
20#include "BLI_heap.hh"
21#include "BLI_math_geom_c.hh"
22#include "BLI_math_vector_c.hh"
24#include "BLI_set.hh"
25
26#include "MEM_guardedalloc.h"
27
28#include "bmesh.hh"
29#include "bmesh_beautify.hh" /* own include */
30
31// #define DEBUG_TIME
32
33#ifdef DEBUG_TIME
34# include "BLI_time.hh"
36#endif
37
38namespace blender {
39
40/* -------------------------------------------------------------------- */
41/* Set for edge rotation */
42
43struct EdRotState {
55
56 friend bool operator==(const EdRotState &a, const EdRotState &b) = default;
57
58 uint64_t hash() const
59 {
60 return get_default_hash(this->v_pair, this->f_pair);
61 }
62};
63
64#if 0
65/* use BLI_ghashutil_inthash_v4 direct */
66static uint erot_gsetutil_hash(const void *ptr)
67{
68 const EdRotState *e_state = (const EdRotState *)ptr;
69 return BLI_ghashutil_inthash_v4(&e_state->v_pair[0]);
70}
71#endif
72#if 0
73static int erot_gsetutil_cmp(const void *a, const void *b)
74{
75 const EdRotState *e_state_a = (const EdRotState *)a;
76 const EdRotState *e_state_b = (const EdRotState *)b;
77 if (e_state_a->v_pair[0] < e_state_b->v_pair[0]) {
78 return -1;
79 }
80 if (e_state_a->v_pair[0] > e_state_b->v_pair[0]) {
81 return 1;
82 }
83 if (e_state_a->v_pair[1] < e_state_b->v_pair[1]) {
84 return -1;
85 }
86 if (e_state_a->v_pair[1] > e_state_b->v_pair[1]) {
87 return 1;
88 }
89 if (e_state_a->f_pair[0] < e_state_b->f_pair[0]) {
90 return -1;
91 }
92 if (e_state_a->f_pair[0] > e_state_b->f_pair[0]) {
93 return 1;
94 }
95 if (e_state_a->f_pair[1] < e_state_b->f_pair[1]) {
96 return -1;
97 }
98 if (e_state_a->f_pair[1] > e_state_b->f_pair[1]) {
99 return 1;
100 }
101 return 0;
102}
103#endif
104
105/* ensure v0 is smaller */
106#define EDGE_ORD(v0, v1) \
107 if (v0 > v1) { \
108 std::swap(v0, v1); \
109 } \
110 (void)0
111
112static void erot_state_ex(const BMEdge *e, int v_index[2], int f_index[2])
113{
115 BLI_assert(BM_vert_in_edge(e, e->l->prev->v) == false);
116 BLI_assert(BM_vert_in_edge(e, e->l->radial_next->prev->v) == false);
117
118 /* verts of the edge */
119 v_index[0] = BM_elem_index_get(e->v1);
120 v_index[1] = BM_elem_index_get(e->v2);
121 EDGE_ORD(v_index[0], v_index[1]);
122
123 /* verts of each of the 2 faces attached to this edge
124 * (that are not a part of this edge) */
125 f_index[0] = BM_elem_index_get(e->l->prev->v);
126 f_index[1] = BM_elem_index_get(e->l->radial_next->prev->v);
127 EDGE_ORD(f_index[0], f_index[1]);
128}
129
130static void erot_state_current(const BMEdge *e, EdRotState *e_state)
131{
132 erot_state_ex(e, e_state->v_pair, e_state->f_pair);
133}
134
135static void erot_state_alternate(const BMEdge *e, EdRotState *e_state)
136{
137 erot_state_ex(e, e_state->f_pair, e_state->v_pair);
138}
139
140/* -------------------------------------------------------------------- */
141/* Calculate the improvement of rotating the edge */
142
143static float bm_edge_calc_rotate_beauty__angle(const float v1[3],
144 const float v2[3],
145 const float v3[3],
146 const float v4[3])
147{
148 /* not a loop (only to be able to break out) */
149 do {
150 float no_a[3], no_b[3];
151 float angle_24, angle_13;
152
153 /* edge (2-4), current state */
154 normal_tri_v3(no_a, v2, v3, v4);
155 normal_tri_v3(no_b, v2, v4, v1);
156 angle_24 = angle_normalized_v3v3(no_a, no_b);
157
158 /* edge (1-3), new state */
159 /* only check new state for degenerate outcome */
160 if ((normal_tri_v3(no_a, v1, v2, v3) == 0.0f) || (normal_tri_v3(no_b, v1, v3, v4) == 0.0f)) {
161 break;
162 }
163 angle_13 = angle_normalized_v3v3(no_a, no_b);
164
165 return angle_13 - angle_24;
166 } while (false);
167
168 return FLT_MAX;
169}
170
172 const BMVert *v2,
173 const BMVert *v3,
174 const BMVert *v4,
175 const short flag,
176 const short method)
177{
178 /* not a loop (only to be able to break out) */
179 do {
180 if (flag & VERT_RESTRICT_TAG) {
181 const BMVert *v_a = v1, *v_b = v3;
183 break;
184 }
185 }
186
187 if (v1 == v3) [[unlikely]] {
188 // printf("This should never happen, but does sometimes!\n");
189 break;
190 }
191
192 switch (method) {
193 case 0:
195 v1->co, v2->co, v3->co, v4->co, flag & EDGE_RESTRICT_DEGENERATE);
196 default:
197 return bm_edge_calc_rotate_beauty__angle(v1->co, v2->co, v3->co, v4->co);
198 }
199 } while (false);
200
201 return FLT_MAX;
202}
203
204static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const short method)
205{
206 const BMVert *v1, *v2, *v3, *v4;
207 v1 = e->l->prev->v; /* First vert co */
208 v2 = e->l->v; /* `e->v1` or `e->v2`. */
209 v3 = e->l->radial_next->prev->v; /* Second vert co */
210 v4 = e->l->next->v; /* `e->v1` or `e->v2`. */
211
212 return BM_verts_calc_rotate_beauty(v1, v2, v3, v4, flag, method);
213}
214
215/* -------------------------------------------------------------------- */
216/* Update the edge cost of rotation in the heap */
217
218BLI_INLINE bool edge_in_array(const BMEdge *e, const BMEdge **edge_array, const int edge_array_len)
219{
220 const int index = BM_elem_index_get(e);
221 return ((index >= 0) && (index < edge_array_len) && (e == edge_array[index]));
222}
223
224/* recalc an edge in the heap (surrounding geometry has changed) */
226 Heap *eheap,
227 HeapNode **eheap_table,
228 const Span<Set<EdRotState>> edge_state_arr,
229 /* only for testing the edge is in the array */
230 const BMEdge **edge_array,
231 const int edge_array_len,
232
233 const short flag,
234 const short method)
235{
236 if (edge_in_array(e, edge_array, edge_array_len)) {
237 const int i = BM_elem_index_get(e);
238 const Set<EdRotState> &e_state_set = edge_state_arr[i];
239
240 if (eheap_table[i]) {
241 BLI_heap_remove(eheap, eheap_table[i]);
242 eheap_table[i] = nullptr;
243 }
244
245 /* check if we can add it back */
247
248 /* check we're not moving back into a state we have been in before */
249 EdRotState e_state_alt;
250 erot_state_alternate(e, &e_state_alt);
251 if (e_state_set.contains(e_state_alt)) {
252 // printf(" skipping, we already have this state\n");
253 return;
254 }
255
256 {
257 /* recalculate edge */
258 const float cost = bm_edge_calc_rotate_beauty(e, flag, method);
259 if (cost < 0.0f) {
260 eheap_table[i] = BLI_heap_insert(eheap, cost, e);
261 }
262 else {
263 eheap_table[i] = nullptr;
264 }
265 }
266 }
267}
268
269/* we have rotated an edge, tag other edges and clear this one */
271 Heap *eheap,
272 HeapNode **eheap_table,
273 const Span<Set<EdRotState>> edge_state_arr,
274 const BMEdge **edge_array,
275 const int edge_array_len,
276 /* only for testing the edge is in the array */
277 const short flag,
278 const short method)
279{
280 int i;
281
282 BMEdge *e_arr[4] = {
283 e->l->next->e,
284 e->l->prev->e,
285 e->l->radial_next->next->e,
286 e->l->radial_next->prev->e,
287 };
288
289 BLI_assert(e->l->f->len == 3 && e->l->radial_next->f->len == 3);
290
292
293 for (i = 0; i < 4; i++) {
295 e_arr[i], eheap, eheap_table, edge_state_arr, edge_array, edge_array_len, flag, method);
296 }
297}
298
299/* -------------------------------------------------------------------- */
300/* Beautify Fill */
301
303 BMEdge **edge_array,
304 const int edge_array_len,
305 const short flag,
306 const short method,
307 const short oflag_edge,
308 const short oflag_face)
309{
310 Heap *eheap; /* edge heap */
311 HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */
312
313 Array<Set<EdRotState>> edge_state_arr(edge_array_len);
314 BLI_mempool *edge_state_pool = BLI_mempool_create(sizeof(EdRotState), 0, 512, BLI_MEMPOOL_NOP);
315 int i;
316
317#ifdef DEBUG_TIME
318 TIMEIT_START(beautify_fill);
319#endif
320
321 eheap = BLI_heap_new_ex(uint(edge_array_len));
322 eheap_table = MEM_new_array_uninitialized<HeapNode *>(size_t(edge_array_len), __func__);
323
324 /* build heap */
325 for (i = 0; i < edge_array_len; i++) {
326 BMEdge *e = edge_array[i];
327 const float cost = bm_edge_calc_rotate_beauty(e, flag, method);
328 if (cost < 0.0f) {
329 eheap_table[i] = BLI_heap_insert(eheap, cost, e);
330 }
331 else {
332 eheap_table[i] = nullptr;
333 }
334
335 BM_elem_index_set(e, i); /* set_dirty */
336 }
338
339 while (BLI_heap_is_empty(eheap) == false) {
340 BMEdge *e = static_cast<BMEdge *>(BLI_heap_pop_min(eheap));
341 i = BM_elem_index_get(e);
342 eheap_table[i] = nullptr;
343
345
347
348 BLI_assert(e == nullptr || BM_edge_face_count_is_equal(e, 2));
349
350 if (e) [[likely]] {
351 Set<EdRotState> &e_state_set = edge_state_arr[i];
352
353 /* add the new state into the set so we don't move into this state again
354 * NOTE: we could add the previous state too but this isn't essential
355 * for avoiding eternal loops */
356 EdRotState *e_state = static_cast<EdRotState *>(BLI_mempool_alloc(edge_state_pool));
357 erot_state_current(e, e_state);
358 BLI_assert(!e_state_set.contains(*e_state));
359 e_state_set.add(*e_state);
360
361 // printf(" %d -> %d, %d\n", i, BM_elem_index_get(e->v1), BM_elem_index_get(e->v2));
362
363 /* maintain the index array */
364 edge_array[i] = e;
366
367 /* recalculate faces connected on the heap */
369 eheap,
370 eheap_table,
371 edge_state_arr,
372 (const BMEdge **)edge_array,
373 edge_array_len,
374 flag,
375 method);
376
377 /* update flags */
378 if (oflag_edge) {
379 BMO_edge_flag_enable(bm, e, oflag_edge);
380 }
381
382 if (oflag_face) {
383 BMO_face_flag_enable(bm, e->l->f, oflag_face);
384 BMO_face_flag_enable(bm, e->l->radial_next->f, oflag_face);
385 }
386 }
387 }
388
389 BLI_heap_free(eheap, nullptr);
390 MEM_delete(eheap_table);
391
392 BLI_mempool_destroy(edge_state_pool);
393
394#ifdef DEBUG_TIME
395 TIMEIT_END(beautify_fill);
396#endif
397}
398
399} // namespace blender
#define BLI_ghashutil_inthash_v4(key)
Definition BLI_ghash.hh:590
A min-heap / priority queue ADT.
Platform independent time functions.
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
#define TIMEIT_END(var)
Read Blender memory allocation and freeing.
#define BLI_INLINE
#define EDGE_ORD(v0, v1)
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
#define BM_edge_face_count_is_equal(e, n)
bool contains(const Key &key) const
Definition BLI_set.hh:310
bool add(const Key &key)
Definition BLI_set.hh:248
#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
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
unsigned __int64 uint64_t
Definition BKE_text.h:91
Heap * BLI_heap_new_ex(unsigned int reserve_num) ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:173
static void erot_state_ex(const BMEdge *e, int v_index[2], int f_index[2])
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 void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
Definition BLI_heap.cc:309
static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, const Span< Set< EdRotState > > edge_state_arr, const BMEdge **edge_array, const int edge_array_len, const short flag, const short method)
float BM_verts_calc_rotate_beauty(const BMVert *v1, const BMVert *v2, const BMVert *v3, const BMVert *v4, const short flag, const short method)
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
BLI_INLINE bool BM_edge_is_manifold(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
@ BM_EDGEROT_CHECK_EXISTS
BLI_INLINE bool edge_in_array(const BMEdge *e, const BMEdge **edge_array, const int edge_array_len)
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
VecBase< int32_t, 2 > int2
BMEdge * BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
Rotate Edge.
static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, const Span< Set< EdRotState > > edge_state_arr, const BMEdge **edge_array, const int edge_array_len, const short flag, const short method)
float BLI_polyfill_edge_calc_rotate_beauty__area(const float v1[3], const float v2[3], const float v3[3], const float v4[3], bool lock_degenerate)
static float bm_edge_calc_rotate_beauty(const BMEdge *e, const short flag, const short method)
static void erot_state_alternate(const BMEdge *e, EdRotState *e_state)
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
static float bm_edge_calc_rotate_beauty__angle(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
@ BLI_MEMPOOL_NOP
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
@ EDGE_RESTRICT_DEGENERATE
static void erot_state_current(const BMEdge *e, EdRotState *e_state)
void BM_mesh_beautify_fill(BMesh *bm, BMEdge **edge_array, const int edge_array_len, const short flag, const short method, const short oflag_edge, const short oflag_face)
constexpr uint64_t get_default_hash(const T &v, const Args &...args)
Definition BLI_hash.hh:252
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
uint64_t hash() const
friend bool operator==(const EdRotState &a, const EdRotState &b)=default