Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ты.
)На шаге удаления граней для проверки пересечений многогранников применен алгоритм, использующий дерево ограничивающих параллелепипедов [8]. Важно было хорошо оптимизировать этот шаг, поскольку проверку пересечений нужно выполнять для каждой грани, а на сложных входных данных образуется большое количество таких граней. Примененный на этом шаге алгоритм показал неплохие результаты.
За счет всех вышеперечисленных оптимизаций удалось достичь хорошей производительности алгоритма.
Среда для разработки и тестирования алгоритмов
В ходе работы над проектом была создана Среда для разработки и тестирования алгоритмов проверки пересечений. Эта среда позволяет выполнять следующие действия:
1)Загрузить из файлов многогранники, для которых будут проверяться столкновения.
2)Редактировать iену:
a.Поместить многогранники на iену (можно помещать несколько копий одного и того же многогранника).
b.Удалить многогранник со iены..Переместить многогранник.
3)Сохранить/загрузить iену.
4)Выбрать алгоритм для проверки пересечений.
)Запустить предрасчет; предрасчитанные данные будут записаны в файл.
)Проверить работу алгоритма: пользователь может перемещать многогранники, пересекающиеся объекты будут подкрашиваться другим цветом.
)Сравнить алгоритмы по времени работы и потребляемой памяти.
Рис. 10. Среда для разработки и тестирования алгоритмов
В Среде можно выделить три подсистемы, взаимодействующие друг с другом:
1)Система тестирования
2)Система плагинов
)Система визуализации
Среда разрабатывалась командой из трех человек, каждый из членов команды отвечал за одну из подсистем. В качестве языка программирования был выбран C++, для визуализации применяется графическая библиотека OpenGL, для создания графического пользовательского интерфейса используется библиотека FOX Toolkit. Моя задача заключалась в написании Системы плагинов.
Система плагинов
Одно из важных требований, предъявляемых к среде, - возможность легко расширять ее, добавляя новые алгоритмы обнаружения пересечений. Для этой цели была разработана Система плагинов.
Каждый плагин представляет собой динамическую библиотеку, содержащую реализацию одного алгоритма. Система плагинов загружает плагины и предоставляет пользователю возможность выбрать один из алгоритмов. Выбранный алгоритм будет использован для обнаружения пересечений.
Плагин
Все плагины являются реализацией одного общего интерфейса. Для того чтоб написать новый плагин, необходимо реализовать методы этого интерфейса, а именно:
void precompute (Polyhedron[] polyhedrons) - этот метод вызывается, когда приходит запрос выполнить предрассчет.
void debugDraw (RenderSystem renderer) - в этом методе определяется как должны быть визуализированы предрасчитанные данные. При разработке алгоритма очень важно наглядно представить обрабатываемую информацию, чтобы в случае некорректной работы алгоритма можно было заметить и исправить ошибку. Система визуализации предоставляет плагину все необходимые методы для отображения многогранников и других графических элементов.
bool checkCollision (Polyhedron poly1, Polyhedron poly2) - в этой функции реализуется проверка пересечений двух многогранников. Функция возвращает true, если объекты пересекаются, и false в противном случае. Для проверки могут быть использованы предрасчитанные данные.
void load (ifstream file)
void save (ofstream file) - сохранение и загрузка предрасчитанных данных. Процесс предрасчета для некоторых алгоритмов может занимать много времени, поэтому нужна возможность сохранить результат в файл и загрузить эти данные, когда они будут необходимы, вместо того, чтоб вычислять их заново. Формат, в котором хранить предрасчитанные данные, остается на усмотрение разработчика алгоритма.
После того, как все эти функции реализованы, плагин может быть встроен в среду.
Результаты
В ходе работы над проектом были получены следующие результаты:
1)Разработан и реализован алгоритм построения характеристического многогранника.
2)Алгоритм был внедрен в среду, и была показана корректность его работы на различных тестовых данных.
)Алгоритм был применен для проверки пересечений.
)Разработана и реализована Система плагинов.
)Результаты работы докладывались на XLIX Международной Научной Студенческой Конференции. Доклад был удостоен диплома III степени.
Рис. 12. Результат работы алгоритма
Перспективы
В перспективе возможно:
1)Доработать алгоритм построения характеристического многогранника с учетом случая вырожденных скольжений.
2)Использовать алгоритм для различных геометрических задач: поиска траектории движения по полигональной поверхности, задачи упаковки.
)Проанализировать возможность применения метода, основанного на характеристических многогранниках, для случая, когда многогранники могут вращаться.
Определения и обозначения
Определения
Многоугольник - геометрическая фигура, состоящая из 3 или более точек плоскости, не лежащих на одной прямой и попарно соединённых не пересекающимися отрезками.
Многогранник - замкнутая поверхность, составленная из многоугольников, а также тело ограниченное такой поверхностью. Многоугольники, из которых составлен многогранник, называются гранями, их стороны - ребрами, а их вершины - верш