#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include "MEM_guardedalloc.h"
#include "BLI_listbase.h"
#include "BLI_math_geom.h"
#include "BLI_math_matrix.h"
#include "BLI_math_vector.h"
#include "BLI_memarena.h"
#include "BLI_utildefines.h"
#include "BLI_scanfill.h"
#include "BLI_strict_flags.h"

Macros
#define	SF_EPSILON 0.00003f
#define	SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)
#define	SF_VERT_NEW 0 /* all new verts have this flag set */
#define	SF_VERT_AVAILABLE 1 /* available - in an edge */
#define	SF_VERT_ZERO_LEN 2
#define	SF_EDGE_NEW 0 /* all new edges have this flag set */
#define	SF_EDGE_INTERNAL 2 /* edge is created while scan-filling */
#define	SF_POLY_NEW 0 /* all polys initialized to this */
#define	SF_POLY_VALID 1 /* has at least 3 verts */

Functions
static int	vergscdata (const void a1, const void a2)
ScanFillVert *	BLI_scanfill_vert_add (ScanFillContext *sf_ctx, const float vec[3])
ScanFillEdge *	BLI_scanfill_edge_add (ScanFillContext sf_ctx, ScanFillVert v1, ScanFillVert *v2)
static void	addfillface (ScanFillContext sf_ctx, ScanFillVert v1, ScanFillVert v2, ScanFillVert v3)
static bool	boundisect (const PolyFill pf2, const PolyFill pf1)
static void	fill_target_map_recursive (const PolyFill __restrict pf_list, const uint pf_len, const uint pf_target, const uint pf_test, uint __restrict target_map)
static void	mergepolysSimp (ScanFillContext sf_ctx, PolyFill pf1, PolyFill *pf2)
static bool	testedgeside (const float v1[2], const float v2[2], const float v3[2])
static bool	addedgetoscanvert (ScanFillVertLink sc, ScanFillEdge eed)
static ScanFillVertLink *	addedgetoscanlist (ScanFillVertLink scdata, ScanFillEdge eed, uint len)
static bool	boundinsideEV (const ScanFillEdge eed, const ScanFillVert eve)
static void	testvertexnearedge (ScanFillContext *sf_ctx)
static void	splitlist (ScanFillContext sf_ctx, ListBase tempve, ListBase *temped, ushort nr)
static uint	scanfill (ScanFillContext sf_ctx, PolyFill pf, const int flag)
void	BLI_scanfill_begin (ScanFillContext *sf_ctx)
void	BLI_scanfill_begin_arena (ScanFillContext sf_ctx, MemArena arena)
void	BLI_scanfill_end (ScanFillContext *sf_ctx)
void	BLI_scanfill_end_arena (ScanFillContext sf_ctx, MemArena arena)
uint	BLI_scanfill_calc_ex (ScanFillContext *sf_ctx, const int flag, const float nor_proj[3])
uint	BLI_scanfill_calc (ScanFillContext *sf_ctx, const int flag)

Detailed Description

Triangulate multiple 2D/3D polygon with support for holes, use for tessellating curves, fonts and geometry. See main function BLI_scanfill_calc

Uses sweep-line method.

Note: There is a similar API in polyfill2d.c which uses ear clipping, but has no hole support.

Definition in file scanfill.cc.

Macro Definition Documentation

◆ SF_EDGE_INTERNAL

#define SF_EDGE_INTERNAL 2 /* edge is created while scan-filling */

Definition at line 69 of file scanfill.cc.

Referenced by scanfill().

◆ SF_EDGE_NEW

#define SF_EDGE_NEW 0 /* all new edges have this flag set */

ScanFillEdge::f (status)

Definition at line 67 of file scanfill.cc.

Referenced by BLI_scanfill_edge_add(), and scanfill().

◆ SF_EPSILON

#define SF_EPSILON 0.00003f

Definition at line 56 of file scanfill.cc.

Referenced by BLI_scanfill_calc_ex(), and testvertexnearedge().

◆ SF_EPSILON_SQ

#define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)

Definition at line 57 of file scanfill.cc.

Referenced by testvertexnearedge().

◆ SF_POLY_NEW

#define SF_POLY_NEW 0 /* all polys initialized to this */

#PolyFill::f (status)

Definition at line 72 of file scanfill.cc.

Referenced by BLI_scanfill_calc_ex(), and scanfill().

◆ SF_POLY_VALID

#define SF_POLY_VALID 1 /* has at least 3 verts */

Definition at line 73 of file scanfill.cc.

Referenced by BLI_scanfill_calc_ex().

◆ SF_VERT_AVAILABLE

#define SF_VERT_AVAILABLE 1 /* available - in an edge */

Definition at line 61 of file scanfill.cc.

Referenced by BLI_scanfill_calc_ex(), and scanfill().

◆ SF_VERT_NEW

#define SF_VERT_NEW 0 /* all new verts have this flag set */

ScanFillVert::f (status)

Definition at line 60 of file scanfill.cc.

Referenced by BLI_scanfill_vert_add(), and scanfill().

◆ SF_VERT_ZERO_LEN

#define SF_VERT_ZERO_LEN 2

Definition at line 62 of file scanfill.cc.

Referenced by scanfill().

Function Documentation

◆ addedgetoscanlist()

ScanFillVertLink * addedgetoscanlist	(	ScanFillVertLink *	scdata,
		ScanFillEdge *	eed,
		uint	len )

static

Definition at line 308 of file scanfill.cc.

References addedgetoscanvert(), len, printf, UNLIKELY, ScanFillEdge::v1, ScanFillEdge::v2, vergscdata(), and ScanFillVert::xy.

Referenced by scanfill().

◆ addedgetoscanvert()

bool addedgetoscanvert	(	ScanFillVertLink *	sc,
		ScanFillEdge *	eed )

static

Definition at line 257 of file scanfill.cc.

References BLI_addtail(), BLI_insertlinkbefore(), ScanFillEdge::next, ScanFillEdge::prev, ScanFillEdge::v1, ScanFillEdge::v2, x, ScanFillVert::xy, and y.

Referenced by addedgetoscanlist().

◆ addfillface()

void addfillface	(	ScanFillContext *	sf_ctx,
		ScanFillVert *	v1,
		ScanFillVert *	v2,
		ScanFillVert *	v3 )

static

Definition at line 141 of file scanfill.cc.

References ScanFillContext::arena, BLI_addtail(), BLI_memarena_alloc(), ScanFillContext::fillfacebase, ScanFillFace::v1, ScanFillFace::v2, v2, and ScanFillFace::v3.

Referenced by scanfill().

◆ BLI_scanfill_begin()

void BLI_scanfill_begin ( ScanFillContext * sf_ctx )

Definition at line 775 of file scanfill.cc.

References ScanFillContext::arena, BLI_memarena_new(), BLI_SCANFILL_ARENA_SIZE, ScanFillContext::poly_nr, and SF_POLY_UNSET.

Referenced by bmo_triangle_fill_exec().

◆ BLI_scanfill_begin_arena()

void BLI_scanfill_begin_arena	(	ScanFillContext *	sf_ctx,
		MemArena *	arena )

Definition at line 782 of file scanfill.cc.

References ScanFillContext::arena, ScanFillContext::poly_nr, and SF_POLY_UNSET.

Referenced by BKE_displist_fill(), and BKE_maskrasterize_handle_init().

◆ BLI_scanfill_calc()

uint BLI_scanfill_calc	(	ScanFillContext *	sf_ctx,
		const int	flag )

Definition at line 1131 of file scanfill.cc.

References BLI_scanfill_calc_ex(), and flag.

◆ BLI_scanfill_calc_ex()

uint BLI_scanfill_calc_ex	(	ScanFillContext *	sf_ctx,
		const int	flag,
		const float	nor_proj[3] )

Definition at line 809 of file scanfill.cc.

References add_newell_cross_v3_v3v3(), axis_dominant_v3_to_m3_negate(), BLI_assert, BLI_listbase_clear(), BLI_listbase_is_empty(), BLI_movelisttolist(), BLI_remlink(), BLI_SCANFILL_CALC_HOLES, BLI_SCANFILL_CALC_LOOSE, BLI_SCANFILL_CALC_POLYS, compare_v3v3(), copy_v3_v3(), ScanFillVert::edge_count, fill_target_map_recursive(), ScanFillContext::filledgebase, ScanFillContext::fillvertbase, ListBase::first, flag, ListBase::last, len_squared_v3(), LIKELY, LISTBASE_FOREACH, MEM_calloc_arrayN(), MEM_freeN(), MEM_malloc_arrayN(), mergepolysSimp(), mul_v2_m3v3(), ScanFillEdge::next, normalize_v3(), pf, ScanFillContext::poly_nr, ScanFillEdge::poly_nr, ScanFillVert::poly_nr, ScanFillEdge::prev, printf, range_vn_u(), scanfill(), SF_EPSILON, SF_POLY_NEW, SF_POLY_UNSET, SF_POLY_VALID, SF_VERT_AVAILABLE, splitlist(), testvertexnearedge(), UNLIKELY, ScanFillEdge::v1, ScanFillEdge::v2, and zero_v3().

Referenced by BKE_displist_fill(), BKE_maskrasterize_handle_init(), BLI_scanfill_calc(), and bmo_triangle_fill_exec().

◆ BLI_scanfill_edge_add()

ScanFillEdge * BLI_scanfill_edge_add	(	ScanFillContext *	sf_ctx,
		ScanFillVert *	v1,
		ScanFillVert *	v2 )

Definition at line 122 of file scanfill.cc.

References ScanFillContext::arena, BLI_addtail(), BLI_memarena_alloc(), ScanFillEdge::c, ScanFillEdge::f, ScanFillContext::filledgebase, ScanFillContext::poly_nr, ScanFillEdge::poly_nr, SF_EDGE_NEW, ScanFillEdge::tmp, ScanFillEdge::user_flag, ScanFillEdge::v1, ScanFillEdge::v2, and v2.

Referenced by BKE_displist_fill(), BKE_maskrasterize_handle_init(), bmo_triangle_fill_exec(), scanfill(), scanfill_preprocess_self_isect(), and testvertexnearedge().

◆ BLI_scanfill_end()

void BLI_scanfill_end ( ScanFillContext * sf_ctx )

Definition at line 789 of file scanfill.cc.

References ScanFillContext::arena, BLI_listbase_clear(), BLI_memarena_free(), ScanFillContext::filledgebase, ScanFillContext::fillfacebase, and ScanFillContext::fillvertbase.

Referenced by bmo_triangle_fill_exec().

◆ BLI_scanfill_end_arena()

void BLI_scanfill_end_arena	(	ScanFillContext *	sf_ctx,
		MemArena *	arena )

Definition at line 799 of file scanfill.cc.

References ScanFillContext::arena, BLI_assert, BLI_listbase_clear(), BLI_memarena_clear(), ScanFillContext::filledgebase, ScanFillContext::fillfacebase, and ScanFillContext::fillvertbase.

Referenced by BKE_displist_fill(), and BKE_maskrasterize_handle_init().

◆ BLI_scanfill_vert_add()

ScanFillVert * BLI_scanfill_vert_add	(	ScanFillContext *	sf_ctx,
		const float	vec[3] )

◆ boundinsideEV()

bool boundinsideEV	(	const ScanFillEdge *	eed,
		const ScanFillVert *	eve )

static

Return true if eve inside the bound-box of eed.

Definition at line 345 of file scanfill.cc.

References ScanFillEdge::v1, ScanFillEdge::v2, and ScanFillVert::xy.

Referenced by testvertexnearedge().

◆ boundisect()

bool boundisect	(	const PolyFill *	pf2,
		const PolyFill *	pf1 )

static

Definition at line 157 of file scanfill.cc.

References pf2.

Referenced by fill_target_map_recursive().

◆ fill_target_map_recursive()

void fill_target_map_recursive	(	const PolyFill *__restrict	pf_list,
		const uint	pf_len,
		const uint	pf_target,
		const uint	pf_test,
		uint *__restrict	target_map )

static

Definition at line 183 of file scanfill.cc.

References BLI_assert, boundisect(), and fill_target_map_recursive().

Referenced by BLI_scanfill_calc_ex(), and fill_target_map_recursive().

◆ mergepolysSimp()

void mergepolysSimp	(	ScanFillContext *	sf_ctx,
		PolyFill *	pf1,
		PolyFill *	pf2 )

static

Definition at line 205 of file scanfill.cc.

References ScanFillContext::filledgebase, ScanFillContext::fillvertbase, LISTBASE_FOREACH, and pf2.

Referenced by BLI_scanfill_calc_ex().

◆ scanfill()

uint scanfill	(	ScanFillContext *	sf_ctx,
		PolyFill *	pf,
		const int	flag )

static

◆ splitlist()

void splitlist	(	ScanFillContext *	sf_ctx,
		ListBase *	tempve,
		ListBase *	temped,
		ushort	nr )

static

Definition at line 427 of file scanfill.cc.

References BLI_addtail(), BLI_movelisttolist(), BLI_remlink(), ScanFillContext::filledgebase, ScanFillContext::fillvertbase, and LISTBASE_FOREACH_MUTABLE.

Referenced by BLI_scanfill_calc_ex().

◆ testedgeside()

bool testedgeside	(	const float	v1[2],
		const float	v2[2],
		const float	v3[2] )

static

Definition at line 236 of file scanfill.cc.

References v2.

Referenced by scanfill().

◆ testvertexnearedge()

void testvertexnearedge ( ScanFillContext * sf_ctx )

static

Definition at line 373 of file scanfill.cc.

References BLI_scanfill_edge_add(), boundinsideEV(), compare_v2v2(), dist_squared_to_line_v2(), ScanFillVert::edge_count, ScanFillContext::filledgebase, ScanFillContext::fillvertbase, ListBase::first, LISTBASE_FOREACH, ScanFillEdge::next, ScanFillEdge::poly_nr, SF_EPSILON, SF_EPSILON_SQ, ScanFillEdge::v1, and ScanFillEdge::v2.

Referenced by BLI_scanfill_calc_ex().

◆ vergscdata()

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

static

Definition at line 77 of file scanfill.cc.

References ScanFillVert::xy.

Referenced by addedgetoscanlist(), and scanfill().

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ SF_EDGE_INTERNAL

◆ SF_EDGE_NEW

◆ SF_EPSILON

◆ SF_EPSILON_SQ

◆ SF_POLY_NEW

◆ SF_POLY_VALID

◆ SF_VERT_AVAILABLE

◆ SF_VERT_NEW

◆ SF_VERT_ZERO_LEN

Function Documentation

◆ addedgetoscanlist()

◆ addedgetoscanvert()

◆ addfillface()

◆ BLI_scanfill_begin()

◆ BLI_scanfill_begin_arena()

◆ BLI_scanfill_calc()

◆ BLI_scanfill_calc_ex()

◆ BLI_scanfill_edge_add()

◆ BLI_scanfill_end()

◆ BLI_scanfill_end_arena()

◆ BLI_scanfill_vert_add()

◆ boundinsideEV()

◆ boundisect()

◆ fill_target_map_recursive()

◆ mergepolysSimp()

◆ scanfill()

◆ splitlist()

◆ testedgeside()

◆ testvertexnearedge()

◆ vergscdata()