Fix T99033: KDTree deduplication can erase values
Differential Revision: https://developer.blender.org/D15220
This commit is contained in:
parent
a18c291435
commit
95465606b3
Notes:
blender-bot
2023-02-14 01:21:16 +01:00
Referenced by issue #99033, Weld by distance does nothing when the distance is zero
|
@ -445,6 +445,7 @@ if(WITH_GTESTS)
|
|||
tests/BLI_index_range_test.cc
|
||||
tests/BLI_inplace_priority_queue_test.cc
|
||||
tests/BLI_kdopbvh_test.cc
|
||||
tests/BLI_kdtree_test.cc
|
||||
tests/BLI_length_parameterize_test.cc
|
||||
tests/BLI_linear_allocator_test.cc
|
||||
tests/BLI_linklist_lockfree_test.cc
|
||||
|
|
|
@ -927,6 +927,14 @@ int BLI_kdtree_nd_(calc_duplicates_fast)(const KDTree *tree,
|
|||
/** \name BLI_kdtree_3d_deduplicate
|
||||
* \{ */
|
||||
|
||||
static int kdtree_cmp_bool(const bool a, const bool b)
|
||||
{
|
||||
if (a == b) {
|
||||
return 0;
|
||||
}
|
||||
return b ? -1 : 1;
|
||||
}
|
||||
|
||||
static int kdtree_node_cmp_deduplicate(const void *n0_p, const void *n1_p)
|
||||
{
|
||||
const KDTreeNode *n0 = n0_p;
|
||||
|
@ -939,17 +947,16 @@ static int kdtree_node_cmp_deduplicate(const void *n0_p, const void *n1_p)
|
|||
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;
|
||||
|
||||
if (n0->d != KD_DIMS && n1->d != KD_DIMS) {
|
||||
/* Two nodes share identical `co`
|
||||
* Both are still valid.
|
||||
* Cast away `const` and tag one of them as invalid. */
|
||||
((KDTreeNode *)n1)->d = KD_DIMS;
|
||||
}
|
||||
|
||||
/* Keep sorting until each unique value has one and only one valid node. */
|
||||
return kdtree_cmp_bool(n0->d == KD_DIMS, n1->d == KD_DIMS);
|
||||
}
|
||||
|
||||
/**
|
||||
|
|
|
@ -0,0 +1,63 @@
|
|||
/* SPDX-License-Identifier: Apache-2.0 */
|
||||
|
||||
#include "testing/testing.h"
|
||||
|
||||
#include "BLI_kdtree.h"
|
||||
|
||||
#include <math.h>
|
||||
|
||||
/* -------------------------------------------------------------------- */
|
||||
/* Tests */
|
||||
|
||||
static void standard_test()
|
||||
{
|
||||
for (int tree_size = 30; tree_size < 500; tree_size++) {
|
||||
int tree_index = 0;
|
||||
KDTree_1d *tree = BLI_kdtree_1d_new(tree_size);
|
||||
int mask = tree_size & 31;
|
||||
bool occupied[32] = {false};
|
||||
|
||||
for (int i = 0; i < tree_size; i++) {
|
||||
int index = i & mask;
|
||||
occupied[index] = true;
|
||||
float value = fmodf(index * 7.121f, 0.6037f); /* Co-prime. */
|
||||
float key[1] = {value};
|
||||
BLI_kdtree_1d_insert(tree, tree_index++, key);
|
||||
}
|
||||
int expected = 0;
|
||||
for (int j = 0; j < 32; j++) {
|
||||
if (occupied[j]) {
|
||||
expected++;
|
||||
}
|
||||
}
|
||||
|
||||
int dedup_count = BLI_kdtree_1d_deduplicate(tree);
|
||||
EXPECT_EQ(dedup_count, expected);
|
||||
BLI_kdtree_1d_free(tree);
|
||||
}
|
||||
}
|
||||
|
||||
static void deduplicate_test()
|
||||
{
|
||||
for (int tree_size = 1; tree_size < 40; tree_size++) {
|
||||
int tree_index = 0;
|
||||
KDTree_1d *tree = BLI_kdtree_1d_new(tree_size);
|
||||
for (int i = 0; i < tree_size; i++) {
|
||||
float key[1] = {1.0f};
|
||||
BLI_kdtree_1d_insert(tree, tree_index++, key);
|
||||
}
|
||||
int dedup_count = BLI_kdtree_1d_deduplicate(tree);
|
||||
EXPECT_EQ(dedup_count, 1);
|
||||
BLI_kdtree_1d_free(tree);
|
||||
}
|
||||
}
|
||||
|
||||
TEST(kdtree, Standard)
|
||||
{
|
||||
standard_test();
|
||||
}
|
||||
|
||||
TEST(kdtree, Deduplicate)
|
||||
{
|
||||
deduplicate_test();
|
||||
}
|
Loading…
Reference in New Issue