#include "BLI_utildefines.h"
#include "BLI_heap.h"
#include "BLI_math_geom.h"
#include "BLI_math_matrix.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)
float	BLI_polyfill_edge_calc_rotate_beauty__area (const float v1[3], const float v2[3], const float v3[3], const float v4[3], const bool lock_degenerate)
static float	polyedge_rotate_beauty_calc (const float(coords)[2], const HalfEdge edges, const HalfEdge e_a, float r_area)
static void	polyedge_beauty_cost_update_single (const float(coords)[2], const HalfEdge edges, HalfEdge e, Heap eheap, HeapNode **eheap_table)
static void	polyedge_beauty_cost_update (const float(coords)[2], HalfEdge edges, HalfEdge e, Heap eheap, HeapNode **eheap_table)
static void	polyedge_rotate (HalfEdge edges, const 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.cc.

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 363 of file polyfill_2d_beautify.cc.

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, i, is_boundary_edge(), 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::ngon::calc_corner_tris(), 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 86 of file polyfill_2d_beautify.cc.

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

Referenced by BLI_polyfill_edge_calc_rotate_beauty__area(), and polyedge_rotate_beauty_calc().

◆ BLI_polyfill_edge_calc_rotate_beauty__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],
		const bool	lock_degenerate )

Check if input faces are already flipped. Logic for 'signum_i' addition is:

Accept:

(1, 1) or (-1, -1): same side (common case).
(-1/1, 0): one degenerate, OK since we may rotate into a valid state.

Ignore:

(-1, 1): opposite winding, ignore.
( 0, 0): both degenerate, ignore.

Note: The cross product is divided by 'no_scale' so the rotation calculation is scale independent.

Important to lock degenerate here, since the triangle pars will be projected into different 2D spaces. Allowing to rotate out of a degenerate state can flip the faces (when performed iteratively).

Definition at line 180 of file polyfill_2d_beautify.cc.

References add_v3_v3v3(), axis_dominant_v3_to_m3(), BLI_assert, BLI_polyfill_beautify_quad_rotate_calc_ex(), cross_tri_v2(), cross_tri_v3(), ELEM, eps, FLT_MAX, mul_v2_m3v3(), normalize_v3(), signum_i_ex(), UNLIKELY, and v2.

Referenced by BM_verts_calc_rotate_beauty(), and blender::geometry::quad::calc_quad_direction_beauty().

◆ is_boundary_edge()

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

Definition at line 81 of file polyfill_2d_beautify.cc.

References BLI_assert, BLI_INLINE, and UNLIKELY.

Referenced by BLI_polyfill_beautify().

◆ oedge_cmp()

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

static

Definition at line 51 of file polyfill_2d_beautify.cc.

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

Referenced by BLI_polyfill_beautify().

◆ polyedge_beauty_cost_update()

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

static

Definition at line 300 of file polyfill_2d_beautify.cc.

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

Referenced by BLI_polyfill_beautify().

◆ polyedge_beauty_cost_update_single()

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

static

Definition at line 270 of file polyfill_2d_beautify.cc.

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

Referenced by polyedge_beauty_cost_update().

◆ polyedge_rotate()

void polyedge_rotate	(	HalfEdge *	edges,
		const 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 318 of file polyfill_2d_beautify.cc.

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

Referenced by BLI_polyfill_beautify().