Разработка и исследование алгоритмов сжатия 3-х мерных графических объектов для коллективного проектирования в компьютерных сетях

• Автор: Федотов, Роман Владимирович
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Самара
• Количество страниц: 133 с. : ил.

ОГЛАВЛЕНИЕ
Введение

1 Краткий обзор состояния вопроса и постановка задач исследования

1.1 Алгоритмы снижения числа элементов описывающих

ЗОмодель.

1.2 Оптимизация модели с учетом передачи по сети

1.3 Задачи исследования.

2 Сжатие инженерных моделей с учетом специфики сжимаемых данных

2.1 Специфика инженерных ЗОмоделей.

2.2 Распознавание и кодирование повторяющихся объектов

2.3 Метод сжатия полигональных инженерных ЗОмоделей с

помощью автоматического поиска плоских элементов . .
2.4 Выводы по главе 2.
3 Реализация алгоритмов автоматического поиска плоских элементов
3.1 Общая схема алгоритмов поиска плоских элементов .
3.2 Алгоритм перебора сочетаний.
3.3 Алгоритм плоских сечений
3.3.1 Исследование сечений множества Уо в направлении
3.3.2 Генерация множеств с заданным отклонением соседних элементов
3.3.3 Оценка быстродействия и ресурсоемкости алгоритма
3.4 Эффективное кодирование найденных групп.
3.4.1 Оценка эффективности введения группы
3.4.2 Подбор оптимального сочетания множеств V2 для максимизации коэффициента сжатия
3.5 Сетевая передача .
3.5.1 Оптимизированная передача с постоянным уровнем детализации
3.5.2 Прогрессивная передача модели.
3.6 Выводы по главе 3.
4 Экспериментальные исследования
4.1 Задачи экспериментальных исследований.
4.2 Разработанное программное обеспечение.
4.3 Экспериментальные подтверждения эффективности метода сжатия с помощью поиска плоских элементов
4.4 Экспериментальные данные о производительности алгоритмов поиска плоских элементов.
4.5 Результаты работы алгоритма плоских сечений. Сравнение данных о различных способах генерации множества
4.5.1 Анализ зависимости коэффициента сжатия от числа итераций.
4.5.2 Анализ Зависимости числа найденных плоских элементов от числа итераций
4.5.3 Анализ зависимости коэффициента сжатия от
числа найденных плоских элементов.
4.6 Выводы по главе 4
Заключение
Литература


Апробация результатов работы и публикации. Основные результаты по теме диссертационного исследования докладывались на X и XI Всероссийских научных конференциях ПГАТИ (Самара, , г. Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и образовании» РГРТА (Рязань, ), IV Международной школе-семинаре БИКАМП' (ГУАП, Санкт-Петербург, г. Основные научные и прикладные результаты опубликованы в 3 статьях в периодических научных изданиях и в 3 публикациях в форме тезисов докладов на российских конференциях. Объем и структура работы: Диссертация состоит из введения, 4 глав, списка литературы, включающего наименований и приложений. Настоящая работа выполнялась на кафедре вычислительной техники Поволжской государственной академии телекоммуникаций и информатики. Экспериментальные исследования были выполнены в ФГУП «Научное конструкторско-технологическое бюро „Парсек" Минобразования России». Полигональная ЗО-модель представляет из себя один или несколько многогранников, состоящих из треугольных граней [ — ]. Модель задают множеством вершин V — {п,. К3 и г = (гх,гу,г2) и множеством граней и ребер К, описывающим топологию модели. Ребро, соединяющее вершины и г}, задается парой чисел {г,і), где г,. Треугольная грань с вершинами г}, г}, г* задается тройкой чисел {і,і>к}, где г,Л: Є {1,. Обозначим модель, заданную множествами V и /С, как Л/(К, /С). Модель до сжатия обозначим как Л/о(Ц, ^о)< после сжатия Л/С(КС, /<ГС). Существуют и другие способы описания трехмерной геометрии [,], но спектр их применения значительно ниже, по сравнению с полигональным способом задания. Уменьшение числа обрабатываемых граней или описание их с помощью более сложных примитивов широко используется при кодировании смежных граней. Грань модели во множестве К задается тройкой чисел {г,к}, являющимися ссылками на вершины г}, г;, г*. Учитывая тот факт, что модель состоит из смежных граней, были разработаны способы эффективного кодирования граней [4 — , —]. Основная идея такого кодирования смежных граней заключается в кодировании лент и вееров граней модели (см. Рис. Для кодирования смешанной ленты (см. Для ленты бит равен О, для веера 1. Обычно модель невозможно описать при помощи одной ленты. При кодировании топологических элементов таким методом организуется дерево, состоящее из отдельных смешанных лент. Такой способ представления широко используется в сетевых форматах [], так как при передаче очередной вершины автоматически восстанавливается треугольная грань. Системы построения изображения реального времени используют примитив, описывающий ленту граней. В стандарте орепСЬ [] существует такой примитив. Это связано с упрощением закраски граней, организованных таким способом. Уменьшение числа вершин (ребер, граней), описывающих модель (упрощение геометрии модели), приводит к повышению быстродействия алгоритмов просчета изображения, упрощает манипуляции с моделью и сокращает используемую память и, как следствие, трафик при сетевом доступе [ — ]. Ус , Кс. Множество Ус может являться подмножеством или иметь с ним область пересечения в зависимости от того, перестраивает ли алгоритм модель или просто упрощает, удаляя вершины менее всего влияющие на геометрию по заданным параметрам. Рис. Наиболее быстрым алгоритмом упрощения геометрии является алгоритм кластеризации вершин [ —]. Метод состоит в объединении вершин, находящихся в одном кластере пространства, в одну. Кластеры представляют собой трехмерную сетку, то есть координаты вершин фактически округляются с заданной точностью, а при совпадении нескольких вершин, после округления, вершины заменяются одной. Все ссылки множества К наколлапсируемые вершины заменяются ссылками на новую вершину (см. Большим преимуществом данного метода является его простота и быстродействие, что дает возможность использовать его в режиме реального времени []. Основным минусом является потеря первоначальной топологии объекта, это может привести к серьезным ошибкам, поэтому метод не может быть универсальным.