polyfill_2d.cc File Reference

#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"

Go to the source code of this file.

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_ear_tip_find(), and pf_triangulate().

USE_CLIP_SWEEP

#define USE_CLIP_SWEEP

Definition at line 53 of file polyfill_2d.cc.

Referenced by pf_ear_tip_find(), and 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 BLI_INLINE, sub_v2_v2v2(), and v2.

Referenced by span_tri_v2_sign().

BLI_polyfill_calc()

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

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.

BLI_polyfill_calc_arena()

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 )

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 BLI_polyfill_calc().

kdtree2d_balance()

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()

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 i, KDNODE_UNSET, kdtree2d_balance_recursive(), pos, and SWAP.

Referenced by kdtree2d_balance(), and kdtree2d_balance_recursive().

kdtree2d_init()

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, i, indices, KDNODE_UNSET, sign(), and tree.

Referenced by polyfill_calc().

kdtree2d_init_mapping()

void kdtree2d_init_mapping ( KDTree2D * tree )

static

Definition at line 302 of file polyfill_2d.cc.

References BLI_assert, i, KDNODE_UNSET, and tree.

Referenced by polyfill_calc().

kdtree2d_isect_tri()

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, i, kdtree2d_isect_tri_recursive(), max, min, mul_v2_fl(), and tree.

Referenced by pf_ear_tip_check().

kdtree2d_isect_tri_recursive()

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, span_tri_v2_sign(), and tree.

Referenced by kdtree2d_isect_tri().

kdtree2d_new()

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()

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, and tree.

Referenced by pf_coord_remove(), and pf_triangulate().

pf_coord_remove()

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()

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 float, pf, and span_tri_v2_sign().

Referenced by pf_triangulate(), and polyfill_prepare().

pf_ear_tip_check()

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, float, kdtree2d_isect_tri(), pf, span_tri_v2_sign(), UNLIKELY, v, and v2.

Referenced by pf_ear_tip_find().

pf_ear_tip_cut()

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()

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

static

Definition at line 594 of file polyfill_2d.cc.

References i, pf, pf_ear_tip_check(), USE_CLIP_EVEN, and USE_CLIP_SWEEP.

Referenced by pf_triangulate().

pf_tri_add()

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()

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(), USE_CLIP_EVEN, and USE_CLIP_SWEEP.

Referenced by polyfill_calc().

polyfill_calc()

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()

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(), i, 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 BLI_INLINE, and UNLIKELY.

Referenced by span_tri_v2_sign().

span_tri_v2_sign()

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().