Blender V5.3
polyfill_2d_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
25
26#include "BLI_utildefines.hh"
27
28#include "BLI_heap.hh"
29#include "BLI_math_geom_c.hh"
30#include "BLI_math_matrix_c.hh"
31#include "BLI_memarena.hh"
32
33#include "BLI_polyfill_2d_beautify.hh" /* own include */
34
35#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
36
37namespace blender {
38
39/* Used to find matching edges. */
44
45/* Half edge used for rotating in-place. */
52
53static int oedge_cmp(const void *a1, const void *a2)
54{
55 const OrderEdge *x1 = static_cast<const OrderEdge *>(a1);
56 const OrderEdge *x2 = static_cast<const OrderEdge *>(a2);
57 if (x1->verts[0] > x2->verts[0]) {
58 return 1;
59 }
60 if (x1->verts[0] < x2->verts[0]) {
61 return -1;
62 }
63
64 if (x1->verts[1] > x2->verts[1]) {
65 return 1;
66 }
67 if (x1->verts[1] < x2->verts[1]) {
68 return -1;
69 }
70
71 /* Only for predictability. */
72 if (x1->e_half > x2->e_half) {
73 return 1;
74 }
75 if (x1->e_half < x2->e_half) {
76 return -1;
77 }
78 /* Should never get here, no two edges should be the same. */
79 BLI_assert(false);
80 return 0;
81}
82
83BLI_INLINE bool is_boundary_edge(uint i_a, uint i_b, const uint coord_last)
84{
85 BLI_assert(i_a < i_b);
86 return ((i_a + 1 == i_b) || UNLIKELY((i_a == 0) && (i_b == coord_last)));
87}
89 const float v2[2],
90 const float v3[2],
91 const float v4[2],
92 const bool lock_degenerate,
93 float *r_area)
94{
95 /* not a loop (only to be able to break out) */
96 do {
97 /* Allow very small faces to be considered non-zero. */
98 const float eps_zero_area = 1e-12f;
99 const float area_2x_234 = cross_tri_v2(v2, v3, v4);
100 const float area_2x_241 = cross_tri_v2(v2, v4, v1);
101
102 const float area_2x_123 = cross_tri_v2(v1, v2, v3);
103 const float area_2x_134 = cross_tri_v2(v1, v3, v4);
104
105 BLI_assert((ELEM(v1, v2, v3, v4) == false) && (ELEM(v2, v1, v3, v4) == false) &&
106 (ELEM(v3, v1, v2, v4) == false) && (ELEM(v4, v1, v2, v3) == false));
107
108 if (r_area) {
109 *r_area = (fabsf(area_2x_234) + fabsf(area_2x_241) +
110 /* Include both pairs for predictable results. */
111 fabsf(area_2x_123) + fabsf(area_2x_134)) /
112 8.0f;
113 }
114
115 /*
116 * Test for unusable (1-3) state.
117 * - Area sign flipping to check faces aren't going to point in opposite directions.
118 * - Area epsilon check that the one of the faces won't be zero area.
119 */
120 if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) {
121 break;
122 }
123 if ((fabsf(area_2x_123) <= eps_zero_area) || (fabsf(area_2x_134) <= eps_zero_area)) {
124 break;
125 }
126
127 /* Test for unusable (2-4) state (same as above). */
128 if ((area_2x_234 >= 0.0f) != (area_2x_241 >= 0.0f)) {
129 if (lock_degenerate) {
130 break;
131 }
132
133 return -FLT_MAX; /* always rotate */
134 }
135 if ((fabsf(area_2x_234) <= eps_zero_area) || (fabsf(area_2x_241) <= eps_zero_area)) {
136 return -FLT_MAX; /* always rotate */
137 }
138
139 {
140 /* testing rule: the area divided by the perimeter,
141 * check if (1-3) beats the existing (2-4) edge rotation */
142 float area_a, area_b;
143 float prim_a, prim_b;
144 float fac_24, fac_13;
145
146 float len_12, len_23, len_34, len_41, len_24, len_13;
147
148 /* edges around the quad */
149 len_12 = len_v2v2(v1, v2);
150 len_23 = len_v2v2(v2, v3);
151 len_34 = len_v2v2(v3, v4);
152 len_41 = len_v2v2(v4, v1);
153 /* edges crossing the quad interior */
154 len_13 = len_v2v2(v1, v3);
155 len_24 = len_v2v2(v2, v4);
156
157 /* NOTE: area is in fact (area * 2),
158 * but in this case its OK, since we're comparing ratios */
159
160 /* edge (2-4), current state */
161 area_a = fabsf(area_2x_234);
162 area_b = fabsf(area_2x_241);
163 prim_a = len_23 + len_34 + len_24;
164 prim_b = len_41 + len_12 + len_24;
165 fac_24 = (area_a / prim_a) + (area_b / prim_b);
166
167 /* edge (1-3), new state */
168 area_a = fabsf(area_2x_123);
169 area_b = fabsf(area_2x_134);
170 prim_a = len_12 + len_23 + len_13;
171 prim_b = len_34 + len_41 + len_13;
172 fac_13 = (area_a / prim_a) + (area_b / prim_b);
173
174 /* negative number if (1-3) is an improved state */
175 return fac_24 - fac_13;
176 }
177 } while (false);
178
179 return FLT_MAX;
180}
181
183 const float v2[3],
184 const float v3[3],
185 const float v4[3],
186 const bool lock_degenerate)
187{
188 /* not a loop (only to be able to break out) */
189 do {
190 float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2];
191
192 /* first get the 2d values */
193 {
194 const float eps = 1e-5f;
195 float no_a[3], no_b[3];
196 float no[3];
197 float axis_mat[3][3];
198 float no_scale;
199 cross_tri_v3(no_a, v2, v3, v4);
200 cross_tri_v3(no_b, v2, v4, v1);
201
202 // printf("%p %p %p %p - %p %p\n", v1, v2, v3, v4, e->l->f, e->l->radial_next->f);
203 BLI_assert((ELEM(v1, v2, v3, v4) == false) && (ELEM(v2, v1, v3, v4) == false) &&
204 (ELEM(v3, v1, v2, v4) == false) && (ELEM(v4, v1, v2, v3) == false));
205
206 add_v3_v3v3(no, no_a, no_b);
207 if ((no_scale = normalize_v3(no)) == 0.0f) [[unlikely]] {
208 break;
209 }
210
211 axis_dominant_v3_to_m3(axis_mat, no);
212 mul_v2_m3v3(v1_xy, axis_mat, v1);
213 mul_v2_m3v3(v2_xy, axis_mat, v2);
214 mul_v2_m3v3(v3_xy, axis_mat, v3);
215 mul_v2_m3v3(v4_xy, axis_mat, v4);
216
232 if (!(signum_i_ex(cross_tri_v2(v2_xy, v3_xy, v4_xy) / no_scale, eps) +
233 signum_i_ex(cross_tri_v2(v2_xy, v4_xy, v1_xy) / no_scale, eps)))
234 {
235 break;
236 }
237 }
238
246 v1_xy, v2_xy, v3_xy, v4_xy, lock_degenerate, nullptr);
247 } while (false);
248
249 return FLT_MAX;
250}
251
252static float polyedge_rotate_beauty_calc(const float (*coords)[2],
253 const HalfEdge *edges,
254 const HalfEdge *e_a,
255 float *r_area)
256{
257 const HalfEdge *e_b = &edges[e_a->e_radial];
258
259 const HalfEdge *e_a_other = &edges[edges[e_a->e_next].e_next];
260 const HalfEdge *e_b_other = &edges[edges[e_b->e_next].e_next];
261
262 const float *v1, *v2, *v3, *v4;
263
264 v1 = coords[e_a_other->v];
265 v2 = coords[e_a->v];
266 v3 = coords[e_b_other->v];
267 v4 = coords[e_b->v];
268
269 return BLI_polyfill_beautify_quad_rotate_calc_ex(v1, v2, v3, v4, false, r_area);
270}
271
272static void polyedge_beauty_cost_update_single(const float (*coords)[2],
273 const HalfEdge *edges,
274 HalfEdge *e,
275 Heap *eheap,
276 HeapNode **eheap_table)
277{
278 const uint i = e->base_index;
279 /* recalculate edge */
280 float area;
281 const float cost = polyedge_rotate_beauty_calc(coords, edges, e, &area);
282 /* We can get cases where both choices generate very small negative costs,
283 * which leads to infinite loop. Anyway, costs above that are not worth recomputing,
284 * maybe we could even optimize it to a smaller limit?
285 * Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully?
286 * See #43578, #49478.
287 *
288 * In fact a larger epsilon can still fail when the area of the face is very large,
289 * now the epsilon is scaled by the face area.
290 * See #56532. */
291 if (cost < -1e-6f * max_ff(area, 1.0f)) {
292 BLI_heap_insert_or_update(eheap, &eheap_table[i], cost, e);
293 }
294 else {
295 if (eheap_table[i]) {
296 BLI_heap_remove(eheap, eheap_table[i]);
297 eheap_table[i] = nullptr;
298 }
299 }
300}
301
303 const float (*coords)[2], HalfEdge *edges, HalfEdge *e, Heap *eheap, HeapNode **eheap_table)
304{
305 HalfEdge *e_arr[4];
306 e_arr[0] = &edges[e->e_next];
307 e_arr[1] = &edges[e_arr[0]->e_next];
308
309 e = &edges[e->e_radial];
310 e_arr[2] = &edges[e->e_next];
311 e_arr[3] = &edges[e_arr[2]->e_next];
312
313 for (uint i = 0; i < 4; i++) {
314 if (e_arr[i] && e_arr[i]->base_index != UINT_MAX) {
315 polyedge_beauty_cost_update_single(coords, edges, e_arr[i], eheap, eheap_table);
316 }
317 }
318}
319
320static void polyedge_rotate(HalfEdge *edges, const HalfEdge *e)
321{
338 HalfEdge *ed[6];
339 uint ed_index[6];
340
341 ed_index[0] = uint(e - edges);
342 ed[0] = &edges[ed_index[0]];
343 ed_index[1] = ed[0]->e_next;
344 ed[1] = &edges[ed_index[1]];
345 ed_index[2] = ed[1]->e_next;
346 ed[2] = &edges[ed_index[2]];
347
348 ed_index[3] = e->e_radial;
349 ed[3] = &edges[ed_index[3]];
350 ed_index[4] = ed[3]->e_next;
351 ed[4] = &edges[ed_index[4]];
352 ed_index[5] = ed[4]->e_next;
353 ed[5] = &edges[ed_index[5]];
354
355 ed[0]->e_next = ed_index[2];
356 ed[1]->e_next = ed_index[3];
357 ed[2]->e_next = ed_index[4];
358 ed[3]->e_next = ed_index[5];
359 ed[4]->e_next = ed_index[0];
360 ed[5]->e_next = ed_index[1];
361
362 ed[0]->v = ed[5]->v;
363 ed[3]->v = ed[2]->v;
364}
365
366void BLI_polyfill_beautify(const float (*coords)[2],
367 const uint coords_num,
368 uint (*tris)[3],
369
370 /* structs for reuse */
371 MemArena *arena,
372 Heap *eheap)
373{
374 const uint coord_last = coords_num - 1;
375 const uint tris_len = coords_num - 2;
376 /* internal edges only (between 2 tris) */
377 const uint edges_len = tris_len - 1;
378
379 HeapNode **eheap_table;
380
381 const uint half_edges_len = 3 * tris_len;
382 HalfEdge *half_edges = static_cast<HalfEdge *>(
383 BLI_memarena_alloc(arena, sizeof(*half_edges) * half_edges_len));
384 OrderEdge *order_edges = static_cast<OrderEdge *>(
385 BLI_memarena_alloc(arena, sizeof(OrderEdge) * 2 * edges_len));
386 uint order_edges_len = 0;
387
388 /* first build edges */
389 for (uint i = 0; i < tris_len; i++) {
390 for (uint j_curr = 0, j_prev = 2; j_curr < 3; j_prev = j_curr++) {
391 const uint e_index_prev = (i * 3) + j_prev;
392 const uint e_index_curr = (i * 3) + j_curr;
393
394 half_edges[e_index_prev].v = tris[i][j_prev];
395 half_edges[e_index_prev].e_next = e_index_curr;
396 half_edges[e_index_prev].e_radial = UINT_MAX;
397 half_edges[e_index_prev].base_index = UINT_MAX;
398
399 uint e_pair[2] = {tris[i][j_prev], tris[i][j_curr]};
400 if (e_pair[0] > e_pair[1]) {
401 SWAP(uint, e_pair[0], e_pair[1]);
402 }
403
404 /* ensure internal edges. */
405 if (!is_boundary_edge(e_pair[0], e_pair[1], coord_last)) {
406 order_edges[order_edges_len].verts[0] = e_pair[0];
407 order_edges[order_edges_len].verts[1] = e_pair[1];
408 order_edges[order_edges_len].e_half = e_index_prev;
409 order_edges_len += 1;
410 }
411 }
412 }
413 BLI_assert(edges_len * 2 == order_edges_len);
414
415 qsort(order_edges, order_edges_len, sizeof(OrderEdge), oedge_cmp);
416
417 for (uint i = 0, base_index = 0; i < order_edges_len; base_index++) {
418 const OrderEdge *oe_a = &order_edges[i++];
419 const OrderEdge *oe_b = &order_edges[i++];
420 BLI_assert(oe_a->verts[0] == oe_b->verts[0] && oe_a->verts[1] == oe_b->verts[1]);
421 half_edges[oe_a->e_half].e_radial = oe_b->e_half;
422 half_edges[oe_b->e_half].e_radial = oe_a->e_half;
423 half_edges[oe_a->e_half].base_index = base_index;
424 half_edges[oe_b->e_half].base_index = base_index;
425 }
426 /* order_edges could be freed now. */
427
428 /* Now perform iterative rotations. */
429#if 0
430 eheap_table = BLI_memarena_alloc(arena, sizeof(HeapNode *) * size_t(edges_len));
431#else
432 /* We can re-use this since its big enough. */
433 eheap_table = reinterpret_cast<HeapNode **>(order_edges);
434 order_edges = nullptr;
435#endif
436
437 /* Build heap. */
438 {
439 HalfEdge *e = half_edges;
440 for (uint i = 0; i < half_edges_len; i++, e++) {
441 /* Accounts for boundary edged too (UINT_MAX). */
442 if (e->e_radial < i) {
443 const float cost = polyedge_rotate_beauty_calc(coords, half_edges, e, nullptr);
444 if (cost < 0.0f) {
445 eheap_table[e->base_index] = BLI_heap_insert(eheap, cost, e);
446 }
447 else {
448 eheap_table[e->base_index] = nullptr;
449 }
450 }
451 }
452 }
453
454 while (BLI_heap_is_empty(eheap) == false) {
455 HalfEdge *e = static_cast<HalfEdge *>(BLI_heap_pop_min(eheap));
456 eheap_table[e->base_index] = nullptr;
457
458 polyedge_rotate(half_edges, e);
459
460 /* recalculate faces connected on the heap */
461 polyedge_beauty_cost_update(coords, half_edges, e, eheap, eheap_table);
462 }
463
464 BLI_heap_clear(eheap, nullptr);
465
466 // MEM_delete(eheap_table); /* arena */
467
468 /* Get triangles from half edge. */
469 uint tri_index = 0;
470 for (uint i = 0; i < half_edges_len; i++) {
471 HalfEdge *e = &half_edges[i];
472 if (e->v != UINT_MAX) {
473 uint *tri = tris[tri_index++];
474
475 tri[0] = e->v;
476 e->v = UINT_MAX;
477
478 e = &half_edges[e->e_next];
479 tri[1] = e->v;
480 e->v = UINT_MAX;
481
482 e = &half_edges[e->e_next];
483 tri[2] = e->v;
484 e->v = UINT_MAX;
485 }
486 }
487}
488
489} // namespace blender
A min-heap / priority queue ADT.
#define SWAP(type, a, b)
#define BLI_INLINE
#define UNLIKELY(x)
#define ELEM(...)
#define FLT_MAX
#define UINT_MAX
Definition hash_md5.cc:46
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
static void polyedge_rotate(HalfEdge *edges, const HalfEdge *e)
unsigned int uint
Definition BKE_text.h:55
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
Definition BLI_heap.cc:309
static void polyedge_beauty_cost_update(const float(*coords)[2], HalfEdge *edges, HalfEdge *e, Heap *eheap, HeapNode **eheap_table)
float BLI_polyfill_beautify_quad_rotate_calc_ex(const float v1[2], const float v2[2], const float v3[2], const float v4[2], bool lock_degenerate, float *r_area)
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
MINLINE int signum_i_ex(float a, float eps)
void cross_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:30
MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2])
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
static float polyedge_rotate_beauty_calc(const float(*coords)[2], const HalfEdge *edges, const HalfEdge *e_a, float *r_area)
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)
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
static int oedge_cmp(const void *a1, const void *a2)
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
Definition BLI_heap.cc:261
static void polyedge_beauty_cost_update_single(const float(*coords)[2], const HalfEdge *edges, HalfEdge *e, Heap *eheap, HeapNode **eheap_table)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
MINLINE float normalize_v3(float n[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float max_ff(float a, float b)
MINLINE float len_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:215
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
BLI_INLINE bool is_boundary_edge(uint i_a, uint i_b, const uint coord_last)
const btScalar eps
Definition poly34.cpp:11
#define fabsf