У меня есть набор трехмерных точек, которые аппроксимируют поверхность. Однако каждая точка подвержена некоторой ошибке. Кроме того, набор точек содержит намного больше очков, чем на самом деле необходимо для представления подстилающей поверхности.
Я ищу алгоритм для создания нового (гораздо меньшего) набора точек, представляющих упрощенную, более плавную версию поверхности (извините за то, что у вас нет лучшего определения, чем "упрощенное, более плавное" ). Подстилающая поверхность не является математической, поэтому я не надеюсь подогнать набор данных к некоторой математической функции.
Вместо того, чтобы иметь дело с ним как облако точек, я бы рекомендовал триангулировать сетку с использованием триангуляции Delaunay: http://en.wikipedia.org/wiki/Delaunay_triangulation
Затем уничтожить сетку. Вы можете исследовать алгоритмы прореживания, но вы можете получить довольно хорошие быстрые и грязные результаты с помощью алгоритма, который просто объединяет соседние трис, имеющие похожие нормали.
Я думаю, вы ищете алгоритмы "Уровень детализации".
Простым для реализации является разбить объем (поверхность) на некоторое количество подтомов. Из точек в каждом субтомнике выберите репрезентативную точку (например, ближайшую к центру или ближайшую к среднему или среднюю и т.д.). используйте эти точки, чтобы перерисовать свою поверхность.
Вы можете настроить количество подтомов для увеличения/уменьшения деталей на лету.
Я подошел бы к этому, ища вершины (точки), которые мало влияют на кривизну поверхности. Найдите все стороны, выходящие из каждой вершины, и возьмем точечные произведения их пар (?). Точки, представляющие очень мелкие "холмы", будут представлять огромные углы (около 180 градусов) и иметь мелкие точечные произведения.
Тогда те вершины с наименьшими числами будут кандидатами на удаление. Вершины вокруг них затем образуют плоскость.
Или что-то в этом роде.
Google для Hugues Hoppe и его "реконструкция поверхности".
Реконструкция поверхности используется для нахождения сетчатой поверхности, соответствующей точечному облаку; однако этот метод дает много треугольников. Затем вы можете применить меш к методу сокращения, чтобы уменьшить количество полигонов, чтобы минимизировать ошибку. В качестве примера вы можете посмотреть методы декомпрессии OpenMesh.
Существует несколько различных методов упрощения модели наземных моделей, в том числе:
См. опрос:
М. Паули, М. Гросса и Л. П. Коббельта. Эффективное упрощение точечно- пробы. В Трудах конференции по визуализации02, страницы 163-170, Вашингтон, О.К., 2002. IEEE.
если вы не каким-либо образом параметризуете свою поверхность, я не уверен, как вы можете решить, какие точки несут подобную информацию (и, таким образом, могут быть выброшены).
Я думаю, вы можете выбрать кучу точек наугад, чтобы избавиться, но это не похоже на то, что вы хотите сделать.
могут быть точки рядом друг с другом (для некоторого определения "рядом" ) можно считать, что они содержат подобную информацию и поэтому сводятся к отдельным представителям для каждой такой группы.
Вы могли бы дать более подробную информацию?
Проще упростить облако точек без ограничений на сетчатые треугольники и индексы.
сглаживание и упрощение - это разные задачи. Чтобы упростить облако, вы должны сначала избавиться от артефактов шума, создав профиль вашего шума, его частотные и направленные характеристики и сделайте профиль шума по сравнению с уменьшением типа. хорошие нормальные векторы - это helfpul.
вот документ о 5-6 упрощениях с использованием команд delauney, voronoi и k ближайших соседей:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.10.9640&rep=rep1&type=pdf
Более поздняя версия с 2008 года: http://www.wseas.us/e-library/transactions/research/2008/30-705.pdf
вот последняя версия С++: https://github.com/tudelft3d/masbcpp/blob/master/src/simplify.cpp