55#define USE_CONVEX_SKIP
66# define USE_KDTREE_INDEX_CACHE
67# ifdef USE_KDTREE_INDEX_CACHE
68# define KDTREE_INDEX_CACHE_UNSET uint32_t(-1)
71# define USE_PRECOMPUTED_ISECT
109struct KDTreeNode2D_head {
124 const float (*coords)[2];
141#ifdef USE_KDTREE_INDEX_CACHE
142enum class PolyIndexFlag :
uint8_t {
147 IndexCacheDirty = 1 << 0,
154 PolyIndex *next, *prev;
157#ifdef USE_KDTREE_INDEX_CACHE
167 const float (*coords)[2];
169#ifdef USE_CONVEX_SKIP
184#ifdef USE_PRECOMPUTED_ISECT
204 t->
c[0] = (t->
edge[0][0] * vs[0][1]) - (vs[0][0] * t->
edge[0][1]);
205 t->
c[1] = (t->
edge[1][0] * vs[1][1]) - (vs[1][0] * t->
edge[1][1]);
206 t->
c[2] = (t->
edge[2][0] * vs[2][1]) - (vs[2][0] * t->
edge[2][1]);
217 return ((t->
edge[1][1] * co[0]) - (t->
edge[1][0] * co[1]) + t->
c[1] >= 0.0f) &&
218 ((t->
edge[2][1] * co[0]) - (t->
edge[2][0] * co[1]) + t->
c[2] >= 0.0f) &&
219 ((t->
edge[0][1] * co[0]) - (t->
edge[0][0] * co[1]) + t->
c[0] >= 0.0f);
230 PolyIndex *pi_ear_init
238static bool pf_ear_tip_check(PolyFill *
pf, PolyIndex *pi_ear_tip,
const eSign sign_accept);
246 if (a == 0.0f) [[unlikely]] {
263 return (d2[0] * d3[1]) - (d3[0] * d2[1]);
272# define KDNODE_UNSET (uint32_t(-1))
282 tree->coords = coords;
284 tree->node_num = tot;
295 for (i = 0,
node = tree->nodes; i < coords_num; i++) {
296 if (indices[i].
sign != CONVEX) {
298 node->index = indices[i].index;
311 const float (*coords)[2],
327 median = node_num / 2;
330 const float co = coords[
nodes[pos].index][axis];
337 while (coords[
nodes[--j].
index][axis] > co && j > neg) {
343 SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&
nodes[i], *(KDTreeNode2D_head *)&
nodes[j]);
346 SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&
nodes[i], *(KDTreeNode2D_head *)&
nodes[pos]);
361 &
nodes[median + 1], (node_num - (median + 1)), axis, coords, (median + 1) + ofs);
376 for (i = 0,
node = tree->nodes; i < tree->node_num; i++,
node++) {
378 tree->nodes[
node->neg].parent = i;
381 tree->nodes[
node->pos].parent = i;
386 tree->nodes_map[
node->index] = i;
403 node = &tree->nodes[node_index];
421 node_child =
node->pos;
424 node_child =
node->neg;
436 KDTreeNode2D *node_parent = &tree->nodes[
node->parent];
437 if (node_parent->neg == node_index) {
438 node_parent->neg = node_child;
442 node_parent->pos = node_child;
446 tree->nodes[node_child].parent =
node->parent;
452 node_index =
node->parent;
465 const float *tri_coords[3],
467 const float tri_center[2],
468 const KDRange2D
bounds[2],
469 const KDTreeNode2D *
node)
471 const float *co = tree->coords[
node->index];
474# ifdef USE_PRECOMPUTED_ISECT
484 if (!
ELEM(
node->index, tri_index[0], tri_index[1], tri_index[2])) {
490# ifdef USE_PRECOMPUTED_ISECT
491# define KDTREE2D_ISECT_ARGS tree, tri_index, tri_isect, tri_center, bounds
493# define KDTREE2D_ISECT_ARGS tree, tri_index, tri_coords, tri_center, bounds
496# define KDTREE2D_ISECT_TRI_RECURSE_NEG \
497 (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) ? \
498 kdtree2d_isect_tri_recursive(KDTREE2D_ISECT_ARGS, &tree->nodes[node->neg]) : \
500# define KDTREE2D_ISECT_TRI_RECURSE_POS \
501 (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) ? \
502 kdtree2d_isect_tri_recursive(KDTREE2D_ISECT_ARGS, &tree->nodes[node->pos]) : \
506 if (tri_center[
node->axis] > co[
node->axis]) {
519# undef KDTREE2D_ISECT_TRI_RECURSE_NEG
520# undef KDTREE2D_ISECT_TRI_RECURSE_POS
521# undef KDTREE2D_ISECT_ARGS
528# ifdef USE_KDTREE_INDEX_CACHE
539 !
ELEM(test_index, tri_index[0], tri_index[1], tri_index[2]))
541 const float *v1 = tree->coords[tri_index[0]];
542 const float *
v2 = tree->coords[tri_index[1]];
543 const float *v3 = tree->coords[tri_index[2]];
544 const float *co = tree->coords[test_index];
546# ifdef USE_PRECOMPUTED_ISECT
547 const float *vs[3] = {v1,
v2, v3};
570 const float *vs[3] = {
571 tree->coords[ind[0]],
572 tree->coords[ind[1]],
573 tree->coords[ind[2]],
576 const KDRange2D
bounds[2] = {
577 {std::min({vs[0][0], vs[1][0], vs[2][0]}), std::max({vs[0][0], vs[1][0], vs[2][0]})},
578 {std::min({vs[0][1], vs[1][1], vs[2][1]}), std::max({vs[0][1], vs[1][1], vs[2][1]})},
581 const float tri_center[2] = {
582 (vs[0][0] + vs[1][0] + vs[2][0]) * (1.0f / 3.0f),
583 (vs[0][1] + vs[1][1] + vs[2][1]) * (1.0f / 3.0f),
586# ifdef USE_PRECOMPUTED_ISECT
600 &tree->nodes[tree->root]);
607 return pf->tris[
pf->tris_num++];
614 if (
pf->kdtree.node_num) {
619 pi->next->prev = pi->prev;
620 pi->prev->next = pi->next;
622 if (
pf->indices == pi) [[unlikely]] {
623 pf->indices = pi->next;
627 pi->next = pi->prev =
nullptr;
639 PolyIndex *pi_ear_init =
pf->indices;
642 bool reverse =
false;
645 while (
pf->coords_num > 3) {
646 PolyIndex *pi_prev, *pi_next;
647 eSign sign_orig_prev, sign_orig_next;
660#ifdef USE_CONVEX_SKIP
661 if (pi_ear->sign != CONVEX) {
662 pf->coords_num_concave -= 1;
666 pi_prev = pi_ear->prev;
667 pi_next = pi_ear->next;
671#ifdef USE_KDTREE_INDEX_CACHE
673 pi_prev->flag |= PolyIndexFlag::IndexCacheDirty;
674 pi_next->flag |= PolyIndexFlag::IndexCacheDirty;
678 sign_orig_prev = pi_prev->sign;
679 sign_orig_next = pi_next->sign;
683 if (sign_orig_prev != CONVEX) {
685#ifdef USE_CONVEX_SKIP
686 if (pi_prev->sign == CONVEX) {
687 pf->coords_num_concave -= 1;
694 if (sign_orig_next != CONVEX) {
696#ifdef USE_CONVEX_SKIP
697 if (pi_next->sign == CONVEX) {
698 pf->coords_num_concave -= 1;
707# ifdef USE_CLIP_SWEEP
708 pi_ear_init = reverse ? pi_prev->prev : pi_next->next;
710 pi_ear_init = pi_next->next;
715# ifdef USE_CLIP_SWEEP
716 if (pi_ear_init->sign != CONVEX) {
718 pi_ear_init = reverse ? pi_ear_init->prev : pi_ear_init->next;
723# ifdef USE_CLIP_SWEEP
724 if ((reverse ? pi_prev->prev : pi_next->next)->sign != CONVEX) {
731 if (
pf->coords_num == 3) {
733 pi_ear =
pf->indices;
734 tri[0] = pi_ear->index;
735 pi_ear = pi_ear->next;
736 tri[1] = pi_ear->index;
737 pi_ear = pi_ear->next;
738 tri[2] = pi_ear->index;
748 const float (*coords)[2] =
pf->coords;
750 pi->sign =
span_tri_v2_sign(coords[pi->prev->index], coords[pi->index], coords[pi->next->index]);
756 PolyIndex *pi_ear_init
791 for (eSign sign_accept = CONVEX; sign_accept >= TANGENTIAL; sign_accept--) {
793 pi_ear = pi_ear_init;
795 pi_ear =
pf->indices;
803 pi_ear = reverse ? pi_ear->prev : pi_ear->next;
805 pi_ear = pi_ear->next;
823 pi_ear = pi_ear_init;
825 pi_ear =
pf->indices;
830 if (pi_ear->sign != CONCAVE) {
833 pi_ear = pi_ear->next;
844 const float (*coords)[2] =
pf->coords;
847 const float *v1, *
v2, *v3;
850#if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE)
851 uint32_t coords_num_concave_checked = 0;
854#ifdef USE_CONVEX_SKIP
856# ifdef USE_CONVEX_SKIP_TEST
859 uint32_t coords_num_concave_test = 0;
860 PolyIndex *pi_iter = pi_ear_tip;
862 if (pi_iter->sign != CONVEX) {
863 coords_num_concave_test += 1;
865 }
while ((pi_iter = pi_iter->next) != pi_ear_tip);
866 BLI_assert(coords_num_concave_test ==
pf->coords_num_concave);
871 if (
pf->coords_num_concave == 0) {
876 if (pi_ear_tip->sign != sign_accept) [[unlikely]] {
882 const uint32_t ind[3] = {pi_ear_tip->index, pi_ear_tip->next->index, pi_ear_tip->prev->index};
884# ifdef USE_KDTREE_INDEX_CACHE
885 const uint32_t cached_hit = pi_ear_tip->index_last_hit;
887 if ((pi_ear_tip->flag & PolyIndexFlag::IndexCacheDirty) == PolyIndexFlag(0)) {
902 pi_ear_tip->flag &= ~PolyIndexFlag::IndexCacheDirty;
912# ifdef USE_KDTREE_INDEX_CACHE
913 pi_ear_tip->index_last_hit = hit;
914 pi_ear_tip->flag &= ~PolyIndexFlag::IndexCacheDirty;
921 v1 = coords[pi_ear_tip->prev->index];
922 v2 = coords[pi_ear_tip->index];
923 v3 = coords[pi_ear_tip->next->index];
929 for (pi_curr = pi_ear_tip->next->next; pi_curr != pi_ear_tip->prev; pi_curr = pi_curr->next) {
932 if (pi_curr->sign != CONVEX) {
933 const float *
v = coords[pi_curr->index];
948# ifdef USE_CONVEX_SKIP
949 coords_num_concave_checked += 1;
950 if (coords_num_concave_checked ==
pf->coords_num_concave) {
965 tri[0] = pi_ear_tip->prev->index;
966 tri[1] = pi_ear_tip->index;
967 tri[2] = pi_ear_tip->next->index;
976 const float (*coords)[2],
980 PolyIndex *r_indices)
983 PolyIndex *indices = r_indices;
988 pf->indices = r_indices;
990 pf->coords_num = coords_num;
991#ifdef USE_CONVEX_SKIP
992 pf->coords_num_concave = 0;
997 if (coords_sign == 0) {
998 coords_sign = (
cross_poly_v2(coords, coords_num) <= 0.0f) ? 1 : -1;
1002#ifdef USE_STRICT_ASSERT
1004 if (coords_sign == 1) {
1014 if (coords_sign == 1) {
1015 for (i = 0; i < coords_num; i++) {
1016 indices[i].next = &indices[i + 1];
1017 indices[i].prev = &indices[i - 1];
1018 indices[i].index = i;
1024 for (i = 0; i < coords_num; i++) {
1025 indices[i].next = &indices[i + 1];
1026 indices[i].prev = &indices[i - 1];
1027 indices[i].index = (n - i);
1030 indices[0].prev = &indices[coords_num - 1];
1031 indices[coords_num - 1].next = &indices[0];
1033 for (i = 0; i < coords_num; i++) {
1034 PolyIndex *pi = &indices[i];
1036#ifdef USE_CONVEX_SKIP
1037 if (pi->sign != CONVEX) {
1038 pf->coords_num_concave += 1;
1041#ifdef USE_KDTREE_INDEX_CACHE
1042 pi->flag = PolyIndexFlag(0);
1051# ifdef USE_CONVEX_SKIP
1052 if (
pf->coords_num_concave)
1067 const int coords_sign,
1073 PolyIndex *indices =
static_cast<PolyIndex *
>(
1089 if (
pf.coords_num_concave) {
1090 pf.kdtree.nodes =
static_cast<KDTreeNode2D *
>(
1092 pf.kdtree.nodes_map =
static_cast<uint32_t *
>(
1095 sizeof(*
pf.kdtree.nodes_map) * coords_num));
1098 pf.kdtree.node_num = 0;
1114 const int coords_sign,
1120 if (coords_num > 8192) [[unlikely]] {
1131 PolyIndex *indices =
static_cast<PolyIndex *
>(
BLI_array_alloca(indices, coords_num));
1146 if (
pf.coords_num_concave) {
1147 pf.kdtree.nodes =
static_cast<KDTreeNode2D *
>(
1149 pf.kdtree.nodes_map =
static_cast<uint32_t *
>(
1152 sizeof(*
pf.kdtree.nodes_map) * coords_num));
1155 pf.kdtree.node_num = 0;
#define BLI_array_alloca(arr, realsize)
#define ENUM_OPERATORS(_enum_type)
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
Read Blender memory allocation and freeing.
#define pf(_x, _i)
Prefetch 64.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static void kdtree2d_node_remove(KDTree2D *tree, uint32_t index)
static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
static PolyIndex * pf_ear_tip_find(PolyFill *pf, PolyIndex *pi_ear_init, bool reverse)
static bool kdtree2d_isect_tri_single(const KDTree2D *tree, const uint32_t tri_index[3], const uint32_t test_index)
float cross_poly_v2(const float verts[][2], unsigned int nr)
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
BLI_INLINE eSign signum_enum(float a)
static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip)
static void pf_triangulate(PolyFill *pf)
static void kdtree2d_balance(KDTree2D *tree)
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
static uint32_t kdtree2d_balance_recursive(KDTreeNode2D *nodes, uint32_t node_num, axis_t axis, const float(*coords)[2], const uint32_t ofs)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void kdtree2d_init(KDTree2D *tree, const uint32_t coords_num, const PolyIndex *indices)
static void polyfill_calc(PolyFill *pf)
static void kdtree2d_init_mapping(KDTree2D *tree)
static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
static void pf_coord_sign_calc(const PolyFill *pf, PolyIndex *pi)
static bool tri_isect_precomputed_test(const TriIsectPrecomputed *t, const float co[2])
static void tri_isect_precomputed_init(TriIsectPrecomputed *t, const float *const vs[3])
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
static void polyfill_prepare(PolyFill *pf, const float(*coords)[2], const uint32_t coords_num, int coords_sign, uint32_t(*r_tris)[3], PolyIndex *r_indices)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip, const eSign sign_accept)
static uint32_t kdtree2d_isect_tri(KDTree2D *tree, const uint32_t ind[3])
static uint32_t 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 void kdtree2d_new(KDTree2D *tree, uint32_t tot, const float(*coords)[2])
static uint32_t * pf_tri_add(PolyFill *pf)
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
#define USE_PRECOMPUTED_ISECT
#define KDTREE2D_ISECT_TRI_RECURSE_NEG
#define KDTREE_INDEX_CACHE_UNSET
#define KDTREE2D_ISECT_TRI_RECURSE_POS
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float