Разработка физической модели разбиения твердого тела для игрового движка

Создать новую статью

Дата последнего изменения :   29.09.2009 17:34
Рейтинг
 


Аннотация

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

Что, зачем и как?

Всем известный факт, что до 80-90% информации человек принимает визуально, кроме того он наделен высоко развитым навыком наблюдения движения и быстро распознаёт движение нехарактерное, невозможное для движущихся объектов. Мы непроизвольно начинаем сравнивать мир игровой (виртуальный) с миром реальным. Такие спецэффекты, как: клубы дыма, идущие от самоходной установки, в которую попал снаряд; отражения луча прожектора от мокрых стен; «живая» вода, бегущая волнами от ног героя; «осыпающиеся» от взрыва стеклянные витрины - никого не оставляют равнодушными: ни продвинутых геймеров, любящих смаковать детали игры, ни гейм-дизайнеров, любящих ввернуть в игру что-нибудь этакое.

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

Остановимся на одном из игровых моментов – хулиганском желании разбить окошко в домике. И не только окошко – дверь, стены и т. д. Еще недавно никакой надежды на физическую подоплеку такого явления не было – максимум, чем могли порадовать производители, была возможность получить заранее заданное разбиение объекта. Художник рисует «паутину» трещин, и в час «X» объект распадается по заранее проведенным линиям. И сколько бы раз вы ни били, и в какую бы область ни целились, результат всегда один, к тому же из полученных осколков нельзя собрать исходный объект. Современные графические процессоры позволяют имитировать явления максимально приближённо к реальности, создавать гейм-эффекты, основанные на расчётах физической модели, и при этом укладываться в realtime.

Стоит отметить, что требования к имитации в компьютерной графике, анимации, играх и инженерии довольно сильно отличаются друг от друга. Прикладная инженерия требует точности в расчётах, чтобы имитация могла передать поведение, характерное для реального мира. В visual computing, напротив, в первую очередь нужна высокая скорость моделирования, естественность при зрительном восприятии, а уже потом численная точность, а потому при решении задач реального физического моделирования идут на различные упрощения. Для изготовления очередного игрового украшательства используется физическая модель определенной степени огрубления, которая может быть применена, исходя из текущих ограничений и условий игры. Так, например, разваливающиеся домики, дробящиеся кирпичи, рвущаяся одежда становятся явлениями весьма схожими по своей физической природе, а, значит, могут быть реализованы с учётом общих законов механики разрушений.

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

Опыт прошлых лет

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

Описания подобных исследований можно найти в работах JamesF. O’Brien [1,2] и коллектива разработчиков из Стэнфорда [3]. Demetri Terzopoulos и Kurt Fleischer в Schlumberger Research представили общую технику анимации вязкоупругой и пластичной деформаций. Они смоделировали эффект трещины, разрывая связи между двумя точками, когда расстояние между ними превышало некоторый заданный порог. Они продемонстрировали эту технику, имитируя разрыв бумаги на клочки и разрыв ткани. AlanNorton и его коллеги в IBM Research разбили модель фарфорового чайника, используя подобную технику. Оба вида анимационной техники показали хорошие результаты, они достигли разлома между границами в исходных ячейках, создавая ложное изображение в местах разрыва. Это особенно заметно в местах границ объекта, создаётся эффект похожий на зазубрины, который появляется при преобразовании границы многоугольника в растровый формат.

В значительной степени трещины были изучены в литературе по механике. Из молекулярной динамики известно, что силы, действующие на уровне атома, гораздо больше, чтобы преодолеть межатомные связи, удерживающие вещество в первоначальном состоянии. Однако в механике разрушения нет четкого понятия механизма распространения трещин. Литература по механике содержит теории, которые абстрактно и отвлечённо описывают разломы мелкого масштаба по отношению к макроскопическому уровню. Работы отечественных авторов в основном посвящены инженерным подходам [7].

Разрушаем по науке

Задача в данном случае формулируется следующим образом:

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

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

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

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

Для нахождения поля напряжений решаем динамическую задачу теории упругости, которая описывается системой тензорных уравнений в заданном объеме сплошной среды Ω с граничными условиями на ее поверхности Γ = Γt+Γu:

где σ – тензор напряжений,

ε – тензор деформаций,

u = u(r,t) – вектор перемещений, зависящий от времени t и радиус-вектора r точек сплошной среды,

bi = bi(r,t) – вектор заданных объемных сил, зависящий от времени t и радиус- вектора r точек сплошной среды, здесь же скрывается информация от точки контакта,

ρ – плотность вещества,

θ – объемная деформация,

λ, μ – коэффициенты Ламе: жёсткость вещества определяется величиной μ, а λ контролирует сопротивление к изменениям в объеме (расширение)

Коэффициенты Ламе связаны с техническими константами вещества: модулем упругости Е, модулем сдвига G и коэффициентом Пуассона ν следующими соотношениями:

В классической задаче теории упругости граничные условия, заданные на поверхности Г, могут быть двух типов: кинематические и силовые граничные условия. Предполагается, что каждый тип граничных условий задан на своей части поверхности: Гu и Гt соответственно.

%u0413%u0440%u0430%u043D%u0438%u0447%u043D%u044B%u0435%20%u0443%u0441%u043B%u043E%u0432%u0438%u044F

Кинематические граничные условия заданы на части поверхности Гu и могут быть записаны в следующей форме:

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

Силовые граничные условия заданы на части поверхности Гt и Гс и могут быть записаны в следующей форме:

Правая часть представляет собой заданные поверхностные силы, а левая часть – вектор напряжений на площадке с нормалью n.

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

Далее применяя какой-либо численный метод к решению данной системы уравнений, находим поле напряжений. В частности, данная задача решалась на треугольной регулярной сетке модифицированным методом конечных элементов, предложенным St. Bordas [4,5].

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

По полю напряжений рассчитываются внутренние силыf[i], необходимые для «расщепления» узлов – раздвоения разностной сетки по узлам.

где А - площадь элемента,

p[j] - позиция j-й вершины в глобальных координатах,

β - матрица перехода из локальных в барицентрические координаты,

νi(σ)- собственное число тензора напряжения,

ni(σ)- собственный вектор тензора напряжения,

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

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

Проще простого

Эврика! Зачем мы мучаемся с физикой, а почему бы не построить алгоритм на эвристике?

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

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

  • Генерируем несколько окружностей, удаленных от точки приложения импульса по экспоненте.
  • На каждой окружности ставим примерно на одинаковом расстоянии точки, и соединяем точки соседних окружностей со смещением, чтобы получить «зазубрины».
  • Проводим трещину - соединяем смежные точки на окружностях (на последних двух окружностях это не делается, иначе получим идеально выбитую окружность).
  • Полученные четырех угольники разбиваем на треугольники путем проведения диагоналей случайным образом.

В случае с магистральными (линейными) трещинами паттерн имеет следующий вид:

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

От трещин к осколкам

Полученные тем или иным способом трещины хранятся в виде графа. Осколок однозначно задается графом трещин, шириной и высотой. Граничные рёбра в графе задают форму объекта и имеют направление. Для каждого ребра хранится номер контура, в который оно входит. Для внешнего контура направление обхода выбрано против часовой стрелки, а для внутренних (отверстия) – по часовой стрелке. Остальные (неграничные) рёбра задают трещины внутри объекта, и направление для них не важно.

Граф является планарным. Если обнаруживается пересечение рёбер, то точке пересечения добавляется вершина, а рёбра разбиваются. Каждый цикл в графе образует один из контуров объекта – рёбра в нём граничные. Если в графе обнаруживается еще не помеченный цикл, в котором рёбра из разных контуров или есть неграничные рёбра, то он образует новый осколок. После обнаружения цикла, его содержимое вырезается из исходного графа и переносится в граф нового осколка. Направление образующего цикла меняется на противоположное.

Циклы в графе находятся по алгоритму поиска в глубину. В ходе разработки специальной библиотеки для работы с графом трещин возникала проблема с пересекающимися циклами. Возможно два варианта пересечения циклов:

  • Новый цикл содержит уже отмеченный цикл. Циклы имеют общие рёбра с совпадающим направлением обхода.
  • Новый цикл пересекает уже отмеченный цикл. Циклы имеют общие рёбра с различным направлением обхода.

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

Для визуализации разбиения твёрдого тела был выбран графический API OpenGL, кроме того для визуализации осколков и окружения были разработаны шэйдеры.

Для получения 3D-модели для отображения осколков была использована библиотека тесселяции из GLU (OpenGL utility library), а для реализации динамики осколков был выбран физический движок Bullet (www.bulletphysics.com).

Результаты наших стараний

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

К окончанию летней школы была представлена демонстрационная версия приложения, позволяющего:

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

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

Планы на будущее

Работы ещё довольно много, есть и новые идеи. В первую очередь необходимо довести реализацию алгоритма с использованием физически обоснованной теории до конечного результата. Затем можно будет визуализировать разрыв металла, ткани, бумаги и т.п., внедрить данные эффекты в какой-нибудь игровой проект. Также стоит подумать над распараллеливанием алгоритма.

Об авторе и от автора

Зайцева Наталья (КГУ, Казань) проходила стажировку в рамках летней школы Intel-ННГУ в Нижнем Новгороде. Хотелось бы отметить огромный вклад своих коллег, летних школьников Бородинова Льва (ВолГТУ, Волгоград) и Бугаева Ильи (ННГУ, Нижний Новгород). Достигнутые результаты стали возможны благодаря их участию в работе над данным проектом. Помимо удовольствия от участия в летней школе, полезной информации, навыков и умений, полученных на лекциях и мастер-классах, я приобрела замечательных друзей в лице неутомимых, целеустремлённых и богатых на идеи ребят из Волгограда. Они научили меня играть в манчкин, просветили на тему спортивного программирования и CodeGameChallenge, в котором, к слову, моя команда заняла почётное второе место.

Пользуясь случаем, в очередной раз хочу поблагодарить организаторов, а именно Фадину Ларису Михайловну, которая заменила нам маму на эти полтора месяца, сотрудников IntelСидорова Сергея и Лялина Сергея за направление наших бурных фантазий и путаных идей в нужное русло, а также отметить увлекательные и запоминающиеся мастер-классы от Антона Бевзюка и Евгения Сорокина. Отдельное спасибо коллективу преподавателей ВМК ННГУ за лекции и лабораторные работы по параллельному программированию, в данный момент я читаю небольшой спецкурс на эту тему студентам КГУ.

Используемая литература

  1. O’Brien, J. and Hodgins, J. Graphical modeling and animation of brittle fracture. In Proceedings of SIGGRAPH’99 (Los Angeles, Calif., Aug. 8–13). ACM Press, New York, 1999, 137–146.
  2. James F. O’Brien. Graphical Modeling and Animation of Fracture. A Thesis of a dissertation for the degree Doctor of Philosophy in Computer Science, Georgia Institute of Technology, July 2000, p.145
  3. Zhaosheng Bao, Jeong-Mo Hong, Joseph Teran, and Ronald Fedkiw. Fracturing Rigid Materials, Stanford, 2006.
  4. St. Bordas. An eXtended Finite Element Method for Elastic and Elastic-Plastic Cracks in Complex Components, Department of Mechanical Engineering, McCormick School of Engineering and Applied Science, Northwestern University, November 16, 2001.
  5. St. Bordas. Extended Finite Element and Level Set Methods with Applications to Growth of Cracks and Biofilms, a dissertation for the degree Doctor of Philosophy (Field of Theoretical and Applied Mechanics), December 2003, p.254
  6. Vinh Phu Nguyen, Timon Rabczuk , Stephane Bordas, Marc Duflot. Meshless methods: A review and computer implementation aspects, 2008 IMACS. Published by Elsevier, p. 51
  7. Пашков С.В. Численное моделирование фрагментации толстостенных цилиндрических оболочек при взрывном нагружении. Диссертация на соискание ученой степени кандидата технических наук, Томск - 2000