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

С.И. ВЯТКИН, М. А. ГОРОДИЛОВ, Б.С. ДОЛГОВЕСОВ

Институт автоматики и электрометрии СО РАН, Новосибирск, Россия

Оглавление

• 1. Введение
• 2. Геометрические объекты
• 3. Геометрические операции
• 4. Определение столкновений
• 5. Интерактивное создание форм
• 6. Алгоритм визуализации
• 7. Адаптированный алгоритм визуализации
• 8. Заключение
• Список литературы

Аннотация

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

Ключевые слова: Геометрическое моделирование, Функции возмущения, Бинарный поиск, Графические акселераторы, CUDA.

1.Введение

         При сканировании двумерного пространства нельзя получить полноценного трехмерного изображения. Полигональная трехмерная графика со сканированием полигонов в плоскости изображения не является трехмерной в полном смысле этого слова. Информация, которая предоставляется пользователю в такой технологии – неполная. Главное – это отсутствие информации о глубине объекта, имеется ввиду не отсутствие Z – координаты точки поверхности, а отсутствие информации о луче, проходящем сквозь объект. Кроме этого, для визуализации научных данных очень актуальны геометрические преобразования - унарные, бинарные и более сложные геометрические операции, которые наиболее оптимально решаются в рамках твердотельного моделирования и конструктивной геометрии для функциональных моделей. Например, теоретико-множественные операции, с помощью которых можно конструировать объекты и их композиции неограниченной сложности. Достигается это, в первую очередь, применением булевых операций объединения и пересечения. Процесс моделирования молекулярных и наноструктур становится значительно эффективнее, если применять функционально заданные примитивы и объемно-ориентированную визуализацию. Предлагается альтернативная технология визуализации, основанная на методе отслеживания лучей и функциональном задании примитивов в отличие от традиционной технологии отображения трехмерных сцен, построенной на методе отрисовки треугольников с помощью алгоритма z-буфера. Принципиальное отличие предлагаемого метода от остальных заключается в неполигональном представлении поверхностей молекулярных сцен и использовании алгоритма отслеживания лучей для растеризации сцены. Механизм рендеринга радикально отличается от реализованных методов в современных ускорителях компьютерной графики. Объекты представляются функционально, что обеспечивает компактность задания баз данных. Использование алгоритма отслеживания лучей решает проблемы, характерные для систем с растрированием на плоскости, и  проблемы больших объемов данных, потому что, чтобы получить полноценную трехмерную сцену молекулярных структур, необходимо иметь огромное число треугольников (сотни миллионов). Для описания даже самых простых структур необходимо иметь большое количество треугольников (Рис. 1, 2). Поскольку в сцене слишком много треугольников, если всю её рисовать, то акселератор не отобразит ее в реальном времени. Двумерные картинки хороши для того, чтобы показывать связи атома-к-атому, но этого недостаточно, когда необходимо описывать молекулярные структуры. Например, молекулярным дизайнерам необходимо знать, как одна функциональная группа входит в другую структуру, т.е. необходима трехмерная картина, с возможностью поворота сцены, перемещения и т.д. (Рис. 3). Кроме этого, трехмерные модели необходимы для показа межмолекулярных взаимодействий, при моделировании некоторых сложных движений молекул. Гипотетически существует 10 молекулярных структур (целая Вселенная), известны только 1000000, а коммерчески используются только 1000. Необходимо также хранить огромное количество информации о молекулярных структурах, необходимо сжатие. При расчете прогноза новых структур необходимо решать дифференциальные уравнения. В задачах молекулярной механики  не хватает вычислительной мощности самых современных суперкомпьютеров.

Рис. 1. Элементарная кубическая                                                      Рис. 2. Часть молекулы
кристаллическая решётка                                                               сульфаниламида

         Наиболее распространенная модель для визуализации трехмерных изображений – полигональное приближение. Наряду с множеством преимуществ, такая модель имеет и свои недостатки. Моделируя реальные объекты, строится приближенная полигональная модель. Для увеличения качества изображения чаще всего необходимо увеличивать количество полигонов. Увеличение количества полигонов, влечет за собой увеличение времени визуализации и объёма используемой памяти. К тому же, дополнительные проблемы вносит изменение масштаба объекта, потому что нельзя быстро и эффективно изменить количество полигонов для модели объекта. От таких недостатков можно избавиться, применяя аналитическое задание объёмов и растеризации их при помощи алгоритмов трассировки лучей. Аналитическое задание объёмов не требует большого объёма памяти. Проблема синтеза реалистичных изображений актуальна для различных тренажеров, виртуальных студий и трехмерных игр. На данный момент уже существуют работы по визуализации функционально заданных поверхностей, но их применение ограничено довольно узким классом поверхностей и медленной визуализацией. Используемые алгоритмы сложно оптимизировать, что также накладывает ограничения на практическое применение. В работе предлагается использовать особый класс объёмов, которые называются «свободные формы». Каждая свободная форма представляют собой базовую поверхность и возмущение на этой поверхности. Базовая поверхность и возмущение задаются полиномами второй степени – квадриками. Чтобы добиться гладкости, функция возмущения возводится в третью степень.

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

Рис. 3. Молекулярные структуры

         Отметим следующие основные функциональные способы задания примитивов. Поверхности свертки [2-4] – это интегральное представление неявно заданных поверхностей, известных в компьютерной графике как капельные модели [5, 6], метасферы [7], мягкие объекты [8]. Данные поверхности сочетают в себе гибкость капельных моделей и компактность скелетных моделей [9]. В то же время, они имеют свои недостатки, к которым можно отнести сложность вычисления точек поверхности.
Теперь рассмотрим известные методы трассировки лучей, отметим их достоинства и недостатки. 

• Маршировка по лучу [10, 11]. Это метод «грубой силы» пошаговых вычислений вдоль луча, функция вычисляется на каждом шаге. Первое изменение знака функции  сигнализирует о том, что найдена поверхность .  Главный недостаток этого метода заключается в том, что он очень медленный и не гарантирует обнаружение поверхности.
• Метод –поверхности [12]. Разработан метод обнаружения поверхности с применением - и - параметров, которые являются константами Липшица для функции и производной  вдоль луча. Для неалгебраической функции вычисления - и - параметров становятся сложными.
• Сфера-трэйсинг [13]. Недостаток заключается в том, что нахождение подходящего радиуса  - нетривиальная задача.
• Трассировка луча с анализом интервала [14]. Для сложных функций очень затратно делать вычисления для каждого луча индивидуально и для каждого интервала вдоль этого луча.
• Быстрая трассировка луча [15]. Данный метод лишен недостатков перечисленных выше методов, однако поиск лучей, пересекающих поверхности сложен и не достаточно эффективен, поскольку способы кластеризации этого метода не решают данную проблему полностью.

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

2. Геометрические объекты

         Функционально заданные поверхности строятся из поверхностей второго порядка с аналитическими функциями возмущения, благодаря чему достигается высокий коэффициент геометрического сжатия высокореалистичных трехмерных объектов (Рис. 4 и 5). Предлагается описывать геометрические объекты (свободные формы), задавая функцию отклонения (второго порядка) от базовой поверхности второго порядка (квадрики). Функция задается алгебраическим неравенством второй степени с тремя неизвестными x,y,z в виде F(X) >= 0. Рассматриваются поверхности как замкнутые подмножества Эвклидова пространства E?, определяемые описывающей функцией F(X)  >= 0. Где F- непрерывная вещественная функция.

Рис. 4. Свободная форма на основе одной квадрики с тремя аналитическими функциями возмущения; форм-фактор отрицательный

X= (x1,x2,x3) – задаваемая координатными переменными точка в E?. Здесь F(X) > 0 задает точки внутри поверхности, F(X) = 0 – точки на границе и F(X) < 0  - точки, лежащие снаружи и не принадлежащие поверхности.

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

F(x,y,z) = A11x2 + A22y2 + A33z2 + A12xy +A13 xz + A23yz + A14x + A24y + A34z + A44 >= 0  (1)

На базе квадрик строятся свободные формы. Свободная форма есть композиция базовой квадрики и возмущений [16]

                                                              (2)
где R(x,y,z) – возмущение,  fi- форм-фактор .
                        (3)

гдеQ(x, y, z) – возмущающая квадрика.  

Рис. 5. Функционально заданные объекты

         В качестве Q так же может быть возмущенная квадрика (свободная форма). Другими словами, композиция базовой квадрики и функции отклонения являются новой функцией возмущения, т.е. производной для другой базовой квадрики. Так как max[Q + R] <= max[Q] + max[R], то для оценки максимума Q на некотором интервале необходимо вычислить максимум функции возмущения на этом же интервале. Получающаяся поверхность будет гладкой (Рис. 4), и потребуется небольшое количество функций возмущения для создания сложных форм поверхностей (Рис. 5). Степень возмущения (3) можно выбирать произвольно. От этого будет зависеть гладкость переходов от базовой поверхности до области с возмущением, и соответственно, размер самого возмущения. Для того чтобы поверхность была гладкой, степень должна быть больше двух. Это условие гарантирует непрерывность функции и её производной. Таким образом, задача конструирования объекта сводится к задаче деформации базовой поверхности нужным образом, а не к аппроксимации ее примитивами.

         Рассмотрим простейший объект с одной базовой квадрикой (эллипсоидом) и двумя функциями возмущения (с положительным и отрицательным форм-факторами)  (Рис. 6).

Рис 6. Свободная форма: эллипсоид с 2 функциями возмущения 2-й степени

Рис 7. Капельная модель

         На рисунке 7 показана капельная модель, визуализированная с помощью PovRay.
         Как уже было сказано выше, для того чтобы поверхность была гладкой достаточно, чтобы степень возмущения была больше двух. Это гарантирует, что сама функция и её производная будут непрерывными. Однако уже вторая производная будет представлена в виде функции с разрывами. Причём эти разрывы будут на границе возмущений. Стоит уточнить, как будут влиять эти разрывы на изображение. В случае, когда степень меньше трёх, видно (Рис. 8), что функция нормалей непрерывна вдоль каждой из координат в силу непрерывности производных. Но, к сожалению, производная этой функции имеет разрывы, так как представляется в виде вторых производных функции плотности. Учитывая то, что используется локальная модель освещения, которая зависит от нормалей, границы возмущений будут сильно заметны. Не смотря на то, что сама поверхность имеет гладкий вид, визуально она будет восприниматься как объединение или пересечение поверхностей. Такие поверхности не представляют большого интереса, потому что визуально близкий к этому результат можно было бы получить теоретико-множественными операциями над базовыми объёмами в виде квадрик. А визуализация объёмов, заданных таким методом, -  менее трудоёмкая задача. И, что самое главное, такие объёмы не являются полностью гладкими. Поэтому используется третья степень функций возмущений, что обеспечивает гладкость не только самой поверхности, но и нормалей (Рис. 9). В этом случае переходы к области с возмущением визуально не выделяются. Такие объекты выглядят реалистичнее.

Рис 8. Степень возмущения равна двум                   Рис 9. Степень возмущения равна трем

         Особенно этот эффект заметен, когда блик попадает на границу возмущений. У объектов со второй степенью возмущений, блики разрываются (Рис. 10). Блики без разрывов изображены на рисунке 11.

         Объекты и операции могут быть следующих видов: Functionally-Based Primitive Object; Functionally-Based Complex Objects;. Базовые типы квадрик: 'ell', 'seat', 'ellpar', 'unihyp', 'duahyp', 'cone', 'cylinder', `layer', ’plane', ’clin’, ’parabola’, ’hyperbola’.
Пример сцены, состоящей из двух примитивов:

ell
{
}
cone

Сложные объекты также добавлены в стандартную библиотеку: Тор (определен ключевым словом ‘torus’); Куб (определен ключевым словом ‘cube’);
Пример:

//x.scene
cube
torus

//y.scn
object x

Рис 10. Степень возмущения равна двум                   Рис 11. Степень возмущения равна  трем

         Предложенный способ описания объектов трехмерных сцен базовыми поверхностями и функциями возмущения имеет компактное описание, что позволяет уменьшить от 10 до 1000 раз объем передаваемых данных в зависимости от конкретных трехмерных сцен и моделей. Объекты с плоскими гранями также легко задаются, например, куб может быть задан тремя квадриками. Кроме того, при решении описывающей функции в виде неравенства F(X)  >= 0, можно визуализировать не только поверхность, но и внутреннюю структуру объекта.

3. Геометрические операции

         Множество геометрических операций   математически выражается следующим образом [1].

                                                   (4)

         Реализованы следующие операции для объектов на базе функций возмущения: проекции, оффсетинг, метаморфозис, кручение и заметание движущимся твердым телом.
         Геометрическая модель должна позволять конструировать объекты и их композиции неограниченной сложности (Рис. 12). Достигается это, в первую очередь, применением булевых операций объединения и пересечения (Рис. 13). Эти операции не изменяют степень функций заданных моделей.

Рис. 12. Сложные и простые геометрические объекты

Рис. 13. Теоретико-множественные операции над объектами: объединение (слева) и пересечение (справа)

4. Определение столкновений

         Одним из примеров отношений [1] может служить определение столкновений между объектами. Бинарное отношение есть множество множества  Оно может быть определено как:

                                                                                       (5)

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

Рис. 14. Определение столкновений функционально заданных объектов на базе функций возмущения

         Пусть объекты  и  определены как и . Бинарная операция пересечения объектов   и определяется следующим образом:

                                                       (6)

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

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

5. Интерактивное создание форм

         В последнее время компьютерная графика, связанная с интерактивным моделированием и редактированием трехмерных объектов, развивается быстрыми темпами.  Известны такие коммерческие системы как SoftImage, MAYA, 3DStudioMax и др. для интерактивного редактирования полигональных моделей. Существуют интерактивные системы на базе полиномов [19], неявных поверхностей [20], треугольных сеток [21, 22], изображений [23], объемов [24-26], функционально заданных моделей [27-31].
Конструирование объекта в нашем случае, как уже было сказано выше, сводится к задаче деформации базовой поверхности нужным образом, а не к аппроксимации ее примитивами, данный процесс напоминает лепку модели из пластилина с применением геометрических операций, представленных выше, и деформации. Основное положительное отличие от известных интерактивных систем на базе функционально заданных моделей -  это то, что нет необходимости в полигонизации функциональной модели перед деформацией [32].
Для этого необходимо было решить следующие задачи.

1. Реакцию программы на события от мыши (и, соответственно, выбор и модифицирование объектов). Необходимо уметь выделять объект (или несколько объектов) в сцене и предоставлять пользователю возможность проделать с ним (с ними) некоторые операции.
2. Выбор операции – аффинные преобразования MRS (move, rotate, scale), геометрические операции или деформация (Рис. 15). Деформация состоит в возможности добавлять в любую точку на поверхности возмущение с параметрами, задаваемыми инструментом. Инструмент задает область действия и вид возмущения. Для этого необходимо графически предоставить пользователю некоторую информацию (в том числе выделять объект, например, цветом, или с помощью  bounding box, рисовать оси и т.д.). Всю отрисовку «поддержки» работы с операциями лучше производить с помощью OpenGL – для скорости и функциональности.
3. Возможность работы со списком инструментов.
4. Запись в файл и загрузка дерева сцены.
5. Возможность создания новых тэгов и их распознавания.

Рис. 15. Главное окно программы. Локальная деформация объекта

         Программная модель алгоритма растрирования и структуры данных объектов реализована на языке высокого уровня С++. Этот язык хорошо подходит для реализации объектной модели описываемой системы, так как является объектно-ориентированным.

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

         Можно также конвертировать полигональные и воксельные модели в функциональное описание [33,  34].

6. Алгоритм визуализации

         Алгебраическим неравенством второй степени (с тремя неизвестными x,y,z) называется всякое неравенство вида:

Q(x, y, z) = A11x2 + A22y2 + A33z2 + A12xy +A13 xz + A23yz + A14x + A24y + A34z + A44 >=? 0, (7)

где x, y и z - пространственные переменные. Можно записать это неравенство в матричном виде:

 >= 0,             (8)

         Алгоритм визуализации объектов, заданных квадриками, и его реализации рассмотрены в работе [16]. На первом шаге рекурсии исходный единичный куб делится на четыре меньшие части (бруски) в плоскости XY (экранной плоскости). На этапе деления пространства по четверичному дереву, где совершается сжатие в два раза и перенос на ±1 по двум координатам, рекурсивное преобразование коэффициентов квадрики выглядит так:

A11’                       =              A11/4;
A22’                       =              A22/4;
A33’                       =              A33;
A12’                       =              A12/4;
A13’                       =              A13/2;
A23’                       =              A23/2;
A14’                       =              A14/2     +              i A11/2           +              j A12/4;
A24’                       =              A24/2     +              i A12/4           +              j A22/2;
A34’                       =              A34         +              i A13/2           +              j A23/2;                                       (9)
A44’                       =              A44         +              i A14/4           +              j A24/4;
A44’’                      =              A44’       +              i A14’/2          +              j A24’/2.

где коэффициенты без штриха берутся с предыдущего шага рекурсии; переменные i, j = ±1 определяются в зависимости от направления погружения в рекурсию (i - по оси x, j - по оси y). Полученные коэффициенты используются в тесте на пересечение. Для каждого нового бруска выполняется тест на пересечение с объектом. Если в уравнении квадрики Q(x, y, z) = 0 значения переменных x, y, z меняются в пределах отрезка [-1, 1], то

max[ |Q(x, y, z) – A44| ] ? maxF = |A11|+|A22|+|A33|+|A12|+|A13|+|A23|+|A14|+|A24|+|A34|        (10)

         Теперь заметим, что если |A44| ? max[ |Q(x, y, z) – A44| ] ? maxF, то, возможно, существует точка M0 = (x0, y0, z0) ( -1 < x0, y0, z0 < 1 ) такая, что Q(x0, y0, z0) = 0. Если же maxF < |A44|, то заведомо таких точек не существует, а знак коэффициента A44 различает расположение бруска текущего уровня внутри или снаружи по отношению к поверхности квадрики Q=0 (если A44 >= 0, тогда брусок внутриквадрики). На основании результатов этого теста осуществляется деление брусков, которые лежат внутри квадрики целиком или, возможно, частично, а заведомо внешние бруски исключаются из обработки. Тест на пересечение брусков со свободными формами несколько отличается. Для базовой квадрики тест на пересечение выглядит следующим образом:

Если ( ( A44+R ) < 0 ) && ( |A11|+|A22|+|A33|+|A12|+|A13|+|A23|+|A14|+|A24|+|A34| < -(A44+R ) ) тогда брусок находится снаружи;                                                                       (11)

Здесь R - есть максимум функции возмущения на текущем интервале, а буквы Aij - коэффициенты квадратичной функции. Для функции возмущения проводится тест:

Если ( |A11|+|A22|+|A33|+|A12|+|A13|+|A23|+|A14|+|A24|+|A34| < |A44| ) тогда брусок  находится снаружи области определения возмущения;                                         (12)

где Aij - коэффициенты квадратичной функции возмущения, и дополнительно вычисляется значение R, которое служит добавкой к базовой функции. Если пересечение имеет место, то брусок подвергается следующему уровню рекурсии. Бруски, не пересекающиеся с объектом, дальнейшему погружению в рекурсию не подлежат, что соответствует исключению из рассмотрения квадратных областей экрана, на которые данный брусок (следовательно, и поверхность объекта) не отображается (Рис. 16). Деление пирамиды видимости ведется до тех пор, пока не достигается максимально установленный уровень рекурсии. Преимущество этой методики в том, что она позволяет на ранней стадии отбросить большие части пустого пространства. В процессе поиска вокселов, содержащих в себе участки поверхности объекта, формирующие изображение, осуществляется обход пирамидального пространства по четверичному дереву, листья которого являются корнями двоичных деревьев. В процессе обхода дерева используется механизм маскирования в случае непрозрачных объектов. Метод многоуровневого отслеживания лучей позволяет эффективно и быстро определить принадлежность лучей разных уровней (брусков) поверхностям и отбраковать области пространства вне объектов.

Рис. 16. Проекции брусков разных уровней на экранную плоскость

        При визуализации поверхности проверяется тест на принадлежность лишь пересеченных вокселов (единичных элементов объема), внешние и внутренние вокселы отбраковываются. Для того чтобы повысить реалистичность изображения и расширить класс отображаемых объектов (полупрозрачные структуры с внутренним распределением плотности, 3D текстуры) необходимо отображать внутреннюю полупрозрачную структуру объекта. Для этого в формировании изображения должны участвовать не только вокселы, которые лежат на поверхности, а также и те, которые находятся внутри объекта. Следовательно, при делении объема внутренние части объекта не отбрасываются, для них проводится дальнейшая рекурсия алгоритма. При сканировании сцены по Z координате, что соответствует сканированию объема в глубину, сканирование не прерывается при встрече с поверхностью, а работает далее, пока полностью не просканируется объем, или не накопится определенное значение прозрачности, большее некоторого порогового значения. Для уменьшения времени вычислений алгоритм адаптирован к быстрому прохождению однородных областей объектов, для которых совсем необязательно полностью сканировать объем, доходя до последнего уровня рекурсии, а следует ‘проскакивать’ пустые или однородные участки по Z координате, и сразу же вычислить цвет и общую прозрачность. Так как прохождение лучом пустого пространства не вносит вклад в конечное изображение, то скачок через пустое пространство способен обеспечить существенное ускорение обработки и не влияет на качество изображения.

Вычисление цвета.

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

C = (QambiCambi + QdiffCdiff + QspecCspec) / (Qambi + Qdiff + Qspec);                                             (13)

где индекс “ambi” относится к характеристикам рассеянного излучения, а “diff” и “spec” - к диффузной и зеркальной частям отраженного света соответственно; C - компоненты цвета; Q - весовые коэффициенты. Вычисления компонент цвета производятся на основе векторной модели освещения. В расчетах участвуют четыре вектора: нормаль к поверхности (n), вектор на источник освещения (l), направление отраженного света (r) и вектор на наблюдателя (v):
Cdiff = (n, l) Clite Csurf; где Clite - цвет источника, Csurf - цвет поверхности.
Cspec = (r, v)p Clite; где p - коэффициент шероховатости поверхности. При моделировании прохождения света через полупрозрачные среды в целях уменьшения количества вычислений можно не учитывать преломление и затухание вторичных лучей. В случае, когда остается только отражение и затухание света на пути следования от объекта к глазу наблюдателя, формулу, по которой вычисляется цвет пиксела, можно выразить следующим образом:

                                                              (14)

где   - конечный цвет пиксела, а  может быть r, g или b (т.е. красный, зеленый или синий, соответственно),  -  интенсивность в n-ом вокселе, вычисленная по модели освещения Фонга,   - непрозрачность n-го воксела.   - отраженный свет от первой точки на луче сканирования,   - цвет фона и . Преодоление порога можно отследить следующим образом, - если на k-ом шаге общая прозрачность  становится меньше некоторого , то это значит, что вклад всех следующих за k-ым вокселей будет малым и, поэтому, сканирование можно прекратить.

        Чтобы учесть перспективу, следует внести поправку в алгоритм накопления цвета в пикселе. Дело в том, что размеры воксела, в результате трансформации геометрических примитивов, становятся зависимыми от координаты Z, поэтому при пересчете цвета в пикселе прозрачность воксела следует также пересчитывать с поправкой на изменение его длины.
Текстурирование объектов на базе функций возмущения описано в работах [35,  36].

7. Адаптированный алгоритм визуализации

        Вышеописанный алгоритм включает два дерева деления объектного пространства: четверичное и двоичное деревья. В таком виде алгоритм не годится для реализации на графическом акселераторе (GPU). Поэтому стояла задача его адаптации для GPU. Для простоты понимания будем считать, что сцена находится в единичном трёхмерном кубе (Рис. 17). Перспектива рассматриваться не будет, ввиду того что она сводится к переходу в другую систему координат. Пирамида видимости будет представлять собой куб в новой системе координат. Поэтому опустим начальные преобразования и уделим больше внимания основной части алгоритма. Будем считать, что наблюдатель смотрит вдоль оси Z. Необходимо получить проекцию сцены на плоскость XY. Проекция должна представлять собой конечный набор значений. Поэтому весь куб будет делиться на "бруски" так, чтобы каждый брусок соответствовал пикселу на изображении. Каждый из брусков будет делиться вдоль оси Z, образуя набор вокселей (Рис. 18). Так как размеры бруска в плоскости XY значительно меньше, чем в направлении оси Z, брусок можно рассматривать как луч. Таким образом, получим функцию плотности вдоль луча, которая зависит от одной переменной. Задача будет состоять в нахождении первой точки, в которой функция обращается в ноль. При нахождении такой точки для каждого луча будет известна глубина кадра. Данными приближениями задача сводится к задаче отслеживания лучей. Далее в каждом пикселе можно вычислить нормаль. А имея данные о глубине и нормали в каждом пикселе, можно использовать модель локального освещения. В итоге получится изображение гладкого объекта с учётом освещения. Главной частью работы является эффективное нахождение первого пересечения луча с поверхностью.

Рис. 17. Единичный куб

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

Рис. 18. Бинарное деление луча для вычисления пересечения луча с поверхностью

        Во второй части метод остаётся прежним. В этом случае уменьшение времени на визуализацию достигается за счёт эффективного использования вычислительных ресурсов графического акселератора. Для реализации была использована Compute Unified Device Architecture (CUDA) от компании NVIDIA. CUDA - это модель параллельного программирования вместе с набором программных средств, которая позволяет реализовывать программы на языке C для исполнения на графическом акселераторе.

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

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

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

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

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

        Было реализовано приложение, которое визуализирует свободные формы, заданные квадриками с возмущениями на графическом акселераторе. В функции графического акселератора входили расчёт глубины кадра, нормалей и освещения. Центральный процессор (ЦПУ или CPU) использовался для геометрических преобразований. Для отображения изображения использовалась DirectX.  Тестирование производилось на процессоре Intel Core2 CPU E8400 3.0 GHz, GPU 9800 GT и 470 GTX. На рисунке 19 показана диаграмма: по оси абсцисс отображен номер теста, по оси ординат – количество кадров в секунду для разных тестов. На рисунке 20 показано среднее время на кадр для разных тестов, а на рисунке 21 – ускорение относительно E8400.

Рис. 19. Диаграмма тестов: количество кадров в секунду для разных тестов

Рис. 20. Диаграмма тестов: среднее время на кадр для разных тестов

Рис. 21. Диаграмма тестов: ускорение относительно E8400 для разных тестов

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

Таблица 1

Продолжение таблицы 1

Таблица 2

Примечание: 5 тест отсутствует, ввиду простоты объекта при тестировании.

        В работе [37] описан метод визуализации алгебраически заданных поверхностей. В этом методе применяются поверхности заданные полиномом высокой степени. Используется метод отслеживания лучей. Предложен эффективный метод нахождения первого пересечения луча с поверхностью. Идея метода состоит в том, что функция, заданная вдоль луча, приближается кривой Безье. Существуют методы нахождения точки, в которой кривая пересекает ось. Причём эти методы гораздо эффективнее, чем методы, которые можно было бы использовать для произвольного полинома высокой степени. Для полиномов шестой степени этот метод эффективнее, чем метод, используемый для визуализации квадрик с возмущением. Но класс поверхностей, которые можно описать квадриками с возмущениями гораздо шире, чем те, что описываются полиномами шестой степени. Чтобы с помощью обычного полинома задать сложную поверхность, необходимо увеличивать его степень. К тому же моделировать реальные объекты с помощью полиномов сложнее, чем квадриками с возмущениями. И необходимо обратить внимание на точность, с которой находится точка пересечения луча. В случае с кривыми Безье гарантируется высокая точность нахождения пересечения с кривой, но не гарантируется то, насколько точно начальная функция будет приближена этой кривой. Ещё одним недостатком этого метода является то, что перевод объекта в другую систему координат – не простая задача. Поэтому создание динамических сцен становиться проблематичным.
Известен ещё один метод визуализации с применением GPU аналитически заданных объектов [38], основанный на отслеживании лучей (Sphere Ray Tracing Implicit Surfaces on the GPU). Он основан на обычном пошаговом отслеживании. Отличием является то, что размер шага не постоянен, а выбирается на каждом шаге. На каждом шаге находится шар с центром в текущей точке на луче. Радиус шара выбирается так, чтобы ни одна точка объёма не лежала внутри него. Выбрав такой шар можно делать шаг в направлении луча на радиус шара. Очевидно, что радиус должен быть наибольшим. Процесс продолжается, пока радиус не превышает выбранной погрешности. Таким образом, скорость поиска будет не медленнее, чем при обычном пошаговом поиске с шагом, равным размеру погрешности. Но почти во всех случаях, используя такой алгоритм, можно найти точку пересечения за меньшее количество шагов. Недостаток заключается в том, что нахождение подходящего радиуса -  нетривиальная задача. Для статичных сцен авторы алгоритма использовали предварительную обработку данных. В этом случае можно добиться неплохой производительности. Но такой метод можно применять только тогда, когда объекты статичны. То есть, когда форма и масштаб самих объектов не изменяется. В таком случае эффективнее будет использовать полигональное задание объекта. На стадии предварительной обработки данных построить сетку и использовать её для визуализации. Поэтому, как и в предыдущем методе, визуализация объектов, которые изменяют свою форму и положение во времени, не эффективно.
Вышеперечисленные методы сложно оптимизировать, что также накладывает ограничения на практическое применение.

8. Заключение

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

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

Рис. 22. Криволинейные формы

Рис. 23. Полупрозрачная  поверхность

        Время визуализации зависит от сложности объекта (Рис. 22 и 23). Для задания более сложных объектов требуется больше возмущений. Производительность сильно зависит от скорости памяти. Поэтому наибольшей производительности можно достичь при использовании только регистров.
        В настоящее время в связи с развитием вычислительной техники численное решение задач трехмерной геометрии, требующих больших вычислительных ресурсов, находит все большее применение в реальных приложениях. Это моделирование динамики твердых и деформируемых тел, решение задач в области вычислительной биологии, молекулярного моделирования и т. д. Компьютерное трехмерное геометрическое моделирование позволяет получить и исследовать геометрические параметры объекта, проанализировать механические свойства, динамику поведения и взаимодействия объектов. Многообразие задач геометрического моделирования требует разработки эффективных методов и алгоритмов формирования компьютерных трехмерных геометрических моделей, способных обеспечить высококачественную и информативную визуализацию в реальном времени, используя стандартные современные программно-аппаратные средства. Функциональное задание объектов особенно актуально в ряде задач компьютерной графики, включая моделирование мягких или органических объектов, трехмерного морфинга, определения столкновений объектов и конструктивной блочной геометрии. Области применения функциональных объектов  - это молекулярная биология, интерактивные графические системы визуализации, CAD-системы, системы 3D-моделирования, 3D веб-визуализация и т.д.

Список литературы

1. Pasko A., Adzhiev V., Sourin, A., et al. Function representation in geometric modeling: concepts, implementation and applications //The Visual Computer, 11, 6, 1995, P 429.

2. Bloomenthal J., Shoemake K. “Convolution surfaces”, SIGGRAPH’91, Computer Graphics,- 1991.- Vol.25.- No.4. - P 251-256.

3. G. Sealy, G. Wyvill. Smoothing of three dimensional models by convolution. In Computer Graphics International’96.- June 1996.- P 184-190.

4. McCormack J., Sherstyuk A. Creating and rendering convolution surfaces. Computing Graphics Forum.- 1998.-Vol. 17.- No.2.- P 113-120.

5. J. F. Blinn. A generation of algebraic surface drawing. ACM Transactions on Graphics.- July 1982.- 1(3)- P. 235-256.

6. S. Muraki. Volumetric shape description of range data using “blobby model”. Computer Graphics.- July 1991.- 25(4)- P. 227-235.

7. H. Nishimura, M. Hirai, T. Kawai, T. Kawata, I. Shirakawa, and K. Omura. Object modelling by distribution function and a method of image generation. The Transactions of the Institute of Electronics and Communication Engineers of Japan.- 1985.-J68-D (4)- P. 718-725.

8. G. Wyvill, C. McPheeters, and B. Wyvill. Data structure for soft objects. The Visual Computer.- 1986.- 2(4)- P. 227-234.

9. Bloomenthal J.  Skeletal Design of Natural Forms. Doctoral dissertation. University of Calgary. Department of Computer Science.- 1995.

10. Tuy, H. and Tuy, L. Direct 2-D Display of 3-D Objects, IEEE Computer Graphics and Applications 4, 10 (October 1984), P. 29-33.

11. K. Perlin, E. M. Hoffert. Hypertexture. Proceedings of the 1989 ACM SIGGRAPH conference, Volume 23 ,  Issue 3  (July 1989), P. 253 – 262.

12. D. Karla and A.H. Barr. Guaranteed ray intersections with implicit surfaces. Computer Graphics, 23:297-306, November 1989.

13. J. C. Hart. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces.  The Visual Computer, 12:527-545, 1994.

14. D. Mitchel. Robust ray intersection with interval arithmetic. In Proceedings on Graphics Interface 1990, P. 68-74. 1990.

15. А. Sherstuyk. Fast ray tracing of implicit surfaces. In Implicit Surfaces’98.- June 1998.- P. 145-153.

16. Вяткин С.И., Долговесов Б.С., Есин А.В. и др. Геометрическое моделирование и визуализация функционально-заданных объектов // Автометрия. 1999. N6. С. 84.

17. Savchenko V.V., Pasko A.A. Collision detection for functionally defined deformable objects: The First International Workshop on Implicit Surfaces (Grenoble, France.- April 18-19, 1995) /Eds. B.Wyvill and M.P. Gascuel: Eurographics-INRIA.- P.217-221.

18. Vyatkin S.I., Dolgovesov B.S. Collision Detection of Functionally Defined Objects for Constant Time // Proc. of 15-th International Conference on Computer Graphics GraphiCon ’2005.- (Novosibirsk.- 2005).- P. 164-169.

19. Alias Wavefront 2001. Maya. http//www.aliaswavefront.com.

20. R.N. Perry and S.F. Frisken. Kizami: A System for Sculpting Digital Characters, in SIGGRAPH’01- 2001.- P. 47-56.

21. M. Agrawala, A.C. Beers and M. Levoy, M. 1995. 3D Painting on Scanned Surfaces.- ISBN 0-89791-736-7. 1995- P. 145-150.

22. Right Hemisphere 2001. DeepPaint3D. http//www.us.deeppaint3d.com.

23. B.M. OH, M. Chen, J. Dorsey and F. Durand. Image-based modeling and photoediting, in SIGGRAPH’01.- 2001.- P. 433-442.

24. E. Ferley, M.-P. Cani and J.-D. Gascuel. Virtual Sculpture, Visual Comput 16:8.- 2000.- P. 469-480.

25. S. Wang and A. Kaufman. Volume Sculpting, in SIGGRAPH’95.- 1995.- P. 151-156.

26. J. Baerentzen. Octree-based Volume Sculpting, Proc. Late Breaking Hot Topics, IEEE Visualization’98.- 1998.- P. 9-12.

27. A.Sourin. Functionally based virtual embossing. The Visual Computer.-7-2001.- P258-271.

28. A.Sourin. Functionally based virtual computer art. The 2001 ACM Symposium on Interactive Computer Graphics, I3D2001, Research Triangle Park, NC, USA, 19-21, March, 2001, ACM ISBN: 1-58113-292-1.-P. 77-84.

29. K.Levinski and A.Sourin, Interactive function-based artistic shape modeling. 2002 International Symposium Cyber Worlds: Theory and Practice 2002, Tokyo, Japan 6-8 November, 2002.-P.521-528.

30. K.Levinski and A.Sourin, Interactive Function-Based Shape Modeling for Cyberworlds, 2004 International Conference on Cyberworlds, Tokyo, 18-20 November, 2004.-P.54-61.

31. Savchenko V., Pasko A., Kunii T., et al. Feature based sculpting of functionally defined 3D geometric objects" // Multimedia Modeling. Towards Information Superhighway, T.S. Chua, H.K. Pung and T.L. Kunii (Eds.), World Scientific, Singapore, 1995, P. 341-347.

32. Вяткин С.И., Долговесов Б.С.  Интерактивная система для создания форм на базе функций возмущения // Труды 16-й Междунар. конф. по компьютерной графике и ее приложениям "Графикон-2006" (Новосибирск, Россия, 1-5 июля 2006). Новосибирск, ИВММГ СО РАН, 2006.

33. Vyatkin S., Dolgovesov B. Converting polygonal and voxel models into function-based description // 8th International Conference “Pattern Recognition and Image Analysis: New Information Technologies” (PRIA-8-2007): Conference Proceedings, vol. 1. (Yoshkar-Ola, Russia, October 7–12, 2007). P. 220–224.

34. Вяткин С.И. Преобразование полигональных моделей в функционально базируемые объекты // Международный научно-технический журнал <Измерительная и вычислительная техника в технологических процессах>, 2008, Хмельницкий национальный университет, г. Хмельницкий, Украина, 2008, № 1. С. 146-150.

35. Вяткин С.И., Долговесов Б.С., Каипов Н.Р. Отображение текстуры  на плоские и криволинейные поверхности, свободные формы и объемы // Автометрия. 2002. N1.С.17-24.

36. S.I.Vyatkin. A 3D Texture-Based Rendering Algorithm, Computer Graphics and Geometry, Volume 8, Number 3, Winter, 2006. http://www.cgg-journal.com/issues.htm http://www.cgg-journal.com/2006-3/05.htm

37. M. Reimers, J. Seland. Ray Casting Algebraic Surfaces using the Frustum Form. Eurographics, Vol. 27 (2008), No. 2, 361-370.

38. G. Liktor. Ray Tracing Implicit Surfaces on the GPU. Computer Graphics and Geometry, Vol. 10, No. 3, 2008, 36-53. http://www.cgg-journal.com/2008-3/04.htm