Blender  V3.3
Classes | Functions
polyfill_2d_beautify.c File Reference
#include "BLI_math.h"
#include "BLI_utildefines.h"
#include "BLI_heap.h"
#include "BLI_memarena.h"
#include "BLI_polyfill_2d_beautify.h"
#include "BLI_strict_flags.h"

Go to the source code of this file.

Classes

struct  OrderEdge
 
struct  HalfEdge
 

Functions

static int oedge_cmp (const void *a1, const void *a2)
 
BLI_INLINE bool is_boundary_edge (uint i_a, uint i_b, const uint coord_last)
 
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_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 void polyedge_rotate (struct HalfEdge *edges, struct HalfEdge *e)
 
void BLI_polyfill_beautify (const float(*coords)[2], const uint coords_num, uint(*tris)[3], MemArena *arena, Heap *eheap)
 

Detailed Description

This function is to improve the tessellation resulting from polyfill2d, creating optimal topology.

The functionality here matches BM_mesh_beautify_fill, but its far simpler to perform this operation in 2d, on a simple polygon representation where we know:

Note

No globals - keep threadsafe.

Definition in file polyfill_2d_beautify.c.

Function Documentation

◆ BLI_polyfill_beautify()

void BLI_polyfill_beautify ( const float(*)  coords[2],
unsigned int  coords_num,
unsigned int(*)  tris[3],
struct MemArena arena,
struct Heap eheap 
)

The intention is that this calculates the output of BLI_polyfill_calc

Note
assumes the coords form a boundary, so any edges running along contiguous (wrapped) indices, are ignored since the edges won't share 2 faces.

Definition at line 290 of file polyfill_2d_beautify.c.

References HalfEdge::base_index, BLI_assert, BLI_heap_clear(), BLI_heap_insert(), BLI_heap_is_empty(), BLI_heap_pop_min(), BLI_memarena_alloc(), e, OrderEdge::e_half, HalfEdge::e_next, HalfEdge::e_radial, is_boundary_edge(), NULL, oedge_cmp(), polyedge_beauty_cost_update(), polyedge_rotate(), polyedge_rotate_beauty_calc(), SWAP, UINT_MAX, HalfEdge::v, and OrderEdge::verts.

Referenced by BM_face_triangulate(), bmesh_calc_tessellation_for_face_beauty(), p_add_ngon(), and test_polyfill_template().

◆ BLI_polyfill_beautify_quad_rotate_calc_ex()

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 
)

Assuming we have 2 triangles sharing an edge (2 - 4), check if the edge running from (1 - 3) gives better results.

Parameters
lock_degenerateUse to avoid rotating out of a degenerate state:
  • When true, an existing zero area face on either side of the (2 - 4 split will return a positive value.
  • When false, the check must be non-biased towards either split direction.
r_areaReturn the area of the quad, This can be useful when comparing the return value with near zero epsilons. In this case the epsilon can be scaled by the area to avoid the return value of very large faces not having a reliable way to detect near-zero output.
Returns
(negative number means the edge can be rotated, lager == better).

Definition at line 81 of file polyfill_2d_beautify.c.

References BLI_assert, cross_tri_v2(), ELEM, fabsf, len_v2v2(), v1, and v2.

Referenced by bm_edge_calc_rotate_beauty__area(), and polyedge_rotate_beauty_calc().

◆ is_boundary_edge()

BLI_INLINE bool is_boundary_edge ( uint  i_a,
uint  i_b,
const uint  coord_last 
)

Definition at line 76 of file polyfill_2d_beautify.c.

References BLI_assert, and UNLIKELY.

Referenced by BLI_polyfill_beautify().

◆ oedge_cmp()

static int oedge_cmp ( const void a1,
const void a2 
)
static

Definition at line 47 of file polyfill_2d_beautify.c.

References BLI_assert, OrderEdge::e_half, OrderEdge::verts, and x2.

Referenced by BLI_polyfill_beautify().

◆ polyedge_beauty_cost_update()

static void polyedge_beauty_cost_update ( const float(*)  coords[2],
struct HalfEdge edges,
struct HalfEdge e,
Heap eheap,
HeapNode **  eheap_table 
)
static

◆ polyedge_beauty_cost_update_single()

static void polyedge_beauty_cost_update_single ( const float(*)  coords[2],
const struct HalfEdge edges,
struct HalfEdge e,
Heap eheap,
HeapNode **  eheap_table 
)
static

◆ polyedge_rotate()

static void polyedge_rotate ( struct HalfEdge edges,
struct HalfEdge e 
)
static

CCW winding, rotate internal edge to new vertical state.

Before After
X X
/ \ /|\
e4/ \e5 e4/ | \e5
/ e3 \ / | \
X ------- X -> X e0|e3 X
\ e0 / \ | /
e2\ /e1 e2\ | /e1
\ / \|/
X X

Definition at line 245 of file polyfill_2d_beautify.c.

References e, HalfEdge::e_next, and HalfEdge::v.

Referenced by BLI_polyfill_beautify().

◆ polyedge_rotate_beauty_calc()

static float polyedge_rotate_beauty_calc ( const float(*)  coords[2],
const struct HalfEdge edges,
const struct HalfEdge e_a,
float r_area 
)
static