[Bf-blender-cvs] [746f0ad] master: Polyfill2d: use kd-tree
Campbell Barton
noreply at git.blender.org
Sat Jun 14 00:33:30 CEST 2014
Commit: 746f0ad257b81e2680db10d9993c9054f059033c
Author: Campbell Barton
Date: Wed Jun 11 10:17:22 2014 +1000
https://developer.blender.org/rB746f0ad257b81e2680db10d9993c9054f059033c
Polyfill2d: use kd-tree
Simple search for intersections became slow for larger concave ngons (100+)
Tested to work with ngons up to 75k sides, performance is approx ~6x faster then scanfill.
This is a 2D version of BLI_kdtree with modifications:
- nodes can be removed
- an index -> node map is stored (especially for tessellation)
===================================================================
M source/blender/blenlib/intern/polyfill2d.c
===================================================================
diff --git a/source/blender/blenlib/intern/polyfill2d.c b/source/blender/blenlib/intern/polyfill2d.c
index 1c0b936..30d1ab4 100644
--- a/source/blender/blenlib/intern/polyfill2d.c
+++ b/source/blender/blenlib/intern/polyfill2d.c
@@ -57,6 +57,10 @@
#define USE_CLIP_SWEEP
// #define USE_CONVEX_SKIP_TEST
+#ifdef USE_CONVEX_SKIP
+# define USE_KDTREE
+#endif
+
// #define DEBUG_TIME
#ifdef DEBUG_TIME
# include "PIL_time_utildefines.h"
@@ -64,6 +68,52 @@
typedef signed char eSign;
+
+#ifdef USE_KDTREE
+/**
+ * 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 then 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.
+ */
+
+typedef bool axis_t;
+
+/* use for sorting */
+typedef struct KDTreeNode2D_head {
+ unsigned int neg, pos;
+ unsigned int index;
+} KDTreeNode2D_head;
+
+typedef struct KDTreeNode2D {
+ unsigned int neg, pos;
+ unsigned int index;
+ axis_t axis; /* range is only (0-1) */
+ unsigned short flag;
+ unsigned int parent;
+} KDTreeNode2D;
+
+struct KDTree2D {
+ KDTreeNode2D *nodes;
+ const float (*coords)[2];
+ unsigned int root;
+ unsigned int totnode;
+ unsigned int *nodes_map; /* index -> node lookup */
+};
+
+struct KDRange2D {
+ float min, max;
+};
+#endif /* USE_KDTREE */
+
enum {
CONCAVE = -1,
TANGENTIAL = 0,
@@ -82,6 +132,10 @@ typedef struct PolyFill {
/* A polygon with n vertices has a triangulation of n-2 triangles. */
unsigned int (*tris)[3];
unsigned int tris_tot;
+
+#ifdef USE_KDTREE
+ struct KDTree2D kdtree;
+#endif
} PolyFill;
@@ -140,6 +194,271 @@ static eSign span_tri_v2_sign(const float v1[2], const float v2[2], const float
return signum_i(area_tri_signed_v2_alt_2x(v3, v2, v1));
}
+
+#ifdef USE_KDTREE
+#define KDNODE_UNSET ((unsigned int)-1)
+
+enum {
+ KDNODE_FLAG_REMOVED = (1 << 0),
+};
+
+static void kdtree2d_new(
+ struct KDTree2D *tree,
+ unsigned int tot,
+ const float (*coords)[2])
+{
+ /* set by caller */
+ // tree->nodes = nodes;
+ tree->coords = coords;
+ tree->root = KDNODE_UNSET;
+ tree->totnode = tot;
+}
+
+/**
+ * no need for kdtree2d_insert, since we know the coords array.
+ */
+static void kdtree2d_init(
+ struct KDTree2D *tree,
+ const unsigned int coords_tot,
+ const PolyIndex *indices)
+{
+ KDTreeNode2D *node;
+ unsigned int i;
+
+ for (i = 0, node = tree->nodes; i < coords_tot; i++) {
+ if (indices[i].sign != CONVEX) {
+ node->neg = node->pos = KDNODE_UNSET;
+ node->index = indices[i].index;
+ node->axis = 0;
+ node->flag = 0;
+ node++;
+ }
+ }
+
+ BLI_assert(tree->totnode == (node - tree->nodes));
+}
+
+static unsigned int kdtree2d_balance_recursive(
+ KDTreeNode2D *nodes, unsigned int totnode, axis_t axis,
+ const float (*coords)[2], const unsigned int ofs)
+{
+ KDTreeNode2D *node;
+ unsigned int neg, pos, median, i, j;
+
+ if (totnode <= 0) {
+ return KDNODE_UNSET;
+ }
+ else if (totnode == 1) {
+ return 0 + ofs;
+ }
+
+ /* quicksort style sorting around median */
+ neg = 0;
+ pos = totnode - 1;
+ median = totnode / 2;
+
+ while (pos > neg) {
+ const float co = coords[nodes[pos].index][axis];
+ i = neg - 1;
+ j = pos;
+
+ while (1) {
+ while (coords[nodes[++i].index][axis] < co) ;
+ while (coords[nodes[--j].index][axis] > co && j > neg) ;
+
+ if (i >= j) {
+ break;
+ }
+ SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[j]);
+ }
+
+ SWAP(KDTreeNode2D_head, *(KDTreeNode2D_head *)&nodes[i], *(KDTreeNode2D_head *)&nodes[pos]);
+ if (i >= median) {
+ pos = i - 1;
+ }
+ if (i <= median) {
+ neg = i + 1;
+ }
+ }
+
+ /* set node and sort subnodes */
+ node = &nodes[median];
+ node->axis = axis;
+ axis = !axis;
+ node->neg = kdtree2d_balance_recursive(nodes, median, axis, coords, ofs);
+ node->pos = kdtree2d_balance_recursive(&nodes[median + 1], (totnode - (median + 1)), axis, coords, (median + 1) + ofs);
+
+ return median + ofs;
+}
+
+static void kdtree2d_balance(
+ struct KDTree2D *tree)
+{
+ tree->root = kdtree2d_balance_recursive(tree->nodes, tree->totnode, 0, tree->coords, 0);
+}
+
+
+static void kdtree2d_init_mapping(
+ struct KDTree2D *tree)
+{
+ unsigned int i;
+ KDTreeNode2D *node;
+
+ for (i = 0, node = tree->nodes; i < tree->totnode; i++, node++) {
+ if (node->neg != KDNODE_UNSET) {
+ tree->nodes[node->neg].parent = i;
+ }
+ if (node->pos != KDNODE_UNSET) {
+ tree->nodes[node->pos].parent = i;
+ }
+
+ /* build map */
+ BLI_assert(tree->nodes_map[node->index] == KDNODE_UNSET);
+ tree->nodes_map[node->index] = i;
+ }
+
+ tree->nodes[tree->root].parent = KDNODE_UNSET;
+}
+
+static void kdtree2d_node_remove(
+ struct KDTree2D *tree,
+ unsigned int index)
+{
+ unsigned int node_index = tree->nodes_map[index];
+ KDTreeNode2D *node;
+
+ if (node_index == KDNODE_UNSET) {
+ return;
+ }
+ else {
+ tree->nodes_map[index] = KDNODE_UNSET;
+ }
+
+ node = &tree->nodes[node_index];
+ tree->totnode -= 1;
+
+ BLI_assert((node->flag & KDNODE_FLAG_REMOVED) == 0);
+ node->flag |= KDNODE_FLAG_REMOVED;
+
+ while ((node->neg == KDNODE_UNSET) &&
+ (node->pos == KDNODE_UNSET) &&
+ (node->parent != KDNODE_UNSET))
+ {
+ KDTreeNode2D *node_parent = &tree->nodes[node->parent];
+
+ BLI_assert((unsigned int)(node - tree->nodes) == node_index);
+ if (node_parent->neg == node_index) {
+ node_parent->neg = KDNODE_UNSET;
+ }
+ else {
+ BLI_assert(node_parent->pos == node_index);
+ node_parent->pos = KDNODE_UNSET;
+ }
+
+ if (node_parent->flag & KDNODE_FLAG_REMOVED) {
+ node_index = node->parent;
+ node = node_parent;
+ }
+ else {
+ break;
+ }
+ }
+}
+
+static bool kdtree2d_isect_tri_recursive(
+ const struct KDTree2D *tree,
+ const unsigned int tri_index[3],
+ const float *tri_coords[3],
+ const float tri_center[2],
+ const struct KDRange2D bounds[2],
+ const KDTreeNode2D *node)
+{
+ const float *co = tree->coords[node->index];
+
+ /* bounds then triangle intersect */
+ if ((node->flag & KDNODE_FLAG_REMOVED) == 0) {
+ /* bounding box test first */
+ if ((co[0] > bounds[0].min) &&
+ (co[0] < bounds[0].max) &&
+ (co[1] > bounds[1].min) &&
+ (co[1] < bounds[1].max))
+ {
+ if ((span_tri_v2_sign(tri_coords[0], tri_coords[1], co) != CONCAVE) &&
+ (span_tri_v2_sign(tri_coords[1], tri_coords[2], co) != CONCAVE) &&
+ (span_tri_v2_sign(tri_coords[2], tri_coords[0], co) != CONCAVE))
+ {
+ if (!ELEM3(node->index, tri_index[0], tri_index[1], tri_index[2])) {
+ return true;
+ }
+ }
+ }
+ }
+
+#define KDTREE2D_ISECT_TRI_RECURSE_NEG \
+ (((node->neg != KDNODE_UNSET) && (co[node->axis] > bounds[node->axis].min)) && \
+ (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \
+ &tree->nodes[node->neg])))
+#define KDTREE2D_ISECT_TRI_RECURSE_POS \
+ (((node->pos != KDNODE_UNSET) && (co[node->axis] < bounds[node->axis].max)) && \
+ (kdtree2d_isect_tri_recursive(tree, tri_index, tri_coords, tri_center, bounds, \
+ &tree->nodes[node->pos])))
+
+ if (tri_center[node->axis] > co[node->axis]) {
+ if (KDTREE2D_ISECT_TRI_RECURSE_POS) {
+ return true;
+ }
+ if (KDTREE2D_ISECT_TRI_RECURSE_NEG) {
+ return true;
+ }
+ }
+ else {
+ if (KDTREE2D_ISECT_TRI_RECURSE_NEG) {
+ return true;
+ }
+ if (KDTREE2D_ISECT_TRI_RECURSE_POS) {
+ return true;
+ }
+ }
+
+#undef KDTREE2D_ISECT_TRI_RECURSE_NEG
+#undef KDTREE2D_ISECT_TRI_RECURSE_POS
+
+ BLI_assert(node->index != KDNODE_UNSET);
+
+ return false;
+}
+
+static bool kdtree2d_isect_tri(
+ struct KDTree2D *tree,
+ const unsigned int ind[3])
+{
+ const float *vs[3];
+ unsigned int i;
+ struct KDRange2D bounds[2] = {
+ {FLT_MAX, -FLT_MAX},
+ {FLT_MAX, -FLT_MAX},
+ };
+ float tri_center[2] = {0.0f, 0.0f};
+
+ for (i = 0; i < 3; i++) {
+ vs[i] = tree->coords[ind[i]];
+
+ add_v2_v2(tri_center, vs[i]);
+
+ CLAMP_MAX(bounds[0].min, vs[i][0]);
+ CLAMP_MIN(bounds[0].max, vs[i][0]);
+ CLAMP_MAX(bounds[1].min, vs[i][1]);
+ CLAMP_MIN(bounds[1].max, vs[i][1]);
+ }
+
+ mul_v2_fl(tri_center, 1.0f / 3.0f);
+
+ return kdtree2d_isect_tri_recursive(tree, ind, vs, tri_center, bounds, &tree->nodes[tree->root]);
+}
+
+#endif /* USE_KDTREE */
+
+
static unsigned int *pf_tri_add(PolyFill *pf)
{
return pf->tris[pf->tris_tot++];
@@ -147,6 +466,13 @@ static unsigned int *pf_tri_add(PolyFill *pf)
static void pf_coord_remove(PolyFill *pf, PolyIndex *pi)
{
+#ifdef USE_KDTREE
+ /* avoid double lookups, since convex coords are ignored when testing intersections */
+ if (pf->kdtree.totnode) {
+ kdtree2d_node_remove(&pf->kdtree, pi->index);
+ }
+#endif
+
pi->next->prev = pi->prev;
pi->prev->next = pi->next;
@@ -221,6 +547,9 @@ static void pf_triangulate(PolyFill *pf)
#ifdef USE_CONVEX_SKIP
if (pi_prev->sign == CONVEX) {
pf->coords_tot_concave -= 1;
+#ifdef USE_KDTREE
+ kdtree2d_node_remove(&pf->kdtree, pi_prev->index);
+#endif
}
#endif
}
@@ -229,6 +558,9 @@ static void pf_triangulate(PolyFill *pf)
#ifdef USE_CONVEX_SKIP
if (pi_next->sign == CONVEX) {
pf->coords_tot_concave -= 1;
+#ifdef USE_KDTREE
+ kdtree2d_node_remove(&pf->kdtree, pi_next->index);
+#endif
}
#endif
}
@@ -333,9 +665,11 @@ static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip)
PolyIndex *pi_curr;
const float (*coords)[2] = pf->coords;
+#ifndef USE_KDTREE
const float *v1, *v2, *v3;
+#endif
-#ifdef USE_CONVEX_SKIP
+#if defined(USE_CONVEX_SKIP) && !defined(USE_KDTREE)
unsigned int coords_tot_concave_checked = 0;
#endif
@@ -348,7 +682,7 @@ static bool pf_ear_tip_check(PolyFill *pf, PolyIndex *pi_ear_tip)
unsigned int coords_tot_concave_test = 0;
unsigned int i = pf->coords_tot;
while (i--) {
- if (pf->indices[i].sign != CONVEX) {
+ if (coords_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list