Blender  V3.3
Classes | Macros | Typedefs | Functions
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)
 
ScanFillVertBLI_scanfill_vert_add (ScanFillContext *sf_ctx, const float vec[3])
 
ScanFillEdgeBLI_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 ScanFillVertLinkaddedgetoscanlist (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

Function Documentation

◆ addedgetoscanlist()

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

◆ addedgetoscanvert()

static bool addedgetoscanvert ( ScanFillVertLink sc,
ScanFillEdge eed 
)
static

◆ addfillface()

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

◆ BLI_scanfill_begin()

void BLI_scanfill_begin ( ScanFillContext sf_ctx)

◆ BLI_scanfill_begin_arena()

void BLI_scanfill_begin_arena ( ScanFillContext sf_ctx,
MemArena arena 
)

◆ 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] 
)

◆ BLI_scanfill_edge_add()

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

◆ BLI_scanfill_end()

void BLI_scanfill_end ( ScanFillContext sf_ctx)

◆ BLI_scanfill_end_arena()

void BLI_scanfill_end_arena ( ScanFillContext sf_ctx,
MemArena arena 
)

◆ BLI_scanfill_vert_add()

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

◆ 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

◆ scanfill()

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

◆ splitlist()

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

◆ 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

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