В.К. Гилой, Г. Расселер,
ГМД Институт Компьютерной Архитектуры и Программных Технологий
w.giloi@first.gmd.de
Д. Джакел,
Университет Ростока

Алгоритм Фонга против алгоритма Гуро
Теория функционирования системы VISA
Общая архитектура рендерера реального времени системы VISA
Процессор рендеринга
Преимущества и ограничения метода карт отражений
Параллельньй рендеринг
Заключение. Развитие работ
Литература

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

Конструирование высокореалистичных систем 3D рендеринга реального времени определяется тремя требованиями:

1) Система должна производить рендеринг наиболее сложных сцен в реальном времени, т.е. со скоростью 20-30 кадров в секунду. Максимальная производительность рендеринга современных графических станций составляет свыше миллиона полигонов в секунду в сочетании со сглаживанием, наложением изображений и т.д.

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

3) Все эти качества системы должны обеспечиваться с максимальной ценовой эффективностью.

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

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

Алгоритм Фонга против алгоритма Гуро

Объекты с отражающими поверхностями могут быть визуализированы на обычных аппаратных средствах, применяемых для интерполяции Гуро, с использованием подхода "грязная закраска Фонга". Недостатком этого метода является появление скачков освещенности. Для получения удовлетворительных результатов визуализации приходится примерно на порядок увеличивать количество полигонов сетки, определяющих поверхность объекта.

Иногда приводится аргумент, что в приложениях САПР из-за высоких требований к точности аппроксимации все равно необходимо большое число полигонов. Однако такая аргументация "смешивает яблоки и апельсины". Точность аппроксимации в САПР относится к абстрактному математическому представлению объектов. Для рендеринга же таких объектов требуется триангуляция их поверхностей. Затем к построенным таким образом полигонам применяется интерполяционный метод (Гуро или Фонга). Отсюда следует, что степень точности триангуляции, определяется исключительно требуемым качеством рендеринга и никак не связано с точностью аппроксимации математического представления.

Чтобы получить качество рендеринга, лучшее, чем при интерполяции Гуро, предпринимались попытки сделать закраску Фонга пригодной для эффективной аппаратной реализации. Один из подходов сводился к увеличению производительности аппаратуры путем вычисления интерполяции и уравнения отражения света с помощью опережающих разностей [1]. Группа специалистов во главе с W.Deering представила модель VLSI-подхода для закрашивателя по вектору нормали (NVS) - чипа, пригодного для закраски Фонга [2]. Производительность рендерера с 16 чипами NVS оценивалась в 220.000 треугольников и 25 миллионов пикселей. Bishop & Weimar предложили метод, аппроксимирующий обычную интерполяцию Фонга и уравнение отражения света рядами Тейлора [3]. Этот метод - быстрая закраска Фонга, уменьшает число шагов вычислений всего до пяти сложений и одного доступа к памяти в расчете на пиксель. Однако дополнительно вычисляется ряд Тейлора,что требует 500 операций с плавающей точкой на вершину полигона, а это делает метод слишком медленным. В альтернативе, предложенной Clausen, интерполируются полярные векторы. Недостатками этого подхода являются высокие погрешности интерполяции при обработке больших полигонов и дополнительные вычисления для преобразования систем координат. Справедливости ради следует отметить, что все эти подходы не привели к созданию быстрой и экономичной аппаратуры для рендеринга Фонга - вот почему все современные коммерческие системы все еще работают с закраской Гуро.

В противоположность всем другим попыткам в этой области с 1988 года в GMD FIRST был разработан ряд уникальных решений [4], которые привели к созданию прототипов рабочих станций с закраской Фонга в реальном времени. Эти Ч? SI-системы, названные VISA (visualization accelerator), с того времени достигли зрелости коммерческого продукта. В последующих разделах мы опишем модель освещенности, на которой основывается рендерер Фонга в VISA, архитектуру аппаратуры и достигнутые характеристики.

Теория функционирования системы VISA

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

Направление нормали N=[xn yn zn] задается углами а1 и a2:

a1 = arctan (xn/zn), a2 = arctan (yn/zn).

Из упрощенной геометрии модели освещенности следует, что количество света, которое отражается от поверхности объекта, задается функцией, зависящей только от двух углов а1 и a2:

r = f (a1, a2).

Значения количества света r могут быть вычислены предварительно для всех комбинаций al, а2 и сохранены в карте отражений. Следовательно, интенсивность света для данного вектора нормали N может быть получена путем вычисления пар углов (al, a2), определяющих направление N, по которым затем из двумерной таблицы с прямым доступом извлекается значение r. Достаточно предварительно вычислить г - значения для относительно небольшого числа углов а1 и а2. В системе VISA берется 180x180 32400 комбинаций al, а2, т.е. таблица содержит приблизительно 32К элементов.

Общая архитектура рендерера реального времени системы VISA

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

Главную роль в двухпроцессорном узле MANNA играют два суперскалярных процессора Intel i860 с совместной пиковой производительностью 100 MFLOPS. Оба процессора работают на (разделяемом) узле памяти со схемой доступа 7-1-1-1 и пиковой пропускной способностью 400 Мбайт/с, что весьма близко к скорости вторичного кэша. - Параллельная операционная система РЕАСЕ, специально разработанная для MANNA, привносит значительно меньше накладных расходов, чем микроядро стандартных операционных систем, используемых сейчас для коммерческих параллельных компьютеров.

Внутренние связи в MANNA основываются на новаторской концепции иерархии кросс-шин. Такая топология позволяет увязать скорость связи (100 Мбайт/с) с предельной ценовой эффективностью и дает возможность реализовать очень большое число связей. Следовательно, вероятность блокирования очень мала и нет лишних затрат на связь между удаленными узлами.

В связке MANNA - VISA задача системы MANNA состоит в вычислении набора параметров, которые требуются для инициализации процессора рендеринга (VISA), а также выполнение в режиме онлайн геометрической обработки, являющейся частью рендеринга. Геометрическая обработка состоит из следующих шагов:

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

Согласно эталонному тестированию, в компьютере MANNA один узел может обработать от 30.000 до 35.000 треугольников. Узел MANNA имеет пиковую производительность 100 MFLOPS. Для компьютера MANNA из 20 узлов, который имеет скорость передачи данных в рендерер 50 Мбайт/с на канал, была достигнута скорость рендеринга около 600 тыс. полигонов в секунду (если бы не было ограничений на полосу пропускания связи, можно было бы рассчитывать на 700 тыс. треугольников). Потенциальная производительность рендеринга в VISA, составляющая до 2.4 (1.3) миллионов полигонов в секунду при 15 (3) пикселях/полигон, требует такой платформы геометрической обработки, которая состоит по-крайней мере из 64 узлов типа MANNA и имеет скорость передачи данных 156 (85) Мбайт/с на канал.

Компьютер МЕТА - следующее поколение архитектуры FIRST, будет оснащен четырьмя процессорами Motorola PowerPC 620 с общей пиковой производительностью от 800 до 1000 MFLOPS на узел. Скорость передачи данных достигнет 150 Мбайт/с. С такими характеристиками производительности относительно маленькая "супер рабочая станция", имеющая скажем, 8 узлов (32 процессора) будет удовлетворять требованиям к геометрической обработке для системы следующего поколения VISA Н.

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

Процессор рендеринга

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

Набор параметров, инициализация

Перед выполнением рендеринга полигона необходимо инициализировать некоторые регистры конвейеров XYZ и RGB нужным набором параметров, определяющим геометрию спроецированного полигона в соответствии с требованиям аппаратуры. Этот набор включает следующую информацию: число сканирующих линий полигона (nl, n2);

-начальные координаты Pstart;
- приращения наклона ребра (ru, lu, rd, 1d);
- параметры наклона поверхности в приращениях по х- и у-направлениям (zx, zy);
-начальный вектор;
-вектор приращений.

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

Конвейер XYZ

Конвейер рендеринга делится на Инициализатор Сканирующей Линии (SLI) и Вычислитель Пиксельных Координат (РСС). SLI вычисляет пиксельные координаты в начальной и конечной точках каждой сканирующей линии. Алгоритм состоит из четырех шагов расчета затравочных координат линейной интерполяции на основе заранее подсчитанных параметров ребра и наклона. РСС выполняет линейную интерполяцию координат всех пикселей сканирующей линии. Вычисляются только к-координаты, т.к. у-координаты сканирующих линий постоянны, а х-координаты увеличиваются с единичным шагом.

Закрашиватель по Вектору Нормали и конвейер RGB

Конвейер RGB состоит из Инициализатора Вектора Нормали и Закрашивателя по Вектору Нормали. Инициализатор Вектора Нормали вычисляет компоненты вектора пикселя в начальной точке сканирующей линии. Это делается аналогично вычислению z-координат. Закрашиватель по Вектору Нормали (NVS) является оригинальным компонентом системы VISA. NVS реализует метод карты отражений закрашивания по Фонгу, т.е. его работа основывается на упрощенной модели освещенности, которая введена в разделе 3.

По аналогии с расчетом z-координат NVS вычисляет вектор нормали N [xn, yn, zn] к пикселю сканирующей линии. Вектор нормали первого пикселя сканирующей линии задается затравочным значением Ni, а нормали всех следующих пикселей определяются из этого значения последовательно:

Н := N + dNx

На следующем шаге обработки компоненты нормали к пикселю преобразуются из [xn, yn, zn] в [xn/zn, yn/zn, 1]. Полученный таким образом вектор позволяет непосредственно получить углы направлений а1 и а2 из двух arctan - таблиц. Совокупность этих двух углов используется, как ключ в прямоадресуемую таблицу Карта Отражений, из которой за один такт извлекается значение отражения r. Для того, чтобы обеспечить возможность "прогулки" по последовательности изображений или просмотр объектов с различными отражательными свойствами поверхности, аппаратура закрашивателя VISA имеет память на 8 Карт Отражений. Для поддержки операции "прогулки" VISA имеет специальный режим. 8 Карт отражений разделены на две группы по 4 карты в каждой и между группами происходят пинг-понговые переключения. В то время как рендерер работает с одной группой, другая группа загружается для последующей закраски.

На последнем шаге обработки полученное значение r комбинируется с цветовым тоном Н и насыщенностью S, значения которых известны для каждого полигона. В предположении, что величина отражения света r и световой поток L одинаковы, выход RGB получается путем применением таблиц преобразований HLS/RGB для трех компонентов.

Все описанные выше шаги легко конвейеризуемы. Параллельно с HLS/RGB преобразованием может быть выполнен процесс 2-фильтрации для определения невидимых пикселей. В результате, конвейер RGB системы VISA способен закрашивать один пиксель каждый тик таймера (25 нс).

Z-фильтр

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

Дополнительный плюс метода Z-фильтра - значительное уменьшение времени инициализации. В то время как для обычного Z-буфера все ячейки должны быть предварительно загружены максимальным значением z(2^24-1), в Z-фильтре требуется инициализация только небольшой части памяти для начала цикла генерация нового изображения. Более детальное описание Z-фильтра можно найти в [6].

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

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

Буфер изображения разработан, как мультипортовая RAM и обеспечивает графическому процессору доступ к данным, работу с шиной изображения и VME. Для получения необходимых характеристик доступа буфер изображения разделен на 8 блоков. Путем применения различных схем адресации для четных и нечетных линий удалось также увеличить скорость записи. В результате теперь скорость доступа к памяти составляет 40 Мегапикселей/с. Передача пикселей на видеологику происходит по восьми 32-разрядным шинам, где 8 пиксельных потоков мультиплицируются видеологикой с частотой 135 МГц.

Преимущества и ограничения метода карт отражений

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

Заранее вычисляемые значения для комбинаций (a1, a2) в карте отражений верны только для фиксированных направлений наблюдения и векторов света. Следовательно, если источник света изменяет позицию или делается рендеринг для "прогулки" по миру виртуальной реальности, эти данные должны перевычисляться от кадра к кадру. В этих случаях описанный выше метод рендеринга существенно быстрее обычных методов закраски, основывающихся на векторе нормали. Ускорение S для нашего метода составляет:

S = Np/Ne

где Np обозначает количество закрашиваемых пикселей на кадр, а Ne - количество элементов в карте отражений на кадр. Np зависит от сложности объекта. Наш практический опыт показал, что достигается ускорение от одного до двух порядков.

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

Параллельньй рендеринг

В случаях, когда даже очень высокой скорости одного рендерера VISA не хватает, можно использовать 2 или 4 рендерера, работающих в параллель. При этом скорость закраски рисунка возрастет соответственно в два или четыре раза по сравнению с однократной системой. Существуют два подхода к параллельному рендерингу [7]:

- композиция изображений, при которой каждый рендерер генерирует полноэкранное изображение части сложной сцены, а полное изображение получается наложением частичных изображений;

- разделение экрана, когда каждый рендерер генерирует полное изображение части экрана, а полное изображение получается "склейкой" различных частичных изображений вместе.

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

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

Система MANNA/VISA с 4 единицами рендеринга, присоединенная к одному буферу кадров, может обработать до 2.8 миллионов полигонов в секунду. Для входной пропускной способности буфера кадров равной 40 Мбайт/с средний размер треугольника составляет 14 пикселей. Поскольку сравнение по глубине к осуществляется локально каждым растеризатором, то можно уменьшить число видимых пикселей путем сортировки преобразованных треугольников по глубине и, тем самым, максимизировать использование данной полосы пропускания буфера кадра.

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

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

Заключение. Развитие работ

Мы привели описание системы 3D-рендеринга реального времени, аппаратно реализующей реалистичную закраску Фонга, а не бедную закраску Гуро. В результате применения прогрессивных решений цена оборудования для выполнения закраски Фонга остается такой же, как и для закраски Гуро, при сравнимой скорости рендеринга. Однако, поскольку закраска Фонга имеет более высокое качество с меньшим числом полигонов, получается существенный выигрыш в геометрической обработке. Следовательно общая цена системы рендеринга Фонга меньше, чем у сравнимого рендерера Гуро, а качество рендеринга значительно лучше.

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

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


Литература

[1] Duff Т. Smoothly shaded rendering of polyhedral objects on raster displays, Computer Graphics Vol. 13, 2. Feb. 1979, рр. 270-275.

[2] Deering W, e.a. The Triangle Processor ond Normal Vector Shader А VLSl System for High Perfonnance Graphics, Computer Graphics VoL. 22, 4. April 1988, рр. 21-30.

[3] Bishop С., Weimar D.M. Fast Phong Shading, Computer Graphics, Vol. 20, 4. April 1986, рр. 103-106.

[4] Jackel О., Ruesseler Н.. А Real-time Raster Scan Display for 3-D Graphics. Advance in Computer Graphics Hardware 1V, S pringer, 1991.

[5] Jackel О. Grafik-Computer, Springer-Verlag, 1992. [6] Cobernuss М., Ruesseler Н.. Verfanren und Schaltungsarundnung zur Untetduckung verdeckter Bikfpunkte, DE 41 43 576 A1, German Patent Of ice 1993.

[7] Molnar S., Zyles,7., etc.: PixalFlow - High-Speed Rendering Using Image Composition, SIGGRAPH'92.

Поделитесь материалом с коллегами и друзьями