scanfill.c File Reference

#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.h"
#include "BLI_memarena.h"
#include "BLI_utildefines.h"
#include "BLI_scanfill.h"
#include "BLI_strict_flags.h"

Go to the source code of this file.

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)
static int	vergpoly (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 (PolyFill *pf2, PolyFill *pf1)
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, unsigned int len)
static bool	boundinsideEV (ScanFillEdge *eed, ScanFillVert *eve)
static void	testvertexnearedge (ScanFillContext *sf_ctx)
static void	splitlist (ScanFillContext *sf_ctx, ListBase *tempve, ListBase *temped, unsigned short nr)
static unsigned int	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)
unsigned int	BLI_scanfill_calc_ex (ScanFillContext *sf_ctx, const int flag, const float nor_proj[3])
unsigned int	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 79 of file scanfill.c.

SF_EDGE_NEW

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

Definition at line 77 of file scanfill.c.

SF_EPSILON

#define SF_EPSILON   0.00003f

Definition at line 66 of file scanfill.c.

SF_EPSILON_SQ

#define SF_EPSILON_SQ   (SF_EPSILON * SF_EPSILON)

Definition at line 67 of file scanfill.c.

SF_POLY_NEW

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

Definition at line 82 of file scanfill.c.

SF_POLY_VALID

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

Definition at line 83 of file scanfill.c.

SF_VERT_AVAILABLE

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

Definition at line 71 of file scanfill.c.

SF_VERT_NEW

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

Definition at line 70 of file scanfill.c.

SF_VERT_ZERO_LEN

#define SF_VERT_ZERO_LEN   2

Definition at line 72 of file scanfill.c.

Typedef Documentation

PolyFill

typedef struct PolyFill PolyFill

ScanFillVertLink

typedef struct ScanFillVertLink ScanFillVertLink

Function Documentation

addedgetoscanlist()

static ScanFillVertLink* addedgetoscanlist ( ScanFillVertLink *  scdata, ScanFillEdge *  eed, unsigned int  len  )

static

Definition at line 324 of file scanfill.c.

References addedgetoscanvert(), len, NULL, 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 273 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 170 of file scanfill.c.

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

Referenced by scanfill().

BLI_scanfill_begin()

void BLI_scanfill_begin

(

ScanFillContext *

sf_ctx

)

Definition at line 794 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 801 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()

unsigned int BLI_scanfill_calc	(	ScanFillContext *	sf_ctx,
		const int	flag
	)

Definition at line 1160 of file scanfill.c.

References BLI_scanfill_calc_ex(), and NULL.

BLI_scanfill_calc_ex()

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

Definition at line 828 of file scanfill.c.

References Freestyle::a, 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, boundisect(), Freestyle::c, ScanFillVert::co, compare_v3v3(), copy_v3_v3(), ScanFillVert::edge_tot, PolyFill::edges, ScanFillVert::f, PolyFill::f, ScanFillContext::filledgebase, ScanFillContext::fillvertbase, ListBase::first, if(), ListBase::last, len_squared_v3(), LIKELY, PolyFill::max_xy, MEM_callocN, MEM_freeN, MEM_mallocN, mergepolysSimp(), PolyFill::min_xy, mul_v2_m3v3(), ScanFillVert::next, ScanFillEdge::next, normalize_v3(), NULL, pf, ScanFillContext::poly_nr, ScanFillVert::poly_nr, ScanFillEdge::poly_nr, ScanFillEdge::prev, scanfill(), SF_EPSILON, SF_POLY_NEW, SF_POLY_UNSET, SF_POLY_VALID, SF_VERT_AVAILABLE, splitlist(), testvertexnearedge(), UNLIKELY, ScanFillEdge::v1, ScanFillEdge::v2, vergpoly(), 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 151 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, 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 808 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 818 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]
	)

Definition at line 129 of file scanfill.c.

References ScanFillContext::arena, BLI_addtail(), BLI_memarena_alloc(), ScanFillVert::co, copy_v3_v3(), ScanFillVert::edge_tot, ScanFillVert::f, ScanFillContext::fillvertbase, ScanFillVert::keyindex, NULL, ScanFillVert::p, ScanFillContext::poly_nr, ScanFillVert::poly_nr, SF_VERT_NEW, ScanFillVert::tmp, ScanFillVert::user_flag, ScanFillVert::xy, and zero_v2().

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

boundinsideEV()

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

static

Definition at line 360 of file scanfill.c.

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

Referenced by testvertexnearedge().

boundisect()

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

static

Definition at line 186 of file scanfill.c.

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

Referenced by BLI_scanfill_calc_ex().

mergepolysSimp()

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

static

Definition at line 228 of file scanfill.c.

References PolyFill::edges, PolyFill::f, ScanFillContext::filledgebase, ScanFillContext::fillvertbase, ListBase::first, ScanFillVert::next, ScanFillEdge::next, PolyFill::nr, pf2, ScanFillVert::poly_nr, ScanFillEdge::poly_nr, and PolyFill::verts.

Referenced by BLI_scanfill_calc_ex().

scanfill()

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

static

Definition at line 475 of file scanfill.c.

References Freestyle::a, addedgetoscanlist(), addfillface(), BLI_addtail(), BLI_assert, BLI_insertlinkbefore(), BLI_remlink(), BLI_SCANFILL_CALC_HOLES, BLI_SCANFILL_CALC_REMOVE_DOUBLES, BLI_scanfill_edge_add(), cos_v2v2v2(), ScanFillVertLink::edge_first, ScanFillVertLink::edge_last, ScanFillVert::edge_tot, equals_v2v2(), ScanFillVert::f, ScanFillEdge::f, ScanFillContext::filledgebase, ScanFillContext::fillvertbase, ListBase::first, MEM_freeN, MEM_mallocN, min_ff(), ScanFillVert::next, ScanFillEdge::next, NULL, pf, ScanFillVert::poly_nr, SF_EDGE_INTERNAL, SF_EDGE_NEW, SF_POLY_NEW, SF_VERT_AVAILABLE, SF_VERT_NEW, SF_VERT_ZERO_LEN, testedgeside(), ScanFillVert::tmp, ScanFillVert::v, ScanFillEdge::v1, v1, ScanFillEdge::v2, v2, vergscdata(), ScanFillVertLink::vert, verts, and ScanFillVert::xy.

Referenced by BLI_scanfill_calc_ex().

splitlist()

static void splitlist ( ScanFillContext *  sf_ctx, ListBase *  tempve, ListBase *  temped, unsigned short  nr  )

static

Definition at line 446 of file scanfill.c.

References BLI_addtail(), BLI_movelisttolist(), BLI_remlink(), ScanFillContext::filledgebase, ScanFillContext::fillvertbase, ListBase::first, ScanFillVert::next, ScanFillEdge::next, ScanFillVert::poly_nr, and ScanFillEdge::poly_nr.

Referenced by BLI_scanfill_calc_ex().

testedgeside()

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

static

Definition at line 252 of file scanfill.c.

References v1, and v2.

Referenced by scanfill().

testvertexnearedge()

static void testvertexnearedge ( ScanFillContext *  sf_ctx )

static

Definition at line 389 of file scanfill.c.

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

Referenced by BLI_scanfill_calc_ex().

vergpoly()

static int vergpoly ( const void *  a1, const void *  a2  )

static

Definition at line 107 of file scanfill.c.

References PolyFill::min_xy, and x2.

Referenced by BLI_scanfill_calc_ex().

vergscdata()

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

static

Definition at line 87 of file scanfill.c.

References ScanFillVertLink::vert, x2, and ScanFillVert::xy.

Referenced by addedgetoscanlist(), and scanfill().