Blender  V3.3
polyfill_2d_beautify.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
23 #include "BLI_math.h"
24 #include "BLI_utildefines.h"
25 
26 #include "BLI_heap.h"
27 #include "BLI_memarena.h"
28 
29 #include "BLI_polyfill_2d_beautify.h" /* own include */
30 
31 #include "BLI_strict_flags.h"
32 
33 /* Used to find matching edges. */
34 struct OrderEdge {
35  uint verts[2];
37 };
38 
39 /* Half edge used for rotating in-place. */
40 struct HalfEdge {
45 };
46 
47 static int oedge_cmp(const void *a1, const void *a2)
48 {
49  const struct OrderEdge *x1 = a1, *x2 = a2;
50  if (x1->verts[0] > x2->verts[0]) {
51  return 1;
52  }
53  if (x1->verts[0] < x2->verts[0]) {
54  return -1;
55  }
56 
57  if (x1->verts[1] > x2->verts[1]) {
58  return 1;
59  }
60  if (x1->verts[1] < x2->verts[1]) {
61  return -1;
62  }
63 
64  /* Only for predictability. */
65  if (x1->e_half > x2->e_half) {
66  return 1;
67  }
68  if (x1->e_half < x2->e_half) {
69  return -1;
70  }
71  /* Should never get here, no two edges should be the same. */
72  BLI_assert(false);
73  return 0;
74 }
75 
76 BLI_INLINE bool is_boundary_edge(uint i_a, uint i_b, const uint coord_last)
77 {
78  BLI_assert(i_a < i_b);
79  return ((i_a + 1 == i_b) || UNLIKELY((i_a == 0) && (i_b == coord_last)));
80 }
82  const float v2[2],
83  const float v3[2],
84  const float v4[2],
85  const bool lock_degenerate,
86  float *r_area)
87 {
88  /* not a loop (only to be able to break out) */
89  do {
90  /* Allow very small faces to be considered non-zero. */
91  const float eps_zero_area = 1e-12f;
92  const float area_2x_234 = cross_tri_v2(v2, v3, v4);
93  const float area_2x_241 = cross_tri_v2(v2, v4, v1);
94 
95  const float area_2x_123 = cross_tri_v2(v1, v2, v3);
96  const float area_2x_134 = cross_tri_v2(v1, v3, v4);
97 
98  BLI_assert((ELEM(v1, v2, v3, v4) == false) && (ELEM(v2, v1, v3, v4) == false) &&
99  (ELEM(v3, v1, v2, v4) == false) && (ELEM(v4, v1, v2, v3) == false));
100 
101  if (r_area) {
102  *r_area = fabsf(area_2x_234) + fabsf(area_2x_241) +
103  /* Include both pairs for predictable results. */
104  fabsf(area_2x_123) + fabsf(area_2x_134) / 8.0f;
105  }
106 
107  /*
108  * Test for unusable (1-3) state.
109  * - Area sign flipping to check faces aren't going to point in opposite directions.
110  * - Area epsilon check that the one of the faces won't be zero area.
111  */
112  if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) {
113  break;
114  }
115  if ((fabsf(area_2x_123) <= eps_zero_area) || (fabsf(area_2x_134) <= eps_zero_area)) {
116  break;
117  }
118 
119  /* Test for unusable (2-4) state (same as above). */
120  if ((area_2x_234 >= 0.0f) != (area_2x_241 >= 0.0f)) {
121  if (lock_degenerate) {
122  break;
123  }
124 
125  return -FLT_MAX; /* always rotate */
126  }
127  if ((fabsf(area_2x_234) <= eps_zero_area) || (fabsf(area_2x_241) <= eps_zero_area)) {
128  return -FLT_MAX; /* always rotate */
129  }
130 
131  {
132  /* testing rule: the area divided by the perimeter,
133  * check if (1-3) beats the existing (2-4) edge rotation */
134  float area_a, area_b;
135  float prim_a, prim_b;
136  float fac_24, fac_13;
137 
138  float len_12, len_23, len_34, len_41, len_24, len_13;
139 
140  /* edges around the quad */
141  len_12 = len_v2v2(v1, v2);
142  len_23 = len_v2v2(v2, v3);
143  len_34 = len_v2v2(v3, v4);
144  len_41 = len_v2v2(v4, v1);
145  /* edges crossing the quad interior */
146  len_13 = len_v2v2(v1, v3);
147  len_24 = len_v2v2(v2, v4);
148 
149  /* NOTE: area is in fact (area * 2),
150  * but in this case its OK, since we're comparing ratios */
151 
152  /* edge (2-4), current state */
153  area_a = fabsf(area_2x_234);
154  area_b = fabsf(area_2x_241);
155  prim_a = len_23 + len_34 + len_24;
156  prim_b = len_41 + len_12 + len_24;
157  fac_24 = (area_a / prim_a) + (area_b / prim_b);
158 
159  /* edge (1-3), new state */
160  area_a = fabsf(area_2x_123);
161  area_b = fabsf(area_2x_134);
162  prim_a = len_12 + len_23 + len_13;
163  prim_b = len_34 + len_41 + len_13;
164  fac_13 = (area_a / prim_a) + (area_b / prim_b);
165 
166  /* negative number if (1-3) is an improved state */
167  return fac_24 - fac_13;
168  }
169  } while (false);
170 
171  return FLT_MAX;
172 }
173 
174 static float polyedge_rotate_beauty_calc(const float (*coords)[2],
175  const struct HalfEdge *edges,
176  const struct HalfEdge *e_a,
177  float *r_area)
178 {
179  const struct HalfEdge *e_b = &edges[e_a->e_radial];
180 
181  const struct HalfEdge *e_a_other = &edges[edges[e_a->e_next].e_next];
182  const struct HalfEdge *e_b_other = &edges[edges[e_b->e_next].e_next];
183 
184  const float *v1, *v2, *v3, *v4;
185 
186  v1 = coords[e_a_other->v];
187  v2 = coords[e_a->v];
188  v3 = coords[e_b_other->v];
189  v4 = coords[e_b->v];
190 
191  return BLI_polyfill_beautify_quad_rotate_calc_ex(v1, v2, v3, v4, false, r_area);
192 }
193 
194 static void polyedge_beauty_cost_update_single(const float (*coords)[2],
195  const struct HalfEdge *edges,
196  struct HalfEdge *e,
197  Heap *eheap,
198  HeapNode **eheap_table)
199 {
200  const uint i = e->base_index;
201  /* recalculate edge */
202  float area;
203  const float cost = polyedge_rotate_beauty_calc(coords, edges, e, &area);
204  /* We can get cases where both choices generate very small negative costs,
205  * which leads to infinite loop. Anyway, costs above that are not worth recomputing,
206  * maybe we could even optimize it to a smaller limit?
207  * Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully?
208  * See T43578, T49478.
209  *
210  * In fact a larger epsilon can still fail when the area of the face is very large,
211  * now the epsilon is scaled by the face area.
212  * See T56532. */
213  if (cost < -1e-6f * max_ff(area, 1.0f)) {
214  BLI_heap_insert_or_update(eheap, &eheap_table[i], cost, e);
215  }
216  else {
217  if (eheap_table[i]) {
218  BLI_heap_remove(eheap, eheap_table[i]);
219  eheap_table[i] = NULL;
220  }
221  }
222 }
223 
224 static void polyedge_beauty_cost_update(const float (*coords)[2],
225  struct HalfEdge *edges,
226  struct HalfEdge *e,
227  Heap *eheap,
228  HeapNode **eheap_table)
229 {
230  struct HalfEdge *e_arr[4];
231  e_arr[0] = &edges[e->e_next];
232  e_arr[1] = &edges[e_arr[0]->e_next];
233 
234  e = &edges[e->e_radial];
235  e_arr[2] = &edges[e->e_next];
236  e_arr[3] = &edges[e_arr[2]->e_next];
237 
238  for (uint i = 0; i < 4; i++) {
239  if (e_arr[i] && e_arr[i]->base_index != UINT_MAX) {
240  polyedge_beauty_cost_update_single(coords, edges, e_arr[i], eheap, eheap_table);
241  }
242  }
243 }
244 
245 static void polyedge_rotate(struct HalfEdge *edges, struct HalfEdge *e)
246 {
262  struct HalfEdge *ed[6];
263  uint ed_index[6];
264 
265  ed_index[0] = (uint)(e - edges);
266  ed[0] = &edges[ed_index[0]];
267  ed_index[1] = ed[0]->e_next;
268  ed[1] = &edges[ed_index[1]];
269  ed_index[2] = ed[1]->e_next;
270  ed[2] = &edges[ed_index[2]];
271 
272  ed_index[3] = e->e_radial;
273  ed[3] = &edges[ed_index[3]];
274  ed_index[4] = ed[3]->e_next;
275  ed[4] = &edges[ed_index[4]];
276  ed_index[5] = ed[4]->e_next;
277  ed[5] = &edges[ed_index[5]];
278 
279  ed[0]->e_next = ed_index[2];
280  ed[1]->e_next = ed_index[3];
281  ed[2]->e_next = ed_index[4];
282  ed[3]->e_next = ed_index[5];
283  ed[4]->e_next = ed_index[0];
284  ed[5]->e_next = ed_index[1];
285 
286  ed[0]->v = ed[5]->v;
287  ed[3]->v = ed[2]->v;
288 }
289 
290 void BLI_polyfill_beautify(const float (*coords)[2],
291  const uint coords_num,
292  uint (*tris)[3],
293 
294  /* structs for reuse */
295  MemArena *arena,
296  Heap *eheap)
297 {
298  const uint coord_last = coords_num - 1;
299  const uint tris_len = coords_num - 2;
300  /* internal edges only (between 2 tris) */
301  const uint edges_len = tris_len - 1;
302 
303  HeapNode **eheap_table;
304 
305  const uint half_edges_len = 3 * tris_len;
306  struct HalfEdge *half_edges = BLI_memarena_alloc(arena, sizeof(*half_edges) * half_edges_len);
307  struct OrderEdge *order_edges = BLI_memarena_alloc(arena,
308  sizeof(struct OrderEdge) * 2 * edges_len);
309  uint order_edges_len = 0;
310 
311  /* first build edges */
312  for (uint i = 0; i < tris_len; i++) {
313  for (uint j_curr = 0, j_prev = 2; j_curr < 3; j_prev = j_curr++) {
314  const uint e_index_prev = (i * 3) + j_prev;
315  const uint e_index_curr = (i * 3) + j_curr;
316 
317  half_edges[e_index_prev].v = tris[i][j_prev];
318  half_edges[e_index_prev].e_next = e_index_curr;
319  half_edges[e_index_prev].e_radial = UINT_MAX;
320  half_edges[e_index_prev].base_index = UINT_MAX;
321 
322  uint e_pair[2] = {tris[i][j_prev], tris[i][j_curr]};
323  if (e_pair[0] > e_pair[1]) {
324  SWAP(uint, e_pair[0], e_pair[1]);
325  }
326 
327  /* ensure internal edges. */
328  if (!is_boundary_edge(e_pair[0], e_pair[1], coord_last)) {
329  order_edges[order_edges_len].verts[0] = e_pair[0];
330  order_edges[order_edges_len].verts[1] = e_pair[1];
331  order_edges[order_edges_len].e_half = e_index_prev;
332  order_edges_len += 1;
333  }
334  }
335  }
336  BLI_assert(edges_len * 2 == order_edges_len);
337 
338  qsort(order_edges, order_edges_len, sizeof(struct OrderEdge), oedge_cmp);
339 
340  for (uint i = 0, base_index = 0; i < order_edges_len; base_index++) {
341  const struct OrderEdge *oe_a = &order_edges[i++];
342  const struct OrderEdge *oe_b = &order_edges[i++];
343  BLI_assert(oe_a->verts[0] == oe_b->verts[0] && oe_a->verts[1] == oe_b->verts[1]);
344  half_edges[oe_a->e_half].e_radial = oe_b->e_half;
345  half_edges[oe_b->e_half].e_radial = oe_a->e_half;
346  half_edges[oe_a->e_half].base_index = base_index;
347  half_edges[oe_b->e_half].base_index = base_index;
348  }
349  /* order_edges could be freed now. */
350 
351  /* Now perform iterative rotations. */
352 #if 0
353  eheap_table = BLI_memarena_alloc(arena, sizeof(HeapNode *) * (size_t)edges_len);
354 #else
355  /* We can re-use this since its big enough. */
356  eheap_table = (void *)order_edges;
357  order_edges = NULL;
358 #endif
359 
360  /* Build heap. */
361  {
362  struct HalfEdge *e = half_edges;
363  for (uint i = 0; i < half_edges_len; i++, e++) {
364  /* Accounts for boundary edged too (UINT_MAX). */
365  if (e->e_radial < i) {
366  const float cost = polyedge_rotate_beauty_calc(coords, half_edges, e, NULL);
367  if (cost < 0.0f) {
368  eheap_table[e->base_index] = BLI_heap_insert(eheap, cost, e);
369  }
370  else {
371  eheap_table[e->base_index] = NULL;
372  }
373  }
374  }
375  }
376 
377  while (BLI_heap_is_empty(eheap) == false) {
378  struct HalfEdge *e = BLI_heap_pop_min(eheap);
379  eheap_table[e->base_index] = NULL;
380 
381  polyedge_rotate(half_edges, e);
382 
383  /* recalculate faces connected on the heap */
384  polyedge_beauty_cost_update(coords, half_edges, e, eheap, eheap_table);
385  }
386 
387  BLI_heap_clear(eheap, NULL);
388 
389  // MEM_freeN(eheap_table); /* arena */
390 
391  /* get tris from half edge. */
392  uint tri_index = 0;
393  for (uint i = 0; i < half_edges_len; i++) {
394  struct HalfEdge *e = &half_edges[i];
395  if (e->v != UINT_MAX) {
396  uint *tri = tris[tri_index++];
397 
398  tri[0] = e->v;
399  e->v = UINT_MAX;
400 
401  e = &half_edges[e->e_next];
402  tri[1] = e->v;
403  e->v = UINT_MAX;
404 
405  e = &half_edges[e->e_next];
406  tri[2] = e->v;
407  e->v = UINT_MAX;
408  }
409  }
410 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
A min-heap / priority queue ADT.
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1
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
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition: BLI_heap.c:224
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition: BLI_heap.c:245
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
MINLINE float max_ff(float a, float b)
MINLINE float cross_tri_v2(const float v1[2], const float v2[2], const float v3[2])
MINLINE float len_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
Definition: BLI_memarena.c:116
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define SWAP(type, a, b)
#define UNLIKELY(x)
#define ELEM(...)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble x2
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define UINT_MAX
Definition: hash_md5.c:43
#define fabsf(x)
Definition: metal/compat.h:219
static void area(int d1, int d2, int e1, int e2, float weights[2])
float BLI_polyfill_beautify_quad_rotate_calc_ex(const float v1[2], const float v2[2], const float v3[2], const float v4[2], const bool lock_degenerate, float *r_area)
static float polyedge_rotate_beauty_calc(const float(*coords)[2], const struct HalfEdge *edges, const struct HalfEdge *e_a, float *r_area)
static void polyedge_rotate(struct HalfEdge *edges, struct HalfEdge *e)
static void polyedge_beauty_cost_update_single(const float(*coords)[2], const struct HalfEdge *edges, struct HalfEdge *e, Heap *eheap, HeapNode **eheap_table)
static void polyedge_beauty_cost_update(const float(*coords)[2], struct HalfEdge *edges, struct HalfEdge *e, Heap *eheap, HeapNode **eheap_table)
static int oedge_cmp(const void *a1, const void *a2)
void BLI_polyfill_beautify(const float(*coords)[2], const uint coords_num, uint(*tris)[3], MemArena *arena, Heap *eheap)
BLI_INLINE bool is_boundary_edge(uint i_a, uint i_b, const uint coord_last)
Definition: BLI_heap.c:43