параметризация поверхности

[sergeydt]

Минимизация количества узловых точек для линейной аппроксимации поверхности.

имеется конечный набор данных (x, y, z) - выборка.
количество таких значений могу взять сколь угодно большое.
эти точки взяты с поверхности z = f(x, y).
область определения [0..1800, 0..1800, 0..100].

1. необходимо найти минимальное количество точек (узлов или параметров), с помощью которых можно будет восстановить исходную поверхность с заданной точностью E (0.5% - 5%)
2. какой лучше использовать алгоритм аппроксимации или интерполяции?

скриншот поверхности http://forum.sources.ru/index.php?act=Attach&type=post&id=2898270&attach_id=9753

[мат-ламер]

Можно разбить область задания функция равномерно на одинаковые треугольники. Затем те треугольники, где точность не достигнута, разбить на четыре равных треугольника. Затем эту процедуру повторять рекурсивно.

[sergeydt]

мат-ламер в сообщении #448450 писал(а):

Можно разбить область задания функция равномерно на одинаковые треугольники. Затем те треугольники, где точность не достигнута, разбить на четыре равных треугольника. Затем эту процедуру повторять рекурсивно.

будет ли такое решение оптимально с точки зрения количества найденных узловых точек?
ведь исходная поверхность нам известна.
также известно, что на ней, например, есть локальные минимумы и максимумы, в которых точно должны быть узловые точки.

-- Сб май 21, 2011 20:47:03 --

у меня пока только 2 идеи:
1. рассмотреть прямые линии на области определения, парллельные осям. на них определены кривые. аппроксимировать каждую и найти на ней точки, в которых либо первая, либо вторая производная обращается в 0. принять найденные точки за узловые.
2. взять изначальную таблицу точек (равномерную сетку) и убирать по 1 узлу, если при замене значения в этом узле на среднее в ближайших точках не будет отклоняться от истинного значения в узле на значение соответствующее заданной допустимой погрешности.

[мат-ламер]

Похожая постановка встречается при моделировании ландшафта для компьютерных игр, в геоинформационных системах и т.д. Наверняка есть хорошие готовые алгоритмы.

[Circiter]

Можно попробовать распределить узлы по максимумам кривизны; интуитивно это кажется приемлемым...

[sergeydt]

мат-ламер в сообщении #448529 писал(а):

Похожая постановка встречается при моделировании ландшафта для компьютерных игр, в геоинформационных системах и т.д. Наверняка есть хорошие готовые алгоритмы.

в поиске, но пока ничего из этой темы не нашел подходящего

-- Вс май 22, 2011 02:07:39 --

Circiter в сообщении #448588 писал(а):

Можно попробовать распределить узлы по максимумам кривизны; интуитивно это кажется приемлемым...

да, я тоже об этом думал.

для этого
- нужна гладкая аппроксимация
- либо программа (возможно статистического анализа), которая бы могла нарисовать контуры (линии уровней) кривызны

рассматриваю сейчас все варианты, но пока ни один не дошел до реализации.

думаю уже найти дизайнера/3d моделера, который бы в каком-нибудь 3d редакторе создал такую поверхность с нуля, имея параллельно загруженный шаблон в том же редакторе.

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

таких поверхностей 20 штук (подобных), поэтому буду рад любым советам и помощи.

если есть желающие сами реализовать какой-нибудь метод, можем поговорить о вознаграждении.

-- Вс май 22, 2011 02:13:03 --

на самом деле конечная задача шире, а именно:

эта поверхность является моделью, все точки просчитаны по определенному алгоритму.

но правда жизни в том, что реальность несколько отличается. есть гипотеза, что реальная поверхность подобна той, о которой речь в теме.

есть возможность получить небольшое число точных точек. и нужно чтобы по ним и по модели наиболее точно построилась реальная поверхность...

[Circiter]

2sergeydt

Цитата:

да, я тоже об этом думал.

Ну раз функция дана, значит можно кривизну вычислить (выбрав подходящее определение кривизны). Здесь упор будет не на стат.анализ, а на численное дифференцирование. :)

P.S.: Насчет готовых алгоритмов. Поиск в интеренете по ключевым словам "adaptive triangulation" что-нибудь дал?

[sergeydt]

Circiter в сообщении #448605 писал(а):

2sergeydt

Цитата:

да, я тоже об этом думал.

Ну раз функция дана, значит можно кривизну вычислить (выбрав подходящее определение кривизны). Здесь упор будет не на стат.анализ, а на численное дифференцирование. :)

P.S.: Насчет готовых алгоритмов. Поиск в интеренете по ключевым словам "adaptive triangulation" что-нибудь дал?

это называется "генерализация поверхности". оказывается существует около десятка методов уменьшения количества узлов (детализации).

есть 2 типа методов. снизу вверх и сверху вниз.
в первом мы строим регулярную детализированную сетку и убираем узлы по критериям. во втором начинаем строить узлы с нуля.

есть 2 критерия.
- мы фиксируем количество узлов, которое хотим получить, и ищем триангуляцию с наименьшей погрешностью
- мы задаем погрешность и ищем триангуляцию с минимальным количеством узлов

ходят слухи что нечто подобное реализовано в 3ds max, буду копать сейчас в сторону реализованного алгоритма.
если не найду ничего подходящего, придется читать умные книжки и реализовывать самому ((