2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 параметризация поверхности
Сообщение21.05.2011, 19:01 


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

имеется конечный набор данных (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

 Профиль  
                  
 
 Re: параметризация поверхности
Сообщение21.05.2011, 19:31 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: параметризация поверхности
Сообщение21.05.2011, 19:40 


21/05/11
4
мат-ламер в сообщении #448450 писал(а):
Можно разбить область задания функция равномерно на одинаковые треугольники. Затем те треугольники, где точность не достигнута, разбить на четыре равных треугольника. Затем эту процедуру повторять рекурсивно.


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

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

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

 Профиль  
                  
 
 Re: параметризация поверхности
Сообщение21.05.2011, 22:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: параметризация поверхности
Сообщение22.05.2011, 00:40 
Заслуженный участник


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

 Профиль  
                  
 
 Re: параметризация поверхности
Сообщение22.05.2011, 01:00 


21/05/11
4
мат-ламер в сообщении #448529 писал(а):
Похожая постановка встречается при моделировании ландшафта для компьютерных игр, в геоинформационных системах и т.д. Наверняка есть хорошие готовые алгоритмы.


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

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

Circiter в сообщении #448588 писал(а):
Можно попробовать распределить узлы по максимумам кривизны; интуитивно это кажется приемлемым...


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

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

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

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

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

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: параметризация поверхности
Сообщение22.05.2011, 04:53 
Заслуженный участник


26/07/09
1559
Алматы
2sergeydt
Цитата:
да, я тоже об этом думал.

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

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

 Профиль  
                  
 
 Re: параметризация поверхности
Сообщение22.05.2011, 17:53 


21/05/11
4
Circiter в сообщении #448605 писал(а):
2sergeydt
Цитата:
да, я тоже об этом думал.

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

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



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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group