Категория
Информатика
Тип
дипломная работа
Страницы
30 стр.
Дата
12.04.2013
Формат файла
.html — Html-документ
Архив
378491.zip — 14.48 kb
  • zadacha-vzaimnogo-razmeshhenija-mnogogrannikov-postroenie-xarakteristicheskogo-mnogogranni_378491_1.html — 84.55 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Задача взаимного размещения многогранников. Построение характеристического многогранника. Система плагинов


Введение


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

- проверку пересечения многогранников, каким-либо образом размещенных в пространстве,

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

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

- вычисление расстояния между двумя многогранниками,

- поиск траектории движения подвижного многогранника от одной точки к другой, такой чтоб он не пересекался с неподвижным многогранником

и другие.

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

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

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





Ваше мнение



CAPTCHA