Рендеринг строк сканирования (также рендеринг строк сканирования и рендеринг строк сканирования ) — это алгоритм определения видимой поверхности в 3D компьютерной графике , который работает построчно, а не по полигону за полигоном или попиксельно . основе. Все полигоны, подлежащие визуализации, сначала сортируются по верхней координате y, в которой они впервые появляются, затем каждая строка или строка сканирования изображения вычисляется с использованием пересечения линии сканирования с полигонами в начале отсортированного списка, в то время как отсортированный список обновляется и отбрасывает невидимые полигоны по мере продвижения активной линии сканирования вниз по изображению.
Основное преимущество этого метода состоит в том, что сортировка вершин по нормали плоскости сканирования уменьшает количество сравнений между ребрами. Еще одним преимуществом является то, что нет необходимости переводить координаты всех вершин из основной памяти в рабочую память — в активной памяти должны находиться только вершины, определяющие ребра, пересекающие текущую строку сканирования, и каждая вершина считывается только один раз. Основная память часто работает очень медленно по сравнению с соединением между центральным процессором и кэш-памятью , и, таким образом, предотвращение повторного доступа к вершинам в основной памяти может обеспечить существенное ускорение.
Этот тип алгоритма можно легко интегрировать со многими другими графическими методами, такими как модель отражения Фонга или алгоритм Z-буфера .
Обычный метод начинается с того, что края проецируемых многоугольников вставляются в сегменты, по одному на строку сканирования; растеризатор поддерживает активную таблицу ребер ( AET ). Записи сохраняют ссылки сортировки, координаты X, градиенты и ссылки на полигоны, которые они связывают. Чтобы растрировать следующую строку сканирования, ненужные края удаляются; добавляются новые ребра из Y-сегмента текущих строк сканирования, вставленные с сортировкой по координате X. В записях таблицы активных ребер X и другая информация о параметрах увеличена. Записи таблицы активных ребер сохраняются в списке, отсортированном по X, что приводит к изменению при пересечении двух ребер. После обновления ребер активная таблица ребер перемещается по оси X, чтобы выделить только видимые промежутки, сохраняя активную таблицу промежутков с Z-сортировкой, вставляя и удаляя поверхности при пересечении ребер. [ нужна цитата ]
Гибрид между этим и Z-буферизацией устраняет активную сортировку таблицы ребер и вместо этого растрирует одну строку сканирования за раз в Z-буфер, сохраняя активные диапазоны полигонов от одной строки сканирования до другой.
В другом варианте буфер ID растеризуется на промежуточном этапе, что позволяет отложить затенение полученных видимых пикселей.
Первую публикацию техники рендеринга развертки, вероятно, сделали Уайли, Ромни, Эванс и Эрдал в 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 , прежде чем остановилась на традиционной схеме CPU/GPU.
Похожий принцип используется при мозаичном рендеринге (наиболее известный из них – чип PowerVR 3D); то есть примитивы сортируются по экранному пространству, а затем визуализируются в быстрой встроенной памяти по одному тайлу за раз. Dreamcast предоставил режим растеризации одного ряда фрагментов за раз для прямого растрового сканирования, что избавляло от необходимости использовать полный буфер кадров, что в некоторой степени в духе аппаратного рендеринга строк сканирования .
Некоторые программные растеризаторы используют «буферизацию интервалов» (или «буферизацию покрытия»), при которой список отсортированных обрезанных диапазонов сохраняется в сегментах строк развертки. Примитивы будут последовательно добавляться к этой структуре данных, а на заключительном этапе растрируются только видимые пиксели.
Основное преимущество рендеринга строк развертки перед Z-буферизацией заключается в том, что количество раз обработки видимых пикселей сводится к абсолютному минимуму, что всегда составляет один раз, если не используются эффекты прозрачности - преимущество в случае высокого разрешения или дорогостоящих вычислений затенения. .
В современных системах Z-буфера аналогичные преимущества можно получить за счет грубой прямой сортировки (приближаясь к «алгоритму обратного рисования»), раннего Z-отклонения (в сочетании с иерархическим Z) и менее распространенных методов отложенного рендеринга, возможных на программируемые графические процессоры.
Методы сканирования строк, работающие с растром, имеют тот недостаток, что перегрузка не обрабатывается корректно.
Считается, что этот метод плохо масштабируется по мере увеличения количества примитивов. Это связано с размером промежуточных структур данных, необходимых во время рендеринга, который может превышать размер Z-буфера для сложной сцены.
Следовательно, в современных интерактивных графических приложениях Z-буфер стал повсеместным. Z-буфер позволяет линейно и параллельно перемещать большие объемы примитивов, что удобно для современного оборудования. Преобразованные координаты, градиенты атрибутов и т. д. никогда не должны покидать графический чип; сохраняются только видимые пиксели и значения глубины.