#include "BLI_utildefines.h"
#include "BLI_heap.h"
#include "BLI_math_geom.h"
#include "BLI_memarena.h"
#include "BLI_polyfill_2d_beautify.h"
#include "BLI_strict_flags.h"

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, const 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:

The polygon is primitive with no holes with a continuous boundary.
Triangles have consistent winding.
2d (saves some hassles projecting face pairs on an axis for every edge-rotation) also saves us having to store all previous edge-states (see EdRotState in bmesh_beautify.cc).

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 294 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 blender::geometry::PackIsland::add_polygon(), BM_face_triangulate(), bmesh_calc_tessellation_for_face_beauty(), blender::geometry::p_add_ngon(), test_polyfill_template(), and uv_select_overlap().

◆ 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_degenerate	Use 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_area	Return 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 84 of file polyfill_2d_beautify.c.

References BLI_assert, cross_tri_v2(), ELEM, fabsf, FLT_MAX, len_v2v2(), 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 79 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 50 of file polyfill_2d_beautify.c.

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

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

Definition at line 228 of file polyfill_2d_beautify.c.

References HalfEdge::base_index, e, HalfEdge::e_next, polyedge_beauty_cost_update_single(), and UINT_MAX.

Referenced by BLI_polyfill_beautify().

◆ 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

Definition at line 198 of file polyfill_2d_beautify.c.

References BLI_heap_insert_or_update(), BLI_heap_remove(), e, max_ff(), NULL, and polyedge_rotate_beauty_calc().

Referenced by polyedge_beauty_cost_update().

◆ polyedge_rotate()

static void polyedge_rotate	(	struct HalfEdge *	edges,
		const 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 249 of file polyfill_2d_beautify.c.

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

Referenced by BLI_polyfill_beautify().