44 #define USE_CONVEX_SKIP
46 #define USE_CLIP_SWEEP
49 #ifdef USE_CONVEX_SKIP
123 #ifdef USE_CONVEX_SKIP
184 return (d2[0] * d3[1]) - (d3[0] * d2[1]);
193 # define KDNODE_UNSET ((uint)-1)
203 tree->coords = coords;
205 tree->node_num = tot;
216 for (i = 0,
node =
tree->nodes; i < coords_num; i++) {
245 median = node_num / 2;
248 const float co = coords[nodes[
pos].
index][axis];
253 while (coords[nodes[++i].
index][axis] < co) {
255 while (coords[nodes[--j].
index][axis] > co && j > neg) {
274 node = &nodes[median];
279 &nodes[median + 1], (node_num - (median + 1)), axis, coords, (median + 1) + ofs);
294 for (i = 0,
node =
tree->nodes; i < tree->node_num; i++,
node++) {
332 if (node_parent->
neg == node_index) {
341 node_index =
node->parent;
351 const uint tri_index[3],
352 const float *tri_coords[3],
353 const float tri_center[2],
357 const float *co =
tree->coords[
node->index];
367 if (!
ELEM(
node->index, tri_index[0], tri_index[1], tri_index[2])) {
374 # define KDTREE2D_ISECT_TRI_RECURSE_NEG \
375 (((node->neg != KDNODE_UNSET) && (co[node->axis] >= bounds[node->axis].min)) && \
376 (kdtree2d_isect_tri_recursive( \
377 tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->neg])))
378 # define KDTREE2D_ISECT_TRI_RECURSE_POS \
379 (((node->pos != KDNODE_UNSET) && (co[node->axis] <= bounds[node->axis].max)) && \
380 (kdtree2d_isect_tri_recursive( \
381 tree, tri_index, tri_coords, tri_center, bounds, &tree->nodes[node->pos])))
383 if (tri_center[
node->axis] > co[
node->axis]) {
400 # undef KDTREE2D_ISECT_TRI_RECURSE_NEG
401 # undef KDTREE2D_ISECT_TRI_RECURSE_POS
416 float tri_center[2] = {0.0f, 0.0f};
418 for (i = 0; i < 3; i++) {
419 vs[i] =
tree->coords[ind[i]];
438 return pf->tris[
pf->tris_num++];
445 if (
pf->kdtree.node_num) {
472 #ifdef USE_CLIP_SWEEP
473 bool reverse =
false;
476 while (
pf->coords_num > 3) {
478 eSign sign_orig_prev, sign_orig_next;
491 #ifdef USE_CONVEX_SKIP
493 pf->coords_num_concave -= 1;
497 pi_prev = pi_ear->
prev;
498 pi_next = pi_ear->
next;
503 sign_orig_prev = pi_prev->
sign;
504 sign_orig_next = pi_next->
sign;
508 if (sign_orig_prev !=
CONVEX) {
510 #ifdef USE_CONVEX_SKIP
512 pf->coords_num_concave -= 1;
519 if (sign_orig_next !=
CONVEX) {
521 #ifdef USE_CONVEX_SKIP
523 pf->coords_num_concave -= 1;
532 # ifdef USE_CLIP_SWEEP
533 pi_ear_init = reverse ? pi_prev->
prev : pi_next->
next;
535 pi_ear_init = pi_next->
next;
540 # ifdef USE_CLIP_SWEEP
543 pi_ear_init = reverse ? pi_ear_init->
prev : pi_ear_init->
next;
554 if (
pf->coords_num == 3) {
556 pi_ear =
pf->indices;
557 tri[0] = pi_ear->
index;
558 pi_ear = pi_ear->
next;
559 tri[1] = pi_ear->
index;
560 pi_ear = pi_ear->
next;
561 tri[2] = pi_ear->
index;
571 const float(*coords)[2] =
pf->coords;
588 const uint coords_num =
pf->coords_num;
594 pi_ear = pi_ear_init;
596 pi_ear =
pf->indices;
604 #ifdef USE_CLIP_SWEEP
605 pi_ear = reverse ? pi_ear->
prev : pi_ear->
next;
607 pi_ear = pi_ear->
next;
624 pi_ear = pi_ear_init;
626 pi_ear =
pf->indices;
634 pi_ear = pi_ear->
next;
645 const float(*coords)[2] =
pf->coords;
648 const float *
v1, *
v2, *v3;
651 #if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE)
652 uint coords_num_concave_checked = 0;
655 #ifdef USE_CONVEX_SKIP
657 # ifdef USE_CONVEX_SKIP_TEST
660 uint coords_num_concave_test = 0;
664 coords_num_concave_test += 1;
666 }
while ((pi_iter = pi_iter->
next) != pi_ear_tip);
667 BLI_assert(coords_num_concave_test ==
pf->coords_num_concave);
672 if (
pf->coords_num_concave == 0) {
692 v2 = coords[pi_ear_tip->
index];
699 for (pi_curr = pi_ear_tip->
next->
next; pi_curr != pi_ear_tip->
prev; pi_curr = pi_curr->
next) {
703 const float *
v = coords[pi_curr->
index];
717 # ifdef USE_CONVEX_SKIP
718 coords_num_concave_checked += 1;
719 if (coords_num_concave_checked ==
pf->coords_num_concave) {
735 tri[1] = pi_ear_tip->
index;
745 const float (*coords)[2],
746 const uint coords_num,
757 pf->indices = r_indices;
759 pf->coords_num = coords_num;
760 #ifdef USE_CONVEX_SKIP
761 pf->coords_num_concave = 0;
766 if (coords_sign == 0) {
767 coords_sign = (
cross_poly_v2(coords, coords_num) >= 0.0f) ? 1 : -1;
771 #ifdef USE_STRICT_ASSERT
773 if (coords_sign == 1) {
783 if (coords_sign == 1) {
784 for (i = 0; i < coords_num; i++) {
792 uint n = coords_num - 1;
793 for (i = 0; i < coords_num; i++) {
802 for (i = 0; i < coords_num; i++) {
805 #ifdef USE_CONVEX_SKIP
807 pf->coords_num_concave += 1;
816 # ifdef USE_CONVEX_SKIP
817 if (
pf->coords_num_concave)
831 const uint coords_num,
832 const int coords_sign,
853 if (
pf.coords_num_concave) {
855 pf.kdtree.nodes_map = memset(
858 sizeof(*
pf.kdtree.nodes_map) * coords_num);
861 pf.kdtree.node_num = 0;
876 const uint coords_num,
877 const int coords_sign,
909 if (
pf.coords_num_concave) {
913 sizeof(*
pf.kdtree.nodes_map) * coords_num);
916 pf.kdtree.node_num = 0;
typedef float(TangentPoint)[2]
#define BLI_array_alloca(arr, realsize)
float cross_poly_v2(const float verts[][2], unsigned int nr)
MINLINE void mul_v2_fl(float r[2], float f)
MINLINE void add_v2_v2(float r[2], const float a[2])
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert * v
static btDbvtVolume bounds(btDbvtNode **leaves, int count)
#define pf(_x, _i)
Prefetch 64.
ccl_gpu_kernel_postfix int ccl_global int * indices
static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip)
static PolyIndex * pf_ear_tip_find(PolyFill *pf, PolyIndex *pi_ear_init, bool reverse)
static bool kdtree2d_isect_tri(struct KDTree2D *tree, const uint ind[3])
struct KDTreeNode2D KDTreeNode2D
static void kdtree2d_init_mapping(struct KDTree2D *tree)
struct KDTreeNode2D_head KDTreeNode2D_head
BLI_INLINE eSign signum_enum(float a)
struct PolyIndex PolyIndex
static void pf_ear_tip_cut(PolyFill *pf, PolyIndex *pi_ear_tip)
#define KDTREE2D_ISECT_TRI_RECURSE_NEG
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)
BLI_INLINE float area_tri_signed_v2_alt_2x(const float v1[2], const float v2[2], const float v3[2])
static void kdtree2d_node_remove(struct KDTree2D *tree, uint index)
void BLI_polyfill_calc_arena(const float(*coords)[2], const uint coords_num, const int coords_sign, uint(*r_tris)[3], struct MemArena *arena)
static void pf_coord_sign_calc(PolyFill *pf, PolyIndex *pi)
void BLI_polyfill_calc(const float(*coords)[2], const uint coords_num, const int coords_sign, uint(*r_tris)[3])
static uint kdtree2d_balance_recursive(KDTreeNode2D *nodes, uint node_num, axis_t axis, const float(*coords)[2], const uint ofs)
static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float v3[2])
static void kdtree2d_balance(struct KDTree2D *tree)
static uint * pf_tri_add(PolyFill *pf)
static void kdtree2d_init(struct KDTree2D *tree, const uint coords_num, const PolyIndex *indices)
static void polyfill_prepare(PolyFill *pf, const float(*coords)[2], const uint coords_num, int coords_sign, uint(*r_tris)[3], PolyIndex *r_indices)
#define KDTREE2D_ISECT_TRI_RECURSE_POS
static void kdtree2d_new(struct KDTree2D *tree, uint tot, const float(*coords)[2])
static void polyfill_calc(PolyFill *pf)
static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
static void pf_triangulate(PolyFill *pf)
struct PolyIndex * indices