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