Разработка алгоритмов построения, анализа и визуализации сверхбольших моделей поверхностей на основе мультитриангуляции тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Мирза, Наталия Сергеевна

• Мирза, Наталия Сергеевна
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Мирза, Наталия Сергеевна

Введение.

Ф Глава 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, разработанных в ООО «Индор-Софт» (г. Томск). Подключенный модуль прошел тестирование на реальных проектах, выполняемых многими проектными организациями Российской Федерации, Украины и Казахстана.

Список литературы диссертационного исследования кандидат технических наук Мирза, Наталия Сергеевна, 2006 год

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.