47 static int oedge_cmp(
const void *a1,
const void *a2)
50 if (x1->
verts[0] >
x2->verts[0]) {
53 if (x1->
verts[0] <
x2->verts[0]) {
57 if (x1->
verts[1] >
x2->verts[1]) {
60 if (x1->
verts[1] <
x2->verts[1]) {
79 return ((i_a + 1 == i_b) ||
UNLIKELY((i_a == 0) && (i_b == coord_last)));
85 const bool lock_degenerate,
91 const float eps_zero_area = 1e-12f;
102 *r_area =
fabsf(area_2x_234) +
fabsf(area_2x_241) +
104 fabsf(area_2x_123) +
fabsf(area_2x_134) / 8.0f;
112 if ((area_2x_123 >= 0.0f) != (area_2x_134 >= 0.0f)) {
115 if ((
fabsf(area_2x_123) <= eps_zero_area) || (
fabsf(area_2x_134) <= eps_zero_area)) {
120 if ((area_2x_234 >= 0.0f) != (area_2x_241 >= 0.0f)) {
121 if (lock_degenerate) {
127 if ((
fabsf(area_2x_234) <= eps_zero_area) || (
fabsf(area_2x_241) <= eps_zero_area)) {
134 float area_a, area_b;
135 float prim_a, prim_b;
136 float fac_24, fac_13;
138 float len_12, len_23, len_34, len_41, len_24, len_13;
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);
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);
167 return fac_24 - fac_13;
184 const float *
v1, *
v2, *v3, *v4;
186 v1 = coords[e_a_other->
v];
188 v3 = coords[e_b_other->
v];
200 const uint i =
e->base_index;
217 if (eheap_table[i]) {
219 eheap_table[i] =
NULL;
231 e_arr[0] = &edges[
e->e_next];
232 e_arr[1] = &edges[e_arr[0]->
e_next];
234 e = &edges[
e->e_radial];
235 e_arr[2] = &edges[
e->e_next];
236 e_arr[3] = &edges[e_arr[2]->
e_next];
238 for (
uint i = 0; i < 4; i++) {
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]];
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]];
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];
291 const uint coords_num,
298 const uint coord_last = coords_num - 1;
299 const uint tris_len = coords_num - 2;
301 const uint edges_len = tris_len - 1;
305 const uint half_edges_len = 3 * tris_len;
308 sizeof(
struct OrderEdge) * 2 * edges_len);
309 uint order_edges_len = 0;
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;
317 half_edges[e_index_prev].
v = tris[i][j_prev];
318 half_edges[e_index_prev].
e_next = e_index_curr;
322 uint e_pair[2] = {tris[i][j_prev], tris[i][j_curr]};
323 if (e_pair[0] > e_pair[1]) {
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;
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++];
356 eheap_table = (
void *)order_edges;
363 for (
uint i = 0; i < half_edges_len; i++,
e++) {
365 if (
e->e_radial < i) {
371 eheap_table[
e->base_index] =
NULL;
379 eheap_table[
e->base_index] =
NULL;
393 for (
uint i = 0; i < half_edges_len; i++) {
396 uint *tri = tris[tri_index++];
401 e = &half_edges[
e->e_next];
405 e = &half_edges[
e->e_next];
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)
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
void BLI_heap_clear(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
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)
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
_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
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)