Построение совокупных пространственных объектов

Федеральное Агентство Образования Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет информатики

Кафедра теоретических основ информатики

УДК 681.03

ДОПУСТИТЬ К ЗАЩИТЕ В ГАК

Зав. Кафедрой, проф., д.т.н.

__________________Ю.Л. Костюк

«___» ____________2008 г.

Магур Екатерина Владимировна

ПОСТРОЕНИЕ СОВОКУПНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ

Дипломная работа

Научный руководитель,                                                                    И.А. Кудрявцев

Исполнитель,                                       

студ. гр. 1431                                                                                                                       Е.В. Магур

Электронная версия дипломной работы помещена

В электронную библиотеку. Файл

Администратор

Томск – 2008

Реферат

Дипломная работа 47 с., 23 рис., 17 источников, 6 приложений

АЛГОРИТМ ПОСТРОЕНИЯ СОВОКУПНОЙ МОДЕЛИ ПЕРЕСЕЧЕНИЯ ТРЕХМЕРНЫХ ОБЪЕКТОВ, 3DS ФОРМАТ, DLL, ПЛАГИН ДЛЯ 3DS MAX

Объект исследования - алгоритмы, обеспечивающие построение совокупного трехмерного объекта на основе пересечения двух других трехмерных объектов.

Цель работы – построение такого алгоритма, разработка динамически подключаемой библиотеки, демонстрирующей работу алгоритма

Методы исследования – стереометрические задачи пересечения плоскостей, алгоритмы триангуляции произвольных полигонов, работа с 3ds форматом, динамические библиотеки классов, расширения для 3D Studio Maх

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

Разработана библиотека классов, которая содержит реализацию вышеперечисленных алгоритмов, а также импорт и экспорт в *.3ds – формат. Разработано расширение для 3D Studio Max.

Содержание

Введение ……………………………………………………………………..…………………4

1.       Разработка математической библиотеки………………………………..………………...5

1.1.       Определение способа задания объекта……………………………..……….............6

1.1.1.       Специфика представления объекта в среде 3D Studio Max.……………….6

1.2.       Геометрические объекты в трехмерном пространстве………………….…………8

1.2.1.       Точка……………………………………………………………….………….8

1.2.2.       Вектор…………………………………………………………………………8

1.2.3.       Луч………………………………………………………………….………….8

1.2.4.       Прямая…………………………………………………………………………9

1.2.5.       Треугольник…………………………………………………………..............10

1.2.6.       Полигон……………………………………………………………………….12

1.2.6.1.        Алгоритм определения положения точки относительно полигона…………………………………………………………….13

1.2.6.2.        Алгоритм триангуляции полигона………………………………...14

1.2.7.       Трехмерный объект…………………………………………………………..16

1.2.7.1.        Алгоритм определения положения точки относительно объекта.16

1.2.7.2.        Алгоритм построения совокупной модели пересечения двух пространственных объектов……………………………………….18

2.       Работа с файлами формата *.3ds…………………………………………………………..24

2.1.       Функция импорта……………………………………………………………………..27

2.2.       Функция экспорта…………………………………………………………………….28

3.       Разработка динамически подключаемой библиотеки классов (DLL)…………………..30

3.1.       Функция экспорта в *.dll-файл………………………………………………………31

3.2.       Функция импорта из *.dll-файла…………………………………………………….32

4.       Разработка плагина для 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.      Объект задается набором треугольников, описывающих его поверхность. Для каждого треугольника известны лицевая и изнаночная стороны.

2.      Поверхность объекта (набор треугольников) должна быть замкнутой, без самопересечений

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.2.           Геометрические объекты в трехмерном пространстве

1.2.1.       Точка

Точка – простейший объект трехмерного мира. Задается значениями трех координат.

На ее основе построены все остальные классы. Единственная функция, реализованная для данного класса: вычисление расстояние между двумя точками, которое вычисляется по формуле:

1.2.2.       Вектор

Вектор задается одной точкой, исходя из того, что начало вектора приходится на начало координат, а его направление задает именно эта точка.

Для данной задачи реализованы такие операции по работе с трехмерными векторами, как:

      скалярное произведение:

,

где и - длины соответствующих векторов

      векторное произведение:

Отсюда легко найти вектор единичный нормальный вектор , т.е. вектор, перпендикулярный векторам и , и имеющий длину 1.

      Косинус угла между векторами. Его легко найти из формулы для скалярного произведения

      Нормализация вектора. Нормализованный вектор – это вектор, имеющий единичную длину. Для нормализации вектора нужно разделить его на текущую его длину.

      Также использованы такие функции, как: деление на скаляр, вычитание векторов, векторы сонаправлены или нет (угол между ними не более 90 градусов, но и не равен 90 градусам), векторы перпендикулярны или нет, вычисление длины вектора и др.

1.2.3.       Луч

Задается точкой, определяющей начало луча, и вектора, определяющего его направление. Никаких специфичных функций данный класс не содержит, единственной причиной, почему этот объект трехмерного мира выделен в отдельный класс – это то, что алгоритм получения положения точки относительно объекта использует в качестве вспомогательного элемента именно этот класс.

1.2.4.       Прямая

Этот класс для данной задачи играет более значительную роль. Задавать линию в трехмерном пространстве можно разными способами. В данной работе реализованы два способа: с помощью двух точек, принадлежащих данной прямой и с помощью одной точки и вектора направления.

Наиболее важными являются функции поиска точки пересечения двух прямых и поиск расстояния от точки до линии. Остановимся на каждой подробнее.

Алгоритм поиска точки пересечения двух прямых:

Изначально нужно проверить пересекаются ли прямые вообще, т.е. имеет ли смысл искать точку пересечения. Для этого сначала нужно проверить лежат ли они в одной плоскости, ведь, если прямые пересекаются, то они однозначно лежат в одной плоскости. Затем, если лежат, с помощью их векторов направления можно проверить их на параллельность. Если прямые не параллельны и лежат в одной плоскости, то, очевидно, они где-то пересекутся. В таком случае можно приступать к поиску точки пересечения.

Прямая в трехмерном пространстве задается уравнением:

Далее, при вычислениях если какой-нибудь из знаменателей данного уравнения окажется равным 0, то это будет означать, что по соответствующей координате стоящей в соответствующем числителе, линия является константой. Т.о., возможно, сразу удастся найти некоторые из неизвестных переменных-координат искомой точки. Составляя такое же уравнение и для другой прямой, ищутся все неизвестные координаты.

Расстояние от точки до линии вычисляется по формуле [3]:

,

где - какая-либо точка прямой , а - направляющий вектор прямой (см. Рисунок  2).

Также этот класс содержит несколько других немаловажных для всей задачи в целом функций, которые будут описаны позже по ходу изложения основных этапов конечного алгоритма.

1.2.5.       Треугольник

Треугольник задается тремя точками-вершинами и вектором нормали к его поверхности, определяющем лицевую и изнаночную сторону данного треугольника. Рассмотрим некоторые функции, выполняемые над треугольниками:

      Определение центра треугольника. Как известно, центр треугольника – точка пересечения его медиан. Медиана, в свою очередь – это отрезок с началом в одной из вершин треугольника и концом в середине противоположной стороны треугольника. Таким образом, все что надо сделать – составить две линии-медианы и найти их точку пересечения с помощью соответствующей функции.

      Определение того,  лежит ли линия в плоскости треугольника. Плоскость в трехмерном пространстве задается уравнением:

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

      Вычисление площади треугольника. Треугольник задан, следовательно, длины всех его сторон известны. Его площадь можно найти по формуле Герона:

      Определение того, находится ли точка внутри треугольника. Для начала можно определить принадлежит ли точка вообще плоскости треугольника. В большинстве случаев в данной задаче точка не будет принадлежать плоскости треугольника, поэтому, желательно такую проверку провести, хотя, следующий алгоритм все равно позволяет это определить. Т.о. точка «попадает» в треугольник, если

,

где – площадь соответствующего треугольника, – величина, близкая к нулю (для учета погрешности вычислений), если не учитывать, то точка принадлежит треугольнику, если:

Рисунок 2 наглядно показывает случай, когда точка лежит внутри треугольника и случай, когда точка лежит снаружи треугольника.

      Определение точки пересечения прямой и треугольника. Сначала удобно сделать проверку на параллельность прямой и плоскости треугольника. Далее, если не параллельны, найти точку пересечения прямой с плоскостью треугольника, а затем определить принадлежит ли данная точка области на этой плоскости, ограниченной тремя сторонами треугольника. Проверка на параллельность выполняется с помощью вектора нормали у треугольника и вектора направления у соответствующей прямой. Но здесь возможен вариант, в случае параллельности, что прямая лежит в плоскости треугольника. В этом случае достаточно определить точки пересечения прямой с ребрами треугольника. Если прямая и плоскость не параллельны, то, очевидно, они где-то пересекаются и можно приступать к поиску соответствующей точки. Сделать это можно, используя уравнение плоскости в трехмерном пространстве:

,

и уравнение прямой в пространстве, заданное в параметрическом виде [5]:

,

где – единичный вектор направления прямой, его можно вычислить следующим образом:

,

здесь и – две точки на прямой, – параметр, пробегающий значения от 0 до 1 и дающий все промежуточные точки на отрезке прямой . Разложив точку по трем координатам и подставив в уравнение для плоскости, можем найти параметр t в уравнении прямой. Далее, подставив найденное значение в уравнение прямой, найдем точку . Фактически, так и реализуется функция поиска точки пересечения двух прямых.

Сразу хочется заметить, что при определении точки пересечения прямой с треугольником, может получиться одна, две и три точки пересечения. Одна – в случае, когда прямая не лежит в плоскости треугольника и пересекает его в это точке; две – когда прямая лежит в плоскости треугольника и пересекает два его ребра; три – прямая лежит в плоскости треугольника и пересекает три его ребра (см. Рисунок 4).

Другие функции для данного класса будут рассмотрены ниже при построении конечных алгоритмов.

1.2.6.  Полигон

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

                                                        Рисунок 5. Примеры полигонов

Для этого класса реализованы 2 алгоритма:

                   Алгоритм определения положения точки относительно произвольного полигона

                   Алгоритм триангуляции полигона

1.2.6.1. Алгоритм определения положения точки относительно произвольного полигона

Идея данного алгоритма аналогична идее алгоритма определения положения точки относительно трехмерного объекта (см. далее)

Реализуется алгоритм в три этапа:

1.             Этап предподготовки: для всех ребер полигона нужно создать список векторов, указывающих правую сторону каждого ребра (т.е. указывающих вовнутрь полигона). Вектора должны находиться в плоскости полигона и каждый вектор должен быть перпендикулярен соответствующему ребру (аналог нормалей для граней трехмерного объекта). Их можно найти с помощью векторного произведения нормали к полигону и вектора направления соответствующего ребра.

2.             Ищем ближайший отрезок к данной точке путем анализа расстояний от точки до середины каждого отрезка.

3.            
Из данной точки пускаем луч в направлении середины найденного ближайшего отрезка в плоскости полигона. Далее сопоставляем направления двух векторов: вектора, построенного для ближайшего отрезка и вектора направления луча. Если они сонаправлены (т.е. угол отклонения не более 90 градусов), то точка находится вне полигона, иначе – внутри (см. Рисунок 7).

Стоит заметить, что данный алгоритм применим для полигонов, содержащих дырки, только если реализован правильный обход ребер полигона: ребра, ограничивающие дырку должны обходиться против часовой стрелки (см. Рисунок 8).

1.2.6.2. Алгоритм триангуляции полигона

Существует множество алгоритмов триангуляции полигонов [7] и все они дают специфичный для каждого алгоритма результат. Некоторые отличаются быстротой выполнения, другие эффективностью представления результата. В данной задаче алгоритм триангуляции используется лишь для того, чтобы разбить полигон, полученный при пересечении двух объектов, представленных в виде списка треугольников, на треугольники. Таким образом, вершин в этом полигоне будет немного. Кроме того, данный полигон может быть совершенно произвольной формы (не только выпуклый). Наиболее «красиво» выглядит триангуляция Делоне, но ввиду произвольности полигона использовать алгоритмы построения такой триангуляции нельзя, за исключением алгоритма, который предполагает разбиение невыпуклого полигона на несколько выпуклых.

В данной работе используется алгоритм, своей идеей похожий на жадный алгоритм [8], который оправдывает себя тем, что на небольшом количестве вершин его трудоемкость не сильно повлияет на трудоемкость всего алгоритма в целом (в общем случае трудоемкость жадного алгоритма имеет порядок N^2 * log N [8]).

Реализуется он следующим образом:

       Составляем список всех отрезков, из которых будут состоять треугольники. Для этого сначала составляем список всех возможных отрезков, которые потенциально могут быть гранями будущих треугольников (т.е. они не могут пересекаться с граничными отрезками). Затем добавляем к результирующему списку отрезки по одному, начиная с того, у которого длина минимальна. При добавлении очередного отрезка нужно учитывать то, что он не должен пересекаться ни с одним из уже добавленных к результирующему списку отрезков (см. Рисунок 2).

На данном этапе понадобится алгоритм определения положения точки относительно полигона (внутри или снаружи) для проверки положения линии относительно полигона: если середина отрезка принадлежит полигону, то отрезок находится внутри полигона,


иначе - снаружи. Этот алгоритм будет рассмотрен ниже.

       Используя список отрезков, являющихся ребрами будущих треугольников, составляем сами треугольники. Причем, вершины их необязательно должны обходиться по часовой стрелке. Но, т.к. нормаль к каждому из этих треугольников известна (она равна нормали к полигону), можно будет потом «развернуть» обход.

Нормали для образованных треугольников совпадают с нормалью для полигона. Это позволяет расположить вершины каждого треугольника по часовой стрелке.

1.2.7.       Трехмерный объект

Как говорилось выше, объект задан набором треугольников. Причем, объект является замкнутым, связным без самопересечений.

1.2.7.1.        Алгоритм определения положения точки относительно объекта

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

Идея состоит в следующем: ищем ближайший к точке треугольник, пускаем луч из данной точки к одной из вершин треугольника. Попутно нужно делать проверку на принадлежность точки текущему треугольнику. Далее смотрим на направление вектора-нормали к ближайшему треугольнику и направление луча. Если они совпадают (вектор нормали и вектор направления луча сонаправлены), то точка находится внутри объекта, иначе снаружи (см. Рисунок 10)

Рисунок 10. Точка находится снаружи объекта, вектора противоположно направлены

Основная сложность такого подхода заключается в нахождении ближайшего к данной точке треугольника. Изначально было сделано ошибочное предположение, что для данного алгоритма достаточно искать ближайший треугольник, высчитывая расстояние от данной точки до центра этого треугольника. Но, такой подход сработает не всегда. Так, на Рисунке 6, расстояние dist2 меньше, чем dist1, хотя ближайшим треугольником к точке является тот, до которого расстояние равно dist1.

Т.о. необходимо точно находить расстояние до треугольников.

Пусть необходимо вычислить расстояние от данной точки до некоторого треугольника. Сделать это можно следующим образом:

1. Опустим на плоскость треугольника перпендикуляр из данной точки, получим проекцию точки на плоскость
2. Если точка проекции принадлежит области, ограниченной данным треугольником, то длину перпендикуляра и будем считать расстоянием.
3. Иначе, находим расстояния до каждого из ребер треугольника и выбираем из них наименьшее. Делается это аналогичным образом: опускаем перпендикуляр на каждую из прямых, содержащих текущее ребро треугольника (т.е. ребро считается неограниченным в обе стороны), и, если точка проекции на прямую принадлежит текущему ребру, то, возможно, это и есть искомое расстояние. Может получиться так, что ни одна из точек проекций не принадлежит ребрам треугольника. В этом случае искомым расстоянием будет минимальное расстояние от точки до одной из вершин треугольника. Но здесь необходимо учитывать еще одну деталь: если точка проекции на плоскость находится за пределами треугольника, тогда при проецировании на ребро возникает неоднозначность выбора ближайшего треугольника

На Рисунке 12 изображена ситуация, когда ищется ближайший треугольник к точке P. Точка P находится «ниже» плоскостей обоих треугольников. Визуально видно, что правильным решением является треугольник АВС. Но расстояние, если следовать рисунку, до треугольника АBD от точки P будет таким же как от P до ABC.

Рисунок 12. Подсчет расстояния до треугольника

Найти правильное решение можно следующим путем:

Пусть угол L1 – угол между плоскостью АPB и плоскостью ABC, а угол L2 – угол между плоскостью APB и плоскостью ABD. Сравним два этих угла: точка будет ближе к тому треугольнику, для которого угол будет больше, т.е. если L2 > L1, то точка ближе к треугольнику ABD.

Возможны случаи, когда точка попадает на плоскость одного из треугольников, т.е. угол к этой плоскости будет равен либо 0, либо 180 градусам. Ближайшим в этом случае будет считаться другой треугольник.

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

1.2.7.2.              Алгоритм построения совокупной модели пересечения двух пространственных объектов

Суть данного алгоритма состоит в отсечении всех «невидимых» частей обоих объектов, т.е. тех их плоскостей, которые окажутся внутри совокупной модели.

Из-за того, что объекты могут пересекаться совершенно произвольным образом, треугольники, описывающие исходные объекты, могут перекрываться не полностью, а вследствие отсечения у них невидимых частей, может получиться произвольный полигон. Так, на Рисунке 13, показан контур полигона, получившийся при пересечении одного из треугольников, принадлежащих объекту A, с объектом B.

Алгоритм представляет собой несколько этапов:

1.             поиск отрезков, принадлежащих границе пересечения двух объектов.

2.             построение заготовок для полигонов и построение внешних отрезков

3.             построение полигонов из заготовок и множества отрезков

4.             построение полигонов из множества отрезков

5.             разбиение полигонов на треугольники (см. выше)

Далее эти этапы рассматриваются подробнее.

Поиск граничных отрезков

Под граничными отрезками понимаются отрезки, принадлежащие границе пересечения двух объектов (см. рисунок 14.В)

Отрезки пересечения двух объектов находятся с помощью функции поиска пересечений двух треугольников, т.о. перебирая все треугольники одного объекта и все треугольники другого объекта и находя их пересечения, можно получить все отрезки пересечения двух объектов в трехмерном пространстве.

Что касается поиска отрезков пересечения двух треугольников в трехмерном пространстве, то здесь используется та же идея, что и при получении списка пересечений двух объектов: сначала запускается процедура поиска всех отрезков пересечений, которые принадлежат ребрам первого треугольника и поверхности, ограниченной ребрами другого треугольника, а затем наоборот (см. Рисунок 15).

Таким образом, для построения отрезков, расположенных на границе пересечения двух объектов возможен следующий алгоритм:

Рассмотрим i-й треугольник, принадлежащий объекту А и j-й треугольник, принадлежащий объекту В. Для каждого ребра i-го треугольника ищем возможные точки пересечения с j-м треугольником. Далее, определяем находится ли найденный сегмент, ограниченный точками пересечения внутри j-го треугольника и, в зависимости от этого включаем его в список отрезков пересечения. То же надо проделать и для j-го треугольника. Т.о. алгоритм поиска пересечений трехмерных треугольников идентичен алгоритму поиска пересечений объектов в пространстве.

Построение заготовок для полигонов и построение внешних отрезков

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

Таким образом, заготовки полигонов, внешние отрезки и отрезки, принадлежащие границе пересечения двух объектов, позволяют получить полигоны. На Рисунке 16 изображены (слева – направо): два отрезка, вошедшие в заготовку для будущего полигона; пять отрезков (один из них скрыт геометрией OBJECT2), вошедших в список отрезков (среди них и внешние отрезки и граничные отрезки); и ребра конечного полигона.

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

На Рисунке 17 показаны несколько отрезков, для которых родителем является изображенный треугольник. Ломаная линия – граница пересечения этого треугольника с другим объектом. Часть треугольника, находящаяся справа от ломаной (залита темным цветом), находится внутри этого объекта.

Рисунок 17. Треугольник-родитель по отношению к выделенным отрезкам

Для отслеживания треугольников-родителей используются дополнительные флаги.

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

Получить такую информацию можно на этапе построения заготовок для полигонов.

Для каждого отрезка из множества отрезков флаги хранятся следующим образом:

int flags[4];

0й и 1й элементы – индексы двух треугольников для данного отрезка.

2й и 3й элементы – номера объектов (1 или 2) для соответствующих индексов треугольников (2й соответствет 0му, 3й – 1му)

Для заготовок достаточно запомнить одного родителя, т.к. он уникален для конкретной заготовки.

Флаги же для набора заготовок представляют собой одномерный массив длинны n+m, где n – количество треугольников в первом объекте, m – количество треугольников во втором объекте. Заготовок для каждого объекта может быть не более, чем количество треугольников в данном объекте (будет равенство, только если объекты не пересекаются). Т.о. начиная с элемента [0] хранятся индексы треугольников-родителей из первого объекта для соответствующей [i]-той заготовки, а с индекса [n] – из второго объекта.

Ниже рассмотрен механизм устранения «дырок» в полигоне за счет использования дополнительных флагов.

Решение проблемы «дырок» в полигонах путем использования дополнительных флагов

Под проблемой «дырок» понимается игнорирование пересечения объекта треугольником, принадлежащим другому объекту, когда ни одно из ребер треугольника не пересекает объект. Для наглядности на Рисунке 18 изображены две пирамиды с четырехугольным основанием, одна из них наполовину находится внутри другой.

Рисунок 18. Проблема «дырок» в полигонах

Треугольник АВС не разбивается на треугольники, т.е. часть треугольника не отсекается другим объектом. В результате полигон представляет собой все тот же треугольник АВС.

Использование дополнительных флагов позволяет решить эту проблему рассмотренным ниже способом.

Для отслеживания дырок необходимо усложнить структуру хранения отрезков дополнительной информацией:

typedef struct FOR_JOIN_LINES_TYP

{

LINE3D line;

int flags[4];

}FOR_JOIN_LINES;

typedef struct JOIN_LINES_TYP

{

vector <FOR_JOIN_LINES> hole1;

vector <FOR_JOIN_LINES> hole2;

              vector <FOR_JOIN_LINES> lines;

}JOIN_LINES;

hole1 и hole2 имеют тот же формат, что и lines и определяют множество дырок для первого и второго объекта соответственно.

Т.о. при построении полигона нужно проверить его на наличие дырок. Об этом скажут флаги в соответствующем множестве. Также при построении полигона в случае отсутствия ребра во множестве обычных отрезков lines нужно проверить не находится ли отрезок во множестве дырок hole.

Построение дырок в полигоне аналогично построению границы полигона, важно только правильно учитывать все флаги.

Не смотря на то, что алгоритм, описанный в данном разделе, разработан, в коде он на момент написания отчета не реализован.

Построение полигонов из заготовок и множества отрезков

Полигон представляет собой список вершин, расположенных по часовой стрелке, для определения лицевой и изнаночной стороны полигона. При построении полигона рассматриваемым алгоритмом обход по часовой стрелке не гарантируется, но, зная нормаль, всегда можно «развернуть» обход в нужном направлении. А нормаль можно узнать, пользуясь идеей дополнительных флагов, рассмотренной выше.

Так как отрезки пересечения не сохраняют направления обхода (для смежных треугольников общее ребро обходится в разных направления, см. Рисунок 19), то при выборе их для включения в полигон может возникнуть неприятный случай зацикливания. Это связано с тем, что отрезок проверяется на принадлежность в двух возможных направлениях. Например, некий отрезок АВ на текущем шаге был включен в полигон, точнее, его точка А совпала с последней точкой полигона, таким образом, последней точкой полигона стала В. Но при следующем обходе опять может выпасть отрезок АВ, т.к. точка В совпадает с последней точкой полигона и логично была бы выбрать для включения А. Чтобы этого избежать достаточно сделать простую проверку на равенство добавляемой точки и предпоследней точки полигона.

Построение полигонов из множества отрезков

Разница от предыдущего этапа в том, что отрезки для построения полигона берем из одного множества. И пытаемся из них составить полигон, учитывая принадлежность конкретному треугольнику-родителю (для отрезков из этого множества их 2). При этом часть отрезков уже включена в полигоны, так что распределить нужно только оставшиеся.

2.  Работа с файлами формата *.3ds

Для удобства загрузки трехмерных объектов в данной работе используется 3ds формат. Этот формат поддерживается большинством распространенных пакетов моделирования. 3ds формат является закрытым, т.е. нет точного указания места хранения нужной информации, что немного усложняет работу с ним.

Формат 3ds-файла имеет следующую особенность: все данные разделены на блоки – чанки.[9] Каждый чанк описывается именем и длиной. Чанки образуют древовидную структуру: один чанк может содержать внутри себя несколько других подчанков.

Каждый чанк имеет следующий формат:

                Заголовок чанка – 2 байта

                Его размер (= 6+n+m) – 4 байта

                Данные  – n байт

                Подчанки – m байт

Т.о., чанк 3DS-Version (будет рассмотрен далее) в двоичном виде будет иметь вид:

Рисунок 20

где

1 – это 0002, заголовок чанка

2 – это число 10, длина чанка (2[имя чанка] + 4[длина информационной части] + 4[сама информационная часть])

3  -  информационная часть, может содержать подчанки

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

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

Для работы с геометрией объекта достаточно знать информацию о нескольких чанках. Их структура представлена ниже:

Рисунок 21

Как уже говорилось выше, чанки, помимо подчанков, могут содержать некоторую информацию. Для данной задачи необходима только информация, содержащаяся в CHUNK_VERTLIST и CHUNK_FACELIST. Ниже они рассматриваются более детально.

CHUNK_VERTLIST (0x4110):

                Количество вершин – 2 байта

                Координаты каждой из вершин:

o                 x – 4 байта (float)

o                 z – 4 байта (float)

o                 y – 4 байта (float)

На каждую координату выделяется 4 байта. Всего у вершины три координаты, значит, на каждую вершину 12 байт. Учитывая количество вершин легко посчитать количество необходимых байт.

Следует заметить, что в 3ds-формате координаты вершины идут не в порядке (x, y, z),  а в порядке (x, z, y).

CHUNK_FACELIST (0x4120):

                Количество граней – 2 байта

                Для каждой грани:

o                 Индекс первой вершины – 2 байта

o                 Индекс второй вершины – 2 байта

o                 Индекс третей вершины – 2 байта

o                 Флаги – 2 байта

Флаги позволяют манипулировать с отображением граней:

                0й бит – грань АВ видима

                1й бит – грань ВС видима

                2й бит – грань СА видима

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

2.1. Функция импорта из *.3ds-файла

Идея алгоритма импорта из *.3ds-файла состоит в том, чтобы побитово считывать информацию, строго придерживаясь структуры файла. Т.е. нельзя искать идентификатор нужного чанка, не найдя идентификатор родителя. Так для извлечения информации о вершинах и гранях объекта необходимо пройти следующие этапы:

      Находим CHUNK_MAIN. Обычно он идет сразу с начала файла, но могут быть и исключения (если использованы чанки глобального уровня [12]) 

      Ищем CHUNK_OBJMESH. При этом нужно пропустить все ненужные чанки, которые могут также содержаться в CHUNK_MAIN. Если этого не сделать, то можно ошибиться, приняв за идентификатор искомого чанка величину 0x3D3D, которая на самом деле представляет данные ненужного чанка.

      Ищем CHUNK_OBJBLOCK.

      Ищем CHUNK_TRIMESH.

      Ищем CHUNK_VERTLIST. Этот чанк уже содержит важную информацию. Извлекаем информацию о количестве вершин, а затем сами вершины (три их координаты). Больше в этом блоке ничего не надо, впрочем, в нем больше ничего быть и не должно. В любом случае неплохо сделать проверку на то, что указатель позиции в файле стоит за CHUNK_VERTLIST.

      Ищем CHUNK_FACELIST. Здесь содержатся данные о гранях. Извлекаем их. В данном блоке могут быть (в отличие от предыдущего) другие подблоки. Поэтому важно переместить указатель позиции в файле на конец данного чанка.

      Теперь вся необходимая информация считана. Но для данной задачи необходимо рассчитать нормали к треугольникам, ограничивающим объект. Это удобно сделать на данном этапе.

2.2. Функция экспорта в *.3ds файл

В данной работе из 3ds-файла извлекается минимальное количество информации, нужное для дальнейшей работы: геометрия объекта. При записи в файл нужно внести немного больше информации, чтобы другие приложения могли использовать файл. Данная работа ориентирована прежде всего для содействия с 3D Studio Max, поэтому в файл записываются минимально достаточные для работы в этой среде с файлом данные.

Функция экспорта представляет собой побитовую запись информации в файл. При экспорте, помимо структуры формата, важно помнить о границе каждого чанка. Если при импорте (считывание из 3ds-файла) приходилось искать нужный чанк по имени и длина чанка, хоть и играла роль, но отступ на несколько байт не был критичным, то при экспорте (запись в 3ds-файл) важен каждый байт.

Что касается четкой границы каждого чанка, то важно помнить, что в файл записывается длина всего чанка, т.е. данные + длина + название [6]. Кроме того, байты пишутся в обратном порядке см. Рисунок 20.

Помимо чанков, которые просматривались для извлечения информации из файла, при записи необходимо знать точные данные следующих чанков:

Обозначения:

Chunk #               : кодовое имя

              Name       : название чанка

              Level      : уровень в дереве чанков

              Size       : длина

              Father     : кодовое имя родительского чанка

Чанки:

________________________________________________________

0x0002 : 3DS-Version

Chunk #    : 0x0002

Name       : 3DS-Version

Level      : 1

Size       : 4

Father     : 0x4D4D (Main chunk)

________________________________________________________

0x3D3E : Mesh version

Chunk #    : 0x3D3E

Name       : Mesh version

Level      : 2

Size       : 4

Father     : 0x3D3D (3D editor chunk)

________________________________________________________

0x0100 : One unit

Chunk #    : 0x0100

Name       : One unit

Level      : 2

Size       : 4

Father     : 3D Editor chunk

В данной работе для них используются стандартные для 3D Studio Max 8.0 значения:

3DS-Version: (int) 3

Mesh version: (int) 3

One unit: 0x0000803F

Остальные чанки описывают различные особенности сцены. Для данной задачи их использование не обязательно. В Приложении Г находится пример 3ds файла в двоичном виде.

Алгоритм экспорта объекта в *.3ds-файл состоит в подсчете длины чанка не в тот момент, когда чанк пишется в файл, а в тот, когда он полностью записан. Это связано с тем, что изначально длины чанков неизвестны (они зависят от длин самых «глубинных» чанков). Удобно изначально оставить место (4 байта) для длины текущего чанка, а потом, подсчитав его длину, на оставленное место записать точное значение.

3. Разработка динамически подключаемой библиотеки классов (DLL)

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

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

Процедуры и функции, содержащиеся в динамической библиотеке, можно разделить на два типа: те, которые могут быть вызваны из других приложений  и те, которые используются только внутри самого файла библиотеки.

Чтобы функции были доступны из внешних приложений, их необходимо объявлять рассмотренным ниже способом.

3.1.               Функция экспорта в dll-файл

В приложении, в котором будет «собираться» библиотека классов, т.е. будет происходить экспорт в dll-файл, нужно указать следующее:

…

extern "C"              //здесь хранятся функции, видимые из внешних приложений

{

_declspec (dllexport)  type NameFunction (parametres)

{

…

}

…

}

…

<здесь могут быть функции, видимые только внутри библиотеки>

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

В данной работе для успешного выполнения задачи необходимо лишь задать объекты. Следовательно, необходим интерфейс для класса OBJECT3D, реализованного в библиотеки классов. Но для описания объекта используется также класс POINT3D. Значит и для этого класса нужен интерфейс:

typedef struct point_type

{

              double x, y, z;

}point_3d;

typedef struct object_type

{

              vector <point_3d> vertexes;             

              vector <unsigned short> faces[3];             

}object_3d;

Эти 2 структуры также нужно объявить во внешнем приложении, использующем данную библиотеку.

Так как приложение, экспортирующее в dll функции, работает с классами, а приложение, импортирующее функции – со структурами, необходимо реализовать переход от класса к структуре и обратно. Все это сделано в библиотеке классов. В Приложении Б приведен код объявления функций, экспортирующих данные в dll.

3.2. Функция импорта из *.dll - файла

Для использования dll из внешнего приложения, следует придерживаться следующих этапов: сначала нужно объявить, как уже говорилось выше, все интерфейсы для классов. Затем нужно подгрузить библиотеку. Сделать это можно двумя способами: статически и динамически.[2]

При статическом использовании библиотека будет подгружаться и храниться в памяти сразу при запуске приложения. Это наиболее легкий способ использования кода, помещенного в dll . Недостаток метода заключается в том, что если файл библиотеки, на который имеется ссылка в приложении, отсутствует, программа откажется загружаться.

При динамической загрузке библиотека подгружается не при старте приложения, а когда это действительно необходимо. Преимуществом такого метода является быстрота работы приложения, т.к. библиотека не хранится в памяти все время. Выгрузить ее можно также вручную, либо она выгрузится сама при завершении работы приложения. Еще одним преимуществом такого способа является быстрый старт приложения, а также, что необходим только один файл *.dll. при статической загрузке нужен также *.lib файл, скомпонованный одновременно с *.dll файлом.

В демонстрационной программе используется динамическая загрузка dll.

Синтаксис следующий:

HINSTANCE hinstLib = LoadLibrary("graphics3d.dll");             

if (hinstLib == NULL)

{

                     printf("ERROR: unable to load DLL\n");

                            getchar();

}

Нужная функция из файла dll импортируется следующим образом:

1) Объявления типа:

typedef object_3d* (*JoinObjects)(object_3d *, object_3d *);

2)Объявление переменной:

JoinObjects JoinObj;

3)Получение адреса функции:

JoinObj = (JoinObjects)::GetProcAddress (hinstLib, "JoinObjects");

С этого момента можно использовать функцию JoinObj:

object3 = JoinObj (object1, object2);

В Приложении Е размещен фрагмент кода из внешнего приложения, иллюстрирующий импорт из dll

4. Разработка плагина для 3D Studio Max 8.0

Для того, чтобы удобнее использовать результат вышеизложенных алгоритмов, было разработано расширение (далее плагин) для 3D Studio Max.

Под плагином (англ. plug-in) понимают независимо компилируемый программный модуль динамически подключаемый к основной программе, предназначенный для расширения или использования её возможностей [4]

Разработка плагинов под 3dmax возможна двумя способами:
1.   с помощью языка скриптов (MAXScript)

2.       с помощью 3D Studio MAX SDK (Software Development Kit) и Visual Studio C++

Возможна еще реализация, совмещающая в себе оба пункта.

Под скриптом (сценарием) понимают программу, которая автоматизирует некоторую задачу, которую без сценария пользователь делал бы вручную, используя интерфейс программы [4]

MAXScript – объектно-ориентированный скриптовый язык программирования, встроенный в 3D Studio Max. Он очень удобен для написании небольших скриптов, позволяющих автоматизировать какие-либо действия в среде 3dmax. Разрабатывать на нем сложные плагины нецелесообразно ввиду относительно медленной скорости выполнения команд. Но MAXScript имеет заметное преимущество по сравнению со вторым методом: простота разработки кода.

Большая часть плагинов для 3dmax – это плагины, реализованные с помощью 3D Studio MAX SDK [10]. Главным преимуществом такого подхода является высокая скорость исполнения команд.

Удобным для разработки кода является способ, при котором интерфейс приложения реализован на MAXScript, а логика с помощью SDK. Это связано с тем, что в среде 3D Studio Max все плагины загружаются в память при запуске приложения. В данном случае интерфейс будет «зафиксирован» средой при запуске, а логика будет подгружаться при выполнении каких-либо действий с формой.

Т.о. плагин (plug-in) обычно понимают как динамически подключаемую библиотеку (DLL), которая экспортирует несколько функций, распознающихся тем приложением, для  которого пишется плагин. Единого стандарта типов экспортируемых функций нет, для каждого приложения требуются строго определенные функции, однако, приложения, предназначенные для одного типа задач, могут «понимать» плагины друг друга [11]

В 3D Studio Max существует огромное множество типов плагинов. Это могут быть экспортеры и импортеры геометрии, утилиты, модификаторы, плагины текстур и материалов и многие другие. Принято соглашение об именовании *.dll файлов согласно их предназначению. Например, для экспортеров характерно расширение *.dle. При этом файл не меняет своей структуры, а является все тем же *.dll-файлом. Для утилит характерно именование *.dlu .

Далее рассмотрены основные моменты реализации утилиты для 3D Studio Max, позволяющей работать с трехмерными объектами.

Структура плагина

Для того, чтобы 3D Studio Max мог распознать плагин, необходимо реализовать несколько, определенных в классах SDK, функций [13]

1. DllMain

              Стандартная main-функция используемая Windows для инициализации DLL

2. LibNumberClasses

В одной библитекеDLL может быть реализовано несколько плагинов. Каждый плагин описывается специальным классом (об этом рассказано ниже) Данная функция возвращает их количество.

3. LibVersion

              Возвращает версию 3D Max, для которой предназначен плагин. Ее можно получить из глобальной константы VERSION_3DSMAX, прописанной в Max SDK

4. LibDescription

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

5. LibClassDesc

Возвращает указатель на экземпляр класса-описателя конкретного плагина.

Все эти функции должны быть экспортируемыми.

Базовый класс

Если реализуется утилита, то класс, описывающий подобный плагин, должен быть порожден от базового класса UtilityObj, описанного в SDK. Именно с помощью этого класса ведется работа с формой. Этот класс является виртуальным и имеет пять методов, три из них разработчик должен реализовать в своём порожденном классе [13]

1.       DeleteThis

Используется для удаления экземпляра класса плагина.

2.       BeginEditParams

3.       EndEditParams

Два последних метода используются для панели управления. Первый – загружает ее в память в тот момент, когда пользователь открывает плагин. Второй – удаляет ее при завершении пользователем работы с плагином.

Панель управления представляет собой обычное диалоговое окно, созданное средствами Visual Studio (см. Рисунок 22).

Рисунок 22. Слева – диалоговое окно, открытое в редакторе Visual Studio, справа – в 3D Studio Max

Все объекты, которые должны реагировать на события (кнопки, поля вывода), являются объектами Custom Controls, что позволяет более удобную обработку событий [13]. Для работы с панелью управления используется класс Interface. Указатель на экземпляр этого класса передается средой в аргументы функций BeginEditParams и EndEditParams.

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

Класс-описатель плагина

Этот класс необходим для того, чтобы сообщить сведения системе о типе плагина. Он должен быть порожденным от класса ClassDesc2 (который порожден от класса ClassDesc), описанном в MAX SDK.

Для указания типа плагина используется уникальный общий идентификатор. Для плагинов утилитного типа его значение хранится в константе UTILITY_CLASS_ID.

Кроме того, каждый конкретный плагин должен иметь свой уникальный идентификатор. Для его генерации можно воспользоваться файлом gencid.exe, который поставляется со стандартным набором MAX SDK.

Ниже приведен фрагмент кода, где показан класс-описатель.

//получение уникального идентификатора

#define PLUGIN_CLASS_ID Class_ID(0x1218491c, 0x405444d4)

class PlaginClassDesc : public ClassDesc2

{

public:

  SClass_ID SuperClassID();

  Class_ID ClassID();

  void * Create(BOOL loading);

  const TCHAR *  ClassName();

  const TCHAR * Category();

  int IsPublic();             

};

Функция SuperClassID возвращает идентификатор UTILITY_CLASS_ID.

Функция ClassID возвращает идентификатор PLUGIN_CLASS_ID.

Функция Create возвращает указатель на экземпляр базового класса.

Функция ClassName возвращает строку, которая будет отображаться на кнопке вызова скрипта.

Функция Category возвращает строку, которая указывает принадлежность плагина к одной из категорий. Категории можно посмотреть в стандартном окне Configure Button Sets

Рисунок 23. Категории плагинов

Логическая часть плагина основана на классах, написанных ранее. Плагин поддерживает выбор объектов из окон трехмерного вида по щелчку мыши, вывод объекта полученного в результате пересечений двух других объектов в сцену, работу с алгоритмом определения положения точки относительно трехмерного объекта в сцене. Руководство пользователя 3D Studio Max 40 находится в Приложении А, руководство прикладного программиста в Приложении Б, руководство разработчика в Приложении В.

Заключение

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

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

Рассмотрена работа с библиотеками классов. Разработана библиотека классов на основе полученных ранее функций и классов.

Разработан плагин для 3D Studio Max, позволяющий использовать алгоритм построения объекта, полученного в результате пересечения двух других объектов.

Список литературы

1. Алексей Игнатенко. Геометрическое моделирование сплошных тел [Электронный ресурс]. – 2004. – Режим доступа к ресурсу: http://graphics.cs.msu.su/ru/library/3d/solid_modelling/index.html, свободный.
2. Библиотека RTFM [Электронный ресурс]. – 2008. – режим доступа к ресурсу: http://docs.luksian.com/programming/delphi/dlldelph/ , свободный
3. Кожухов И.Б., Прокофьев А.А. Универсальный справочник по математике. – М.: Лист Нью, Вече, 2002. – 544 с.
4. Компьютерные вести On-line. Плагин своими руками [Электронный ресурс]. – 2007. – Режим доступа к ресурсу: http://www.kv.by/index2007331201.htm , свободный
5. Ламот А. Программирование трехмерных игр для Windows. Советы профессионала по трехмерной графике и растеризации. /Пер. с англ. – М.: Издательский дом «Вильямс», 2004. – 1424 с.
6. Отрывок из DEMO.DESSIGN 3D programming FAQ [Электронный ресурс]. – Режим доступа к ресурсу: http://www.codenet.ru/progr/formt/3ds.php , свободный
7. Романюк А, Сторчак А.. Алгоритмы триангуляции [Электронный ресурс]. – 2004. – Режим доступа к ресурсу: http://www.citforum.ru/programming/theory/alg_triangl/index.shtml, свободный
8. Скворцов А.В. Триангуляция Делоне и ее применение. – Издательство ТГУ, 2002. – 127с.

9.       GameDev / Формат 3DS: Первый шаг [Электронный ресурс]. – 2005. – Режим доступа к ресурсу: http://www.gamedev.ru/articles/?id=40113&page=2, свободный

10.   GameDev / Р. Марченко. Создание Export плагина для 3D Studio Max [Электронный ресурс]. – 2005. Режим доступа к ресурсу: http://www.codenet.ru/progr/video/3D-Studio-Max-Export-Plugin.php, свободный

11.   GameDev / Основы плагиностроения к 3D Studio Max [Электронный ресурс]. – 2001. Режим доступа к ресурсу: http://www.gamedev.ru/users/wat/articles/MAXPlugins , свободный

12. 3D Studio File Format Information (3dsinfo.txt) by Jochen Wilhelmy [Электронный ресурс]. – 1997. – Режим доступа к ресурсу:   http://www.jalix.org/ressources/graphics/3DS/_unofficials/3ds-info.txt , свободный
13. Autodesk 3ds Max 8 SDK Help

Приложение А. Руководство пользователя 3D Studio Max

Загрузка плагина.

Работоспособность плагина в среде 3D Studio Max младше версии 5.0 не гарантируется.

Для того, чтобы 3D Studio Max распознал плагин и загрузил в систему, необходимо:

1.      скопировать плагин JoinObjects.dlu в папку stdplugs в каталог установки 3D Max

2.      запустить 3D Studio Max. Плагин должен автоматически загрузиться в память. Для проверки корректной загрузки можно использовать окно Plug-in Manager, находящееся в меню Customize (см. рисунок А). Если справа о названия файла плагина стоит loaded, то файл корректно распознан.

Рисунок А. Окно Plug-in Manager

3.      далее нужно добавить кнопку запуска плагина в перечень утилит. Для этого надо перейти на вкладку Utilities в основной панели инструментов, нажать кнопку Configure Button Sets. Установить счетчик Total Buttons на единицу больше и перетащить плагин JoinObjects, который находится в списке Utiliites данного окна в группе Utilities на кнопку, появившуюся в самом конце списка после увеличения счетчика.

4.      После закрытия окна Configure Button Sets появится кнопка в списке Utilities c названием Join Objects

Работа с плагином

Форма плагина содержит 3 группы кнопок (см. Рисунок Б): группы Object1 и Object2 предназначены для выбора двух объектов. В группе Calculate result object содержится кнопка Calculate and output, при нажатии на которой выполнится функция построения третьего объекта на основе двух предыдущих и результат будет отображен в окнах 3D вида. Для каждого объекта предусмотрена функция, при помощи которой можно определить положение точки относительно объекта. Для данной задачи ее можно применять для определения направления нормалей (объекты должны быть замкнутыми и нормали должны смотреть не вовнутрь объекта, а наружу). Для того, чтобы использовать данную функцию, нужно выбрать точку, делается это с помощью кнопки Pick point (по умолчанию точка имеет координаты (0, 0, 0)) и проверить результат, нажав на кнопку Obj has point. Слева выведется результат операции: true или false

Рисунок Б. Панель управления

Если функция определения положения точки относительно объекта дала отрицательный результат (визуально видно, что точка находится внутри/снаружи объекта, а функция вернула false/true), то необходимо для дальнейших корректных вычислений развернуть нормали для треугольников объекта. Делается это нажатием на кнопке Invert normals для соответствующего объекта.

Приложение Б. Руководство прикладного программиста

Файл динамически подключаемой библиотеки имеет название graphics3d.dll.

Экспортируемыми функциями библиотеки являются:

bool WriteObject3ds(const char *path, object_3d *obj);

Позволяет записать объект obj в файл формата *.3ds. path указывает путь к файлу, включая его название. Если такого файла не существует, то он будет создан

object_3d* JoinObjects(object_3d* obj1, object_3d* obj2);

На основе двух пересекающихся трехмерных объектов, которые передаются как параметры функции, строит результирующий объект и возвращает указатель на него.

object_3d* ReadObject3ds(const char* path);

Позволяет считать объект из *.3ds файла, путь к которому передается в переменной path

Для использования этих функций во внешнем приложении необходимо прописать и заполнить при необходимости структуры (интерфейс библиотеки):

typedef struct point_type

{

              double x, y, z;

}point_3d;

typedef struct object_type

{

              vector <point_3d> vertexes;              //все вершины объекта

              vector <unsigned short> faces[3];                            //грани.

} object_3d;

Приложение В. Руководство разработчика

В гарницах данной работы реализованы два продукта, позволяющих работать с операцией объединения двух трехмерных объектов: динамическая библиотека (файл graphics3d.dll) и плагин для 3D Studio Max 8.0 (файл JoinObkect.dlu).

Динамическая библиотека разработана в среде Visual C++, для разработки плагина использовался 3D Studio Max SDK.

В ходе работы разработаны следующие классы:

POIN3D – позволяет работать с трехмерной точкой.

LINE3D – позволяет работать с трехмерной прямой. Содержит такие функции как:

       Поиск точки пересечения двух прямых

       Факт пересечения двух прямых (пересекаются ли прямые вообще)

       Расстояние от точки до линии

       Поиск точки проекции на линию другой точки

LUCH3D – позволяет работать с лучом в трехмерном пространстве. Луч представляет собой точку начала и направление. Специфичных функций не содержит, используется как вспомогательный класс

OBJECT3D – позволяет работать с трехмерным объектом. Содержит такие функции как:

       Определение положения точки относительно объекта (внутри или снаружи)

       Поиск списка точек пересечения объекта трехмерной прямой

       Поиск точек пересечения объекта отрезком трехмерной прямой

       Построение результирующего объекта на основе пересечения двух других объектов

       Поиск отрезков пересечения двух объектов и поиск отрезков, не вошедших в пересечение (т.е. построение «каркаса» результирующего объекта, используемый в предыдущей функции)

POLI3D – позволяет работать с полигоном в трехмерном пространстве. Содержит такие функции как:

       Определение положения точки относительно полигона (внутри или снаружи)

       Триангуляция произвольного полигона

TRIANGLE3D – позволяет работать с треугольником в трехмерном пространстве. Содержит такие функции как:

       Подсчет нормали с учетом расположения вершин по часовой стрелке

       Определение того, лежит ли линия в плоскости треугольника

       Подсчет площади треугольника

       Нахождение точки пересечения с прямой, если она существует

       Определение положения точки относительно треугольника (внутри или снаружи)

       Расстояние от точки до треугольника

       Определение принадлежности точки области треугольника

       Нахождение линии пересечения двух треугольников

VECTOR3D – позволяет работать с вектором в трехмерном пространстве. Содержит такие функции как:

       Подсчет длины вектора

       Нахождение скалярного и векторного произведения векторов

       Нахождение косинуса угла между векторами

       Проверка на сонаправленность векторов

       Проверка перпендикулярности векторов

FORMAT3DS – позволяет работать с форматом *.3ds-файлов. Содержит такие функции как:

       Запись трехмерного объекта в файл

       Считывание трехмерного объекта из файла

Приложение Г. Пример файла в формате 3ds в двоичном виде

Пирамида с четырехугольным основанием в формате 3ds

Приложение Д. Прототипы функций экспорта данных в dll и работа с интерфейсами

object_3d* ModificationObject1(OBJECT3D &other);              //эта функция не //экспортируется

OBJECT3D ModificationObject2(object_3d *other);              //эта функция не //экспортируется

extern "C"              //Тут экспортируемые функции

{

_declspec (dllexport) bool WriteObject3ds(const char *path, object_3d *obj);

_declspec(dllexport) object_3d* JoinObjects(object_3d* obj1, object_3d* obj2);

_declspec(dllexport) object_3d* ReadObject3ds(const char* part);

}

object_3d* ModificationObject1(OBJECT3D &other);

OBJECT3D ModificationObject2(object_3d *other);

Приложение Е. Пример импорта функций из dll внешним приложением

HINSTANCE hinstLib = LoadLibrary("graphics3d.dll");             

if (hinstLib == NULL)

              {

         printf("ERROR: unable to load DLL\n");

                            getchar();

                  }

              //получаем функцию JoinnObjects

              typedef object_3d* (*JoinObjects)(object_3d *, object_3d *);

              JoinObjects JoinObj;

              JoinObj = (JoinObjects)::GetProcAddress (hinstLib, "JoinObjects");

              //получаем функцию ReadObject3ds

              typedef object_3d* (*ReadObject3ds)(const char*);

              ReadObject3ds ReadObj;

              ReadObj = (ReadObject3ds)::GetProcAddress(hinstLib, "ReadObject3ds");

              object1 = new object_3d;

              object2 = new object_3d;

              object1 = ReadObj("object1.3ds");

              object2 = ReadObj("object2.3ds");

              object3 = new object_3d;

              object3 = JoinObj (object1, object2);

              //а теперь запишем в 3ds файл object3

              bool res;              //тут будет результат записи в файл

              typedef bool (*WriteObject3ds)(const char *, object_3d *);

              WriteObject3ds WriteObj;

              WriteObj = (WriteObject3ds)::GetProcAddress(hinstLib, "WriteObject3ds");

res = WriteObj("ResObj.3ds", object3);              //в файле "ResObj.3ds" будет //лежать результирующий объект

              cout << "\nWriteObject3ds: " << res;

40