polyfill_2d.c File Reference

#include "BLI_utildefines.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.

Classes
struct	KDTreeNode2D_head
struct	KDTreeNode2D
struct	KDTree2D
struct	KDRange2D
struct	PolyFill
struct	PolyIndex

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

Typedefs
typedef int8_t	eSign
typedef bool	axis_t
typedef struct KDTreeNode2D_head	KDTreeNode2D_head
typedef struct KDTreeNode2D	KDTreeNode2D
typedef struct PolyFill	PolyFill
typedef struct PolyIndex	PolyIndex

Enumerations
enum	{ CONCAVE = -1 , TANGENTIAL = 0 , CONVEX = 1 }
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 (struct KDTree2D *tree, uint32_t tot, const float(*coords)[2])
static void	kdtree2d_init (struct 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 (struct KDTree2D *tree)
static void	kdtree2d_init_mapping (struct KDTree2D *tree)
static void	kdtree2d_node_remove (struct KDTree2D *tree, uint32_t index)
static bool	kdtree2d_isect_tri_recursive (const struct KDTree2D *tree, const uint32_t tri_index[3], const float *tri_coords[3], const float tri_center[2], const struct KDRange2D bounds[2], const KDTreeNode2D *node)
static bool	kdtree2d_isect_tri (struct 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.c.

Macro Definition Documentation

KDNODE_UNSET

#define KDNODE_UNSET   ((uint32_t)-1)

Definition at line 195 of file polyfill_2d.c.

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 46 of file polyfill_2d.c.

Referenced by pf_triangulate().

USE_CLIP_SWEEP

#define USE_CLIP_SWEEP

Definition at line 49 of file polyfill_2d.c.

Referenced by pf_triangulate().

USE_CONVEX_SKIP

#define USE_CONVEX_SKIP

Definition at line 47 of file polyfill_2d.c.

USE_KDTREE

#define USE_KDTREE

Definition at line 53 of file polyfill_2d.c.

Typedef Documentation

axis_t

typedef bool axis_t

Spatial optimization for point-in-triangle intersection checks. The simple version of this algorithm is O(n^2) complexity (every point needing to check the triangle defined by every other point), Using a binary-tree reduces the complexity to O(n log n) plus some overhead of creating the tree.

This is a single purpose KDTree based on BLI_kdtree with some modifications to better suit polyfill2d.

• KDTreeNode2D is kept small (only 16 bytes), by not storing coords in the nodes and using index values rather than pointers to reference neg/pos values.
• kdtree2d_isect_tri is the only function currently used. This simply intersects a triangle with the kdtree points.
• the KDTree is only built & used when the polygon is concave.

Definition at line 86 of file polyfill_2d.c.

eSign

typedef int8_t eSign

Definition at line 64 of file polyfill_2d.c.

KDTreeNode2D

typedef struct KDTreeNode2D KDTreeNode2D

KDTreeNode2D_head

typedef struct KDTreeNode2D_head KDTreeNode2D_head

PolyFill

typedef struct PolyFill PolyFill

PolyIndex

typedef struct PolyIndex PolyIndex

Circular double linked-list.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
CONCAVE
TANGENTIAL
CONVEX

Definition at line 115 of file polyfill_2d.c.

anonymous enum

anonymous enum

Enumerator
KDNODE_FLAG_REMOVED

Definition at line 197 of file polyfill_2d.c.

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 181 of file polyfill_2d.c.

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 910 of file polyfill_2d.c.

References BLI_array_alloca, BLI_memarena_free(), BLI_memarena_new(), BLI_polyfill_calc_arena(), 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::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 865 of file polyfill_2d.c.

References BLI_memarena_alloc(), 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 ( struct KDTree2D * tree )

static

Definition at line 291 of file polyfill_2d.c.

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 233 of file polyfill_2d.c.

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

Referenced by kdtree2d_balance(), and kdtree2d_balance_recursive().

kdtree2d_init()

static void kdtree2d_init ( struct 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 213 of file polyfill_2d.c.

References BLI_assert, CONVEX, KDNODE_UNSET, KDTreeNode2D::neg, node, PolyIndex::sign, and tree.

Referenced by polyfill_calc().

kdtree2d_init_mapping()

static void kdtree2d_init_mapping ( struct KDTree2D * tree )

static

Definition at line 296 of file polyfill_2d.c.

References BLI_assert, KDNODE_UNSET, node, KDTreeNode2D::parent, and tree.

Referenced by polyfill_calc().

kdtree2d_isect_tri()

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

static

Definition at line 418 of file polyfill_2d.c.

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

Referenced by pf_ear_tip_check().

kdtree2d_isect_tri_recursive()

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

static

Definition at line 358 of file polyfill_2d.c.

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

Referenced by kdtree2d_isect_tri().

kdtree2d_new()

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

static

Definition at line 201 of file polyfill_2d.c.

References KDNODE_UNSET, and tree.

Referenced by polyfill_calc().

kdtree2d_node_remove()

static void kdtree2d_node_remove ( struct KDTree2D * tree, uint32_t index )

static

Definition at line 317 of file polyfill_2d.c.

References BLI_assert, KDTreeNode2D::flag, PolyIndex::index, KDNODE_FLAG_REMOVED, KDNODE_UNSET, KDTreeNode2D::neg, node, KDTreeNode2D::pos, 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 451 of file polyfill_2d.c.

References kdtree2d_node_remove(), NULL, 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 580 of file polyfill_2d.c.

References float, 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 675 of file polyfill_2d.c.

References BLI_assert, CONCAVE, CONVEX, float, PolyIndex::index, kdtree2d_isect_tri(), PolyIndex::next, pf, PolyIndex::prev, PolyIndex::sign, 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 765 of file polyfill_2d.c.

References PolyIndex::index, PolyIndex::next, pf, pf_coord_remove(), pf_tri_add(), and PolyIndex::prev.

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 588 of file polyfill_2d.c.

References CONCAVE, CONVEX, PolyIndex::next, pf, pf_ear_tip_check(), PolyIndex::prev, PolyIndex::sign, and TANGENTIAL.

Referenced by pf_triangulate().

pf_tri_add()

static uint32_t * pf_tri_add ( PolyFill * pf )

static

Definition at line 446 of file polyfill_2d.c.

References pf.

Referenced by pf_ear_tip_cut(), and pf_triangulate().

pf_triangulate()

static void pf_triangulate ( PolyFill * pf )

static

Definition at line 474 of file polyfill_2d.c.

References CONVEX, PolyIndex::index, kdtree2d_node_remove(), PolyIndex::next, pf, pf_coord_sign_calc(), pf_ear_tip_cut(), pf_ear_tip_find(), pf_tri_add(), PolyIndex::prev, PolyIndex::sign, USE_CLIP_EVEN, and USE_CLIP_SWEEP.

Referenced by polyfill_calc().

polyfill_calc()

static void polyfill_calc ( PolyFill * pf )

static

Definition at line 848 of file polyfill_2d.c.

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 779 of file polyfill_2d.c.

References BLI_assert, CONVEX, cross_poly_v2(), 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 164 of file polyfill_2d.c.

References CONCAVE, CONVEX, TANGENTIAL, and 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 189 of file polyfill_2d.c.

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