Содержание к диссертации
Введение
Глава 1. Обзор методов моделирования поверхности ткани в трехмерном пространстве 9
1.1. Основные подходы к моделированию поверхностей тканей 9
1.2. Геометрические методы 9
1.3. Физические методы. 13
1.3.1. Деформационные свойства такни и измерительные системы ,, 13
1.3.2. Методы интегрирования уравнений движения 16
1.3.3. Моделирование взаимодействий ткани и твердых объектов 17
1.4. Гибридные методы 19
1.5. Трехмерное моделирование изделий из ткани в САПР легкой
промышленности 20
Выводы по главе 21
Глава 2. Моделирование ткани методом частиц, 22
2.1. Деформационные свойства ткани 24
2.2. Дискретизация выкройки произвольной формы , 30
2.2.1. Частично равномерная сетка 31
2.2.2. Неравномерная сетка 33
Выводы по главе 36
Глава 3. Методы интегрирования уравнений движения 37
3.1. Уравнения движения системы взаимосвязанных частиц 37
3.2. Методы интегрирования уравнений движения 39
3.2.1. Метод Эйлера 39
3.2.2. Схема с перешагиванием ,40
3.2.3. Метод Рунге-Кутта 42
3.2.4. Метод Рунге-Кутта-Мерсона 42
3.2.5. Контроль точности и устойчивости ,44
3.2.6. Методы STEK и STEKS .45
3.2.7. Неявный метод Эйлера 46
Выводы по главе 52
Глава 4. Алгоритмы моделирования взаимодействий между различными деталями ткани и твердыми объектами 53
4.1. Моделирование взаимодействий ткани и объекта 53
4.1.1. Поиск столкновений 54
4.1.2. Усовершенствование алгоритма поиска пересечений 60
4.1.3. Обработка столкновений 64
4.2. Моделирование сборки изделий, .65
Выводы по главе, 68
Глава 5. Вычислительные эксперименты , 69
5.1. Разработка программного обеспечения 69
5.1.1. Концепция программного обеспечения 70
5.1.2. Входная информация, 71
5.1.3. Выходная информация 74
5.1.4. Интерфейс 76
5.2. Параметры моделирования и единицы измерения 79
5.2.1. Взаимодействие растяжения сжатия 79
5.2.2. Влияние взаимодействий изгиба и сдвига 80
5.3. Различные способы дискретизации ткани 82
5.4. Взаимодействия изгиба между различными фрагментами ткани при сборке 87
5.5. Сравнение эффективности методов интегрирования 88
5.6 Тестирование алгоритма поиска пересечений , 99
5.7. Оценка растяжений 100
Выводы по главе 102
Заключение 103
Список литературы
- Деформационные свойства такни и измерительные системы
- Дискретизация выкройки произвольной формы
- Схема с перешагиванием
- Усовершенствование алгоритма поиска пересечений
Введение к работе
Актуальность работы. Моделирование трехмерных поверхностей и изучение их поведения используется не только в науке, медицине, телевидении и дизайне, а так же и при моделировании одежды. Мощности современных компьютеров и программных средств для них позволяют человеку создавать и моделировать буквально любые интересующие его процессы. Сейчас слова «виртуальная реальность» уже ни у кого не вызывают недоверия или иных негативных эмоций, не говоря уже о том, что, например, при съёмках нашумевшего фильма «Титаник» вода на съёмочной площадке явно не присутствовала - её моделировали 200 компьютеров, объединённых в единую сеть.
Построение моделей объектов виртуальной реальности с достаточно сложной поверхностью, представляет собой процесс, требующий специализированных технологий для конкретных предметных областей. При этом мы должны учитывать как реально доступные средства получения информации об объекте, так и принятые в предметной области информационные характеристики объекта. Одной из наиболее увлекательных и сложных задач компьютерной графики является моделирование поведения ткани при проектировании одежды. Важным в этой задаче является не только достижение наибольшей визуальной реалистичности, но, возможно в большей степени, обеспечение соответствия модели физическим характеристикам ткани, соответствия моделируемых деформаций реальным.
Цель работы. Разработка и исследование методов и алгоритмов моделирования драпировки ткани на поверхности твердого многогранного объекта и сборки изделий из ткани, основанных на ее физических свойствах.
Задачи исследования
Разработка модели ткани на основе метода частиц, с учетом ее физических свойств.
Разработка алгоритма моделирования процесса сборки изделий из ткани на поверхности твердого многогранного объекта.
Разработка алгоритма моделирования взаимодействия ткани с твердыми объектами с учетом особенностей задачи.
Исследование эффективности различных методов решения дифференциальных уравнений, для системы уравнений движения частиц.
Разработка программного обеспечения на базе предложенной модели. Анализ эффективности и характеристик разработанных алгоритмов на основе результатов численных экспериментов.
Методы исследований. Полученные результаты основаны на применении численных методов и метода частиц, аналитической и вычислительной геометрии, а также объектно-ориентированного программирования. В процессе исследований использовались методы и инструменты организации комплексов программных средств, машинные эксперименты для определения эффективности алгоритмов.
Моделирование и вычислительные эксперименты проводились с использованием программного обеспечения, реализованного на C++.
Научная новизна
Новизна разработанной модели заключается в способе вычисления сил внутренних взаимодействий, основанном на том, что на каждую частицу воздействуют двенадцать соседних частиц.
Разработанный алгоритм поиска столкновений частиц с гранями твердого объекта ранее не применялся для задач моделирования ткани.
Впервые в рамках рассматриваемой задачи применены явные методы решения дифференциальных уравнений, разработанные для жестких
задач [], и проведено сравнительное исследование эффективности различных методов.
Достоверность результатов.
Эффективность и достоверность разработанных методов и алгоритмов подтверждается конструктивными программными реализациями, представленными в виде комплексов программ, прошедших тестирование и численный эксперимент.
Практическая значимость работы
Разработанные методы и алгоритмы и созданное на их основе программное обеспечение могут быть использованы:
для моделирования сборки изделий из ткани в системах автоматизации проектирования легкой промышленности;
для расширения возможностей информационно графических систем;
при создании компьютерных игр и анимации.
Материалы диссертации использовались в учебном процессе НГТУ при выполнении курсовых работ по дисциплине «Вычислительная математика», студентами третьего курса АВТФ по направлению информатика и вычислительная техника.
Основные положения, выносимые на защиту
Модель ткани, разработанная на основе метода частиц, с учетом физических свойств тканых материалов.
Методы построения исходной сетки, с учетом выбранных типов структурных взаимодействий между частицами.
Разработанные для предложенной модели алгоритмы моделирования процесса сборки изделий из ткани и взаимодействия ткани с твердыми объектами.
Результаты сравнительного исследования применения различных методов решения дифференциальных уравнений.
7 5. Разработанное на основе предложенных методов и алгоритмов программное обеспечение, позволяющее выполнять моделирование сборки изделий из ткани с последующим наложением на поверхность произвольного многогранного объекта и исследовать эффективность алгоритмов.
Апробация работы
Основные результаты диссертации докладывались на:
Региональной научной конференции «Наука. Техника. Инновации» (Новосибирск, 03 - 07 декабря 2004)
Международной научно-практической конференции isiCAD-2004. (Новосибирск, Академгородок, 21-23 июня, 2004)
15-ой Международной конференции по компьютерной графике и ее приложениям. GraphiCon 2005. (Новосибирск, Академгородок, 20 - 24 июня, 2005)
Korean-Russian International Symposium on Science and Technology. (Novosibirsk, June 26 - July 2,2005)
Международной научно-практической конференции isiCAD-2006 (Новосибирск, Академгородок, 31 мая - 2 июня,2006)
16-ой Международной конференции по компьютерной графике и ее приложениям. GraphiCon 2006. (Новосибирск, Академгородок, 1 - 5 июля, 2006)
Разработка и развитие представленных в диссертации методов осуществлялись при поддержке гранта МО РФ по фундаментальным исследованиям в области технических наук Т02-10.4-3668.
Публикации
По теме диссертации опубликовано 8 печатных работ, в их числе 2 статьи в центральных изданиях входящих в перечень изданий, рекомендованных ВАК РФ, 1 - в сборнике научных трудов, 1 - в научно
8 техническом журнале, 4 в трудах и материалах Международных конференций.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка использованных источников включающего 69 наименований, приложения; содержит 63 рисунка, 21 таблицу, общий объем составляет 117 страниц.
Деформационные свойства такни и измерительные системы
В физических методах ткань, как правило, представляет собой систему взаимосвязанных частиц, движение которых описывается законами механики. А процесс моделирования сводится к решению системы дифференциальных уравнений с начальными условиями и нахождению траекторий движения частиц. Одним из первых использование такого подхода предложил Terzopoulos [59, 60].
В некоторых работах [26] вместо построения динамической модели решается задача поиска конечного состояния системы, в котором энергия частиц минимальна. Следует отметить, что методы основанные на минимизации энергии не получили дальнейшего развития.
До недавнего времени основным фактором, сдерживающим развитие физических методов, был недостаток вычислительных ресурсов. С появлением современной вычислительной техники разработка и исследование таких методов становится все более актуальной и востребованной, что выражается в появлении большого числа зарубежных публикаций в основном в области компьютерной графики и анимации. Несмотря на обилие успешных решений, существует ряд проблем, которые и сегодня не решены до конца.
В процессе разработки физически ориентированной модели ткани можно выделить несколько основных этапов: определение внутренних взаимодействий между частицами, выбор метода решения дифференциальных уравнений и моделирование столкновений между тканью и твердыми объектами. Рассмотрим их более подробно.
Выбор способа взаимодействий между частицами определяется исходя из представлений о деформациях ткани. Наиболее простым и наименее реалистичным является подход, в котором рассматриваются упругие взаимодействия между ближайшими соседними частицами [52].
В середине 90-х группа исследователей Breen D.E., D.H. House, and M.J. Wozny работала над созданием модели в которой предполагалось максимально точно учесть деформационные свойства тканных материалов [19, 20, 21]. В качестве базовой модели использовалась модель частиц, между которыми было выделено три типа взаимодействий: растяжение, изгиб и сдвиг. В качестве характеристик взаимодействий были выбраны функции энергии.
Функции растяжения и сжатия (отталкивания) вместе создают энергетическую яму, которая и поддерживает частицы на номинальном расстоянии. Полная энергия растяжения и энергия сжатия определяются как, сумма составляющих всех связей.
В отличие от растяжения и сжатия, изгиб и сдвиг значительны, даже когда ткань деформируется под влиянием собственного веса. Это - функция угла, сформированного тремя частицами по основе (вдоль) ткани или по утку (поперек).
Взаимодействия сдвига - решеточные взаимодействия. Угол решетки это угол, образованный между равновесным сегментом линии и сегментом линии, соединяющим текущее положение частиц.
Энергии сдвига и изгиба суммируется для четырех углов для каждой частицы.
Для представления конкретной ткани авторы предлагают построить эти функции энергии, основываясь на существующих измерительных системах физических свойств тканей. Примером такой измерительной системы может служить система Kawabata [40, 41, 42]. Система Kawabata - это стандартное оборудование для измерения физических и механических свойств конкретного тканого материала. Результаты этих измерений дают возможность определять количественные соотношения, выражающие физическое поведение тканей, классифицировать и устанавливать существенные свойства различных тканей.
Систему Kawabata можно использовать для измерения свойств, характеризующих изгиб, сдвиг и растяжение ткани. При определении свойств на изгиб, сдвиг и растяжение, оборудование измеряет, сколько силы требуется для выполнения трех видов деформации на образце ткани стандартного размера и формы. Система строит графики каждой силы как функции некоторого геометрического параметра типа угла, длины и т.д. К примеру, для сдвига кривая дает изменение угла сдвига в зависимости от силы. Кривая строится нанесением на график угла сдвига при медленном увеличении сдвиговой силы в одном направлении, затем сила медленно уменьшается, и опять отмечается угол. Затем процесс повторяется при приложении сдвиговой силы в противоположном направлении.
Дискретизация выкройки произвольной формы
Сеточная модель прямоугольного фрагмента ткани, построенная в виде прямоугольной сетки наилучшим образом демонстрирует привлекательность метода частиц для моделирования ткани. Такой подход может быть применен для моделирования некоторых элементов интерьера, таких как занавески и скатерти. И все же объектов прямоугольной формы не так много и в особенности это относится к предметам одежды.
Для моделирования сборки изделий из ткани, исходными данными для построения сеточной модели является контур детали (выкройки), который в общем случае представляет собой произвольный многоугольник. На рис. 2.10 показан результат наложения равномерной прямоугольной сетки на произвольную деталь.
На рис. 2.9 хорошо виден основной недостаток такого подхода -сильное искажение исходного контура. Конечно, можно измельчить сетку в несколько раз, но необходимо учитывать не оправданное возрастание вычислительных затрат. Следовательно необходимо предложить альтернативные способы построения сеточной модели, учитывая что искажение контура, которое хотелось бы свести к минимуму это не единственный критерий.
Прежде всего нужно учесть временные затраты на построение сеточной модели ткани. Это означает, что нужно обратить внимание на возможность и сложность автоматизации этого процесса.
Взаимное расположение частиц имеет смысловую нагрузку, и от того как будет построена сетка и каким образом определены связи, отвечающие различным типам взаимодействий, будет зависеть выбор той или иной структуры данных в программной реализации модели.
Одним из способов приблизить очертания сеточного представления к исходному контуру заключается в перемещении граничных частиц в точки пересечения линий равномерной сетки и линий контура.
В случае если контур представляет собой прямоугольник, то соответствующую ему систему частиц удобнее всего представить в виде матрицы размера MxN. При этом определить взаимодействующие частицы можно исходя из индексов. В других случаях так поступить невозможно, поэтому нужно предложить другой способ хранения данных, например список. Для формирования списка необходимо построить равномерную прямоугольную сетку в виде матрицы частиц {Ру} размера MxN.
Присвоить каждой частице уникальный номер к є [l;MN]. Сформировать для каждой частицы множества номеров связанных частиц для трех типов взаимодействий Rs,ij Rtjj, Rb,ij- Наполнение списка происходит по следующему алгоритму:
Преимущество этого подхода в том, что для формирования сетки нужно выбрать только один параметр - шаг, а все остальные операции будут выполнены автоматически. Недостатком является необходимость хранить дополнительную информацию - множества номеров связанных узлов Rs д., Rtk Rbk которые будут использоваться для вычисления внутренних сил.
Очевидно, что в общем случае сетка представляющая ткань (выкройку) должна быть неравномерной. Потому можно рассмотреть метод получения полностью неравномерной сетки. Предполагаем, что весь контур - это объединение четырех границ рис. 2.12. Границы выбираются произвольно и делятся на произвольное количество отрезков. Таким образом, мы получаем граничные узлы сетки. Единственное условие, которое должно быть выполнено: количество частиц (узлов), составляющих верхнюю границу и количество частиц, составляющих нижнюю границу должны быть равны. То же верно для левой и правой границ.
Схема с перешагиванием
Для построения алгоритмов с контролем точности необходимо оценить ошибку, связанную с применением приближенных формул интегрирования. Многие алгоритмы интегрирования используют оценку локально ошибки (погрешности аппроксимации). Это оправдано тем, что если на каждом шаге контролировать некоторый минимальный уровень локальной ошибки, то глобальная ошибка будет ограничена.
Пятое вычисление правой части не дает увеличение порядка до пятого, однако позволяет увеличить устойчивость и оценить величину локальной ошибки: л,4 = (2 1-9 з+8 4-А$) Алгоритм Шаг 1. Вычисляются приращения /, 1 / 5. Шаг 2. Находится оценка локальной ошибки 8п . Шаг 3. Если для некоторого /, 1 і N, выполняется неравенство А л,4 5е, где і - номер компоненты, то шаг интегрирования уменьшается в 2 раза и управление снова передается на шаг 1. Шаг 4. Вычисляется решение ип+\ Шаг 5. Если для всех і, 1 і N, выполняется неравенство Sn,A - "32 то шаг интегрирования увеличивается в 2 раза. Шаг 6. Выполняется следующий шаг интегрирования. 3.2.5. Контроль точности и устойчивости Для контроля точности в [9] предложено применять неравенство п,р - є» где єпр - оценка ошибки, а є - требуемая точность интегрирования. Определение оценки єпр производится в соответствии с выбранной схемой интегрирования. Учитывая, что єпр =0(hp), где р - порядок точности метода, новый шаг интегрирования определяется по формуле biew = Я ""ти где q - заданный параметр, q 1, a sn вычисляется из уравнения aPs„ р - р Если sn 0, то требуемая точность не выполняется hn полагается равным hnew и решение вычисляется повторно, а в случае sn 0 требуемая точность достигнута, hn+\ полагается равным hnew и осуществляется переход на следующий шаг. Параметр sn полагается целым, а величина q в [9] выбрана 1.1. При решении жестких задач явными методами на большей части интервала интегрирования шаг ограничен не точностью, а устойчивостью численной формулы. В результате из-за отсутствия ограничения сверху на этой части интервала происходит раскачивание шага. Этого можно избежать, если наряду с точностью контролировать устойчивость численной схемы. Для контроля устойчивости используется неравенство Л J Ainax Z), где /Ijnax - максимальное собственное число матрицы Якоби решаемой системы, a D - положительная постоянная связанная с размером области устойчивости. Величину Амідах можно оценить следующим образом ср"п,р-\ Введем обозначение hX„max = Vn Тогда имеем неравенство Vn D Величину шага можно найти из условия устойчивости где параметр гп (учитывая, что Vn = 0(h)) вычисляется из равенства
В случае успешного выполнения неравенства для контроля точности необходимо установить ограничение сверху на шаг. Это можно сделать исходя из условия устойчивости. Новый шаг вычисляется по формуле
Изменение шага в методе STEK производится в соответствии с выражением hnew = q f В методе STEKS управление шагом осуществляется исходя из условий, как точности, так и устойчивости hn+\ = vc x(hn,qram Sn,r , hn).
В целях увеличения устойчивости рассмотрим неявный метод интегрирования, в котором значение F будет определяться в точке Можно сделать вывод, что устойчивость этого метода не зависит от выбора шага. Несмотря на то, что метод имеет всего лишь первый порядок точности, погрешность, внесенная на некотором шаге, не накапливается.
Рассмотрим подробнее реализацию неявного метода. Введем обозначения v„+j - vn = Av, rn+\ -rn=Ar, тогда можно переписать систему в виде (АЛ / = п {AvJ г-1 v„+Av М lF(rn + Ar,vn+Av) Л Для нахождения значений положения и скорости необходимо решить систему относительно Аг и Av, так как уравнения не линейны, решить систему в таком виде задача практически неосуществимая. Применив разложение F в ряд Тейлора в окрестности точки F(rn,vn), и выполнив аппроксимацию первого порядка, получим. F(rn+Ar,vn + Av) = F(rn,vn) + Ar + -Av or dv И перейдем к системе линейных алгебраических уравнений: (Аг vAvy vn+Av M-\F(rn,vn) + -Ar + дг = h +— - Av) dv Подставив в нижнюю строку системы Аг = h(vn + Av), получим Av = hM -1 F(rn,vn) + — LAv + dv dF{r,v) , . ч +— - + (v„+Av) дг J Обозначим за / - единичную матрицу и, перегруппировав отдельные составляющие, получим уравнение v. av dr dF(r,v) v„ 8r dF(r,v) ,25F(r,v) dF(r,v) ( ,b = h F(r,v) + h- rn or \ dr -к dv -1 / = hM F(rn,vn) + h Перепишем его в виде ААу = Ь,ще A = M-h Л Решив систему относительно Av, найдем Аг = h{vn + Av), Таким образом, шаг неявного метода состоит в вычислении F(rn,vn), dF(r,v) 8F(r,v) —-—-, —-—-, формировании и решении системы уравнении dv дг относительно Av и последующем обновлении значений г и V. Особого внимания заслуживает частная производная —L-z-:1, для дг системы с количеством частиц N это матрица размера 3Nx3N, ненулевые элементы которой представляют собой блоки размером 3x3, располагающиеся около главной диагонали и на пересечениях индексов взаимодействующих узлов:
Усовершенствование алгоритма поиска пересечений
Основной целью созданного программного обеспечения является проведение вычислительных экспериментов и анализ эффективности разработанных алгоритмов.
Программа разрабатывалась в C++Builder [15] под Windows, среда Borland C++ Builder является одним из наиболее популярных средств разработки программных продуктов и позволяет в кротчайшие сроки спроектировать интерфейс пользователя.
Подготовка модели является наиболее трудоемким этапом и требует наиболее тесной работы пользователя с системой. На этом этапе необходимо не только ввести геометрическую информацию об объектах моделирования, но и иметь возможность редактировать взаимное расположение объектов и их ориентацию в пространстве. Помимо геометрической информации, вводятся физические характеристики модели и параметры моделирования. Наибольших временных затрат требует определение точек соответствия -частиц образующих швы.
Процесс моделирования представляет собой численное решение уравнений движения частиц с контролем и обработкой пересечений на каждом шаге. Под обработкой результатов моделирования понимается оценка растяжений ткани.
В основу положена идеология объектно-ориентированного программирования. Функции загрузки, сохранения, редактирования и визуализации ткани и твердых объектов реализованы в классах Cloth и Object соответственно. Функции моделирования, обработки результатов, ввода загрузки и сохранения параметров представляют собой методы класса Model. Информация о координатах, скоростях и других свойствах частиц хранится в виде структур. Библиотека алгоритмов численного интегрирования представлена набором методов класса Model и может быть расширена.
На рис. 5.2 представлена структура данных модели, согласно которой объект класса Model включает в себя указатели на объект класса Object и список объектов Cloth, каждый из которых содержит список структур описывающих частицы.
Входной информацией является набор числовых параметров, которые подробно описаны в разделе интерфейс, а также файлы с описанием геометрии объектов моделирования.
Твердые объекты представляются в виде совокупности треугольных граней. Структура файла для хранения информации об объекте представлена нарис. 5.3.
В случае неравномерной сетки координаты промежуточных частиц всегда могут быть восстановлены по координатам граничных частиц, а связи между частицами определяются исходя из индексов. Для частично равномерной сетки необходимо сохранять как положение каждой частицы, так и номера частиц с которыми она взаимодействует, если некоторая связь отсутствует, то в соответствующую ячейку записывается отрицательное значение.
Результаты моделирования могут отображаться в окне программы как на каждом шаге интегрирования, представляя динамику процесса, так и только по окончании моделирования в целях экономии вычислительных ресурсов. Помимо визуализации предусмотрена возможность сохранения результатов в виде файла. Структура файла результатов представлена на рис. 5.7. Все поверхности, как объекта, так и ткани представляются совокупностью треугольных граней.
Интерфейс пользователя разработан с использованием стандартных визуальных компонентов среды Borland C++ Builder 5. Главное окно программы представлено на рис. 5.8. Для удобства работы параметры сгруппированы на различных вкладках в зависимости от их назначения.
Параметры визуализации находятся на вкладке «Вид» рис. 5.9. Здесь можно изменить масштаб, положение начала координат, включить отображение проекций и дополнительных панелей инструментов, изменить способ имитации объемного изображения.
Параметры моделирования, такие как шаг интегрирования, интервал или количество итераций, физические характеристики ткани - коэффициенты жесткости связей, толщина и масса ткани вводятся на вкладке «Свойства» рис. 5.10.
Поля редактирования и элементы управления необходимые для изменения положения, размеров и ориентации в пространстве объектов моделирования расположены на вкладке «Редактирование» рис. 5.11.
Подробное описание интерфейса приведено в приложении 1.
Разработанное программное обеспечение значительно ускоряет процесс подготовки исходных данных для моделирования, предоставляет возможности редактирования и сохранения исходной модели, параметров и результатов моделирования. Пошаговая визуализация результатов, позволяет следить за динамикой процесса моделирования. Формат входных и выходных файлов организован таким образом, что можно без труда организовать импорт и экспорт данных в систему AutoCAD средствами языка LISP.
Все вышеперечисленное позволяет избежать лишних временных затрат и сосредоточиться на сути вычислительных экспериментов, для которых и разрабатывалась программа.
Для определения массы каждой частицы ткани исходной величиной выбрана поверхностная плотность р кг/м. Площадь ткани S можно вычислить как сумму площадей составляющих ее треугольников. Тогда если общее количество частиц равно N, то масса каждой частицы w = — кг. N Координаты частиц и толщина ткани измеряются в метрах, а интервал и шаг интегрирования в секундах. Параметры, характеризующие физические свойства ткани подбирались экспериментально.
