Содержание к диссертации
Введение
1 Краткий обзор состояния вопроса и постановка задач исследования 9
1.1 Алгоритмы снижения числа элементов описывающих ЗБ-модель 9
1.2 Оптимизация модели с учетом передачи по сети 27
1.3 Задачи исследования 34
2 Сжатие инженерных моделей с учетом специфики сжимаемыхданных 35
2.1 Специфика инженерных ЗБ-моделей 36
2.2 Распознавание и кодирование повторяющихся объектов 40
2.3 Метод сжатия полигональных инженерных ЗБ-моделей с помощью автоматического поиска плоских элементов . 46
2.4 Выводы по главе 2 51
3 Реализация алгоритмов автоматического поиска плоских элементов 53
3.1 Общая схема алгоритмов поиска плоских элементов 53
3.2 Алгоритм перебора сочетаний 54
3.3 Алгоритм плоских сечений 59
3.3.1 Исследование сечений множества в направлении 61
3.3.2 Генерация множеств N с заданным отклонением соседних элементов 66
3.3.3 Оценка быстродействия и ресурсоемкое алгоритма 77
3.4 Эффективное кодирование найденных групп 78
3.4.1 Оценка эффективности введения группы 80
3.4.2 Подбор оптимального сочетания множеств для максимизации коэффициента сжатия 81
3.5 Сетевая передача 84
3.5.1 Оптимизированная передача с постоянным уровнем детализации 84
3.5.2 Прогрессивная передача модели 86
3.6 Выводы по главе 3 91
Экспериментальные исследования 92
4.1 Задачи экспериментальных исследований 92
4.2 Разработанное программное обеспечение 93
4.3 Экспериментальные подтверждения эффективности метода сжатия с помощью поиска плоских элементов 96
4.4 Экспериментальные данные о производительности алгоритмов поиска плоских элементов 106
4.5 Результаты работы алгоритма плоских сечений. Сравнение данных о различных способах генерации множества N 107
4.5.1 Анализ зависимости коэффициента сжатия от числа итераций 109
4.5.2 Анализ Зависимости числа найденных плоских элементов от числа итераций 112
4.5.3 Анализ зависимости коэффициента сжатия от числа найденных плоских элементов 112
4.6 Выводы по главе 4 118
Заключение 119
Литература 120
Приложения 130
- Алгоритмы снижения числа элементов описывающих ЗБ-модель
- Распознавание и кодирование повторяющихся объектов
- Генерация множеств N с заданным отклонением соседних элементов
- Экспериментальные подтверждения эффективности метода сжатия с помощью поиска плоских элементов
Введение к работе
Актуальность темы.
Коллективная работа над проектами в компьютерной сети становится сегодня основной технологией инженерного проектирования в различных предметных областях. При этом специфика информационного обмена, связанного с детализацией, комплектованием и инкапсулированием многоуровневых проектных решений требует высокой реактивности и надежности системы «клиент-сервер». В этой связи снижение времени информационного обмена (времени ответа) без потерь информации является основной задачей повышения эффективности многопользовательской работы в сети.
Современные системы автоматизированного инженерного проектирования реализуются в компьютерных сетях, объединяющих различные группы специалистов. Обработка высокодетализированных объектов в таких системах связана с проблемами хранения и передачи данных внутри сети. При проектировании сложных систем растёт занимаемый моделями объем памяти, падает производительность отдельных рабочих мест, повышаются требования к пропускной способности каналов и объему банков информации. Публикации трехмерных объектов в глобальной сети еще более усложняет процесс проектирования.
Наиболее распространенный способ описания объемной модели —представление ее в виде множества смежных треугольных граней. Этот способ описания поддерживается большинством Интернет-ориентированных форматов.
Существенное снижение сетевого трафика при передаче трехмерной модели внутри локальной или глобальной сети возможно через снижение числа описывающих модель примитивов и повышение эффективности кодирования (сжатия) модели. Решение первой задачи связано с потерей точности геометрии модели. Для второй задачи решение связано с отысканием технологии, позволяющей структурировать данные модели для понижения объема передаваемых данных.
Алгоритмы такого кодирования, рассчитанные на сжатие данных любого типа, широко используются, но имеют вполне определенный предел сжатия. Наиболее реальным развитием методов сжатия представляется способ, основанный на анализе геометрии модели. При этом возможен комбинированный способ, последовательно решающий первую и вторую задачи в рамках требуемой точности. В связи с вышеизложенным актуальность предлагаемых к рассмотрению задач заключается в разработке и реализации методов сжатия, основанных на анализе геометрии трёхмерных моделей, без потери точности.
Цель работы заключается в разработке и исследовании алгоритмов сжатия трёхмерных моделей (ЗО-моделей), основанных на анализе геометрических свойств и допускающих восстановление без потери точности представленных объектов.
РОС НАЦИОНАЛЬНАЯ і 6ИЛК0ТЕКА |
тз&\
CTlerepS
О»' кя^
Метода исследования. При решении указанных задач используются методы трёхмерного геометрического моделирования, линейной алгебры, аналитической геометрии, теории сложности алгоритмов, объектно-ориентированного программирования.
Научная новизна работы заключается в следующем:
Выявлен ряд специфических особенностей характерныхдля инженерных ЗО-моделей.
Предложен новый способ кодирования ЗО-моделей, учитывающий специфику геометрии модели.
Разработаны два принципиально различных алгоритма, реализующих предложенный способ кодирования: алгоритм перебора сочетаний и алгоритм плоских сечений.
Для алгоритма плоских сечений разработано три способа генерации множества направлений, исследована их сравнительная эффективность.
Разработан алгоритм подбора сочетаний групп вершин для максимизации коэффициента сжатия.
Предложены способы сетевой передачи сжатой модели.
Практическая ценность и реализация заключается в:
разработке эффективной технологии сжатия и сетевой передачи сжатых инженерных ЗО-моделей.
разработке способа внедрения предлагаемой технологии сжатия в существующие форматы.
разработке программного обеспечения, реализующего алгоритм перебора сочетаний, алгоритм плоских сечений, алгоритм подбора сочетаний групп вершин.
Апробация результатов работы и публикации. Основные результаты по
теме диссертационного исследования докладывались на X и XI Всероссийских научных конференциях ПГАТИ (Самара, 2003, 2004 г., соответственно), 6-й Всероссийской научно-технической конференции «Новые информационные технологии в научных исследованиях и образовании» РГРТА (Рязань, 2001), IV Международной школе-семинаре БИКАМП'ОЗ (ГУАП, Санкт-Петербург, 2003
г.)
Основные научные и прикладные результаты опубликованы в 3 статьях в периодических научных изданиях, и в 3 публикациях в форме тезисов докладов на российских и международных конференциях и семинарах.
Объем и структура работы. Диссертация состоит из введения, 4 глав, спис-калитературы, включающего 72 наименования, и приложений. Основная часть работы содержит ПО страниц, включая 67 рисунков и 5 таблиц.
Алгоритмы снижения числа элементов описывающих ЗБ-модель
Полигональная ЗБ-модель представляет из себя один или несколько многогранников, состоящих из треугольных граней [11 — 15]. Модель задают множеством вершин V = {fi,...,fn}, f.\ є Ш? и г = (rx,ry,rz) и множеством граней и ребер К, описывающим топологию модели. Ребро, соединяющее вершины fi и fj, задается парой чисел {г, j}, где i,j Є {1,..., п}. Треугольная грань с вершинами fit fj, г& задается тройкой чисел {г, j, к}, где i, j, к {1,..., п}. Обозначим модель, заданную множествами V и К, как М(К, К). Модель до сжатия обозначим как M0(Vo, KQ), после сжатия MC(VC, Кс). Существуют и другие способы описания трехмерной геометрии [16,17], но спектр их применения значительно ниже, по сравнению с полигональным способом задания.
Уменьшение числа обрабатываемых граней или описание их с помощью более сложных примитивов широко используется при кодировании смежных граней. Грань модели во множестве К задается тройкой чисел {i,j, к], являющимися ссылками на вершины fit fj, fk. Учитывая тот факт, что модель состоит из смежных граней, были разработаны способы эффективного кодирования граней [4— 10,18 — 21]. Основная идея такого кодирования смежных граней заключается в кодировании лент и вееров граней модели (см. рис. 1.1, а). Обе конструкции кодируются простой последовательностью вершин, в случае ленты грани образуются «зигзагом», в случае веера вокруг центральной вершины. Для кодирования смешанной ленты (см. рис. 1.1, б) для каждой вершины вводится бит операции. Для ленты бит равен О, для веера 1. Обычно модель невозможно описать при помощи одной ленты. При кодировании топологических элементов таким методом организуется дерево, состоящее из отдельных смешанных лент.
Такой способ представления широко используется в сетевых форматах [22], так как при передаче очередной вершины автоматически восстанавливается треугольная грань. Системы построения изображения реального времени используют примитив, описывающий ленту граней. В стандарте openGL [23] существует такой примитив. Это связано с упрощением закраски граней, организованных таким способом.
Уменьшение числа вершин (ребер, граней), описывающих модель (упрощение геометрии модели), приводит к повышению быстродействия алгоритмов просчета изображения, упрощает манипуляции с моделью и сокращает используемую память и, как следствие, трафик при сетевом доступе [24 — 30]. На выходе алгоритма упрощения геометрии имеем множества Ус , Кс. Множество Ус может являться подмножеством или иметь с ним область пересечения в зависимости от того, перестраивает ли алгоритм модель или просто упрощает, удаляя вершины менее всего влияющие на геометрию по заданным параметрам.
Наиболее быстрым алгоритмом упрощения геометрии является алгоритм кластеризации вершин [31 — 34]. Метод состоит в объединении вершин, находящихся в одном кластере пространства, в одну. Кластеры представляют собой трехмерную сетку, то есть координаты вершин фактически округляются с заданной точностью, а при совпадении нескольких вершин, после округления, вершины заменяются одной. Все ссылки множества К на коллапсируемые вершины заменяются ссылками на новую вершину (см. рис. 1.2). Большим преимуществом данного метода является его простота и быстродействие, что дает возможность использовать его в режиме реального времени [35]. Основным минусом является потеря первоначальной топологии объекта, это может привести к серьезным ошибкам, поэтому метод не может быть универсальным. Основной областью применения являются задачи связанные с визуализацией в режиме реального времени [34,36,37]. Более точно передает топологию модели алгоритм прореживания вершин предложенный William J. Schroeder, Jonathan Zarge, and William Lorensen [27]. Это многопроходный алгоритм, суть которого состоит в удалении на каждом проходе, вершин, выбранных по заданному критерию. Для сохранения топологии модели и минимизации повреждения формы при упрощении геометрии, все вершины модели делят на пять а) Простая — вершина, окруженная полным кругом граней, и каж дое ребро, содержащее эту вершину, граничит с двумя гранями; б) Комплексная — вершина, окруженная полным кольцом граней, но содержащая ребро, не граничащее с двумя гранями или не окруженная полным кругом граней; в) Пограничная — вершина, находящаяся на границе объекта, окру женная полукругом граней. г) Если двугранный угол, содержащий простую вершину велик или ребра, содержащие вершину, имеют разрыв дополнительных скалярных параметров (например, разрыв нормали), то такая вершина обозначается как внутри реберная; д) Если внутри реберная вершина содержит более двух ребер с разрывом или с большими двугранными углами, то вершина классифицируется как угловая. При выполнении прохода алгоритма находятся вершины на удаление, при этом критерием на удаление является величина d — расстояние от вершины до усредненной плоскости — максимально близкой к соседним вершинам (см. рис. 1.4).
Распознавание и кодирование повторяющихся объектов
Основная идея предлагаемого способа кодирования ЗЭ-моделей заключается в группировке вершин принадлежащих подмножествам V2, Vі, V0. Вершины не принадлежащие этим множествам задаются тройкой вещественных координат. Вершины внутри группы V2 кодируются двойкой вещественных чисел. Заголовок группы V2 состоит из коэффициентов уравнения плоскости.
Группа V2j кодируется как подгруппа V2. Заголовок такой группы состоит из указателя на заголовок группы V2. Вершины кодируются одним вещественным числом. Вершины принадлежащие подмножеству Vjjk кодируются внутри группы V2 двумя указателями на заголовки групп Vf и V.
Для декодирования модели декартовы координаты сгруппированных вершин получают решая системы линейных уравнений, задающих соответствующие подмножества. Декодирование модели не требует больших временных затрат. Время работы алгоритма декодирования зависит от числа вершин п как 0(п).
Современные системы обработки 3D почти всегда являются комплексными системами, реализующими множество алгоритмов для обработки модели. Это относится и к операции кодирования модели, поэтому важно, чтобы метод эффективно взаимодействовал с уже существующими алгоритмами.
Можно предположить, что метод сжатия плоских элементов будет хуже компоноваться с алгоритмами, перестраивающими множество V. Эти методы сохраняют топологию, описанную множеством К, однако, структура V при этом может серьезно измениться. К таким методам относится метод минимизации энергетической функции [13] и метод перестройки полигональной сетки [38]. На рис. 2.7, а приведён результат операции вращения, описанной в разделе 2.1. Очевидно, что тело имеет ряд горизонтальных и осевых сечений, являющимися плоскими элементами, то есть данное тело эффективно сжимается методом сжатия плоских элементов. После оптимизации методом минимизации энергетической функции получаем результат (см. рис. 2.7, б). Топология модели и точность передачи поверхности прекрасно сохранилась, уменьшилось число вершин и граней, однако, структура множества V коренным образом изменилась, что делает модель плохо сжимаемой методом сжатия плоских элементов.
Более примитивные методы упрощения геометрии не перестраивают множество V, а лишь сокращают его, основываясь на каком-либо критерии. При таком подходе структура V сохраняется и совместное использование с такими алгоритмами наиболее эффективно.
Представителями таких методов является метод прореживания полигональной сетки [27] и метод кластеризации [31,32]. Последний метод относиться к не точным, так как не сохраняет первоначальную топологию модели.
Метод сжатия плоских элементов относится к классу сжатия без потерь, поэтому предварительное упрощение геометрии не должно серьезно изменить геометрию модели. На практике упрощению должны подвергаться фрагменты с излишним кодированием (см. рис. 2.8, а). Такие результаты можно получить методом прореживания вершин при d = Ad, где Ad погрешность вычислений для данной модели. После таком упрощении из Vo будут удалены только вершины, влияющие на геометрию модели в рамках погрешности вычислений (см. рис. 2.8, б).
Генерация множеств N с заданным отклонением соседних элементов
Рассматриваемый метод генерации множества N был разработан как алгоритм разбиения сферы на конечное количество треугольных граней для представления в виде фасетчатой модели. Суть метода заключается в делении каждой треугольной грани правильного многогранника, спроецированной на описанную сферу, на четыре треугольные грани (см. рис. 3.12). В данном случае корректно говорить о де го радиуса. Стороны треугольника при делении треугольника делятся пополам, что должно обеспечивать равенство всех вновь образованных ребер (т.е постоянство угла Аатах), однако, так как делимый треугольник находится на сфере, то утверждать, что ADEF = AADF = = ADBE = AEFC нельзя.
При делении равностороннего эилерового треугольника на четыре треугольника с помощью деления пополам его сторон получим один равносторонний треугольник и три равнобедренных
Доказательство: Построим плоский ААВС и пирамиду АВСО с основанием ABC и вершиной в центре сферы О (см. рис. 3.13). Спроецируем ADEF на плоскость треугольника ААВС, обозначим полученный плоский треугольник как AD E F . OB = ОС = OB = R, следовательно, треугольники ААОС, АСОВ и ААОВ равнобедренные, а их биссектрисы F O, D O, Е О делят противолежащие стороны пополам, то есть AF = F C, AD = D B, BE = Е С. Из равенства сторон следует равенство треугольников ADE F = AAD F = AD BE = AE F C по двум сторонам и углу между ними. Из построения: СЕ = Z.COE, FE = /.FOE. Треугольники AOF C и AOE C равны по трём сторонам. СЕ = E F и сторона Е О общая для АСЕ О и AOF E , /F E O 90, так как AOF E равнобедренный, следовательно, АОЕ С AOF E , из неравенства треугольников следует неравенство углов /F OE и /.СОЕ . ACFE = AADF = ABED и они равнобедренные, ADEF -равносторонний, что и требовалось доказать.
Следует заметить, что чем меньший размер имел делимый треугольник, тем более совпадающими будут получаться треугольники в результате деления.
Для генерации множества N методом деления граней правильного многогранника подходят только многогранники с треугольными гранями. Для трехмерного пространства их три: тетраэдр, икосаэдр, октаэдр. Алгоритм деления носит многоитерационный характер. Способы построения правильных многогранников описаны в [77]. Первона-чально выстраивается правильный многогранник. Затем делят грани многогранника до получения заданной точности. Наиболее приемлемым для способа является икосаэдр, так как его грани имеют минимальную длину. Преимущества икосаэдра состоит также в том, что из каждой его вершины выходит пять ребер, а при делении образуются шестиреберные вершины, таким образом первоначальные 12 вершин будут отличаться от окружающих вершин (см. рис. 3.14). Для октаэдра число ребер выходящих из вершин равно четырем, а для тетраэдра трем. Следовательно, погрешность Аатах при делении граней икосаэдра будет более постоянной, чем у других правильных многогранников.
Такой способ получения множества N дает наиболее точный результат. Погрешность Аатах колеблется незначительно и ощутимо только в окрестностях вершин первоначального многогранника, но такой способ имеет ряд существенных недостатков. Изменение числа т будет носить ступенчатый характер и изменять его можно будет только задавая число итераций.
Для реализации метода необходимо организовать полноценную структуру данных для описания многогранника, а это потребует ресурса памяти, даже если описывать многогранник как двумерную сферическую структуру.
Экспериментальные подтверждения эффективности метода сжатия с помощью поиска плоских элементов
С целью проверки эффективности предлагаемого метода были протестированы модели различного типа и уровня детализации. Подготовленная группа моделей анализировалась при помощи алгоритма перебора сочетаний (для низкодетализированных моделей) и алгоритма плоских сечений. Для сравнения данные модели сжимались при помощи архиватора с открытым кодом gzip, реализующего алгоритм сжатия данных без потерь Зива—Лемпела (LZ77) [83]. Современные программы архивирования реализуют в основном модификации этого алгоритма и дают схожие результаты.
Эксперименты были проведены на специально подготовленных тестовых моделях и на реальном конструкторском проекте ДСЕ — 2 на базе ФГУП «Научное конструкторско-технологическое бюро „Парсек" Минобразования России».
Для экспериментов были подобраны модели с различным числом и расположением плоских элементов (см. рис. 4.5). Для проверки эффективности алгоритмов поиска плоских сечений были выбраны модели с большим количеством плоских элементов заданных, не параллельными плоскостями: «Sphere», «Torus», «Teapot». Для тестирования алгоритма подбора эффективного сочетания плоских элементов были подобраны модели с большим количеством пересекающихся плоских элементов: «Sphere», «Teapot». Проверка эффективности на произвольных инженерных и архитектурных моделей была проведена на моделях:«ARM», «Lamp», «StPauls», «Radiator», «Val», «Porhen», «House».
Проект ДСЕ —2 — инженерно-конструкторская разработка пространственного каркаса кузова автомобиля, разработанная группой специалистов, работавших в локальной вычислительной сети. В этой сети был организован сервер для хранения данных о геометрии деталей. Периодически в процессе проектирования проект сохранялся на магнитооптических носителях. В процессе реализации проекта несколько раз наращивались ресурсы сети в связи с ростом объема обрабатываемых данных.
Изометрическая проекция каркаса показана на рис. 4.4. Каркас состоит из нескольких подборок, которые в свою очередь состоят из отдельных деталей. Для оценки эффективности метода сжатия с помощью поиска плоских элементов проведена серия экспериментов на выборке деталей из конструкции каркаса.
Внешний вид деталей показан на рис. 4.6, 4.7, 4.8. Данные о результате работы алгоритмов сжатия представлены в таблицах 4.3 и 4.1. Эти таблицы состоят из столбцов содержащих число подмножеств V0, Vі, V2, созданных в результате работы алгоритма, и столбцов содержащих число вершин принадлежащих множествам V0, Vі, V2 и число вершин не вошедших в эти множества V3. Столбец сотр содержит коэффициент сжатия модели, рассчитанный для двухбайтного указателя множеств и фактически показывает на сколько сократится трафик при пе редаче сжатой модели по сети. Столбец gzip содержит коэффициент сжатия, полученный при помощи программы gzip.
Таблицы 4.2,4.4 содержат данные о работе алгоритмов поиска плоских элементов. Таблицы содержат данные о способе генерации множества N (Л—коррекция ламе коэффициентами, М—генерация методом Монте-Карло), о времени работы алгоритма, о числе найденных плоских элементов до и после верификации.
Проведенная серия экспериментов показала для тестовых моделей коэффициент сжатия: 27,9% —50,6%. Для деталей проекта ДСЕ —2 коэффициент сжатия: 19,6% —52,1%. Средний коэффициент сжатия для каркаса кузова: 35,88% , следовательно, при использовании исследуемых алгоритмов при разработке проекта ДСЕ —2 сетевой трафик сократился на 35,88%, что существенно повысило бы скорость обработки проекта.
