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

н

ЕРМОЛИН Егор Николаевич

МЕТОДЫ ОПРЕДЕЛЕНИЯ И РАЗРЕШЕНИЯ СТОЛКНОВЕНИЙ НА ПОЛИГОНАЛЬНЫХ МОДЕЛЯХ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

Новосибирск-2011 1 2 МАЙ 2011

4845142

Работа выполнена в Учреждении Российской академии наук Институте систем информатики им. А.П. Ершова Сибирского отделения РАН

Научный руководитель: кандидат физико-математических

наук

Ушаков Дмитрий Михайлович

Защита состоится 10 мая 2011 г. в 15 ч. 00 мин. на заседании диссертационного совета Д 003.061.02 при Учреждении Российской академии наук Институте вычислительной математики и математической геофизики Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института вычислительной математики и математической геофизики Сибирского отделения РАН.

Официальные оппоненты:

доктор технических наук, доцент Дебелов Виктор Алексеевич

кандидат физико-математических наук, доцент Сарайкин Виталий Александрович

Ведущая организация: Учреждение Российской академии

наук Институт автоматики и электрометрии Сибирского отделения РАН

Автореферат разослан

апреля 20'1 г

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

диссертационного совета Д 003.061.02 при ИВМиМГ СО РАН, д.ф.-м.н.

Сорокин С. Б.

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

Актуальность работы. Развитие ЭВМ и растущая доступность персонажных компьютеров, игровых приставок и прочих мультимедийных устройств повлекло рост потребности в интерактивных приложениях, моделирующих виртуальную среду и позволяющих получить нужную информацию или ожидаемое поведение от некоторого виртуального объекта, обычно являющегося моделью реального объекта. Примерами могут послужить расчеты прочностных характеристик деталей, осуществляемые инженером в современной САПР; нахождение массы тела; моделирование движения автомобиля в игровом симуляторе. В настоящей работе рассмотрена задача математического моделирования движения системы твердых недеформируемых тел, актуальная для нескольких прикладных областей: цифровое прототипирование как часть процесса разработки изделия с помощью САПР; виртуальных средах, позволяющих получить опыт взаимодействия в реальной среде (космические экспедиции и т.п.); игровых приложениях. Важнейшими требованиями пользователей данных приложений являются достоверность математической модели, соответствие результатов виртуальных испытаний результатам физических опытов; и быстродействие - обычно ожидается, что расчет должен происходить в интерактивном режиме.

Методы определения столкновений и расчета реакции тел на столкновение являются алгоритмической основой решения данной задачи. Анализ опубликованных подходов по решению задачи определения столкновений показывает, что наиболее эффективными с точки зрения производительности и качества результата являются методы, работающие на выпуклой полигональной геометрии, что делает актуальной задачу приближенной выпуклой декомпозиции, строящую покрытие исходной геометрии набором выпуклых тел. Задача приближенной выпуклой декомпозиции рассмотрена для плоского случая, было показано, что существующие подходы строят избыточное покрытие, тяготеющее к триангуляции, поэтому их необходимо улучшать. Существующие методики по расчету реакции твердых недеформируемых тел на удар используют модель мгновенного обмена импульсами между телами и имеют ограниченную область применимости - предлагаемые решения либо обрабатывают соударения поочередно, что дает нереалистичный результат, либо, оперируя неравенствами для задания условий непроникновения тел, не удовлетворяют закону сохранения кинетической энергии системы при абсолютно упругом ударе. Таким образом, актуальной задачей расчета реакции тел на удар является разработка метода, обрабатывающего удары комплексно при соблюдении законов сохранения импульса, момента импульса и энергии. Расчет реакции тел на удар, препятствующей проникновению тел друг в друга, и соответствующее изменение положений и скоростей тел обычно называют разрешением столкновений (collision resolution).

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

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

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

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

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

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

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

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

- реализация разработанных алгоритмов;

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

- разработка и реализация динамического модуля;

- проведение вычислительных экспериментов;

- - создание программного средства Noir для визуализации результатов моделирования.

Область исследования. Содержание диссертации соответствует специальности 05.13.18 "Математическое моделирование, численные методы и комплексы программ", области исследования п. 1 "Разработка новых математических методов моделирования объектов и явлений", п. 3 "Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий" и п. 8 "Разработка систем компьютерного и имитационного моделирования" Паспорта специальности.

Научная новизна работы заключается в следующем;

- предложен метод приближенной выпуклой декомпозиции двумерного многоугольника с внутренними границами;

- предложено усовершенствование метода разрешения столкновений, отвечающее законам механики твердых тел;

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

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

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

Достоверность полученных результатов подтверждается:

- численными экспериментами на модельных тестах, имеющих аналитические решения;

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

- физическим экспериментом, заключающемся в измерении времени удара последней кости домино в цепочке и визуализации движения. Время, полученное с помощью расчетов, отличается в среднем на 20% от измеренного в реальном эксперименте, качественная картина движения костей воспроизведена достоверно.

Апробация работы. Основные научные результаты докладывались автором на международных конференциях isiCAD 2004 (Новосибирск, Россия, 2004), GraphiCon (Новосибирск, Россия, 2005), на конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, Россия, 2007), на семинаре "3D графика и геометрия, высокопроизводительные вычисления" (Новосибирск, Россия, 2008), на выпускном семинаре ИСИ СО РАН (Новосибирск, Россия, 2010) под руководством д.ф.-м.н., профессора Марчука А.Г..

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

Структура и объем работы Диссертационная работа состоит из введения, шести глав, заключения и списка литературы. Общий объем работы - 155 страниц. Список литературы содержит 67 наименований. Работа включает 14 таблиц, 89 рисунков и графиков.

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

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

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

определения геометрических и динамических свойств тела и связь с пользовательским приложением. Подходы по определению и разрешению столкновений работают над статичным, моментальным снимком системы; динамический модуль оперирует временным шагом. Каждый шаг определяется уникальной конфигурацией - положениями, скоростями тел, приложенными внешними по отношению к телам силами. При переходе на следующий шаг производится приращение скоростей, вызванное внешними силами, и пересчет трансформаций (положения центра масс и ориентации тел). Пересчет скоростей тел, вызванный столкновением тел, осуществляется модулем разрешения столкновений и занимает ровно один временной шаг динамического модуля. В разделе первой главы Определение столкновений рассматриваются современные подходы по определению столкновений на полигональных моделях. Дается постановка задачи, рассматриваются две фазы определения столкновений; разбирается базирующийся на методе ОПЬегЫоЬпзоп-КееЛЫ (ОЖ) алгоритм, определяющий столкновение выпуклых тел путем анализа их разницы Минковского. Ограничение работы алгоритма поддержкой только выпуклых тел требует приближенной выпуклой декомпозиции, разобранной в разделе этой же главы. Вследствие сложности решения задачи в трехмерном пространстве была рассмотрена задача приближенной выпуклой декомпозиции многоугольника в двумерном случае. Раздел Разрешение столкновений дает описание различных современных подходов по разрешению столкновений: штрафные методы, на которых основана пружинная модель, импульсный подход, развитый в настоящей работе, и псевдодинамический подход, основанный на создании и разрешении геометрических ограничений. Первые два подхода более реалистично моделируют взаимодействие системы тел. Для данных методов разрешения столкновений определение столкновений на основе ОЖ оказалось лучшим выбором.

Во второй главе, посвященной Динамическому модулю, вводятся законы динамики твердого тела, изучаемые в рамках теоретической механики. В этой главе вводятся понятия, определяющие геометрические, кинематические и динамические свойства тела. Помимо формы тела, основным геометрическим свойством является трансформация Т=<?,о> тела (положение и ориентация локальной системы координат относительно мировой). К кинематическим свойствам относятся моментальные поступательная V и угловая а скорости тела; соответствующие ускорения а и е. Кинематика твердого тела в мировой системе координат описывается системой обыкновенных дифференциальных уравнений:

сВ - й® _ От - ¿д _

— = а: ——- = Е ■—=у:— = о> (1)

а Ж Ж Л Вводится понятие временного шага Л/ и на основе формул (1) определяются формулы пересчета трансформации тел и скоростей. С помощью явной разностной схемы первого порядка точности система (1) заменяется системой разностных уравнений:

V = V,, + аЫ ; 3 = 30 + ЕЫ; Г = Г0 + V Д/; О = 0„ + ЙЛ/; (2)

где нижним индексом "О" обозначены значения функций на предыдущем шаге. К динамическим свойствам относятся: масса т, центр масс, тензор инерции ./, сила Р,

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

Здесь {F,) - множество внешних сил, приложенных к телу, {/;) - радиус-вектора от центра масс тела к точкам приложения сил, тензор инерции тела определен относительно мировой системы координат.

Работа динамического модуля заключается в:

1. Получении изначальной конфигурации от пользовательского приложения: геометрии {G,},;e(l,n); трансформаций {7]},;е (1,п); начальных скоростей {{?,.<",}},/е(1, л) тел; внешних сил {{F^jnd^j е(\,т), приложенных к центрам масс тел, где ind1 - индекс тела, к которому приложена сила; вращательных моментов ({Л7;),indl},_/ е (1, да);

2. Нахождении массы {ш,},/е(1,и), тензора инерции {7,},;е(1,и) тел, для чего пользователь задает удельную плотность ¡р,}.;е (!,/»)• Можно комплексно определить тело, как совокупность геометрических, кинематических и динамических свойств, доступ к которым имеет как пользовательское приложение, так и динамический модуль:

3. Выполнении шага моделирования - пересчете скоростей, ускорений по формулам (2);

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

5. Разрешении столкновений - изменении скоростей тел, чтобы в следующий временной интервал взаимопроникновения не произошло;

6. Продолжении шага моделирования - пересчете положений тел вследствие скоростей тел по формулам (2);

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

Метод выпуклой декомпозиции, представленный в данной работе, поддерживает только плоскую геометрию, представленную набором замкнутых многоугольников. В связи с распространением форматов данных, описывающих треугольные сетки было решено воспользоваться ими для представления входных данных. Был реализован алгоритм нахождения плоской границы (контура) треугольной сетки-призмы, симметричной относительно плоскости ОХУ. Для нахождения динамических свойств тел - массы, центра масс и тензора инерции, насчитанного в центре масс, используется способ подсчета, в основе которого лежит подсчет и аккумуляция динамических свойств пирамид, образованных ориентированными треугольниками сетки и некоторой точкой в пространстве. Например, объем пирамиды может входить в общую сумму как со знаком "плюс", так и "минус", в зависимости от положения

(3)

(4)

точки относительно треугольника. Координаты точки столкновения и направления разрешения столкновений транслируются в трехмерное пространство по закону: (Р,,Р,)-+(Р„Ру,0) (яЛ,п,)-»(»„яг,0) (5)

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

В третьей главе, Определение столкновений, даны описания метода Gilbert-Johnson-Keerthi (GJK) определения столкновения между телами, и метода Expanding Polytope (ЕРА) нахождения направления разрешения столкновений и минимальной глубины проникновения пары выпуклых тел. Под точкой контакта здесь и далее будем понимать точку, лежащую на одном из тел и относящуюся к проникновению другого тела. Главной точкой контакта считается точка, соответствующая точке наиболее глубокого проникновения тел. Предложен способ нахождения дополнительных точек контакта, требуемых для моделирования стабильных конфигураций тел. Функционально модуль определения столкновений можно определить следующим образом:

- на вход он принимает множество геометрий тел и их трансформаций {а,, т,};

- выходом служит набор контактов {C} = {{A,BJpn,dl}}. Каждый контакт описывает пару индексов тел А и В, мировые координаты точки столкновения, направление разрешения столкновения Я, глубину dj проникновения тел, соответствующую данной точке.

В основе алгоритмов GJK и ЕРА лежит работа с разницей Минковского пары тел -информация о столкновении находится путем построения геометрических примитивов на вершинах оболочки разницы Минковского. Определение столкновений для множества тел заключается в прогоне алгоритмов GJK/EPA для каждой пары тел - выполнении так называемой узкой фазы определения столкновений. Совокупность методик ускорения работы узкой фазы путем отсечения заведомо непересекающихся пар тел называется широкой фазой определения столкновений и к ней можно отнести окружение геометрий тел примитивами, проверка которых на взаимное пересечение выполняется быстро. При создании модуля определения столкновений в качестве ограничивающего примитива был выбран ориентированный прямоугольник, для нахождения которого был использован точный метод Rotating Calipers.

Обработка невыпуклых тел требует препроцессинга геометрии: строится приближенная выпуклая декомпозиция невыпуклой геометрии о е ¡о,}, где jg,} -множество геометрий входных тел. Результатом декомпозиции каждой геометрии является составная геометрия G -»{G'i\G:, выпуклая,^jG\sG}. Составная выпуклая

геометрия {С,) будет передаваться в модуль определения столкновений в качестве геометрического представления данного тела. Задача приближенной выпуклой декомпозиции изложена в пятой главе.

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

- при абсолютно неупругом ударе нормальные скорости тел в точках контакта после удара будут равны, тела перестанут проникать друг в друга;

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

Таким образом, задача продолжительного контакта (пересечения) и передачи конечной силы в течение короткого промежутка времени сведена к моментальному контакту и передаче конечного импульса. Направлением импульса будет направление разрешения столкновений:

Р = рп (6)

величина импульса р является неизвестной. Согласно принятой ранее нотации, на вход разрешения столкновений поступает набор контактов {С} ={{А.В,ггп,с1,}}: идентификаторы пары тел, мировые координаты точки контакта г, направление разрешения я, внешнее для тела А. Глубина проникновения не играет роли, поскольку считается незначительной. Для каждой точки контакта определяется относительная скорость

гЛП = Ь {г)-?в{7) (7)

Под г,понимается скорость точки тела А, имеющей мировые координаты г. Данная скорость является функцией поступательной скорости у , центра масс тела А и угловой скорости <3, тела:

?.,(?) = V,+<яА X(г-г(,,) (8)

где гс, - координаты центра масс тела А, аналогично определяется ?„(г). После чего берется проекция относительной скорости на направление разрешения:

= (9)

Далее согласно полученной величине \-рг] следует классификация точки контакта:

точка "проникновения", если не предпринять никаких урп >0 действий, то в следующий момент проникновение увеличится.

,, = о точка "касания", контакт сохранится в следующий момент (10) " времени.

<(у точка "покидания", в следующий момент тела перестанут " касаться в данной точке. Интерес представляют точки с положительным значением проекции, так как точки остальных двух классов не приведут к взаимному пересечению тел в следующий момент. В предложенном в настоящей работе импльусном подходе решается следующая задача: какие импульсы нужно применить в каждой точке проникновения соответствующей пары тел вдоль направления разрешения, чтобы все точки проникновения превратились в точки касания? Скорость данной точки тела зависит

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

се! | Аг,вг,;,а,<*',) ,х -я,-

тх (11)

Зх = ыох + Гх ]Г 5&п(х> С)р{7с -гх)хпс

Спил- .в,- гЯЛМ.Х'А-юиХ^В,.. Функция 5§п(Л',С) для точки контакта Си телаХопределяется как

5ёп(А\С) = = (12)

[ 0,иначе

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

- - Се{{Гг.гг.г.п,</Ц.А=)'с«™А=2г

= -—-+

тА (13)

+ (®о л +Гл ^Щп(А,С)р(гс-гА)хпс)х(г-?А)

а проекция относительной скорости тел А и В в точке столкновения на направление разрешения столкновения • (г) - уге,п = (V, (г) - л>в (г))п =

СЧЦГг.2с,г,М)М=1'г|"«'<=2('__- ! ¡'г Л с .г ,Я ,<1)), В =У,-ми»=г,-

- 1.У0Л + У0В

«л тв (14)

+ {< + ¿А Е ^^ ~7А) ■Х "г):* (г -г А)

- (¿50£ + X С)Р^с ~ 7в ) х »с ) х (г -.гл ))й

Потребуем теперь, чтобы все проекции относительных скоростей в точках проникновения на направления разрешения были равны 0. Вводим множество С':

{С\С е[{Ас,Вс,г,Я,<1}),грг](?с-)> 0) (15)

Для каждой точки контакта из множества С' требуем

%,•(?.) = 0 \/с'еС' (16)

Проиндексируем элементы множества С':

С'={С„С2,...,СП> (17)

(19)

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

Ар = В (18)

и определим элементы матрицы А и правого столбца Ь. Элемент А:] матрицы описывает влияние точки контакта С, на проекцию относительной скорости тел в точке С,. Элементы матрицы А и столбца Ь в явном виде:

Д; = Д} ~ Д/

4 = Ьёп(4- , С, + (Г', (гС} - г^) х ) х (?г - ?л,)) •

тлс,

( "с \

Д; = 5ёп(Вс ,С,+ (гс -г )х пс )X (гг - г )) ■ п

"с,

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

р', = (1 + е,)р<; е,=еХАс,Вс ) (20)

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

Теорема 1 (О сохранении импульса и момента импульса). При разрешении столкновений системы незакрепленных тел и применении найденных в (18) импульсов к телам импульс и момент импульса системы сохраняются.

Теорема 2 (О сохранении энергии). При разрешении столкновений системы незакрепленных тел и применении найденных в (18) импульсов к телам с коэффициентом восстановления равным 1 во всех точках контакта, кинетическая энергия системы сохраняется.

Если задать в точке контакта три направления, совпадающие с осями мировой системы координат с коэффициентами восстановления равными нулю, то после разрешения относительная скорость пары тел в этой точке станет равной нулю, в следующий момент времени точка контакта между телами сохранится. Это позволяет естественным образом ввести геометрическое ограничение типа "сферическая кинематическая пара". Согласно принятой во второй главе схеме, при переходе на следующий шаг смещение тел будет линейным относительно шага по времени. Точка тела А, занимающая сейчас положение 7Л , по прошествии времени д/ будет иметь координаты

Гл = ГА+{У0А+-—-*-'-+

Пл (21)

+ «4 ^^пСЛ.СХгс-гА)хпс)х{?-7-а))А^у„

Сеигс.гг.г.амп.А=гсшп1Лшг1. Аналогичным образом вычисляются координаты точки тела В. Условие совпадения координат точек тел в следующий момент времени

г\ = г'в (22)

дает по уравнению на каждую координату.

Сила трения скольжения относится к внешней силе, ее учет выполнен в динамическом модуле. Она направлена против вектора относительной скорости в точке контакта и по модулю равна |, где Я - сила реакции опоры в точке, ц-коэффициент трения между телами. Силы реакции опоры, действуя в течение времени А/, равно как и импульсы, предотвращают проникновение тел, что позволяет установить связь

р ~ Ям (23)

Таким образом, применив к телам импульсы в направлении, противоположном касательной составляющей относительной скорости в точках контакта и равные по модулю я]/>'|, ц\р"'\..., можно достаточно успешно моделировать действие

силы трения скольжения.

В пятой главе, Приближенная выпуклая декомпозиция, предлагается эффективный алгоритм покрытия многограничного многоугольника выпуклыми однограничными многоугольниками с контролируемым качеством приближения. Дается определение контура как границы многограничного многоугольника. Обозначение контура - (С), что следует понимать, как "множество замкнутых ломаных (границ)", число границ обозначено ||{С}||. Контур с п границами кратко обозначается как п-контур.

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

SplitMulti Итеративное упрощение я-контура (п > 2) до 2-контура путем отсечений границ. На каждой итерации отсечение уменьшает число границ на 1. Отсекаемые области представляют собой невыпуклые 1-контуры

SplitDuo Деление 2-контура на пару невыпуклых 1-контуров

Simplify Рекурсивное деление получившихся на предыдущих шагах однограничных контуров. Каждый контур делится до тех пор, пока не выполнится условие останова, связанное с исходным параметром яГЬт. После этого каждый контур заменяется своей выпуклой оболочкой

В основе алгоритмов лежат атомарные топологические операции: вставка новой вершины в контур; деление ребром I-контура; вырезание 1-контура из «-контура по двум ребрам. До и после операций контур остается многообразным, атомарность означает, что все промежуточные действия по перестроению контура, во время которых нарушается его топологическая целостность, неподконтрольны извне. Метод подбора делящих отрезков является эвристическим и учитывает следующие факторы: локальную невыпуклость контура; углы, образованные ребром деления с границей контура; периметр контуров, полученных в результате деления. Алгоритмы SplitMulti и SplitDuo не упрощают исходную геометрию, контроль качества декомпозиции лежит полностью на Simplify. Временная сложность алгоритма SplitMulti определяется как 0(||{C}||nlog/i)+0(||{C}|f п). Квадрат ||(С}|[ относится к худшему случаю, и на практике время работы в среднем можно оценить как 0(|| (С) || пlogп). Временная сложность алгоритма SplitMulti - O(nlogn), где п - число вершин контура {С}, достигается при нахождении выпуклой оболочки внутренней границы контура. Временная сложность алгоритма Simplify в худшем случае оценена как 0(n\ogn). и соответствует контуру с зигзагообразной границей и

□ООО □□оо -1 ¿И

УТ

1

□□оо <

Исходный контур Разбиение с высокой точностью Более грубое разбиение

Рис. 1 Пример выпуклой декомпозиции многограничного контура

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

~7777^77777777777~

комбинация стала возможна в виду высокой степени модульности реализованных алгоритмов. Для визуального тестирования и создания иллюстраций и демонстрационных роликов было реализовано \¥т32-приложение Noir, выступающее в роли пользовательского приложения и использующее описанные выше модули. Использование MFC с архитектурой документ-вид позволило упростить создание каркаса приложения, визуализация сцены выполнена с помощью OpenGL. Задание сцен выполняется с помощью текстовых файлов, разбитых на секции (опции, геометрия, трансформации, скорости, ограничения и т.д.).

Приведены результаты тестовых расчетов. В частности, для проверки достоверности был проведен физический эксперимент. На поверхности гладкого стола установлено 27 костей домино рубашкой в одну сторону с расстоянием D между рубашками соседних костей. Перед выстроенной цепочкой под углом положена книга, так что расстояние от рубашки первой кости домино до нижней точки книги равно S. Высота наивысшей точки книги над столом равна Н. С верхнего края книги отпускается кость домино и сбивает цепочку, замеряется время между ударом первой и последней в цепочке, двадцать седьмой, кости домино. Для реального эксперимента была взята книга с гладкой обложкой с размерами 22x15x3.6 см, размер кости домино 3.9x1.9x0.7 см; параметры модели выбраны, как Н=14 см, S=2 см, D варьировалось от 1 до 3 см включительно с шагом 1 см. Эксперимент снимался на цифровую камеру, что позволило замерить время касания кости домино с точностью 30 мс. Съезд с верхней части обложки книги под действием силы тяжести хорошо воспроизводится в физическом эксперименте (время удара первой кости "битой" составляет 0.3+0.03 секунды с момента начала эксперимента); аналогичные начальные условия заданы при описании сцены определением положения биты. Результаты физического эксперимента представлены в Табл. 1.

Рис. 2 Модель эксперимента

D=1 см D=2 см D=3cm

Время между касанием первой и последней кости 0.26 с 0.50 с 1.15с

Табл. 1 Результаты физического эксперимента.

Во входном файле программы Noir была описана сцена, отвечающая начальным условиям данного эксперимента; с различными коэффициентами восстановления были воссозданы все три конфигурации с параметром D, сила трения скольжения не учитывалась. Смоделированное время контакта "биты" с первой костью домино составляет 0.28 с. В Табл. 2 в столбцах указаны значения коэффициентов восстановления, в строках - шаг по времени и параметр D. Во внутренних ячейках

е=0.7 е=0.8 е=0.9 е=1

д, =0.0003 D = 1 0.18 с 0.18 с 0.19 с 0.14 с

д, =0.0003 D = 2 0.43 с 0.43 с 0.43 с 0.43 с

д/=0.0003 D = 3 0.94 с 0.94 с 0.95 с 0.93 с

Табл. 2 Время между касанием первой и последней кости домино для соответствующих значений е

Минимальное отличие результатов от эксперимента при D=1 составило порядка 25%, для получения этого результата было выполнено в среднем 630 шагов моделирования. Минимальная ошибка при D=2 составляет 12%, моделирование в среднем заняло 1430 шагов. Расчет случая D=3 потребовал в среднем 3160 шагов и дал ошибку порядка 18%. Моделирование каждого шага заняло в среднем 0.02 секунды машинного времени Intel Dual Core % 2.7 GHz при однопоточных вычислениях. Легко заметить, что во всех случаях искомое время уменьшено, что может быть объяснено отсутствием силы трения при моделировании. Следует отметить явное качественное совпадение расчетов с результатами физического эксперимента._

Ы^..........- ц

J^zzsssszsssssss^(ЩИ

0.1 с 0.3 с 0.5 с

Табл. 3 Сопоставление физического эксперимента и моделирования при 0=2, за 0.0с принято время столкновения "биты" с первой костью

Моделирование воспроизвело удлинение начала цепочки в сторону "книги", показало адекватную работу в середине цепочки, удлинение хвостовой части цепочки и подчеркнуло такую деталь, как отрыв самой правой кости в цепочке при 0.5 с.

В Заключении сформулированы основные результаты диссертационной

работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

2. Реализован метод определения столкновений в двумерном случае для выпуклых тел на основе алгоритмов йЖ и ЕРА.

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

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

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

5. Для визуальной демонстрации результатов было реализовано приложение для 32-битной платформы Windows с использованием библиотеки классов MFC и графической библиотеки OpenGL.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Рецензируемые журналы по перечню ВАК

1. Ермолин Е.Н., Казаков А.Ю. Импульсный метод одновременного разрешения столкновений твердых тел // "Сибирский Журнал Вычислительной Математики", Том 9. - Новосибирск, 2006. - С. 253-262

2. Ермолин Е., Богданов М., Кусков Р., Лыков К., Попова А. Автоматическое определение минимальных габаритов деталей // "САПР и Графика", Выпуск 12. -Москва, 2007.-С. 80-81

Расширенные тезисы конференций, препринты, конференции и семинары

3. Ермолин Е.И., Казаков А.Ю. Impulse-based Simultaneous Resolution of Rigid Body Collisions // "isiCAD 2004. Proceedings of the International Forum". -Novosibirsk, 2004. - P. 214-223

4. Ermolin E.N., Kazakov A. Yu. Impulse-based Approach for Rigid Body Collisions Simultaneous Resolution // "Graphicon 2005. Conference Proceedings". -Novosibirsk, 2005. - P. 58-62

5. Ермолин E., Казаков А. Подход к моделированию механических систем твердых тел // "Препринт 10. ЗАО ЛЕДАС". - Новосибирск, 2004. - 60 стр.

6. Ермолин Е.Н., Личман И.В., Казаков А.Ю., Лавров Р.А. Построение гибридных полигональных сеток для задач САПР // Конференция-конкурс "Технологии Microsoft в теории и практике программирования". -Новосибирск, 2007.

7. Ермолин Е. Моделирование механических систем и связанные задачи // Семинар "3D графика и геометрия, высокопроизводительные вычисления" ИВМиМГ СО РАН, Intel-Novosibirsk. - Новосибирск, 2008.

ИСПОЛЬЗУЕМЫЕ СОКРАЩЕНИЯ

ЭВМ - Электронно-вычислительная Машина

САПР - Системы Автоматизации Проектных Работ

GJK - алгоритм определения столкновений, названный по фамилиям авторов Gilbert, Johnson,

Keerthi

ЕРА - Expanding Polytope Algorithm, алгоритм определения минимальной глубины

проникновения двух выпуклых тел

MFC - Microsoft Foundation Classes, библиотека классов корпорации Microsoft

Подписано в печать 01.04.2011г. Формат 60x84 1\16 Усл. печ. л. 1,0 Объем 16 стр. Тираж 100 экз.

Отпечатано в типографии ООО « Омега Принт» 630090, г. Новосибирск, пр. Ак.ЛаврентьеваД оф.3-022 тел/факс (383) 335-65-23 email: omegap@yandex.ru

Перечень условных обозначений.

Введение.

Общая характеристика работы.

Содержание работы.

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

Постановка задачи.

Решение задачи с помощью ЭВМ.

Представление геометрии тел.

Обзор методов определения столкновений.

Обзор методов разрешения столкновений.

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

Глава 2 Динамический модуль.

Глава 3 Определение столкновений.

Алгоритм GJK определения столкновений пары выпуклых тел.

Алгоритм ЕРА определения минимальной глубины проникновения и направления разрешения столкновений.

Нахождение дополнительных точек контакта.

Производительность алгоритма определения столкновений.

Оптимизация определения столкновений. Окружающие примитивы.

Глава 4 Разрешение столкновений.

Поддержка ограничений "кинематическая пара".

Учет силы трения.

Выбор метода определения столкновений.

Оптимизация метода разрешения столкновений.

Глава 5 Приближенная выпуклая декомпозиция.

Деление многограничного контура.

Деление двухграничного контура.

Упрощение однограничного контура.

Примеры работы приближенной выпуклой декомпозиции.

Общая характеристика работы Актуальность работы.

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

Рассмотрим задачу моделирования на ЭВМ движения системы твердых недеформируемых тел в соответствии с законами механики. Ее самое распространенное применение проще всего описать с точки зрения конечного пользователя — взаимодействие в некотором виртуальном окружении с предметами и предметов друг с другом, при этом предметы должны двигаться натуральным, привычным образом и, отталкиваясь, не проникать внутрь друг друга. Более строгая формализация потребует разделения задачи на два основных этапа — определения столкновений и пересчета скоростей тел в результате удара. Второй этап все чаще называют разрешением столкновений (collision resolution). Помимо этого в реализациях обычно существует еще третий модуль, согласовывающий работу вышеупомянутых. Также он отвечает за пересчет положений тел, скоростей под действием внешних сил (например, силы тяжести) и осуществляет взаимодействие с конечнопользовательским приложением.

Алгоритмы определения столкновений зависят от представления геометрии объектов, но, как правило, укладываются в общую схему - попарно рассматривают тела на предмет столкновений, предлагают подход по быстрому отсечению заведомо непересекающихся пар тел, после чего позволяют локализовать информацию о контакте. В настоящее время в качестве определения столкновений используются алгоритмы, производные от GJK+EPA, которые работают только на выпуклых телах. Это, в свою очередь, обращает внимание на задачу декомпозиции геометрии на выпуклые части. Таким образом, текущий фронт задач включает в себя как определение столкновений, так и вспомогательные задачи вычислительной геометрии.

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

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

Цель диссертационной работы: разработка и программная реализация алгоритмов определения и разрешения столкновений гранично заданных тел в соответствии с законами механики твердых тел.

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

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

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

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

- развитие метода для поддержки неупругих столкновений и ограничений типа "кинематическая пара";

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

- проведение вычислительных экспериментов;

- проведение физического эксперимента с костями домино;

- создание программного средства Noir для визуализации.

Область исследования. Содержание диссертации соответствует специальности 05.13.18 "Математическое моделирование, численные методы и комплексы программ", области исследования - п. 1 "Разработка новых математических методов моделирования объектов и явлений, перечисленных в формуле специальности", и п. 9 " Разработка систем имитационного моделирования" Паспорта специальности.

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

- предложен метод приближенной выпуклой декомпозиции двумерного многоугольника с внутренними границами;

- предложен метод разрешения столкновений, отвечающий законам механики твердых тел;

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

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

Достоверность полученных результатов подтверждается:

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

- численными экспериментами на модельных тестах, имеющих аналитические решения;

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

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

- физическим экспериментом, заключающемся в измерении времени удара последней кости домино в цепочке и визуализации движения. Время, полученное с помощью расчетов, отличается в среднем на 20% от измеренного в реальном эксперименте, качественная картина движения костей воспроизведена достоверно.

Апробация работы. Основные научные результаты докладывались автором на международных конференциях isiCAD 2004 (Новосибирск, Россия, 2004), GraphiCon (Новосибирск, Россия, 2005), на конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, Россия, 2007), на семинаре "3D графика и геометрия, высокопроизводительные вычисления" (Новосибирск, Россия, 2008),), на выпускном семинаре ИСИ СО РАН (Новосибирск, Россия, 2010) под руководством д.ф.-м.н., профессора Марчука А.Г.

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

Структура и объем работы Диссертационная работа состоит из введения, шести глав, заключения и списка литературы. Общий объем работы - 155 страниц. Список литературы содержит 67 наименований. Работа включает 14 таблиц, 88 рисунков и графиков.

Заключение

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

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

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

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

Для визуальной демонстрации результатов было реализовано Win32-приложение на MFC и OpenGL.

1. Ли К.: Основы САПР (CAD/CAM/CAE). // Питер, СПб 2004

2. Lombardo J.-C., Cani М.-Р, Neyret F.: Real-time Collision Detection for Virtual Surgery // Computer Animation May 1999

3. Lafleur В., Magnenat Thalmann N., Thalmann D.: Cloth Animation with Self-Collision Detection // IFIP Conference on Modeling in Computer Graphics, Springer, Tokyo, 1991 Tokyo, 1991,-pp. 179-187.

4. Sobottka G., Varnik E., Weber A.: Collision Detection in Densely Packed Fiber Assemblies with Application to Hair Modeling // Proceedings of CISST, June, 2005 pp. 244-250

5. Cohen J., Lin M., Manocha D., Ponamgi M.: Interactive and Exact Collision Detection for Large-Scale Environments. Technical Report TR94-005, University of North Carolina at Chapel Hill, March 1994.

6. Gottschalk S., Lin M.C., Manocha D.: OBBTree: a hierarchical structure for rapid interference detection. //ASM SIGGRAPH, 1996 pp. 171-180

7. O'Rourke J.: Finding minimal enclosing boxes // International Journal of Computational. Informatics Science, vol. 14 (3), 1985 pp. 183-199

8. Ермолин E., Богданов M., Кусков Р., Лыков К., Попова А.: Автоматическое определение минимальных габаритов деталей // САПР и Графика, Выпуск 12. Москва, 2007. - С. 80-81

9. Golshtein Е., Tretyakov N.: Modified Lagrangians and monotone maps in optimization. // New York: Wiley, 1996 p. 6

10. Klosowski J., Held M., Mitchell J.: Efficient collision detection using bounding volume hierarchies of k-DOPs. // IEEE Transactions on Visualization and Computer Graphics, 4(1), 1998 — pp. 21-36

11. Bradshav G., O'SuIlivan C.: Sphere-tree construction using dynamic medial axis approximation.// ACM SIGGRAPH, 2002 July, 2002, San Antonio, Texas- pp.22-40

12. Larsen E., Gottschalk S., Lin M.C., Manocha D.: Fast distance queries with rectangular swept sphere volumes // IEEE Conf., 2002, Vol.4 - pp. 37193726

13. Krishnan S., Patteka A., Lin M.: Spherical Shell: A Higher Order Bounding Volume for Fast Proximity Queries // Proceedings of 3rd International Workshop on Algorithmic Foundations of Robotics, 1998 pp. 177-190

14. Held M.: ERIT: A Collection of Efficient and Reliable Intersection Tests// Journal of Graphical Tools, volume 2 (4), 1997 pp. 25-44

15. Eberly D.: Intersection of a Sphere and a Cone // Technical Report, Magic Software, March 2002

16. Eberly D.: Intersection of Cylinders // Technical Report, Magic Software, November 2000.

17. Guibas L., Nguyen A., Zhang L.: Zonotopes as Bounding Volumes // Proceedings of 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, USA, 2003.

18. Fares C., Hamam Y. Collision detection for rigid bodies: a state of the art review // Graphicon 2005, Russia, Novosibirsk

19. Coeurjolly D., Hulin J., Sivignon I.: Finding a minimum medial axis of a discrete shape is NP-hard // Theoretical Computer Science, Vol. 406, Issue 12, 2008 pp. 72-79

20. Dey T., Zhao W.: Approximate medial axis as a voronoi subcomplex // Proceedings of the seventh ACM symposium on Solid modeling and applications, 2002 — pp. 356-366

21. Foskey M., Lin M., Manocha D.: Efficient computation of a simplified medial axis // Proceedings of the eighth ACM symposium on Solid modeling and applications, 2003 — pp. 96-107

22. Bradshaw G., O'Sullivan C.: Sphere-tree construction using dynamic medial axis approximation // Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, 2002 pp. 3340

23. Lin M.: Efficient collision detection for animation and robotics // PhD Thesis, University of California, Berceley, USA, 1993.

24. Mirtich B.: V-Clip: Fast and robust polyhedral collision detection // ACM Trans. Graph, Vol.17, N. 3., July, 1998 pp. 177-208

25. Cohen J., Lin M., Manocha D., Ponamgi M.: I-COLLIDE: an interactive and exact collision detection system for large-scale environments // Proceedings of the 1995 symposium on Interactive 3D graphics table of contents, 1995 pp. 189-196

26. Van Den Bergen G.: A Fast and Robust GJK Implementation for collision detection of convex objects // Journal of Graphics Tools, 1999, 4(2) pp. 7-25

27. Van Den Bergen G.: Proximity queries and penetration depth computation on 3D game objects // Proc. Game Developers Conf., 2001

28. Van den Bergen G.: Collision Detection in Interactive 3D Environments // Morgan Kaufmann Series, USA, 2004

29. Ericson C.: Real-time collision detection // Morgan Kaufmann, 2005

30. Barzel R., Barr A.: A Modeling System Based on Dynamic Constraints // Computer Graphics 22(4), 1994 pp. 179-188

31. Cremer J., Stewart J.: The Architecture of Newton a General purpose Dynamics Simulator // International Conference on Robotics and Automation, IEEE, 1989-pp. 1806-1811

32. Mirtich B., Canny J.: Impulse-based Simulation of Rigid Bodies // Proceedings of 1995 Symposium on Interactive 3D Graphics, 1995 pp. 181-ff

33. Raibert M., Hodgins J.: Animation of dynamic legged locomotion // Computer Graphics, SIGGRAPH Conference Proceedings, 1991, pp. 349-358

34. McKenna M., Zeltzer D.: Dynamic simulation of autonomous legged locomotion// Computer Graphics, SIGGRAPH Conference Proceedings, 1991, pp. 29-38

35. Moore M., Wilhelms J.: Collision detection and response for computer animation // Computer Graphics Proceedings, 1988, pp. 289-298

36. Hahn J.: Realistic animation of rigid bodies // Computer Graphics Proceedings, 1988, pp. 299-308

37. Яблонский А.: Курс теоретической механики. Часть II. Динамика // Издательство Высшая Школа, Москва, 1966

38. Gengsheng W.: Three-Dimensional Collision Modeling for Rigid Bodies and its Coupling with Fluid Flow Computation // Flow Science Technical Note 75, 2006

39. Giang Т., Bradshaw G., O'Sullivan C.: Complementarity Based Multiple Point Collision Resolution // Proc. Fourth Irish Workshop Computer Graphics, 2003, pp. 1-8

40. Baraff D.: Analytical methods for dynamic simulation of non-penetrating rigid bodies // Computer Graphics Proceedings, 1989, pp. 223-232

41. Baraff D: Fast contact force computation for nonpenetrating rigid bodies // Computer Graphics Proceedings, 1994, pp. 23-34

42. Ермолин E., Казаков А.: Импульсный метод одновременного разрешения столкновений твердых тел // "Сибирский Журнал Вычислительной Математики", Том 9. Новосибирск, 2006. - С. 253-262

43. Ермолин Е., Казаков A.: Impulse-based Simultaneous Resolution of Rigid Body Collisions // isiCAD 2004. Proceedings of the International Forum. -Novosibirsk, 2004. pp. 214-223

44. Ermolin E., Kazakov A.: Impulse-based Approach for Rigid Body Collisions Simultaneous Resolution // Graphicon 2005. Conference Proceedings. -Novosibirsk, 2005. pp. 58-62

45. Ермолин E., Казаков А.: Подход к моделированию механических систем твердых тел // Препринт 10. ЗАО ЛЕДАС. Новосибирск, 2004. - 60 стр.

46. Blow J., Binstock A.: How to find the inertia tensor (or other mass properties) of a 3D solid body represented by a triangle mesh // Technical report, http://www.number-none.com, 2004

47. Keil J.: Polygon decomposition // Handbook of Computational Geometry, Elsevier Science Publishers B.V., North-Holland, 2000, pp. 491-518

48. Ермолин Е., Личман И., Казаков А., Лавров Р.: Построение гибридных полигональных сеток для задач САПР // Конференция-конкурс "Технологии Microsoft в теории и практике программирования". — Новосибирск, 2007.

49. Ермолин Е. Моделирование механических систем и связанные задачи // Семинар "3D графика и геометрия, высокопроизводительные вычисления" ИВМиМГ СО РАН, Intel-Novosibirsk. — Новосибирск, 2008.

50. Chazelle В.: Convex decompositions of polyhedra // Proc. 13th Annu. ACM Sympos. Theory Comput., 1981, pp. 70-79

51. Chazelle В.: Convex partitions of polyhedra: A lower bound and worst-case optimal algorithm // SIAM J. Comput., vol. 13, 1984, pp. 488-507

52. Bajaj C., Dey Т.: Convex decomposition of polyhedra and robustness // SIAM J. Comput., vol. 21, 1992, pp. 339-364

53. Lien J.: Approximate Convex Decomposition and Its Applications // Ph.D. Thesis, Department of Computer Science, Texas A&M University, 2006

54. Chazelle В., Dobkin D., Shouraboura N.: Strategies for polyhedral surface decomposition: An experimental study // Proc. 11th Annu. ACM Sympos. Comput. Geom., 1995, pp. 297-305

55. Chazelle В., Palios L.: Decomposing the boundary of a nonconvex polyhedron // Proc. 3rd Scand. Workshop Algorithm Theory, ser. Lecture Notes Comput. Sci., vol. 621. Springer-Verlag, 1992, pp. 364-375

56. Chazelle В.: A theorem on polygon cutting with applications // Proc. 23rd Annu. IEEE Sympos. Found. Comput. Sci., 1982, pp. 339-349

57. Greene D.: The decomposition of polygons into convex parts // Computational Geometry, ser. Adv. Comput. Res., F. P. Preparata, Ed. Greenwich, CT: JAI Press, vol. 1, 1983, pp. 235-259

58. Chazelle В., Dobkin P.: Optimal convex decompositions // Computational Geometry, G. T. Toussaint, Ed. Amsterdam, Netherlands: North-Holland, 1985, pp. 63-133

59. Tor S. and Middleditch A.: Convex decomposition of simple polygons // ACM ransactions on Graphics, vol. 3, N. 4, 1984, pp. 244-265

60. Siddiqi K., Kimia В.: Parts of visual form: Computational aspects // IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, N. 3, 1995, pp. 239-251

61. Dey Т., Giesen J., Goswami S.: Shape segmentation and matching with low discretization // Proc. Workshop on Algorithms and Data Structures, 2003, pp. 25-36

62. ODE, Open Dynamics Engine // www.ode.org

63. Newton Game Dynamics // http://newtondynamics.com

64. Millington I.: Game Physics Engine Development // Morgan Kaufmann Publishers, USA, 2007

65. Toussaint G.: Solving geometric problems with the rotating calipers // Proc. MELECON '83, Athens, 1983

66. Lloyd Т., Bau D.: Numerical Linear Algebra // SIAM, 1997

67. Широносов В.: Резонанс в физике, химии и биологии // ИД "Удмуртский университет", Ижевск, 2000/01й/