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

На правахрукописи

Федотов Роман Владимирович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ СЖАТИЯ 3-Х МЕРНЫХ ГРАФИЧЕСКИХ ОБЪЕКТОВ ДЛЯ КОЛЛЕКТИВНОГО ПРОЕКТИРОВАНИЯ В КОМПЬЮТЕРНЫХСЕТЯХ

Специальность 05.13.13 Телекоммуникационные системы и компьютерные сети

Авто реферат диссертации на соискание ученой степени кандидата технических наук

Самара -

2004

Работа выполнена в Поволжской государственной академии телекоммуникаций и информатики (ПГАТИ) Министерства Российской Федерации по связи и информатизации.

Научный руководитель:

-доктор технических наук, профессор

Официальные оппоненты:

-доктор технических наук, профессор

-кандидаттехнических наук, докторант

Кораблин МЛ

Ка рташевский В.Г. Глумов Н.И.

Ведущее предприятие Институт систем обработки изображений РАН.

Защита диссертации состоится .

. 2004 г. в

на заседании дис-

сертационного совета Д 219.003.002 Поволжской государственной академии телекоммуникаций и информатики по адресу. 443010, г. Самара, ул. Льва Толстого 23.

Отзыв на автореферат в двух экземплярах, заверенный печатью учреждения, просим высылать по адресу: 443010, г. Самара, ул. Льва Толстого 23, ПГАТИ.

С диссертацией соискателя можно ознакомиться в библиотеке Поволжской государственной академии телекоммуникаций и информатики.

Автореферат разослан

г.

Ученый секретарь

диссертационного совета Д 219.003.002, доктор технических наук, профессор

Николаев Б.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность темы.

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

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

Наиболее распространенный способ описания объемной модели — представление ее в виде множества смежных треугольных граней. Этот способ описания поддерживается большинством Интернет-ориентированных форматов.

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

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

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

РОС'НАЦНОНЛЛЬНЛЯI БИБЛИОТЕКА 1

оУ^Ш 1

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

Научная новизна работы заключается в следующем:

1. Выявлен ряд специфических особенностей характерных для инженерных ЗО-моделей.

2. Предложен новый способ кодирования ЗО-моделей, учитывающий специфику геометрии модели.

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

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

5. Разработан алгоритм подбора сочетаний групп вершин для максимизации коэффициента сжатия.

6. Предложены способы сетевой передачи сжатой модели.

Практическая ценность и реализация заключается в:

• разработке эффективной технологии сжатия и сетевой передачи сжатых инженерных ЗО-моделей.

• разработке способа внедрения предлагаемой технологии сжатия в существующие форматы.

• разработке программного обеспечения, реализующего алгоритм перебора сочетаний, алгоритм плоских сечений, алгоритм подбора сочетаний групп вершин.

Апробация результатов работы и публикации. Основные результаты по теме диссертационного исследования докладывались на X и XI Всероссийских научных конференциях ПГАТИ (Самара, 2003, 2004 г., соответственно), 6-й Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и образовании» РГРТА (Рязань, 2001), IV Международной школе-семинаре БИКАМП'03 (ГУАП, Санкт-Петербург, 2003 г.)

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

Объем и структура работы. Диссертация состоит из введения, 4 глав, списка литературы, включающего 72 наименования, и приложений. Основная часть работы содержит 110 страниц, включая 67 рисунков и 5 таблиц.

Настоящая работа выполнялась на кафедре вычислительной техники Поволжской государственной академии телекоммуникаций и Информатики. Экспериментальные исследования были выполнены в ФГУП «Научное конструкторско-технологическое бюро „Парсек" Минобразования России».

На защиту выносятся:

1* метод кодирования ЗБ-моделей с помощью автоматического поиска плоских элементов;

• алгоритм сжатия на основе перебора сочетаний троек вершин;

• алгоритм сжатия на основе поиска плоских сечений;

• алгоритмы генерации множества направлений для алгоритма плоских сечений;

• структура сжатых данных;

• адаптация существующих методов сетевой передачи для сжатых данных;

• программа, реализующая разработанные алгоритмы сжатия;

• результаты экспериментальных, исследований предложенных алгоритмов.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматриваются существующие алгоритмы эффективного кодирования, упрощения и сетевой передачи ЗЭ-моделей.

Полигональная ЗЭ-модель представляет из себя один или несколько многогранников, состоящих из треугольных граней. Модель задают множеством вершин V — {п,..., f„}. ?¡ € R3 и г = (гх, гу, г,) и множеством граней и ребер К, описывающим топологию модели. Ребро, соединяющее вершины г< и rj, задается парой чисел {», j}, где i,j € {1,...,«}. Треугольная грань с вершинами г<, Tj, Гк задается тройкой чисел {i,j,k}, где i,j,k 6 {1,...,п}. Существуют и другие способы описания трехмерной геометрии, но спектр их применения значительно уже по сравнению с полигональным способом задания трехмерных объектов.

Рассматриваемая группа алгоритмов снижает объем, занимаемый 3D-моделью за счет эффективного кодирования множеств V и К. Рассматриваются алгоритмы по поиску и кодированию «ленты граней». Такой способ задания удобен для быстрого построения изображений и широко используется в системах трёхмерной графики. Наиболее известными в этой области являются работы Изенбурга (Isenburg M.). Snoeyink J. Капуэ (Кароог N. S.), Кодаковского

(Khodakovsky А.), Алиеза (Alliez Р.), Дезбрана (Desbrun М.), Шредера (Schroeder Р.).

Вторая группа рассматриваемых алгоритмов сжимает ЗО-модель, сокращая множество Vo с целью уменьшения числа описывающих модель примитивов. Эти алгоритмы описаны в работах Россинака (Rossignac J.), Борела (Borrel P.), Лоу (Low К. L), Тан (Tan T. S). Наиболее быстродейственные и простые алгоритмы этой группы прореживают множество Vo по заданному критерию. Сложные алгоритмы производят оптимизацию геометрии модели, минимизируя целевую функцию. Качество работы прореживающих алгоритмов зависит от выбора критерия для удаления вершины и предварительной классификации вершин. После удаления вершины необходимо решить задачу триангуляции отверстия. Описаны несколько алгоритмов триангуляции.

Перестройка множества Vo — более ресурсоемкая стратегия упрощения геометрии. Для реализации таких алгоритмов вводят критерии оценки сохранения первоначальной формы объекта. Для гладких поверхностей Турк (Turk G.) предложил сохранять кривизну, для общих случаев Хоупом (Норре Н.), Дэ'Роузом (DeRose Т.), Дюшаном (Duchamp Т.) разработана энергетическая функция, оценивающая суммарное отклонение элементов множества Vc от идеальной модели. Многоитерационный алгоритм, перестраивающий модель путем оценки энергетической функции, является наиболее точным алгоритмом упрощения геометрии.

Рассматривается стратегия организации ЗD-модели для сетевой передачи с переменным уровнем детализации. Рассмотрена возможность прогрессивной передачи модели, упрощенной различными алгоритмами. Структура прогрессивной сетки была предложена Хоупом (Норре Н. L). Наиболее известные алгоритмы связанные с организацией прогрессивной передачи разработаны Баджаем (Bajaj С), Паскучи (Pascucci V.), Зуангом (Zhuang G.), Швелденсом (Sweldens W.), Ли (U J.), Kyo (Kuo С). В завершающей части главы приведён сравнительный анализ рассмотренных алгоритмов. Среди рассмотренных направлений выбрано наиболее перспективное для сжатия инженерных 3D-моделей.

Во второй главе рассматриваются методы сжатия инженерных 3D-моделей с учетом специфики сжимаемых данных.

Рассмотрены специфические особенности инженерных ЗD-моделей:

• повторяющаяся геометрия (повторение фрагментов, деталей и узлов модели);

• геометрия, полученная при помощи стандартных операций: вытягивания, вращения, построения по конечному количеству сечений;

• большое количество плоскостей.

Для эффективного кодирования инженерных ЗD-моделей рассмотрен метод, основанный на распознавании повторяющейся геометрии. Рассматриваются алгоритмы распознавания повторяющихся фрагментов, объектов и узлов.

Рассмотрена структура хранения модели, состоящей из повторяющихся элементов.

Разработан новый метод сжатия без потерь инженерных ЗЭ-моделей, основанный на предположении, что множество V содержит подмножества вершин, лежащих в одной плоскости. Такие подмножества названы плоскими элементами и описываются следующим образом:

где М и А коэффициенты уравнения задающего плоскость. Положение вершины множества V2 в пространстве можно задать парой координат гх и г„. Третью координату гг вершины г можно получить из уравнения плоскости.

Если существуют такие V2 и V2, что V2 ПV2 ф 0, то получаем подмножество К1, вершины которого принадлежат прямой линии:

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

В случае расположения вершины в точке пересечения трех плоскостей: -

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

Для кодирования модели задается множество плоскостей. Вершина, не принадлежащая этим плоскостям, задается тройкой координат. Если вершина принадлежит одной или нескольким плоскостям, то одна или несколько координат заменятся указателями на плоскости. При восстановлении модели декартовы координаты таких вершин получим, решая системы линейных уравнений методом Гаусса.

Замена координаты на указатель дает экономию памяти, так как координата — это вещественное число, а указатель — целое. Выгодно группировать вершины, принадлежащие одной плоскости. Группой V2 назовем структуру данных, состоящую из заголовка, содержащего уравнение плоскости, и множества вершин, принадлежащих этой плоскости. Внутри такой группы вершина задается только двумя координатами без указателя на плоскость. Так же эффективно группировать вершины, принадлежащие одной прямой.

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

У2 = {ге + = 0},

(1)

(2)

(3)

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

Рис. 1. Общая блок-схема алгоритмов сжатия плоских элементов.

шить следующие задачи:

1. Поиск плоских элементов. На этом шаге необходимо найти максимальное число плоских элементов, содержащих более трёх вершин (для заданного множества Уо число плоских элементов конечно). От количества найденных на данном шаге плоских элементов напрямую зависит коэффициент компрессии. Множество найденных плоских элементов обозначим как IV2 = {У2,..., На этом шаге организуются группы V2,...,

2. Подбор сочетания плоских элементов. На данном шаге необходимо подобрать такие плоские элементы, кодирование которых даст максимальный коэффициент сжатия. При подборе учитывается пересечение плоских элементов. Результатом работы является множество IV* С IV3. Не вошедшие в него группы удаляют.

3. Для построения структуры сжатой модели находят все пересечения элементов множества ТУ2. Создаются вложенные группы V1 и Vго.

Наиболее сложным и ресурсоемким является шаг №1 — поиск плоских элементов. В диссертационной работе представлено два алгоритма реализации поиска плоских элементов: алгоритм перебора сочетаний и алгоритм плоских сечений.

Основная идея алгоритма перебора сочетаний состоит в генерации всех возможных для данного V«) множеств V2 таких, что |У2| > 3 (любые три вершины однозначно задают плоскость). Здесь || обозначает мощность множества.

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

1 Генерация индексов очередного сочетания й. »г. >з;

2 begin

3 Генерация уравнения + D, — 0,сведение Я, к единичному вектору;

4 Сравнение Л?« и Di с уже созданными группами множества W2;

5 Проверка всех вершин множества Vo на принадлежность к множеству V,2;

6 if |V?\ > 3 then W := W* U V,2;

7 end;_

Вычисления внутри цикла перебора сочетаний требуют 0(п — 3) времени, где п = |Vo|. Количество сочетаний по 3 элемента из п определяет, сколько раз эти • вычисления будут выполнены, т. е. общая временная сложность определяется следующим образом;

0{С3п(п- 3));

С"=М(т-к)Г СЛеА°ВаТеЛЬНО: °(зК^Гз)Т(г1-3>) ^

0(|п4-п3 + ^п2-6п)=>0(п4), (4)

т. е. быстродействие алгоритма падает прямо пропорционально 4-й степени п.

Алгоритм плоских сечений состоит в поиске подмножеств V2, заданных параллельными плоскостями с общим нормальным вектором Й. Первоначально выстраивается множество векторов N = {fit, • • •, Л»}. Затем для каждого & производится поиск подмножеств V2, заданных плоскостями, нормальными Я. В случае, если такие подмножества (содержащие более 3-х элементов) будут найдены, создается класс множеств Wj^ = {УД^,..., }. После m исследований множества Vo получим совокупность классов W2, являющуюся результатом работы алгоритма. Общую последовательность шагов алгоритма можно представить следующим образом:_

1 Генерация множества N;

2 for i <— 1 to m do begin

3 измерение расстояний элементов множества Vo до плоскости г& = 0;

4 поиск точек с равным расстоянием;

5 if точки найдены then генерация V^ ;

6 W3 <— IV2 и

7 end

8 Верификация групп множества W2;___

Для исследования множества Vo в направлении Л^ измеряются расстояния

от вершин модели до плоскости N,f = 0, затем массив расстояний D — = {di,..., d„} сортируется. Полученная диаграмма (см. рис. 2) анализируется на присутствие «плоских площадок» — подмножеств вершин, находящихся на равном расстоянии от плоскости tftr = 0. Разработаны два критерия отыскания

dt и

О 20 40 < <0 tt 100 120 140 I

Рис. 2. Левые края «плоских площадок», пунктир—диаграмма массива D = = {¿1,..., dn}.

«плоских площадок». Наиболее эффективным является поиск левых краев (см. рис. 2). После обнаружения вершины «плоских площадок» проверяются на принадлежность одному плоскому элементу. Таким образом отыскиваются все плоские элементы в направлении

Для эффективного поиска плоских элементов необходимо сгенерировать множество направлений N с заданным отклонением соседних элементов Actmax / Разработано несколько способов генерации множества N:

• Способ перебора сферических координат с заданым шагом состоит в переборе пар углов в и ф задающих вектор jtf, на сфере единичного радиуса Aamex в пределах:

Результат генерации множества N способом перебора сферических координат показан на рис. 3, а.

• Способ Монте-Карло состоит в генерации случайных пар чисел в и ф в пределах (5) (см. рис. 3, б);

• Способ перебора сферических координат, скорректированный коэффициентами Даме (см. рис. 3, в). В диссертационной работе представлен вывод коэффициентов Даме, расчет числа |N| для заданного Aamaz-

• Коррекция метода Монте-Карло при помощи коэффициентов Ламе. Для работы метода Монте-Карло с коэффициентами Ламе необходимо, чтобы распределение вероятности вдоль оси в происходило по закону cos в. Для реализации такого распределения вероятности генерируем пару случайных чисел вх и ву в диапазоне:

0уе[О,1], 9х 6 [0, тг/2] (6)

если ву ^ cos вх, то на данной итерации в = вх, если нет, то генерация случайных чисел повторяется до тех пор, пока условие не будет выполнено.

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

Для реализации метода организована полноценная структура данных для описания многогранника

Обработка элементов множества ^ в методе плоских сечений производится только при исследовании множества Уо в направлении Время исполнения этого цикла прямо пропорционально квадрату количества вершин п Следовательно, время выполнения алгоритма зависит от числа обрабатываемых вершин, как 0(п2) При больших п алгоритм перебора сочетаний значительно менее эффективен по времени исполнения

Для решения задачи подбора сочетания групп вводится функция оценки коэффициента сжатия

(?)

Разработан многоитерационный алгоритм, минимизирующий данную функцию, оценивая на каждой итерации ее изменение в зависимости от введения новых групп. В результате работы этого алгоритма класс множеств Ж содержит группы, необходимые для эффективного сжатия ЗD-модели.

Предложены способы сетевой передачи сжатой модели с постоянным уровнем детализации.

Рассмотрены способы передачи сжатой 3D-модели с переменным уровнем детализации: методом прогрессивной передачи бит и методом прогрессивной сетки.

Рис. 4. Главное окно программы сжатия.

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

1. Проверка предположения о существовании плоских элементов в инженерных 3D моделях.

2. Исследования алгоритма перебора сочетаний 3 Исследование алгоритма плоских сечений

а) сравнение сжатия плоских элементов, со сжатием дир для различных тестовых ЗО-моделей

«' | ———ДД ■ ■ --

• к « м 10 100 139 140 1М 110 хо»

число вершин

б) Кривая производительности для алгоритма перебора сочета ний и алгоритма плоских сечений 1 —алгоритм плоских сечений, 2—алгоритм перебора сочетаний

Рис. 5. Основные результаты экспериментальных исследований.

4. Испытания метода сжатия с помощью поиска плоских элементов на инженерных моделях различного типа и уровня детализации.

С целью проверки эффективности предлагаемого метода были исполь3D-ваны тестовые 3D-модели 11-ти различных типов, различающиеся формой и уровнем детализации. Подготовленная группа моделей анализировалась при помощи алгоритма перебора сочетаний (для низкодетализированных моделей) и алгоритма плоских сечений. Кроме того, эксперименты были проведены на специально подготовленных тестовых моделях и на реальном конструкторском проекте ДСЕ-2 на базе ФГУП «Научное конструкторско-технологическое бюро „Парсек" Минобра3Dвания России»

Для сравнения данные модели сжимались при помощи архиватора с открытым кодом gzip, реализующего алгоритм сжатия данных без потерь Зива-Лемпела (Ь/77). Современные программы архивирования реализуют в основном модификации этого алгоритма и дают схожие результаты. Диаграмма коэффициента сжатия показана на рис. 5, а. Из результатов экспериментов следует, что предлагаемый алгоритм сжатия без потерь более эффективен, чем алгоритмы общего назначения. Коэффициент сжатия достигает в среднем 30-40%.

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

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

Сравнивая кривые производительности, получаем, что для низкодетализи-рованных моделей эти алгоритмы сжатия мало отличаются друг от друга. Для высокодетализированных моделей алгоритм перебора сочетаний практически не применим, так как время его работы растет, как функция четвертой степени от числа вершин. Более эффективным является алгоритм плоских сечений. Время работы этого алгоритма возрастает значительно медленнее, чем время работы алгоритма перебора сочетаний, что делает его более применимым для сжатия высокодетализированных инженерных объектов.

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

• времени работы алгоритма;

• коэффициента сжатия модели;

• числа найденных плоских элементов до верификации;

• числа найденных плоских элементов после верификации;

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

• генерация множества N методом Монте-Карло дает большее число найденных плоских элементов;

• коррекция коэффициентами Ламе увеличивает количество найденных плоских элементов;

• при коррекции коэффициентами Ламе при поиске плоских элементов возникает меньше ошибок, что уменьшает время, затрачиваемое на верификацию.

Введение коэффициентов Ламе во всех случаях повышает эффективность сжатия данных.

В заключении сформулированы следующие основные результаты работы:

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

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

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

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

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

6. Проведена серия экспериментов, получены данные, подтверждающие эффективность применения предложенного способа. Проведены испытания алгоритмов над реальными объектами инженерного проектирования.

В приложениях представлены акты о внедрении результатов работы.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ:

1. Федотов Р. В. Алгоритмы оптимизации фасетчатых моделей и методы их сетевой передачи // Вычислительные методы и программирование. — Издательство Московского университета, Научно-исследовательский вычислительный центр МГУ — 2003. — Т. 4, № 2. — С. 47 - 57.

2. Федотов Р. В. Методы сетевой передачи, оптимизированных фасетчатых моделей. // Инфокоммуникационные технологии. — ПГАТИ,— Самара — 2003 Т. 3, — С. 34-40.

3. Федотов Р. В., Федотов Г. В. Разработка программы визуализации компьютерных моделей // Повышение эффективности работы железнодорожного транспорта. — СамИИТ,— Самара— 2000. — Т. 2, № 20. — С. 169-170.

4. Федотов Р. В. Упаковка трехмерных моделей методом ра3Биения множестве точек, на подмножества с ограничивающим условием // Тезисы докладов X Российская НК / ПГАТИ. — Самара: 2003. — март. — С. 137.

5. Федотов Р. В. Сжатие инженерных 3Б-моделей при помощи автоматического поиска плоских элементов, для минимизации сетевого трафика // Тезисы докладов XI Российская НК / ПГАТИ. — Самара: 2004. — февраль. — С. 227.

6. Федотов Р. В., Кораблин М. А. Разработка методов и средств оптимизации формата угш1 для исполь3Бвания в сети интернет // Тезисы докладов 6-й всероссийской НТК / РГРТА. — Рязань: 2001. — С. 154.

Подписано в печать 04.03.04 Формат 60х84'/ю Бумага писчая № 1 Гарнитура Тайме Печать оперативная Усл. печ. л. 0,87 Физ. печ. л. 0,94 Уч-изд. л. 0,48 Тираж! 00 экз.

Типография государственного обра3Бвательного учреждения высшего профессионального сбраЮвания «Поволжская государственная академия телекоммуникаций и информатики» 443010, г. Самара, ул. Л. Толстого, 23. Тел./факс (8462) 39-11-11,39-11-81

Введение

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 Исследование сечений множества Vo в направлении iVj.

3.3.2 Генерация множеств N с заданным отклонением соседних элементов.

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.

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

Наиболее распространенный способ описания объемной модели — представление ее в виде множества смежных треугольных граней. Этот способ описания поддерживается большинством Интернет-ориентированных форматов.

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

Алгоритмы такого кодирования, рассчитанные на сжатие данных любого типа [1—3], широко используются, но имеют вполне определенный предел сжатия. Наиболее реальным развитием методов сжатия представляется способ, основанный на анализе геометрии модели [4—10]. При этом возможен комбинированный способ, последовательно решающий первую и вторую задачи в рамках требуемой точности. В связи с вышеизложенным актуальность предлагаемых к рассмотрению задач заключается в разработке и реализации методов сжатия, основанных на анализе геометрии трехмерных моделей без потери точности.

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

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

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

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

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

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

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

Разработан алгоритм подбора сочетаний групп вершин для максимизации коэффициента сжатия.

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

Предложены способы сетевой передачи сжатой модели.

Практическая ценность и реализация: заключается в:

• разработке эффективной технологии сжатия и сетевой передачи сжатых инженерных ЗБ-моделей.

• разработке способа внедрения предлагаемой технологии сжатия в существующие форматы.

• разработке программного обеспечения, реализующего алгоритм перебора сочетаний, алгоритм плоских сечений, алгоритм подбора сочетаний групп вершин.

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

Апробация результатов работы и публикации. Основные результаты по теме диссертационного исследования докладывались на X и XI Всероссийских научных конференциях ПГАТИ (Самара, 2003, 2004 г., соответственно), 6-й Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и образовании» РГРТА (Рязань, 2001), IV Международной школе-семинаре БИКАМП'ОЗ (ГУАП, Санкт-Петербург, 2003 г.)

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

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

Основные результаты исследования:

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

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

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

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

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

6. Проведена серия экспериментов, получены данные, подтверждающие эффективность применения предложенного способа. Проведены испытания алгоритмов над реальными объектами инженерного проектирования.

Заключение

1. Huffman D. A. A method for the construction of minimum redundancy codes. // 1.stitute of Electrical and Radio Engineers 40,9(Sept.). — 1952. — Pp. 1098-1101.

2. Langdon G.f Rissanen J. Compression of black-white images with arithmetic coding. // IEEE Trans.Commun.COM. — № 29. — 1981. — Jun. — C. 858-867.

3. Ziv J., Lempel A. Compression of individual sequences via variable-rate coding. // IEEE Trans.Inf.Theory IT-24(5. — No. 24. — 1978. — Sept. — Pp. 530-536.

4. Bajaj C., Pascucci V., Zhuang G. Compression and coding of large CAD models: Ticam: The University of Texas at Austin, 1998.

5. Isenburg M., Snoeyink J. Coding polygon meshes as compressable ASCII // 3DPVT '2002 / University of North Carolina at Chapel Hill and INRIA Sophia-Antipolis. — 2002.

6. Kapoor N. S. Geometry based connectivity compression of triangular meshes. — 2000.

7. Isenburg M., Snoeyink J. Coding with ASCII: compact, yet text-based 3D content // International Symposium on 3D Data Processing Visualization and Transmission. — 2002. — Pp. 609 — 616.

8. Khodakovsky A., Alliez P., Desbrun M„ Schroeder P. Near-optimal connectivity encoding of 2-manifold polygon meshes. — 2001.

9. King D., Rossignac J., Szymczak A. Connectivity compression for irregular quadrilateral meshes: GVU TR-99-36: Georgia Tech, 1999.

10. Taubin G., Horn W. et al. Geometry coding and VRML // IEEE. — Vol. 86. — 1998. — June. — Pp. 1228-1243.

11. Andbjar C. Geometry simplification.— 1999. — February.

12. Bajaj C. L., Pascucci V., Zhuang G. Single resolution compression of arr bitrary triangular meshes with properties // Data Compression Conference. — 1999. — Pp. 247-256.

13. Hoppe H., DeRose T. et al. Mesh optimization // Computer Graphics. — 1993. — Vol. 27, no. Annual Conference Series. — Pp. 19-26.

14. Hinker P., Hansen C. Geometric optimization // Proc. Visualization '93. — San Jose, С A: 1993. — October. — Pp. 189-195.

15. Шикин E. В., Боресков А. В. Компьютерная графика. Полигональные модели. — М. Диалог-МИФИ, 2000.

16. Isenburg М., Alliez P. Compressing hexahedral volume meshes // Pacific Graphics '2002 / University of North Carolina at Chapel Hill and INRLA Sophia-Antipolis. — 2002.

17. And'ujar C. Octree-based Simplification of Polyhedral Solids: Cs dept / Universitat Polit'ecnica de Catalunya. — Barcelona, Spain, 1999.

18. Isenburg M. Compressing polygon mesh connectivity with degree duality prediction // Graphics Interface '2002 / University of North Carolina at Chapel Hill. — 2002.

19. Saupe D., KuskaJ. Compression of isosurfaces for structured volumes: Tech. rep. — 04109 Leipzig, Germany: University of Leipzig, Computer Science Institute Augustusplatz, 2001. — November.

20. Searching triangle strips guided by simplification criterion // WSCG 2001 Conference Proceedings / Ed. by V. Skala. — 2001.

21. Xiang, Held, Mitchell. Fast and effective stripification of polygonal surface models (short) // SODA: ACM-SLAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms). — 1999.

22. Carey R., Bell G., Marrin C. — The Virtual Reality Modeling Language. — ISO/IEC DIS 14772-1, 1997. — April.

23. Jackie Neider T. D., Woo M. — OpenGL Programming Guide — The Official Guide to Learning OpenGL, Version 1.1.— Addison-Wesley, Reading, MA, USA, 1997.

24. Kronrod В., Gotsman C. Optimized triangle mesh compression using prediction trees // Pacific Graphics '2000. — 2000.

25. NganA. Simplification of 3D meshes. — 2000.

26. Gumhold S., Strauer W. Real time compression of triangle mesh connectivity // Computer Graphics. — 1998. — Vol. 32, no. Annual Conference Series. — Pp. 133— 140.

27. Schroeder W. J., Zarge J. A., Lorensen W. E. Decimation of triangle meshes // Computer Graphics. — 1992. — Vol. 26, no. 2. — Pp. 65 — 70.

28. Szymczak A., Rossignac J. Grow & fold: Compression of tetrahedral meshes: Tech. Rep. SM99-021. — Atlanta USA: School of Mathematics Georgia Institute of Technology and Graphics, Visualization & Usability Center College of Computing, 1999. —January.

29. Taubin G., Rossignac J. Geometric compression through topological surgery // ACM Transactions on Graphics. — 1998. — Vol. 17, no. 2. — Pp. 84-115.

30. Федотов P. В., Кораблин M. А. Разработка методов и средств опти-мизацииформата vrml для использования в сети интернет // Тезисы докладов 6-й всероссийской НТК / РГРТА.— Рязань: 2001.— С. 154.

31. Rossignac J. Geometric simplification and compression // SIG-GRAPH'97. — 1997.

32. Rossignac J., Borrel P. Multi-resolution 3d approximations for rendering complex scenes // Geometric Modeling in Computer Graphics. — Springer Verlag, 1993. June-July. — Pp. 455-465.

33. LowK. L., Tan T. S. Model simplification using vertex-clustering.

34. Hoppe H. Progressive meshes // Computer Graphics.— 1996.— Vol. 30, no. Annual Conference Series. — Pp. 99— 108.

35. Федотов P. В., Федотов Г. В. Разработка программы визуализации компьютерных моделей // Повышение эффективности работы железнодорожного транспорта.— 2000.— Т. 2, № 20.— С. 169 — 170.

36. Evans F, Skiena S. S., Varshney A. Optimizing triangle strips for fast rendering // IEEE Visualization '96 / Ed. by R. Yagel, G. M. Nielson. — 1996. —Pp. 319-326.

37. Bajaj C. L., Ihm /., Park S. Compression-based 3D texture mapping for real-time rendering // Graphical Models. — 2000. — Vol. 62, no. 6. — Pp. 391-410.

38. Turk G. Re-tiling polygonal surfaces // Computer Graphics. — 1992. — Vol. 26, no. 2. — Pp. 55 64.

39. SzymczakA., RossignacJ., King D. Piecewise regular meshes: Construction and compression: GVU GA 30332. — Atlanta USA: Georgia Tech, 2002. — February.

40. Yuen P., Khalili N., Mokhtarian F. Curvature estimation on smoothed 3d meshes: Tech. rep.: Centre for Vision, Speech and Signal Processing School of Electronic Engineering, Information Technology and Mathematics University of Surrey,, 1999.

41. Boehm W.t Prautzsch H. Geometric fundamentals.

42. JoeW., Tony D. Barycentric coordinates for convex polytopes.— 1993.

43. Golub G., Van Loan C. Matrix Computations. — 2nd edition. — University Press, 1989.

44. Du W. A Study of Several Specific Secure Two-party Computation Problems: Ph.D. thesis / Purdue University. — West Lafayette, Indiana, 2001.

45. L. Bajaj С., Pascucci V., Zhuang G. Progressive compression and transmission of arbitrary triangular meshes // IEEE Visualization '99 / Ed. by D. Ebert, M. Gross, B. Hamann. — San Francisco: 1999. — Pp. 307 — 316.

46. Taubin G. 3D geometry compression and progressive transmission // EUROGRAPHICS 99. — 1999.

47. Hoppe H. Efficient implementation of progressive meshes // Computers and Graphics. — 1998. — Vol. 22, no. 1. — Pp. 27 36.

48. Khodakovsky A., Schroder P., Sweldens W. Progressive geometry compression // Siggraph 2000, Computer Graphics Proceedings / Ed. by K. Akeley. — ACM Press / ACM SIGGRAPH / Addison Wesley Longman, 2000. — Pp. 271-278.

49. Li J., Li J., Кио С. C. J. Progressive compression of 3D graphic models // International Conference on Multimedia Computing and Systems. — 1997. —Pp. 135-142.

50. Pajarola R.f Rossignac J. Compressed progressive meshes // IEEE Transactions on Visualization and Computer Graphics. — 2000. — /. — Vol. 6, no. 1. —Pp. 79-93.

51. Pajarola R. В., Rossignac J., Szymczak A. Implant sprays: Compression of progressive tetrahedral mesh connectivity// IEEE Visualization '99 / Ed. by D. Ebert, M. Gross, B. Hamann. — San Francisco: 1999. — Pp. 299-306.

52. Popovic J., Hoppe H. Progressive simplicial complexes // SIGGRAPH.— 1997. —Pp. 217-224.

53. Cohen-Or D., Levin D., Remez O. Progressive compression of arbitrary triangular meshes // IEEE Visualization '99 / Ed. by D. Ebert, M. Gross, B. Hamann. — San Francisco: 1999. — Pp. 67 — 72.

54. Progressive forest split compression / G. Taubin, A. Gueziec, W. Horn, F. Lazarus // Computer Graphics. — 1998. — Vol. 32, no. Annual Conference Series. — Pp. 123— 132.

55. VarshneyA. A hierarchy of techniques for simplifying polygonal models // SIGGRAPH '97 Course Notes CD-ROM, Course 25: Multiresolu-tion Surface Modeling. ACM SIGGRAPH. — 1997. — August.

56. Захаров А. А., Брагин П. А. Разработка методов изменения геометрической сложности графических объектов для систем генерации визуальной обстановки // Методы и устройства передачи и обработки информации. — 2002. — Т. 2. — С. 88-92.

57. Multiresolution analysis of arbitrary meshes / M. Eck, T. DeRose, T. Duchamp et al. // Computer Graphics. — 1995. — Vol. 29, no. Annual Conference Series. — Pp. 173—182.

58. Shamir A., Bajaj C. L., Pascucci V. Multi-resolution dynamic meshes with arbitrary deformations // IEEE Visualization.— 2000.— Pp. 423-430.

59. Федотов Р. В. Алгоритмы оптимизации фасетчатых моделей и методы их сетевой передачи // Вычислительные методы и программирование — Издательство Московского университета, Научно-исследовательсуий вычислительный центр МГУ.— 2003.— Т. 4, №2, —С. 47-57.

60. Федотов Р. В. Методы сетевой передачи, оптимизированных фасетчатых моделей. // Инфокоммуникационные технологии. — 2003.

61. Захаров А. А., Масанов А. Н. Синтез изображений протяженных участов местности // Методы и устройства передачи и обработки информации. — 2002. — Т. 2. — С. 98-102.

62. Barequet, Sharir. Partial surface and volume matching in three dimensions // IEEETPAMI: IEEE Transactions on Pattern Analysis and Machine Intelligence.— 1997. —Vol. 19.

63. Dorai C., Jain A. K. COSMOS a representation scheme for 3d free-form objects // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1997. — Vol. 19, no. 10. — Pp. 1115 - 1130.

64. Osada R., Funkhouser T. et al. Matching 3d models with shape distributions // International Conference on Shape Modelling and Applications (SMI2001). — 2001. — May. — Pp. 154- 166.

65. Novotni M., Klein R. A geometric approach to 3d object comparison // International Conference on Shape Modelling and Applications (SMI2001). — 2001. —May. — Pp. 167-175.

66. Реппес X., Ayache N. A geometric algorithm to find small but highly similar 3D substructures in proteins // Bioinformatics.— 1998.— No. 14.—Pp. 516-522.

67. Automated discovery of active motifs in three dimensional molecules // Knowledge Discovery and Data Mining.— 1997.— Pp. 89-95.

68. Федотов P. В. Упаковка трёхмерных моделей методом разбиения множестве точек, на подмножества с ограничивающим условием // Тезисы докладов X Российская НК / ПГАТИ. — Самара: 2003. —март. — С. 137.

69. Федотов Р. В. Сжатие инженерных ЗО-моделей при помощи автоматического поиска плоских элементов, для минимизации сетевого трафика // Тезисы докладов XI Российская НК / ПГАТИ. — Самара: 2004.

70. Степанов Н. Н. Сферическая тригонометрия.— 2 изд.— Л.-М., 1948.

71. Lamme С. Lecons sur Les Coordonnees curvilignes et leurs diverses applications. — P., 1859.

72. Лаптев Г. Ф. Элементы векторного исчисления. — М., 1975.

73. Шикин Е. В., Боресков А. В. Компьютерная графика, динамика реалистические изображения. — М. Диалог-МИФИ, 1995.

74. Alliez P., Desbrun М. Valence-driven connectivity encoding for 3D meshes // EG 2001 Proceedings / Ed. by A. Chalmers, T.-M. Rhyne. — Blackwell Publishing, 2001. — Vol. 20(3). — Pp. 480-489.

75. Howard P. G. The design and analysis of efficient lossless data compression systems: Tech. Rep. CS-93-28: 1993.

76. Zhuang G. Compression and Progressive Transmission of Three-Dimensional Models: Ph.D. thesis / Purdue University. — 1998.

77. Jiankun L., JayKuo C. Embedded coding of mesh geometry: Tech. rep.: ISO/IEC JTC1/SC29/WG11 MPEG98/M3325, 1998. —March.

78. Andersson O., Armstrong P., othes. — Scalable Vector Graphics (SVG) 1.1 Specification. — W3C, 2003. — January.

79. P. D. — GZIP file format specification version 4.3. — Aladdin Enterprises, 1996. —May.