Введение
3D компьютерная графика: метод рендеринга изображений
Scanline rendering (также scan line rendering и scan line rendering) — это алгоритм определения видимой поверхности в 3D компьютерной графике, который работает построчно, а не по многоугольникам или пикселям. Все полигоны, подлежащие рендерингу, сначала сортируются по верхней y-координате их появления, затем каждая строка (линия сканирования) изображения вычисляется на основе пересечения линии сканирования с полигонами в начале отсортированного списка. При этом отсортированный список обновляется для удаления полигонов, которые больше не видны, по мере продвижения активной линии сканирования вниз по изображению. Основное преимущество этого метода заключается в том, что сортировка вершин вдоль нормали плоскости сканирования уменьшает количество сравнений между ребрами. Другое преимущество состоит в том, что нет необходимости переносить координаты всех вершин из основной памяти в рабочую — в активной памяти должны находиться только вершины, определяющие ребра, пересекающие текущую линию сканирования, и каждая вершина считывается только один раз. Основная память часто значительно медленнее, чем связь между центральным процессором и кэш-памятью, поэтому избежание повторного доступа к вершинам в основной памяти может обеспечить существенное ускорение. Этот алгоритм легко интегрируется с другими графическими методами, такими как модель отражения Фонга или Z-буферный алгоритм.
Алгоритм
Обычный метод начинается с краев проецируемых многоугольников, помещаемых в ячейки, по одному на линию сканирования; растеризатор поддерживает активную таблицу краев (AET). Элементы таблицы содержат ссылки для сортировки, X-координаты, градиенты и ссылки на полигоны, которые они ограничивают. Для растрирования следующей линии сканирования удаляются неактуальные края; добавляются новые края из Y-ячейки текущих линий сканирования, вставляемые в отсортированном порядке по X-координате. X-координаты и другая параметрическая информация в элементах активной таблицы краев обновляются. Элементы активной таблицы краев поддерживаются в списке, отсортированном по X, и изменяются при пересечении двух краев. После обновления краев активная таблица краев просматривается в порядке возрастания X для формирования только видимых отрезков, поддерживая Z-сортированную активную таблицу отрезков, вставляя и удаляя поверхности при пересечении краев.
Варианты
Гибридный подход, сочетающий данный метод и Z-буферизацию, избавляет от необходимости сортировки в активной таблице краев и вместо этого растрирует по одной линии сканирования в Z-буфер, сохраняя активные участки многоугольников от одной линии сканирования к следующей. В другом варианте буфер идентификаторов растрируется на промежуточном этапе, что позволяет выполнять отложенное затенение результирующих видимых пикселей.
История
Первая публикация техники сканирования с помощью линий, вероятно, принадлежит Уайли, Ромни, Эвансу и Эрдалу в 1967 году. Другие ранние разработки метода сканирования были выполнены Боукнайтом в 1969 году и Ньюэллом, Ньюэллом и Санчей в 1972 году. Значительная часть ранних работ по этим методам проводилась в графической группе Ивана Сазерленда в Университете Юты и в компании Evans & Sutherland в Солт-Лейк-Сити.
Использование в реендеринге в реальном времени
Ранняя линейка генераторов изображений Evans & Sutherland ESIG (IG) использовала эту технику аппаратно, "на лету", для генерации изображений по одной растровой строке за раз, без использования кадрового буфера, что позволяло избежать необходимости в тогдашней дорогостоящей памяти. Более поздние варианты использовали гибридный подход. Nintendo DS – последнее на сегодняшний день аппаратное обеспечение, которое выполняет рендеринг 3D-сцен таким образом, с возможностью кэширования растровых изображений в VRAM. Аппаратное обеспечение для спрайтов, широко распространенное в игровых системах 1980-х годов, можно рассматривать как простую 2D-форму рендеринга по сканирующим строкам. Эта техника была использована в первом движке Quake для программного рендеринга окружения (но движущиеся объекты отрисовывались поверх с использованием Z-буфера). Для статических объектов сцены использовалась сортировка на основе BSP для определения приоритета. Она оказалась эффективнее алгоритмов, основанных на Z-буфере или алгоритме художника, при обработке сцен с высокой сложностью геометрии и дорогостоящими операциями с пикселями (например, перспективно-корректное текстурирование без аппаратной поддержки). Это применение предшествовало широкому распространению GPU с Z-буфером, которые сейчас обычно используются в ПК. Компания Sony экспериментировала с программными рендерерами по сканирующим строкам на втором процессоре Cell во время разработки PlayStation 3, прежде чем перейти к традиционной схеме CPU/GPU.
Аналогичные методы
Аналогичный принцип используется в тайловой отрисовке (наиболее известный пример – чип PowerVR 3D); то есть, примитивы сортируются в экранном пространстве, а затем быстро отрисовываются в памяти чипа, по одной тайлу за раз. Dreamcast предоставлял режим растрирования по одной строке тайлов для непосредственного вывода растра, что избавляло от необходимости в полноценном буфере кадров и в некоторой степени напоминало аппаратную отрисовку по сканам. Некоторые программные растрировщики используют "буферизацию отрезков" (или "буферизацию покрытия"), в которой список отсортированных и отсеченных отрезков хранится в букетах по линиям сканирования. Примитивы последовательно добавляются в эту структуру данных, после чего происходит растрирование только видимых пикселей на финальном этапе.
Сравнение с алгоритмом Z-буфера
Основным преимуществом сканлайнового рендеринга перед Z-буферизацией является то, что количество обработок видимых пикселей поддерживается на абсолютном минимуме – ровно один раз, если не используются эффекты прозрачности, что особенно выгодно при высоком разрешении или сложных вычислениях затенения. В современных Z-буферных системах аналогичные преимущества достигаются за счет приблизительной сортировки спереди назад (приближающейся к алгоритму «обратного художника»), раннего отсечения по глубине (в сочетании с иерархическим Z-буфером) и менее распространенных методов отложенного рендеринга, доступных на программируемых графических процессорах. Методы сканирования, работающие с растром, имеют недостаток в том, что перегрузки обрабатываются неэффективно. Считается, что эта техника плохо масштабируется при увеличении количества примитивов, поскольку размер промежуточных структур данных, необходимых для рендеринга, может превысить размер Z-буфера для сложной сцены. В результате, в современных интерактивных графических приложениях Z-буфер стал повсеместно используемым. Z-буфер позволяет обрабатывать большие объемы примитивов линейно и параллельно, что оптимально для современного оборудования. Преобразованные координаты, градиенты атрибутов и т.п. не покидают графический чип; сохраняются только видимые пиксели и значения глубины.