Рендеринг строки сканирования - Scanline rendering

Пример алгоритма развертки

Рендеринг строки сканирования (также рендеринг линии развертки и растровый рендеринг) - алгоритм для определение видимой поверхности, в 3D компьютерная графика, который работает построчно, а не многоугольник -полигонально или пиксель попиксельная основа. Все полигоны для визуализации сначала сортируются по верхней координате y, в которой они появляются впервые, затем по каждой строке или линия развертки изображения вычисляется с использованием пересечения строки развертки с многоугольниками в начале отсортированного списка, в то время как отсортированный список обновляется, чтобы отбросить невидимые многоугольники по мере продвижения активной строки развертки вниз по изображению.

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

Этот вид алгоритма может быть легко интегрирован со многими другими графическими методами, такими как Модель отражения Фонга или Z-буфер алгоритм.

Алгоритм

Обычный метод начинается с того, что края спроецированных многоугольников вставляются в сегменты, по одному на строку сканирования; растеризатор поддерживает активную таблицу краев (AET). Записи содержат ссылки сортировки, координаты X, градиенты и ссылки на полигоны, которые они связывают. Чтобы растрировать следующую строку сканирования, края, которые больше не актуальны, удаляются; добавляются новые ребра из Y-сегмента текущей развертки, вставляются отсортированные по координате X. Активные записи краевой таблицы имеют увеличенный X и другую информацию о параметрах. Активные записи краевой таблицы поддерживаются в X-сортированном списке по пузырьковая сортировка, выполняя изменение при пересечении 2 ребер. После обновления ребер таблица активных ребер перемещается в X-порядке, чтобы выделять только видимые пролеты, поддерживая Z-сортированную активную таблицу пролета, вставляя и удаляя поверхности при пересечении ребер.[нужна цитата ]

Варианты

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

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

История

Вероятно, первая публикация техники рендеринга растровой линии была сделана Уайли, Ромни, Эвансом и Эрдалом в 1967 году.[1]

Другие ранние разработки метода рендеринга растровой линии были сделаны Букнайтом в 1969 г.[2] и Ньюэлл, Ньюэлл и Санча в 1972 году.[3] Большая часть ранних работ по этим методам была выполнена в Иван Сазерленд графическая группа в Университет Юты, а на Эванс и Сазерленд компания в Солт-Лейк-Сити.

Использование в рендеринге в реальном времени

Ранняя линия генераторов изображений (IG) Evans & Sutherland ESIG использовала аппаратную технику «на лету», чтобы генерировать изображения по одной растровой строке за раз без кадровый буфер, избавляя от необходимости использовать дорогостоящую память. Более поздние варианты использовали гибридный подход.

В Nintendo DS это новейшее оборудование для рендеринга 3D-сцен таким образом с возможностью кэширования растеризованных изображений во VRAM.

В спрайтовое оборудование Распространенные в игровых машинах 1980-х годов можно рассматривать простую двухмерную форму рендеринга строк развертки.

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

Sony экспериментировала с программными модулями рендеринга строк на секунду Ячейка процессор во время разработки PlayStation 3, прежде чем остановиться на обычном расположении CPU / GPU.

Подобные техники

Аналогичный принцип используется в плиточный рендеринг (самый известный PowerVR 3D чип); то есть примитивы сортируются в экранное пространство, затем визуализируются в быстрой встроенной памяти, по одной плитке за раз. В Dreamcast предоставил режим для растеризации одной строки тайлов за раз для прямого растрового сканирования, избавляя от необходимости в полном буфере кадра, в некотором смысле в духе аппаратного рендеринга строк развертки.

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

Сравнение с алгоритмом Z-буфера

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

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

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

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

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

Смотрите также

использованная литература

  1. ^ Wylie, C, Romney, G.W, Evans, D.C, и Erdahl, A, "Полутоновые перспективные рисунки с помощью компьютера", Proc. AFIPS FJCC 1967, Vol. 31, 49
  2. ^ Букнайт В.Дж. "Улучшенная процедура генерации полутонового изображения компьютерной графики, "UI, Скоординированная научная лаборатория, сентябрь 1969 г.
  3. ^ Ньюэлл М.Е., Ньюэлл Р.Г. и Санча Т.Л. "Новый подход к проблеме затененного изображения", Proc ACM National Conf. 1972 г.

внешние ссылки