Commit: 3602071e47f4cb6613448c14c931fbd6ffb45ead
Author: Campbell Barton
Date: Thu Mar 21 02:27:27 2019 +1100
Branches: master
https://developer.blender.org/rB3602071e47f4cb6613448c14c931fbd6ffb45ead
BLI_kdtree: add deduplicate function
Function to remove exact duplicates from the tree before balancing.
===================================================================
M source/blender/blenlib/BLI_kdtree_impl.h
M source/blender/blenlib/intern/kdtree_impl.h
===================================================================
diff --git a/source/blender/blenlib/BLI_kdtree_impl.h
b/source/blender/blenlib/BLI_kdtree_impl.h
index 08b66c16d3e..bd4fa908b14 100644
--- a/source/blender/blenlib/BLI_kdtree_impl.h
+++ b/source/blender/blenlib/BLI_kdtree_impl.h
@@ -67,6 +67,9 @@ int BLI_kdtree_nd_(calc_duplicates_fast)(
const KDTree *tree, const float range, bool use_index_order,
int *doubles);
+
+int BLI_kdtree_nd_(deduplicate)(KDTree *tree);
+
/* Versions of find/range search that take a squared distance callback to
support bias. */
int BLI_kdtree_nd_(find_nearest_n_with_len_squared_cb)(
const KDTree *tree, const float co[KD_DIMS],
diff --git a/source/blender/blenlib/intern/kdtree_impl.h
b/source/blender/blenlib/intern/kdtree_impl.h
index 62bd51eea80..1bce3473bde 100644
--- a/source/blender/blenlib/intern/kdtree_impl.h
+++ b/source/blender/blenlib/intern/kdtree_impl.h
@@ -910,3 +910,58 @@ int BLI_kdtree_nd_(calc_duplicates_fast)(
}
/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name BLI_kdtree_3d_deduplicate
+ * \{ */
+
+static int kdtree_node_cmp_deduplicate(const void *n0_p, const void *n1_p)
+{
+ const KDTreeNode *n0 = n0_p;
+ const KDTreeNode *n1 = n1_p;
+ for (uint j = 0; j < KD_DIMS; j++) {
+ if (n0->co[j] < n1->co[j]) {
+ return -1;
+ }
+ else if (n0->co[j] > n1->co[j]) {
+ return 1;
+ }
+ }
+ /* Sort by pointer so the first added will be used.
+ * assignment below ignores const correctness,
+ * however the values aren't used for sorting and are to be discarded.
*/
+ if (n0 < n1) {
+ ((KDTreeNode *)n1)->d = KD_DIMS; /* tag invalid */
+ return -1;
+ }
+ else {
+ ((KDTreeNode *)n0)->d = KD_DIMS; /* tag invalid */
+ return 1;
+ }
+}
+
+/**
+ * Remove exact duplicates (run before before balancing).
+ *
+ * Keep the first element added when duplicates are found.
+ */
+int BLI_kdtree_nd_(deduplicate)(KDTree *tree)
+{
+#ifdef DEBUG
+ tree->is_balanced = false;
+#endif
+ qsort(tree->nodes, (size_t)tree->nodes_len, sizeof(*tree->nodes),
kdtree_node_cmp_deduplicate);
+ uint j = 0;
+ for (uint i = 0; i < tree->nodes_len; i++) {
+ if (tree->nodes[i].d != KD_DIMS) {
+ if (i != j) {
+ tree->nodes[j] = tree->nodes[i];
+ }
+ j++;
+ }
+ }
+ tree->nodes_len = j;
+ return (int)tree->nodes_len;
+}
+
+/** \} */
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
