Почему KD-деревья так чертовски медленны для поиска ближайшего соседа в наборе точек?
Я использую (новейшую) реализацию KD-дерева в CGAL для поиска ближайших соседей по наборам точек. А также Википедия и другие ресурсы, кажется, предполагают, что KD-деревья — это путь. Но почему-то они слишком медленные, и вики также предлагает их худшее время O (n), которое далеко от идеального.
[НАЧАТЬ-EDIT] Сейчас я использую «nanoflann», который примерно в 100-1000 раз быстрее, чем эквивалент в CGAL для поиска K-соседей. И я использую Intel Embree для радиопередачи, которая примерно в 100-200 раз быстрее, чем AGB-деревья CGAL.[END-EDIT]
Моя задача выглядит так:
У меня есть ОГРОМНАЯ точка, скажем, до нескольких сотен миллионов. точки!! и их распределение находится на поверхностях триангулированной геометрии (да, трассер фотонов). Таким образом, можно сказать, что их распределение в трехмерном пространстве 2D, потому что в 3D оно редкое, но плотное при взгляде на поверхности … Это может быть проблемой, верно? Потому что мне кажется, что это запускает наихудшую производительность KD-дерева, которая, вероятно, могла бы справиться гораздо лучше с трехмерными плотными наборами точек …
CGAl довольно хорош в том, что он делает, поэтому я немного сомневаюсь, что их реализация просто отстой. Их дерево AABB, которое я использую для трассировки лучей, сжигает миллиард лучей в нескольких минутах в земле … Думаю, это замечательно. Но их KD-дерево, с другой стороны, не может справиться даже с мио. точки и 250 тыс. образцов (точечные запросы) в любое разумное время …
Я придумал два решения, которые выбивают дерьмо из KD-деревьев:
1) Используйте текстурные карты для хранения фотонов в связанном списке по геометрии. Это всегда операция O (1), так как вы все равно должны сделать raycast …
2) Используйте зависимые от вида нарезанные хэш-наборы. Это чем дальше, тем грубее хэш-наборы. Таким образом, вы можете думать о растре 1024x1024x1024 в координатах NDC, но с хэш-наборами, чтобы сохранить память в редких областях. Это в основном имеет сложность O (1) и может быть эффективно распараллелено как для вставок (микро-шардинг), так и для запросов (без блокировок).
Предыдущее решение имеет тот недостаток, что его практически невозможно усреднить по спискам соседних фотонов, что важно в более темных областях, чтобы избежать шума.
Последнее решение не имеет этой проблемы и должно быть наравне с KD-деревьями, просто оно имеет O (1) производительность в худшем случае, смеется.
Так что ты думаешь? Плохая реализация KD-дерева? Если нет, то есть ли что-то «лучше», чем KD-дерево для ограниченных запросов ближайшего соседа? Я имею в виду, что ничего не имею против моего второго решения выше, но «проверенная» структура данных, которая обеспечивает аналогичную производительность, была бы лучше!
Спасибо!
Вот код (хотя и не компилируемый), который я использовал:
#include "stdafx.h"#include "PhotonMap.h"
#pragma warning (push)
#pragma warning (disable: 4512 4244 4061)
#pragma warning (disable: 4706 4702 4512 4310 4267 4244 4917 4820 4710 4514 4365 4350 4640 4571 4127 4242 4350 4668 4626)
#pragma warning (disable: 4625 4265 4371)
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Orthogonal_incremental_neighbor_search.h>
#include <CGAL/basic.h>
#include <CGAL/Search_traits.h>
#include <CGAL/point_generators_3.h>
#pragma warning (pop)
struct PhotonicPoint
{
float vec[3];
const Photon* photon;
PhotonicPoint(const Photon& photon) : photon(&photon)
{
vec[0] = photon.hitPoint.getX();
vec[1] = photon.hitPoint.getY();
vec[2] = photon.hitPoint.getZ();
}
PhotonicPoint(Vector3 pos) : photon(nullptr)
{
vec[0] = pos.getX();
vec[1] = pos.getY();
vec[2] = pos.getZ();
}
PhotonicPoint() : photon(nullptr) { vec[0] = vec[1] = vec[2] = 0; }
float x() const { return vec[0]; }
float y() const { return vec[1]; }
float z() const { return vec[2]; }
float& x() { return vec[0]; }
float& y() { return vec[1]; }
float& z() { return vec[2]; }
bool operator==(const PhotonicPoint& p) const
{
return (x() == p.x()) && (y() == p.y()) && (z() == p.z()) ;
}
bool operator!=(const PhotonicPoint& p) const
{
return ! (*this == p);
}
};
namespace CGAL
{
template <>
struct Kernel_traits<PhotonicPoint>
{
struct Kernel
{
typedef float FT;
typedef float RT;
};
};
}
struct Construct_coord_iterator
{
typedef const float* result_type;
const float* operator()(const PhotonicPoint& p) const
{
return static_cast<const float*>(p.vec);
}
const float* operator()(const PhotonicPoint& p, int) const
{
return static_cast<const float*>(p.vec+3);
}
};
typedef CGAL::Search_traits<float, PhotonicPoint, const float*, Construct_coord_iterator> Traits;
typedef CGAL::Orthogonal_incremental_neighbor_search<Traits> NN_incremental_search;
typedef NN_incremental_search::iterator NN_iterator;
typedef NN_incremental_search::Tree Tree;struct PhotonMap_Impl
{
Tree tree;
PhotonMap_Impl(const PhotonAllocator& allocator) : tree()
{
int counter = 0, maxCount = allocator.GetAllocationCounter();
for(auto& list : allocator.GetPhotonLists())
{
int listLength = std::min((int)list.size(), maxCount - counter);
counter += listLength;
tree.insert(std::begin(list), std::begin(list) + listLength);
}
tree.build();
}
};
PhotonMap::PhotonMap(const PhotonAllocator& allocator)
{
impl = std::make_shared<PhotonMap_Impl>(allocator);
}
void PhotonMap::Sample(Vector3 where, float radius, int minCount, std::vector<const Photon*>& outPhotons)
{
NN_incremental_search search(impl->tree, PhotonicPoint(where));
int count = 0;
for(auto& p : search)
{
if((p.second > radius) && (count > minCount) || (count > 50))
break;
count++;
outPhotons.push_back(p.first.photon);
}
}
Решение
По моему опыту, качество реализации, к сожалению, сильно различается. Я, однако, никогда не смотрел на реализацию CGAL.
Наихудший случай для k-d-дерева обычно происходит, когда из-за постепенных изменений он становится слишком несбалансированный, и должен быть перезагружен.
Однако, как правило, такие деревья наиболее эффективны, когда вы не знаете распределение данных.
В вашем случае это звучит так, как будто простой подход на основе сетки может быть лучшим выбором. Если вы хотите, вы можете считать текстуру плотной двумерной сеткой. Поэтому, возможно, вы можете найти 2-мерную проекцию, где сетка работает хорошо, а затем пересечь эту проекцию.
Другие решения
Ответы — это не место, чтобы задавать вопросы, но ваш вопрос — не вопрос, а утверждение, что kd-дерево CGAL — отстой.
Чтение 1,8 млн. Точек модели геологических данных и вычисление 50 самых близких точек для каждой из этих точек дает следующую производительность на моем Dell Precision, Windows7, 64-бит, VC10:
- чтение точек из файла: 10 сек
- Построение дерева 1,3 сек
- 1,8 миллиона запросов, сообщающих о 50 ближайших точках: 17 секунд
У вас есть похожие выступления. Вы ожидаете, что kd-дерево будет быстрее?
Также мне интересно, где находятся ваши точки запроса, это близко к поверхности или близко к каркасу.
Несколько месяцев назад я провел некоторое исследование быстрых реализаций KD-дерева, и я согласен с Anony-Mousse, что качество (и «вес» библиотек) сильно варьируется. Вот некоторые из моих выводов:
kdtree2 Это малоизвестная и довольно простая реализация дерева KD, которая, как мне показалось, довольно быстрая для задач 3D, особенно если вы позволяете ей копировать и пересортировать ваши данные. Кроме того, он небольшой и его очень легко встроить и адаптировать. Вот это статья о реализации, выполненная автором (не стоит откладывать упоминание Фортрана в заголовке). Это библиотека, которую я использовал в конечном итоге. Мои коллеги сравнили его скорость с 3D-точками VLFeat-х KD-деревья и другая библиотека, которую я не помню (многие FLANN, см. Ниже), и она победила.
Flann имеет репутацию быстрого и часто используется и рекомендуется в последнее время. Он нацелен на случай более высокой размерности, где он предлагает приблизительные алгоритмы, но также используется в Библиотека облаков точек которая занимается проблемами 3D.
Я не экспериментировал с CGAL, так как обнаружил, что библиотека слишком тяжелая. Я согласен, что CGAL имеет хорошую репутацию, но я чувствую, что иногда он страдает от чрезмерной сложности.
Взгляните на библиотеку ApproxMVBB под лицензией MPL:
https://github.com/gabyx/ApproxMVBB:
Реализация kdTree должна быть сопоставима с PCL (FLANN) и может быть даже быстрее. (С моей реализацией тесты с PCL казались быстрее!)
Diclaimer: Я владелец этой библиотеки, и ни в коем случае эта библиотека не претендует на ускорение, а серьезные тесты производительности еще не проводились, но я успешно использую эту библиотеку в гранулированной динамике твердого тела, где скорость король!
Тем не менее, эта библиотека очень мала, а реализация kdTree очень универсальна (см. Примеры) и позволяет вам создавать собственные эвристики разбиения и другие интересные вещи :-).
Реализованы те же улучшения и соображения, что и в nanoflann (прямой доступ к данным и т. Д., Общие данные, n-мерные) … (см. Заголовок KdTree.hpp).
Некоторые обновления по времени:
Пример kdTreeFilteringсодержит несколько небольших тестов:
Загружен стандартный кролик с 35947 пунктами (полностью рабочий пример в репо из коробки):
Результаты, достижения:
Bunny.txt
Loaded: 35947 points
KDTree:: Exotic point traits , Vector3* + id, start: =====
KdTree build took: 3.1685ms.
Tree Stats:
nodes : 1199
leafs : 600
tree level : 11
avg. leaf data size : 29.9808
min. leaf data size : 0
max. leaf data size : 261
min. leaf extent : 0.00964587
max. leaf extent : 0.060337
SplitHeuristics Stats:
splits : 599
avg. split ratio (0,0.5] : 0.5
avg. point ratio [0,0.5] : 0.22947
avg. extent ratio (0,1] : 0.616848
tries / calls : 599/716 = 0.836592
Neighbour Stats (if computed):
min. leaf neighbours : 6
max. leaf neighbours : 69
avg. leaf neighbours : 18.7867
(Built with methods: midpoint, no split heuristic optimization loop)Saving KdTree XML to: KdTreeResults.xml
KDTree:: Simple point traits , Vector3 only , start: =====
KdTree build took: 18.3371ms.
Tree Stats:
nodes : 1199
leafs : 600
tree level : 10
avg. leaf data size : 29.9808
min. leaf data size : 0
max. leaf data size : 306
min. leaf extent : 0.01
max. leaf extent : 0.076794
SplitHeuristics Stats:
splits : 599
avg. split ratio (0,0.5] : 0.448302
avg. point ratio [0,0.5] : 0.268614
avg. extent ratio (0,1] : 0.502048
tries / calls : 3312/816 = 4.05882
Neighbour Stats (if computed):
min. leaf neighbours : 6
max. leaf neighbours : 43
avg. leaf neighbours : 21.11
(Built with methods: midpoint, median,geometric mean, full split heuristic optimization)
Lucy.txt модель с 14 миллионами очков:
Loaded: 14027872 points
KDTree:: Exotic point traits , Vector3* + id, start: =====
KdTree build took: 3123.85ms.
Tree Stats:
nodes : 999999
leafs : 500000
tree level : 25
avg. leaf data size : 14.0279
min. leaf data size : 0
max. leaf data size : 159
min. leaf extent : 2.08504
max. leaf extent : 399.26
SplitHeuristics Stats:
splits : 499999
avg. split ratio (0,0.5] : 0.5
avg. point ratio [0,0.5] : 0.194764
avg. extent ratio (0,1] : 0.649163
tries / calls : 499999/636416 = 0.785648
(Built with methods: midpoint, no split heuristic optimization loop)
KDTree:: Simple point traits , Vector3 only , start: =====
KdTree build took: 7766.79ms.
Tree Stats:
nodes : 1199
leafs : 600
tree level : 10
avg. leaf data size : 11699.6
min. leaf data size : 0
max. leaf data size : 35534
min. leaf extent : 9.87306
max. leaf extent : 413.195
SplitHeuristics Stats:
splits : 599
avg. split ratio (0,0.5] : 0.297657
avg. point ratio [0,0.5] : 0.492414
avg. extent ratio (0,1] : 0.312965
tries / calls : 5391/600 = 8.985
Neighbour Stats (if computed):
min. leaf neighbours : 4
max. leaf neighbours : 37
avg. leaf neighbours : 12.9233
(Built with methods: midpoint, median,geometric mean, full split heuristic optimization)
Позаботьтесь о толковании! и посмотрите на настройки, использованные в примере файл.
Однако, по сравнению с результатами других людей: ~ 3100 мс для 14 * 10⁶ баллов довольно гладко 🙂
Используемый процессор: Intel® Core ™ i7 CPU 970 @ 3,20 ГГц × 12, 12 ГБ ОЗУ
Если kdtree быстрое для небольших наборов, но «медленное» для больших (> 100000?) Наборов, возможно, вы страдаете от очистки кэшей процессора. Если верхние несколько узлов чередуются с редко используемыми конечными узлами, то вы поместите меньше интенсивно используемых узлов в кэш-память (и) процессора. Это может быть улучшено путем минимизации размера узлов и тщательного размещения узлов в памяти … но в конечном итоге вы все равно будете сбрасывать достаточное количество узлов. Вы можете получить доступ к основной памяти, являющейся узким местом.
Valgrind говорит мне, что одна версия моего кода на 5% меньше инструкций, но я считаю, что секундомер, когда он говорит мне, что примерно на 10% медленнее для того же ввода. Я подозреваю, что Вальгринд, выполнив полную симуляцию кэша, скажет мне правильный ответ.
Если вы многопоточны, вы можете поощрять потоки выполнять поиск в аналогичных областях для повторного использования кэша … что предполагает использование одного многоядерного процессора — несколько процессоров могут захотеть противоположный подход.
Подсказка: вы упаковываете в память больше 32-битных индексов, чем 64-битных указателей.