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

На права* рукописи

Потий Олег Александрович

ТЕКСТУРНАЯ ВИЗУАЛИЗАЦИЯ ВЕКТОРНЫХ ПОЛЕЙ С ИСПОЛЬЗОВАНИЕМ ВОЗМОЖНОСТЕЙ ГРАФИЧЕСКОГО ОБОРУДОВАНИЯ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

i

г. Ростов-на-Дону - 2005 г.

Работа выполнена в Южно-Российском региональном центре информатизации при Ростовском государственном университете

Научные руководители - кандидат технических наук,

доцент Крицкий С.П.

Официальные оппоненты - Доктор технических наук,

профессор

Божич Владимир Иванович

Кандидат технических наук, профессор

Иванченко Александр Николаевич Ведущая организация - Южный научный центр РАН

Защита состоится 27 декабря 2005г. в 11 час. на заседании диссертационного совета К212.208.04 Южно-Российского регионального центра информатизации при Ростовском государственном университете по адресу: 344090, г. Ростов-на-Дону, пр. Стачки, 200/1, корп. 2, ЮГИНФО РГУ.

С диссертацией можно ознакомиться в Зональной научной библиотеке РГУ (по адресу г. Ростов-на-Дону, ул. Пушкинская, 148).

Автореферат разослан "26" ноября 2005 г.

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

кандидат физ.-мат. наук — Муратова Галина Викторовна

н

226WS

3

Общая характеристика работы

Актуальность темы

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

Значимость этой стадии часто недооценивается и отдается на откуп стандартным математическим пакетам, в которых реализованы устаревшие методы визуализации, такие как стрелочные диаграммы или цветовое кодирование. Эти мгтоды просты в реализации и не требуют больших вычислительных затрат. Недостатком стрелочных диаграмм явпяется низкая разрешающая способность при отображении векторного поля, а изображения, полученные с помощью метода цветового кодирования, не доступны для понимания без дополнительной информации. При этом мало внимания уделяется текстурным методам визуализации течений, в то время как это семейство алгоритмов, позволяющим передать информацию о течении в каждой точке рассматриваемой обласи. Изображения, полученные с помощью этого семейства методов, непрерывно покрывают всю визуализируемую область течения, в отличие от стрелочных диаграмм Текстурная визуализация дает исследователю понятную картину течения, содержащую информацию о структуре течения и скорости в разных участках. Однако, киассические текстурные алгоритмы гакие как LIC (I ine Integral Convolution, Cabral and Leedom, 1993) требуют больших вычислительных затрат для своей работы и сложны в реализации.

Это обстоятельство сохранялось до недавнего времени Разработка методов IBFV (Image-Based Flow Visualization, I van Wijk, 2002) и LEA (Lagrangian-Eu)enan Advection, В Jobard, 2002) положила начало адаптации текстурных алгоритмов с использованием аппаратных возможное гей гпгрр.шпипгп грпф^нт'Т'го оборудования. Аппаратная архитектура с4вр8вейМй'0,ргЦ||1«В*-*их карт пре-

доставляет большие возможности для управления ходом визуализации трехмерной сцены Наличие графического процессора (GPU -Graphic Processing Unit) и быстрой SDRAM памяти на самой графической плате позволяет рассматривать персональный компьютер как двухпроцессорную машину с разделяемой памятью. Реализация методов визуализации векторных полей с использованием ресурсов GPU позволяет достичь высокой производительности за счет переноса части или всех этапов алгоритма на сторону графического процессора. Применение этого подхода дает возможность производить визуализацию двумерного стационарного течения в интерактивном режиме. В случае нестационарного двумерного или трехмерного течения производительность текстурных алгоритмов резко снижается. Примером такого метода является 3D IBFV (van Wijk, 2004), предназначенный для визуализации стационарного трехмерного течения.

Задача визуализации трехмерного течения требует особенного рассмотрения, поскольку в этом случае мы имеем дело с текстурным кубом, отображение которого необходимо выделять в отдельную стадию алгоритма. Непрерывный характер визуализации является препятствием для визуализации участков течения, скрытых внутри текстурного куба. Для решения этой проблемы возможно рассмотрение текстурного куба в виде отдельных частиц. Примером такого подхода является метод немецких ученых (Weiskopf, 2004), основанный на текстурной адвзкции частиц в трехмерном пространстве. В работах Guthe (2000-2002) предложено производить анимацию множества полупрозрачнь х частиц, на которые накладывается текстурное изображение. Однако, производительность этих алгоритмов невысока. Кроме этого, визуализация нестационарного течения с использованием этих методов является затруднительной.

Цель работы

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

Для достижения этих целей решаются следующие задачи:

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

• разработка эффективного представления данных для методов, реализуемых на основе вершинных и фрагментных программ для графических процессоров

• создание новых методов визуализации, обладающих большей познавательной силой и производительностью

• распространение алгоритмов текстурной адвекции на случай трехмерного течения. Для этого необходимо рассмотрение как текстурных методов, так и алгоритмов, основанных на трассировке системы частиц.

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

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

Достоверность и обоснованность результатов

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

Достоверность и обоснованность результатов

Основные результаты, выносимые на защиту

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

2. Разработана модификация метода IBFV на основе использования графического процессора для визуализации двумерного нестационарного течения (GPU-Based IBFV). Предлагаемый алгоритм использует вершинные программы графического процессора для расчета адвекции текстурного изображения.

3. Предложен алгоритм, реализующий концепцию LEA в случае двумерного течения с помощью фрагментных инструкций графического процессора (GPU-Based LEA).

4. Создана программа fVIz для интерактивной визуализации плоских сечений трехмерного поля скоростей с помощью анимации течения, интуитивно понятной наблюдателю. Приложение реализует как оригинальный метод IBFV, так и предложенный алгоритм GPU-Based IBFV.

5. Разработан алгоритм текстурной визуализации нестационарного трехмерного нестационарного течения на основе предложенного метода GPU-Based IBFV. Показано падение производительности текстурных методов визуализации в случае трехмерного течения.

6. Разработан способ декомпозиции трехмерного текстурного куба для представления трехмерного векторного поля в виде двумерного текстурного объекта.

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

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

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

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

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

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

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

Практическая ценность

В ходе исследовательской работы была разработана программа визуализации сечений трехмерного течения. Приложение используется в лаборатории вычислительного эксперимента ЮГИНФО для визуального наблюдения результатов математического моделирования.

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

Апробация результатов работы и публикации

Основные результаты работы докладывались и обсуждались на следующих конференциях и круглых :толах: на XIII, XIV, XV Международных конференциях посвящеьных проблемам компьютерной графики «Графикон 2003» (г Москва, 2003г.), «Графикон 2004» (г Москва, 2004г), «Графикон 2005» (г Новосибирск 2005г.); на круглом столе участников конференции «Графикон 2003»; на XII Международной конференции по вычислительной механике и современным прикладным программным системам (г. Владимир, 2003г); на X Всероссийской Школе-Семинаре "Современные проблемы Матемагического Моделирования" 'г Абрау-Дюрсо 2003г);

По результатам выполненных исследований опубликовано 7 печатных работ, в гом числе 5 в соавторстве Из них 1 статья в российском рецензируемом журнале, 5 статей в сборниках трудов и 1 в тезисах докладов всероссийских и международных конференций

Объем и структура работы.

Работа состоит из введения, четырех глав и заключения. Объем работы составляет 134 страницы включая 31 рисунок и 3 таблицы. Список цитируемой литературы состоит из 90 наименований.

Содержание работы

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

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

В первой части главы приводятся краткие сведения из предметной области - определение векторного поля, основных кривых и поверхностей. Векторные поля определяются посредством задачи Коши:

¿х

— = /(*,0, *('о) = *о (1)

ш

Рассматриваются следующие кривые: линия тока, линия пути, линия следа и материальная линия. Последние два объекта могут быть использованы для визуализации распространения примеси в течении или развития его фронта. Рассматриваются способы представления правой части задачи Коши (1) на регулярных и нерегулярных вычислительных решетках.

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

Другим подходом к построению текстуры, отображающей течение, является адвекция некоторого исходного изображения вдоль линий тока векторного поля (LEA). Термин "адвекция" обозначает перенос скалярного значения в векторном поле, при котором это значение не изменяется. Примером такого явления служит распространение примеси в течении. Модель адвекции вещества в векторном поле хорошо подходит для визуализации поведения течения в гидрогазодинамике. Любой алгоритм текстурной визуализации течения с использованием адвекции изображения состоит из трех стадий - адвекции первоначальной текстуры, смешивание ее с шумовым изображением и опциональная пост-обработка результата с помощью какого-либо сглаживающего фильтра. Результат участвует в следующей итерации метода. Этот класс методов можно адаптировать к реализации с помощью графического процессора. Одной из первых попыток использования ресурсов графической карты для визуализации течения стал алгоритм IBFV. В то время как алгоритмы семейства LIC требуют большого объема вычислений и плохо подходят к использованию в интерактивном режиме, синтез анимации течения на основе текстурной адвекции позволяет решить проблему производительности в случае двумерного течения. В обзоре обозначены две проблемы текстурных методов в случае трехмерного течения: низкая производительность методов адвекции текстурного куба и недостаточная познавательная ценность результатов визуализации. Решением данных проблем может стать подход на основе комбинирования текстурных методов и алгоритмов отображения геометрических объектов. Для этого рассматриваются алгоритмы, использующие трассировку системы частиц в пространстве. Текстурные методы анимации системы частиц позволяют получать визуализацию с высоким пространственным разрешением Однако, это делает необходимым наличие большого числа частиц в потоке, что предъявляет определенные требования к производительности системы.

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

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

Во второй главе рассматриваются технические средства, необходимые для реализации алгоритмов визуализации на основе графического процессора. При этом особенный акцент был сделан на том, каким образом эти средства могут быть использованы для построения системы визуализации. Автором предлагается обобщенная модель вычислений на основе GPU. Рассматривается аспекты построения систем визуализации на базе графического процессора, ис- i пользуемого в качестве дополнительного вычислительного устройства. Для работы с графическим оборудованием в качестве программного интерфейса используется библиотека OpenGL.

В первой части главы рассматриваются основные стадии конвейера растеризации и его расширение с помощью программ графического процессора. GPU является высокопроизводительным потоковым процессором, оптимизированным для выполнения векторных операций. С точки зрения обработки вершинных данных, его архитектуру можно рассматривать как MIMD. На стадии растрирования фрагментов, GPU выступает в роли SIMD-системы. Графическое оборудование выполняет растеризацию виртуальной сцены как последовательность операций, составляющих конвейер растеризации. Входными данными для конвейера являются поток вершинных данных и набор текстурных объектов. На выходе синтезируется растровое изображение виртуальной трехмерной сцены. Сам конвейер может быть условно разделен на следующие структурные блоки (Рис.1): обработка входного потока геометрических данных, растеризация фрагментов и операции с ними.

<Р ♦

Рис 1 Конвейер растеризации

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

GPU и не затрагивает CPU. Для их использования в OpenGL введено расширение ARB_vertex_program и ARB_Fragment_Program. Если вершинные программы оперируют с геометрическими данными, фрагментные программы работают с отдельными пикселями, попадающими в буфер кадра. Дается краткое описание этих расширений.

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

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

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

В третьей главе приводится описание двух алгоритмов текстурной визуализации двумерного течения, непосредственно использующих процессор графической системы компьютера (GPU-Based IBFV и GPU-Based LEA). Предложенный подход позволяет не ограничиваться случаем стационарного течения и улучшить производительность текстурных методов визуализации. На основе предложенного алгоритма для анимации двумерного течения разработан метод визуализации трехмерного поля Также представлена программа для интерактивной визуализации сечений трехмерного поля скоростей, реализующая один из разработанных методов.

В первом разделе главы описывается модификация метода IBFV выполненная на основе GPU GPU-Based IBFV. Для расчета текстурных координат в предлагаемом алгоритме используется механизм вершинных программ, что позволяет снять нагрузку с центрального процессора при визуализации нестационарного векторного поля. Приводится краткое описание оригинального алгоритма IBFV. Алгоритм основывается на плотном покрытии визуализируемой области поля V(xj) частицами, наделенными некоторым свойством, распределение которого задается скалярным полем F(s,t) - в точке s в момент времени t находится частица со свойством F. Предположение о сохранении этого свойства выглядит так: F(pitl,tt&l) = F{pk,tk). Для интегрирования вдоль линий тока используется метод первого порядка. Синтез изображения F{prt„) на п-ом шаге производится согласно уравнению (2)'

^(Д„/„) = аХ(1-аУ0(Л.,Л_,) (2)

1-0

где а - доля шумовых сигналов Ск в результирующем изображении, необходимых для устранения эффекта «вымывания» изображения за пределы визуализируемой области. Реализация этого метода состоит в разбиении изображения на мелкие квадратные участки, смещенные вдоль линий тока. Это выполняется с помощью наложения текстурного изображения на полигональную сетку, узлы которой сдвинуты согласно значению поля скоростей в этих точках. После растеризации искаженной текстуры составляется линейная комбинация Р(р,„1„) и шумовой текстуры 0„. Результат сохраняется в качестве нового изображения, участвующего в следующей итерации метода.

Использование ГОРУ для визуализации нестационарного поля приводит к интенсивному использованию центрального процессора Каждое изменение векторного поля У(х,1) приводит к пересчету координат полигональной сетки размером Нх-М, что ведет к вычислению уравнения (Лг + 1)х(М+1) раз. Предлагаемая в данной главе модификация этого метода позволяет достичь лучших результатов при визуализации нестационарного течения, перенеся стадию вычислений текстурных координат на сторону графического процессора

Была произведена следующая модификация структуры метода: сетка остается неизменной, в то время как изменяются текстурные координаты, благодаря чему и происходит продвижение текстурного изображения. Более подробно этот процесс представлен на рис. 3 На приведенной схеме показаны узлы сетки р, в которых заданы значения векторного поля У(х,1). Интегрируя назад на один шаг Д/ получаем точку текстурной области р-УНи, которая в момент ? будет располагаться в р .

Суть предложенного метода состоит в динамическом вычислении текстурных координат, соответствующих узлам р полиго-

Рис 3 Наложение текстуры на полигональную сетку

нальной сетки. В ОРи-Ваэес! ЮИУ полигональная сетка используется лишь для задания векторного поля - удобно с помощью нормали вершины представить значение векторного поля в этой точке.

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

Р =(Р Р Р ) Вершинная программа

vertex. attnbfO], pout

V(P.t)=Np=(Nx, Ny, Nz) Vertex attnb(2], MAO T=P,n-h-Np ^=^Texcoord vertex attnb(d].

Рис.4 Схема вычислений вершинной программы

Во второй части третьей главы представлена реализация концепции переноса текстурного значения Лагранжа-Эйлера с помощью фрагментных программ (GPU-Based LEA). Приводится краткое описание метода адвекции Лагранжа-Эйлера. Согласно концепции адвекции текстурного значения отдельные точки изображения Т остаются неизменными при переносе вдоль линии пути частицы в потоке, т е. следующая материальная производная равна нулю:

= + /(x>,)vr(i(jc>,)) = 0 (3)

Идея этого метода заключается в совмещении двух подходов на основе кинематик Лагранжа и Эйлера. Для расчета последовательности изображений, представляющей последовательный перенос вещества в потоке, на каждом шаге координаты множества частиц рассчитываются согласно лагранжевой кинематике, а перенос текстурного значения осуществляется по эйлеровой схеме. Формально это процесс можно выразить соотношением (4), V определяет, какие цветовые значения будут втекать в T(x,t) через границу Е.

Vp.....U-hUE <4>

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

Предлагаемый алгоритм GPU-Based LEA основывается на стадии растеризации конвейера OpenGL. В данном случае нет возможности использовать нормали вершин для задания векторного поля. Для хранения информации о течении используется дополнительная текстура, элементы которой имеют формат числа с плавающей точкой. Компонента RGB-изображения рассматриваются как вектор скорости, определенный в соответствующем узле квадратной регулярной сетки. Не нарушая общности, можно полагать, что векторное поле задано на единичном двумерном кубе. Результатом работы метода является цвет точки изображения T(xj), рассчитанный согласно (4). Входными данными для фрагментной программы являются текстура с адвектируемым изображением T(xj) и текстурный массив вещественных RGB-значений, содеэжагций значения поля /. Изображение Т подается на первый текстурный модуль, а массив с полем скоростей - на второй. На выходе ядра фрагментной программы получаем текстурное значение T(x(t-h),c-h). Работа фрагментной программы проиллюстрирована на рис.5.

Рис 5 Схема вычислений фрагментной программы

После растеризации Т(х(1-к),г-И) выполняется смешивание с шумовым сигналом и копирование результата в текстурную память, по аналогии с предыдущим методом. Необходимо отметить, что применение описанного алгоритма не ограничивается областью [0,1]х[0,1|. Случай произвольной области реализуется с помощью теста трафарета описанного во второй главе. Данный механизм позволяет ограничить область просмотра контуром произвольной формы. Другим способом решения этой проблемы является отсечение фра1 ментов на уровне текстурной программы. В этом случае альфа-компонента прямоугольной текстуры, содержащей значения

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

Преимуществами данного метода являются: Высокое пространственное разрешение. В отличие от 1ВРУ, этот алгоритм позволяет производить визуализацию течения с большим пространственным разрешением и точностью, так как в данном случае каждой точке х сопоставлен пиксель изображения Т и значение векторного поля /(*,?) - адвекция Т производится для всех его точек, а не только для вершин-узлов полигональной решетки. Отсутствие сложной геометрии. Предложенный метод позволяет ограничиться минимальным количеством геометрических объектов (один четырехугольник) и существенно упростить реализацию метода.

Высокая производительность. По производительности фрагмент-ные программы значительно превосходят вершинные. Упомянутые обстоятельства делают э"от метод одним из самых быстрых алгоритмов визуализации нестационарного течения с высокой разрешающей способностью и качеством на уровне ЫС-алгоритмов.

В третьей части главы производится описание разработанного автором приложения РЛг для интерактивной визуализации срезов трехмерного течения не доступном графическом оборудовании. Приложение реализует как 1ВЕУ, так и СРи-Ваэес! ЮБУ. Программа имеет расширенный интерфейс (рис.6), позволяющий контролировать параметры визуализации.

Рис 6 Работа с видовыми преобразованиями в

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

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

В программе имеется возможность сохранения анимационной последовательности в виде последовательности копий экрана в формате *.Ьтр Код приложения легко переносим для сборки в различных операционных системах

В четвертом разделе приводится описание разработанного автором текстурного метода визуализации нестационарного трехмерного течения. Работу описанных текстурных методов визуализации течения можно условно разделить на три этапа - адвекция исходной текстуры, смешивание ее с шумовым сигналом и копирование результата в основную текстурную память. Математический аппарат рассмотренных алгоритмов допускает их естественный перенос на трехмерный случай. Однако, при реализгции этих этапов на графическом оборудовании существует несколько проблем - отсутствие сплошного объемного геометрического примитива, позволяющего целиком производить его текстурирование трехмерным текстурным кубом » двухмерНость буфера кадра, в котором происходит альфа-смешивание текстуры изображения ^ с шумом. Решением указанных проблем является разбиение трехмерного текстурного куба на плоские слои и выполнение операций .адвекции и примешивания шумового сигнала в этих двумерных слоях Трехмерный текстурный куб рассматривается как стек двумерных текстурных слоев (рис 7) Перенос точек каждого текстурного слоя может выполняться как с

Рис.7 Процесс послойного смешивания трехмерных текстур

помощью GPU-Based IBFV, так и с помощью аппаратной адбекции GPU-Based LEA. отображение очередного кадра анимации течения состоит из двух стадий -последовательная адвекция каждого текстурного слоя и растеризация полученной трехмерной текстуры. В рамках исследований методов трехмерной адвекции автором был реализован метод 3D GPU-Based IBFV. Его производительность оказглась приблизительно в полтора раза ниже чем 3D IBFV (van Wijk, 2004) - 5-7 кадров в секунду для поля размерности 643. Этот факт является следствием того, что в предлагаемом методе в качестве F(pn,tj и шумовых текстур Gn используется трехмерный текстурный куб в явном виде, в то время как в методе 3D IBFV применяется стек двумерных текстур. Операция трилинейной интерполяции, действующая в случае выборки цветового значения из трехмерной текстуры, требует больших ресурсов графического процессора, чем билинейная интерполяция при выборке из плоской текстуры. Использование текстурного куба делает визуализацию объема более точной (в силу трилинейной фильтрации). 3D GPU-Based IBFV может быть использован для визуализации нестационарного векторного поля, так как он не ограничен фиксированным состоянием течения. Пример визуализации вихревого трехмерного поля показан рис. 8.

Рис.8 Визуализация, полученная с применением 30 ОРи-Вазес11ВРУ

В четвертой главе предлагается эффективный и быстрый метод визуализации трехмерного нестационарного течения с использо-

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

После этого происходит растеризация следов частиц Тройка ТШВ-значений текстуры с плавающей точкой используется для хранения координат вершины р = (р,,р,,р. р,) ■ Четвертая компонента р, (альфа-значение) выбрана для предсаг.вления времени жизни частицы. Программа рассчитывает новое положение частицы, основываясь на текущих координатах, извлекая из упакованного трехмерного поля скоростей Тех, вектор скорости в точке р (рис.9). На г-ом шаге на вход фрагментной программы подается три текстурных объекта: гекстура-массив с »• текущими координа-

тами частиц Техр(1), упакованное в двумерную текстуру трехмерное поле скоростей Те.х,, одна текстура

Техпк1(1),/ =1М из набора случайных положений частиц, необходимых для обновления координат "умерших" части« На выходе получаем текстурный массив Тех {> ч 11 В связи с 1ем, что в современном

Текстура с п ;лем скорости

Рис 9 Структура метода.

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

При непрерывном продвижении частиц в течении со временем все они будут либо вынесены за пределы визуализируемой области, либо накопившаяся при интегрировании погрешность сделает траекторию частицы неправдоподобной. Описываемый метод наследует концепцию примешивания шумового сигнала. Для ее реализации применительно к геометрическим данным используются два средства: время жизни частицы в потоке р,, и набор массивов с заранее рассчитанными случайно взятыми атрибутами, играющих роль шумовых текстур. На каждом шаге итерационного процесса происходит инкрементирование параметра р, При достижении некоторого предельного значения I этот параметр обнуляется и частица считается "умершей" и вновь "возродившейся". Возрождается мертвая частица в точке единичного куба /?„^еГехт((у),у = 1,Л^. Кроме этого частица ограничивается в рамках единичного куба, что не дает ей выйти за пределы визуализируемой области если частица выходит за рамки единичного куба, то она так же считается умершей и ей присваивается случайное положение. Таким образом, фрагментная программа производит вычисление ри +1) согласно выражению-

р(1+\) = (Рг,Л1 + \),Р1и + 1)) =

'0>™=(') + /„ ала'0 + 1)

еслиргу.О -1-1)е Л1 (0,1) и р,(1) < I.

(5)

е Тех„и1(к) в противном случае

В работе приводится структурная схема фрагмент ной программы (рис 10), реализующей эти вычисления, и ее код. Объясняются детали реализации этого алгоритма - реализация обратного преобразования двумерного текстурного массива в трехмерный, вычисление р(1 +•1).

Текстурный массив {р}

-ЦТЕХО (->| КО=р, |--

Массив

случайных

положений

частиц р,-НтМГИ Ч^^Ш-Д

Упакованное

трехмерное ^_

попе Я-НТЕХ21-

Обратное преобразование ТЕХ2 и нахождение

Решение о "жизни" и "смерти'

частицы Р?1 =И1 или Р!ЫО(р,)

> Новый

—¡К1=р,^—► текстурный массив {р,}

Рис 10 Структура фрагментной профаммы.

После растеризации текстурного массива его содержимое копируется в основную память компьютера как массив вершин. Время жизни частицы р1 рассматривается как индекс элемента в массиве, визуализация которого дает трассировку следа частицы в виде полигонального представления. Использование полупрозрачных линий позволяет получить визуально однородное изображение течения, так же как при использовании трехмерной текстурной визуализации. Разрешающая способность линий тока как полигональных примитивов в данном случае оказывается выше, чем в случае применения методов визуализации объема (см. ЗО СРи-Вазе(1 ЮРУ). При отображении множества линий тока используется перспективная проекция, что дает лучшее ощущение трехмерного пространства.

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

ласти, использование геометрических, а не текстурных объектов, возможность визуализации нестационарных течений. Пример визуализации течения показан на рис. 11.

Рис 11 Визуализация течений, полученная с помощью метода

В заключении сформулированы результаты проведенных исследований.

Основные результаты работы и выводы

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

2. На основе текстурного алгоритма IBFV создан метод GPU-Based IBFV, реализующий продвижение текстурного значения с помощью динамического вычисления текстурных координат производимого вершинной программой. Предложенный алгоритм может быть использован для построения высокоэффективной потоковой системы визуализации нестационарных двумерных данных

3. Разработан алгоритм аппаратной адвекции Лагранжа-Эйлера GPU-Based LEA на основе фрагментных программ графического процессора. Метод позволяет производить анимацию нестацио-

парного двумерного течения. Особенностью алгоритма является большая разрешающая способность визуализации по сравнению с IBFV и GPU-Based IBFV GPU-Based LEA является одним из самых быстрых на сегодняшний момент алгоритмов визуализации. Благодаря отсутствию сложной полигональной геометрии реализация этого метода в виде программного продукта отличается чрезвычайной простотой.

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

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

6 Разработано приложение fViz, реализующее как оригинальный метод IBFV, так и его модификацию - GPlJ-Based IBFV. Данный программный продукт позволяет получать интерактивную анимацию сечений трехмерного течения с высоким качеством. Для работы программы не требуется высокопроизводительной рабочей станции, достатг чно наличия персонального компьютера с бытовым графическим ускорителем Это обстоятельство позволяет сделать высококачественную текстурную визуализацию доступной для массового использования В программе реализована

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

Основные публикации по теме диссертации

1. Аниканов A.A., ПотийО.А. Проблемы и подходы к решению задачи визуализации данных о течениях в природных объектах // «Научная визуализация в прикладных задачах». Изд МГУ 2003. С. 20-22.

2. Anikanov A.A., Potiy О./ Texture Advection for 3D Flow Visualization // The 13th International Conference on Computer Graphics: GraphiCon'2003, Sept. 5-10, 2003, Moscow, Russia. P. 100-105.

3. Аниканов A.A., Потий O.A. Использование текстур при визуализации трехмерных течений // Тезисы докладов двенадцатой международной конференции по вычислительной механике и современным прикладным программным системам. Владимир. 30 июня - 5 июля 2003. ' т. С. 53-55.

4. Потий O.A. Визуализация объемов с помощью аппаратных ресурсов графических ускорителей // Сборник трудов X Всероссийской Школы-Семинара "Современные проблемы Математического Моделирования", Абрау-Дюрсо, 15-20 сентября, 2003 г, С. 191-196.

5. Potiy O.A., Anikanov A.A. GPU-Based Texture Flow Visualization // The 14th International Conference on Computer Graphics: Graphi-Con'2004, Sept. 6-10,2004, Moscow, Russia, P.155-158

6. Potiy OA., Anikanov A.A. 3D Flow visualization using GPU-driven particle system // The 15th International Conference on Computer Graphics: GraphiCon'2005, June 20 - 23, 2005, Novosibirsk, Russia, P. 121-124

7. Потий O.A. Визуализация трехмерного течения с помощью системы частиц на основе графического процессора. Приложение к журналу «Известия вузов. Северо-Кавказский регион. Естественные науки», 2005, №11, С. 58-65

В совместных работах личный вклад автора заключается в разработках, связанных с графическим процессором. В работах [5] и [6] автору принадлежит основная идея алгоритмов и их реализация

\

1>

<

Потий Олег Александрович

ТЕКСТУРНАЯ ВИЗУАЛИЗАЦИЯ ВЕКТОРНЫХ ПОЛЕЙ С ИСПОЛЬЗОВАНИЕМ ВОЗМОЖНОСТЕЙ ГРАФИЧЕСКОГО ОБОРУДОВАНИЯ

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

Подписано в печать "21" ноября 2005 г.

Формат 60х 84 1/16 Бумага офсетная.

Печать оперативная. Усл. п л. 1,0. Тираж 100 экз. Заказ 25-11

ООО "Мини Тайп"

344010, г. Ростов-на-Дону, пр Ворошиловский, 87/65

»25304

РНБ Русский фонд

2006-4 29513

Введение

Объект исследования и актуальность темы . . !.

Состояние проблемы

Цель работы.

Основные результаты, выносимые на защиту.

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

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

Объем и содержание работы.

1 Объекты предметной области и обзор текстурных методов их визуализации

1.1 Базовые понятия теории векторных полей.

1.1.1 Векторное поле.

1.1.2 Основные кривые и поверхности векторного поля

1.1.3 Поле скоростей как результат численного эксперимента

1.2 Текстурные методы визуализации векторного поля

1.2.1 Семейство методов свертки вдоль линий тока (LIC)

1.2.2 Методы визуализации течения посредством адвекции исходного изображения

1.2.3 Текстурные методы визуализации течения с использованием системы частиц.

1.3 Методы визуализации объемных данных.

1.3.1 Выводы.

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

2.1 Основные стадии конвейера растеризации и его расширение с помощью программ графического процессора

2.1.1 Обработка геометрических данных и вершинные программы.

2.1.2 Растеризация фрагментов и фрагментные программы.

2.1.3 Операции с фрагментами.

2.2 Обобщенная модель вычислительного алгоритма на основе графического процессора.

2.2.1 Общая структура.

2.2.2 Текстурные объекты как способ хранения данных

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

3 Методы аппаратной адвекции текстуры в потоке tp. 3.1 Модификация алгоритма IBFV на основе графического процессора.

3.1.1 Метод IBFV.

3.1.2 Реализация IBFV с помощью вершинных программ (GPU-Based IBFV).

3.2 Аппаратная адвекция Лагранжа-Эйлера.

3.2.1 Метод адвекции Лагранжа-Эйлера.

3.2.2 GPU-Based LEA.

3.3 Описание приложения для визуализации сечений трехмерного течения.

3.3.1 Входные данные и интерфейс программы.

3.3.2 Визуализация в системе fViz.

3.3.3 Визуализация продвижения фронта.

3.4 Трехмерная адвекция с использованием GPU.

3.5 Результаты и выводы.

4 Метод визуализации трехмерного течения с помощью системы частиц

4.1 Анимация системы частиц на основе GPU.

4.1.1 Вычисление координат точек с помощью графического процессора.

4.1.2 Метод декомпозиции трехмерного текстурного куба в двумерную текстуру.

4.1.3 Поведение частиц в течении.

4.1.4 Используемый способ визуализации частиц

4.2 Реализация метода.

4.3 Сравнение производительности и качества получаемой визуализации с методами, основанными на адвекции текстурного куба.

4.4 Результаты.

Объект исследования и актуальность темы

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

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

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

Метод цветового кодирования векторного поля ставит в соответствие каждому значению двумерного поля скоростей значение из цветового пространства HSL (оттенок-насыщенность-яркость). Направление поля определяет компоненту цветового оттенка согласно модели цветового круга. Яркость и насыщенность выбираются согласно величине векторного значения в этой точке. Метод цветового кодирования позволяет получать визуализацию в режиме реального времени, однако интерпретация результатов визуализации требует некоторых умственных усилий. Указанное обстоятельство делает изображения, полученные с помощью этого алгоритма не доступными для понимания без дополнительных умственных усилий.

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

Одной из особенностей данного семейства методов является возможность реализации с помощью аппаратных средств графического оборудования, установленного на неспециализированных рабочих станциях. Аппаратная архитектура современных графических плат имеет сложную структуру, предоставляющую большие возможности для управления ходом визуализации трехмерной сцены. Наличие графического процессора (GPU - Graphic Processing Unit) и быстрой SDRAM памяти на самой графической плате позволяет рассматривать персональный компьютер как двухпроцессорную машину с разделяемой памятью. Такие графические системы позволяют гибко контролировать конвейер растеризации двумерных и трехмерных объектов. Это дает возможность полностью переопределить операции текстурирования и реализовать текстурные методы визуализации целиком на графическом процессоре.

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

Состояние проблемы

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

Одной из первых работ в направлении текстурной визуализации была работа Jack van Wijk [86], в которой он предложил метод пятнистого шума. Этот алгоритм создает изображение течения посредством суперпозиции отдельных эллиптических пятен, обозначающих частицы, помещенные в поток. Направление движения пятна в текстуре соответствует направлению поля скоростей в рассматриваемой локальной области.

Дальнейшие работы в области текстурной визуализации привели к созданию алгоритмов семейства Line Integral Convolution [24, 77]. Существуют модификации этого метода для отображения течений на поверхностях [75, 76] и трехмерных полей [39]. Основная идея этого метода состоит в построении интенсивности изображения векторного поля как результата свертки специально подобранной функции-фильтра и белого шума вдоль линии тока. Этот метод получил широкое распространение в связи с высоким качеством получаемого изображения. Однако, для того, чтобы рассчитать интенсивность пикселя в этом методе необходимо провести интегрирование вдоль всей линии тока, проходящей через эту точку. Это приводит к высокой вычислительной стоимости визуализации.

Производились несколько попыток снижения вычислительных затрат этого метода. Была разработана модификация методов [74], основанных на использовании значений интенсивностей точек, расположенных в окрестности рассматриваемой. Другим подходом является использование анимации таблицы цветов [20, 33]. Это позволило несколько сократить объем вычислений, однако интерактивная анимация нестационарного течения с использованием этого алгоритма возможна лишь на мощных специализированных станциях.

Одним из важнейших этапов развития данной области научной визуализации, давших начало многим методикам, стала адвекция Лагранжа-Эйлера(ЬЕА — Largangian-Eulerian Advection) [35]. Идея этого алгоритма состоит в совместном использовании лагранжевой и эйлеровой кинематики распространения сплошной среды.

С появлением методов, использующих аппаратные возможности графических адаптеров, стало возможным получать качественную текстурную визуализацию двумерного течения на персональном компьютере интерактивно, в режиме реального времени. В разработанном Jack van Vijk алгоритме IBFV(Image Based Flow Visualization) [88j было предложено производить адвекцию изображения вдоль линий тока поля скоростей за счет аппаратной операции наложения текстуры на смещенную полигональную сетку, в узлах которой заданы значения векторного поля. Последующие исследования в области текстурной визуализации привели к разработке метода визуализации стационарного трехмерного поля скоростей [90]. Недостатком данного алгоритма является возможность визуализации лишь стационарного течения.

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

Другой способ текстурной визуализации с помощью системы частиц описан в работах [42, 43, 44[. В этих работах предложено производить анимацию множества полупрозрачных частиц, на которые накладывается текстурное изображение.

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

Цель работы

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

Основными критериями оценки производительности алгоритмов визуализации выступают удобство интерпретации и производительность. Необходимым требованием при разработке методов визуализации является их полная или частичная адаптация к реализации на графическом процессоре.

Для достижения этой цели в работе решаются следующие задачи:

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

• разработка эффективного представления данных для методов, реализуемых на основе вершинных и фрагментных программ для графических процессоров

• создание новых методов визуализации, обладающих большей познавательной силой и производительностью

• распространение алгоритмов текстурной адвекции на случай трехмерного течения. Для этого необходимо рассмотрение как текстурных методов, так и алгоритмов, основанных на трассировке системы частиц.

Основные результаты, выносимые на защиту

В ходе работы получены следующие результаты:

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

2. Разработана модификация метода IBFV на основе использования графического процессора для визуализации двумерного нестационарного течения (GPU-Based IBFV). Предлагаемый алгоритм использует вершинные программы графического процессора для расчета адвекции текстурного изображения

3. Предложен алгоритм, реализующий концепцию LEA с помощью фрагментных инструкций графического процессора (GPU-Based LEA).

4. Создана программа для интерактивной визуализации сечений трехмерного поля скоростей с помощью анимации течения, интуитивно понятной наблюдателю (fViz). Приложение реализует как оригинальный метод IBFV, так и предложенный алгоритм GPU-Based IBFV.

5. Разработан алгоритм текстурной визуализации трехмерного неста-цинарного течения на основе предложенного метода GPU-Based IBFV.

6. Разработан способ декомпозиции трехмерного текстурного куба для представления трехмерного векторного поля в виде двумерного текстурного объекта.

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

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

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

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

Основу для трех из представленных методов составляет алгоритм IBFV и адвекция Лагранжа-Эйлера. В данной работе предлагается модификация этих методов с помощью графического процессора. Представленные алгоритмы позволяют снизить нагрузку на центральный процессор при визуализации стационарного и нестационарного течения. Кроме этого, предложенный способ вычислений позволяет выйти на более высокий уровень абстракции при построении системы визуализации.

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

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

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

Практическая ценность

В ходе работы над упомянутыми методами была разработана программа визуализации сечений трехмерного течения. Приложение используется в лаборатории вычислительного эксперимента ЮГИНФО для визуального наблюдения результатов математического моделирования.

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

Объем и содержание работы

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

Вторая глава содержит аналитическое описание конвейера растеризации OpenGL в контексте его использования в алгоритмах научной визуализации. В данной главе содержатся необходимые сведения об организации вычислительных алгоритмов на базе графического процессора. Приводится описание фрагментных и вершинных программ. Дается прототип обобщенной схемы алгоритмов, основанных на применении графического процессора как дополнительного вычислительного SIMD-устройства. На основе этой схемы дается описание потоковой модели вычислений GPU, в частности, приводится описание способов представления входных и выходных данных ядра фрагментной программы.

В третьей главе дается описание предлагаемых текстурных алгоритмов визуализации, названных автором GPU-Based IBFV и GPU-Based LEA. Коль скоро эти алгоритмы основываются на IBFV и LEA, описание базовых методов предваряет описание новых. Рассматриваются алгоритмические аспекты реализации GPU-Based IBFV и GPU-Based LEA на базе вершинных и фрагментных программ графического процессора. Обсуждается эффективность и возможные сферы применения этих алгоритмов. Особенное внимание в этой главе уделяется модификации указанных процедур для случая трехмерного течения: рассматриваются детали реализации, производится оценка эффективности предложенных алгоритмов. Здесь же приводится описание программы визуализации сечений трехмерного течения (fViz) на основе имеющихся и сконструированных автором алгоритмов.

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

В заключении формулируются основные результаты исследования.

2.2.3 Выводы и результаты

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

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

В случае двумерной визуализации используется двумерная текстура произвольного размера (NVtexturerectangle) элементы которой имеют формат числа с плавающей точкой (NVfloatbuffer).

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

Глава 3

Методы аппаратной адвекции текстуры в потоке

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

На основе предложенного алгоритма для анимации двумерного течения разработан метод визуализации трехмерного поля.

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

3.1 Модификация алгоритма IBFV на основе графического процессора

В этом параграфе описывается модификация метода IBFV выполненная на основе непосредственного использования GPU. Для расчета текстурных координат в предлагаемом алгоритме используется механизм вершинных программ, что позволяет снять нагрузку с центрального процессора при визуализации нестационарного векторного поля.

3.1.1 Метод IBFV

Метод IBFV (Image Based Flow Visualization) был предложен Jarke van Wijk [88]. Рассматривается, в общем случае, n-мерное векторное поле (в дальнейшем будем полагать п = 2 или 3 ) и соответствующая задача Коши:

V(x, t) <=Rn,x<= Rn, t e Л, (3.1)

- = V(p(t),t),pM=Po (3-2)

Численная аппроксимация этого уравнения первого порядка [6] с фиксированным по времени шагом At при обозначении tk = Atk имеет вид: pk+i=pk + V{pk,tk)AL (3.3)

Введем в рассмотрение поле материальных значений F(z, t), где х G S. Физический смысл этого поля таков - в момент времени t в точке х находится частица, обладающая свойством F(x, t). Как правило под абстрактным свойством понимается тройка RGB, вес, значение освещенности в точке и т.д. Временная инвариантность изображения в данном случае означает F(pk+i,tk+i) = F(pk,tk) если pk+i,pk € S. В общем случае, исходя из (3.11), имеем:

3.4)

I 0, else

Со временем наступит такой момент, когда большая часть F(x, t) будет иметь значение 0, так как почти все рк выйдут за рамки области S. Воспрепятствовать этому явлению "вымывания"изображения F(x,t) можно путем подмешивания к полю материальных значений шумового сигнала G(x,t):

F(pk+1,tk+1) = (1 - a)F(pk,tk) + aG(pk+l,tk+l) (3.5)

Повторяя это процесс N раз и полагая первое слагаемое F(p0, tQ) абсолютно черным, дабы исключить его влияние на итоговое изображение, имеем:

71— 1

F(pn, tn) = aJ2(l~ ayG(pk-i, tk-i) (3.6) i=0

Таким образом, цвет каждой точки изображения рп представляет собой численную аппроксимацию свертки шумового изображения вдоль линии тока р с экспоненциально затухающей функцией фильтра а(1 — а)*. Это делает метод похожим на алгоритмы семейства Line Integral Convolution, с тем отличием, что наблюдаемый результат в нашем случае является эволюцией во времени выражения (3.6) Шумовое изображение G(x, t) выбирается таким, чтобы оно не содержало компонент высоких частот, например - розовый шум.

Реализация этого метода в контексте OpenGL состоит в разбиении изображения на мелкие квадратные участки, смещенные вдоль линий тока. Такое смещенное разбиение удобно производить с помощью наложения текстурного изображения на полигональную сетку, узлы которой сдвинуты согласно значению поля скоростей в этих точках. Данное наложение текстуры обеспечивает продвижение отдельных участков изображения в течении в рамках одной итерации метода. После отрисов-ки искаженной текстуры в буфер кадра, с помощью операций альфа-смешивания составляется линейная комбинация F и шумовой тесксту-ры Gk, где к = 1 , ЛГ. Результат линейной комбинации копируется из буфера кадра и сохраняется в качестве нового изображения F - оно участвует в следующей итерации метода. Необходимо отметить, что строгие рассуждения относительно F(pn,tn) (З.б) справедливы лишь для точек, расположенных в узлах сетки. Внутри ячейки сетки к текстуре будут применены операции билинейного интерполирования с учетом четырех точек, определяющих узлы сетки. Однако выбор достаточно малого шага полигональной сетки (несколько пикселей) позволяет получать качественную визуализацию течения.

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

3.1.2 Реализация IBFV с помощью вершинных программ (GPU-Based IBFV)

Использование оригинального алгоритма IBFV [88] для визуализации нестационарного поля приводит к интенсивному использованию центрального процессора. Дело в том, что каждое изменение векторного поля V(x,t) приводит к пересчету координат полигональной сетки, что ведет к вычислению уравнения (3.3) (N + 1) х (М + 1) раз (N,M -количество ячеек по горизонтали и вертикали ).

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

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

Рис. 3.1: Наложение текстуры на полигональную сетку

На приведенной схеме показаны узлы сетки р, в которых заданы значения векторного поля V(p, t). Интегрируя назад по времени вдоль линий тока на один шаг At получаем координаты точки текстурной области (р — v(p,t)At) которая, переместившись во времени в момент t, будет располагаться в точке р. Такая реализация метода позволяет говорить об адвекции текстурного изображения по Лагранжу-Эйлеру [35].

Суть предложенного метода состоит в динамическом вычислении текстурных координат, соответствующих узлам р полигональной сетки. Описываемый алгоритм использует расширение ARBvertexprogram библиотеки OpenGL [16], [45], позволяющее контролировать стадию геометрических преобразований.

Согласно представленной в § 2.2 обобщенной модели вычислений с использованием графического процессора, входными данными для этого метода является полигональная сетка с квадратными ячейками и набор текстурных объектов. Эта модель является неоднородной относительно входных и выходных данных при использовании геометрических объектов, однако в данном случае, это не является препятствием. Действительно, в GPU-Based IBFV полигональная сетка используется лишь для задания векторного поля - удобно с помощью нормали вершины представить значение векторного поля в этой точке. -in р р \ Вершинная программа in у z > vertex.attrib[0]; pout w

V(P,t)=Np=(Nx, Ny, Nz) vertex.attrib[2]; MAD T=Pin-h*Np ^"^Texcoord vertex.attrib[8];

Рис. 3.2: Схема вычислений вершинной программы

Таким образом, на вход вершинной программы подается координата вершины, обозначающая точку р, и нормаль в точке, рассматриваемая как вектор скорости V(p, t) в точке р. На выходе вершинной программы мы имеем координату текстурного изображения, вычисленной согласно заданным значениям р и V(p, t).

Текст этой вершинной программы таков:

ATTRIB Pin = vertex.attrib[0] ATTRIB Np = vertex.attrib[2]; координата точки p нормаль в точке - значение вектора V(p, t)

OUTPUT Pout = result.position OUTPUT T = result.texcoord; результирующая позиция рассчитанные текстурные координаты

MOV Pout, Pin; MAD T,h,Np,Pin; расчет текстурной координаты

Как видно из приведенного отрывка программного кода графического процессора, операция численного интегрирования (3.3) производится с помощью всего лишь одной инструкции MAD - multiply and add (умножить и сложить) выполняемой GPU за один такт. Результатом ее являются координаты точки в текстурной области F(p, t), соответствующей вершине р.

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

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

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

3.2 Аппаратная адвекция Лагранжа-Эйлера

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

3.2.1 Метод адвекции Лагранжа-Эйлера

Рассмотрим, в общем случае, нестационарное векторное поле скоростей f(x, t) заданное с помощью следующего уравнения: х' = f (х, t) f (х, t): Е х J Rn, (3.7)

В данной работе рассматриваются случаи п = 2 и п = 3.

Пусть для момента времени t0 задано изображение Т(х, £0)> Необходимо определить способ нахождения изображения Т(х, £), являющегося результатом адвекции в потоке, определенном векторным полем f(x, t), исходного изображения Т(х, io) за время t G J. Как говорилось выше, адвекция в нашем случае понимается как перенос точек исходного текстурного изображения вдоль линий тока.

Для решения этой задачи удобно рассмотреть совокупность частиц {si}, распределенных в потоке и плотно покрывающих область Е. Тогда адвекцию изображения Т(х, t) можно представить как процесс распространения частиц из {Si}, каждой из которых присвоено свойство T(sj), равное значению Т(х, t) в точке положения частицы Sj в момент времени to- Для момента времени t € J каждая точка х € Е связана с некоторой частицей из {sj}, находящейся в данной точке. Обозначим эту частицу через s(x, t).

Согласно концепции адвекции текстурного значения отдельные точки изображения Т остаются неизменными при переносе вдоль линии пути частицы в потоке, таким образом материальная производная ^^ равна нулю: = ^>)+f(X)()VT(s(Xi()) = 0 (38)

Это уравнение можно рассматривать с двух точек зрения. С одной стороны, оно описывает процесс распространения в потоке изображения Т(х, t), которое можно рассматривать как некоторое скалярное поле, известное для каждого момента времени в любой точке области Е. При таком рассмотрении частицы теряют свою индивидуальность. Подход непосредственного решения уравнения (3.8) называют эйлеровым.

Другая точка зрения на данное уравнение связана с лагранжевым подходом, заключающимся в отдельном вычислении траектории каждой частицы в потоке. Траектория или линия пути частицы s, обозначенная через рs(t), будет определяться уравнением = .,*)- (3.9)

Идея метода лагранжево-эйлеровой адвекции [35] заключается в совмещении двух вышеуказанных подходов. Для расчета последовательности изображений, представляющей последовательный перенос вещества в потоке, на каждом шаге координаты множества частиц рассчитываются согласно лагранжевой кинематике, а адвекция свойств частиц осуществляется по эйлеровой (см. Рис. 1.6). В ходе адвекции Т(х, t) за период времени h координаты каждой точки Pimg(t) данного изображения интегрируются назад по времени с шагом —h. Интегрируя уравнение (3.9), получим:

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

Выбор значения V для точек рimg{t—h) Е определяет, какие цветовые значения будут втекать в T(x,t) через границу Е.

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

3.10)

Vpimg(t ~ h) в Е VPimg{t ~h)iE

3.11) точки, в которых нет цветового значения. При использовании обратного интегрирования, напротив, происходит обращение к предыдущим положениям частиц в потоке, что гарантирует окраску всех точек изображения даже без применения билинейной интерполяции при выполнении операции выборки текстурного значения.

3.2.2 GPU-Based LEA

В рамках работы над текстурными методами визуализации автором был разработан метод аппаратной адвекции Лагранжа-Эйлера на основе фрагментных программ. Как было упомянуто в параграфе 2.1.2, расширение ARBFragmentProgram дает возможность гибко контролировать стадию растеризации изображения, позволяя управлять растеризацией каждого пикселя. Для работы фрагментной программы, в отличие от вершинной, не требуется наличия сложного геометрического полигонального объекта, что делает ненужным наличие детализированной четырехугольной сетки - достаточно лишь одного четырехугольника, к которому будет применяться операция текстурирования.

Предлагаемый алгоритм целиком основывается на стадии растеризации конвейера OpenGL. В данном случае у нас нет возможности использовать нормали вершин для задания векторного поля. Согласно предложенной обобщенной модели GPU-вычислений (параграф 2.2) для хранения информации о течении используется дополнительная текстура, элементы которой имеют формат числа с плавающей точкой. В рамках этой модели компоненты RGB-изображения рассматриваются как вектор скорости, определенный в соответствующем узле квадратной регулярной сетки.

Не нарушая общности, можно полагать, что векторное поле задано на единичном двумерном кубе. При таком рассмотрении координату частицы в визуализируемой области можно получить из координат точки текстуры х = (v, w) € [0,1] х [0,1], которые 'фрагментная программа получает на вход при каждом вызове.

Результатом работы такой процедуры должен стать цвет точки изображения Т(х, £), х G [О, I]2, рассчитанный согласно (3.11). Таким образом, входными данными для фрагментной программы являются текстура с адвектируемым изображением Т(х, t) и текстурный двумерный массив вещественных RGB-значений, содержащий значения поля f(x, t). Изображение Т(х, t) подается на первый текстурный модуль, а массив с полем скоростей - на второй. На выходе ядра фрагментной программы получаем текстурное значение Т(х, t—h). Работа фрагментной программы проиллюстрирована на рис. 3.3:

Рис. 3.3: Схема вычислений фрагментной программы

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

Весь код фрагментной программы представлен в следующем листинге:

ТЕХ R0, f[TEXl], ТЕХ1, RECT выборка из текстурного массива значения поля

MOV Rl, f[TEX0]; текстурные координаты изображения принимаются за положение частицы

MAD R2,-h,R0,Rl; вычисление предыдущего положения точки в потоке

MAX Rl , R2 , 0.001 ограничение текстурных

MIN R2 , Rl , 0.999 координат в интервале (0,1)

TEX o[COLR],R2, TEX0, 2D; выборка текстурного значения, соответствующего R2

Иструкции МАХ и MIN необходимы в этом случае для ограничения координат точки текстурной области R2 в интервале (0,1). Это

Рис. 3.4: Эффект "втекания"и его устранение нормированием текстурных координат необходимо для предотвращения выхода за пределы текстурной области ТЕХО, в противном случае возможно появление эффекта втекания постороннего цветового значения (рис. 3.4). Границы отрезка [0.001,0.999] выбраны экспериментально, исходя из точности расчетов графической карты при операциях с текстурными координатами.

После растеризации T{x,t — h) выполняется смешивание с шумовым сигналом и копирование результата в текстурную память, по аналогии с предыдущим методом.

Применение описанного алгоритма не ограничивается областью [О, I]2. Случай произвольной области реализуется с помощью теста трафарета (см. параграф 2.1.3). Данный механизм позволяет ограничить область просмотра контуром произвольной формы. Другим способом решения этой проблемы является отсечение фрагментов на уровне текстурной программы. В этом случае альфа-компонента прямоугольной текстуры, содержащей значения векторного поля, используется для хранения маскирующего значения области просмотра - 0, если точка не принадлежит области и 1, если точка находится внутри нее. В ходе работы фрагментной программы это значение проверяется и принимается решение о том, будет ли эта точка визуализирована либо отклонена.

Преимуществами данного метода являются:

• Высокое пространственное разрешение. В отличии от аппаратного IBFV, такой алгоритм позволяет производить визуализацию течения с большим пространственным разрешением и точностью, так как в данном случае каждой точке х сопоставлен пиксель изображения Т(х, t) и значение векторного поля f (х, t). Таким образом, адвекция текстурного изображения Т(х, t) производится для всех его точек, а не только для вершин-узлов полигональной решетки.

• Отсутствие сложной геометрии. Предложенный метод позволяет ограничится минимальным количеством геометрических объектов (один четырехугольник), поскольку для задания течения используется трехмерная текстура.

• Высокая производительность. Производительность фрагмент-ных программ, как правило, оказывается значительно превосходит производительность вершинных программ. Упомянутые обстоятельства делают этот метод одним из самых быстрых алгоритмов визуализации нестационарного течения с высокой разрешающей способностью и качеством на уровне LIC-алгоритмов.

Экспериментальные замеры показали следующие результаты в fps (frame per second - кадр в секунду):

Год Метод Размерность данных течения Оборудование fps

2000 LEA [34] 256 х 256 SGI Octane, EMXI graphics 2

2002 IBFV [88] 147 х 147 PC, GeForceFX 5900 137

2005 GPU LEA 256 х 256 PC, GeForceFX 5900 350

3.3 Описание приложения для визуализации сечений трехмерного течения

С использованием предложенного выше метода аппаратной адвекции было разработано приложение, реализующее как обычный IBFV, так и GPU-Based IBFV — fViz (Flow Visualization). Основными требованиями при разработке данного программного продукта были следующие положения:

Заключение

В заключении подведем итог проделанной работе. Основной целью является разработка и реализация эффективных методов визуализации векторных полей. Спецификой исследований стала попытка адаптации алгоритмов визуализации и вычислительных методов к новым возможностям, предоставляемым современным графическим оборудованием. При таком подходе GPU рассматривается как дополнительное мощное вычислительное устройство, поддерживающее потоковые SIMD-вычисления. В диссертационной работе производится анализ возможности построения вычислительных алгоритмов на базе библиотеки OpenGL и его расширений: вершинных и фрагментных программ. Делается особенный акцент на способе представления входных и выходных данных ядра GPU-программы. Автором предлагается обобщенная модель вычислений таких алгоритмов. В работе показано, каким образом вычислительный алгоритм, не имеющий прямого отношения к компьютерной графике, может быть реализован с использованием графического процессора. Описанные средства позволяют реализовать алгоритмы широкого профиля на базе графического процессора (General-purpose GPU computations)

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

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

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

Разработан алгоритм аппаратной адвекции Лагранжа-Эйлера (GPU-Based LEA) на основе фрагментных программ графического процессора. Отличительной его особенностью является практически полное отсутствие геометрических объектов. Данный метод позволяет производить анимацию нестационарного двумерного течения. Особенностью алгоритма является большая разрешающая способность визуализации по сравнению с методом IBFV. Кроме этого GPU-Based LEA является одним из самых быстрых на сегодняшний момент алгоритмов визуализации. Благодаря отсутствию сложной полигональной геометрии реализация этого метода в виде программного продукта отличается чрезвычайной простотой.

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

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

В ходе работы над этим алгоритмом был разработан метод упаковки трехмерного текстурного куба. Этот алгоритм дает способ описания трехмерного массива значений поля скоростей в виде двумерного текстурного объекта.

В ходе работы над указанными методами разработано приложение fViz, реализующее как оригинальный метод IBFV, так и его модификацию GPU-Based IBFV. Данный программный продукт позволяет получать интерактивную анимацию сечений трехмерного течения с высоким качеством. Для работы программы не требуется высокопроизводительной рабочей станции, достаточно наличия стандартного персонального компьютера с бытовым графическим ускорителем. Это обстоятельство позволяет сделать высококачественную текстурную визуализацию доступной для массового использования. Хотя в настоящий момент программа используется для визуализации стационарного течения, имеется возможность ее расширения на случай поля, зависящего от времени. В программе реализована трехмерная рабочая область, что дает возможность исследователю получить больше информации о поле, основываясь лишь на его трех основных сечениях.

1. Абламейко С.В., Лагуновский Д.М. Обработка изображений: технология, методы, применение. Учебное пособие. — Мн.: Амалфея, 2000. - 304 с

2. Аниканов Л.Л., Николаев И.А., Крицкий С.П. Методы визуализации векторных полей // Современные проблемы механики сплошной среды: Тр. V Межд. конф. Ростов н/Д, 12-14 окт. 1999. Т. 2, Ростов н/Д: Изд-во СКНЦ ВШ. 2000. С. 6-10.

3. Аниканов Л.Л., Потий О.А. Проблемы и подходы к решению задачи визуализации данных о течениях в природных объектах // "Научная визуализация в прикладных задачах". Изд. МГУ. 2003. С. 20-22.

4. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. Москва: Наука, 1987.

5. Бибиков Ю.Н. Курс обыкновенных дифференциальных уравнений: Учеб. пособие для ун-тов. — М.: Высш. шк., 1991.

6. Брилл М., Хаген X., Родриан Х.-К., Дьячин В., Клименко С.В.\ Использование техники стримбол для визуализации течений // Программирование, т. 5, 1995. С. 63-73.

7. Брилл М., Хаген X., Родриан Х.-К., Дьячин В., Клименко С.В., Веймер X. Неявные методы визуализации потока жидкости // Программирование, т. 5, 1995. С. 74-79.

8. К.В. Дедкова, Д.В. Могиленских, И.В. Павлов, В.В. Федоров Визуализация линий тока и методы комплексной визуализации дискретных векторных полей. // Тезисы конференции VII Забабахинские научные чтения (ЗНЧ-VII), Снежинск, 2003, С. 209-210

9. Потпий О.А.\ Визуализация объемов с помощью аппаратных ресурсов графических ускорителей // Сборник трудов X Всероссийской Школы-Семинара "Современные проблемы Математического Моделирования", Абрау-Дюрсо, 15-20 сентября, 2003, С. 191-196.

10. Потпий О.А.\ fVis программа для текстурной визуализации сечений трехмерного течения //Сборник трудов аспирантов и соискателей РГУ, 2005

11. Чикин А. Л. Трехмерная математическая модель гидродинамики Азовского моря // Математическое моделирование и проблемы экологической безопасности: Тр. Всерос. конф. Ростов н/Д, 2000. С. 222-229.

12. Шикин А. В., Боресков Л. В. Компьютерная графика. Полигональные модели. М.: ДИАЛОГ-МИФИ, 2001.-464с.

13. ATI Technologies Inc. ATI OpenGL Extension Support. 2002, P. 490

14. Dave Astle, Kevin Hawkins. Beginning OpenGl Game Programmnig. // THOMSON, Course Technology, 2004, P. 301

15. G. V. Bancroft, F. J. Merritt, Т. C. Plessel P. G. Kelaita, R. K. McCabe, and A. Globus. FAST: A multiprocessed environment for visualization of computational fluid dynamics. In Proc. of Visualization 90, pages 14-27, 1990.

16. Carl de Boor A practical guide to splines. Springer-Verlag,New York, 2001, p. 341

17. Jeff Bolz, Ian Farmer, Eitan Grinspun, Peter SchrooderSpa,Tse matrix solvers on the GPU: conjugate gradients and multigrid. //ACM

18. Transactions on Graphics (TOG), SESSION: Computation on GPUs ,Volume 22 , Issue 3 (July 2003), P. 917-924

19. Steve Bryson and Creon Levitt The virtual windtunnel: An environment for the exploration of three-dimensional unsteady flows. In Visualization '91, pages 17-24, 1991.

20. Cabral, В., and Leedom, L. C.\ Imaging vector Fields using line integralconvolution. //In Proceedings of ACM SIGGRAPH 93, Computer Graphics Proceedings, Annual Conference Series,1993, ACM, vol. 4, 263-272.

21. Cabral, В., and Leedom, L. C.\ Highly parallel vector visualization using line integral convolution //In Seventh SIAM Conference on Parallel Processing for Scientific Computing. Feb 1995. P. 802-807.

22. D. Dovey. Vector plots for irregular grids // IEEE Computer Society. Visualization'95. 1995. P. 248-253.

23. N. Dyn, D. A. Levin ., J. Gregory. Butterfly Subdivision Scheme for Surface Interpolation with Tension Control. ACM Transactions on Graphics. Vol. 9, No. 2, April 1990

24. N. Dyn, D. A. Levin ., S. Hed. Subdivision Schemes for Surface Interpolation. Workshop in Computational Geometry, 1993

25. Klaus Engel ., Markus Hadwiger, Joe M. Kniss, Christof R-S. High-Quality Volume Graphics on Consumer PC Hardware. // SIGGRAPH 2002, Course Notes 42,2002,July, 122 P., P. 37-48

26. Klaus Engel., Ertl T. Interactive high-quality volume rendering with flexible consumer graphics hardware. // Eurographics 2002 State-of-the-Art (STAR) Report, 2002. P. 24р

27. Randima Fernando GPU Gems: Programming Techniques, Tips, and Tricks for Real-Time Graphics. nVIDIA, 2005, P. 816.

28. James D.Foley, Andries Van Dam Fundamentals of Interactive Computer Graphics. Addison-Wesley Publishig Company, 1982. (Русский перевод: Док. Фоли, А. вэн Дэм Основы интерактивной машинной графики. Том 1. М.: Мир, 1985.)

29. Bruno Jobard ., Lefer W. The Motion Map: efficient computation of steady flow animation // IEEE Visualization '97. Phoenix, Arizona, USA. 1997. P. 323-328.

30. Bruno Jobard, Gordon Erlebacher, M. Yousuff Hussaini . Hardware-Accelerated Texture Advection For Unsteady Flow Visualization. // Proceedings of the conference on Visualization '00, Salt Lake City, US.2000. P. 155-162.

31. Bruno Jobard, Gordon Erlebacher, M. Yousuff Hussaini . Lagrangian-eulerian advection of noise and dye textures for unsteady flow visualization.// IEEE Transactions on Visualization and Computer Graphics 8, 3, 2002, P. 211-222.

32. Robert Haimes. pv3: A distrubuted system for large-scale unsteady cfd visualization. In AIAA Papers 94-0321, 1994.

33. Halstead M., M. Kass, and T. DeRose Efficient, Fair Interpolation Using Catmull-Clark Surfaces. Siggraph '93. p. 35.

34. A. Hilton and J. Illingworth. Marching triangles: Delaunay implicit surface triangulation. Technical Report CVSSP 01, University of Surrey, January 1997.

35. V. Interrante and Ch. Grosch. Strategies for effectively visualizing 3D flow with volume LIC. //In IEEE Visualization '97 Proceedings, pages 421- 424. IEEE Computer Society, October 1997.

36. Tommi Ilmonen and Janne Kontkanen The Second Order Particle System // In WSCG Proceedings 2003, P. 123-127

37. Goryachev V.D., Smirnov E.M. A Computer and Information System for Computer Fluid Dynamics: SELIGER. //In Proc. of the 15th IMACS World Congress on Scientific Computation, Modelling and Applied Math. 09. 24-29. 1997. Berlin, Vol. 3, 1997, P. 47-53

38. Stefan Guthe . Visualisierung dreidimensionaler Vectorfelder. Diplomarbeit, WSI/GRIS University of Tubingen, July 2000

39. Stefan Guthe, Stefan Gumhold, Wolfgang Straber . Texture Particles: Interactive Visualization of Volumetric Vector Fields. // Workshop uber Trends und Hohepunkte der Graphischen Datenverarbeitung 2001

40. Stefan Guthe, Stefan Gumhold, Wolfgang Straber . Interactive Visualization of Volumetric Vector Fields Using Texture Based Particles. //Proceedings of WSCG 2002, 2002, P. 9

41. M. J. Kilgard , Nvidia opengl extension specifications,// Nvidia corp, May 19, 2004.

42. Gunter Knittel The ULTRA VIS system. //Proceedings of the 2000 IEEE symposium on Volume visualization, Salt Lake City, Utah, 2000, P. 71-79

43. M. Levoy. Display of surfaces from volume data. // IEEE Computer Graphics and Applications, 8(3), pages 29-37, May 1988.

44. Charles T. Loop Smooth Subdivision Surfaces Based on Triangles.Master of Science Thesis. University of Utah. 1987

45. W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3D surface construction algorithm. //In Proc. of SIGGRAPH '87, pages 163-169, 1987.

46. David Luebke, Mark Harris GPGPU: General Purpose Computation On Graphics Hardware, SIGGRAPH 2005 Course Notes, P. 227

47. Nelson L. Max, Barry G. Becker., David A. Lane. Unsteady Flow Volumes. //In "Proceedings Visualization '95", Atlanta, GA. (October 1995), IEEE Computer Society Press, P. 329-337

48. Mark Segal, Kurt Akeley The OpenGL® Graphics System: A Specification (Version 1.4). //Silicon Graphics, Inc, 2002, P. 312

49. Mark J. Kilgard The OpenGL Utility Toolkit (GLUT) Programming Interface, API Version 3. // Silicon Graphics, Inc. November 13, 1996, P. 68

50. Mason Woo, Jackie Neider, Tom Davis, Dave Shreiner OpenGL Programming Guide, Third Edition. // OpenGL Arcitecture Review Board, ADDISON-WESLEY, 2000, P. 574

51. N. Max. Optical models for direct volume rendering. //IEEE Transactions on Visualization and Computer Graphics, 1995, P. 99— 108

52. Michael Meibner, Urs Kanus ., W. Straber. VIZARD II, A PCI-Card for Real-Time Volume Rendering. // Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware Lisbon, 1998, Portugal, P. 61-67

53. Michael Meibner, Urs Kanus., Michael Doggett. A Low-Cost Memory Architecture For PCI-Based Interactive Ray Casting. //Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, Los Angeles, California, United States, 1999, P. 7-13

54. Jason L. Mitchell RADEONtm 9700 Shading. ATI Research. Appeared in SIGGRAPH 2002 State of the Art in Hardware Shading Course Notes, P. 39

55. Paul Rademacher GLUI. A GLUT-Based User Interface Library, Version 2.0. // June 10, 1999, P. 38

56. Matt Pharr GPU Gems 2: Programming Techniques for High-Performance Graphics and General-Purpose Computation. nVIDIA, 2005, P. 880.

57. H. Pfister, J. Hardenbergh, G. Knittel, H. Lauer and L. Seiler The VolumePro Real-Time Ray-Casting System. //In Proceedings of of SIGGRAPH 99, pages 251 260. ACM, 1999

58. Potiy O.A., Anikanov A.A. Texture Advection for 3D Flow Visualization // The 13th International Conference on Computer Graphics: GraphiCon'2003, Sept. 5-10, 2003, Moscow, Russia. P. 100105.

59. Potiy O.A.\, Anikanov A.A. GPU-Based Texture Flow Visualization // The 14th International Conference on Computer Graphics: GraphiCon'2004, Sept. 6 10, 2004, Moscow, P. 155-158

60. Potiy O.A., Anikanov A.A. GPU-Based Texture Flow Visualization // The 15th International Conference on Computer Graphics: GraphiCon'2005, June 20 23, 2005, Novosibirsk, P. 121-124

61. Reeves W. Т. Particle Systems — A Technique for Modeling a Class of Fuzzy Objects, // Computer Graphics 17:3 pp. 359-376, 1983

62. Reeves W. T.\, Ricki Blau Approximate and probabilistic algorithms for shading and rendering structured particle systems. // In B. A. Barsky, editor, Computer Graphics (SIGGRAPH '85 Proceedings), volume 19, pages 313-322, July 1985.

63. Rogers D. Procedural Elements for Computer Graphics. McGraw-Hill, 1985. (Русский перевод: Роджерс Д. Алгоритмические основы машинной графики. М.: Мир, 1989, 512 с.)

64. Jurgen Schulze, Ulrich Lang ., Steffen P. Walz. Volume Rendering in a Virtual Environment. //In Proceedings of 5th IPTW andv Eurographics Virtual Environments, Springer Verlag, 2001, ISBN 3211.83671-3, P. 187-198

65. Jurgen Schulze, Ulrich Lang ., U. Wossner. Remote Volume Rendering for Virtual Environments using PC Clusters. // VR-Cluster '03: Workshop on Commodity Clusters for Virtual Reality, IEEE VR, Los Angeles, March 22-26, 2003

66. H. W. Shen and D. L. Kao. A New Line Integral Convolution Algorithm for Visualizing Time-Varying Flow Fields. IEEE Transactions on Visualization and Computer Graphics, 4(2):98-108, April June, 1998.ft

67. Richard M. Stallman and GCC Developer Community Using the GNU Compiler Collection. GNU Press, 23 May 2004, P. 420

68. D. Stalling, Неде H. C. . Fast and resolution independent line integral convolution // SIGGRAPH'95 Conference Proceedings. 1995. P. 249256

69. D. Stalling, Неде H. C. ., Battke H. Fast line integral convolution for arbitrary surfaces in 3d // Visualization and Mathematics. Springer-Verlag. Heidelberg, 1997. P. 181-195

70. D. Stalling . LIC on Surfaces. In Texture Synthesis with Line Integral Convolution. ACM SIGGRAPH 97, International Conference on Computer Graphics and Interactive Techniques, 1997. P. 51—64

71. D. Stalling . Fast Texture-based Algorithms for Vector Field Visualization // Ph.D. thesis, der Freien Universitat Berlin. December 1998. P. 139

72. Teitzel C., Grosso R., Ertl T. Line integral convolution on triangulated surfaces // WSCG '97, The Fifth International Conference in Central Europe on Computer Graphics and Visualization '97, vol. 3, Plzen, Czech Republic, February 1997. P. 572-581.

73. Turk G., Banks D. Image-Guided Streamline Placement // Computer Graphics, SIGGRAPH 96 Conference Proceedings. 1996. P. 453-460.