Введение к работе
Актуальность исследования. Моделирование и реалистичная визуализация геоповерхностей является ключевой составляющей многих приложений, среди которых: военные и аэрокосмические тренажеры; системы виртуальных путешествий; ландшафтные и архитектурные редакторы; компьютерные игры; симуляторы наземного транспорта и др. Достижение реалистичности виртуального рельефа при сохранении интерактивной частоты отображения (25 кадров в секунду и более) является основным требованием к подсистеме визуализации подобных приложений.
Разработка эффективных технологий сжатия изображений и другой информации с целью повышения эффективности хранения и передачи, а также методов многомасштабного моделирования объектов различной природы, в том числе и рельефа, отвечающих современному уровню развития вычислительной техники, является активно исследуемой областью как в России, так и за ее пределами. Подтверждением этому является большое количество публикаций, посвященных проблемам сжатия изображений и пространственных данных. Здесь следует отметить работы Ю.Г. Васина, А.В. Кудина, СВ. Жерздева, В.В.Сергеева, В.А.Сойфера, М.Кунта (M.Kunt), Дж. Шапиро (J.Shapiro), А.Саида (A.Said), У.Перельмана (W.Pearlman) и др. Многомасштабным моделям и методам построения адаптивных триангуляции рельефов для их эффективной визуализации также посвящено много работ. В последние годы этой проблемой занимались А.В.Плесков, Ю.Г.Васин, А.В. Переберин, Ю.М. Баяковский, М.В. Михайлюк, П.Линдстром (P. Lindstrom), М.Дюшейн (М. Duchaineau), Х.Хоуп (Н. Норре), и др. Тем не менее, с развитием вычислительной техники быстро растут требования к реалистичности выводимой сцены, увеличиваются объемы данных, задающих рельеф местности.
В многомасштабных моделях рельефа особенно актуальна задача полного использования аппаратных возможностей программируемых графических процессоров и распараллеливания вычислений. Проблемы построения эффективных алгоритмов параллельной обработки нерегулярных иерархических структур данных актуальны не только в рамках задачи визуализации рельефа, но также важны и сами по себе, поскольку находят применение во многих других областях (таких, например, как сжатие изображений).
В последние годы опубликовано множество подходов, которые предлагают решения различных аспектов задач хранения, моделирования и визуализации поверхности. В это же время, наряду с увеличением числа ядер центрального процессора, появилась возможность многократно увеличить производительность вычислений, используя графический сопроцессор компьютера, а значит, появилась возможность для новых информационных решений в моделировании и визуализации геоповерхностей.
Одной из актуальнейших задач является многократное уплотнение представления исходной информации о геоповерхности с целью размещения значительно большего ее объема в оперативной памяти в виде данных, при сохранении возможности обработки закодированных данных в реальном времени. Ре-
зультатом может быть комплексное алгоритмическое решение, сочетающее в себе: сжатое многомасштабное представление исходных данных о рельефе; построение адаптивной триангуляции; полное использование возможностей высокопроизводительных параллельных архитектур новейших графических и центральных процессоров. Поиску такого решения и посвящено настоящее исследование.
Цель и задачи исследования. Целью исследования является развитие методов и алгоритмов многомасштабного моделирования и визуализации геоповерхностей большой площади в реальном времени (не менее 25 кадров в секунду), а также методов высокопроизводительной реализации моделей и алгоритмов на параллельных аппаратных архитектурах современных центральных и графических процессоров.
Поставленная цель требует решения следующих задач:
Провести анализ существующих методов построения адаптивной модели рельефа местности, а также методов сжатия изображений и пространственных данных.
Развить существующие технологии иерархического сжатия и хранения матрицы высот рельефа, чтобы обеспечить использование многократно сжатого представления в качестве исходных данных в параллельных алгоритмах адаптивного восстановления и визуализации рельефа на многоядерных CPU и GPU, существенно повысив тем самым точность задания и площадь территории, доступной для одновременной загрузки и обработки в оперативной памяти.
Развить методы и алгоритмы многомасштабного моделирования и визуализации геоповерхностей с целью обеспечения высокопроизводительной, эффективной по времени и ресурсам реализации разработанной модели на современных центральных и графических процессорах, в том числе:
о разработать алгоритм построения адаптивной триангуляции, допускающий эффективную реализацию с использованием возможностей графических процессоров последнего поколения;
о разработать метод эффективного распараллеливания рекурсивных вычислений на нерегулярных иерархических структурах данных;
о разработать метод текстурирования визуализируемой поверхности, согласованный с методами моделирования.
Разработать программный комплекс, реализующий предложенные технологии на современных параллельных аппаратных архитектурах центральных и графических процессоров.
Экспериментально исследовать эффективность комплекса и реализованных в нем моделей и методов.
Объектом исследования являются информационные модели открытых территорий большой площади.
Предметом исследования являются информационные модели описания открытых территорий большой площади; способы адаптивной триангуляции геоповерхностей, компактного представления, кодирования и хранения; методы распараллеливания вычислений, реалистичной визуализации и высокопроизводительной реализации на ЭВМ.
Методы исследования. Решение задач диссертационной работы базируется на: методах обработки и сжатия изображений, в том числе теории вейвлет-преобразований; теории информации; теории вероятностей; теоретических основах аналитической геометрии; методах компьютерной графики; методах параллельных вычислений. Теоретической базой настоящего исследования явились основополагающие работы: отечественных ученых - Ю.Г.Васина, В.В.Сергеева, В.А.Виттиха, В.А.Сойфера и их учеников, а также зарубежных ученых - М.Кунта (M.Kunt), У.К. Прэтта (W.K.Pratt), И.Добеши (I.Daubechies), Дж. Шапиро (J.Shapiro), У.Перельмана (W.Pearlman), П.Линдстрома (P. Lindstrom) и др.
Научная новизна работы заключается в следующем. Предложен комплексный подход к многомасштабному моделированию и визуализации геоповерхностей, позволяющий работать в оперативной памяти с многократно более плотным представлением данных, реализующий возможности параллельного программирования современных многоядерных центральных и графических процессоров. При разработке подхода получены следующие новые результаты:
Предложено развитие блочно-иерархического вейвлет-сжатия матрицы высот, не уступающее по степени сжатия лучшим методам из своего класса, которое обеспечивает однородность представления данных, повышая, тем самым, эффективность их параллельной обработки, и может применяться в качестве входных данных для систем визуализации геоповерхностей.
Разработана информационная многомасштабная модель рельефа местности, отличающаяся тем, что непосредственно на входе использует сжатое представление, что позволяет многократно повысить площадь доступной для загрузки и обработки поверхности. Модель обеспечивает высокую производительность вычислений за счет реализации разработанного метода построения адаптивной триангуляции поверхности с помощью аппаратных возможностей графических процессоров класса DirectSDl 1.
Теоретически обоснован и реализован алгоритм равномерного распараллеливания рекурсивных вычислений, выполняемых на усеченном квадродере-ве блоков вершин, при исполнении адаптивной триангуляции поверхности на многоядерных центральных процессорах.
Практическая значимость исследования. Результаты исследования имеют практическую значимость и как единый продукт (программный комплекс), и как отдельные компоненты. Особенно - новый метод иерархического сжатия матрицы высот, превосходящий по эффективности существующие методы сжатия данных о рельефе и полутоновых изображений.
Создан набор библиотек СОМ-компонентов, реализующих разработанные модели и алгоритмы, готовый к практическому использованию в подсистемах визуализации местности таких приложений как авиакосмические симу-ляторы, системы виртуальной реальности для киноиндустрии и путешествий, игры и т.д. Модель внедрена в корпорации Интел; в НИИ Системных Исследований РАН; использована институтом машиноведения УрО РАН. Программный комплекс включен в виде лабораторной работы по моделированию рельефа в учебно-методический комплекс «Компьютерная графика» и может быть использован в учебном процессе вузов.
Достоверность результатов работы подтверждена компьютерными экспериментами по моделированию конкретных участков земной поверхности, заданных равномерной матрицей высот (рельеф гор Кавказа, прилегающая территория горы Puget Sound, рельеф Великого Каньона США и др.).
Апробация работы. Основные результаты работы доложены и обсуждены на: международной конференции по компьютерной графике, визуализации и компьютерному зрению WSCG2011 (Пльзень, Чехия, 2011); международной конференции по компьютерной графике, визуализации, компьютерному зрению и обработке изображений CGVCVIP'2010 (Фрейбург, Германия, 2010); международных конференциях по компьютерной графике и визуализации -GraphiCon (Новосибирск, 2005, 2006; Москва, 2007, 2008; Санкт-Петербург, 2010); международной научной конференции «Параллельные Вычислительные Технологии (ПаВТ'2009)»; всероссийских конференциях «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2006, 2007, 2008 - дипломы I степени на конкурсах, проводимых в рамках конференций); всероссийской конференции по параллельным вычислениям (Нижний Новгород, 2008); всероссийских конференциях «Методы и средства обработки сложной графической информации» (Нижний Новгород, 2005, 2006); семинарах кафедры МО ЭВМ факультета ВМК ННГУ. Лабораторная работа по моделированию рельефа внедрена в курсе «Компьютерная графика» на факультете ВМК ННГУ, использована в образовательном проекте Intel Studio Graphics 2008, во Всероссийской научной школе для молодежи «Компьютерное зрение, 3D моделирование и компьютерная графика» 2010 года (госконтракт №02.741.12.2170). Результаты работы использованы корпорацией Интел, НИИ Системных Исследований РАН, а также институтом машиноведения УрО РАН. Работа также прошла конкурсный отбор для участия в программе У.М.Н.И.К (госконтракт №7095р/9642).
Публикации. Основные результаты исследования опубликованы в 17 работах, из них 4 - публикации в изданиях, рекомендованных ВАК.
Основные положения, выносимые на защиту:
1. Новый метод иерархического вейвлет-сжатия матрицы высот, включая: метод блочно-иерархической вейвлет-декомпозиции; представление вейвлет-декомпозиции в виде квадродерева невязок вейвлет-
предсказания; метод двухэтапного сжатия матриц невязок: отсечение нуль-деревьев, улучшенное применением адаптивного статистического моделирования, и сжатие поля поэлементных ошибок восстановления; 2. Новая высокопроизводительная многомасштабная модель для визуализации геоповерхностей, включая: новый метод построения адаптивной триангуляции, эффективно реализуемый на графических процессорах имеющих тесселяторы; новый метод распараллеливания рекурсивных вычислений на усеченном квадродереве для многоядерных процессоров.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 160 наименований. Общий объем - 180 стр.
