Blender  V3.3
Classes | Macros | Typedefs | Enumerations | Functions
polyfill_2d.c File Reference
#include "BLI_math.h"
#include "BLI_utildefines.h"
#include "BLI_alloca.h"
#include "BLI_memarena.h"
#include "BLI_polyfill_2d.h"
#include "BLI_strict_flags.h"

Go to the source code of this file.

Classes

struct  KDTreeNode2D_head
 
struct  KDTreeNode2D
 
struct  KDTree2D
 
struct  KDRange2D
 
struct  PolyFill
 
struct  PolyIndex
 

Macros

#define USE_CLIP_EVEN
 
#define USE_CONVEX_SKIP
 
#define USE_CLIP_SWEEP
 
#define USE_KDTREE
 
#define KDNODE_UNSET   ((uint)-1)
 
#define KDTREE2D_ISECT_TRI_RECURSE_NEG
 
#define KDTREE2D_ISECT_TRI_RECURSE_POS
 

Typedefs

typedef signed char eSign
 
typedef bool axis_t
 
typedef struct KDTreeNode2D_head KDTreeNode2D_head
 
typedef struct KDTreeNode2D KDTreeNode2D
 
typedef struct PolyFill PolyFill
 
typedef struct PolyIndex PolyIndex
 

Enumerations

enum  { CONCAVE = -1 , TANGENTIAL = 0 , CONVEX = 1 }
 
enum  { KDNODE_FLAG_REMOVED = (1 << 0) }
 

Functions

static void pf_coord_sign_calc (PolyFill *pf, PolyIndex *pi)
 
static PolyIndexpf_ear_tip_find (PolyFill *pf, PolyIndex *pi_ear_init, bool reverse)
 
static bool pf_ear_tip_check (PolyFill *pf, PolyIndex *pi_ear_tip)
 
static void pf_ear_tip_cut (PolyFill *pf, PolyIndex *pi_ear_tip)
 
BLI_INLINE eSign signum_enum (float a)
 
BLI_INLINE float area_tri_signed_v2_alt_2x (const float v1[2], const float v2[2], const float v3[2])
 
static eSign span_tri_v2_sign (const float v1[2], const float v2[2], const float v3[2])
 
static void kdtree2d_new (struct KDTree2D *tree, uint tot, const float(*coords)[2])
 
static void kdtree2d_init (struct KDTree2D *tree, const uint coords_num, const PolyIndex *indices)
 
static uint kdtree2d_balance_recursive (KDTreeNode2D *nodes, uint node_num, axis_t axis, const float(*coords)[2], const uint ofs)
 
static void kdtree2d_balance (struct KDTree2D *tree)
 
static void kdtree2d_init_mapping (struct KDTree2D *tree)
 
static void kdtree2d_node_remove (struct KDTree2D *tree, uint index)
 
static bool kdtree2d_isect_tri_recursive (const struct KDTree2D *tree, const uint tri_index[3], const float *tri_coords[3], const float tri_center[2], const struct KDRange2D bounds[2], const KDTreeNode2D *node)
 
static bool kdtree2d_isect_tri (struct KDTree2D *tree, const uint ind[3])
 
static uintpf_tri_add (PolyFill *pf)
 
static void pf_coord_remove (PolyFill *pf, PolyIndex *pi)
 
static void pf_triangulate (PolyFill *pf)
 
static void polyfill_prepare (PolyFill *pf, const float(*coords)[2], const uint coords_num, int coords_sign, uint(*r_tris)[3], PolyIndex *r_indices)
 
static void polyfill_calc (PolyFill *pf)
 
void BLI_polyfill_calc_arena (const float(*coords)[2], const uint coords_num, const int coords_sign, uint(*r_tris)[3], struct MemArena *arena)
 
void BLI_polyfill_calc (const float(*coords)[2], const uint coords_num, const int coords_sign, uint(*r_tris)[3])
 

Detailed Description

An ear clipping algorithm to triangulate single boundary polygons.

Details:

Note

Changes made for Blender.

Note

No globals - keep threadsafe.

Definition in file polyfill_2d.c.

Macro Definition Documentation

◆ KDNODE_UNSET

#define KDNODE_UNSET   ((uint)-1)

Definition at line 193 of file polyfill_2d.c.

◆ KDTREE2D_ISECT_TRI_RECURSE_NEG

#define KDTREE2D_ISECT_TRI_RECURSE_NEG
Value:
(((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) && \
tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->neg])))
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
Definition: btDbvt.cpp:299
OperationNode * node
void * tree
static bool kdtree2d_isect_tri_recursive(const struct KDTree2D *tree, const uint tri_index[3], const float *tri_coords[3], const float tri_center[2], const struct KDRange2D bounds[2], const KDTreeNode2D *node)
Definition: polyfill_2d.c:350
#define KDNODE_UNSET
Definition: polyfill_2d.c:193

◆ KDTREE2D_ISECT_TRI_RECURSE_POS

#define KDTREE2D_ISECT_TRI_RECURSE_POS
Value:
(((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) && \
tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->pos])))

◆ USE_CLIP_EVEN

#define USE_CLIP_EVEN

Definition at line 43 of file polyfill_2d.c.

◆ USE_CLIP_SWEEP

#define USE_CLIP_SWEEP

Definition at line 46 of file polyfill_2d.c.

◆ USE_CONVEX_SKIP

#define USE_CONVEX_SKIP

Definition at line 44 of file polyfill_2d.c.

◆ USE_KDTREE

#define USE_KDTREE

Definition at line 50 of file polyfill_2d.c.

Typedef Documentation

◆ axis_t

typedef bool axis_t

Spatial optimization for point-in-triangle intersection checks. The simple version of this algorithm is O(n^2) complexity (every point needing to check the triangle defined by every other point), Using a binary-tree reduces the complexity to O(n log n) plus some overhead of creating the tree.

This is a single purpose KDTree based on BLI_kdtree with some modifications to better suit polyfill2d.

  • KDTreeNode2D is kept small (only 16 bytes), by not storing coords in the nodes and using index values rather than pointers to reference neg/pos values.
  • kdtree2d_isect_tri is the only function currently used. This simply intersects a triangle with the kdtree points.
  • the KDTree is only built & used when the polygon is concave.

Definition at line 83 of file polyfill_2d.c.

◆ eSign

typedef signed char eSign

Definition at line 61 of file polyfill_2d.c.

◆ KDTreeNode2D

typedef struct KDTreeNode2D KDTreeNode2D

◆ KDTreeNode2D_head

◆ PolyFill

typedef struct PolyFill PolyFill

◆ PolyIndex

typedef struct PolyIndex PolyIndex

Circular double linked-list.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
CONCAVE 
TANGENTIAL 
CONVEX 

Definition at line 112 of file polyfill_2d.c.

◆ anonymous enum

anonymous enum
Enumerator
KDNODE_FLAG_REMOVED 

Definition at line 195 of file polyfill_2d.c.

Function Documentation

◆ area_tri_signed_v2_alt_2x()

BLI_INLINE float area_tri_signed_v2_alt_2x ( const float  v1[2],
const float  v2[2],
const float  v3[2] 
)

alternative version of area_tri_signed_v2 needed because of float precision issues

Note
removes / 2 since its not needed since we only need the sign.

Definition at line 179 of file polyfill_2d.c.

References sub_v2_v2v2(), v1, and v2.

Referenced by span_tri_v2_sign().

◆ BLI_polyfill_calc()

void BLI_polyfill_calc ( const float(*)  coords[2],
unsigned int  coords_num,
int  coords_sign,
unsigned int(*)  r_tris[3] 
)

Triangulates the given (convex or concave) simple polygon to a list of triangle vertices.

Parameters
coords2D coordinates describing vertices of the polygon, in either clockwise or counterclockwise order.
coords_numTotal points in the array.
coords_signPass this when we know the sign in advance to avoid extra calculations.
r_trisThis array is filled in with triangle indices in clockwise order. The length of the array must be coords_num - 2. Indices are guaranteed to be assigned to unique triangles, with valid indices, even in the case of degenerate input (self intersecting polygons, zero area ears... etc).

Definition at line 875 of file polyfill_2d.c.

References BLI_array_alloca, BLI_memarena_free(), BLI_memarena_new(), BLI_polyfill_calc_arena(), indices, pf, polyfill_calc(), polyfill_prepare(), TIMEIT_END, TIMEIT_START, and UNLIKELY.

Referenced by BKE_gpencil_stroke_fill_triangulate(), BKE_mesh_remap_calc_polys_from_mesh(), BM_face_calc_tessellation(), gpencil_sbuffer_stroke_ensure(), GPU_batch_tris_from_poly_2d_encoded(), sculpt_gesture_trim_geometry_generate(), test_polyfill_template(), ui_draw_but_CURVEPROFILE(), and uv_select_overlap().

◆ BLI_polyfill_calc_arena()

void BLI_polyfill_calc_arena ( const float(*)  coords[2],
unsigned int  coords_num,
int  coords_sign,
unsigned int(*)  r_tris[3],
struct MemArena arena 
)

◆ kdtree2d_balance()

static void kdtree2d_balance ( struct KDTree2D tree)
static

Definition at line 284 of file polyfill_2d.c.

References kdtree2d_balance_recursive(), and tree.

Referenced by polyfill_calc().

◆ kdtree2d_balance_recursive()

static uint kdtree2d_balance_recursive ( KDTreeNode2D nodes,
uint  node_num,
axis_t  axis,
const float(*)  coords[2],
const uint  ofs 
)
static

Definition at line 229 of file polyfill_2d.c.

References KDTreeNode2D::index, PolyIndex::index, KDNODE_UNSET, node, pos, and SWAP.

Referenced by kdtree2d_balance().

◆ kdtree2d_init()

static void kdtree2d_init ( struct KDTree2D tree,
const uint  coords_num,
const PolyIndex indices 
)
static

no need for kdtree2d_insert, since we know the coords array.

Definition at line 211 of file polyfill_2d.c.

References BLI_assert, CONVEX, indices, KDNODE_UNSET, node, KDL::sign(), and tree.

Referenced by polyfill_calc().

◆ kdtree2d_init_mapping()

static void kdtree2d_init_mapping ( struct KDTree2D tree)
static

Definition at line 289 of file polyfill_2d.c.

References BLI_assert, KDNODE_UNSET, node, and tree.

Referenced by polyfill_calc().

◆ kdtree2d_isect_tri()

static bool kdtree2d_isect_tri ( struct KDTree2D tree,
const uint  ind[3] 
)
static

◆ kdtree2d_isect_tri_recursive()

static bool kdtree2d_isect_tri_recursive ( const struct KDTree2D tree,
const uint  tri_index[3],
const float tri_coords[3],
const float  tri_center[2],
const struct KDRange2D  bounds[2],
const KDTreeNode2D node 
)
static

◆ kdtree2d_new()

static void kdtree2d_new ( struct KDTree2D tree,
uint  tot,
const float(*)  coords[2] 
)
static

Definition at line 199 of file polyfill_2d.c.

References KDNODE_UNSET, and tree.

Referenced by polyfill_calc().

◆ kdtree2d_node_remove()

static void kdtree2d_node_remove ( struct KDTree2D tree,
uint  index 
)
static

◆ pf_coord_remove()

static void pf_coord_remove ( PolyFill pf,
PolyIndex pi 
)
static

Definition at line 441 of file polyfill_2d.c.

References PolyIndex::index, kdtree2d_node_remove(), PolyIndex::next, NULL, pf, PolyIndex::prev, and UNLIKELY.

Referenced by pf_ear_tip_cut().

◆ pf_coord_sign_calc()

static void pf_coord_sign_calc ( PolyFill pf,
PolyIndex pi 
)
static
Returns
CONCAVE, TANGENTIAL or CONVEX

Definition at line 568 of file polyfill_2d.c.

References float(), PolyIndex::index, PolyIndex::next, pf, PolyIndex::prev, PolyIndex::sign, and span_tri_v2_sign().

Referenced by pf_triangulate(), and polyfill_prepare().

◆ pf_ear_tip_check()

static bool pf_ear_tip_check ( PolyFill pf,
PolyIndex pi_ear_tip 
)
static

◆ pf_ear_tip_cut()

static void pf_ear_tip_cut ( PolyFill pf,
PolyIndex pi_ear_tip 
)
static

Definition at line 730 of file polyfill_2d.c.

References PolyIndex::index, PolyIndex::next, pf, pf_coord_remove(), pf_tri_add(), and PolyIndex::prev.

Referenced by pf_triangulate().

◆ pf_ear_tip_find()

static PolyIndex * pf_ear_tip_find ( PolyFill pf,
PolyIndex pi_ear_init,
bool  reverse 
)
static

Definition at line 576 of file polyfill_2d.c.

References CONCAVE, PolyIndex::next, pf, pf_ear_tip_check(), PolyIndex::prev, and PolyIndex::sign.

Referenced by pf_triangulate().

◆ pf_tri_add()

static uint* pf_tri_add ( PolyFill pf)
static

Definition at line 436 of file polyfill_2d.c.

References pf.

Referenced by pf_ear_tip_cut(), and pf_triangulate().

◆ pf_triangulate()

static void pf_triangulate ( PolyFill pf)
static

◆ polyfill_calc()

static void polyfill_calc ( PolyFill pf)
static

◆ polyfill_prepare()

static void polyfill_prepare ( PolyFill pf,
const float(*)  coords[2],
const uint  coords_num,
int  coords_sign,
uint(*)  r_tris[3],
PolyIndex r_indices 
)
static

Initializes the PolyFill structure before tessellating with polyfill_calc.

Definition at line 744 of file polyfill_2d.c.

References BLI_assert, CONVEX, cross_poly_v2(), indices, pf, pf_coord_sign_calc(), and PolyIndex::sign.

Referenced by BLI_polyfill_calc(), and BLI_polyfill_calc_arena().

◆ signum_enum()

BLI_INLINE eSign signum_enum ( float  a)

Definition at line 161 of file polyfill_2d.c.

References Freestyle::a, and UNLIKELY.

Referenced by span_tri_v2_sign().

◆ span_tri_v2_sign()

static eSign span_tri_v2_sign ( const float  v1[2],
const float  v2[2],
const float  v3[2] 
)
static