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

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

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

Ни одна из архитектур не позволяет линейно масштабировать производительность систем [1]. Когда вычислительная нагрузка достигает предела производительности одного графического конвейера, тогда для получения желаемого ускорения необходимо ставить параллельно несколько конвейеров и подбирать подходящий метод распределения данных. Частичным решением данной проблемы является так называемая тайловая технология (Tile Technology) [2] или, реализованная в системе визуализации " Ариус" виртуальная методика визуализации [3], [4]. Однако ограничения, создаваемые промежуточной виртуальной памятью - буфером тайлов (Tile Buffer) и дополнительная транспортная задержка вычислительного тракта не позволяют использовать данную технологию для приложений, где эти ограничения существенны (научная визуализация и авиасимуляторы военного назначения).

С другой стороны, доводы в пользу того, что треугольник является самой простейшей фигурой в природе, с помощью которой можно отобразить все, не совсем верны. Так, в тренажерных системах военного назначения изображение проецируется на купол (Dome) [5], и искажения, вносимые как самим криволинейным экраном, так и перемещениями наблюдателя и проектора, необходимо корректировать (DDC - Dynamic Distortion Correction). Следует отметить, что в этом случае, когда угол обзора (FOV - field of view) больше, чем 180 градусов, Z-буфер не может решить задачу определения видимости многоугольников по глубине z, которые пересекают плоскость z=0. R-буфер решает эту проблему, вычисляя истинный диапозон (range) точек двух объектов, одна из которых видима наблюдателю. Изображение может проецироваться непосредственно прямо на сетчатку глаза человека с помощью персонального проектора, и это устройство может заменить дисплей компьютера.

С эгоцентрической точки зрения наблюдателя окружающее его пространство является сферическим [6]. В этом случае отображение также будет нелинейным (NLIM - non-linear image mapping), как и в первом примере. Треугольник уже не будет той простой фигурой, к которой все привыкли, а будет менять свою форму (искривляться) и не будет плоским. Можно обойти эту проблему и делить треугольник на более мелкие и плоские, но, с одной стороны, для сильных искажений трудно или почти невозможно сделать триангуляцию, с другой, - где предел решений методом грубой силы (brute force)? Автор считает что, технологии, основанные на полигональном задании объектов, достигли предела и приводит перечень основных проблем полигональной технологии:

1. На границе силуэта проявляется многоугольная структура объекта, т. е. граница имеет форму ломаной. Следовательно, полностью скрыть " граненость" тела не удается. Обычно этот дефект частично устраняется более точной аппроксимацией поверхности, что требует увеличения количества многоугольников.

2. Большое количество " мелкого мусора" - вырожденных граней, которые удалить на раннем этапе довольно трудно.

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

4. Сложность визуализации аморфных объектов (облака, дым и т.д.).

5. Проблемы приоритетов, определения и смены уровней детальности, клиппирования многоугольников пирамидой видимости и т.д.

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

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

8. Сложность анимации поверхностей и морфинга объектов. Морфинг негомеоморфных объектов (тора и сферы) и морфинг с ограничениями невозможен без разрыва поверхности и последующего " склеивания" последней. Это доступно технологиям с функциональным описанием примитивов.

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

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

Способы задания свободных форм объектов. Характерной особенностью предлагаемых способов задания свободных форм является, то что:

· Основными примитивами выбраны поверхности второго порядка - квадрики. Квадрик определяется с помощью вещественной непрерывной описывающей функции трех переменных (x1, x2, x3) в виде F(X) 0. Рассматриваются квадрики, как замкнутые подмножества Евклидова пространства En, определяемые описывающей функцией F(X) 0, где F - непрерывная вещественная функция и X= (x1, x2, x3) - задаваемая координатными переменными точка в En. Здесь F(X) > 0 задает точки внутри квадрика, F(X) = 0 - точки на границе и F(X) < 0 - точки, лежащие снаружи и не принадлежащие квадрику. На базе квадриков строится первый класс свободных форм с использованием вещественных функций возмущения. Класс свободных форм такого типа выгодно применять при синтезе искусственных (рукотворных) объектов.

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

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

· Применять треугольники там, где это выгодно (плоские грани стен домов, кристаллов и т.д.).

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

RTViz (Real Time Visualization) - Mitsubishi Electric и 3Dlabs анонсировали новую систему, в которой наряду с воксельным массивом данных будут и треугольники. Существует система реального времени, позволяющая отображать объёмные данные, представленные одним трёхмерным массивом значений. В предлагаемой автором системе, можно отображать скалярные массивы, аналитически заданные объекты и их произвольную комбинацию, что значительно расширяет область применения.

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

Сцена на рисунке 15.1, описанная 6 свободными формами с аналитическими функциями возмущения (всего 42 функции), требует в 500 раз меньше информации по сравнению с заданием ее полигонами.	На рисунке 15.2 показана полупрозрачная поверхность, описанная четырьмя функциями второго порядка, заполненная трехмерной текстурой
На рисунке 15.3 показан результат моделирования аморфного объекта (трехмерного облака с непрозрачным объектом внутри облака) с применением данного вида свободных форм.	На рисунке 15.4 показан результат моделирования рельефа местности без предварительной триангуляции с билинейной интерполяцией значений высот с разрешением карты высот 200x200

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

На базе квадриков строятся свободные формы. Свободная форма есть композиция базового квадрика и возмущения ), где функция возмущения R(x, y, z) находится следующим образом:

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

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

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

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

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

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

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

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

Поскольку во время растеризации необходимо оценивать максимум функции на трехмерном или одномерном интервале, то для эффективности вычислений предварительно составляются карты уровней детальности. Исходные данные составляют уровень n, если размерность сетки равна 2ⁿ x 2ⁿ. Данные для уровня n-1 получаются выбором максимума из четырех смежных значений уровня n, остальные три далее не учитываются, т.е. получаем размерность сетки 2^n-1 x 2^n-1. Уровень 0 состоит из единственного значения - максимума по всей карте высот. Т.е., можно рассматривать карту высот как текстуру формы.

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

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

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

· Уменьшение количества поверхностей для описания криволинейных объектов. Задание объектов поверхностями свободных форм сокращает в 500 и более раз описание баз данных по сравнению с заданием их полигонами. На рисунке 1 показан результат моделирования объекта сцены с помощью свободных форм, на описание, которого потребовалось 4K байт информации, что в 500 раз меньше полигонального описания, которое составило бы 2Mбайт информации.

· Снижение нагрузки на геометрический процессор и уменьшение потока данных от него в видеопроцессор.

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

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

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

· Простота анимации, деформации и морфинга объектов.

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

Контрольные вопросы:

1. Как развивались способы отображения рисунков и сцен на ПК?

2. Какие программы для визуализации объектов вам знакомы?

3. В чем сущность процессов анимации?