В четверг, 20 мая состоится очное заседание семинара “Вычислительная математика и приложения”, руководители: д.ф.-м.н. В.И. Агошков, д.ф.-м.н. А.Б. Богатырев, чл.-корр. Ю.В. Василевский, д.ф.-м.н. Ю.М. Нечепуренко, ак. Е.Е.Тыртышников. Будет представлен доклад В.А. Гаранжа (ВЦ им. Дородницына РАН) “Распутывание сеток и построение оптимальных деформаций в задачах компьютерной графики”.
Аннотация доклада:
В последние годы в компьютерной графике наблюдается всплеск интереса к методам распутывания сеток и построения оптимальных деформаций. По-видимому, это связано с развитием алгоритмов расширенной реальности и реалистичной компьютерной графики. В недавней работе Du et al, SIGGRAPH2020, проведенной совместно Facebook Inc и Adobe Research, был предложен тестовый набор из 10тыс двумерных задач и тысячи трехмерных задач на распутывание симплициальных расчетных сеток. Авторы утверждали, что среди известных им только их алгоритм смог распутать 100% тестовых сеток.
Проф. Соколов (Univ. Lorrein, Inria, Nancy, France) показал, что его реализация эвристического алгоритма распутывания Гаранжи и Капорина,
ЖВМ и МФ , 1999, также решает весь тестовый набор. Получены следующие результаты:
– доказана теорема о конечном числе шагов для распутывания, когда на каждом шаге приближенно решается задача безусловной минимизации и требуется лишь выполнение некоторого условия существенного убывания;
– доказано, что при этой стратегии распутывания положительно определенная часть матрицы Гессе остается спектрально эквивалентной
конечно-элементному Лапласиану и не происходит неограниченного роста обусловленности при пересечении границы множества допустимых сеток, что возможно в алгоритме Гаранжи, Капорина, 1999;
– описан простой алгоритм распутывания сеток с использования стандартной библиотеки оптимизации, опубликован его код;
– построен алгоритм распутывания для сеток со свободными границами, который гарантирует локальную обратимость, т.е. отсутствие двунакрытий окрестностей вершин сетки (сеточных звезд);
– доказана теорема о конечном числе шагов для достижения заданного порога качества, когда на каждом шаге приближенно решается задача
безусловной минимизации и требуется лишь выполнение некоторого условия существенного убывания;
Сравнение с известными алгоритмами показало, что только предложенный алгоритм решает весь тестовый набор с произвольного начального
приближения, а алгоритм Du et al, 2020, легко “ломается” за счет случайного возмущения начальных данных.
Сравнение с известными алгоритмами по критерию качества построенных деформаций показало примущество предложенного алгоритма. Как показал сравнительный анализ, попытки улучшить меры качества деформации (минимизировать максимальное искажение) в известных алгоритмах приводят к зашумленности решений и потере симметрий. В предложенном алгоритме решается поливыпуклая вариационная задача, зависящая от параметра продолжения, так что наилучшие среди известных алгоритмов числовые характеристики качества деформаций достигаются на гладких решениях, сохраняющих изначальные симметрии.
- 2021-05-20 16:15:00
- 2021-05-20 18:00:00