8#include "testing/testing.h"
40 for (
const int i : indices) {
57 positions[i++] =
float3(
float(
x),
float(
y),
float(
z));
93 float distance_sq = -1.0f;
95 EXPECT_FLOAT_EQ(distance_sq, 1.0f);
110 for (
const float3 &query : queries) {
112 float distance_sq = -1.0f;
115 EXPECT_FLOAT_EQ(distance_sq, expected.
first().distance_sq);
128 ASSERT_EQ(expected.
first().index, i);
130 [&](
const int other) {
return other != i; });
136 [](
const int other) {
return other % 2 == 0; });
140 for (
const Nearest &nearest : expected) {
141 if (nearest.index % 2 == 0) {
155 for (
const float3 &query : queries) {
162 EXPECT_FLOAT_EQ(nearest[i].distance_sq, expected[i].distance_sq);
164 EXPECT_LE(nearest[i - 1].distance_sq, nearest[i].distance_sq);
185 for (
const float3 &query : queries) {
186 for (
const float radius : {0.05f, 0.2f, 2.0f}) {
189 if (nearest.distance_sq <= radius * radius) {
198 EXPECT_FLOAT_EQ(found[i].distance_sq, expected[i].distance_sq);
208 std::ranges::sort(visited);
209 ASSERT_EQ(visited.
size(), expected.
size());
211 for (
const Nearest &nearest : expected) {
212 expected_indices.
append(nearest.index);
214 std::ranges::sort(expected_indices);
225 const float3 center(1.0f, 1.0f, 1.0f);
239 EXPECT_FLOAT_EQ(nearest.distance_sq, 1.0f);
251 EXPECT_FLOAT_EQ(distance_sq, 0.25f);
253 EXPECT_TRUE(nearest == 4 || nearest == 13) <<
"found point " << nearest;
257 EXPECT_FLOAT_EQ(nearest_n[0].distance_sq, 0.25f);
258 EXPECT_FLOAT_EQ(nearest_n[1].distance_sq, 0.25f);
273 for (
const float3 &query : queries) {
277 float distance_sq = -1.0f;
281 EXPECT_FLOAT_EQ(distance_sq, expected.
first().distance_sq);
291 for (
const Nearest &nearest : found) {
293 EXPECT_LE(nearest.distance_sq, 0.3f * 0.3f);
324 positions[i] = i < 60 ?
float3(1.0f, 1.0f, 1.0f) :
float3(
float(i), 0.0f, 0.0f);
335 EXPECT_FLOAT_EQ(nearest[i].distance_sq, 0.0f);
359 const bool pairwise =
true)
361 const float range_sq = range * range;
364 for (
const int i : indices) {
365 const int target = duplicates[i];
366 if (target == -1 || target == i) {
372 <<
"point " << i <<
" merged into " << target <<
" beyond the range";
374 EXPECT_EQ(duplicates[target], target) <<
"point " << i <<
" merged into a merged point";
383 for (
const int i : indices) {
384 if (duplicates[i] != -1) {
387 for (
const int j : indices) {
388 if (j == i || duplicates[j] != -1) {
392 <<
"points " << i <<
" and " << j <<
" are in range but neither was merged";
399 for (
const int points_num : {10, 100, 2000}) {
403 for (
const float range : {0.001f, 0.02f, 0.05f, 0.2f, 5.0f}) {
407 SCOPED_TRACE(std::to_string(points_num) +
" points, range " + std::to_string(range));
419 positions[i] =
float3(
float(i % 10), 0.0f, 0.0f);
432 ASSERT_NE(duplicates[i], -1) <<
"point " << i <<
" was left out of a cluster";
434 targets_num += duplicates[i] == i;
446 positions[i] =
float3(
float(i % 3), 0.0f, 0.0f);
508 EXPECT_EQ(duplicates[i], i) <<
"preset point " << i <<
" was merged into another point";
523 for (
const float range : {0.02f, 0.05f, 0.2f}) {
524 SCOPED_TRACE(
"range " + std::to_string(range));
533 if (duplicates[i] != -1) {
534 EXPECT_GE(i, duplicates[i]) <<
"point " << i <<
" merged into a higher index";
570 for (
const int i : indices) {
571 if (duplicates[i] != -1) {
572 EXPECT_GE(i, duplicates[i]) <<
"point " << i <<
" merged into a higher index";
586 tree, 0.1f, indices.
as_span(), from_indices);
607 for (
const float3 &query : queries) {
608 int expected_index = -1;
609 float expected_distance_sq =
FLT_MAX;
612 if (distance_sq < expected_distance_sq) {
613 expected_distance_sq = distance_sq;
618 float distance_sq = -1.0f;
620 EXPECT_FLOAT_EQ(distance_sq, expected_distance_sq);
630 for (
const int threads_num : {1, 2, 3, 8}) {
643 EXPECT_EQ(other_found, found) << threads_num <<
" threads";
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
IndexRange index_range() const
void fill(const T &value) const
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
constexpr IndexRange()=default
int find_in_radius(const T &position, const value_type radius, Vector< Nearest > &r_nearest) const
void foreach_in_radius(const T &position, const value_type radius, Fn &&fn) const
int find_nearest(const T &position, value_type *r_distance_sq=nullptr) const
int count_in_radius(const T &position, const value_type radius) const
int find_nearest_filtered(const T &position, Filter &&filter, value_type *r_distance_sq=nullptr) const
int find_nearest_n(const T &position, MutableSpan< Nearest > r_nearest) const
void append(const T &value)
IndexRange index_range() const
MutableSpan< T > as_mutable_span()
Span< T > as_span() const
#define EXPECT_GT(result, expect)
#define EXPECT_LT(result, expect)
#define EXPECT_GE(result, expect)
#define EXPECT_NE(result, expect)
#define EXPECT_TRUE(result)
#define EXPECT_LE(result, expect)
void fill_index_range(MutableSpan< T > span, const T start=0)
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
static Array< float3 > grid_points(const int side)
static Array< float3 > random_points(const int points_num, const int seed=0)
static void check_duplicates(const Span< float3 > positions, const Span< int > indices, const float range, const Span< int > duplicates, const int found, const bool pairwise=true)
KDTreeNew< float3 >::Nearest Nearest
TEST(any_virtual, DefaultConstructor)
static Vector< int > all_indices(const int points_num)
static Vector< Nearest > brute_force_sorted(const Span< float3 > positions, const Span< int > indices, const float3 &position)
void BLI_system_num_threads_override_set(int num)
void BLI_task_scheduler_exit()
VecBase< float, 2 > float2
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void BLI_task_scheduler_init(bool use_flush_denormals_to_zero=true)
VecBase< float, 3 > float3