автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование процесса сборки трехмерных изделий из плоских заготовок

На правах рукописи

оозовэг^и

- V 1*1 гч VI ¿.ии/

Ландовский Владимир Владимирович

МОДЕЛИРОВАНИЕ ПРОЦЕССА СБОРКИ ТРЕХМЕРНЫХ ИЗДЕЛИЙ ИЗ ПЛОСКИХ ЗАГОТОВОК

Специальность 05 13 18 - Математическое моделирование, численные методы

и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск — 2007

003069253

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

Научный руководитель доктор технических наук, профессор

Фроловский Владимир Дмитриевич

Официальные оппоненты доктор физико-математических наук, профессор

Вшивков Виталий Андреевич кандидат технических наук Токарева Марина Георгиевна

Ведущая организация Сибирский государственный университет

телекоммуникаций и информатики, г Новосибирск

Защита состоится 23 мая 2007 г в 1630 на заседании диссертационного совета Д212 1 73 06 в Новосибирском государственном техническом университете по адресу 630092, г Новосибирск, пр К Маркса, 20

С диссертацией можно ознакомиться в библиотеке Новосибирского государственного технического университета

Автореферат разослан « » апреля 2007 г

Ученый секретарь

диссертационного совета Чубич В М

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы Моделирование трехмерных поверхностей и изучение их поведения используется не только в науке, медицине, телевидении и дизайне, а так же и при моделировании одежды Мощности современных компьютеров и программных средств для них позволяют человеку создавать и моделировать буквально любые интересующие его процессы Сейчас слова «виртуальная реальность» уже ни у кого не вызывают недоверия или иных негативных эмоций, не говоря уже о том, что, например, при съемках нашумевшего фильма «Титаник» вода на съемочной площадке явно не присутствовала - ее моделировали 200 компьютеров, объединенных в единую сеть

Построение моделей объектов виртуальной реальности с достаточно сложной поверхностью, представляет собой процесс, требующий специализированных технологий для конкретных предметных областей При этом мы должны учитывать как реально доступные средства получения информации об объекте, так и принятые в предметной области информационные характеристики объекта Одной из наиболее увлекательных и сложных задач компьютерной графики является моделирование поведения ткани при проектировании одежды Важным в этой задаче является не только достижение наибольшей визуальной реалистичности, но, возможно в большей степени, обеспечение соответствия модели физическим характеристикам ткани, соответствия моделируемых деформаций реальным

Цель работы Разработка и исследование методов и алгоритмов моделирования драпировки ткани на поверхности твердого многогранного объекта и сборки изделий из ткани, основанных на ее физических свойствах

Задачи исследования

1 Разработка модели ткани на основе метода частиц, с учетом ее физических свойств

2 Разработка алгоритма моделирования процесса сборки изделий из ткани на поверхности твердого многогранного объекта

3 Разработка алгоритма моделирования взаимодействия ткани с твердыми объектами с учетом особенностей задачи

4 Исследование эффективности различных методов решения дифференциальных уравнений, для системы уравнений движения частиц

5 Разработка программного обеспечения на базе предложенной модели Анализ эффективности й характеристик разработанных алгоритмов на основе результатов численных экспериментов

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

Моделирование И вычислительные эксперименты проводились с использованием программного обеспечения, реализованного на С++

Научная новизна

1 Новизна разработанной модели заключается в способе вычисления сил внутренних взаимодействий, основанном на том, что на каждую частицу воздействуют двенадцать соседних частиц

2 Разработанный алгоритм поиска столкновений частиц с гранями твердого объекта ранее не применялся для задач моделирования ткани

3 Впервые в рамках рассматриваемой задачи применены явные методы решения дифференциальных уравнений, разработанные для жестких задач, и проведено сравнительное исследование эффективности различных методов

Достоверность результатов.

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

Практическая значимость работы

Разработанные методы и алгоритмы и созданное на их основе программное обеспечение могут быть использованы

- для моделирования сборки изделий из ткани в системах автоматизации проектирования легкой промышленности,

- для расширения возможностей информационно графических систем,

- при создании компьютерных игр и анимации

Материалы диссертации использовались в учебном процессе НГТУ при выполнении курсовых работ по дисциплине «Вычислительная математика», студентами третьего курса АВТФ по направлению информатика и вычислительная техника

Основные положения, выносимые на защиту

1 Модель ткани, разработанная на основе метода частиц, с учетом физических свойств тканых материалов

2 Методы построения исходной сетки, с учетом выбранных типов структурных взаимодействий между частицами

3 Разработанные для предложенной модели алгоритмы моделирования процесса сборки изделий из ткани и взаимодействия ткани с твердыми объектами

4 Результаты сравнительного исследования применения различных методов решения дифференциальных уравнений

5 Разработанное на основе предложенных методов и алгоритмов программное обеспечение, позволяющее выполнять моделирование сборки изделий из ткани с последующим наложением на поверхность произвольного многогранного объекта и исследовать эффективность алгоритмов

Апробация работы

Основные результаты диссертации докладывались на

1 Региональной научной конференции «Наука Техника Инновации» (Новосибирск, 03 - 07 декабря 2004)

2 Международной научно-практической конференции isiCAD-2004 (Новосибирск, Академгородок, 21-23 июня, 2004)

3 15-ой Международной конференции по компьютерной графике и ее приложениям GraphiCon 2005 (Новосибирск, Академгородок, 20 - 24 июня,

2005)

4 Korean-Russian International Symposium on Science and Technology (Novosibirsk, June 26 - July 2, 2005)

5 Международной научно-практической конференции isiCAD-2006 (Новосибирск, Академгородок, 31 мая - 2 июня,2006)

6 16-ой Международной конференции по компьютерной графике и ее приложениям GraphiCon 2006 (Новосибирск, Академгородок, 1-5 июля,

2006)

Разработка и развитие представленных в диссертации методов осуществлялись при поддержке гранта МО РФ по фундаментальным исследованиям в области технических наук Т02-10 4—3668

Публикации

По теме диссертации опубликовано 8 печатных работ, в их числе 2 статьи в центральных изданиях входящих в перечень изданий, рекомендованных ВАК

РФ, 1 - в сборнике научных трудов, 1 - в научно техническом журнале, 4 в трудах и материалах Международных конференций

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников включающего 69 наименований, приложения, содержит 63 рисунка, 21 таблицу, общий объем составляет 117 страниц

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе приводится обзор основных подходов деформационного моделирования поверхностей тканей в пространстве

Среди множества методов деформационного моделирования поверхностей тканей в пространстве выделено на три основные группы физические геометрические методы и гибридные методы

Геометрические модели рассматривают не физические свойства ткани, а сгибы и складки, которые представляются в виде геометрических уравнений Попытки создания гибридных методов, с целью объединения достоинств геометрических и физических моделей, как правило, заканчивались неудачно

Основное внимание уделяется физическим методам, в которых ткань представлена в виде системы взаимосвязанных частиц, движение которых описывается законами механики А процесс моделирования сводится к решению системы дифференциальных уравнений с начальными условиями и нахождению траекторий движения частиц

В главе рассмотрены деформационные свойства тканных материалов и существующие системы измерения физических свойств ткани Наиболее реалистичные результаты позволяют получить модели, в которых учитывается три типа взаимодействий растяжение, изгиб и сдвиг Растяжение и сжатие (отталкивание) поддерживают частицы на номинальном расстоянии Взаимодействия изгиба и сдвига, оказывают значительное воздействие на

форму поверхности и определяются исходя из углов, образованных линиями сетки

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

В конце главы обсуждается актуальность применения методов моделирования ткани в системах автоматизации проектирования одежды

Во второй главе рассмотрены основные особенности применения метода частиц для моделирования ткани В ткани, тонкие волокна скручены в нити, и эти нити более или менее жестко сплетены во взаимосвязанную сеть Компоненты сети удерживаются вместе трением, а поведение зависит от типа и веса волокна, плотности и типа сплетения Порядок расположения нитей относительно друг друга рис 1 остается неизменным даже при существенных деформациях, а деформация ткани представляет собой изменение формы и размеров ячеек Из этого следует предложение рассматривать ткань как систему частиц, которые размещены в точках пересечения продольных и поперечных нитей

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

плоскости окружающей ткани Сдвиг представляет собой деформацию ячейки сети

Рис 1 Примеры структур ткани

Для моделирования взаимодействий между частицами предложено учитывать влияние двенадцати соседних частиц на каждую внутреннюю частицу На рис 2 взаимодействия растяжения-сжатия, сдвига и изгиба обозначены связями 1, 2 и 3 соответственно

Рассмотрены способы получения исходной сетки для ткани произвольной формы Для моделирования сборки изделий из ткани, исходными данными для построения сеточной модели является контур детали (выкройки), который в общем случае представляет собой произвольный многоугольник На рис 3 показан результат наложения равномерной прямоугольной сетки на произвольную деталь

Рис 3 Равномерная прямоугольная сетка

Основной недостаток такого подхода - сильное искажение исходного контура Предложен метод получения неравномерной сетки, состоящий в следующем предположим, что весь контур - это объединение четырех границ рис 4 Границы выбираются произвольно и делятся на произвольное количество отрезков Таким образом, мы получаем граничные узлы сетки Единственное условие, которое должно быть выполнено количество частиц (узлов), составляющих верхнюю границу и количество частиц, составляющих нижнюю границу должны быть равны. То же верно для левой и правой границ

Координаты промежуточных узлов можно определить следующим образом

Рис 4 Неравномерная сетка

} = {] -1) (х1ц - хм<])/М + х^

или х^=(г-1) {х^-х^/Ы + х^и,

координаты уи] аналогично, где М - количество частиц левой и правой

границы, N - верхней и нижней

В третьей главе рассматриваются уравнения движения системы взаимосвязанных частиц и методы их решения

Движение системы описывается обобщенными перемещениями , и

на каждом временном слое ищутся положения частиц в пространстве

На основании законов механики систему дифференциальных уравнений движения частиц можно записать в следующем виде

г' = V

V' = М~^Р(г,у)'

где Яг,О" функция, описывающая действие внутренних и внешних сил на ткань, М матрица инерции - диагональная матрица, описывающая распределение масс ткани

Начальные условия г]^ = , ,Р1п4= 0, где /<"т( это

результирующая сила внутренних взаимодействий

Для решения полученной задачи Коши предлагается использовать следующие методы явный и неявный методы Эйлера, метод с перешагиванием, метод Рунге-Кутта четвертого порядка точности и методы с автоматическим управлением шагом интегрирования, основанные на методе Рунге-Кутта-Мерсона

Для методов Эйлера и схемы с перешагиванием проведена теоретическая оценка точности и устойчивости, в зависимости от величины шага интегрирования

Подробно рассмотрен вопрос реализации неявного метода Эйлера

гп+1~гп =Чн-1

- V« = АМ , у„+1)

Пусть у„+1-у„=Ду, г„+1-ги=Дг, тогда можно переписать систему в

виде

(АН

М

М

у„+ДУ

М~^Р(гп + Дг,У„ + Ду)

Применив разложение F в ряд Тейлора в окрестности точки и

выполнив аппроксимацию первого порядка, получим

Эг

И перейдем к системе линейных алгебраических уравнений

ГДИ кДу)

= й

у„+Ду

дг

даДу)

5У

Подставив в нижнюю строку системы Дг = Ыуп + Ду), получим

Ду = ИМ

-1

Эу

+—г-^+Ол+Ду) дг

Обозначим за I - единичную матрицу и, перегруппировав отдельные составляющие, получим уравнение

Зу

дг

Перепишем его в виде

5у дг I дг J

Решив систему относительно Av, найдем Дг = h(vn + Av) Таким образом, шаг неявного метода состоит в вычислении F(rn,vn), 8F(r,v) 8F{r,v) ,

—г-,-1, формировании и решении системы уравнении относительно

civ or

Дуй последующем обновлении значений г и v

Частная производная —-—-, для системы с количеством частиц N это

or

матрица размера 3Nx3N, ненулевые элементы которой представляют собой блоки размером 3x3, располагающиеся около главной диагонали и на пересечениях индексов взаимодействующих частиц Блоки 3x3, характеризующие координатные составляющие сил, и вся матрица в целом обчадают свойством симметрии Для решения системы используется метод сопряженных градиентов Так как каждая частица взаимодействует только с двенадцатью соседними то, матрица А будет разряженной В целях ускорения работы алгоритма решения, для хранения матрицы А предложено использовать метод Compressed Sparse Row

В четвертой главе описывается алгоритм моделирования взаимодействий ткани с твердыми объектами и алгоритм моделирования сборки изделий из ткани

Если в некоторый момент времени траектория движения частицы пересекла грань объекта, то необходимо скорректировать ее положение и скорость Поиск пересечений для объекта представленного совокупностью М треугольных граней и ткани, представленной сеткой из N частиц, представляет собой последовательность М N процедур проверки пересечения отрезка и треугольной грани в трехмерном пространстве Каждая из таких проверок требует большого количества вычислений Чтобы сократить количество вычислений вводятся предварительные проверки, для этого выделяется прямоугольная область, ограниченная максимальными и минимальными координатами объекта xmax, >,max> ^ах,*^, .JW, 2тш Пусть

r" = (x",y",z") и =(x"~\y"~\z"~l) положение частицы на текущем и

предыдущем временном слое В случае xf-1 > xmsx & х" > xmax или

<xmin <хгшп, перемещение частицы произошло правее или левее объекта и, следовательно, она не могла пересечь ни одной грани Тоже следует проверить и для координат у и z Точно также можно поступить и в случае отдельно взятой грани, тогда вместо громоздких вычислений, в подавляющем большинстве случаев будет выполнено лишь несколько операторов сравнения

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

Пусть Nx - количество интервалов по координате х, Ny и Nz по

координатам у и z соответственно, тогда номер интервала по оси х index,. =-X"~Xmm-+ 1,

(■^max ~xmn\)lNx

а номер трехмерной ячейки

index = mdexx Ny Nz + indexy Nz + indexz — 1

Таким образом, поиск пересечений сводится к следующей последовательности действий

1 Заполнить списки граней для каждой ячейки

2 На каждом шаге для каждой частицы

2 1 определить номера ячеек для положений г"~1, г", 2 2 проверить пересечения с гранями из списков с полученными номерами

Обработка найденных столкновений заключается в перемещении частицы относительно точки пересечения грани объекта на малую величину а так,

чтобы она снова оказалась вне тела, и изменении скорости частицы Возврат производится по нормали к грани, проходящей через точку пересечения

Сборка модели одежды и наложение ее на поверхность манекена представляет собой следующую последовательность действий В начальный момент времени тело и ткань должны находиться вблизи друг от друга, чтобы избежать напрасных затрат на сближение Чтобы сконструировать одежду, определяются частицы, которые будут участвовать в формировании шва Определяется, с какими точками, какой именно выкройки должно быть установлено соответствие Каждая частица, участвующая в формировании шва подвергается воздействию сил, стягивающих соответствующие точки выкроек к геометрической середине отрезка между ними

Моделирование сборки осуществляется в два этапа На первом этапе вводятся стягивающие силы Второй этап - окончательное наложение здесь учитывается действие силы и стягивающих сил

Пятая глава посвящена вычислительным экспериментам, проведенным для анализа эффективности разработанных алгоритмов, и описанию разработанного программного обеспечения

Программа разрабатывалась с помощью С++ Builder 5 под Windows В основу положена идеология объектно-ориентированного программирования Функции загрузки, сохранения, редактирования и визуализации ткани и твердых объектов реализованы в классах Cloth и Object соответственно Функции моделирования, обработки результатов, ввода загрузки и сохранения параметров представляют собой методы класса Model

Входной информацией является набор числовых параметров, а также файлы с описанием геометрии объектов моделирования, которые можно получить импортом данных из хорошо известной системы Auto CAD

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

Помимо визуализации предусмотрена возможность сохранения результатов в виде файла, данные из которого могут быть в дальнейшем переданы в Auto CAD для более детального просмотра

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

Таблица 1

Оценка растяжений.

Максимальное растяжение Среднее растяжение Максимальное растяжение по вертикали Максимальное растяжение по горизонтали

3,5 23,5 6,8 9,5 12,0

4,5 18,2 5,2 7,2 9,2

5,5 16,4 4,2 6,0 7,9

6,5 15,1 3,5 5,0 6,7

7,5 12,2 3,1 4,3 5,9

11,5 9,3 2,0 2,8 4,0

15,5 6,7 1,4 2,2 зд

Сравниваются результаты моделирования, полученные с использованием различных методов построения исходной сетки Использование неравномерной сетки позволяет достичь наиболее реалистичных результатов

Тестирование алгоритма поиска столкновений показало, что в случае прямого поиска пересечений - перебора всех пар частица-грань затраченное на это время составляет более 90% времени моделирования, и каждая итерация может длиться более пяти секунд При использовании списка ограничивающих областей и принадлежащих им граней время поиска и обработки пересечений сокращается на несколько порядков, и в рассмотренных тестовых примерах не превышает 40% общего времени моделирования

Таблица 2

Время поиска и обработки пересечений 15100 граней, 1600 частиц

Количество интервалов Размер ячейки, м Количество итераций Время поиска и обработки пересечений Время интегрирования

X У г с % С %

1 1 1 0,56x0,61x0,39 50 242,4 99,7 0,7 0,3

5 5 5 0,11x0,12x0,08 500 29,3 83 6,1 17

10 10 10 0,06x0,06x0,04 500 7,8 56 6Д 44

15 15 15 0,04x0,04x0,03 500 4,5 42 6,1 58

20 20 20 0,03x0,03x0,02 500 3,8 38 6,1 62

По результатам сравнительного исследования различных методов решения системы дифференциальных уравнений движения частиц сделаны следующие выводы Добиться наилучших результатов с наименьшими временными затратами позволяет схема с перешагиванием Метод Рунге-Кутга 4-го порядка точности позволяет увеличить значение шага интегрирования только вдвое, в то время как временные затраты на один шаг возрастают в четыре раза по сравнению с методом с перешагиванием Методы с автоматическим управлением шагом также не дают преимуществ Классический метод Рунге-Кутта-Мерсона имеет слишком грубый способ управления шагом, из-за чего уменьшение шага происходит практически после каждой успешной итерации Модификации метода Мерсона разработанные для решения жестких задач управляют шагом значительно эффективнее однако суммарные временные затраты оказываются слишком велики Неявный метод Эйлера - единственный метод, позволяющий получить решение быстрее схемы с перешагиванием, но при этом качество полученного результата неприемлемо Приложения содержат описание интерфейса пользователя разработанного программного обеспечения

Основные результаты работы 1 Разработана модель ткани на основе метода частиц и физических свойств тканых материалов Определены основные типы взаимодействий между частицами, и выражения для вычисления сил этих взаимодействий

2 Разработаны следующие методы и алгоритмы

2 1 Методы построения частично равномерной и неравномерной сетки, для инициализации начального расположения частиц, с учетом выбранных типов взаимодействий между частицами По результатам экспериментов в качестве более подходящего способа выбрана неравномерная сетка

2 2 Алгоритм взаимодействия ткани с твердыми объектами Особенностью данного алгоритма является высокая скорость поиска столкновений частиц с гранями твердого объекта, что значительно сокращает время решения задачи

2 3 Алгоритм моделирования процесса сборки изделий из ткани на поверхности твердого многогранного объекта

3 Программно реализованы некоторые явные одношаговые методы и неявный метод Эйлера для решения системы дифференциальных уравнений движения частиц Проведено сравнительное исследование эффективности этих методов

4 На базе разработанных методов и алгоритмов создано программное обеспечение, которое может быть использовано для моделирования сборки изделий из ткани и последующего наложения на поверхность произвольного многогранного объекта Для проверки качества разработанных методов и алгоритмов проведены вычислительные эксперименты

Основные научные результаты диссертации опубликованы в следующих работах

1 Landovsky V V Modelmg of fabric based on particles method / Frolovsky V D , Landovsky V V // Proceedings of the International Forum isiCAD-2004, Novosibirsk, Ledas Ltd, 2004 - P 224-229 [Моделирование ткани методом частиц]

2 Landovsky V V Explicit and Implicit integration in the problem of modeling of fabric based on particles method / Frolovsky V D , Landovsky V V // Proc 9th Russian-Korean International Symposium on Science and Technology, Russia,

Novosibirsk, 2005 - P 596-600 [Явное и неявное интегрирование в задаче моделирования ткани методом частиц]

3 Ландовский В В Методы интегрирования дифференциальных уравнений в задаче моделирования поведения ткани методом частиц // Материалы 15-ой международной конференции по компьютерной графике, Новосибирск Институт вычислительной математики и математической геофизики СО РАН, 2005 -С 234-241

4 Ландовский В В Компьютерное моделирование одежды с использованием метода частиц // Информационные технологии моделирования и управления, -2005 -№7(25) - С 934-941

5 Ландовский В В Исследование методов интегрирования дифференциальных уравнений в задаче моделирования поведения ткани на основе метода частиц / Ландовский В В , Фроловский В Д // Сибирский журнал вычислительной математики, Т9,№3 -2006 -С 101-112

6 Ландовский В В Моделирование сборки деталей из тканых материалов на твердотельных поверхностях // Материалы 16-ой международной конференции по компьютерной графике, Новосибирск Институт вычислительной математики и математической геофизики СО РАН, 2006 -С 146-153

7 Ландовский В В Моделирование взаимодействий ткани с твердыми многогранными объектами // Сборник научных трудов НГТУ, 2006 -№2(44) - С 53-58

8 Ландовский В В Разработка и исследование компьютерных методов трехмерного проектирования одежды / Фроловский В Д , Ландовский В В // Омский научный вестник, 2006 -№3(36) -С 132-137

Отпечатано в типографии Новосибирского государственного технического университета 630092, г Новосибирск, пр К. Маркса, 20,

тел/факс (383) 346-08-57 формат 60x84/16, объем 1,25 п л, тираж 105 экз, заказ № 680 подписано в печать16 04 07г

Введение.

Глава 1. Обзор методов моделирования поверхности ткани в трехмерном пространстве.

1.1. Основные подходы к моделированию поверхностей тканей.

1.2. Геометрические методы.

1.3. Физические методы.

1.3.1. Деформационные свойства такни и измерительные системы.

1.3.2. Методы интегрирования уравнений движения.

1.3.3. Моделирование взаимодействий ткани и твердых объектов.

1.4. Гибридные методы.

1.5. Трехмерное моделирование изделий из ткани в САПР легкой промышленности.

Выводы по главе.

Глава 2. Моделирование ткани методом частиц.

2.1. Деформационные свойства ткани.

2.2. Дискретизация выкройки произвольной формы,.

2.2.1. Частично равномерная сетка.

2.2.2. Неравномерная сетка.

Выводы по главе.

Глава 3. Методы интегрирования уравнений движения.

3.1. Уравнения движения системы взаимосвязанных частиц.

3.2. Методы интегрирования уравнений движения.

3.2.1. Метод Эйлера.

3.2.2. Схема с перешагиванием.

3.2.3. Метод Рунге-Кутта.

3.2.4. Метод Рунге-Кутта-Мерсона.

3.2.5. Контроль точности и устойчивости.

3.2.6. Методы STEK и STEKS.

3.2.7. Неявный метод Эйлера.

Выводы по главе.

Глава 4. Алгоритмы моделирования взаимодействий между различными деталями ткани и твердыми объектами.

4.1. Моделирование взаимодействий ткани и объекта.

4.1.1. Поиск столкновений.

4.1.2. Усовершенствование алгоритма поиска пересечений.

4.1.3. Обработка столкновений.

4.2. Моделирование сборки изделий,.

Выводы по главе.

Глава 5. Вычислительные эксперименты.

5.1. Разработка программного обеспечения.

5.1.1. Концепция программного обеспечения.

5.1.2. Входная информация,.

5.1.3. Выходная информация.

5.1.4. Интерфейс.

5.2. Параметры моделирования и единицы измерения.

5.2.1. Взаимодействие растяжения сжатия.

5.2.2. Влияние взаимодействий изгиба и сдвига.

5.3. Различные способы дискретизации ткани.

5.4. Взаимодействия изгиба между различными фрагментами ткани при сборке.

5.5. Сравнение эффективности методов интегрирования.

5.6 Тестирование алгоритма поиска пересечений.

5.7. Оценка растяжений.

Выводы по главе,.

Актуальность работы. Моделирование трехмерных поверхностей и изучение их поведения используется не только в науке, медицине, телевидении и дизайне, а так же и при моделировании одежды. Мощности современных компьютеров и программных средств для них позволяют человеку создавать и моделировать буквально любые интересующие его процессы. Сейчас слова «виртуальная реальность» уже ни у кого не вызывают недоверия или иных негативных эмоций, не говоря уже о том, что, например, при съёмках нашумевшего фильма «Титаник» вода на съёмочной площадке явно не присутствовала - её моделировали 200 компьютеров, объединённых в единую сеть.

Построение моделей объектов виртуальной реальности с достаточно сложной поверхностью, представляет собой процесс, требующий специализированных технологий для конкретных предметных областей. При этом мы должны учитывать как реально доступные средства получения информации об объекте, так и принятые в предметной области информационные характеристики объекта. Одной из наиболее увлекательных и сложных задач компьютерной графики является моделирование поведения ткани при проектировании одежды. Важным в этой задаче является не только достижение наибольшей визуальной реалистичности, но, возможно в большей степени, обеспечение соответствия модели физическим характеристикам ткани, соответствия моделируемых деформаций реальным.

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

Задачи исследования

1. Разработка модели ткани на основе метода частиц, с учетом ее физических свойств.

2. Разработка алгоритма моделирования процесса сборки изделий из ткани на поверхности твердого многогранного объекта.

3. Разработка алгоритма моделирования взаимодействия ткани с твердыми объектами с учетом особенностей задачи.

4. Исследование эффективности различных методов решения дифференциальных уравнений, для системы уравнений движения частиц.

5. Разработка программного обеспечения на базе предложенной модели. Анализ эффективности и характеристик разработанных алгоритмов на основе результатов численных экспериментов.

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

Моделирование и вычислительные эксперименты проводились с использованием программного обеспечения, реализованного на С++.

Научная новизна

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

2. Разработанный алгоритм поиска столкновений частиц с гранями твердого объекта ранее не применялся для задач моделирования ткани.

3. Впервые в рамках рассматриваемой задачи применены явные методы решения дифференциальных уравнений, разработанные для жестких задач [], и проведено сравнительное исследование эффективности различных методов.

Достоверность результатов.

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

Практическая значимость работы

Разработанные методы и алгоритмы и созданное на их основе программное обеспечение могут быть использованы:

- для моделирования сборки изделий из ткани в системах автоматизации проектирования легкой промышленности;

- для расширения возможностей информационно графических систем;

- при создании компьютерных игр и анимации.

Материалы диссертации использовались в учебном процессе НГТУ при выполнении курсовых работ по дисциплине «Вычислительная математика», студентами третьего курса АВТФ по направлению информатика и вычислительная техника.

Основные положения, выносимые на защиту

1. Модель ткани, разработанная на основе метода частиц, с учетом физических свойств тканых материалов.

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

3. Разработанные для предложенной модели алгоритмы моделирования процесса сборки изделий из ткани и взаимодействия ткани с твердыми объектами.

4. Результаты сравнительного исследования применения различных методов решения дифференциальных уравнений.

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

Апробация работы

Основные результаты диссертации докладывались на:

1. Региональной научной конференции «Наука. Техника. Инновации» (Новосибирск, 03 - 07 декабря 2004)

2. Международной научно-практической конференции isiCAD-2004. (Новосибирск, Академгородок, 21-23 июня, 2004)

3. 15-ой Международной конференции по компьютерной графике и ее приложениям. GraphiCon 2005. (Новосибирск, Академгородок, 20 - 24 июня,

2005)

4. Korean-Russian International Symposium on Science and Technology. (Novosibirsk, June 26 - July 2, 2005)

5. Международной научно-практической конференции isiCAD-2006 (Новосибирск, Академгородок, 31 мая - 2 июня,2006)

6. 16-ой Международной конференции по компьютерной графике и ее приложениям. GraphiCon 2006. (Новосибирск, Академгородок, 1 - 5 июля,

2006)

Разработка и развитие представленных в диссертации методов осуществлялись при поддержке гранта МО РФ по фундаментальным исследованиям в области технических наук Т02-10.4-3668.

Публикации

По теме диссертации опубликовано 8 печатных работ, в их числе 2 статьи в центральных изданиях входящих в перечень изданий, рекомендованных ВАК РФ, 1 - в сборнике научных трудов, 1 - в научно техническом журнале, 4 в трудах и материалах Международных конференций.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников включающего 69 наименований, приложения; содержит 63 рисунка, 21 таблицу, общий объем составляет 117 страниц.

Основные результаты диссертационной работы заключаются в следующем:

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

2. Разработаны следующие методы и алгоритмы:

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

2.2. Алгоритм взаимодействия ткани с твердыми объектами. Особенностью данного алгоритма является высокая скорость поиска столкновений частиц с гранями твердого объекта, что значительно сокращает время решения задачи.

2.3. Алгоритм моделирования процесса сборки изделий из ткани на поверхности твердого многогранного объекта.

3. Программно реализованы некоторые явные одношаговые методы и неявный метод Эйлера для решения системы дифференциальных уравнений движения частиц. Проведено сравнительное исследование эффективности этих методов.

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

ЗАКЛЮЧЕНИЕ

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

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

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

1. Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности. Новосибирск: Изд-во НГТУ, 2000.

2. Бескоровайная Т.П. Конструирование одежды для индивидуального потребителя. М., 2001.

3. Бузов Б. А. Материаловедение в производстве изделий легкой промышленности. М.: Издательский центр «Академия», 2004. 448 с.

4. Ландовский В.В. Моделирование взаимодействий ткани с твердыми многогранными объектами // Сборник научных трудов НГТУ, 2006. -№2(44).-С 53-58.

5. Ландовский В.В. Компьютерное моделирование одежды с использованием метода частиц // Информационные технологии моделирования и управления, 2005. - № 7(25). - С. 934-941.

6. Ландовский В.В. Исследование методов интегрирования дифференциальных уравнений в задаче моделирования поведения ткани на основе метода частиц / Ландовский В.В., Фроловский В.Д. // Сибирский журнал вычислительной математики, Т 9, №3. 2006. - С. 101112.

7. Новиков Е.А. Явные методы для жестких систем Новосибирск: Наука. Сиб. Предприятие РАН, 1997. 195 с.

8. Ю.Писсанецки С. Технология разреженных матриц. М.: Мир, 1988.

9. П.Полищук В., Полищук A. AutoCAD 2002. Практическое руководство, издательство "Диалог МИФИ" 2002 г. 528 с.

10. Фроловский В. Д. Разработка и исследование компьютерных методов трехмерного проектирования одежды / Фроловский В. Д., Ландовский В.В. // Омский научный вестник, 2006. № 3(36). - С. 132-137.

11. Чебышев П.Л. О кройке одежды. Успехи математических наук. 1946., Т. 1. -№ 2. С. 38 42.

12. М.Чуприн А. И. AutoCAD 2000/2002 (2-е издание) издательство "Диасофт" 2002 г. 784 с.

13. Шамис В. A. Borland С++ Builder 5. Техника визуального программирования- ЗАО "Издательство Нолидж", Москва 2001г. 678 с.

14. Agui Т., Nagao Y. and Nakajma М. An expression method of cylindrical cloth objects an expression of folds of a sleeve using computer graphics. Trans. Society of Electronics, Information and Communications, J73-D-II, 7:10951097,1990.

15. Ascher U. and Boxerman E. On the modified conjugate gradient method in cloth simulation. The Visual Computer, 2003,19(7-8): 526-531

16. Baraff D. and Witkin A. Large steps in cloth simulation. In M. Cohen, editor, SIGGRAPH 98 Conference Proceedings, Annual Conference Series, pages 4354. ACM SIGGRAPH, Addison Wesley, July 1998. ISBN 0-89791-999-8.

17. Breen D.E., House D.H., and Wozny MJ. Predicting the drape of woven cloth using interacting particles. Computer Graphics (Proc. SIGGRAPH), pages 365372,1994.

18. Breen D.E., House D.H. and Wozny M.J. "A Particle-Based Model for Simulating the Draping Behavior of Woven Cloth," Textile Research Journal, Vol. 64, No. 11, November 1994, pp. 663-685.

19. Breen D.E. and House D.H. A physically based model of woven cloth, the Visual Computer, 8(5-6):264-277, June 1992.

20. Choi Kwang-Jin and Ко Hyeong-Seok. Stable but responsive cloth. ACM Transactions on Graphics, 21 (3):604-611, July 2002.

21. Eberhardt В., Weber A., Strasser W. A fast, flexible, particle-system model for clothes draping. IEEE Computer Graphics and Applications. № 16,1996. P. 5259.

22. Eberhardt B. and Weber A. A particle system approach to knitted textiles. Computers & Graphics, 23(4): 599-606,1999.

23. Eberhardt В., Etzmuss 0., and Hauth M. Implicit-explicit schemes for fast animation with particles systems. Proc. Eurographics Workshop Computer Animation and Simulation pp. 137-151, 2000.

24. Feynman C. Modeling the appearance of cloth. Master's thesis. Department of EECS. Massachusetts Institute of Technology. Massachusetts.

25. Frolovsky V. D. Modeling of fabric based on particles method / Frolovsky V. D., Landovsky V. V. // Proceedings of the International Forum isiCAD-2004, Novosibirsk, Ledas Ltd, 2004. P. 224-229. Моделирование ткани методом частиц.

26. Gagalowicz A. Realistic 3D Simulation of Garments. The 15-th International Conference on Computer Graphics and Applications GraphiCon-2005, Novosibirsk, Russia, 2005.

27. Gilbert E.G., Johnson D.W., and Keerthi S.S. A Fast Procedure for Computing the Distance Between Complex Objects in Three- Dimensional Space. IEEE Journal of Robotics and Automation, 4(2), 1988.

28. Gottschalk S., Lin M.C., and Manocha D. OBBTree: A Hierarchical Structure for Rapid Interference Detection. Computer Graphics, 30(Annual Conference Series): 171-180,1996.

29. Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching. Proc. ACM SIGMOD Conference, Boston, pages 47-57,1984.

30. Hing N. Ng, Richard L. Grimsdale. Computer Graphics Techniques for Modeling Cloth. IEEE Computer Graphics and Applications, Vol. 16, № 5, 1996, pp. 28-41.

31. Hockney W. and Eastwood J.W., Computer Simulation Using Particles. McGraw-Hill, New York, 1981

32. House D.H., DeVaul R.W. and Breen D.E. "Towards Simulating Cloth Dynamics Using Interacting Particles," International Journal of Clothing Science and Technology, Vol. 8, No. 3, pp. 75-94,1996.

33. Howletty P., Hewittz W.T. Mass-Spring Simulation using Adaptive Non-Active Points. EUROGRAPHICS '98/ N. Ferreira and M. Gbel (Guest Editors) Volume 17 (1998), Number 3.

34. Hubbard P.M. Approximating Polyhedra with Spheres for Time-Critical Collision Detection. ACM Transactions on Graphics, 15(3): 179-210,1996.

35. Kang Y.-M., Choi J.-H, Cho H.-G. Fast and stable animation of cloth with an approximated implicit method. Proc Comput Graph Int 2000; 247-561.

36. Kang Y.-M., Choi J.-H., Cho H.-G., Lee D.-H., and Park C.-J. Real-time animation technique for flexible and thin objects. In WSCG, pages 322-329, Feb. 2000.

37. Kawabata S., Niwa M., and Kwai H. The finite deformation theory of plain weave part I to III. (2):21-85, February 1973.

38. Kawabata S. The standardisation and analysis of hand evaluation. Technical report, The textile machinery society of Japan, Osaka, July 1980.

39. Kawabata S., Postle R., Niwa M. Objective Specification of Fabric Quality, Mechanical Properties and Performance, The Textile Mach. Soc. Japan Publications. 1982.

40. Kunii T.L. and Gotoda H. Singularity theoretical modeling and animation of garment wrinkle formation process. The Visual Computer, 6(6): 326-336,1990.

41. Kunii T.L. and Gotoda H. Modeling and animation of garment wrinkle formation processes. InProc. Computer Animation, pages 131--147,1990.

42. Li T.-Y. and Chen J.-S. Incremental 3D Collision Detection with Hierarchical Data Structures. In Proc. of the ACM Symposium on Virtual reality software and technology, 1998.

43. Li Ling et al, A Model for Animating the Motion of Cloth, International Journal of Systems and Applications in Computer Graphics, November 1994.

44. Lin M.C. and Canny J.F. A Fast Algorithm for Incremental Distance Calculation. In IEEE International Conference on Robotics and Automation, pages 1008-1014,1991.

45. Lafleur Benoit, Magnenat-Thalmann Nadia, Thalmann Daniel. Cloth Animation with Self- Collision Detection. In Proc. IFIP Conference on Modeling in Computer Graphics, Springer, Tokyo, 1991, pp. 179-187.

46. Mirtich B. VClip: Fast and Robust Polyhedral Collision Detection. ACM Transactions on Graphics, 17(3): 177-208,1998.

47. Metzger J., Kimmerle S., Etzmuss O. Hierarchical techniques in collision detection for cloth animation. Journal of WSCG (2003); Vol. 11, No. 1.

48. Ngo-Ngoc Cyril and Boivin Samuel. Nonlinear cloth simulation. Technical report, INRIA Research Report #5099, January 2004.

49. Provot X. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In Graphics Interface, pages 147-155,1995.

50. Provot X. Collision and self-collision handling in cloth model dedicated to design garments. In Graphics Interface 97 (1997), pp. 177- 189.

51. Rudomin I.J. Simulating Cloth using a Mixed Geometry-Physical Method. PhD thesis, Department of Computer and Information Science, University of Pennsylvania. 1990

52. Shewchuk J. An introduction to the conjugate gradient method without the agonizing pain. Technical Report CMUCS- TR-94-125, Carnegie Mellon University, 1994.

53. Thalman N.M., Yang Ying. A Survey of Cloth Animation Techniques. In N.M. Thalmann, Daniel Thalmann, New Trends in Animation and Visualisation. Wiley, 1991. p. 243 -249.

54. Tchebychef P. Sur la coupte des vetements//C.r. Assoc. France Pour l'avancement des sciences. 1878,5p.

55. Terzopoulos D. and Fleischer K. Deformable models. Visual Computer, 4:306331,1988.

56. Terzopoulos D. and Fleischer K. Modeling inelastic deformation: Viscoelasticity, plasticity, fracture. In Computer Graphics (Proc. SIGGRAPH), volume 22, pages 269-278. ACM, August 1988.

57. Terzopoulos D., Piatt J., Barr A., Fleischer K. Elastically deformable models, Computer Graphics, Vol 21,4, pp. 205-214, July, 1987.

58. Terzopoulos D. and Witkin A. Physically based model with rigid and deformable components. IEEE Computer Graphics and Applications, pages 4151, December 1988.

59. Van den Bergen G. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools, 2(4): 1-14,1999.

60. Volino P., Courchesne M., and Magnenat Thalmann N. Versatile and efficient techniques for simulating cloth and other deformable objects. Computer Graphics (Proc. SIGGRAPH), pages 137-144, 1995.

61. Volino P.and Magnenat-Thalmann N. Implementing fast Cloth Simulation with Collision Response. In Computer Graphics International, June 2000.

62. Volino P. and Magnenat-Thalmann N. Efficient Self-Collision Detection on Smoothly Discretized Surface Animations using Geometrical Shape Regularity. Computer Graphics Forum, 13(3):155cl66, 1994.

63. Volino P., Magnenat Thalmann N., Jianhua S., and Thalmann D. An evolving system for simulating clothes on virtual actors. IEEE Computer Graphics and Applications, 16:42-51,1996.

64. Volino P. and Magnenat Thalmann N. Accurate Collision Response on Polygonal Meshes. Computer Animation Conference, 2000.

65. Weil J. The synthesis of cloth objects. In Computer Graphics (Proceedings of SIGGRAPH 86), volume 20 of Computer Graphics Proceedings, Annual Conference Series, pages 49-54.

66. Zachmann G. Rapid Collision Detection by Dynamically Aligned DOP-Trees. Proc. of IEEE, VRAIS'98 Atlanta, 1998.