#c #tree #structure
#c #дерево #структура
Вопрос:
Я искал повсюду (в основном в Google) быстрый, эффективный, шаблонный (ie. со свойствами, подобными STL) реализация octree, безуспешно. Я хочу использовать это в контексте графика 3D-сцены.
Существует ли такая вещь, или люди обычно создают свои собственные? Я надеюсь, что мои друзья из stackoverflow знают, где ее найти.
Комментарии:
1. В целом, я чувствую, что если вам нужно самое быстрое решение, вам нужно создать свое собственное, потому что варианты использования сильно различаются: от восьмиярусных, хранящих точки, восьмиярусных, хранящих элементы с размерами, свободных восьмиярусных, которые более эффективно хранят элементы с размерами, SVO для воксельных данных, восьмиярусных, которые используют SPFP, восьмиярусных, которые используют DPFP, восьмиярусных, которые используют целые числа для использования большего количества побитовых операций и т.д. и т.п. И т.п. Список можно продолжать и дальше, и если бы вы нашли единственное универсальное octree, которое очень эффективно удовлетворяло всем возможным критериям, его использование, вероятно, было бы ужасным.. как шаблон класса политики…
2. … с 16 различными политиками, которые можно указать в качестве параметров шаблона, например, в этот момент простое использование такой неуклюжей вещи может занять больше времени, чем создание собственной или поиск простого, но эффективного примера чего-то более узко применимого, что ближе к вашим потребностям, и настройка его по мере необходимости. Общие структуры данных, как правило, хорошо работают для более простых вещей, таких
std::vectorкак абстрагирование идеи динамического массива переменного размера с небольшим снижением производительности (единственная причина, по которой я могу думать, что кто-то хочет чего-то другого […]3. […] это если они хотят другую политику перераспределения / резервирования, например, возможность контролировать, сколько памяти вектор перераспределяет, когда она заполнена, или использовать целые числа размером меньше 64 бит для хранения размера и емкости) — очень суетливая штука. Но по мере того, как вы приближаетесь к более сложным структурам, таким как пространственные индексы, и особенно к структурам данных, которые, как правило, бывают самых разнообразных форм и размеров в зависимости от предметной области, в которой они используются, становится довольно громоздко пытаться искать идеальную вещь общего назначения, поскольку на этом этапе «общего назначения» и «сделано для моей цели» несовместимы.
Ответ №1:
-
http://nomis80.org/code/octree.html
Это мое любимое. Это GPL и у него есть собственная домашняя страница, поэтому он предназначен для использования другими. В нем есть документация Doxygen, и авторы отвечают на вопросы.
-
http://www.flipcode.com/archives/Octree_Implementation .shtml
Эта реализация не является шаблонной. В коде больше комментариев, чем в любом другом, который я видел, так что это может быть более полезным, если вы пытаетесь выяснить, как работают octrees.
Комментарии:
1. Код GPL на самом деле не предназначен для использования другими. По крайней мере, не в реальном мире. 😉
Ответ №2:
Также недавно выпущено:http://www.openvdb.org
Формат иерархии томов от Dreamworks.
Ответ №3:
Проверьте это: http://svn.pointclouds.org/pcl/trunk/octree
Обновленная ссылка:https://github.com/PointCloudLibrary/pcl/tree/master/octree
Комментарии:
1. Спасибо. Интересно, но, похоже, недокументировано.
2. Моя ошибка. Нашел документацию: docs.pointclouds.org/group__octree.html .
3. Кроме того, существует test/test_octree.cpp чтобы посмотреть на использование.
4. Есть идеи о том, как его использовать, не включая и не компилируя всю библиотеку point cloud?