Я пытаюсь выяснить, какие алгоритмы существуют для восстановления поверхности из данных 3D-диапазона. На первый взгляд кажется, что алгоритмы шарового шарнира (BPA) и поверхностная реконструкция Пуассона являются более установленными методами?
Я столкнулся с этой дилеммой уже несколько месяцев и сделал исчерпывающие исследования.
В основном существуют две категории алгоритмов: геометрия вычислений и неявные поверхности.
Они соответствуют сетке в существующих точках.
Вероятно, самый известный алгоритм этой группы powercrust, потому что он теоретически обоснован - он гарантирует водонепроницаемую сетку.
Ball Pivoting запатентован IBM. Кроме того, он не подходит для точечных облаков с различной точечной плотностью.
Один помещает неявные функции в pointcloud, а затем использует алгоритм, похожий на похожий на кубик, для извлечения нулевого набора функции в сетку.
Методы в этой категории отличаются главным образом различными неявными функциями.
Пуассон, Hoppe's, и MPU - самые известные алгоритмы в этой категории. Если вы новичок в этой теме, я рекомендую прочитать тезис Хоппе, это очень объяснительно.
Алгоритмы этой категории обычно могут быть реализованы так, чтобы они могли обрабатывать огромные входы очень эффективно, и можно масштабировать их соотношение качества ↔ speed. Они не нарушаются шумом, различной точечной плотностью, дырками. Недостатком их является то, что они требуют последовательно ориентированных нормалей поверхности в входных точках.
Вы найдете небольшое количество бесплатных реализаций. Однако это зависит от того, собираетесь ли вы интегрировать его в бесплатное программное обеспечение (в этом случае лицензия GPL приемлема для вас) или в коммерческое программное обеспечение (в этом случае вам нужна более либеральная лицензия). Последнее очень редко.
Один находится в VTK. Я подозреваю, что это трудно интегрировать (документация не доступна бесплатно), у нее странная, сложная архитектура и не предназначена для высокопроизводительных приложений. Также имеет некоторые ограничения для допустимых входных точек.
Взгляните на эту реализацию Poisson, и после этого поделитесь своим опытом со мной, пожалуйста.
также: здесь - это несколько высокопроизводительных алгоритмов, с поверхностной реконструкцией среди них.
CGAL - известная 3d-библиотека, но она бесплатна только для бесплатных проектов. Meshlab - известное приложение с GPL.
Также (Добавлено в августе 2013 года): В библиотеке PCL есть модуль, посвященный реконструкции поверхности, и в активной разработке (и является частью Google Summer of Code). Поверхностный модуль содержит ряд различных алгоритмов реконструкции. PCL также имеет возможность оценивать нормали поверхности, если вы не имеете их, снабженных вашими точечными данными, эту функциональность можно найти в функциях . PCL выпускается в соответствии с условиями лицензии BSD и является программным обеспечением с открытым исходным кодом, оно бесплатное для коммерческих и исследовательских целей.
Если вы хотите сделать некоторые прямые эксперименты с различными алгоритмами восстановления поверхности, вы должны попробовать MeshLab, сетка -процессорная система, она является открытым исходным кодом и содержит реализации многих ранее упомянутых алгоритмов восстановления поверхности, таких как:
Источники защищены GPL, поэтому вы не можете использовать их в коммерческом проекте с закрытым исходным кодом, но очень важно получить правильное представление о свойствах различных алгоритмов восстановления поверхности (насколько они чувствительны к шуму, скорость, устойчивость к выбросам, как они сохраняют мелкие детали и т.д.), прежде чем приступить к реализации одного из них.
Вы можете начать изучать некоторые недавние работы в этой области - в настоящее время что-то вроде Быстрая низкоскоростная потоковая MLS-реконструкция точечно-выборочных поверхностей Джанмауро Куккуру, Энрико Гобетти, Фабио Мартон, Ренато Паджарола и Руджеро Пинтуса. Его цитаты помогут вам быстро пройти литературу.
Пока я не представлял собой сетку, экс-коллега рекомендовал мне эту ссылку к исходному коду для метода тонких пластин:
Кто-нибудь попробовал?
Не уверен, что это правильно для вашего дела, так как кажется странным, что вы его пропустили, но маршевые кубы обычно упоминаются в случаях как они.
Здесь на GitHub, это открытый Mesh Processing Library в С++ Dr. Hugues Hoppe, в котором программа восстановления поверхности Recon является хорошим вариантом для вашей проблемы...
Вам может быть интересно Alpha Shapes.
Инструмент 3D Delaunay с помощью геометрических инструментов. Этот инструмент используется DirecX и OpenGL. К сожалению, вам может потребоваться купить книгу, чтобы увидеть фактический пример кода библиотеки. Вы все еще читаете код и выясняете.
Matlab также представил инструмент восстановления поверхности, используя Delaunay, класс delaunayTriangulation.
Поскольку у меня тоже была эта проблема, я разработал и реализовал свой собственный алгоритм облачной корозии облаков. Источники, а также документацию можно найти на github.com: https://github.com/ricebean-net/PointCloudCrust. Алгоритм реализован на Java.
Может быть, это может вам помочь. Вы также можете найти короткий python script на странице, который иллюстрирует, как использовать библиотеку. Получайте удовольствие!