Образования Российской Федерации томский государственный университет факультет информатики Кафедра теоретических основ информатики удк 681. 03

Федеральное Агентство Образования Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет информатики Кафедра теоретических основ информатики УДК 681.03 ДОПУСТИТЬ К ЗАЩИТЕ В ГАК Зав. Кафедрой, проф., д.т.н. __________________Ю.Л. Костюк «___» ____________2008 г. Магур Екатерина Владимировна ПОСТРОЕНИЕ СОВОКУПНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ Дипломная работа Научный руководитель, И.А. Кудрявцев Исполнитель, студ. гр. 1431 Е.В. Магур Электронная версия дипломной работы помещена В электронную библиотеку. Файл Администратор Томск – 2008 Реферат Дипломная работа 47 с., 23 рис., 17 источников, 6 приложений АЛГОРИТМ ПОСТРОЕНИЯ СОВОКУПНОЙ МОДЕЛИ ПЕРЕСЕЧЕНИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ, 3DS ФОРМАТ, DLL, ПЛАГИН ДЛЯ 3DS MAX Объект исследования - алгоритмы, обеспечивающие построение совокупного трехмерного объекта на основе пересечения двух других трехмерных объектов. Цель работы – построение такого алгоритма, разработка динамически подключаемой библиотеки, демонстрирующей работу алгоритма Методы исследования – стереометрические задачи пересечения плоскостей, алгоритмы триангуляции произвольных полигонов, работа с 3ds форматом, динамические библиотеки классов, расширения для 3D Studio Maх Разработан алгоритм построения совокупной модели двух пересекающихся объектов, разработан ряд вспомогательных алгоритмов: определение положения точки относительно объекта, триангуляция произвольного полигона и др. Разработана библиотека классов, которая содержит реализацию вышеперечисленных алгоритмов, а также импорт и экспорт в *.3ds – формат. Разработано расширение для 3D Studio Max. Содержание Введение ……………………………………………………………………..…………………4 Разработка математической библиотеки………………………………..………………...5 Определение способа задания объекта……………………………..……….............6 Специфика представления объекта в среде 3D Studio Max.……………….6 Геометрические объекты в трехмерном пространстве………………….…………8 Точка……………………………………………………………….………….8 Вектор…………………………………………………………………………8 Луч………………………………………………………………….………….8 Прямая…………………………………………………………………………9 Треугольник…………………………………………………………..............10 Полигон……………………………………………………………………….12 Алгоритм определения положения точки относительно полигона…………………………………………………………….13 Алгоритм триангуляции полигона………………………………...14 Трехмерный объект…………………………………………………………..16 Алгоритм определения положения точки относительно объекта.16 Алгоритм построения совокупной модели пересечения двух пространственных объектов……………………………………….18 Работа с файлами формата *.3ds…………………………………………………………..24 Функция импорта……………………………………………………………………..27 Функция экспорта…………………………………………………………………….28 Разработка динамически подключаемой библиотеки классов (DLL)…………………..30 Функция экспорта в *.dll-файл………………………………………………………31 Функция импорта из *.dll-файла…………………………………………………….32 Разработка плагина для 3D Studio Max 8.0……………………………………………….33 Заключение……………………………………………………………………….……………..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. Косинус угла между векторами. Его легко найти из формулы для скалярного произведения Нормализация вектора. Нормализованный вектор – это вектор, имеющий единичную длину. Для нормализации вектора нужно разделить его на текущую его длину. Также использованы такие функции, как: деление на скаляр, вычитание векторов, векторы сонаправлены или нет (угол между ними не более 90 градусов, но и не равен 90 градусам), векторы перпендикулярны или нет, вычисление длины вектора и др. Луч Задается точкой, определяющей начало луча, и вектора, определяющего его направление. Никаких специфичных функций данный класс не содержит, единственной причиной, почему этот объект трехмерного мира выделен в отдельный класс – это то, что алгоритм получения положения точки относительно объекта использует в качестве вспомогательного элемента именно этот класс. Прямая Этот класс для данной задачи играет более значительную роль. Задавать линию в трехмерном пространстве можно разными способами. В данной работе реализованы два способа: с помощью двух точек, принадлежащих данной прямой и с помощью одной точки и вектора направления. Наиболее важными являются функции поиска точки пересечения двух прямых и поиск расстояния от точки до линии. Остановимся на каждой подробнее. Алгоритм поиска точки пересечения двух прямых: Изначально нужно проверить пересекаются ли прямые вообще, т.е. имеет ли смысл искать точку пересечения. Для этого сначала нужно проверить лежат ли они в одной плоскости, ведь, если прямые пересекаются, то они однозначно лежат в одной плоскости. Затем, если лежат, с помощью их векторов направления можно проверить их на параллельность. Если прямые не параллельны и лежат в одной плоскости, то, очевидно, они где-то пересекутся. В таком случае можно приступать к поиску точки пересечения. Прямая в трехмерном пространстве задается уравнением: Далее, при вычислениях если какой-нибудь из знаменателей данного уравнения окажется равным 0, то это будет означать, что по соответствующей координате стоящей в соответствующем числителе, линия является константой. Т.о., возможно, сразу удастся найти некоторые из неизвестных переменных-координат искомой точки. Составляя такое же уравнение и для другой прямой, ищутся все неизвестные координаты. Расстояние от точки до линии вычисляется по формуле [3]: , где - какая-либо точка прямой , а - направляющий вектор прямой (см. Рисунок 2). Также этот класс содержит несколько других немаловажных для всей задачи в целом функций, которые будут описаны позже по ходу изложения основных этапов конечного алгоритма. Рисунок 2. Расчет расстояния от точки до линии Треугольник Треугольник задается тремя точками-вершинами и вектором нормали к его поверхности, определяющем лицевую и изнаночную сторону данного треугольника. Рассмотрим некоторые функции, выполняемые над треугольниками: Определение центра треугольника. Как известно, центр треугольника – точка пересечения его медиан. Медиана, в свою очередь – это отрезок с началом в одной из вершин треугольника и концом в середине противоположной стороны треугольника. Таким образом, все что надо сделать – составить две линии-медианы и найти их точку пересечения с помощью соответствующей функции. Определение того, лежит ли линия в плоскости треугольника. Плоскость в трехмерном пространстве задается уравнением: Все коэффициенты этого уравнения известны. Подставив в него две точки заданной линии, определим принадлежность линии плоскости треугольника. Вычисление площади треугольника. Треугольник задан, следовательно, длины всех его сторон известны. Его площадь можно найти по формуле Герона: Определение того, находится ли точка внутри треугольника. Для начала можно определить принадлежит ли точка вообще плоскости треугольника. В большинстве случаев в данной задаче точка не будет принадлежать плоскости треугольника, поэтому, желательно такую проверку провести, хотя, следующий алгоритм все равно позволяет это определить. Т.о. точка «попадает» в треугольник, если , где – площадь соответствующего треугольника, – величина, близкая к нулю (для учета погрешности вычислений), если не учитывать, то точка принадлежит треугольнику, если: Рисунок 2 наглядно показывает случай, когда точка лежит внутри треугольника и случай, когда точка лежит снаружи треугольника. Рисунок 3. Слева: точка находится снаружи треугольника; справа – внутри треугольника Определение точки пересечения прямой и треугольника. Сначала удобно сделать проверку на параллельность прямой и плоскости треугольника. Далее, если не параллельны, найти точку пересечения прямой с плоскостью треугольника, а затем определить принадлежит ли данная точка области на этой плоскости, ограниченной тремя сторонами треугольника. Проверка на параллельность выполняется с помощью вектора нормали у треугольника и вектора направления у соответствующей прямой. Но здесь возможен вариант, в случае параллельности, что прямая лежит в плоскости треугольника. В этом случае достаточно определить точки пересечения прямой с ребрами треугольника. Если прямая и плоскость не параллельны, то, очевидно, они где-то пересекаются и можно приступать к поиску соответствующей точки. Сделать это можно, используя уравнение плоскости в трехмерном пространстве: , и уравнение прямой в пространстве, заданное в параметрическом виде [5]: , где – единичный вектор направления прямой, его можно вычислить следующим образом: , здесь и – две точки на прямой, – параметр, пробегающий значения от 0 до 1 и дающий все промежуточные точки на отрезке прямой . Разложив точку по трем координатам и подставив в уравнение для плоскости, можем найти параметр t в уравнении прямой. Далее, подставив найденное значение в уравнение прямой, найдем точку . Фактически, так и реализуется функция поиска точки пересечения двух прямых. Сразу хочется заметить, что при определении точки пересечения прямой с треугольником, может получиться одна, две и три точки пересечения. Одна – в случае, когда прямая не лежит в плоскости треугольника и пересекает его в это точке; две – когда прямая лежит в плоскости треугольника и пересекает два его ребра; три – прямая лежит в плоскости треугольника и пересекает три его ребра (см. Рисунок 4). А) три пересечения Б) два пересечения Рисунок 4. Точки пересечения ребер треугольника и прямой Другие функции для данного класса будут рассмотрены ниже при построении конечных алгоритмов.

Похожие:

	Министерство образования и науки российской федерации томский государственный... Целью дисциплины является ознакомление студентов с базовыми понятиями следующих разделов информатики: теория информации, технические...		Красноярский государственный педагогический университет факультет информатики Задание: Разработать требования к оборудованию и оснащению кабинета информатики с заданным количеством персональных эвт в учебном...
	Минобрнауки томский государственный университет факультет информатики утверждаю Задача учебного курса – освоение психолого-педагогических знаний, вопросов методики преподавания, современных методов обучения		Молдавский Государственный Университет Факультет Математики и Информатики.... За последние 9 лет (c 1993) в мире персональных компьютеров появился новый участник – персональный карманный компьютер (кпк). Большую...
	Программа по формированию навыков безопасного поведения на дорогах... Московский Государственный Университет Приборостроения и Информатики, Факультет "Технологическая информатика", кафедра "Компьютерный...		Министерство образования и науки РФ новосибирский государственный... Когда появляется изображение цепи ордена Андрея Первоз­ванного на российском гербе
	Министерство образования и науки российской федерации томский государственный... Государственное общеобразовательное учреждение-средняя общеобразовательная школа		Государственное образовательное учреждение высшего профессионального... Аннотация умкд…
	Государственное образовательное учреждение высшего профессионального... Аннотация умкд…		Государственное образовательное учреждение высшего профессионального... Аннотация умкд…
	Российской Федерации Федеральное государственное бюджетное образовательное... «Московский государственный университет экономики, статистики и информатики (мэси)»		Российской Федерации Федеральное государственное бюджетное образовательное... «Московский государственный университет экономики, статистики и информатики (мэси)»
	Министерство сельского хозяйства российской федерации Е образовательноЕ учреждениЕ высшего профессионального образования «Московский государственный университет экономики, статистики...		Российской Федерации Карельский государственный педагогический университет... В 1962 году на факультете физической культуры была создана первая специальная кафедра теоретических основ физического воспитания....
	Методические рекомендации по подготовке и выполнению вкр министерство... Фгбоу впо «Московский Государственный Университет экономики, статистики и информатики (мэси)»		О. В. Артюшкин Хакасский государственный университет им. Н. Ф. Катанова... При рассмотрении информатики с позиций гуманитарной, технической, естественной и фундаментальных наук даются ее определения. В заключительной...