Я столкнулся с этой дилеммой уже несколько месяцев и провел исчерпывающее исследование.
Алгоритмы
В основном есть две категории алгоритмов: вычислительная геометрия и неявные поверхности.
Вычислительная геометрия
Они соответствуют сетке на существующих точках.
Вероятно, наиболее известным алгоритмом этой группы является powercrust , потому что он теоретически обоснован - он гарантирует водонепроницаемость сетки.
Ball Pivoting запатентована IBM. Кроме того, он не подходит для облаков с различной плотностью точек.
Неявные функции
Один устанавливает неявные функции на pointcloud, затем использует алгоритм, подобный движущемуся кубу, чтобы извлечь нулевое множество функции в сетку.
Методы в этой категории отличаются в основном различными неявными функциями.
Пуассона , Хоппе и MPU являются наиболее известными алгоритмами в этой категории. Если вы новичок в этой теме, я рекомендую прочитать тезис Хоппе, это очень объяснительно.
Алгоритмы этой категории обычно могут быть реализованы так, чтобы они могли очень эффективно обрабатывать огромные входные данные, и можно масштабировать их <-> скорость компромисса. Их не беспокоит шум, разная плотность точек, дырки. Недостатком их является то, что они требуют последовательно ориентированных нормалей поверхности в точках ввода.
Реализация
Вы найдете небольшое количество бесплатных реализаций. Однако это зависит от того, собираетесь ли Вы интегрировать его в свободное программное обеспечение (в этом случае для вас приемлема лицензия GPL) или в коммерческое программное обеспечение (в этом случае вам нужна более либеральная лицензия). Последнее очень редко.
Один находится в VTK . Я подозреваю, что его сложно интегрировать (документация не предоставляется бесплатно), он имеет странную, слишком сложную архитектуру и не предназначен для высокопроизводительных приложений. Также есть некоторые ограничения для разрешенных входных облаков точек.
Взгляните на эту реализацию Пуассона, и после этого поделитесь со мной своим опытом, пожалуйста.
Также:
здесь - несколько высокопроизводительных алгоритмов, среди которых реконструкция поверхности.
CGAL - это знаменитая 3d-библиотека, но она бесплатна только для бесплатных проектов.
Meshlab - известное приложение с лицензией GPL.
Также (добавлено в августе 2013 г.):
Библиотека PCL имеет модуль , предназначенный для реконструкции поверхности, и находится в активной разработке (и является частью Google Summer of Code). Поверхностный модуль содержит ряд различных алгоритмов реконструкции. PCL также имеет возможность для оценки нормалей поверхности, в случае, если вы не предоставили их вместе с вашими точечными данными, эту функцию можно найти в функциях module . PCL выпущен на условиях лицензии BSD и является программным обеспечением с открытым исходным кодом, он бесплатный для коммерческого и исследовательского использования.