Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики удк 681. 03
|
Скачать 483.13 Kb.
|
|
Федеральное Агентство Образования Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет информатики Кафедра теоретических основ информатики УДК 681.03 ДОПУСТИТЬ К ЗАЩИТЕ В ГАК Зав. Кафедрой, проф., д.т.н. __________________Ю.Л. Костюк «___» ____________2008 г. Магур Екатерина Владимировна ПОСТРОЕНИЕ СОВОКУПНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ Дипломная работа Научный руководитель, И.А. Кудрявцев Исполнитель, студ. гр. 1431 Е.В. Магур Электронная версия дипломной работы помещена В электронную библиотеку. Файл Администратор Томск – 2008 Реферат Дипломная работа 47 с., 23 рис., 17 источников, 6 приложений АЛГОРИТМ ПОСТРОЕНИЯ СОВОКУПНОЙ МОДЕЛИ ПЕРЕСЕЧЕНИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ, 3DS ФОРМАТ, DLL, ПЛАГИН ДЛЯ 3DS MAX Объект исследования - алгоритмы, обеспечивающие построение совокупного трехмерного объекта на основе пересечения двух других трехмерных объектов. Цель работы – построение такого алгоритма, разработка динамически подключаемой библиотеки, демонстрирующей работу алгоритма Методы исследования – стереометрические задачи пересечения плоскостей, алгоритмы триангуляции произвольных полигонов, работа с 3ds форматом, динамические библиотеки классов, расширения для 3D Studio Maх Разработан алгоритм построения совокупной модели двух пересекающихся объектов, разработан ряд вспомогательных алгоритмов: определение положения точки относительно объекта, триангуляция произвольного полигона и др. Разработана библиотека классов, которая содержит реализацию вышеперечисленных алгоритмов, а также импорт и экспорт в *.3ds – формат. Разработано расширение для 3D Studio Max. Содержание Введение ……………………………………………………………………..…………………4
Заключение……………………………………………………………………….……………..38 Приложение А. Руководство пользователя 3D Studio Max…………………….……………40 Приложение Б. Руководство прикладного программиста…………………………………..42 Приложение В. Руководство разработчика………………………………………………….43 Приложение Г. Пример файла в формате 3ds в двоичном виде…………………………….45 Приложение Д. Прототипы функций экспорта данных в dll и работа с интерфейсами…...46 Приложение Е. Пример импорта функций из dll внешним приложением………………….47 Введение Построение совокупной модели двух пересекающихся объектов – это, в сущности, построение отсечения некоторых полигонов модели. Данная проблема довольно актуальна, например, при создании трехмерных игр: отсечение частей объекта, вышедших за область камеры с целью понижения трудоемкости отображения трехмерной модели. Также эта проблема актуальна в различных программах моделирования трехмерных объектов. Для алгоритма построения совокупной модели использован вспомогательный алгоритм определения положения точки в трехмерном пространстве. Данный алгоритм может применяться в тех же трехмерных играх, например, для обнаружения попадания снаряда в цель. Целью данной работы является разработка динамической библиотеки классов, позволяющих построить совокупную модель двух пересекающихся объектов, а также взаимодействие библиотеки со средой 3D Studio Max В ходе данного проекта реализована динамическая библиотека классов, которая позволяет работать с трехмерными объектами посредством функций импорта, экспорта в *.3ds-файл, и функции построения результирующего объекта на основе двух других пересекающихся трехмерных объектов. Также разработано расширение для среды 3D Studio Max. Проект реализован в среде Visual C++, в ходе работы тестирование проводилось с использованием библиотеки OpenGL
Постановка задачи Пусть заданы два объекта в трехмерном пространстве, причем, их поверхности пересекаются. Необходимо построить на основе их пересечения третий объект, соответствующий области, ограниченной двумя исходными объектами (операция объединения). Ограничения на объекты:
1.1. Определение способа задания объекта Существует множество вариантов представления трехмерного объекта. Во-первых, множество вариантов, дающих приближенное представление о поверхности, ограничивающей объект. Это воксельное представление [1] (объект состоит из множества отдельных кубов (вокселей), которые в совокупности дают контуры этого объекта), представление с помощью ограничивающей поверхности [1], представление с помощью пространственной геометрии [1] (объект состоит из набора элементарных трехмерных фигур). Достаточно точным является вариант явного представления [1]. В этом случае объект состоит из набора граней, каждая из которых является полигоном. Недостатком такого представления является то, что полигоны представляются набором вершин, следовательно, вершины будут повторяться, так как трехмерный объект – это замкнутая фигура в пространстве. Для решения такой проблемы можно использовать список вершин [3], а далее, при описании полигонов просто ссылаться на индексы нужных вершин. Существуют и более экономные варианты, основанные уже не на переборе граней объекта, а на построении обхода всего объекта по граням. Таким вариантом является, например, «крылатое» представление [1]. Данная работа нацелена на взаимодействие со средой 3D Studio Max, основным форматом файлов в которой является *.3ds - формат. Кроме того, файлы *.3ds поддерживаются многими приложениями, что позволит в них использовать библиотеку классов, реализованную в данной работе. 2.1.1. Специфика представления объекта в среде 3D Studio Max Для правильной визуализации трехмерного объекта необходимо учитывать лицевую и изнаночную сторону каждого его полигона. Для этого используется нормаль к плоскости треугольника. Чтобы избежать хранение дополнительной информации в структуре объекта, принято соглашение: все вершины треугольника полигона (в данной работе это только треугольники) должны обходиться строго по часовой стрелке. Таким образом, всегда можно узнать направление нормали для конкретного треугольника. Это легко реализовать с помощью векторного произведения.  Рисунок 1. Вершины обходятся по часовой стрелке, нормаль направлена вверх Таким образом (см. Рисунок 1), составив вектора ВА и ВС и посчитав их векторное произведение, найдем вектор N. Нужно заметить, что подобным образом можно рассчитывать вектора нормали только для треугольников (которые, по сути, являются выпуклыми полигонами), но нельзя для невыпуклых полигонов, т.к. вектора направления двух смежных ребер и вектор нормали необязательно будут образовывать правую тройку [3]. Зная вектор нормали нетрудно реализовать и обратную операцию: расположение вершин треугольника по часовой стрелке. Для удобства взаимодействия со средой 3D Studio Max в данной работе используется явное представление объекта, причем, все полигоны являются только треугольниками и вершины в них расположены по часовой стрелке.
Точка – простейший объект трехмерного мира. Задается значениями трех координат. На ее основе построены все остальные классы. Единственная функция, реализованная для данного класса: вычисление расстояние между двумя точками, которое вычисляется по формуле: 
Вектор задается одной точкой, исходя из того, что начало вектора приходится на начало координат, а его направление задает именно эта точка. Для данной задачи реализованы такие операции по работе с трехмерными векторами, как:
 ,где  и  - длины соответствующих векторов
 Отсюда легко найти вектор единичный нормальный вектор  , т.е. вектор, перпендикулярный векторам  и  , и имеющий длину 1.
Задается точкой, определяющей начало луча, и вектора, определяющего его направление. Никаких специфичных функций данный класс не содержит, единственной причиной, почему этот объект трехмерного мира выделен в отдельный класс – это то, что алгоритм получения положения точки относительно объекта использует в качестве вспомогательного элемента именно этот класс.
Этот класс для данной задачи играет более значительную роль. Задавать линию в трехмерном пространстве можно разными способами. В данной работе реализованы два способа: с помощью двух точек, принадлежащих данной прямой и с помощью одной точки и вектора направления. Наиболее важными являются функции поиска точки пересечения двух прямых и поиск расстояния от точки до линии. Остановимся на каждой подробнее. Алгоритм поиска точки пересечения двух прямых: Изначально нужно проверить пересекаются ли прямые вообще, т.е. имеет ли смысл искать точку пересечения. Для этого сначала нужно проверить лежат ли они в одной плоскости, ведь, если прямые пересекаются, то они однозначно лежат в одной плоскости. Затем, если лежат, с помощью их векторов направления можно проверить их на параллельность. Если прямые не параллельны и лежат в одной плоскости, то, очевидно, они где-то пересекутся. В таком случае можно приступать к поиску точки пересечения. Прямая в трехмерном пространстве задается уравнением:   Далее, при вычислениях если какой-нибудь из знаменателей данного уравнения окажется равным 0, то это будет означать, что по соответствующей координате стоящей в соответствующем числителе, линия является константой. Т.о., возможно, сразу удастся найти некоторые из неизвестных переменных-координат искомой точки. Составляя такое же уравнение и для другой прямой, ищутся все неизвестные координаты. Расстояние от точки до линии вычисляется по формуле [3]:  ,где  - какая-либо точка прямой  , а  - направляющий вектор прямой (см. Рисунок 2).Также этот класс содержит несколько других немаловажных для всей задачи в целом функций, которые будут описаны позже по ходу изложения основных этапов конечного алгоритма.  Рисунок 2. Расчет расстояния от точки до линии
Треугольник задается тремя точками-вершинами и вектором нормали к его поверхности, определяющем лицевую и изнаночную сторону данного треугольника. Рассмотрим некоторые функции, выполняемые над треугольниками:
 Все коэффициенты этого уравнения известны. Подставив в него две точки заданной линии, определим принадлежность линии плоскости треугольника.
 ,где  – площадь соответствующего треугольника,  – величина, близкая к нулю (для учета погрешности вычислений), если не учитывать, то точка принадлежит треугольнику, если: Рисунок 2 наглядно показывает случай, когда точка лежит внутри треугольника и случай, когда точка лежит снаружи треугольника.   Рисунок 3. Слева: точка находится снаружи треугольника; справа – внутри треугольника
,и уравнение прямой в пространстве, заданное в параметрическом виде [5]:  ,где – единичный вектор направления прямой, его можно вычислить следующим образом: ,здесь  и  – две точки на прямой,  – параметр, пробегающий значения от 0 до 1 и дающий все промежуточные точки на отрезке прямой  . Разложив точку  по трем координатам  и подставив в уравнение для плоскости, можем найти параметр t в уравнении прямой. Далее, подставив найденное значение в уравнение прямой, найдем точку . Фактически, так и реализуется функция поиска точки пересечения двух прямых.Сразу хочется заметить, что при определении точки пересечения прямой с треугольником, может получиться одна, две и три точки пересечения. Одна – в случае, когда прямая не лежит в плоскости треугольника и пересекает его в это точке; две – когда прямая лежит в плоскости треугольника и пересекает два его ребра; три – прямая лежит в плоскости треугольника и пересекает три его ребра (см. Рисунок 4).   А) три пересечения Б) два пересечения Рисунок 4. Точки пересечения ребер треугольника и прямой Другие функции для данного класса будут рассмотрены ниже при построении конечных алгоритмов. |
Похожие:
 |
Гбоуво рк «крымский инженерно-педагогический университет» Факультет... Программные средства разработки flash-приложения «анимация для школьников» 22 |
|
Минобрнауки томский государственный университет факультет информатики утверждаю Цель курса – изучение методов объектно-ориентированного анализа и проектирования |
|
Правительство Российской Федерации Федеральное государственное автономное... Факультет Бизнес-Информатики Кафедра инноваций и бизнеса в сфере информационных технологий |
|
Правительство Российской Федерации Федеральное государственное автономное... Факультет бизнес-информатики Кафедра инноваций и бизнеса в сфере информационных технологий |
|
«Поволжский государственный университет телекоммуникаций и информатики» Факультет Федеральное государственное бюджетное образовательное учреждение высшего образования |
|
Уральский Государственный Университет Факультет коммерции Кафедра «Экономика торговли» Целью данной работы является рассмотрение теоретических основ технологии бесперегрузочных сообщений, а также изучение основных требований... |
|
Факультет бизнес-информатики Кафедра информационных технологий в... Постановка задачи, выбор методов реализации и описание технического задания. 14 |
 |
Национальный исследовательский университет "Высшая школа экономики"... Разработка предметно-ориентированного языка описания структуры и содержания электронных документов |
|
Пермский филиал Факультет бизнес-информатики Кафедра информационных... Данные гис – данные, полученные в результате геофизического исследования скважин. Синоним к термину «Каротажные данные» |
|
Паспорт кабинета информатики Использовать кабинет информатики с целью освоения средств икт на уроках информатики и в свободное от уроков время |
|
Методические рекомендации по управления рисками проекта создания... Московский государственный университет приборостроения и информатики, экономический факультет. Москва, Российская федерация |
|
Министерство образования и науки Российской Федерации Нижегородский... Мероприятие 2 Совершенствование образовательных технологий, укрепление материально-технической базы учебного процесса |
|
«компетентностный подход на уроках информатики» предназначена для... Щерба Валентина Юрьевна, учитель информатики, мкоу «Средняя ощеобразовательная школа №5, г. Киренска» |
|
Отчет о результатах самообследования красноярского филиала государственного... Красноярский филиал государственного образовательного учреждения высшего профессионального образования «московский государственный... |
|
Конкурсе видеоуроков учителей и преподавателей математики и информатики Ехнологий боу дпо (ПК) с «Чувашский республиканский институт образования» Минобразования Чувашии в рамках XXVI республиканского методического... |
|
В кабинете вычислительной техники для заведующего кабинетом и учителей информатики Заведующий кабинетом информатики, учителя информатики принимают необходимые меры для создания здоровых и безопасных условий проведения... |