Blender V5.3
BLI_kdtree_performance_test.cc File Reference
#include <algorithm>
#include <array>
#include <cinttypes>
#include <cmath>
#include <ctime>
#include "testing/testing.h"
#include "BLI_array.hh"
#include "BLI_function_ref.hh"
#include "BLI_index_mask.hh"
#include "BLI_kdtree.hh"
#include "BLI_kdtree_new.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_rand.hh"
#include "BLI_task_c.hh"
#include "BLI_threads.hh"
#include "BLI_time.hh"

Go to the source code of this file.

Classes

struct  blender::Distribution

Namespaces

namespace  blender
 BMesh Iterators.

Functions

static float blender::radius_for_neighbor_count (const int64_t points_num)
Benchmarks
 blender::TEST (kdtree_performance, Build)
 blender::TEST (kdtree_performance, FindNearest)
 blender::TEST (kdtree_performance, FindNearestSkipSelf)
 blender::TEST (kdtree_performance, FindNearestN)
 blender::TEST (kdtree_performance, RangeSearch)
 blender::TEST (kdtree_performance, CalcDuplicates)
Threaded Build
 blender::TEST (kdtree_performance, ThreadedBuild)
Tiny Trees

Nodes that group points by an ID build one tree per group, so trees with a handful of points are common and the cost of building one is part of every query. These measure whole workloads including the build, rather than a single query against a tree that already exists.

 blender::TEST (kdtree_performance, TinyTreesBuild)
 blender::TEST (kdtree_performance, TinyTreesFindNearestOther)
 blender::TEST (kdtree_performance, TinyTreesCalcDuplicates)
Leaf Size
 blender::TEST (kdtree_performance, KDTreeNewLeafSize)

Variables

static const std::array< int64_t, 4 > blender::POINT_COUNTS = {1000, 10000, 100000, 1000000}
static const std::array< int64_t, 5 > blender::TINY_POINT_COUNTS = {4, 16, 64, 256, 1024}
static constexpr int64_t blender::QUERY_COUNT = 100000
static constexpr int blender::NEAREST_N = 8
static constexpr double blender::NEIGHBORS_IN_RANGE = 8.0

Utilities

enum class  blender::Impl { blender::BLI , blender::New }
using blender::RunCellFn = FunctionRef<double(Impl impl, const Span<float3> positions, int64_t points_num)>
static const std::array< Impl, 2 > blender::IMPLEMENTATIONS = {Impl::BLI, Impl::New}
static const char * blender::impl_name (const Impl impl)
static Array< float3 > blender::make_query_points (const Span< float3 > positions)
static KDTree< float3 > * blender::build_bli_tree (const Span< float3 > positions)
static double blender::run_iterations (const int64_t points_num, const FunctionRef< void()> function)
static double blender::run_batched (const int64_t points_num, const FunctionRef< void()> function)
static double blender::run_queries (const Span< float3 > queries, const FunctionRef< void(const float3 &query)> query_fn)
static void blender::print_time (const double seconds)
static void blender::print_table_header (const char *title, const char *value_description, const Span< int64_t > point_counts)
static void blender::run_table (const char *title, const char *value_description, const RunCellFn run_cell, const Span< int64_t > point_counts=POINT_COUNTS, const Span< Impl > implementations=IMPLEMENTATIONS)

Point Distributions

All of these fill the unit cube, so a given radius means the same thing for each of them.

using blender::MakePointsFn = Array<float3> (*)(int64_t)
static const Distribution blender::DISTRIBUTIONS []
static Array< float3 > blender::make_random_points (const int64_t points_num)
static Array< float3 > blender::make_contiguous_points (const int64_t points_num)
static Array< float3 > blender::make_duplicate_points (const int64_t points_num)