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

Question

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

Интересно, какой самый быстрый / доступный алгоритм для этого?

Answer 1

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

• Потоковое вычисление триангуляций Делоне

• Двумерный генератор качественной сетки и Делоне Triangulator

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

Answer 2

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

Чтобы сгенерировать поверхности в R3, посмотрите на работу Хьюга Хоппе и его работу по «реконструкции поверхности».

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

Hugues Hoppe

OpenMesh

Answer 3

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