#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#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"

Classes
struct	PolyFill

struct	ScanFillVertLink

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 */

Typedefs
typedef struct PolyFill	PolyFill

typedef struct ScanFillVertLink	ScanFillVertLink

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.c.

Macro Definition Documentation

◆ SF_EDGE_INTERNAL

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

Definition at line 65 of file scanfill.c.

Referenced by scanfill().

◆ SF_EDGE_NEW

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

ScanFillEdge::f (status)

Definition at line 63 of file scanfill.c.

Referenced by BLI_scanfill_edge_add(), and scanfill().

◆ SF_EPSILON

#define SF_EPSILON 0.00003f

Definition at line 52 of file scanfill.c.

Referenced by BLI_scanfill_calc_ex(), and testvertexnearedge().

◆ SF_EPSILON_SQ

#define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)

Definition at line 53 of file scanfill.c.

Referenced by testvertexnearedge().

◆ SF_POLY_NEW

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

PolyFill::f (status)

Definition at line 68 of file scanfill.c.

Referenced by BLI_scanfill_calc_ex(), and scanfill().

◆ SF_POLY_VALID

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

Definition at line 69 of file scanfill.c.

Referenced by BLI_scanfill_calc_ex().

◆ SF_VERT_AVAILABLE

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

Definition at line 57 of file scanfill.c.

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 56 of file scanfill.c.

Referenced by BLI_scanfill_vert_add(), and scanfill().

◆ SF_VERT_ZERO_LEN

#define SF_VERT_ZERO_LEN 2

Definition at line 58 of file scanfill.c.

Referenced by scanfill().

Typedef Documentation

◆ PolyFill

typedef struct PolyFill PolyFill

◆ ScanFillVertLink

typedef struct ScanFillVertLink ScanFillVertLink

Function Documentation

◆ addedgetoscanlist()

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

static

Definition at line 314 of file scanfill.c.

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

Referenced by scanfill().

◆ addedgetoscanvert()

static bool addedgetoscanvert	(	ScanFillVertLink *	sc,
		ScanFillEdge *	eed )

static

Definition at line 263 of file scanfill.c.

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

Referenced by addedgetoscanlist().

◆ addfillface()

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

static

Definition at line 136 of file scanfill.c.

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 791 of file scanfill.c.

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 798 of file scanfill.c.

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 1152 of file scanfill.c.

References BLI_scanfill_calc_ex(), flag, and NULL.

◆ BLI_scanfill_calc_ex()

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

Definition at line 825 of file scanfill.c.

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, ScanFillVert::co, compare_v3v3(), copy_v3_v3(), ScanFillVert::edge_count, PolyFill::edges, PolyFill::f, ScanFillVert::f, fill_target_map_recursive(), ScanFillContext::filledgebase, ScanFillContext::fillvertbase, ListBase::first, flag, ListBase::last, len_squared_v3(), LIKELY, PolyFill::max_xy, MEM_freeN(), MEM_mallocN, mergepolysSimp(), PolyFill::min_xy, mul_v2_m3v3(), ScanFillEdge::next, ScanFillVert::next, normalize_v3(), NULL, 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, PolyFill::verts, ScanFillVert::xy, 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 117 of file scanfill.c.

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 805 of file scanfill.c.

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

Referenced by bmo_triangle_fill_exec().

◆ BLI_scanfill_end_arena()

void BLI_scanfill_end_arena	(	ScanFillContext *	sf_ctx,
		MemArena *	arena )

Definition at line 815 of file scanfill.c.

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

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

static

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

Definition at line 351 of file scanfill.c.

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

Referenced by testvertexnearedge().

◆ boundisect()

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

static

Definition at line 152 of file scanfill.c.

References PolyFill::edges, PolyFill::max_xy, PolyFill::min_xy, and pf2.

Referenced by fill_target_map_recursive().

◆ fill_target_map_recursive()

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 )