[Bf-blender-cvs] [3602071e47f] master: BLI_kdtree: add deduplicate function

[Campbell Barton]

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;
+}
+
+/** \} */