Алгоритм для упрощения 3-й поверхности?
У меня есть ряд 3-х точек, которые приближают поверхность. Каждая точка, однако, подвергается некоторой ошибке. Кроме того, набор точек содержат намного больше точек, чем на самом деле необходимо для представления базовой поверхности.
То, что я ищу, является алгоритмом для создания нового (намного меньшего) набора точек, представляющего упрощенную, более гладкую версию поверхности (прощение за то, что не имелось лучшее определение, чем "упрощенный, более гладкий"). Базовая поверхность не является математической, таким образом, я не надеюсь соответствовать набору данных к некоторой математической функции.
5 ответов
Вместо того, чтобы работать с ним как с облаком точек, я бы рекомендовал триангулировать сетку с помощью триангуляции Делоне: http://en.wikipedia.org/wiki/Delaunay_triangulation
Затем уничтожить сетку. Вы можете исследовать алгоритмы прореживания, но вы можете получить довольно хорошие быстрые и грязные результаты с помощью алгоритма, который просто объединяет соседние трис, имеющие похожие нормали.
Я бы подошел к этому, ища вершины (точки), которые мало влияют на кривизну поверхности. Найдите все стороны, выходящие из каждой вершины, и возьмите скалярные произведения пар (?) Из них. Точки, представляющие очень мелкие «холмы», будут иметь огромные углы (около 180 градусов) и иметь небольшие точечные произведения.
Тогда те вершины с наименьшими номерами будут кандидатами на удаление. Вершины вокруг них образуют плоскость.
Или что-то в этом роде.
Google для Хьюга Хоппе и его работы по "реконструкции поверхности".
Реконструкция поверхности используется для нахождения поверхности с сеткой, соответствующей облаку точек; однако этот метод дает партии треугольников. Затем вы можете применить технику уменьшения сетки, чтобы уменьшить количество полигонов и минимизировать ошибки. В качестве примера вы можете взглянуть на методы децимации OpenMesh.
Я думаю, вы ищете алгоритмы "уровня детализации".
Простой алгоритм состоит в том, чтобы разбить ваш объем (поверхность) на некоторое количество подобъемов. Из точек каждого под-объема выберите репрезентативную точку (например, ближайшую к центру, или ближайшую к среднему, или среднюю и т.д.). Используйте эти точки для перерисовки поверхности.
Вы можете изменять количество суб-объемов для увеличения/уменьшения детализации на лету.
если вы не параметрируете поверхность каким-то образом, я не уверен, как вы можете решить, какие точки несут аналогичную информацию (и, следовательно, могут быть отброшены).
Наверное, можно выбрать кучу точек наугад, чтобы избавиться от них, но это не похоже на то, что вы хотите сделать.
возможно, точки, расположенные рядом друг с другом (при некотором определении понятия "рядом"), можно считать содержащими сходную информацию, и таким образом свести к единичным представителям для каждой такой группы.
не могли бы вы дать больше деталей?