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

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

МЕЖЕНИН АЛЕКСАНДР ВЛАДИМИРОВИЧ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И ПРОГРАММНЫХ СРЕДСТВ ДЛЯ СОЗДАНИЯ И ОТОБРАЖЕНИЯ ТРЕХМЕРНЫХ ВИРТУАЛЬНЫХ ОБЪЕКТОВ В ИНТЕРНЕТ

Специальность 05.13.12 — Системы автоматизации проектирования (приборостроение)

АВТОРЕФЕРАТ

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

Санкт-Петербург-2005

Работа выполнена на кафедре инженерной и компьютерной 1рафики Санкт-Петербургского государственного университета информационных технологий, механики и оптики

Научный руководитель. кандидат технических наук,

доцент Тозик В Т

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

доктор технических наук, профессор Дегтярев В.М., кандидат технических наук, доцент Никитин A.B.

Ведущая организация. ФГУП СПб ОКБ «Электроавтоматика»

Защита состоится «21» июня 2005 г. в 1550 - на заседании диссертационного совета Д. 212.227 05 при Санкт-Петербургском государственном университете информационных технологий, механики и оптики

Адрес 197101, Санкт-Петербург, Кронверкский пр д 49, ГОУ ВПО СПбГУ ИТМО

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

Автореферат разослан « 20 » мая 2005 г.

Ученый секретарь диссертационного совета у /

Поляков В.И

23£ ЧЧЧ!

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

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

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

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

Любые разработки в области трехмерного Интернета сталкиваются с главной проблемой для прикладных программ, работающих в реальном времени - ограничение на пропускную способность ресурсов Интернет (каналы, узлы связи, вычислительные установки).

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Провести анализ и сравнительные оценки существующих технологий отображения трехмерной информации в Интернете и тенденций их развития для возможностей трехмерной графики и САПР.

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

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

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

5 Разработать алгоритмы и программные средства для реализации задачи отображения трехмерных виртуальных объектов в Интернете

6. Провести эксперименты, подтверждающие применимость и эффективность предложенных методов.

Методы исследования.

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

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

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

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

Практическая ценность.

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

Предлагаемые методы представления трехмерного Интернета как набора аппаратных и программных модулей охватывают все этапы создания таких систем, от моделирования трехмерных объектов, преобразования их в трехмерные форматы Интернет, до выбора модулей отображения и позволяют

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

Основные положения диссертации, выносимые на защиту:

• Структуры данных, описывающих трехмерные полигональные модели.

• Методы и алгоритмы упрощения полигональных моделей.

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

• Методы организации передачи трехмерных данных по сети Интернет.

• Алгоритмы визуализации полученных трехмерных данных. Достоверность и обоснованность результатов работы определяется

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

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

Результаты работы внедрены и используются на кафедре инженерной и компьютерной графики в проекте «Виртуальная кафедра» Научные результаты используются в учебном процессе университета по специальности 030500-«Профессиональное обучение»

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

1) Международных конференциях «Информационные технологии в образовании» (1999 - 2003).

2) 3-ей Межрегиональной н.-практ. конф. «Дополнительное профессиональное образование», СПб: 2000 г.

3) Юбилейной н.-т. конф. «ИТМО-ЮО лет»-СПб: 2000 г.

4) IV межрегион, науч -практ. конф. «Проблемы и перспективы взаимодействия ВУЗов СПб с регионами России в контексте реформирования образования» - СПб, 2001 г.

5) Второй всероссийской научно-практической конференции «Российская школа и Интернет» (2002).

6) Всероссийских научно-методических конференциях «Телематика 19982003».

7) Международном семинаре «Высшее образование в XXI веке: проблемы и перспективы», (2003 г.)

8) Заседаниях секции «Начертательной геометрии и автоматизации проектирования» при Доме Ученых им. A.M. Горького (1999-2005 г.). Публикации. По теме диссертационной работы опубликовано 16 работ

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

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

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

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

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

В современных системах компьютерной графики, особенно работающих в режиме реального времени, используется несколько типов алгоритмов, позволяющих снизить вычислительные затраты. Одним из таких алгоритмических подходов является отображение объекта с различным уровнем детализации с точки зрения визуального разрешения. При создании каждого последующего уровня упрощения мелкие детали модели, фактически не влияющие на структуру изображения, объединяются и заменяются на более крупные. Эта технология известна как Level of Detail (LOD) - уровень детализации.

Реализация механизма ЬСШ позволяет существенно повысить производительность систем

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

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

параметра оптимизации будет минимальным или максимальным (рис. 2).

Большинство итерационных алгоритмов упрощения полигональных моделей можно разделить на три категории:

• прореживание вершин;

• свертывание ребра;

• прореживание граней.

Алгоритм кластеризации вершин относится к категории / прореживания вершин и состоит в объединении вершин,

находящихся в одном кластере

пространства, в одну. Кластеры Рис. 3. Кластеризация вершин представляют собой трехмерную

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

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

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

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

Последовательность свертывания ребер определяется некой мерой Рис. 4. Операция свертывания ребра

ошибки, которая отражает локальное

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

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

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

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

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

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

4 3 4 3 4 3

Первоначальная модель - прямоугольная поверхность с

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

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

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

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

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

Шаг.1. Строится ограничивающий объем, представляющий собой параллелепипед, стороны которого параллельны осям координат. Координаты вершин параллелепипеда находятся как значения минимальных и максимальных координат вершин объекта по осям:

*m« = min(x„*2,...,x11)> х^ = max(x,,x2,...,x„),

Утт З'ша, =тах(у„>'2,...,уя),

zm,n = min(z,,z2)...,zn), =таx(z,,z2,...,zj

Шаг. 2. Координаты ограничивающих объемов находятся из предыдущих значений следующим образом:

X + X V + V Z 4- 7. у. _ min так _ s min s тах ^ _ min тах

" ~ 2 кх ' Ск 2 ку ' * ~ 2 kz ' где к.х,ку,кх - количество разбиений по осям X, Y, Z.

Шаг. 3. Определяется принадлежность вершин к каждой области разбиения путем проверки условий:

X ■< X < X V < V 5 V 2 < 2 < 2

пнп — / — тах 1 у тт — / — -'тах > тт / тах •

Шаг. 4. Определяется квадрат расстояния от вершин области до центров областей разбиения:

с1] ={хем -х,)1 +(уСм -уУ - г,)2.

Шаг. 5. Находятся минимальные и максимальные квадраты расстояний. Вершины, расположенные на минимальном и максимальном расстояниях, удаляться не будут.

Рис. 6. Выделение опорных точек . I I

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

• Вычисляется показатель ошибки для каждой операции свертывания ребра и выполняется упорядочивание по приоритетам.

• Выбирается ребро ё г (V 0 , V ) ь-» V (рис. 7) с минимальной величиной ошибки и заменяется на V. Во время этой операции треугольники, имеющие общие ребра с ег становятся сингулярными и удаляются. Оставшиеся грани, инцидентные вершине V,, модифицируются таким образом, что все, что было связано с v0, заменяется на V.

• Пересчитывается величина ошибки свертки ребра ёг (у,, у) (—> у. Добавляется стоимость ошибки схлопывания ё = (у0 , у,) в ту часть очереди,

которая связана с вершиной V, и модифицируется очередь по приоритетам. В результате формируется прогрессивная структура сети. Когда происходит свертывание произвольного ребра ё г (у 0 , V ) I—> V две грани, примыкающие к ребру становятся выродившимися.

Рис. 7. Свертывание ребра е, приводит к отображению

треугольника / = (у0,у,,у2) в треугольник /'= (у,у,,у2). Ребра {у,,^,} и {усуг}треугольника ^ = (у0,у,,у2) вырождаются

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

другой стороны, площадью треугольника ?'= (у0,у,у,). Чем больше та или другая величина, тем больше изменение формы поверхности.

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

<2, = Ав, где А = — |а х Ь||; а = у„ - Ь = VI - V, в - угол между

векторами нормалей двух треугольников. Суммарная величина ошибки ®г(у0'у) у может быть определена как сумма ошибок сверток всех граней,

примыкающих к : Сох1{ег) =

К!»!.»!«»

Граничные грани требуют специальной обработки для сохранения формы модели. Ребра, расположенные вдоль границы, делим на две категории: ребра, которые имеют одну вершину на границе ё = (у, V,) и ребра, имеющие две вершины на границе £ = (V,, у2 )

Ребро е, = {у0 , У|} поворачивается на угол ф при свертывании ё = > у2) ■ Соответственно, если свертывается ё = (у2 , у, ), то ребро ег = (у2'уз} повернется на угол ф0, при этом получается ф0 <ф. В результате

схлопывания ребра е = {у„,у} треугольник ' = (уо'У1 >у2) может перекрыть грань (рис. 8).

Свертывание ребра ё — (^, V,) (-» V, с конечной вершиной, находящейся на границе не требует специальной обработки. Однако, если начальная вершина находится на границе, то свертывание ребра исказит границу, и это необходимо учитывать.

Ребро е = может быть свернуто в вершины V, или v2, но лучший

результат будет при сворачивании в V,. Для достижения этого необходимо измерить угол ф и фй между ребрами ех и е]' и ег е2' соответственно.

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

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

Рассмотрим положения векторов нормалей граней, примыкающих к V, и ^ до и после сокращения (рис. 9). Если изменение положения вектора нормали будет превышать некоторый порог, мы можем рассматривать эту грань как «зеркально отраженную» в результате сокращения, что позволяет решить проблему появление сверток.

Рис. 9.

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

Г 2 , 2 2 45-УЗ

45л/3 <а +Ь +с , л- —5 ^ где а,о,с - длины сторон

а +о + с

треугольника, а его площадь.

Соответственно, для равностороннего треугольника /1 = 1, при уменьшении одного из углов треугольника эта величина будет приближаться к 0. Используя эту величину мы можем отменять те треугольники, чья правильность меньше некоторого порога.

лат

Рис. 10. Результат работы алгоритма: а) исходная модель 3679 граней -100%, Ь) 2856 граней - 80%, с) 2441 граней - 60%.

Основные характеристики разработанного алгоритма:

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

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

• Разработанный алгоритм в вычислительном отношении показывает лучшие результаты по сравнению с известными алгоритмами, основанными на свертывании ребер.

• Алгоритм автоматически предотвращает появление искажений типа сверток.

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

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

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

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

Полусуммы можно рассматривать как крупномасштабное представление исходного образа, а полуразности - числа которые необходимы для восстановления мелких подробностей или поправок. Обратное преобразование позволяет целиком восстановить исходные данные. Но если значения х, и х1+1 исходной последовательности оказываются близкими друг другу, то в этом случае их полуразность <Л мала, и может быть заменена на нули. Тем самым можно получить сжатие с потерей части информации.

Этот метод обобщается на двумерные массивы данных. Двумерное ВП может быть реализовано композицией одномерных. Это с успехом используется для сжатия оцифрованных изображений. Рассмотренная последовательность трансформаций массива данных является простейшим примером поддиапазонного преобразования.

Рис. 11. Упрощение модели на основе использования вейвлет -преобразования. Количество нулевых коэффициентов а) 100 %, Ь) 80%, с) 60%.

а Ь с

s

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

£2'= f¿2'1 -1 = ^^-1 = 2"'-2 = 2(2" -1) = -1)

/.ï V/-o /

В разработанном алгоритме перед применением ВП исходная модель преобразуется в "ленты многоугольников" (polygon strips). Грани модели упорядочиваются таким образом, чтобы "развернуть" модель в ленту из связанных граней. Результат работы алгоритма представлен на рис. 11.

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

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

В работе предложен подход, позволяющий в цифровой форме сравнивать две полигональных модели с различными уровнями детализации. При этом, не имеет значения, какие методы упрощения моделей использовались. Ошибка аппроксимации между двумя полигональными моделями базируется на вычислении расстояния аппроксимации {approximate distance) и может быть определена следующим образом. Дана точка р и поверхность S (рис. 12). Определим расстояние e(p,S), и расстояние между двумя поверхностями S^,S2 как e(p,S) = mind(p,p') E(St,S2) = maxe(p,S2)

p'zS peSt

где d() - Евклидово расстояние между двумя точками в Ег.

Необходимо отметить, что это расстояние не симметрично. Существуют поверхности такие, что E{SltS2) * £(iS2,Si). Хаусдорфово расстояние (двустороннее) может быть получено как максимум E(S,,S2) и E(S2,St). Среднее (mean) Ет расстояние между двумя поверхностями можно определить как интеграл по поверхности, определенный областью

Pi| s,

Если поверхность S, ориентирована в пространстве, мы можем расширить определение расстояния между точкой р поверхности S, и поверхностью S2 как расстояние е' положительное (positive) до ближайшей точки p,eS2, расположенной по одну сторону , и отрицательное (negative) в другом случае. Другими словами, если Nр вектор нормали к S, в точке р и p'eS2 - ближайшая точка, тогда знак расстояния может быть определен как знак Np * (р'-р).

Эти определения позволяют ввести различия между положительными и отрицательными расстояниями между поверхностями.

E+(St,S2) = maxe4p,S2) E'(Sl,S2) =

peS,

min e'(p,S2)

peS,

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

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

ОвИт а Ро1усгипсЬ г Разр. алгоритм

Рис. 13. График средней ошибки в зависимости от количества граней для разных алгоритмов упрощения

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

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

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

В ходе экспериментальной проверки была разработана прикладная программа работающей по HTTP протоколу с сервером. Графическая часть программы реализована на основе библиотеки OpenGL. Алгоритм работы выглядит следующим образом:

1) Клиентская программа обращается к PHP скрипту, расположенному на сервере.

2) PHP скрипт обрабатывает файл данных file.dat.

3) PHP скрипт посылает обработанные данные в виде заголовков (headers) на клиента, используя протокол HTTP. Каждый заголовок содержит идентификатор, размер, название и само содержимое.

4) На основе полученных данных в прикладной программе формируется массив, который отображается на экране.

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

Р-Ш

RAM

128Mb

1 Граней Иск j файл, байт Сжатый файл. байт Козфф Сжатия Т. сек 1)

3 851 ' 214855 10 564 20 3 05

1 948 1 4P 607 2 951 16.8 02

2 340 1 115 748 4 989 23.2 03

1 596 1 115 559 6 757 17 1 04

1 800 88 727 3 486 25 5 02

б 428 , 328 420 14 333 22 S 08

Рис. 14. Интерфейс программы и количественные показатели ее работы

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

Основные результаты диссертационной работы следующие:

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

2. Определены перспективные области применения трехмерных Интернет -технологий. Показана необходимость использования технологии

упрощения, на основе уровней детализации для повышения производительности систем трехмерной визуализации

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

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

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

6. Решена задача сохранения топологических особенностей, что является важным для геометрических моделей в системах САПР.

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

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

9. Предложен метод измерения качества упрощения на основе измерения Хаусдорфова расстояния. Для повышения уровня достоверности результатов предложено использовать метод Монте-Карло для генерации к выборок пропорциональных площади каждой грани.

Ю.Проведено исследование возможности передачи трехмерных полигональных моделей через Интернет. На их основе разработано клиент/серверное приложение. 11 .Проведена программная реализация разработанных алгоритмов упрощения. Показана эффективность предложенных алгоритмов. Трудоемкость алгоритмов оценивается кубической степенной функцией от числа вершин объекта визуализации. Основное содержание диссертационной работы изложено в следующих публикациях:

1. Меженин A.B. Виртуальные миры в учебном процессе // Тезисы докл. всерос. н.-методич. конф. "ТЕЛЕМАТИКА-98",СПб, 1998

2. Меженин A.B., Тозик В.Т.Использование современных информационных технологий для дистанционного обучения в МИПК ИТМО // Труды Всерос. н.-метод. конференция «ТЕЛЕМАТИКА '1999», СПб.

3. Бочков А.Л., Меженин A.B., Тозик В.Т. Мультимедийные технологии при дистанционном обучении компьютерной графике // Материалы IX международной конференции ИГО - 99 «Информационные технологии в образовании», ч.З -М: 1999 г.

4. Меженин A.B., Тозик В.Т. Создание сервера виртуальных миров кафедры ИКГ // Тезисы докл. Юбилейной н.-т. конф. «ИТМО-ЮО лет», ч.2 -СПб: 2000 г.

5. Меженин A.B., Тозик В.Т. Методология создания учебных курсов дистанционного обучения в системе дополнительного профессионального образования // Тезисы докл. 3-ей Межрегиональной н.-практ. Конф. «Дополнительное проф. образование», СПб: 2000г.

6. Меженин A.B. Создание электронных учебников с использованием VRML-технологий // Тезисы докл. Межд. Н.-методич. Конф. «ТЕЛЕМАТИКА-2000». СПб, 2000 г.

7. A.B. Меженин, В.Т. Тозик Анализ и сравнительная оценка инструментальных средств 3D - визуализации в Интернет - образовании // Материалы X международной конференции «Информационные технологии в образовании» (ИТО-2000), 2000 г.

8. A.B. Меженин, В.Т. Тозик «Технология преобразования трехмерных объектов для Интернет», Международный семинар «Высшее образование в XXI веке: проблемы и перспективы»: Материалы семинара, Санкт-Петербург, 29июня-3июля 2002 г. /СПбГУАП, СПб., 2002. 153 е.: ил. ISBN 5-8088-0071-4

9. A.B. Меженин, В.Т. Тозик «Современная технология для представления трехмерных моделей в Интернет» Труды X Всероссийской научно-методической конференции «Телематика '2003», СПб, 2003 г.

10. Меженин A.B., Безгодов A.A. Разработка ActiveX элемента управления для представления 3D информации в Интернет // Материалы XII международной конференции «Информационные технологии в образовании» (ИТО-2003), 2003 г.

11. Меженин A.B., Шамазова С.Т. Особенности использования языка VRML // Материалы ХП международной конференции «Информационные технологии в образовании» (ИТО-2003), 2003 г.

12. Меженин A.B. Методика моделирования 3D моделей в проекте «Высшая школа С.-Петербурга в киберпространстве»// Межвуз. Сб. научно-метод. статей «Инф. техн. в проф. и проф.-пед. образов.»-СПб, 2003

13. A.JI. Бочков, A.B. Меженин. Графика для Web и современные технологии мультимедиа. Учебно-методическое пособие. -СПб. :СПбГИТМО("ГУ), 2003,-102с

14. Интернет-технологии - образованию / Под редакцией В.Н. Васильева, JI.C. Лисицыной. - СПб.: Питер, 2003. - 464 е.: ил.

15. Меженин A.B. ActiveX элемент управления для отображения трехмерной графической информации в Интернете. - М.: ВНТИЦ, - № 50200401145.

16. Тозик В.Т., Меженин A.B. 3ds max 7: трехмерное моделирование и анимация. - СПб.: БХВ-Петербург, 2005. - 992 е.: ил.

РНЬ Русский фонд

2007^4 ~3336~

Изготовлено в Центре издательских систем СПб ГУИТМО Тел. (812^388538. Лицензия ПЛД №69-182 от 29.11.96 Заказ № £5". Подписано в печать 05.05 Тираж 100 экз.

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

1. АНАЛИЗ И СРАВНИТЕЛЬНАЯ ОЦЕНКА МЕТОДОВ И ПРОГРАММНЫХ СРЕДСТВ В ОБЛАСТИ СОЗДАНИЯ И ОТОБРАЖЕНИЯ ТРЕХМЕРНЫХ ВИРТУАЛЬНЫХ ОБЪЕКТОВ В

ИНТЕРНЕТ.

1.1 .Состояние исследований в области трехмерных технологий в

Интернете.

1.1.1. Системы и технологии.

1.1.2. Области применения трехмерных технологий в Интернете.

1.1.3. Стандарты в области трехмерного Интернета.

1.2.Полигональные модели.

1.3.Представление больших объемов данных и поддержка различных уровней детализации.

1.3.1. Технологии LOD.

1.3.2. Реализация LOD в языке VRML.

1.4.Полигональные модели с переменным разрешением. Классификация итеративных методов упрощения.

1.5.Постановка задачи диссертационного исследования.

Выводы по главе 1.

2. РАЗРАБОТКА АЛГОРИТМОВ УПРОЩЕНИЯ ПОЛИГОНАЛЬНЫХ

МОДЕЛЕЙ.

2.1.Разработка алгоритма упрощения на основе оценки изменения геометрических параметров.

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

2.1.2. Оценка скорости вывода.

2.1.3. Неравномерная сетка.

2.1.4. Топологический аспект моделей.

2.1.5. Методы представления пространства и манипулирования геометрическими элементами.

2.1.6. Описание алгоритма.

2.2.Разработка алгоритма упрощения с использованием вейвлет-преобразований.

2.3.Измерение качества упрощения моделей.

Выводы по главе 2.

3. РАЗРАБОТКА КОМПЛЕКСА ПРОГРАММ ДЛЯ ПЕРЕДАЧИ И

ОТОБРАЖЕНИЯ ТРЕХМЕРНЫХ МОДЕЛЕЙ В СЕТИ ИНТЕРНЕТ.

3.1.Клиент-серверная платформа для передачи и отображения трехмерных данных.

3.1.1. Язык Java и Java-апплеты.

3.1.2. ActiveX.Ill

3.1.3. Обоснование выбора графической платформы.

3.2.Организация данных для прогрессивной передачи с различными уровнями детализации.

3.3.Экспериментальная оценка работы разработанных алгоритмов в VRML-среде.

3.4.Разработка программы клиента и Active-X элемента управления. 129 Выводы по главе 3.

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

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

Любые разработки в области трехмерного Интернета сталкиваются с главной проблемой для прикладных программ, работающих в реальном времени - ограничением на пропускную способность ресурсов Интернета (каналы, узлы связи, вычислительные установки).

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

Цель работы. Целью диссертационной работы является разработка эффективных методов, алгоритмов и программ для создания системы трехмерной визуализации объектов САПР в Интернете.

Задачи исследования. Для достижения поставленной цели необходимо решить следующие задачи:

1. Провести анализ и дать сравнительную оценку существующих технологий отображения трехмерной информации в Интернете и тенденций их развития для возможностей трехмерной графики и САПР.

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

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

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

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

6. Провести эксперименты, подтверждающие эффективность предложенных методов.

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

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

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

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

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

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

Основные положения диссертации, выносимые на защиту:

• Методы и алгоритмы упрощения полигональных моделей.

• Методы организации передачи трехмерных данных по сети Интернет.

• Алгоритмы визуализации полученных трехмерных данных.

• Структуры данных, описывающих трехмерные полигональные модели.

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

Реализация и внедрение результатов работы. Работа выполнена на кафедре инженерной и компьютерной графики (ИКГ) Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПбГУИТМО). Теоретическое исследование, предложенные методы и .разработанное программное обеспечение внедрены и использовались:

1) При создании Виртуального мира СПб ГУИТМО в рамках проекта «Высшая школа Санкт-Петербурга в киберпространстве»,' выполненного в рамках договора №103/120 от 10.042002.г. по заказу администрации Санкт-Петербурга.

2) При выполнении госконтракта №799 от 04.11.2004г. «Исследование проблем использования перспективных технологий мультимедиа при разработке интерактивных информационно-образовательных и обучающих программ», выполненного по заказу ФАО РФ в рамках научной программ «Федерально-региональная политика в науке и образовании».

3) при разработке электронных учебных пособий и лабораторных работ на кафедре ИКГ для студентов технических специальностей СПбГУИТМО в рамках проекта «Виртуальная кафедра».

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

1) Международных конференциях «Информационные технологии в образовании» (1999 - 2003).

2) 3-ей Межрегиональной научно-практической конференции «Дополнительное профессиональное образование» - СПб, 2000 г.

3) Юбилейной научно-теоретической конференции «ИТМО - 100 лет» -СПб, 2000 г.

4) IV межрегиональной научно-практической конференции «Проблемы и перспективы взаимодействия ВУЗов СПб с регионами России в контексте реформирования образования» - СПб, 2001 г.

5) Второй всероссийской научно-практической конференции «Российская школа и Интернет» - СПб, 2002 г.

6) Всероссийских научно-методических конференциях «Телематика 19982003».

7) Международном семинаре «Высшее образование в XXI веке: проблемы и перспективы» - СПб, 2003 г.

8) Заседаниях секции «Начертательной геометрии и автоматизации проектирования» при Доме Ученых им. A.M. Горького (1999-2005 г.). Публикации. По теме диссертационной работы опубликовано 16 работ.

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

Выводы по главе 3

В главе описана программная реализация системы передачи и отображения трехмерных полигональных объектов в Интернете. На основе анализа различных технологий реализации клиентской части программного комплекса и организации данных для прогрессивной передачи данных с различными уровнями детализации проведена разработка программного комплекса и экспериментальная оценка работы разработанных программ в VRML-среде.

Описана структура и функционирование программы клиента в виде самостоятельного приложения и в виде встраиваемого элемента управления

Active-X. Графическая часть программы реализована с помощью библиотеки OpenGL. Проведена экспериментальная оценка работы разработанных программ.

Основные особенности разработанного программного обеспечения:

1. Ориентация на работу в сети. Система обеспечивает работу в режиме "клиент-сервер" через Интернет и по ЛВС с использованием стандартного протокола TCP/IP.

2. Под держка потоковой передачи данных трехмерных моделей с различной степенью детализации.

3. Интерактивность. Система настроек позволяет выбирать различные алгоритмы упрощения и визуализации.

4. Инвариантность к различным, платформам на уровне исходных текстов программ.

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

ЗАКЛЮЧЕНИЕ

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

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

2. Обоснована необходимость использования технологий упрощения на основе уровней детализации для повышения производительности систем трехмерной визуализации, особенно для сложных моделей

САПР.

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

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

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

6. Решена задача сохранения топологических особенностей моделей, что является важным для геометрических моделей в системах САПР.

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

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

9. Разработан алгоритм многомасштабного представления моделей на основе применения вейвлет-преобразований.

10.Предложен метод измерения качества упрощения на основе измерения Хаусдорфова расстояния. Для повышения уровня достоверности результатов предложено использовать метод Монте-Карло для генерации к выборок пропорциональных площади каждой грани.

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

138

1. Амерал Л. Машинная графика на языке С. В 4-х кн. Пер. с англ. — М.: Сол Систем, 1992.

2. Берлянт А. М. Картография: Учебник для вузов.— М.: Аспект Пресс, 2001.—336 с.

3. Борковский А. Б. Англо-русский словарь по программированию и информатике (с толкованиями). — М.: Рус. яз., 1989. — 335 с.

4. Бочков А.Л., Меженин A.B., Тозик В.Т. Мультимедийные технологии при дистанционном обучении компьютерной графике // Материалы IX международной конференции ИТО 99 «Информационные технологии в образовании», ч.З - М: 1999 г.

5. А.Л. Бочков, A.B. Меженин. Графика для Web и современныетехнологии мультимедиа. Учебно-методическое пособие. -СПб.:СПбГИТМО(ТУ), 2003.-102с

6. Вельтмандер П. В. Машинная графика: Учеб. пособие в 3-х кн. — Новосибирск: Новосибирский гос. ун-т, 1997.

7. Вернер А. В., Кантор Б. Е., Франгулов С. А. Геометрия. Ч. I. Учебное пособие. — СПб.: Специальная литература, 1997. — 352 с.

8. Вернер А. В., Кантор Б. Е., Франгулов С. А. Геометрия. Ч. И. Учебное пособие. — СПб.: Специальная литература, 1997. — 320 с.

9. Воеводин В. В. Линейная алгебра. — М.: Наука, 1980. — 400 с.

10. Ю.Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. — М.:1. Наука, 1984.—318 с.

11. П.Гусев A.B., Ивашин С.Л., Та^ныкин Э.А. Математические модели сцен в синтезирующих системах визуализации реального времени // Автометрия. 1985. №4.3-9

12. Игнатенко А. Методы представления дискретных трехмерных данных. http://graphics.cs.msu.su

13. З.Иванов А. П., Батраков А. С. Трехмерная компьютерная графика. — М.: Радио и связь, 1995. — 224 с.

14. Кнут Д. Искусство программирования. В 3-х томах.— М.: Издательский дом "Вильяме", 2001.

15. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). — М.: Наука, 1978. — 832 с.

16. Майкл Ласло. Вычислительная геометрия и компьютерная графика на С+ + : Пер. с англ. — М.: Бином, 1997. — 304 с.

17. Математика и САПР. В 2-х кн. Кн. 1,2. Пер. с франц. / Шенен П., Коснар М., Гардан И. и др. — М.: Мир, 1988. — 204 с.

18. Меженин A.B. Виртуальные миры в учебном процессе // Тезисы докладов всероссийской научно-методической конференции "ТЕЛЕМАТИКА-98",СПб, 1998

19. Меженин A.B., Тозик В.Т. Использование современных информационных технологий для дистанционного обучения в МИПК ИТМО Н Труды Всерос. н.-метод. конференция «ТЕЛЕМАТИКА '1999», СПб.

20. Меженин A.B., Тозик В.Т. Создание сервера виртуальных миров кафедры ИКГ // Тезисы докл. Юбилейной н.-т. конф. «ИТМО-ЮО лет», ч.2 -СПб: 2000 г.

21. Меженин A.B., Тозик В.Т. Методология создания учебных курсов дистанционного обучения в системе дополнительного профессионального образования // Тезисы докл. 3-ей Межрегиональной н.-практ. Конф. «Дополнительное проф. образование», СПб: 2000г.

22. Меженин A.B. Создание электронных учебников с использованием VRML-технологий // Тезисы докл. Межд. Н.-методич. Конф. «ТЕЛЕМАТИКА-2000». СПб, 2000 г.

23. Меженин A.B., Тозик В.Т. Анализ и сравнительная оценка инструментальных средств 3D визуализации в Интернет -образовании // Материалы X международной конференции «Информационные технологии в образовании» (ИТО-2000), 2000 г.

24. Меженин A.B., Тозик В.Т. «Современная технология для представления трехмерных моделей в Интернет» Труды X Всероссийской научно-методической конференции «Телематика '2003», СПб, 2003 г.

25. Меженин A.B., Безгодов A.A. Разработка ActiveX элемента управления для представления 3D информации в Интернет // Материалы XII международной конференции «Информационные технологии , в образовании» (ИТО-2003), 2003 г.

26. Меженин A.B., Шамазова С.Т. Особенности использования языка VRML // Материалы XII международной конференции «Информационные технологии в образовании» (ИТО-2003), 2003 г.

27. Меженин A.B. Методика моделирования 3D моделей в проекте «Высшая школа С.-Петербурга в киберпространстве»// Межвуз. Сб. научно-метод. статей «Инф. техн. в проф. и проф.-пед. образов.»-СПб, 2003

28. Меженин A.B. Графика и мультимедиа для Web Сборник Интернет-технологии - образованию / Под редакцией В.Н. Васильева, Л.С. Лисицыной. - СПб.: Питер, 2003. - 464 е.: ил.

29. Меженин A.B. ActiveX 'элемент управления для отображения трехмерной графической информации в Интернете. М.: ВНТИЦ, - № 50200401145.

30. Пайтген Х.-О., Рихтер П. X. Красота фракталов. Образы комплексных динамических систем. — М.: Мир, 1993. — 176 с.

31. Порев В. Н. Компьютерная графика. — СПб.: БХВ-Петербург, 2002. — 432 с.

32. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989. —478 с.

33. Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989.—512 с.

34. Роджерс Д., Адаме Дж. Математические основы машинной графики.— М.: Мир, 2001.—604 с.

35. Сэломон Д. Сжатие данных, изображений и звука Москва: Техносфера, 2004.- 368с.

36. Тозик В.Т., Меженин А.В. 3ds max 7: трехмерное моделирование и анимация. СПб.: БХВ-Петербург, 2005. - 992 е.: ил.

37. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособие. М.: Издательство Триумф, 2003 - 320 е.: ил.

38. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. — М.: Мир, 1982. — 304 с.

39. Хирн Д., Бейкер М. Микрокомпьютерная графика.— М.: Мир, 1987.—352 с.

40. Хори Р., Джонсон Ч. Матричный анализ. — М.: Мир, 1989. — 655 с.

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

42. Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. — М.: ДИАЛОГ-МИФИ, 2000. — 464 с.

43. Эйнджел Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGL, 2-е изд. — М.: Издательский дом "Вильяме", 2001. — 592 с. *

44. Alliez Р. and Desbrun М. Progressive Compression for Lossless Transmission ofTriangle Meshes. In ACM SIGGRAPH 2001 Conference Proceedings, pages 195-202, 2001.

45. Algori M. and Schmitt F., "Mesh simplification," Computer Graphics Forum (Proc. Eurographics '96) 15(3), (1996).

46. Bajaj C. and Schikore D., "Error-Bounded Reduction of Triangle Meshes with Multivariate Data," Proc. SPIE, Vol. 2656, SPIE Press, Bellingham, Wash., 1996, pp. 34-45.

47. Braden B., Clark D. and Shenker S. RFC 1633: Integrated Services in the Internet Architecture: an Overview. The Internet Society, 1994.

48. Bill Shannon, Mark Hapner, Vlada Matena, Eduardo PelegriLlopart,James Davidson, Larry Cable, and The Enterprise Team. Java. 2 Platform, Enterprise Edition: Platform and Component Specifications.

49. Carey R. and Bell G., The Annotated VRML 2.0 Reference Manual, Reading, Mass., Addison Wesley, 1997.

50. Ciampalini A., Cignoni P., Montani C., and Scopigno R., "Multiresolution decimation based on global error," The Visual Computer 13, 228-246 (1997).

51. Cignoni P., Montani C., and Scopigno R., "A comparison of mesh simplification algorithms," Computer & Graphics 22(1), 37-54 (1998).

52. Cignoni P., Rocchini C., and Scopigno R., "Metro: measuring error on simplified surfaces," Computer Graphics Forum 17(2), 167-174 (1998).

53. Chen B.-Y. and Nishita. T. jGL and its Applications as a Web3D Platform. In ACM Web 3D 2001 Conference Proceedings, pages 85-91, 2001.

54. Cohen J., Varshney A., Manocha D., Turk G., Weber H., Agarwal P., Brooks F. and Wright W. Simplification Envelopes. In ACM S1GGRAPH 96 Conference Proceedings,pages 119-128, 1996.

55. Cohen J., Manocha D., and Olano M., "Simplifying Polygonal Models using Successive Mappings," Proc. IEEE Visualization 97, ACM Press, New York, 1997, pp. 395-402.

56. Deering M., "Geometric Compression," Proc. Siggraph 95 ACM Press, New York, 1995, pp. 13-20.

57. DeFloriani L., Magillo P., and Puppo E., "Building and Traversing a Surface at Variable Resolution," Proc. IEEE Visualization 97, ACM Press, New York, 1997, pp. 103-110.

58. Eck M., DeRose T., Duchamp T., Hoppe H., Lounsbery L. and Stuetzle. W. Multiresolution Analysis of Arbitrary Meshes. In ACM SIGGRAPH 95 Conference Proceedings, pages 173-182, 1995.

59. Faux I. and Pratt M., Computational Geometry for Design and Manufacture (Ellis Horwood, Chichester, 1979).

60. Frank K. and Lang U., "Data-dependent surface simplification," Eurographics Workshop on Visualization in Scientific Computing (Germany, April 1998).

61. Garland M. "Multiresolution modeling: survey & future opportunities," State of the Art Report (STAR), EUROGRAPHICS '99 (1999).

62. Garland M. and Heckbert P.S. Simplifying Surfaces with Color and Texture Using Quadric Error Metrics. In IEEE Visualization 98 Conference

63. Proceedings,, pages 263-269,1998.

64. Garland M. and Heckbert P.S. Surface Simplification Using Quadric Error Metrics . In ACM SIGGRAPH 97 Conference Proceedings, pages 209-216, 1997.

65. Garland M., Willmott A. and Heckbert P.S. Hierarchical Face Clustering on Polygonal Surfaces. In ACM 2001 Symposium on Interactive 3D Graphics Proceedings, pages 49-58, 2001.

66. Gieng T.S., Hamann B., Joy K.I., Schussman G.L., and Trotts I.J., "Smooth hierarchical surface triangulations,"in Proc. IEEE Visualization '97, 379-386(1997).

67. Gurceziec A., "Locally toleranced surface simplification," IEEE Transactions on Visualization find Computer Graphics 5(2), 168-189 (1999).

68. Gueziec A. et al., "Simplicial Maps for Progressive Transmission of Polygonal Surfaces," Proc. VRML 98, ACM Press, New York, 1998, pp. 2531.

69. Guéziec A., "Surface Simplification with Variable Tolerance," Proc. Second Annual Symp. Medical Robotics and Computer-Assisted Surgery, Wiley and Sons, New York, 1995, pp. 132-139.

70. Gumbold S. and Strasser W., "Real-Time Compression of Triangle Mesh Connectivity," Proc. Siggraph 1998, ACM Press, New York, 1998, pp. 133140.

71. Hamann B., "A data reduction scheme for triangulated surfaces," Computer Aided Geometric Design 11,197-214 (1994).

72. Heckbert P. and Garland M., "Multiresolution modeling for fast rendering," in Proc. Graphics Interface '94, 43-50 (1994).

73. Heckbert P.S. and Garland M. Survey of Polygonal Surface Simplification Algorithms. In ACM SIGGRAPH 97 Conference, Multiresolution Surface . Modeling Course Notes, 1997.

74. Hoppe. H. New Quadric Metric for Simplifying Meshes with Appearance Attributes. In IEEE Visualization 99 Conference Proceedings, pages 59-66, 1999.

75. Hoppe H. Efficient Implementation of Progressive Meshes. In Computer & Graphics. Vol. 22, No. 1, pages 27-36, 1998. 14. H. Hoppe. View-dependent Refinement of Progressive Meshes. In ACM SIGGRAPH 97 Conference Proceedings, pages 189-198,1997.

76. Hoppe. H. Progressive Meshes. In ACM SIGGRAPH 96 Conference Proceedings, pages 99-108,1996.

77. Hoppe H., DeRose T., Duchamp T., McDonald J. and Stuetzle W. Mesh Optimization. In ACM SIGGRAPH 9¡Conference Proceedings, pages 19-26, 1993.

78. Hoppe H., "View-Dependent Refinement of Progressive Meshes," Proc. Siggraph 97, ACM Press, New York, 1997, pp. 189-198.

79. Ho Y.-S. and Ahn J.-H., "Geometry compression of 3D meshes using optimal quantization for prediction errors,", ISO/IEC JTC1/SC29AVG11 MPEG98/m3751, July 1998.

80. Hussain M., Okada Y., and Niijima K., "Fast, simple and memory efficient mesh simplification," in Proc. Fourth IASTED International Conference on Computer Graphics and Imaging (CGIM200I) 72-77 (2001).

81. Kalvin A.D. and Taylor R.H., "Superfaces: Polygonal Mesh Simplification with Bounded Error," IEEE Computer Graphics and Applications, Vol. 16, No. 3, May 1996, pp. 64-77.

82. Khodakovsky A., Schroder P. and Sweldens W. Progressive Geometry Compression. In ACM SIGGRAPH 2000 Conference Proceedings, pages 271-278, 2000.

83. Kobbelt L., Campagna S., and Seidel H.P., "A general framework for mesh decimation," in Proc. Graphics Interface '98, 311-318 (1998).

84. Lee A., Sweldens W., Schoroder P., Cowsar L. and Dobkin D. MAPS:

85. Multiresolution Adaptive Parameterization of Surfaces. In ACM SIGGRAPH 98 Conference Proceedings, pages 95-104,1998.

86. Li J. and C.-C. Jay Kuo, "Progressive coding of 3D graphic models," Proc. IEEE, vol. 86, pp. 1252-1263, June 1998.

87. Lindstrom P. and Turk G., "Fast and memory efficient polygonal simplification," in Proc. IEEE Visualization '98 544, 279-286 (1998).

88. Lindstrom P. and Turk G., "Evaluation of memoryless simplification," IEEE Transactions on Visualization and Computer Graphics 5(2), 98-115 (1999).

89. Luebke D. and Erikson C., "View-Dependent Simplification of Arbitrary Polygonal Environments," Proc. Siggraph 97, ACM Press, New York, 1997,

90. Puppo E., "Variable resolution triangulations," Technical Report 12/96 (Institute for Applied Mathematics, C.N.R. Genova, Italy, November 1996).

91. Reddy M., "SCROOGE: Perceptually-driven polygon reduction," Computer Graphics Forums 15(4), 191-203 (1996).

92. Ronfard R. and Rossignac J., "Full-Range Approximation of Triangulated Polyhedra," Computer Graphics Forum, Proc. Eurographics 96, Vol. 15, No. 3, 1996, C67-C76.

93. Rossignac J., Borrel P. Multi-resolution 3D approximations for rendering complex scenes // Modeling in Computer Graphics. BerlinA SpringerVerlag, 1993.455-465

94. Sander P., Snyder J., Gortier S. and Hoppe H. Texture Mapping Progressive Meshes. In ACM S1GGRAPH 2001Conference Proceedings, 2001.

95. Schroeder W.J., Zarge J. A. and Lorensen W.E. Decimation of Triangle Meshes. In ACM Computer Graphics (SIGGRAPH 92 Conference Proceedings), Vol. 26, No. 2, pages 65-70, 1992.

96. Soucy M. and Laurendeau D., "Multiresolution surface modeling based on hierarchical triangulation," Computer Vision and Image Understanding 63(1), 1-14(1996).

97. Sowizral Henry, Rushforth Kevin, and Deering Michael. The Java 3D. API Specification. Addison-Wesley, 2nd. edition, 2000.

98. Taubin G. and Rossignac J., "Geometric compression through topological surgery," IBM Research Division, Online. Available HTTP: http://www.research.watson.ibm.com/vrml/binary/pdfs/ibm20340rl.pdf, Jan. 1996.

99. Taubin G. et al., "Progressive Forest Split Compression," Proc. Siggraph 1998, ACM Press, New York, 1998, pp. 123-132.

100. Taubin G., Horn W.P., Lazarus F., and Rossignac J, "Geometry coding and VRML," Proc. IEEE, vol. 86, pp. 1228-1243, June 1998.

101. Taubin G., Horn W., and Lazarus F., "The VRML compressed binary format—ISO/IEC 14 772-3 editor's draft 5,", Onine., Available HTTP: http://www.research.ibm.com/Vrml/binary/, Feb. 1998.

102. Tarjan R.E., Data Structures and Network Algorithms, No. 44 in CBMS-NSF Regional Conference Series in Applied Mathematics, Soc. for Industrial and Applied Mathematics (SIAM), Philadelphia, 1983.

103. To D., Lau R. and Green M. An Adaptive Multi-Resolution Method for Progressive Model Transmission. In Presence: Teleoperators and Virtual Environments, Vol. 10, No. 1, pages 62-74,2001.

104. Turk G. Re-tiling Polygonal Surfaces. In ACM Computer Graphics (SIGGRAPH 92 Conference Proceedings), Vol. 26, No. 2, pages 55-64, 1992.

105. Watt Alan. 3D Computer Graphics. Addison-Wesley, 3rd. edition, 1999.

106. Womack Paula and Leech Jon. OpenGL® Graphics with the X window System® (Version 1.3). Silicon Graphics, Inc., 1998.

107. Woo Mason, Neider Jackie, Davis Tom, and Shreiner Dave. OpenGL® Programming Guide: The Official Guide to Learning OpenGL, Version 1.2. Addison-Wesley, 3rd. edition, 1999.

108. Wu J.-H, Hu S.-M., Tai C.-L., and Sun J.-G., "An effective feature-preserving mesh simplification scheme based on face constriction,"in Proc, Pacific Graphics '01 (2001).