Генерация сетки из точек с координатами x, y и z

Проблема: создание сетки из трехмерных точек (с координатами x, y и z).

У меня есть точки в трехмерном пространстве (с координатами x, y и z), вы можете увидеть их на рисунке 1.
На выходе получится изображение 2 или изображение 3, или изображение 4. Короче говоря, это будет меш. Материал на нем может быть предоставлен, если у меня есть сетка.

Я видел, как многие люди говорят, что триангуляции Делоне или ограниченные триангуляции Делоне помогут мне в генерации сетки, но в основном я обнаружил, что это реализация в 2D точках (только с координатами x и Y).

Но моя проблема в том, что у меня есть очки в 3D, как вы можете видеть на рисунке 1.

Будут ли триангуляции Делоне или ограниченные триангуляции Делоне работать с 3D-точками? Если да, то как? Или мне нужно найти другой алгоритм для создания сетки из трехмерных точек?

Примечание: одно хорошее объяснение триангуляции Делоне для 2D-точек можно найти здесь

Ответ 1

вот некоторые другие хорошие ссылки для генерации сетки и связанной с ней работы.

• TetGen: Тетраэдрический сетчатый генератор качества http://wias-berlin.de/software/tetgen/

• CGal - Библиотека алгоритмов вычислительной геометрии http://www.cgal.org/. http://www.cgal.org/Manual/latest/doc_html/cgal_manual/packages.html#Pkg:Triangulation3. http://www.cgal.org/Manual/latest/doc_html/cgal_manual/contents.html#part_VI.
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Surface_reconstruction_points_3/Chapter_main.html.
3D Surface Mesh Generation - http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Surface_mesher/Chapter_main.html

• GTSLibrary - GNU Triangulated Surface Library. http://gts.sourceforge.net/index.html

• Джонатан Шевчук - http://www.cs.berkeley.edu/~jrs/ http://www.cs.cmu.edu/~quake/robust.html

• VTK: Инструмент визуализации (VTK) представляет собой свободно распространяемую программную систему с открытым исходным кодом http://www.vtk.org/.

• Объем и поверхностное зацепление - http://www.cse.ohio-state.edu/~tamaldey/mesh.htm.

• Poly2Tri: Библиотека CDT с открытым исходным кодом http://code.google.com/p/poly2tri/.

• Инструменты CM2Mesh - http://www.computing-objects.com/index.php.

• Адаптивная тесселяция - http://fluxionsdividebyzero.com/p1/math/geometry/g046.html#_3D

• CUBIT - Набор инструментов CUBIT Geometry and Mesh Generation. http://cubit.sandia.gov/index.html

• Геометрия в действии - http://www.ics.uci.edu/~eppstein/geom.html

• SlimDX - SlimDX - это бесплатная среда с открытым исходным кодом, которая позволяет разработчикам легко создавать приложения DirectX с использованием технологий .NET, таких как С#, VB http://slimdx.org/

Ответ 2

Трехмерная треугольная треугольная обработка приведет к (трёхмерному) объему сетки. Я предполагаю, что вы хотите (2D) поверхностную сетку, встроенную в 3D, которая аппроксимирует данный набор точек.

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

Для ориентированного множества точек с небольшим шумом и без выбросов вы можете рассмотреть восстановление поверхности Пуассона (например, в Майкл Каждан, М. Болито и Хьюг Хоппе. Поверхностная реконструкция Пуассона. В Symp. по обработке геометрии, страницы 61-70, 2005.).
Обратите внимание, что вы можете предварительно обработать свои данные для полного заполнения требований, см., Например, Обычная оценка. Вот библиотека С++, реализующая Poisson Surface Reconstruction (с хорошими пояснениями): CGAL Surface Reconstruction from Point Sets
Для данных рассеянных точек см., например, Ohtake, Y.; Беляев А. и Зейдель Х. П. Многомасштабный подход к интерполяции трехмерных рассеянных данных с компактно поддерживаемыми базисными функциями Shape Modeling International, 2003, 2003, 153-161. Он использует иерархический подход для создания нескольких уровней интерполяции.
Другой подход для сильно неравномерных или шумных рассеянных данных Zhao, H.-K.; Osher, S. and Fedkiw, R. Быстрое восстановление поверхности с использованием метода набора уровней Вариационные методы и методы набора уровней в Computer Vision, 2001. Труды. IEEE, 2001, 194-201. Он использует вариационные методы и PDE (особенно методы набора уровней).

Ответ 3

ENIGMA. Разработанный в основном для решения PDE, он также имеет ограниченный генератор поверхности и объема. Все еще не уверен, собирается ли выпустить его в будущем с открытым исходным кодом.

https://www.sites.google.com/site/billyaraujo/enigma/volume-mesh-generation