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

• Автор: Мирза, Наталия Сергеевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Томск
• Количество страниц: 130 с. : ил.

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

Ф Глава 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. Разбиение кластера МТ на блоки.
1Г 2.3.5. Разбиение исходной триангуляции на части.
2.4. Построение сверхбольшой мультитриангуляции.
2.5. Управление оперативной памятью.
2.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. Модуль трхмерной визуализации 1пс1огУ1еуегЗО
4.1. Системы трхмерного моделирования
4.1.1. Введение.
4.1.2. Данные ГИС и САПР
4.1.3. Обзор существующих систем трхмерной визуализации
4.2. 1пс1огУ1сусгЗО
4.2.1. Архитектура 1пбогУ1ечусгЗО.
4.2.2. Навигация в 1пс1огУ1сусгЗО.
4.2.3. Обмен данными с ГИС и САПР.
4.2.4. Применение 1пс1огУ1еуегЗО в системе 1пс1огСАПН.оа1.
4.2.5. Применение 1пс1огУуегЗО в системе II
4.3. Выводы
Заключение
Литература


Для блочно-кластерной МТ предложен алгоритм управления памятью, контролирующий загрузку и выгрузку блоков БК-МТ согласно заданному критерию детализации извлекаемой поверхности и в зависимости от объёма доступной оперативной памяти. Предложен алгоритм извлечения из МТ топологически связанной триангуляции требуемого уровня детализации, основанный на модифицированной структуре МТ, в которой для каждого треугольника хранятся 3 наиболее вероятных соседних треугольника. Полученный алгоритм имеет трудоёмкость O(N) в среднем (по сравнению с 0(NogN) у других известных алгоритмов). Кроме того, алгоритм отличается низкими затратами по оперативной памяти. На основе разработанных алгоритмов впервые предложена комплексная технология обработки сверхбольших моделей поверхностей от построения до анализа и визуализации. Теоретическая и практическая ценность. Предложенные в работе структуры данных К-МТ и БК-МТ позволяют использовать параллельные вычисления для построения и обработки моделей поверхностей. Предложенные автором алгоритмы позволяют существенно повысить операционные и функциональные характеристики существующих графических систем, работающих с моделями рельефа (в т. ГИС и САПР), т. На базе предложенных автором алгоритмов разработан модуль трёхмерной визуализации данных, который может использоваться в графических системах классов ГИС и САПР. Модуль позволяет реалистично отображать объекты реального мира и эффективно обрабатывать огромные объёмы данных. Внедрение результатов работы. Разработанные автором алгоритмы включены в коммерческую библиотеку процедур обработки триангуляционных моделей данных 1пс1огТпаг^и1а-’оп, которая предоставляет возможности для решения различных задач, базирующихся на триангуляции и мультитриангуляции. На основе созданных автором алгоритмов разработан модуль трёхмерной визуализации данных, который встроен в коммерческие ГИС 1пс1оЮ и САПР 1пс1огСАО. Алгоритм построения сверхбольшой триангуляции Делоне, состоящей из смежных триангуляций Делоне. Кластерная и блочно-кластерная мультитриангуляция (МТ) и их применение для обработки сверхбольших моделей поверхностей. Асинхронный алгоритм управления степенью загрузки зависимых блоков блочно-кластерной МТ. Алгоритм извлечения из МТ топологически связанной триангуляции. Разработанная совокупность алгоритмов для работы с МТ позволяет решать все основные задачи обработки сверхбольших моделей поверхностей: от построения до анализа и визуализации. Библиотека процедур 1пс1огТпапби1айоп для моделирования сверхбольших моделей поверхностей и модуль трёхмерной визуализации данных 1п-(1огУ]‘еуегЗО. Апробация работы. XV Международной конференции по компьютерной графике и её приложениям «Графикон-» (Новосибирск, ). ХБН и Х1ЛН Международных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, , ). III и IV Всероссийских научно-практических конференциях «Информационные технологии и математическое моделирование» (Анжеро-Судженск, , ). V Всероссийской конференции «Системы и средства автоматизации» (Томск, ). VI Научно-практической конференции Тюменского проектн. Тюмень, ). Публикации. По результатам выполненных исследований автором опубликовано печатных работ, в том числе 1 зарегистрированная программа для ЭВМ и 8 статей, из которых 4 в журналах из списка, рекомендованных ВАК. Личный вклад. Основные научные результаты получены автором самостоятельно. Постановка задачи была выполнена автором совместно с научным руководителем. Разработка предложенных алгоритмов и экспериментальное моделирование их работы была проведена единолично. Внедрение разработанных алгоритмов в САПР 1пс1огСАО и ГИС 1пс1ог5 было произведено автором совместно с научным руководителем и Петренко Д. Структура диссертации. Работа состоит из введения, 4 глав, заключения, списка литературы и приложения, включающее 1 документ о внедрении. Общий объём работы составляет 0 страниц, из них 2 страницы - приложение, страниц - список литературы (4 названий). Текст работы иллюстрируется рисунками и 7 таблицами.