Алгоритмы восстановления трехмерных объектов по трем двухмерным ортогональным проекциям. Разработка программы, принимающей на вход три 2D проекции в одном из базовых CAD форматов и восстанавливающей каркасную 3D модель заданного объекта на выходе.
Аннотация к работе
Для того чтобы получить более широкое представление о том, что получится в итоге, создается 3D модель, даже если этот процесс занимает значительное количество времени. Наибольший прорыв в области восстановления 3D моделей совершили Wesley и Markowsky в своих работах [8, 11], предложив использовать каркасную модель как промежуточный шаг процесса восстановления. На сегодняшний день они являются одними из самых известных исследователей в этой области, а их подход используется при разработке практически любого нового алгоритма восстановления 3D моделей. Процесс восстановления, который включает в себя взаимодействие пользователя с системой, чаще всего занимает значительное количество времени, вследствие чего разрабатываются различные алгоритмы для автоматического восстановления 3D моделей. На данных момент существует два основных похода к восстановление 3D моделей: метод отображения границ и метод конструктивной сплошной геометрии.Кроме этого Kompas-3D и Blender не имеют функционала восстановления 3D моделей из 2D проекций. Autocad широко используется в сфере инженерного проектирования, однако реализованная в этой программе система восстановления 3D моделей из проекций основана на взаимодействии пользователя с системой. 3DS Max является практически самой распространенной и широко используемой системой для работы с трехмерной графикой. Программа предоставляет возможность восстанавливать 3D модель по проекциям, однако имеет довольно сложный интерфейс, а так же работает только в операционной системе Windows. Целью данной выпускной квалификационной работы является разработка программы восстановления каркасных 3D объектов, состоящих из многогранников, по 2D ортогональным проекциям для операционной системы OS X.Idesawa предложил способы восстановления трехмерных вершин, ребер и лицевых поверхностей для многогранных объектов. Кроме того, так как некоторый набор вершин и ребер (каркасная модель) может описывать несколько объектов, он предложи способ, как удалять “призрачные ”ребра для того чтобы в итоге получать уникальный объект. Все вершины представляются в виде их координат x, y, z и порядковых номеров этих вершин. Пусть описывает вершину, тогда описывает набор вершин, которые соединяюются с ребрами. Точки в трехмерном пространстве описываются как , (1) где - координаты i-го элемента списка вершин, с - некоторая координата, - количество вершин в , - количество вершин в , - количество вершин в .На входе в программу принимаются три проекции, из которых считываются данные о примитивах. Шаг 2: Найти, сохранить в списке все элементарные петли (петли, которые не содержат других петель) и отметить их как “открытые”. Для того чтобы доказать или опровергнуть это, необходимо выполнить следующий алгоритм: · Случайным образом выбирается проекция и в ней ищутся все прямоугольные силуэты , которые совпадают с P. · Проанализировать P и найти все примитивы, которые требуют наличия линий в одной или обеих проекциях (базовая проекция не учитывается). Шаг 5: “Увеличить” петлю P, создав все петли, которые включают в себя петли, прилежащие к P, если их еще не существует.Каркасная модель объекта строится по фронтальной проекции (FV - front view), боковой проекции - виду справа (SV - side view) и верхней проекции - вид сверху (TV - top view), которые подаются на вход программе в формате систем автоматизированного проектирования (САПР) DXF.Для того чтобы уменьшить количество параметров, определяющих ребра, каждая вершина отмечается порядковым номером. Номера вершин будут описывать ребра вместо координат этих вершин. Таким образом для каждой проекции создаются матрицы и для хранения информации о вершинах и ребрах соответственно: , где - порядковый номер i-ой вершины, - координаты i-ой вершины, i =1,2,…,k k - количество вершин проекции. Каждый объект типа «ребро» содержит4 следующую информацию: , где - порядковый номер ребра, - порядковый номер вершины, определяющей начало ребра, - порядковый номер вершины, определяющей конец ребра, - тип ребра, i = 1,2,…,n, n - количество ребер проекции. Таким образом, матрица вершин содержит порядковые номера вершин проекции и их координаты, а матрица ребер - порядковые номера ребер и порядковые номера вершин, определяющих эти ребра.Для последующей работы с данными о проекциях необходимо создать две новых матрицы и для верхней и боковой проекции соответственно. После этого нужно выполнить следующие операции над новыми матрицами: , , где rtv[i,3] - элемент i-ой строки и третьего столбца матрицы (координата y), rtv[i,4] - элемент i-ой строки и четвертого столбца матрицы (координата z), rsv[i,2] - элемент i-ой строки и второго столбца матрицы (координата x), rsv[i,4] - элемент i-ой 4строки и четвертого столбца матрицы (координата z).Заранее не известно, какие именно ребра пересекаются; для каждого ребра проверяются все остальные, еще не проверенные ребра, на предмет их пересечения. В этой проверке можно выделить четыре случая: ребра параллельны / находятся на одной прямой / скрещиваются (лежат в параллельных п
План
Содержание
Введение
1. Обзор существующих подходов и программных решений
1.1 Существующие подходы
1.1.1 Метод отображения границ
1.1.2 Конструктивная сплошная геометрия
1.1.3 Восстановление сплошных тел по шести проекциям
2. Описание используемых алгоритмов
2.1 Извлечение 2D ортографической информации
2.2 Разметка 2D граней и вершин
2.3 Объединение граней и вершин
2.4 Нахождение точек пересечения ребер
2.4.1 Определение нахождения ребер на одной прямой
2.4.2 Определение пересечения ребер
2.5 Создание не ортогональных ребер
2.6 Удаление лишних ребер
3. Разработка программы
3.1 Формат DXF
3.2 Формат входных данных
3.3 Выходные данные
3.4 Выбор средств разработки
3.5 Диаграмма классов
3.6 Вывод на экран каркасной модели
Заключение
Используемые источники
Приложение
Введение
Восстановление 3D моделей по их 2D проекциям является важным объектом исследования уже долгое время. В основном свое применение эта область исследования нашла в инженерном деле. До того как построить некоторую деталь, создаются ее различные чертежи и проекции. Для того чтобы получить более широкое представление о том, что получится в итоге, создается 3D модель, даже если этот процесс занимает значительное количество времени.
Наибольший прорыв в области восстановления 3D моделей совершили Wesley и Markowsky в своих работах [8, 11], предложив использовать каркасную модель как промежуточный шаг процесса восстановления. На сегодняшний день они являются одними из самых известных исследователей в этой области, а их подход используется при разработке практически любого нового алгоритма восстановления 3D моделей.
Процесс восстановления, который включает в себя взаимодействие пользователя с системой, чаще всего занимает значительное количество времени, вследствие чего разрабатываются различные алгоритмы для автоматического восстановления 3D моделей. Эти алгоритмы могут быть разделены на два типа в зависимости от существующих подходов. На данных момент существует два основных похода к восстановление 3D моделей: метод отображения границ и метод конструктивной сплошной геометрии. Метод отображения границ состоит в работе с линиями (ребрами) и вершинами, в свою очередь метод конструктивной сплошной геометрии основан на работе с геометрическими примитивами, такими как куб или шар.
Можно выделить две основные стадии восстановления 3D объектов по проекциям: создание псевдокаркасной модели объекта (pseudo-wireframe) и создание объекта (solid). Псевдокаркасная модель состоит из набора вершин и ребер, соединяющих эти вершины. Она может содержать лишнюю, но в то же время более полную информацию об описываемом объекте. В отличие от каркасной модели, она может включать в себя «лишние» ребра, которые принадлежат описывающим ее проекциям (рис. 1) Одна псевдокаркасная модель может описывать большое количество 3D объектов (рис .2).
Рисунок 1 Три проекции октаэдра
Рисунок 2 (a) - псевдокаркасная модель октаэдра, (b, c, d) - возможные solid объекты, этой модели
При анализе существующих приложений, предоставляющих возможность работы с 3D моделями, было выделено несколько самых популярных решений: Autodesk 3DS Max, Autodesk Autocad, Kompas-3D, Matlab, Blender (табл. 1).
Сравнительная таблица существующих решений
Windows OS X Необходимость специальных знаний Восстановление каркасной модели Автоматическое выполнение функции Лицензия