86 return ((i_a + 1 == i_b) ||
UNLIKELY((i_a == 0) && (i_b == coord_last)));
92 const bool lock_degenerate,
98 const float eps_zero_area = 1e-12f;
106 (
ELEM(v3, v1,
v2, v4) ==
false) && (
ELEM(v4, v1,
v2, v3) ==
false));
109 *r_area = (
fabsf(area_2x_234) +
fabsf(area_2x_241) +
120 if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) {
123 if ((
fabsf(area_2x_123) <= eps_zero_area) || (
fabsf(area_2x_134) <= eps_zero_area)) {
128 if ((area_2x_234 >= 0.0f) != (area_2x_241 >= 0.0f)) {
129 if (lock_degenerate) {
135 if ((
fabsf(area_2x_234) <= eps_zero_area) || (
fabsf(area_2x_241) <= eps_zero_area)) {
142 float area_a, area_b;
143 float prim_a, prim_b;
144 float fac_24, fac_13;
146 float len_12, len_23, len_34, len_41, len_24, len_13;
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);
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);
175 return fac_24 - fac_13;
186 const bool lock_degenerate)
190 float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2];
194 const float eps = 1e-5f;
195 float no_a[3], no_b[3];
197 float axis_mat[3][3];
204 (
ELEM(v3, v1,
v2, v4) ==
false) && (
ELEM(v4, v1,
v2, v3) ==
false));
207 if ((no_scale =
normalize_v3(no)) == 0.0f) [[unlikely]] {
246 v1_xy, v2_xy, v3_xy, v4_xy, lock_degenerate,
nullptr);
262 const float *v1, *
v2, *v3, *v4;
264 v1 = coords[e_a_other->
v];
266 v3 = coords[e_b_other->
v];
278 const uint i =
e->base_index;
291 if (cost < -1e-6f *
max_ff(area, 1.0f)) {
295 if (eheap_table[i]) {
297 eheap_table[i] =
nullptr;
306 e_arr[0] = &edges[
e->e_next];
307 e_arr[1] = &edges[e_arr[0]->
e_next];
309 e = &edges[
e->e_radial];
310 e_arr[2] = &edges[
e->e_next];
311 e_arr[3] = &edges[e_arr[2]->
e_next];
313 for (
uint i = 0; i < 4; i++) {
314 if (e_arr[i] && e_arr[i]->base_index !=
UINT_MAX) {
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]];
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]];
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];
367 const uint coords_num,
374 const uint coord_last = coords_num - 1;
375 const uint tris_len = coords_num - 2;
377 const uint edges_len = tris_len - 1;
381 const uint half_edges_len = 3 * tris_len;
386 uint order_edges_len = 0;
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;
394 half_edges[e_index_prev].
v = tris[i][j_prev];
395 half_edges[e_index_prev].
e_next = e_index_curr;
399 uint e_pair[2] = {tris[i][j_prev], tris[i][j_curr]};
400 if (e_pair[0] > e_pair[1]) {
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;
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++];
433 eheap_table =
reinterpret_cast<HeapNode **
>(order_edges);
434 order_edges =
nullptr;
440 for (
uint i = 0; i < half_edges_len; i++,
e++) {
442 if (
e->e_radial < i) {
448 eheap_table[
e->base_index] =
nullptr;
456 eheap_table[
e->base_index] =
nullptr;
470 for (
uint i = 0; i < half_edges_len; i++) {
473 uint *tri = tris[tri_index++];
478 e = &half_edges[
e->e_next];
482 e = &half_edges[
e->e_next];
A min-heap / priority queue ADT.
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)
static void polyedge_rotate(HalfEdge *edges, const HalfEdge *e)
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
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])
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)
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)
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
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)
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)