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

На правах рукописи УДК 519.683

Мирза Наталия Сергеевна

РАЗРАБОТКА АЛГОРИТМОВ ПОСТРОЕНИЯ, АНАЛИЗА И ВИЗУАЛИЗАЦИИ СВЕРХБОЛЬШИХ МОДЕЛЕЙ ПОВЕРХНОСТЕЙ НА ОСНОВЕ МУЛЬТИТРИАНГУЛЯЦИИ

Специальность 05.13.11 -«Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»

Автореферат

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

Томск - 2006

Работа выполнена в Томском государственном университете.

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

д.т.н., доцент Скворцов Алексей Владимирович.

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

д.т.н., профессор Ехлаков Юрий Поликарпович, к.т.н. Ковин Роман Владимирович.

Ведущая организация:

Сибирский государственный аэрокосмический университет.

Защита состоится 15 июня 2006 г. в 10:30 на заседании Диссертационного совета Д 212.267.08 при Томском государственном университете (634050, г. Томск, пр. Ленина, 36) в ауд. 102 второго корпуса.

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

Отзывы на автореферат (2 экз.), заверенные печатью, высылать по адресу: 634050, г. Томск, пр. Ленина, 36, учёному секретарю ТГУ.

Автореферат разослан 12 мая 2006 г.

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

диссертационного совета, д.т.н., доцент

А.В. Скворцов

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

Актуальность. На сегодняшний день задачи построения и визуализации больших трёхмерных моделей открытых участков местности (крупномасштабных моделей городов и протяжённых объектов транспортного, промышленного и гражданского строительства; любых мелкомасштабных моделей территорий) находят широкое применение в самых различных областях человеческой деятельности: для анализа пространственных данных, при проектировании объектов строительства, при обучении лётчиков на компьютерных тренажёрах -симуляторах, в индустрии развлечений (создание компьютерных игр и видеофильмов) и военных целях для моделирования обстановки на поле боя.

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

Проблема 1. Построение и использование сверхбольших моделей поверхностей.

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

Основные классические результаты в области построения и анализа триангуляционных моделей данных получили Дж. Бентли, Г.Ф. Вороной, Б.Н. Делоне, Д. Киркпатрик, Р. Липтон, Ф. Препарата, Д. Роджерс, Р. Тарьян, М. Шей-мос. Самые современные и комплексные исследования в области построения и обработки триангуляционных моделей данных проведены в работах A.B. Скворцова.

Проблема 2. Эффективная обработка и визуализация сверхбольших моделей поверхностей. ■ • •

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

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

Большой вклад в решение задачи разработки высокоэффективных алгоритмов обработки больших поверхностей внесли Е. Пуппо, Л. Дс Флориани, П. Магилло, К. Де Берг, П. Сигнони, Р. Клейн, Дж. Кохен, П. Хекберт, М. Гарланд, X. Хоппе и др.

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

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

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

1. Исследование существующих методов моделирования поверхностей.

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

3. Разработка модуля трёхмерной визуализации данных графических систем классов ГИС и САПР внедрение его в коммерческие САПР 1пс1огСАВ и ГНСМоЮ^.

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

При выполнении диссертационной работы использовались методы вычислительной геометрии, машинной графики, аналитической геометрии, теории сложности алгоритмов, математической статистики.

Научная новизна.

1. Предложен алгоритм построения сверхбольшой триангуляции Делоне, основанный на разбиении всей триангуляции на множество смежных невыпуклых триангуляций Делоне, и позволяющий обрабатывать сверхбольшие объёмы данных по частям, не понижая при этом точности представления поверхности. Доказана трудоёмкость алгоритма О(А') в среднем и 0(ЛЧод/У) в худшем случае.

2. На основе классической мультитриангуляции (МТ) разработана модель данных «кластерная МТ (К-МТ)», граф которой состоит из ряда независимых подграфов (кластеров), что позволяет эффективно (быстро и с низкими затратами оперативной памяти) строить МТ и выполнять локальные модификации триангуляционной модели поверхности.

3. На основе кластерной МТ разработана модель данных «блочно-кпастерная МТ (БК-МТ)», каждый кластер которой состоит из блоков, последовательно детализирующих локальные участки модели поверхности, что позволяет решить задачу анализа и визуализации сверхбольших моделей поверхностей, загружая и выгружая из памяти блоки БК-МТ.

4. Для блочно-кластерной МТ предложен алгоритм управления памятью, контролирующий загрузку и выгрузку блоков БК-МТ согласно заданному критерию детализации извлекаемой поверхности и в зависимости от объёма доступной оперативной памяти.

5. Предложен алгоритм извлечения из МТ топологически связанной триангуляции требуемого уровня детализации, основанный на модифицированной структуре МТ, в которой для каждого треугольника хранятся 3 наиболее вероятных соседних треугольника. Полученный алгоритм имеет трудоёмкость 0{И) в среднем (по сравнению с (^^^¿М) у других известных алгоритмов). Кроме того, алгоритм отличается низкими затратами по оперативной памяти.

6. На основе разработанных алгоритмов впервые предложена комплекс-• ная технология обработки сверхбольших моделей поверхностей от построения

до анализа и визуализации.

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

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

2. Предложенные в работе структуры данных К-МТ и БК-МТ позволяют использовать параллельные вычисления для построения и обработки моделей поверхностей.

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

4. На базе предложенных автором алгоритмов разработан модуль трёхмерной визуализации данных, который может, использоваться в графических системах классов ГИС и САПР. Модуль позволяет реалистично отображать объекты реального мира и эффективно обрабатывать огромные объёмы данных.

Внедрение результатов работы.

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

2. На основе созданных автором алгоритмов разработан модуль трёхмерной визуализации данных, который встроен в коммерческие ГИС ГпёоКНБ и САПР МогСАО.

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

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

2. Кластерная и блочно-кластерная мультитрнангуляция (МТ) и их применение для обработки сверхбольших моделей поверхностей.

3. Асинхронный алгоритм управления степенью загрузки зависимых блоков блочно-кластерной МТ.

4. Алгоритм извлечения из МТ топологически связанной триангуляции.

5. Разработанная совокупность алгоритмов для работы с МТ позволяет решать все основные задачи обработки сверхбольших моделей поверхностей: от построения до анализа и визуализации.

6. Библиотека процедур 1пс1огТпа^иЫюп для моделирования сверхбольших моделей поверхностей и модуль трёхмерной визуализации данных 1п-(1ог\'ш\уегЗО.

Апробация работы.

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

1. XV Международной конференции по компьютерной графике и её приложениям «Графикон-2005» (Новосибирск, 2005).

2. Х1Л1 и Х1ЛН Международных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, 2004,2005).

3. III и IV Всероссийских научно-практических конференциях «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2004,2005).

4. V Всероссийской конференции «Системы и средства автоматизации» (Томск, 2004).

5. VI Научно-практической конференции Тюменского проекта, и научно-исследовательского института нефтяной и газовой промышленности (Тюмень, 2006).

Публикации.

По результатам выполненных исследований автором опубликовано 14 печатных работ, в том числе 1 зарегистрированная программа для ЭВМ и 8 статей, из которых 4 в журналах из списка, рекомендованных ВАК.

Личный вклад.

Основные научные результаты получены автором самостоятельно. Постановка задачи была выполнена автором совместно с научным руководителем. Разработка предложенных алгоритмов и экспериментальное моделирование их работы была проведена единолично. Внедрение разработанных алгоритмов в САПР МогСАГ) и ГИС 1т1огС18 было произведено автором совместно с научным руководителем и Петренко Д.А.

Структура диссертации.

Работа состоит из введения, 4 глав, заключения, списка литературы и приложения, включающего 1 документ о внедрении. Общий объём работы составляет 130 страниц, из них 2 страницы — приложение, 14 страниц — список литературы (114 названий). Текст работы иллюстрируется 50 рисунками и 7 таблицами.

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

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

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

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

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

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

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

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

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

Рис, 1. Схема взаимодействия алгоритмов построения сверхбольших триангуляционных моделей поверхностей

1. Алгоритм построения смежных триангуляций Делоне.

2. Алгоритм построения модифицированной мультитриангуляции по каждой смежной триангуляции (не обязательно обладающей свойством Делоне).

3. Алгоритм асинхронного управления загрузкой блоков блочно-кластерной МТ.

Далее рассмотрим все предлагаемые алгоритмы более подробно.

Алгоритм 1. Построение смежных триангуляций Делоне.

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

Рассмотрим этот алгоритм в варианте N = 2, т.е. когда исходное множество точек необходимо разделить на две части (для случаев N >2 алгоритм легко обобщается).

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

Входные данные: Множество точек Р.

Выходные данные-. Смежные триангуляции 7] и Тг.

Шаг 1. Исходное множество Р делится на две части Р[ и Р2 вертикальной или горизонтальной прямой так, чтобы в каждой из частей было примерно равное число точек.

Шаг 2. Находятся минимальные ограничивающие прямоугольники Вх и В2 множеств Р1 и Р2 соответственно.

Шаг 3. Во множество Р{ добавляются две точки из В2, сопредельные с В1 (рис. 2). Добавленным точкам выставляется пометка «1», По множеству строится триангуляция Г,.

Шаг 4. Для всех треугольников 7], у которых есть узлы с пометкой «1», запускается следующая рекурсивная процедура проверки:

Шаг 4.1. Рассчитывается расстояние й от центра описанной окружности треугольника до прямой, образованной точками Вг, сопредельными с В1, а также вычисляется центр и радиус описанной окружности Л.

Шаг 4.2. Если £> < Л, следовательно, треугольник может быть перестроен в результате добавления точек из Р2, поэтому непомеченным узлам треугольника, устанавливается пометка «2», после чего они добавляются в Р2.

Шаг 4.3. Процедура рекурсивно вызывается для соседних треугольников.

Шаг 4.4. Сам треугольник удаляется.

Шаг 5. По множеству Р2 строится триангуляция Г2.

Шаг 6. Из 7г удаляются треугольники, которые пересекаются с Тх.

Конец алгоритма.

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

Тем не менее, эта возможность обработки обманчива. Обработка такой огромной модели займёт слишком много времени в реальных условиях. К тому же это не всегда оправдано, особенно в следующих двух случаях: 1) необходимо обработать только часть поверхности (например, построить изолинии только на небольшом участке поверхности), либо 2) необходимо обработать всю поверхность, но с заданным качеством. Так во втором случае часто нужно построить изолинии для всей модели поверхности с определенной точностью (например, для отображения карты в мелком масштабе). Для этого обычно строятся изолинии максимальной точности, которые затем упрощаются до необходимого уровня (кстати, при таком упрощении могут возникнуть и серьезные семантические ошибки, например, пересечение изолиний). В обоих этих случаях трудоёмкость обработки пропорциональна размеру всей триангуляционной модели. Именно поэтому автором был предложен усовершенствованный вариант этой модели, основанный на мультитриангуляционном подходе, позволяющий извлекать из мультитриангуляции и затем обрабатывать относительно небольшие триангуляции, размер которых пропорционален получаемому результату (например, общему числу точек в построенных изолиниях). Это позволяет существенно снизить трудоёмкость обработки. Кроме того, это позволяет избежать семантических ошибок при построении изолиний, т.к. изолинии строятся по уже упрощенной модели поверхности, и отсутствует этап их независимого упрощения.

Алгоритм 2. Кластерная и блочно-кластерная МТ.

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

Алгоритм построения кластерной МТ.

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

Шаг 2. Внутри каждой триангуляции строятся кластеры К-МТ любым известным алгоритмом построения МТ.

Шаг 3. Из оставшейся триангуляции путём упрощения до самого грубого фрагмента строится основная часть К-МТ. Конец алгоритма.

Таким образом, на выходе алгоритма получится структура К-МТ, схематично изображённая на рис, 3. Как видно из рисунка, получается несколько частей: основная часть и кластеры МТ, которые можно загружать или выгружать независимо друг от друга.

Рис. 3. Структура кластерной мультитриангуляции (К-МТ)

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

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

На основании проведённого автором экспериментального моделирования работы алгоритма на различных законах распределения исходных точек получена формула для расчета оптимального числа кластеров для сбалансированной К-МТ.

СС(Л0 =

I

--1,866 + 13,732 383

где СС(М) — число кластеров для заданного числа узлов N (№> 1000) исходной триангуляции, а — округление до ближайшего целого вверх.

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

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

Кластер К-МТ Кластер БК-МТ

Рис. 4. Разбиение кластера К-МТ на блоки

Алгоритм 3. Управление оперативной памятью БК-МТ.

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

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

Таким образом, при обращении к нижнему фрагменту треугольника необходимо загрузить блок, в котором он лежит, что, в свою очередь, может потребовать загрузки всех родительских блоков. Особенностью алгоритма загрузки БК-МТ, предлагаемого автором, является то, что БК-МТ загружается по

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

В связи с тем, что БК-МТ может иметь размеры большие, чем доступная оперативная память, то в какой-то момент для загрузки очередного блока возникнет необходимости освободить память, занимаемую другим блоком. Стандартным приёмом в таком случае является выгрузка блока, который дольше всех остальных не был затребован. Однако особенностью БК-МТ является то, что все блоки образуют некоторый граф зависимостей друг от друга, а потому не каждый блок можно выгрузить, не нарушив структуру данных БК-МТ.

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

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

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

Автором предлагается следующее решение данной проблемы.

Предложение 1: хранить для каждого треугольника ссылки на 3 самых вероятных соседних треугольника.

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

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

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

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

Предложение 2: хранить для каждого треугольника ссылки на 3 верхних и 1 нижний треугольник.

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

В четвёртой главе приводится архитектура разработанного модуля визуализации трёхмерных данных 1п<1огУ1е\уегЗО, основанного на библиотеке МогТпагщЫаСюп, в которую включены предлагаемые автором алгоритмы построения и обработки сверхбольших моделей поверхностей.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведено комплексное исследование существующих подходов к моделированию1 поверхностей. Особое внимание уделено методам построения, анализа и визуализации моделей поверхностей на основе триангуляции Делоне и мультитриангуляции (МТ). Выявлены недостатки существующих алгоритмов, препятствующие их использованию для моделирования сверхбольших поверхностей.

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

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

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

5. Разработанные автором алгоритмы включены в коммерческую библиотек;/ процедур IndorTriangulation, предназначенную для использования в графических системах, имеющих дело с большими размерами моделируемых поверхностей, в первую очередь, в системах классов ГИС и САПР

6. Специально для использования в системах ГИС и САПР автором был разработан коммерческий модуль трёхмерной визуализации данных Indor-Viewer3D, построенный на основе библиотеки IndorTriangulation и объектно-ориентированных моделей объектов. Модуль выполнен в среде Delphi7 с использованием технологий ActiveX на базе DirectX.

7. Выполнено подключение разработанного модуля трёхмерной визуализации IndorViewer3D к системе автоматизированного проектирования объектов транспортного, промышленного и гражданского строительства IndorCAD 6.0 и к геоинформационной системе IndorGIS 6.0, разработанных в ООО «Индор-Софт» (г. Томск). Подключенный модуль прошел тестирование на реальных проектах, выполняемых многими проектными организациями Российской Федерации, Украины и Казахстана.

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Мирза Н.С. Построение смежных триангуляций Делоне И Вестник ТГУ, Приложение, 2006, № 16, март, с. 162-165.

2. Мирза Н.С., Скворцов A.B., Чаднов Р.В. Визуализация сверхбольших поверхностей // Вестник ТГУ, 2006, № 290, март, с. 267-271.

3. Мирза Н.С., Петренко Д.А., Скворцов A.B. Технология трёхмерной визуализации данных ГИС и САПР IndorViewer3D // Вестник ТГУ, 2006, № 290, март, с. 263—267.

4. Петренко Д.А., Мирза Н.С., Скворцов A.B. Взаимодействие объектов в системе автоматизированного проектирования IndorCAD // Вестник ТГУ, 2006, № 290, март, с. 271-275.

5. Мирза Н.С., Скворцов A.B., Соболев В.А. Мулктитриангуляция // Информационные системы. Вып. 3.: Труды Постоянно действующей научно-технической школы-семинара студентов, аспирантов и молодых специалистов «Информационные системы мониторинга окружающей среды», сент.-окт. 2004 г. - Томск: Изд-во ТУСУР, с. 62-69.

6. Мирза Н.С., Скворцов A.B., Чаднов Р.В. Упрощение триангуляционных поверхностей // Теоретическая и прикладная информатика / Под ред. проф. А. Ф. 'Герпугова. Вып. 1. - Томск: Изд-во Том. ун-та, 2004, с. 50-61.

7. Петренко Д.А., Куленов P.O., Мирза Н.С., Субботин С.А., Скворцов A.B. Линейка программных продуктов IndorCAD // Теоретическая и прикладная информатика / Под ред. проф. А. Ф. Терпугова. Вып. 1. — Томск: Изд-во Том. унта, 2004, с. 85-100.

8. Мирза Н.С., Скворцов A.B., Чаднов Р.В. Применение мультитриангуляции для визуализации сверхбольших поверхностей // Труды 15-й международной конференции по компьютерной графике и её приложениям «Графикон-2005» - Новосибирск: Институт вычислительной математики и геофизики. СО РАН, 2005, с. 250-254.

9. Мирза Н.С., Чаднов Р.В. Триангуляция Делоне переменного разрешения // Материалы XLII Международной студенческой конференции «Студент и научно-технический прогресс»: Информационные технологии. - Новосибирск: Новосиб. гос. ун-т, 2004, с. 13-14.

10. Мирза Н.С., Чаднов Р.В., Псахье Н.С. Трёхмерная визуализация данных САПР // Материалы V Всероссийской конференции «Системы и средства автоматизации»: Алгоритмы и программное обеспечение - Томск: Изд-во ТУСУР,

2004, с. 115.

11. Мирза Н.С., Скворцов A.B., Чаднов Р.В. Построение мультитриангуляции // Материалы III Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование». Новые информационные технологии - достижения и перспективы, Анжеро-Судженск. -Томск: Изд-во Том. ун-та, 2004, с. 82-84.

12. Мирза Н.С., Чаднов Р.В. Генерализация поверхности // Материалы XLIII Международ, науч. студен, конф. «Студент и научно-технический прогресс»: Информационные технологии. — Новосибирск: Изд-во Новосиб. гос. ун-та,

2005, с. 41-42.

13. Мирза Н.С. Построение смежных триангуляции Делоне // Материалы IV Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование». Численные методы и комплексы программ, Анжеро-Судженск. - Томск: Изд-во Том. ун-та, 2005, с. 57-60.

14. Бойков В.Н., Петренко Д.А., Мирза Н.С., Перфильев A.B., Скворцов A.B. Система автоматизированного проектирования объектов промышленного, гражданского и транспортного строительства IndorCAD. — М.: ВНТИЦ, 2006. -Свидетельство о регистрации в отраслевом фонде алгоритмов и программ Министерства образования и науки РФ № 50200600304.

Заказ 507. Тираж 100. Томский государственный университет систем управления и радиоэлектроники 634050, г. Томск, пр. Ленина, 40

Введение.

Ф Глава 1. Моделирование поверхностей.

1.1. Введение.

1.2. Исходные данные для построения моделей поверхности.

1.3. Методы моделирования поверхностей.

1.4. Триангуляция.

1.4.1. Определения.

1.4.2. Структуры данных для представления триангуляции.

1.4.3. Проверка условия Делоне.

1.4.4. Построение триангуляции Делоне.

1.5. Моделирование больших поверхностей.

Ф 1.5.1. Упрощение триангуляции.

1.5.2. Триангуляция переменного разрешения.

1.6. Моделирование сверхбольших поверхностей.

1.7. Выводы.

Глава 2. Построение и визуализация сверхбольших моделей поверхностей.

2.1. Схема работы алгоритмов.

2.2. Построение смежных триангуляций Делоне.

2.3. Модификация мультитриангуляции.

2.3.1. Общая идея.

2.3.2. Разбиение МТ на части.

2.3.3. Учёт структурных линий.

2.3.4. Разбиение кластера МТ на блоки.

IT 2.3.5. Разбиение исходной триангуляции на части.

2.4. Построение сверхбольшой мультитриангуляции. л 2.5. Управление оперативной памятью.

-32.6. Визуализация сверхбольшой МТ.

2.7. Экспериментальное моделирование.

2.7.1. Условия эксперимента.

2.7.2. Выбор числа кластеров для сбалансированной К-МТ.

2.7.3. Построение БК-МТ.

2.7.4. Визуализация сверхбольшой БК-МТ.

2.7.5. Критерий визуализации БК-МТ.

2.8. Выводы.

Глава 3. Анализ сверхбольших моделей поверхностей.

3.1. Постановка задачи.

3.2. Существующие решения.

3.3. Восстановление топологической информации из МТ.

3.3.1. Изменение структуры МТ.

3.3.2. Извлечение топологической информации.

3.4. Восстановление топологии из сверхбольшой МТ.

3.5. Экспериментальное моделирование.

3.5.1. Условия эксперимента.

3.5.2. Оценка числа вырожденных случаев.

3.5.3. Быстродействие алгоритма.

3.6. Выводы.

Ф Глава 4. Модуль трёхмерной визуализации IndorViewer3D.

4.1. Системы трёхмерного моделирования.

4.1.1. Введение.

4.1.2. Данные ГИС и САПР.

4.1.3. Обзор существующих систем трёхмерной визуализации.

4.2. IndorViewer3D.

4.2.1. Архитектура IndorViewer3D.

4.2.2. Навигация в IndorViewer3D. ф 4.2.3. Обмен данными с ГИС и САПР.

-44.2.4. Применение IndorViewer3D в системе IndorCAD/Road.

4.2.5. Применение IndorViewer3D в системе IndorGIS.

4.3. Выводы.

Актуальность. На сегодняшний день задачи построения и визуализации больших трёхмерных моделей открытых участков местности (крупномасштабных моделей городов и протяжённых объектов транспортного, промышленного и гражданского строительства; любых мелкомасштабных моделей территорий) находят широкое применение в самых различных областях человеческой деятельности: для анализа пространственных данных, при проектировании объектов строительства, при обучении лётчиков на компьютерных тренажёрах-симуляторах, в индустрии развлечений (создание компьютерных игр и видеофильмов) и военных целях для моделирования обстановки на поле боя.

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

Проблема 1. Построение и использование сверхбольших моделей поверхностей.

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

Основные классические результаты в области построения и анализа триангуляционных моделей данных получили Дж. Бентли, Г.Ф. Вороной, Б.Н. Делоне, Д. Киркпатрик, Р. Липтон, Ф. Препарата, Д. Роджерс, Р. Тарьян, М. Шей-мос. Самые современные и комплексные исследования в области построения и обработки триангуляционных моделей данных проведены в работах А.В. Скворцова.

Проблема 2. Эффективная обработка и визуализация сверхбольших моделей поверхностей.

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

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

Большой вклад в решение задачи разработки высокоэффективных алгоритмов обработки больших поверхностей внесли Е. Пуппо, JI. Де Флориани, П. Магилло, К. Де Берг, П. Сигнони, Р. Клейн, Дж. Кохен, П. Хекберт, М. Гарланд, X. Хоппе и др.

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

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

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

1. Исследование существующих методов моделирования поверхностей.

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

3. Разработка модуля трёхмерной визуализации данных графических систем классов ГИС и САПР внедрение его в коммерческие САПР IndorCAD и ГИС IndorGIS.

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

При выполнении диссертационной работы использовались методы вычислительной геометрии, машинной графики, аналитической геометрии, теории сложности алгоритмов, математической статистики.

Научная новизна.

1. Предложен алгоритм построения сверхбольшой триангуляции Делоне, основанный на разбиении всей триангуляции на множество смежных невыпуклых триангуляций Делоне, и позволяющий обрабатывать сверхбольшие объёмы данных по частям, не понижая при этом точности представления поверхности. Доказана трудоёмкость алгоритма 0(N) в среднем и 0(N\ogN) в худшем случае.

2. На основе классической мультитриангуляции (МТ) разработана модель данных «кластерная МТ (К-МТ)», граф которой состоит из ряда независимых подграфов {кластеров), что позволяет эффективно (быстро и с низкими затратами оперативной памяти) строить МТ и выполнять локальные модификации триангуляционной модели поверхности.

3. На основе кластерной МТ разработана модель данных «блочно-кластерная МТ (БК-МТ)», каждый кластер которой состоит из блоков, последовательно детализирующих локальные участки модели поверхности, что позволяет решить задачу анализа и визуализации сверхбольших моделей поверхностей, загружая и выгружая из памяти блоки БК-МТ.

4. Для блочно-кластерной МТ предложен алгоритм управления памятью, контролирующий загрузку и выгрузку блоков БК-МТ согласно заданному критерию детализации извлекаемой поверхности и в зависимости от объёма доступной оперативной памяти.

5. Предложен алгоритм извлечения из МТ топологически связанной триангуляции требуемого уровня детализации, основанный на модифицированной структуре МТ, в которой для каждого треугольника хранятся 3 наиболее вероятных соседних треугольника. Полученный алгоритм имеет трудоёмкость 0(N) в среднем (по сравнению с 0(N\ogN) у других известных алгоритмов). Кроме того, алгоритм отличается низкими затратами по оперативной памяти.

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

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

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

2. Предложенные в работе структуры данных К-МТ и БК-МТ позволяют использовать параллельные вычисления для построения и обработки моделей поверхностей.

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

4. На базе предложенных автором алгоритмов разработан модуль трёхмерной визуализации данных, который может использоваться в графических системах классов ГИС и САПР. Модуль позволяет реалистично отображать объекты реального мира и эффективно обрабатывать огромные объёмы данных.

Внедрение результатов работы.

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

2. На основе созданных автором алгоритмов разработан модуль трёхмерной визуализации данных, который встроен в коммерческие ГИС IndorGIS и САПР IndorCAD.

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

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

2. Кластерная и блочно-кластерная мультитриангуляция (МТ) и их применение для обработки сверхбольших моделей поверхностей.

3. Асинхронный алгоритм управления степенью загрузки зависимых блоков блочно-кластерной МТ.

4. Алгоритм извлечения из МТ топологически связанной триангуляции.

-105. Разработанная совокупность алгоритмов для работы с МТ позволяет решать все основные задачи обработки сверхбольших моделей поверхностей: от построения до анализа и визуализации.

6. Библиотека процедур IndorTriangulation для моделирования сверхбольших моделей поверхностей и модуль трёхмерной визуализации данных 1п-dorViewer3D.

Апробация работы.

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

1. XV Международной конференции по компьютерной графике и её приложениям «Графикон-2005» (Новосибирск, 2005).

2. XLII и XLIII Международных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, 2004, 2005).

3. III и IV Всероссийских научно-практических конференциях «Информационные технологии и математическое моделирование» (Анжеро-Судженск, 2004, 2005).

4. V Всероссийской конференции «Системы и средства автоматизации» (Томск, 2004).

5. VI Научно-практической конференции Тюменского проектн. и научно-исследовательского института нефтяной и газовой промышленности (Тюмень, 2006).

Публикации.

По результатам выполненных исследований автором опубликовано 14 печатных работ, в том числе 1 зарегистрированная программа для ЭВМ и 8 статей, из которых 4 в журналах из списка, рекомендованных ВАК.

Личный вклад.

Основные научные результаты получены автором самостоятельно. Постановка задачи была выполнена автором совместно с научным руководителем.

Разработка предложенных алгоритмов и экспериментальное моделирование их работы была проведена единолично. Внедрение разработанных алгоритмов в САПР IndorCAD и ГИС IndorGIS было произведено автором совместно с научным руководителем и Петренко Д.А.

Структура диссертации.

Работа состоит из введения, 4 глав, заключения, списка литературы и приложения, включающее 1 документ о внедрении. Общий объём работы составляет 130 страниц, из них 2 страницы - приложение, 14 страниц - список литературы (114 названий). Текст работы иллюстрируется 50 рисунками и 7 таблицами.

-1144.3. Выводы

1. В п. 4.1 рассмотрены существующие системы трёхмерной визуализации больших объёмов данных. Выявлены их достоинства и недостатки.

2. В п. 4.2 описана архитектура разработанного автором модуля трёхмерной визуализации данных IndorViewer3D, который отличается от известных систем возможностью визуализации сверхбольших моделей рельефа в режиме реального времени, что особенно актуально для систем класса ГИС и САПР.

3. Выполнено подключение разработанного модуля трёхмерной визуализации IndorViewer3D к системе автоматизированного проектирования объектов транспортного, промышленного и гражданского строительства IndorCAD 6.0 и к геоинформационной системе IndorGIS 6.0, разработанных в ООО «Индор-Софт» (г. Томск). Подключенный модуль прошел тестирование на реальных проектах, выполняемых многими проектными организациями Российской Федерации, Украины и Казахстана (ООО «ИДЦ Индор», ООО «КазДорПроект» и

ДР-)

-115

ЗАКЛЮЧЕНИЕ

Далее приводятся обобщённые выводы представленные по главам:

1. Проведено комплексное исследование существующих подходов к моделированию поверхностей. Особое внимание уделено методам построения, анализа и визуализации моделей поверхностей на основе триангуляции Делоне и мультитриангуляции (МТ). Выявлены недостатки существующих алгоритмов, препятствующие их использованию для моделирования сверхбольших поверхностей.

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

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

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

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

6. Специально для использования в системах ГИС и САПР автором был разработан коммерческий модуль трёхмерной визуализации данных IndorViewer3D, построенный на основе библиотеки IndorTriangulation и объектно-ориентированных моделей объектов. Модуль выполнен в среде Delphi7 с использованием технологий ActiveX на базе DirectX.

-1167. Выполнено подключение разработанного модуля трёхмерной визуализации IndorViewer3D к системе автоматизированного проектирования объектов транспортного, промышленного и гражданского строительства IndorCAD 6.0 и к геоинформационной системе IndorGIS 6.0, разработанных в ООО «Индор-Софт» (г. Томск). Подключенный модуль прошел тестирование на реальных проектах, выполняемых многими проектными организациями Российской Федерации, Украины и Казахстана.

1. Мирза Н.С. Построение смежных триангуляций Делоне // Вестник ТГУ, Приложение, 2006, № 16, март, с. 162-165.

2. Мирза Н.С., Петренко Д.А., Скворцов А.В. Технология трёхмерной визуализации данных ГИС и САПР IndorViewer3d // Вестник ТГУ, 2006, № 290, март, с. 263-267.

3. Мирза Н.С., Скворцов А.В., Чаднов Р.В. Визуализация сверхбольших поверхностей // Вестник ТГУ, 2006, № 290, март, с. 267-271.

4. Мирза Н.С., Скворцов А.В., Чаднов Р.В. Упрощение триангуляционных поверхностей // Теоретическая и прикладная информатика / Под ред. проф. А. Ф. Терпугова. Томск: Изд-во Том. ун-та, 2004. - Вып. 1, с. 50-61.

5. Мирза Н.С., Чаднов Р.В. Генерализация поверхности // Материалы XLIII Международ, науч. студен, конф. «Студент и научно-технический прогресс»: Информационные технологии. — Новосибирск: Изд-во Новосиб. гос. ун-та, 2005, с. 41-42.

6. Мирза Н.С., Чаднов Р.В. Триангуляция Делоне переменного разрешения // Материалы XLII Международной студенческой конференции «Студент и научно-технический прогресс»: Информационные техноф логии. Новосибирск: Новосиб. гос. ун-т, 2004, с. 13-14.

7. Мирза Н.С., Чаднов Р.В., Псахье Н.С. Трёхмерная визуализация данных САПР // Материалы V Всероссийской конференции «Системы и средства автоматизации»: Алгоритмы и программное обеспечение -Томск: Изд-во ТУ СУР, 2004, с. 115.

8. Петренко Д.А., Мирза Н.С., Скворцов А.В. Взаимодействие объектов в * системе автоматизированного проектирования IndorCAD // Вестник

9. ТГУ, 2006, № 290, март, с. 271-275.-11915. Скворцов А.В. Геоинформационная система IndorGIS 5.0. Томск: ООО «ИндорСофт», 2004. - 350 с.

10. Скворцов А.В. Построение сверхбольшой триангуляции Делоне // Изв. ф вузов. Физика, 2002, №6, с. 22-25.

11. Скворцов А.В. Триангуляция Делоне и её применение. Томск: Изд-во Том. ун-та, 2002. - 128 с.

12. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том. ун-та, 1998. С. 22-41.

13. Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. М.: ДИАЛОГ-МИФИ, 1996.-240 с.к

14. Algorri М.Е., Schmitt F. Mesh simplification 11 Computer Graphics Forum (Eurographics'96 Proc.), 1996, Vol. 15, No. 3, pp. 78-86.

15. Alliez P., Desbrun M. Progressive encoding for lossless transmission of 3D meshes //SIGGRAPH 2001 Conference Proceedings, pp. 195-202.

16. Alliez P., Desbrun M. Valence-driven connectivity encoding of 3D meshes // Eurographics 2001 Conference Proceedings, pp. 480^189.

17. Andrews D.S. Simplifying terrain models and measuring terrain model accuracy / Msc. Thesis. Tech. Report 96-05, Dept. of CS, UBC, 1996, 55 p.

18. Andujar C., Ayala D., Brunet P., Joan-Arinyo R., Sole J. Automatic genera-ф tion of multiresolutionboundary representations // Computer Graphics Forum (Eurographics'96 Proc.), 1996, Vol. 15, No. 3, pp. 87-96.

19. Bajaj C.L., Schikore D.R. Error bounded reduction of triangle meshes with multivariate data // SPIE, 1996, Vol. 2656, pp. 34-45.

20. Brown P.J.C. A fast algorithm for selective refinement of terrain meshes // COMPUGRAPHICS 96, GRASP, 1996, pp. 70-82. (Technical Report No. 417, Computer Laboratory, Cambridge University, CB2 3QG, UK, February 1997).

21. Catmull E., Clark J. Recursively generated B-Spline surfaces on arbitrary topological meshes // Computer Aided Design, 1978, Vol. 10, No. 6, pp. 350-355.

22. Certain, A., Popovic, J., Duchamp, Т., Salesin, D., Stuetzle, W., DeRose T. Interactive multiresolution surface viewing. Computer Graphics (SIGGRAPH'96 Proceedings), 1996, pp. 91-98.

23. Ciampalini A., Cignoni P., Montani C., Scopigno R. Multiresolution decimation based on global error // The Visual Computer, 1997, June, Vol. 13, No. 5, pp. 228-246.

24. Cignoni P., De Floriani L., Montani C., Puppo E., Scopigno R. Multiresolu-tional modeling and visualization of volume data based on simplicial complexes // Proc. Symp. On Volume visualization. Tysons Corner. Virginia. United States, 1994, pp. 19-26.

25. Cignoni P., Montani C., Puppo E., Scopigno R. Multiresolution modeling and visualization of volume data // IEEE Transactions on Visualization andф Computer Graphics, 1997, Vol. 3, No. 4, pp. 352-369.

26. Cignoni P., Montani C., Scopigno R.A. Comparison of mesh simplification algorithms // Computer & Graphics, 1998, Vol. 22, No. 1, pp. 37-54.

27. Cignoni P., Rocchini C., Scopigno R. Metro: measuring error on simplified surfaces // Computer Graphics Forum, 1998, Vol. 17? No. 2, pp.167-174.

28. Clark J. Hierarchical geometric models for visible surface algorithms // * Communications of the ACM 19,1976, October, No. 10, pp. 547-554.

29. Cohen J., Varshney A., Manocha D., Turk G., Weber H., Agarwal P., Brooks F., Wright W. Simplification envelopes // Computer Graphics (SIGGRAPH '96 Proceedings), 1996, pp. 119-128.

30. Cohen-Or D., Rich E., Lerner U., Shenkar V. A real-time photo-realistic visual flythrough // IEEE Transaction on Visualization and Computer Graphics, 1996, Vol. 2., No. 3, September, pp. 255-264.

31. Danovaro E., De Floriani L., Magillo P., Puppo E. Data structures for 3D multi-tessellations: an overview / Technical Report DISI-TR-02-01, Department of Computer and Information Science, University of Genova (Italy), 2002. -17 p.

32. De Berg M., Dobrindt K. On levels of detail in terrains // Proceedings of the eleventh annual symposium on Computational geometry, June 05-07, 1995, pp. 26-27.

33. De Floriani L., Falcidieno В., Pienovi C., Nagy G. A hierarchical data structure for surface approximation // Computer Graphics, 1984, Vol. 8, No. 2, pp. 475-484.

34. De Floriani L., Magillo P. Regular and Irregular MultiResolution Terrain Models: a Comparison // ACM 10th international symposium on Advances in geographic information systems Proceedings, McLean, Virginia, USA, 2002, pp. 143-148.

35. De Floriani L., Magillo P. Visibility Computations on Hierarchical Triangulated Terrain Models // Geoinformatica, 1997, No. I, pp. 219-250.

36. De Floriani L., Magillo P., Puppo E. Building and traversing a surface at variable resolution // Proc. Conf. On Visualization '97,1997, pp. 18-24.

37. De Floriani L., Magillo P., Puppo E. Data structures for simplicial multi-complexes // Lecture Notes in Computer Science, 1999, Vol. 1651, pp. 3351.

38. De Floriani L., Magillo P., Puppo E., Bertolotto M. Variable resolution operators on a multiresolution terrain model // ACM 4th Workshop on Advances in Geographic Information Systems, 1996, pp. 123-130.

39. De Floriani L., Marzano P., Puppo E. Hierarchical terrain models: survey and formalization // Proceedings SAC'94, Phoenix (AR), March 1994, pp. 323-327.

40. De Floriani L., Marzano P., Puppo E. Multiresolution Models for Topographic Surface Description // The Visual Computer, 1996, Vol. 12, No. 7, pp. 317-345.

41. De Floriani L., Puppo E. Hierarchical triangulation for multiresolution surface description // ACM Trans, on Graphics, 1995, Vol. 14, No. 4, pp. 363411.

42. De Floriani L., Puppo E., Magillo P. A formal approach to multiresolution hypersurface modeling // Geometric Modeling: Theory and Practice, Springer-Verlag, 1997, pp. 302-323.

43. De Haemer M.J., Zyda M.J. Simplification of objects rendered by polygonal approximations // Computers & Graphics, 1991, Vol. 15, No. 2, pp. 175-184.

44. Duchaineau M., Wolinsky M., Sigeti D., Miller M., Aldrich C., Mineed-Weinstein M. ROAMing terrain: Real-time optimally adapting meshes // Proceedings IEEE Visualization'97,1997, pp. 81-88.

45. Eck M., De Rose Т., Duchamp Т., Hoppe M., Lounsbery M., Stuetzle W. Multiresolutional analysis of arbitrary meshes // Computer Graphics Proceedings, 1995, pp. 173-181.

46. Erikson C. Polygonal simplification: An overview / Technical Report TR96-016, Department of Computer Science, University of North Carolina, 1996, February 16. Chapel Hill. - 33 p.

47. Evans W., Kirkpatrick D., Townsend G. Right-triangulated irregular networks // Algorithmica, 2001, pp. 264-286.

48. Falby J.S., Zyda M.J., Pratt D.R., Mackey R.L. NPSNET: Hierarchical datastructures for real-time three-dimensional visual simulation // Computersand Graphics, January-February 1993, Vol. 17, No. 1, pp. 65-69.

49. Ferguson R.L., Economy R., Kelley W.A., Ramos P.P. Continuous terrain level of detail for visual simulation // Proceedings of the 1990 Image V Conference, Image Society, Tempe, AZ, June 1990, pp. 145-151.

50. Fowler R.J., Little J.J. Automatic extraction of irregular network digital terrain models // Computer Graphics, August 1979, Vol. 13, No. 3, pp. 199207.

51. Funkhouser T.A., Sequin C.H. Adaptive display algorithm for interactiveframe rates during visualization of complex virtual environments // Computer Graphics, 27(Annual Conference Series), 1993, pp. 247-254.

52. Garland M., Heckbert P. Surface simplification using quadric error metrics // Computer Graphics Proceedings, 1997, Vol. 31, pp. 209-216.

53. Gerstner T. Multiresolution visualization and compression of global topographic data // Spatial Data Handling, IGU/GISc, 2000, pp. 14-27.

54. Guibas L., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams // ACM Transactions on Graphics, 1985, Vol. 4, No. 2, pp. 74-123.

55. Hamann B. A data reduction scheme for triangulated surfaces // Computer

56. Symbolic Computation, 1994, Vol. 17, pp. 457^72.

57. Heckbert P., Garland M. Multiresolution Modeling for Fast Rendering // Graphics Interface '94 Proceedings, 1994, pp. 43-50.

58. Hoppe H. Progressive Meshes // Computer Graphics, 1996, pp. 99-108.

59. Hoppe H. Smooth view-dependent level-of-detail control and its application to terrain rendering // Proceedings IEEE Visualization'98, IEEE Computer Society, 1998, pp. 35^2.

60. Hoppe H. View-dependent refinement of progressive meshes // Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH), ACM Press, 1997, pp. 189-198.

61. Hoppe H., De Rose Т., Duchamp Т., McDonald J. Stuetzle W. Mesh Optimization // Computer Graphics Proceedings. 1993, pp. 19-26.

62. Hoppe H., DeRose Т., Duchamp Т., Halstead M., Jin H., McDonald J., Schweitzer J., Stuetzle W. Piecewise smooth surface reconstruction // SIGGRAPH'94 Conference Proceedings, 1994, pp. 295-302.

63. Klein R., Huettner T. Simple camera-dependent approximation of terrain surfaces for fast visualization and animation // Visualization 96, ACM, November 1996, pp. 20-25.

64. Klein R., Huettner T. Generation of multiresolution models from CAD ^ data// Theory and Practice of Geometric Modeling, (Blaubeuren II),

65. Spinger-Verlag, 1997, pp. 324-334.-12580. Klein R., Liebich G., Straber W. Mesh reduction with error control // Visualization Proceedings, 1996, pp. 311-318.

66. Lawson C. Software for C1 surface interpolation // Mathematical Software III, NewYork, Academic Press, 1977, pp. 161-194.

67. Lee J. Comparison of existing methods for building triangular irregular network models of terrain from grid digital elevation models // Int. Journal of GIS, 1991, Vol. 5, No. 3, pp. 267-285.

68. Lee M., De Floriani L., Samet H. Constant-time neighbor finding in hierarchical meshes // International Conference on Shape Modeling, Genova (Italy), May 7-11 2001, pp. 286-295.

69. Lee M., Samet H. Navigating through triangle meshes implemented as linear quadreees // ACM Trans, on Graphics, 2000, Vol. 19, No. 2, pp. 79121.

70. Lindstrom P., Koller D., Ribarsky W., Hodges L., Faust N., Turner G. Real-^ time, continuous level of detail rendering of height fields // ACM Computer

71. Graphics (SIGGRAPH '96 Proceedings), ACM Press, 1996, pp. 109-118.

72. Lindstrom P., Pascucci V. Visualization of large terrains made easy // IEEE Visualization'01, San Diego, CA, 2001, pp. 363-370.

73. Low K.L., Tan T.S. Model simplification using vertex clustering // ACM Symposium on Interactive 3D Graphics, 1997, pp. 75-82.

74. Luebke D., Erikson C. View-dependent simplification of arbitrary polygo-q nal environments // Computer Graphics Proceedings, Annual Conference

75. Series (SIGGRAPH), ACM Press, 1997, pp. 199-207.

76. Maciel P.W.C., Shirley P. Visual navigation of large environments using textured clusters // Symposium on Interactive 3D Graphics, ACMSIGGRAPH, April 1995, pp. 95-102.

77. Ohlberger M., Rumpf M. Hierachical and adaptive visualization on nested grids // Computing, 1997, Vol. 56, pp. 365-385.

78. Pajarola R. Large scale terrain visualization using the restricted quadtree triangulation // IEEE Visualization'98, Research Triangle Park, NC, IEEE Computer Society, 1998, pp. 19-26.

79. Popovic J., Hoppe H. Progressive simplicial complexes // ACM Computer Graphics Proc., Annual Conference Series, (Siggraph '97), 1997, pp. 217224.

80. Puppo E. Variable resolution triangulations // Computational Geometry, 1998, Vol. 11, pp. 219-238.

81. Puppo E., Scopigno R. Simplification, LOD and multiresolutional principles and applications // EUROGRAPHICS'97, 1997, Vol. 16, No. 3, pp. 14-27.

82. Rabinovich В., Gotsman C. Visualization of large terrains in resource-limited computing environments // IEEE Visualization'97, 1997, October, pp. 95-102.v 98. Reddy M. Scrooge: Perceptually-driven polygon reduction // Computer

83. О Graphics Forum, 1996, Vol. 15, No. 4, pp. 191-203.

84. Renze K.J., Oliver J.H. Generalized unstructured decimation // IEEE Computational Geometry & Applications, 1996, Vol. 16, No. 6, pp. 24-32.

85. Rivara M. Algorithms for refining triangular grids suitable for adaptive and multigrid techniques // International Journal of Numerical Engineering, 1984, Vol. 20, pp. 281-290.

86. Schrack G. Finding neighbors of equal size in linear quadtrees and octrees in constant time // Computer Vision, Graphics, and Image Processing: Image Understanding, 1992, Vol. 55, No. 3, pp. 221-230.

87. Schroeder P. Opportunities for subdivision-based multiresolution modeling // Pacific Graphics 99 Conference Proceedings, 1999, pp. 104-105.

88. Schroeder W., Zarge J., LorensenW. Decimation of triangle meshes // Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH), ACM Press, 1992, pp. 65-70.

89. Sloan S.W. A fast algorithm for constructing Delaunay triangulations in the plane // Adv. Eng. Software, 1987, Vol. 9, No. 1, pp. 34-55.

90. Soucy M., Godin G., Rioux M. A texture-mappping approach for the compression of colored 3d triangulations // The Visual Computer, 1996, No. 12, pp. 503-514.

91. Soucy M., Laurendeau D. Multiresolution surface modeling based on hierarchical triangulation // Computer Vision and Image Understanding, 1996, Vol.63, No. l,pp. 1-14.

92. Turk G. Re-tiling polygonal surfaces // ACM Computer Graphics (SIGGRAPH'92 Proceedings), July 1992, Vol. 26, pp. 55-64.

93. Velho L. Mesh simplification using four-face clusters // International Conference on Shape Modeling, Genova (Italy), 2001, May 7-11, pp. 200-208.

94. Xia J., El-Sana J., Varshney A. Adaptive real-time level-of-detail-based rendering for polygonal models // IEEE Transactions on Visualization and Computer Graphics, 1997, pp. 171-183.