Е.А. Башков, С.А. Зори - Исследование эффективности реализации синтеза изображений рельефов алгоритмом ROAM

УДК 004.93

Исследование эффективности реализации синтеза изображений рельефов алгоритмом ROAM на параллельных вычислительных системах

Е. А. Башков, Донецкий национальный технический университет, кафедра прикладной математики и информатики, bashkov@pmi.dgtu.donetsk.ua

С. А. Зори, Донецкий национальный технический университет, кафедра прикладной математики и информатики, zori@pmi.dgtu.donetsk.ua

Аннотация

Рассматривается задача синтеза реалистичных изображений рельефов и ландшафтов в реальном времени с использованием алгоритма ROAM. Исследуется эффективность его реализации на современных параллельных архитектурах: графических процессорах (GPU) с технологией CUDA и кластерной системе NeClus с использованием MPI. Показано, что ограничения CUDA по рекурсивным вычислениям и динамическим древовидным структурам делают применение GPU для ROAM неэффективным, тогда как кластерный вариант с MPI обеспечивает необходимую производительность и соответствует требованиям реального времени.

Ключевые слова: реалистичная визуализация, рельеф, алгоритм ROAM, синтез изображения, параллельные вычисления, графический мультипроцессор, CUDA, кластер, MPI, NeClus.

Введение

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

Перспективным направлением является использование иерархических триангуляций на основе квадродеревьев и бинарных деревьев треугольников, а также адаптивных кластерных подходов. Одним из наиболее известных и эффективных алгоритмов этого класса является ROAM (Real-time Optimally Adapting Meshes), обеспечивающий адаптивную детализацию рельефа в зависимости от положения наблюдателя.

Цель работы — оценить возможность и эффективность синтеза изображений рельефов алгоритмом ROAM в реальном времени при использовании специализированных параллельных вычислительных систем.

Синтез изображений рельефов алгоритмом ROAM

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

Иллюстрация метода ROAM (итеративная бисекция треугольников) — Рисунок 1 — Иллюстрация метода ROAM

На основе программной реализации ROAM были исследованы характеристики алгоритма при работе на четырёхъядерном процессоре: время загрузки карты высот, зависимость кадровой частоты (FPS) от числа выводимых треугольников и количества активных ядер.

График зависимости FPS от числа ядер и количества треугольников — Рисунок 2 — Зависимость FPS от числа ядер и сценарных полигонов

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

Реализация ROAM на параллельных платформах графических процессоров

В качестве первого варианта параллелизации была реализована версия ROAM на графическом процессоре с использованием технологии CUDA. Анализировались полное время работы алгоритма, а также отдельные составляющие: время вычислений на GPU и время передачи данных между памятью CPU и GPU.

Программное моделирование алгоритма ROAM на CUDA — Рисунок 3 — Программное моделирование ROAM на CUDA

Исследования показали, что, хотя вычислительная часть функций на GPU выполняется в несколько раз быстрее, чем на CPU, общий выигрыш нивелируется из-за постоянных операций загрузки и выгрузки данных, а также архитектурных ограничений CUDA: отсутствие поддержки рекурсивных вычислений и динамических деревьев в памяти видеокарты.

Сравнение времени выполнения вычислительной части и общего времени (CPU/GPU) — Рисунок 4 — Сравнение CPU и GPU при реализации ROAM на CUDA

В результате использование CUDA для реализации полного алгоритма ROAM признано неэффективным: выигрыш на вычислениях компенсируется значительными затратами на обмен данными и упрощение структуры алгоритма под ограничения платформы.

Синтез изображений рельефов методом ROAM на кластерной системе

Второй вариант параллелизации основан на использовании вычислительного кластера NeClus ДонНТУ и технологии MPI для распределённой обработки данных. Алгоритм ROAM был адаптирован к кластерной архитектуре посредством разбиения карты высот на отдельные части (патчи), которые затем обрабатываются параллельно на разных узлах кластера.

Схема реализации ROAM на кластере NeClus — Рисунок 5 — Реализация алгоритма ROAM на кластере NeClus

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

Зависимость времени синтеза от числа узлов кластера — Рисунок 6 — Характеристики реализации ROAM на кластере NeClus

По мере двукратного увеличения числа узлов достигается заметное снижение времени синтеза (до 85–90 % для отдельных конфигураций), что демонстрирует хорошую масштабируемость решения.

Выводы

Для задач реалистичной визуализации рельефов и ландшафтов предложено использовать алгоритм ROAM как эффективный метод адаптивной триангуляции. Проведено исследование параллельной реализации алгоритма на двух архитектурах: GPU с технологией CUDA и вычислительном кластере NeClus с использованием MPI.

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

Литература

Schroeder W.J., Zarge J.A., Lorensen W.E. Decimation of triangle meshes // SIGGRAPH ’92 Proc.: Computer Graphics. 1992. Vol. 26, No. 2. P. 65–70.
Rossignac J., Borrel P. Multi-resolution 3D approximations for rendering complex scenes // Modeling in Computer Graphics: Methods and Applications. 1993. P. 455–465.
De Boer W.H. Fast Terrain Rendering Using Geometrical MipMapping // E-mersion Project. October, 2000.
Hoppe H. View-dependent refinement of progressive meshes // SIGGRAPH ’97 Proceedings. 1997.
Duchaineau M. et al. ROAMing terrain: Realtime optimally adapting meshes // Proc. IEEE Visualization. 1997. P. 81–88.
Ulrich T. Rendering massive terrains using chunked level of detail // Super-size-it! Scaling up to Massive Virtual Worlds (ACM SIGGRAPH Tutorial Notes). 2000.
Зори С.А., Лисеенко В.В. Методы синтеза реалистичных изображений рельефов и ландшафтов для параллельных вычислительных систем трёхмерной компьютерной графики // Моделювання та комп’ютерна графіка: Матеріали 4-ї міжнародної науково-технічної конференції. Донецьк, 2011. С. 114–118.

Annotation

Bashkov E.A., Zori S.A. Research of efficiency of realization of the image synthesis of reliefs by algorithm ROAM on parallel computing systems. The paper considers the problem of real-time relief and landscape image synthesis and analyzes the efficiency of using the ROAM algorithm on different parallel architectures. The authors compare GPU-based implementation using CUDA and a cluster-based implementation using MPI on the NeClus system. It is shown that CUDA limitations on recursive computations and dynamic tree structures make GPU implementation inefficient, while an MPI-based cluster solution provides significant speedup and enables real-time terrain rendering.

Key words: realistic visualization, relief, ROAM algorithm, image synthesis, parallel computing, GPU multiprocessor, CUDA, cluster, MPI, NeClus.

Источник: Исследование эффективности реализации синтеза изображений рельефов алгоритмом roam на параллельных вычислительных системах / Е.А. Башков, С.А. Зори // Известия ЮФУ. Технические науки. 2013. – С. 46–51.