Методы определения и разрешения столкновений на полигональных моделях

• Автор: Ермолин, Егор Николаевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Новосибирск
• Количество страниц: 155 с. : ил.

СОДЕРЖАНИЕ

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

Введение

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

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

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

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

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

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

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

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

Обзор сопутствующих задач расчет динамических свойств сетки, приближенная
выпуклая декомпозиция
Глава 2 Динамический модуль
Глава 3 Определение столкновений.
Алгоритм определения столкновений пары выпуклых тел
Алгоритм ЕРА определения минимальной глубины проникновения и направления
разрешения столкновений
Нахождение дополнительных точек контакта.
Производительность алгоритма определения столкновений
Оптимизация определения столкновений. Окружающие примитивы.
Глава 4 Разрешение столкновений
Поддержка ограничений кинематическая пара
Учет силы трения.
Выбор метода определения столкновений
Оптимизация метода разрешения столкновений.
Глава 5 Приближенная выпуклая декомпозиция.
Деление многограничного i
Деление двухграничного контура
Упрощение однограничного контура
Примеры работы приближенной выпуклой декомпозиции.
Заключение
Глава 6 Комплекс программ для моделирования динамических систем твердых тел
Программа i
Физический эксперимент
Моделирование маятника Капицы.
Моделирование движения системы сложных многосвязных тел.
Заключение
Список литературы


В основе алгоритмов лежат атомарные топологические операции: вставка новой вершины в контур; деление ребром 1-контура; вырезание I-контура из л-контура по двум ребрам. До и после операций контур остается многообразным, атомарность означает, что все промежуточные действия по перестроению контура, во время которых нарушается его топологическая целостность, неподконтрольны извне. Метод подбора делящих отрезков является эвристическим и учитывает следующие факторы: локальную невыпуклость контура; углы, обрадованные ребром деления с границей контура; периметр контуров, полученных в результате деления. Алгоритмы SpIitMulti и SplitDuo не упрощают исходную геометрию, контроль качества декомпозиции лежит полностью на Simplify. Временная сложность алгоритма SpIitMulti определяется как 0(||{C}||«log/i) + O(||{C}||2 п). Квадрат || {С} || относится к худшему случаю, и на практике время работы в среднем можно оценить как 0(||{С} J| wlog/i). Временная сложность алгоритма SpIitMulti - 0(л log п), где п - число вершин контура {С}, достигается при нахождении выпуклой оболочки внутренней границы контура. Временная сложность алгоритма Simplify в худшем случае оценена как 0(«log«), и соответствует контуру с зигзагообразной границей и требованию разбиения до появления только выпуклых контуров. В тестой главе, Комплекс программ для моделирования динамических систем твердых тел, представлены подробности реализации описанных выше алгоритмов. Для визуального тестирования и создания иллюстраций и демонстрационных роликов было реализовано Win-приложение Noir, выступающее в роли пользовательского приложения и использующее описанные выше модули. OpenGL. Задание сцен выполняется с помощью текстовых файлов, разбитых на секции (опции, геометрия, трансформации, скорости, ограничения и т. Приведены результаты тестовых расчетов. В частности, для проверки достоверности был проведен физический эксперимент. На поверхности гладкого стола установлено костей домино рубашкой в одну сторону. Перед выстроенной цепочкой под углом положена книга. С верхнего края книги отпускается кость домино и сбивает цепочку, замеряется время между ударом первой и последней в цепочке, двадцать седьмой, кости домино. Во входном файле программы Noir была описана сцена, отвечающая начальным условиям данного эксперимента; с различными коэффициентами восстановления были воссозданы все конфигурации с различными расстояниями между костями. Измерялось время между началом движения первой и последней в цепочке костей домино. Отличие результатов моделирования от экспериментальных варьируется от % до %, продемонстрировано явное качественное совпадение результатов, которое дает модель, с результатами физического эксперимента (разброс костей, отрыв последней кости от “стопки” и т. В Заключении перечислены основные результаты диссертационной работы. Задача по моделированию движения системы твердых недеформируемых тел может быть сформулирована следующим образом. В трехмерном евклидовом пространстве определена система координат, в дальнейшем называемая мировой, и задана система твердых тел, геометрия которых задана в граничном представлении С? Геометрия каждого тела определена в связанной с телом локальной системой координат, положение которой определено трансформацией Г=<Я,«>, где г -вектор переноса локальной системы координат, о- ось поворота. С<р = СО$<р, 5<Р=П(? Кинематика системы тел, движущихся без столкновений, может быть описана с помощью задания моментальных поступательной V и угловой со скоростей каждого тела; и соответствующих ускорений а и ё . СІ? Формула, связывающая угловую скорость и вектор о, справедлива для случая, когда вектора о и со коллииеарны. В общем случае связь ориентации тела д и угловой скорости со устанавливается более сложным образом, позволяя говорить, что вектор сдсії при бесконечном малом сії у отвечает моментальному повороту тела. При этом композиция текущей ориентации о и “поворота” сосії не может быть выражена суммой векторов. В дальнейшем будет показано, как эта проблема обходится при составлении разностной схемы ().