Blender V5.3
polyfill_2d.cc File Reference
#include "BLI_utildefines.hh"
#include <algorithm>
#include <cstdlib>
#include "MEM_guardedalloc.h"
#include "BLI_alloca.hh"
#include "BLI_enum_flags.hh"
#include "BLI_math_geom_c.hh"
#include "BLI_math_vector_c.hh"
#include "BLI_memarena.hh"
#include "BLI_polyfill_2d.hh"
#include "BLI_strict_flags.hh"

Go to the source code of this file.

Classes

struct  blender::TriIsectPrecomputed

Namespaces

namespace  blender
 BMesh Iterators.

Macros

#define USE_CLIP_EVEN
#define USE_CONVEX_SKIP
#define USE_CLIP_SWEEP
#define USE_KDTREE
#define USE_KDTREE_INDEX_CACHE
#define KDTREE_INDEX_CACHE_UNSET   uint32_t(-1)
#define USE_PRECOMPUTED_ISECT
#define KDNODE_UNSET   (uint32_t(-1))
#define KDTREE2D_ISECT_ARGS   tree, tri_index, tri_isect, tri_center, bounds
#define KDTREE2D_ISECT_TRI_RECURSE_NEG
#define KDTREE2D_ISECT_TRI_RECURSE_POS

Enumerations

enum  { blender::KDNODE_FLAG_REMOVED = (1 << 0) }

Functions

static void blender::tri_isect_precomputed_init (TriIsectPrecomputed *t, const float *const vs[3])
static bool blender::tri_isect_precomputed_test (const TriIsectPrecomputed *t, const float co[2])
static void blender::pf_coord_sign_calc (const PolyFill *pf, PolyIndex *pi)
static PolyIndex * blender::pf_ear_tip_find (PolyFill *pf, PolyIndex *pi_ear_init, bool reverse)
static bool blender::pf_ear_tip_check (PolyFill *pf, PolyIndex *pi_ear_tip, const eSign sign_accept)
static void blender::pf_ear_tip_cut (PolyFill *pf, PolyIndex *pi_ear_tip)
BLI_INLINE eSign blender::signum_enum (float a)
BLI_INLINE float blender::area_tri_signed_v2_alt_2x (const float v1[2], const float v2[2], const float v3[2])
static eSign blender::span_tri_v2_sign (const float v1[2], const float v2[2], const float v3[2])
static void blender::kdtree2d_new (KDTree2D *tree, uint32_t tot, const float(*coords)[2])
static void blender::kdtree2d_init (KDTree2D *tree, const uint32_t coords_num, const PolyIndex *indices)
static uint32_t blender::kdtree2d_balance_recursive (KDTreeNode2D *nodes, uint32_t node_num, axis_t axis, const float(*coords)[2], const uint32_t ofs)
static void blender::kdtree2d_balance (KDTree2D *tree)
static void blender::kdtree2d_init_mapping (KDTree2D *tree)
static void blender::kdtree2d_node_remove (KDTree2D *tree, uint32_t index)
static uint32_t blender::kdtree2d_isect_tri_recursive (const KDTree2D *tree, const uint32_t tri_index[3], const TriIsectPrecomputed *tri_isect, const float tri_center[2], const KDRange2D bounds[2], const KDTreeNode2D *node)
static bool blender::kdtree2d_isect_tri_single (const KDTree2D *tree, const uint32_t tri_index[3], const uint32_t test_index)
static uint32_t blender::kdtree2d_isect_tri (KDTree2D *tree, const uint32_t ind[3])
static uint32_t * blender::pf_tri_add (PolyFill *pf)
static void blender::pf_coord_remove (PolyFill *pf, PolyIndex *pi)
static void blender::pf_triangulate (PolyFill *pf)
static void blender::polyfill_prepare (PolyFill *pf, const float(*coords)[2], const uint32_t coords_num, int coords_sign, uint32_t(*r_tris)[3], PolyIndex *r_indices)
static void blender::polyfill_calc (PolyFill *pf)
void blender::BLI_polyfill_calc_arena (const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
void blender::BLI_polyfill_calc (const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])

Detailed Description

An ear clipping algorithm to triangulate single boundary polygons.

Details:

  • The algorithm guarantees all triangles are assigned (number of coords - 2) and that triangles will have non-overlapping indices (even for degenerate geometry).
  • Self-intersections are considered degenerate (resulting triangles will overlap).
  • While multiple polygons aren't supported, holes can still be defined using key-holes (where the polygon doubles back on itself with exactly matching coordinates).
Note

Changes made for Blender.

  • loop the array to clip last verts first (less array resizing)
  • advance the ear to clip each iteration to avoid fan-filling convex shapes (USE_CLIP_EVEN).
  • avoid intersection tests when there are no convex points (USE_CONVEX_SKIP).
Note

No globals - keep threadsafe.

Definition in file polyfill_2d.cc.

Macro Definition Documentation

◆ KDNODE_UNSET

◆ KDTREE2D_ISECT_ARGS

#define KDTREE2D_ISECT_ARGS   tree, tri_index, tri_isect, tri_center, bounds

◆ KDTREE2D_ISECT_TRI_RECURSE_NEG

#define KDTREE2D_ISECT_TRI_RECURSE_NEG
Value:
(((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) ? \
kdtree2d_isect_tri_recursive(KDTREE2D_ISECT_ARGS, &tree->nodes[node->neg]) : \
#define KDNODE_UNSET
#define KDTREE2D_ISECT_ARGS

Referenced by blender::kdtree2d_isect_tri_recursive().

◆ KDTREE2D_ISECT_TRI_RECURSE_POS

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

Referenced by blender::kdtree2d_isect_tri_recursive().

◆ KDTREE_INDEX_CACHE_UNSET

#define KDTREE_INDEX_CACHE_UNSET   uint32_t(-1)

Definition at line 68 of file polyfill_2d.cc.

Referenced by blender::pf_ear_tip_check(), and blender::polyfill_prepare().

◆ USE_CLIP_EVEN

#define USE_CLIP_EVEN

Definition at line 54 of file polyfill_2d.cc.

Referenced by blender::pf_ear_tip_find(), and blender::pf_triangulate().

◆ USE_CLIP_SWEEP

#define USE_CLIP_SWEEP

Definition at line 57 of file polyfill_2d.cc.

Referenced by blender::pf_ear_tip_find(), and blender::pf_triangulate().

◆ USE_CONVEX_SKIP

#define USE_CONVEX_SKIP

Definition at line 55 of file polyfill_2d.cc.

◆ USE_KDTREE

#define USE_KDTREE

Definition at line 61 of file polyfill_2d.cc.

◆ USE_KDTREE_INDEX_CACHE

#define USE_KDTREE_INDEX_CACHE

Cache the last hit vertex index to avoid repeated KDTree lookups.

Definition at line 66 of file polyfill_2d.cc.

◆ USE_PRECOMPUTED_ISECT

#define USE_PRECOMPUTED_ISECT

Precompute edge vectors for point-in-triangle test.

Definition at line 71 of file polyfill_2d.cc.

Referenced by blender::kdtree2d_isect_tri(), and blender::kdtree2d_isect_tri_recursive().