#include "BLI_utildefines.h"
#include <cstdlib>
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_math_geom.h"
#include "BLI_math_vector.h"
#include "BLI_memarena.h"
#include "BLI_polyfill_2d.h"
#include "BLI_strict_flags.h"

Macros
#define	USE_CLIP_EVEN

#define	USE_CONVEX_SKIP

#define	USE_CLIP_SWEEP

#define	USE_KDTREE

#define	KDNODE_UNSET (uint32_t(-1))

#define	KDTREE2D_ISECT_TRI_RECURSE_NEG

#define	KDTREE2D_ISECT_TRI_RECURSE_POS

Enumerations
enum	{ KDNODE_FLAG_REMOVED = (1 << 0) }

Functions
static void	pf_coord_sign_calc (const PolyFill pf, PolyIndex pi)

static PolyIndex *	pf_ear_tip_find (PolyFill pf, PolyIndex pi_ear_init, bool reverse)

static bool	pf_ear_tip_check (PolyFill pf, PolyIndex pi_ear_tip, const eSign sign_accept)

static void	pf_ear_tip_cut (PolyFill pf, PolyIndex pi_ear_tip)

BLI_INLINE eSign	signum_enum (float a)

BLI_INLINE float	area_tri_signed_v2_alt_2x (const float v1[2], const float v2[2], const float v3[2])

static eSign	span_tri_v2_sign (const float v1[2], const float v2[2], const float v3[2])

static void	kdtree2d_new (KDTree2D tree, uint32_t tot, const float(coords)[2])

static void	kdtree2d_init (KDTree2D tree, const uint32_t coords_num, const PolyIndex indices)

static uint32_t	kdtree2d_balance_recursive (KDTreeNode2D nodes, uint32_t node_num, axis_t axis, const float(coords)[2], const uint32_t ofs)

static void	kdtree2d_balance (KDTree2D *tree)

static void	kdtree2d_init_mapping (KDTree2D *tree)

static void	kdtree2d_node_remove (KDTree2D *tree, uint32_t index)

static bool	kdtree2d_isect_tri_recursive (const KDTree2D tree, const uint32_t tri_index[3], const float tri_coords[3], const float tri_center[2], const KDRange2D bounds[2], const KDTreeNode2D *node)

static bool	kdtree2d_isect_tri (KDTree2D *tree, const uint32_t ind[3])

static uint32_t *	pf_tri_add (PolyFill *pf)

static void	pf_coord_remove (PolyFill pf, PolyIndex pi)

static void	pf_triangulate (PolyFill *pf)

static void	polyfill_prepare (PolyFill pf, const float(coords)[2], const uint32_t coords_num, int coords_sign, uint32_t(r_tris)[3], PolyIndex r_indices)

static void	polyfill_calc (PolyFill *pf)

void	BLI_polyfill_calc_arena (const float(coords)[2], const uint32_t coords_num, const int coords_sign, uint32_t(r_tris)[3], MemArena *arena)

void	BLI_polyfill_calc (const float(coords)[2], const uint32_t coords_num, const int coords_sign, uint32_t(r_tris)[3])

Detailed Description

An ear clipping algorithm to triangulate single boundary polygons.

Details:

The algorithm guarantees all triangles are assigned (number of coords - 2) and that triangles will have non-overlapping indices (even for degenerate geometry).
Self-intersections are considered degenerate (resulting triangles will overlap).
While multiple polygons aren't supported, holes can still be defined using key-holes (where the polygon doubles back on itself with exactly matching coordinates).

Note

Changes made for Blender.

loop the array to clip last verts first (less array resizing)
advance the ear to clip each iteration to avoid fan-filling convex shapes (USE_CLIP_EVEN).
avoid intersection tests when there are no convex points (USE_CONVEX_SKIP).

Note

No globals - keep threadsafe.

Definition in file polyfill_2d.cc.

Macro Definition Documentation

◆ KDNODE_UNSET

#define KDNODE_UNSET (uint32_t(-1))

Definition at line 203 of file polyfill_2d.cc.

Referenced by kdtree2d_balance_recursive(), kdtree2d_init(), kdtree2d_init_mapping(), kdtree2d_isect_tri_recursive(), kdtree2d_new(), and kdtree2d_node_remove().

◆ KDTREE2D_ISECT_TRI_RECURSE_NEG

#define KDTREE2D_ISECT_TRI_RECURSE_NEG

Value:

    (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) && \
     kdtree2d_isect_tri_recursive( \
         tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->neg]))

Referenced by kdtree2d_isect_tri_recursive().

◆ KDTREE2D_ISECT_TRI_RECURSE_POS

#define KDTREE2D_ISECT_TRI_RECURSE_POS

Value:

    (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) && \
     kdtree2d_isect_tri_recursive( \
         tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->pos]))

Referenced by kdtree2d_isect_tri_recursive().

◆ USE_CLIP_EVEN

#define USE_CLIP_EVEN

Definition at line 50 of file polyfill_2d.cc.

Referenced by pf_triangulate().

◆ USE_CLIP_SWEEP

#define USE_CLIP_SWEEP

Definition at line 53 of file polyfill_2d.cc.

Referenced by pf_triangulate().

◆ USE_CONVEX_SKIP

#define USE_CONVEX_SKIP

Definition at line 51 of file polyfill_2d.cc.

◆ USE_KDTREE

#define USE_KDTREE

Definition at line 57 of file polyfill_2d.cc.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Enumerator
KDNODE_FLAG_REMOVED

Definition at line 205 of file polyfill_2d.cc.

Function Documentation

◆ area_tri_signed_v2_alt_2x()

BLI_INLINE float area_tri_signed_v2_alt_2x	(	const float	v1[2],
		const float	v2[2],
		const float	v3[2] )

alternative version of area_tri_signed_v2 needed because of float precision issues

Note: removes / 2 since its not needed since we only need the sign.

Definition at line 189 of file polyfill_2d.cc.

References sub_v2_v2v2(), and v2.

Referenced by span_tri_v2_sign().

◆ BLI_polyfill_calc()

void BLI_polyfill_calc	(	const float(*)	coords[2],
		unsigned int	coords_num,
		int	coords_sign,
		unsigned int(*)	r_tris[3] )

Triangulates the given (convex or concave) simple polygon to a list of triangle vertices.

Parameters

coords	2D coordinates describing vertices of the polygon, in either clockwise or counterclockwise order.
coords_num	Total points in the array.
coords_sign	Pass this when we know the sign in advance to avoid extra calculations.
r_tris	This array is filled in with triangle indices in clockwise order. The length of the array must be `coords_num - 2`. Indices are guaranteed to be assigned to unique triangles, with valid indices, even in the case of degenerate input (self intersecting polygons, zero area ears... etc).

Definition at line 918 of file polyfill_2d.cc.

References BLI_array_alloca, BLI_memarena_free(), BLI_memarena_new(), BLI_polyfill_calc_arena(), indices, pf, polyfill_calc(), polyfill_prepare(), TIMEIT_END, TIMEIT_START, and UNLIKELY.

Referenced by BKE_gpencil_stroke_fill_triangulate(), BKE_mesh_remap_calc_faces_from_mesh(), BM_face_calc_tessellation(), blender::geometry::ngon::calc_corner_tris(), blender::ed::sculpt_paint::trim::generate_geometry(), GPU_batch_tris_from_poly_2d_encoded(), test_polyfill_template(), and ui_draw_but_CURVEPROFILE().

◆ BLI_polyfill_calc_arena()

void BLI_polyfill_calc_arena	(	const float(*)	coords[2],
		unsigned int	coords_num,
		int	coords_sign,
		unsigned int(*)	r_tris[3],
		struct MemArena *	arena )

A version of BLI_polyfill_calc that uses a memory arena to avoid re-allocations.

Definition at line 871 of file polyfill_2d.cc.

References BLI_memarena_alloc(), indices, pf, polyfill_calc(), polyfill_prepare(), TIMEIT_END, and TIMEIT_START.

Referenced by blender::geometry::PackIsland::add_polygon(), BLI_polyfill_calc(), BM_face_triangulate(), bmesh_calc_tessellation_for_face_beauty(), bmesh_calc_tessellation_for_face_impl(), C_BVHTree_FromPolygons(), blender::bke::mesh::mesh_calc_tessellation_for_face_impl(), mesh_tessface_calc(), blender::geometry::p_add_ngon(), blender::bke::greasepencil::update_triangle_cache(), and uv_select_overlap().

◆ kdtree2d_balance()

static void kdtree2d_balance ( KDTree2D * tree )

static

Definition at line 297 of file polyfill_2d.cc.

References kdtree2d_balance_recursive(), and tree.

Referenced by polyfill_calc().

◆ kdtree2d_balance_recursive()

static uint32_t kdtree2d_balance_recursive	(	KDTreeNode2D *	nodes,
		uint32_t	node_num,
		axis_t	axis,
		const float(*)	coords[2],
		const uint32_t	ofs )

static

Definition at line 239 of file polyfill_2d.cc.

References KDNODE_UNSET, kdtree2d_balance_recursive(), node, pos, and SWAP.

Referenced by kdtree2d_balance(), and kdtree2d_balance_recursive().

◆ kdtree2d_init()

static void kdtree2d_init	(	KDTree2D *	tree,
		const uint32_t	coords_num,
		const PolyIndex *	indices )

static

no need for kdtree2d_insert, since we know the coords array.

Definition at line 221 of file polyfill_2d.cc.

References BLI_assert, indices, KDNODE_UNSET, node, sign(), and tree.

Referenced by polyfill_calc().

◆ kdtree2d_init_mapping()

static void kdtree2d_init_mapping ( KDTree2D * tree )

static

Definition at line 302 of file polyfill_2d.cc.

References BLI_assert, KDNODE_UNSET, node, and tree.

Referenced by polyfill_calc().

◆ kdtree2d_isect_tri()

static bool kdtree2d_isect_tri	(	KDTree2D *	tree,
		const uint32_t	ind[3] )

static

Definition at line 424 of file polyfill_2d.cc.

References add_v2_v2(), bounds(), CLAMP_MAX, CLAMP_MIN, FLT_MAX, kdtree2d_isect_tri_recursive(), max, min, mul_v2_fl(), and tree.

Referenced by pf_ear_tip_check().

◆ kdtree2d_isect_tri_recursive()

static bool kdtree2d_isect_tri_recursive	(	const KDTree2D *	tree,
		const uint32_t	tri_index[3],
		const float *	tri_coords[3],
		const float	tri_center[2],
		const KDRange2D	bounds[2],
		const KDTreeNode2D *	node )

static

Definition at line 364 of file polyfill_2d.cc.

References BLI_assert, bounds(), ELEM, KDNODE_FLAG_REMOVED, KDNODE_UNSET, KDTREE2D_ISECT_TRI_RECURSE_NEG, KDTREE2D_ISECT_TRI_RECURSE_POS, max, min, node, span_tri_v2_sign(), and tree.

Referenced by kdtree2d_isect_tri().

◆ kdtree2d_new()

static void kdtree2d_new	(	KDTree2D *	tree,
		uint32_t	tot,
		const float(*)	coords[2] )

static

Definition at line 209 of file polyfill_2d.cc.

References KDNODE_UNSET, and tree.

Referenced by polyfill_calc().

◆ kdtree2d_node_remove()

static void kdtree2d_node_remove	(	KDTree2D *	tree,
		uint32_t	index )

static

Definition at line 323 of file polyfill_2d.cc.

References BLI_assert, KDNODE_FLAG_REMOVED, KDNODE_UNSET, node, and tree.

Referenced by pf_coord_remove(), and pf_triangulate().

◆ pf_coord_remove()

static void pf_coord_remove	(	PolyFill *	pf,
		PolyIndex *	pi )

static

Definition at line 457 of file polyfill_2d.cc.

References kdtree2d_node_remove(), pf, and UNLIKELY.

Referenced by pf_ear_tip_cut().

◆ pf_coord_sign_calc()

static void pf_coord_sign_calc	(	const PolyFill *	pf,
		PolyIndex *	pi )

static

Returns: CONCAVE, TANGENTIAL or CONVEX

Definition at line 586 of file polyfill_2d.cc.

References pf, and span_tri_v2_sign().

Referenced by pf_triangulate(), and polyfill_prepare().

◆ pf_ear_tip_check()

static bool pf_ear_tip_check	(	PolyFill *	pf,
		PolyIndex *	pi_ear_tip,
		const eSign	sign_accept )

static

Definition at line 681 of file polyfill_2d.cc.

References BLI_assert, kdtree2d_isect_tri(), pf, span_tri_v2_sign(), UNLIKELY, v, and v2.

Referenced by pf_ear_tip_find().

◆ pf_ear_tip_cut()

static void pf_ear_tip_cut	(	PolyFill *	pf,
		PolyIndex *	pi_ear_tip )

static

Definition at line 771 of file polyfill_2d.cc.

References pf, pf_coord_remove(), and pf_tri_add().

Referenced by pf_triangulate().

◆ pf_ear_tip_find()

static PolyIndex * pf_ear_tip_find	(	PolyFill *	pf,
		PolyIndex *	pi_ear_init,
		bool	reverse )

static

Definition at line 594 of file polyfill_2d.cc.

References pf, and pf_ear_tip_check().

Referenced by pf_triangulate().

◆ pf_tri_add()

static uint32_t * pf_tri_add ( PolyFill * pf )

static

Definition at line 452 of file polyfill_2d.cc.

References pf.

Referenced by pf_ear_tip_cut(), and pf_triangulate().

◆ pf_triangulate()

static void pf_triangulate ( PolyFill * pf )

static

Definition at line 480 of file polyfill_2d.cc.

References kdtree2d_node_remove(), pf, pf_coord_sign_calc(), pf_ear_tip_cut(), pf_ear_tip_find(), pf_tri_add(), sign(), USE_CLIP_EVEN, and USE_CLIP_SWEEP.

Referenced by polyfill_calc().

◆ polyfill_calc()

static void polyfill_calc ( PolyFill * pf )

static

Definition at line 854 of file polyfill_2d.cc.

References kdtree2d_balance(), kdtree2d_init(), kdtree2d_init_mapping(), kdtree2d_new(), pf, and pf_triangulate().

Referenced by BLI_polyfill_calc(), and BLI_polyfill_calc_arena().

◆ polyfill_prepare()

static void polyfill_prepare	(	PolyFill *	pf,
		const float(*)	coords[2],
		const uint32_t	coords_num,
		int	coords_sign,
		uint32_t(*)	r_tris[3],
		PolyIndex *	r_indices )

static

Initializes the #PolyFill structure before tessellating with polyfill_calc.

Definition at line 785 of file polyfill_2d.cc.

References BLI_assert, cross_poly_v2(), indices, pf, and pf_coord_sign_calc().

Referenced by BLI_polyfill_calc(), and BLI_polyfill_calc_arena().

◆ signum_enum()

BLI_INLINE eSign signum_enum ( float a )

Definition at line 172 of file polyfill_2d.cc.

References UNLIKELY.

Referenced by span_tri_v2_sign().

◆ span_tri_v2_sign()

static eSign span_tri_v2_sign	(	const float	v1[2],
		const float	v2[2],
		const float	v3[2] )

static

Definition at line 197 of file polyfill_2d.cc.

References area_tri_signed_v2_alt_2x(), signum_enum(), and v2.

Referenced by kdtree2d_isect_tri_recursive(), pf_coord_sign_calc(), and pf_ear_tip_check().

Macros

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ KDNODE_UNSET

◆ KDTREE2D_ISECT_TRI_RECURSE_NEG

◆ KDTREE2D_ISECT_TRI_RECURSE_POS

◆ USE_CLIP_EVEN

◆ USE_CLIP_SWEEP

◆ USE_CONVEX_SKIP

◆ USE_KDTREE

Enumeration Type Documentation

◆ anonymous enum

Function Documentation

◆ area_tri_signed_v2_alt_2x()

◆ BLI_polyfill_calc()

◆ BLI_polyfill_calc_arena()

◆ kdtree2d_balance()

◆ kdtree2d_balance_recursive()

◆ kdtree2d_init()

◆ kdtree2d_init_mapping()

◆ kdtree2d_isect_tri()

◆ kdtree2d_isect_tri_recursive()

◆ kdtree2d_new()

◆ kdtree2d_node_remove()

◆ pf_coord_remove()

◆ pf_coord_sign_calc()

◆ pf_ear_tip_check()

◆ pf_ear_tip_cut()

◆ pf_ear_tip_find()

◆ pf_tri_add()

◆ pf_triangulate()

◆ polyfill_calc()

◆ polyfill_prepare()

◆ signum_enum()

◆ span_tri_v2_sign()