Введение к работе
Актуальность работы. Развитие ЭВМ и растущая доступность персональных компьютеров, игровых приставок и прочих мультимедийных устройств повлекло рост потребности в интерактивных приложениях, моделирующих виртуальную среду и позволяющих получить нужную информацию или ожидаемое поведение от некоторого виртуального объекта, обычно являющегося моделью реального объекта. Примерами могут послужить расчеты прочностных характеристик деталей, осуществляемые инженером в современной САПР; нахождение массы тела; моделирование движения автомобиля в игровом симуляторе. В настоящей работе рассмотрена задача математического моделирования движения системы твердых недеформируемых тел, актуальная для нескольких прикладных областей: цифровое прототипирование как часть процесса разработки изделия с помощью САПР; виртуальных средах, позволяющих получить опыт взаимодействия в реальной среде (космические экспедиции и т.п.); игровых приложениях. Важнейшими требованиями пользователей данных приложений являются достоверность математической модели, соответствие результатов виртуальных испытаний результатам физических опытов; и быстродействие - обычно ожидается, что расчет должен происходить в интерактивном режиме.
Методы определения столкновений и расчета реакции тел на столкновение являются алгоритмической основой решения данной задачи. Анализ опубликованных подходов по решению задачи определения столкновений показывает, что наиболее эффективными с точки зрения производительности и качества результата являются методы, работающие на выпуклой полигональной геометрии, что делает актуальной задачу приближенной выпуклой декомпозиции, строящую покрытие исходной геометрии набором выпуклых тел. Задача приближенной выпуклой декомпозиции рассмотрена для плоского случая, было показано, что существующие подходы строят избыточное покрытие, тяготеющее к триангуляции, поэтому их необходимо улучшать. Существующие методики по расчету реакции твердых недеформируемых тел на удар используют модель мгновенного обмена импульсами между телами и имеют ограниченную область применимости - предлагаемые решения либо обрабатывают соударения поочередно, что дает нереалистичный результат, либо, оперируя неравенствами для задания условий непроникновения тел, не удовлетворяют закону сохранения кинетической энергии системы при абсолютно упругом ударе. Таким образом, актуальной задачей расчета реакции тел на удар является разработка метода, обрабатывающего удары комплексно при соблюдении законов сохранения импульса, момента импульса и энергии. Расчет реакции тел на удар, препятствующей проникновению тел друг в друга, и соответствующее изменение положений и скоростей тел обычно называют разрешением столкновений (collision resolution).
Реализации методов определения и разрешения столкновений обычно существуют в виде отдельных программных компонент, называемых модулями. Помимо этого в реализациях обычно существует еще третий модуль, динамический, согласовывающий работу вышеупомянутых. Также он отвечает за пересчет
положений тел, скоростей под действием внешних сил (например, силы тяжести) и осуществляет взаимодействие с конечнопользовательским приложением.
Таким образом, актуальной проблемой является развитие методов разрешения столкновений, гарантирующих реалистичное поведение объектов, и согласованных с этими методами алгоритмов определения столкновений.
Цель диссертационной работы: разработка эффективных и физически достоверных алгоритмов математического моделирования движения системы твердых не деформируемых тел и их программная реализация.
Для достижения указанной цели были сформулированы и решены следующие задачи:
разработка на основе импульсного подхода физически достоверного метода разрешения столкновений для системы трехмерных тел без ограничений на представление геометрии, число тел и число точек столкновения;
разработанный метод был развит для поддержки геометрических ограничений типа "кинематическая пара";
разработка эффективного и качественного метода приближенной декомпозиции невыпуклых двумерных тел на множество выпуклых тел;
реализация разработанных алгоритмов;
реализация метода определения столкновений, нахождения точек контакта, оптимального направления разрешения для пары выпуклых двумерных тел;
разработка и реализация динамического модуля;
проведение вычислительных экспериментов;
создание программного средства Noir для визуализации результатов моделирования.
Область исследования. Содержание диссертации соответствует специальности 05.13.18 "Математическое моделирование, численные методы и комплексы программ", области исследования п. 1 "Разработка новых математических методов моделирования объектов и явлений", п. 3 "Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий" и п. 8 "Разработка систем компьютерного и имитационного моделирования" Паспорта специальности.
Научная новизна работы заключается в следующем:
предложен метод приближенной выпуклой декомпозиции двумерного многоугольника с внутренними границами;
предложено усовершенствование метода разрешения столкновений, отвечающее законам механики твердых тел;
предложено расширение метода, позволяющее учитывать геометрические ограничения между телами.
Научная ценность диссертационной работы заключается в разработке и создании эффективных реализаций алгоритмов декомпозиции многограничного
многоугольника, определения и разрешения столкновений; разработке динамического модуля, пригодного для использования в интерактивных приложениях виртуальной реальности. Основные свойства разработанных алгоритмов сформулированы и доказаны в виде теорем.
Достоверность полученных результатов подтверждается:
численными экспериментами на модельных тестах, имеющих аналитические решения;
сравнением с результатами работы алгоритмов, решающих аналогичные задачи, но неэффективных с вычислительной точки зрения;
физическим экспериментом, заключающемся в измерении времени удара последней кости домино в цепочке и визуализации движения. Время, полученное с помощью расчетов, отличается в среднем на 20% от измеренного в реальном эксперименте, качественная картина движения костей воспроизведена достоверно.
Апробация работы. Основные научные результаты докладывались автором на международных конференциях isiCAD 2004 (Новосибирск, Россия, 2004), GraphiCon (Новосибирск, Россия, 2005), на конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, Россия, 2007), на семинаре "3D графика и геометрия, высокопроизводительные вычисления" (Новосибирск, Россия, 2008), на выпускном семинаре ИСИ СО РАН (Новосибирск, Россия, 2010) под руководством д.ф.-м.н., профессора Марчука А.Г..
Личный вклад соискателя. Все выносимые на защиту результаты принадлежат лично автору. Представление результатов совместных исследований в диссертационной работе согласовано с соавторами. Личный вклад соискателя заключается в обсуждении постановок задач; разработке адекватных численных алгоритмов и методов решения; разработке, реализации и тестировании программ, проведении численных экспериментов и интерпретации результатов.
Структура и объем работы Диссертационная работа состоит из введения, шести глав, заключения и списка литературы. Общий объем работы - 155 страниц. Список литературы содержит 67 наименований. Работа включает 14 таблиц, 89 рисунков и графиков.
