Blender
V3.3
|
#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 |
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 PolyIndex * | pf_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 uint * | pf_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]) |
An ear clipping algorithm to triangulate single boundary polygons.
Details:
Changes made for Blender.
No globals - keep threadsafe.
Definition in file polyfill_2d.c.
Definition at line 193 of file polyfill_2d.c.
#define KDTREE2D_ISECT_TRI_RECURSE_NEG |
#define KDTREE2D_ISECT_TRI_RECURSE_POS |
#define USE_CLIP_EVEN |
Definition at line 43 of file polyfill_2d.c.
#define USE_CLIP_SWEEP |
Definition at line 46 of file polyfill_2d.c.
#define USE_CONVEX_SKIP |
Definition at line 44 of file polyfill_2d.c.
#define USE_KDTREE |
Definition at line 50 of file polyfill_2d.c.
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.
Definition at line 83 of file polyfill_2d.c.
typedef signed char eSign |
Definition at line 61 of file polyfill_2d.c.
typedef struct KDTreeNode2D KDTreeNode2D |
typedef struct KDTreeNode2D_head KDTreeNode2D_head |
anonymous enum |
Enumerator | |
---|---|
CONCAVE | |
TANGENTIAL | |
CONVEX |
Definition at line 112 of file polyfill_2d.c.
anonymous enum |
Enumerator | |
---|---|
KDNODE_FLAG_REMOVED |
Definition at line 195 of file polyfill_2d.c.
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
Definition at line 179 of file polyfill_2d.c.
References sub_v2_v2v2(), v1, and v2.
Referenced by span_tri_v2_sign().
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.
coords | 2D coordinates describing vertices of the polygon, in either clockwise or counterclockwise order. |
coords_num | Total points in the array. |
coords_sign | Pass this when we know the sign in advance to avoid extra calculations. |
r_tris | This 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().
void BLI_polyfill_calc_arena | ( | const float(*) | coords[2], |
unsigned int | coords_num, | ||
int | coords_sign, | ||
unsigned int(*) | r_tris[3], | ||
struct MemArena * | arena | ||
) |
A version of BLI_polyfill_calc that uses a memory arena to avoid re-allocations.
Definition at line 830 of file polyfill_2d.c.
References BLI_memarena_alloc(), indices, pf, polyfill_calc(), polyfill_prepare(), TIMEIT_END, and TIMEIT_START.
Referenced by BLI_polyfill_calc(), BM_face_triangulate(), bmesh_calc_tessellation_for_face_beauty(), bmesh_calc_tessellation_for_face_impl(), C_BVHTree_FromPolygons(), mesh_calc_tessellation_for_face_impl(), mesh_tessface_calc(), and p_add_ngon().
Definition at line 284 of file polyfill_2d.c.
References kdtree2d_balance_recursive(), and tree.
Referenced by polyfill_calc().
|
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().
|
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().
Definition at line 289 of file polyfill_2d.c.
References BLI_assert, KDNODE_UNSET, node, and tree.
Referenced by polyfill_calc().
Definition at line 408 of file polyfill_2d.c.
References add_v2_v2(), bounds(), CLAMP_MAX, CLAMP_MIN, kdtree2d_isect_tri_recursive(), max, min, mul_v2_fl(), and tree.
Referenced by pf_ear_tip_check().
|
static |
Definition at line 350 of file polyfill_2d.c.
References BLI_assert, bounds(), CONCAVE, ELEM, KDNODE_FLAG_REMOVED, KDNODE_UNSET, KDTREE2D_ISECT_TRI_RECURSE_NEG, KDTREE2D_ISECT_TRI_RECURSE_POS, max, min, node, span_tri_v2_sign(), and tree.
Referenced by kdtree2d_isect_tri().
Definition at line 199 of file polyfill_2d.c.
References KDNODE_UNSET, and tree.
Referenced by polyfill_calc().
Definition at line 310 of file polyfill_2d.c.
References BLI_assert, KDTreeNode2D::flag, PolyIndex::index, KDNODE_FLAG_REMOVED, KDNODE_UNSET, KDTreeNode2D::neg, node, KDTreeNode2D::pos, and tree.
Referenced by pf_coord_remove(), and pf_triangulate().
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().
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().
Definition at line 641 of file polyfill_2d.c.
References BLI_assert, CONCAVE, CONVEX, float(), PolyIndex::index, kdtree2d_isect_tri(), PolyIndex::next, pf, PolyIndex::prev, PolyIndex::sign, span_tri_v2_sign(), UNLIKELY, v, v1, and v2.
Referenced by pf_ear_tip_find().
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().
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().
Definition at line 436 of file polyfill_2d.c.
References pf.
Referenced by pf_ear_tip_cut(), and pf_triangulate().
Definition at line 464 of file polyfill_2d.c.
References CONVEX, PolyIndex::index, kdtree2d_node_remove(), PolyIndex::next, pf, pf_coord_sign_calc(), pf_ear_tip_cut(), pf_ear_tip_find(), pf_tri_add(), PolyIndex::prev, PolyIndex::sign, USE_CLIP_EVEN, and USE_CLIP_SWEEP.
Referenced by polyfill_calc().
Definition at line 813 of file polyfill_2d.c.
References kdtree2d_balance(), kdtree2d_init(), kdtree2d_init_mapping(), kdtree2d_new(), pf, and pf_triangulate().
Referenced by BLI_polyfill_calc(), and BLI_polyfill_calc_arena().
|
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().
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().
Definition at line 187 of file polyfill_2d.c.
References area_tri_signed_v2_alt_2x(), signum_enum(), v1, and v2.
Referenced by kdtree2d_isect_tri_recursive(), pf_coord_sign_calc(), and pf_ear_tip_check().