Blender  V3.3
Classes | Macros | Typedefs | Functions
scanfill.c File Reference
Blender » BlenLib
#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 62 of file scanfill.c.

◆ SF_EDGE_NEW

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

#ScanFillEdge.status

Definition at line 60 of file scanfill.c.

◆ SF_EPSILON

#define SF_EPSILON   0.00003f

Definition at line 49 of file scanfill.c.

◆ SF_EPSILON_SQ

#define SF_EPSILON_SQ   (SF_EPSILON * SF_EPSILON)

Definition at line 50 of file scanfill.c.

◆ SF_POLY_NEW

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

#PolyFill.status

Definition at line 65 of file scanfill.c.

◆ SF_POLY_VALID

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

Definition at line 66 of file scanfill.c.

◆ SF_VERT_AVAILABLE

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

Definition at line 54 of file scanfill.c.

◆ SF_VERT_NEW

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

#ScanFillVert.status

Definition at line 53 of file scanfill.c.

◆ SF_VERT_ZERO_LEN

#define SF_VERT_ZERO_LEN   2

Definition at line 55 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 307 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 256 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 153 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 779 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 786 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 1145 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 813 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_count, 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 134 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 793 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 803 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 112 of file scanfill.c.

References ScanFillContext::arena, BLI_addtail(), BLI_memarena_alloc(), ScanFillVert::co, copy_v3_v3(), ScanFillVert::edge_count, 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(), bmo_triangle_fill_exec(), scanfill_preprocess_self_isect(), and scanfill_vert_add_v2_with_depth().

◆ boundinsideEV()

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

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

Definition at line 346 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 169 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 211 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 460 of file scanfill.c.

References Freestyle::a, addedgetoscanlist(), addfillface(), usdtokens::b(), BLI_addtail(), BLI_assert, BLI_insertlinkbefore(), BLI_remlink(), BLI_SCANFILL_CALC_HOLES, BLI_SCANFILL_CALC_REMOVE_DOUBLES, BLI_scanfill_edge_add(), cos_v2v2v2(), ScanFillVert::edge_count, ScanFillVertLink::edge_first, ScanFillVertLink::edge_last, 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 431 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 235 of file scanfill.c.

References v1, and v2.

Referenced by scanfill().

◆ testvertexnearedge()

static void testvertexnearedge ( ScanFillContext *  sf_ctx)
static

Definition at line 374 of file scanfill.c.

References BLI_scanfill_edge_add(), boundinsideEV(), compare_v2v2(), dist_squared_to_line_v2(), ScanFillVert::edge_count, 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 90 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 70 of file scanfill.c.

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

Referenced by addedgetoscanlist(), and scanfill().

Generated on Tue Oct 22 2024 13:18:25 for Blender by  doxygen 1.9.1