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

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

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


algorithm point geometry mesh
person Open the way    schedule 24.10.2011    source источник

Ответы (3)


arrow_upward
14
arrow_downward

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

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

person mloskot    schedule 24.10.2011
comment
Магия в gp3.reconstruct (triangles) случае PCL - увы, в презентации она не раскрыта. - person wcochran; 17.06.2019

arrow_upward
11
arrow_downward

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

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

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

Хьюг Хоппе

OpenMesh

person Throwback1986    schedule 25.10.2011

arrow_upward
6
arrow_downward

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

person sloriot    schedule 25.10.2011