Алгоритм создания треугольной сетки из облака точек

В некоторой программе моделирования мы генерируем поверхности объектов в терминах точек, каждая точка имеет 3D-координаты и вектор, который представляет нормаль к поверхности в этой точке. Для целей визуализации мы хотели бы создать сетку, состоящую из треугольников; каждая из трех близких точек образует один треугольник с его нормальным. Затем мы можем отправить эту информацию в некоторые стандартные программы визуализации, которые отображают поверхность как VMD (Visual Molecular Dynamics).

Мы задаемся вопросом, который является самым быстрым/доступным алгоритмом для этого.

Ответ 1

Взгляните на Джонатан Шевчук, особенно на его (вместе со своими коллегами) известные работы и реализации:

Существует также быстрая реализация несортированных точечных облаков, реализованных в библиотеке Point Cloud (PCL). Проверьте их презентацию на Быстрая триангуляция неупорядоченных точечных облаков.

Ответ 2

Обратите внимание, что триангуляции Delaunay могут не соответствовать вашему приложению в том, что триангуляции Delaunay не подходят для истинных 3D-проблем (т.е. где точки хорошо распределены в R3). Они более подходят для задач двумерного многообразия (т.е. Местности и т.д.).

Чтобы создать поверхности в R3, посмотрите на работу Hugues Hoppe и его "реконструкцию поверхности".

Реконструкция поверхности используется для нахождения сетчатой поверхности, соответствующей точечному облаку; однако этот метод дает высокие значения треугольников. Если это проблема, вы можете применить mesh метод сокращения, чтобы уменьшить количество полигонов, чтобы свести к минимуму ошибку. В качестве примера вы можете посмотреть методы декомпрессии OpenMesh.

Hugues Hoppe

OpenMesh

Ответ 3

Алгоритм Миша Каждан Пуассон может хорошо работать с вашими данными. Его страница программного обеспечения здесь. Обратите внимание, что существует также версия CGAL. Руководство здесь и готово использовать демонстрацию Windows здесь (при условии вы установили эти dlls).