что такое растеризация изображения
Растеризация
Растеризация (англ. Rasterisation, Rasterization ), растрирование — процессы, конечным результатом которых являются растровые изображения:
Содержание
В информатике
В полиграфии
Термин зародился в середине XIX века с появлением офсетного способа печати и появлением технологии растра, необходимой для качественной печати.
В фотографии и обработке растровых изображений
Растеризация в фотографии и обработке изображений означает получение эффекта, сходного с растеризацией изображения при офсетной печати.
Восстановление изображений
Растеризация — наложение сетки, каждая из ячеек которой обрабатывается особым образом. В простейшем случае одна ячейка — один пиксель. Однако применяется и неоднотонная заливка ячейки, а по сложным алгоритмам — заливка оттенками цвета от одного края до другого, так называемая градиентная. В зависимости от выбора алгоритма заливки ячейки, становится возможным улучшение качества старых или поврежденных изображений.
См. также
Примечания
Полезное
Смотреть что такое «Растеризация» в других словарях:
растеризация — Преобразование векторной модели пространственных данных в растровую модель. [ГОСТ Р 52438 2005] растеризация Преобразование векторной графики в растровое изображение. [http://www.morepc.ru/dict/] Тематики географические информационные… … Справочник технического переводчика
растеризация — сущ., кол во синонимов: 1 • преобразование (41) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов
Растеризация — цифровое электронное растрирование с определенным количеством градаций черного (серого) … Реклама и полиграфия
растеризация — Растрирование, Растеризация (Rasterization) Преобразование полутоновых и штриховых изображений в микроштриховые с помощью растра в репродукционных фотоаппаратах и контактно копировальных станках. В компьютерных издательских системах… … Шрифтовая терминология
растеризация — 50 растеризация: Преобразование векторной модели пространственных данных в растровую модель. Источник: ГОСТ Р 52438 2005: Географические информационные системы. Термины и определения оригинал документа … Словарь-справочник терминов нормативно-технической документации
Разложение в растр — Растеризация это перевод двухмерного изображения, описанного векторным форматом в пиксели или точки, для вывода на дисплей или принтер. Процесс, обратный векторизации. Выше указано ныне традиционная трактовка термина. Однако… Термин зародился в… … Википедия
Разрешение (компьютерная графика) — У этого термина существуют и другие значения, см. Разрешение. Разрешение величина, определяющая количество точек (элементов растрового изображения) на единицу площади (или единицу длины). Термин обычно применяется к изображениям в цифровой… … Википедия
RasterDesk — Тип Гибридный графический редактор Разработчик «CSoft Develop … Википедия
Spotlight (графический редактор) — У этого термина существуют и другие значения, см. Spotlight. Spotlight Тип Гибридный гра … Википедия
Что значит растрировать слой
Векторные изображения состоят совокупности простых геометрических элементов (примитивов, например, кругов, прямоугольников, отрезков дуг и т.п.), где для каждого элемента определены управляющие параметры. Например, для прямоугольника управляющим параметром является длина, ширина, расстояние по двум осям от верхней левой вершины до верхнего левого угла изображения, цвет и толщина линии границы, цвет внутренней области.
Отсюда следует, что:
Эти формы остаются векторными даже при сохранении документа в фотошоповском формате PSD.
Инструменты рисования и почти все фильтры программы не могут применяться к слоям, содержащим векторные объекты. К таким слоям относятся текстовые слои, слой-фигуры, векторные маски, а средства рисования, например, инструмент «Кисть», не могут быть применены даже к смарт-объектам. Также инструменты рисования и фильтры не могут быть применены к производным слоям (например, к слоям-заливкам).
Следовательно, растрирование слоя в Photoshop необходимо для применения этих инструментов к слоям.
Растрирвание слоя необратимо!
После растрирпования мы сможем применять к слою любой из фильтров Photoshop, но текст уже не будет текстовым элементом, а простым пиксельным изображением, для которого недоступны элементы управления текстового редактора.
Но и здесь Photoshop предоставляет нам отличный способ обойти это правило. Вместо того, чтобы превратить текст в пиксельное изображение, следует конвертировать его в смарт-объект.
После конвертации текста в смарт-объект мы можем применять к тексту фильтры Photoshop в качестве смарт-фильтров, а сам текст редактировать текстовым редактором внутри смарт-объекта
Растрирование слоя в Фотошопе
Растрирование – одна из наиболее часто выполняемых процедур в графических редакторах. Давайте посмотрим, каким образом можно справиться с этой задачей в Фотошопе.
Определение растрового изображения
Для начала напомним, что цифровые изображения бывают двух видов:
Несмотря на очевидное преимущество векторных изображений, у них есть и явный минус: к ним нельзя применять фильтры и многие другие инструменты. И если возникает такая необходимость, слой с такой графической информацией сначала требуется растрировать – это значит преобразовать его в растровое изображение. Кстати, данная операция в Фотошопе применима и к текстовым слоям.
Растрирование слоя
Процедура растрирования выполняется довольно просто и быстро. В качестве примера будем использоваться слой с фигурой в виде ромба.
Итак, вот что мы делаем:
Примечание: кстати, если попробовать применить какой-нибудь фильтр к нерастрированному слою, появится сообщение с предложением выполнить соответствующую операцию или преобразовать его в смарт-объект.
Если растрировать слой таким образом, то в Палитре результат будет иным – добавится векторная маска, а также видоизменится исходный слой.
Ввиду этого, такой способ достаточно специфичный и применяется реже, чем описанный выше.
Растрирование текста
Для текстового слоя выполняются аналогичные действия – кликаем по нему правой кнопкой мыши (но только не по миниатюре) и выбираем в появившемся меню нужный пункт – “Растрировать текст”.
Сменившаяся миниатюра слоя говорит о том, что мы все сделали правильно. Текст будет перенесен в виде изображения на прозрачный фон.
Также вместо этого можно, выбрав нужный слой в Палитре, затем нажать комбинацию Ctrl+A, что позволит выделить текст. Далее в меню “Редактированию” сначала выбираем команду “Копировать”, затем – “Вставить”. Или же для копирования или вставки можно воспользоваться горячими клавишами Ctrl+C и Ctrl+V, соответственно.
В отличие от первого варианта, растрированный текст будет добавлен в виде отдельного слоя с сохранением исходного.
Заключение
Таким образом, в том, чтобы растрировать слой с картинкой/фигурой или текстом в Фотошопе, нет ничего сложного. Операция выполняется буквально в несколько кликов и займет считанные секунды. При этом практическая польза этого действия, безусловно, велика, т.к. после его выполнения возможности в обработке полученного изображения практически безграничны.
Растрирование
Каталог статей
Содержание
Процессы, описанные в этой статье, являются базовыми для понимания основ офсетной полиграфии. Тот, кто сможет понять основы растрирования, сможет разобраться с любой, самой трудной полиграфической задачей.
Часто приходится встречать такой вопрос: «Три слова в полиграфии«. Мой ответ такой: растрирование; CMYK; ротация. Вот об одном таком слове и пойдёт речь в данной статье.
Казалось бы, про растрирование написано много, зачем ещё одна статья? Действительно мне пришлось перелопатить немало материала, прежде чем достигнуть существующего уровня понимания вопроса. Буду откровенен, последнюю точку в вопросе растрирования мне помогла поставить работа над полиграфическим словарём. Я разбирался с терминологией вокруг растрирования и обратился к первоисточнику, а именно, к англоязычной википедии. И с помощью неё, разобравшись с терминологией, мне стало понятно насколько в нашей литературе всё запутано.
Действительно растрирование стало грандиозной вехой в полиграфии и дало лёгкий способ переноса на печать тоновых изображений. Как же до появления растра печатались изображения? Методом штрихового рисунка. На рис. 1 изображена старая литография, сделанная мастером по технологии штрихового рисунка. В принципе технология штрихового рисунка позволяла получать достаточно сложные тоновые изображения, однако, была трудозатратна и требовала большого мастерства. Даже с помощью современных программных средств нет технологий получения штрихового рисунка из тонового изображения. А с появлением фотографии количество тоновых изображений начало стремительно возрастать. Вот тут и возникла реальная потребность в появлении растра.
Палитра CMYK
Статья в полной мере описывает особенности палитры CMYK, её отличия от иных палитр. Особое внимание уделено практической стороне работы палитры CMYK в полиграфическом производстве. Рассказывается о таких явлениях как точка белого, плотность красок, максимальная сумма красок и мн. др…
В этой статье будет рассмотрен один из видов полиграфических растров – регулярный растр. Для упрощения понимания вопроса рассмотрим процесс растрирования черно-белого тонового изображения. Под растрированием (halftoning или screenning) будем понимать процесс преобразования тонового изображения в изображение, содержащее полиграфический растр (halftone screen), назовём его растрированным изображением, тем более другого термина нет.
Постановка задачи
Какую задачу предстояло решить изобретателю растра? Исходный материал – тоновое ч/б изображение. Конечная цель – bitmap изображение.
На этом этапе следует ввести понятие bitmap. В современном понимании bitmap это цветовая палитра на информацию о цвете в которой выделен всего один bit информации. Поэтому цвет в bitmap изображении может быть только чёрным или белым, а если более точно, может быть, а может не быть (to be, or not to be). И именно bitmap технология лежит в основе современных печатных форм. Иными словами, на печатную форму нанесено bitmap изображение. Поэтому задачу можно сформулировать следующим образом: как тоновое ч/б изображение, содержащее 256 оттенков серого*¹, отобразить в палитре bitmap. Такая формулировка задачи приобретает достаточно простой математический смысл. Если имеются точки тонового изображения со значениями в диапазоне от 0 до 255, то для отображения их в цветовой модели bitmap потребуется матрица разрядностью 16×16 пикселей. Под пикселем будем понимать наименьшую (элементарную) точку, которую можно воспроизвести на печатном оттиске. А физический размер этой точки будет тесно связан с понятием разрешения фотовыводного устройства. Но об этом позже. Таким образом, цветовая точка тонового изображения будет «зажигать» в матрице соответствующее количество пикселей (см. рис. 2). Например, всем известная шахматная доска представляет собой матрицу разрядностью 8×8, передающую тоновую точку с 50% (32 из диапазона 0–63) интенсивностью цвета*².
Цветовая матрица в полиграфии называется (halftone cell) или растровая ячейка, а заполнение её пикселями происходит не хаотично, а по строгим правилам. Вообще правила всего два: в случае нормального распределения пикселей по растровой ячейке получаем стохастический растр или стохастику; в случае концентрации пикселей в одном месте получаем регулярный растр. Площадь (поле) концентрации пикселей в растровой ячейке называется (halftone dot) – растровое пятно (см. рис. 3). Почему растровое пятно, а не растровая точка? Потому что термин растровая точка занят. О ней (растровой точке) будет сказано ниже. Для предотвращения муара в полиграфии растровую ячейку поворачивают на некоторый угол – угол поворота растра. Такая растровая ячейка или их совокупность (для палитры CMYK) называется (halftone screen) – растровой точкой. В полноцветной полиграфии растровая точка образует характерный рисунок, поэтому её иногда называют растровой розеткой. Форма растрового пятна может быть различной, например, квадрат, круг или эллипс. Оптимальной считается эллиптическая форма растрового пятна (в литературе растровая точка).
Понятие линиатуры
Сколько необходимо иметь растровых точек на единицу поверхности для получения качественного печатного оттиска?
Экспериментальным путём установлено, что на высококачественных бумагах не возможно устойчиво отпечатать более 175–200 растровых точек на 1 дюйм длины. Это и есть понятие линиатуры. Иными словами, линиатура это частота (количество) растровых точек на дюйм поверхности. Во всех направлениях линиатура одинакова. Измеряется линиатура в lpi (line per inch), что переводят как количество линий на дюйм. Но под линиями следует понимать именно растровые точки. Не сложно вычислить физический размер растровой точки при линиатуре 200 lpi. Имеем 200 точек/дюйм, применим операцию (1/х) и получим размер одной растровой точки 1/200 = 0,005 (дюйма). Учитывая, что в одном дюйме 25,2 мм получаем размер растровой точки 0,126 (мм).
Печатные формы / пластины
Читайте статью об изготовлении печатных форм из печатных пластин. Прочитав статью, вы узнаете: чем отличаются печатные пластины от печатных форм; что такое комплект форм и каков его размер; а также подробно познакомитесь с технологий изготовления печатных форм по технологии CtP…
Связь линиатуры и разрешения
Теперь мы вплотную подошли к понятию разрешения. Разрешение связывает, до сих пор абстрактное, понятие пикселя с занимаемой им площадью на реальном физическом носителе. В нашем случае носителем является печатная форма. В предыдущем параграфе мы выяснили размер растровой точки, необходимый для высококачественной печати. Также нам известно, что растровая точка состоит из растровой ячейки разрядностью 16×16 пикселей. Делим имеющиеся показатели на 16 и получаем физический размер одного пикселя ≅ 0,0003 (дюйма) или ≅ 0,0079 (мм). Сколько же таких пикселей размещается на одном дюйме печатной формы, снова применим операцию (1/х) и получим необходимое разрешение фотовыводящего устройства – 3200 ppi (pixel per inch). Что и требовалось доказать.
Зависимость линиатуры от печатной машины и типа бумаги приведена в таблице.
Таблица 1. Ограничения по total ink (TIL) и типичная линиатура печати для различных классов полиграфических бумаг| Вид печати | Бумага | total ink Fogra % | WB Fogra | Линиатура, lpi |
|---|---|---|---|---|
| Листовая | мелованная глянцевая плотностью свыше 130 г/м² | 330 | 39 | 175 |
| немелованная | 300 | 39, 47 | 133 | |
| мелованная матовая | 150 | |||
| мелованная глянцевая до 130 г/м² (включительно) | 175 | |||
| Рулонная | мелованная матовая, мелованная глянцевая | 41, 45 | 150 | |
| SC суперкаландр | 270 | 40 | 133 | |
| газетная | 260 Heatset*¹ | 42 | 120 | |
| 200–240 max Coldset |
REG.ru
Важные интуиции, вытекающие из выше изложенного
Если тоновое изображение является штриховым рисунком или bitmap изображением, то при растрировании оно не меняется. Фактически при растрировании bitmap изображения его разрешение будет преобразовано к разрешению фотовывода. Следовательно, для получения максимального качества bitmap изображения необходимо делать его с разрешением близким к разрешению фотовывода. На практике достаточно разрешения bitmap изображения в 1200 ppi, т.к. дальнейшее увеличение разрешения не заметно глазу. На рис. 4 приведены фрагменты bitmap изображений сделанные при различных разрешениях.
Аналогичного качества можно достигнуть и при использовании векторных изображений (но только при условии их окрашивания в плашечный цвет), т.к. векторы масштабируются без потери качества.
Что произойдёт, если мы окрасим векторное изображение не в плашечный цвет, а, например, в 60% Black? В этом случае от разрешения фотовывода в 3200 ppi мы перейдём к линиатуре 200 lpi. Иными словами, разрешение выводящегося изображения уменьшится в 16 раз (рис. 5). При этом возникает эффект «пилы». Поэтому не рекомендую задавать шрифтам не плашечные цвета при линиатуре печати ниже 175 lpi. При линиатуре 150 lpi и ниже сильно заметной становится «пила».
Полиграфический дуализм
Какое разрешение необходимо задавать изображению перед отправкой его на фотовывод? Из логики следует, что разрешение изображения должно соответствовать линиатуре печати. Почему тогда рекомендуют делать разрешение чуть выше, чем линиатура печати, примерно в 1,5–2 раза? В этом есть смысл, если чёрный выступает в качестве контура. Иными словами, если чёрный специально обработан. В результате обработки он должен приобрести свойства bitmap изображения. Как этого можно достичь? Путём шарпенса чёрного. В результате шарпенса контуры изображения уконтращиваются и появляются малые участки где чёрный достигает 100%-интенсивности. Это и придаёт ему свойства bitmap изображения. Этот эффект я назвал полиграфическим дуализмом. На рис. 6 приведены примеры исходного изображения и после правильного шарпенса.
Software renderer — 2: растеризация и интерполяция атрибутов
Привет. В прошлой статье я описал математику, которая необходима для вывода трехмерной сцены на экран в виде сетки — т.е. мы остановились на моменте получения координат вершин в пространстве экрана. Следующий шаг — это «заполнение» полигонов из которых состоит объект, т.е. поиск пикселей, которые входят в изображение объекта на экране. Процесс поиска этих точек называется растеризацией. Мы так же хотим иметь возможность текстурировать и освещать объекты — для этого необходимо уметь интерполировать атрибуты, заданные в вершинах (например, текстурные координаты, нормали, цвет и другие).
Основы
Итак, растеризация — это процесс поиска пикселей, «входящих» в заданный полигон. Для начала, мы будем считать, что нам достаточно закрасить полигон сплошным цветом — ничего лишнего.
Представим, что у нас есть следующий треугольник для вывода на экран (все координаты уже представлены в пространстве экрана):
Какие пиксели необходимо закрасить? Пиксель может быть целиком вне полигона, частично в полигоне и целиком в полигоне:
Оранжевым цветом отмечены пиксели, которые частично входят в оба полигона. Теперь представим, что мы растеризуем оба этих полигона. Если мы решаем, что все пиксели, частично входящие в полигон, должны быть заполнены, мы получим заполнение одних и тех же пикселей дважды (или больше, в случае если есть общая вершина для более чем двух полигонов). Это может не показаться проблемой на первый взгляд, но, на самом деле, это приведет к различным артефактам при использовании некоторых техник, таких как альфа-смешивание (отрисовка с использованием альфа-канала для имитации прозрачности). Так же это ведет к снижению производительности, т.к. количество пикселей, для которых нам необходимо вычислять значения атрибутов, увеличивается. Если же мы, наоборот, решим, что такие пиксели не входят в итоговое изображение и не должны быть заполнены, мы получим «дыры» между полигонами, что неприемлимо.
Таким образом мы пришли к пониманию того, что каждый пиксель при отрисовке смежных полигонов должен быть заполнен ровно один раз. Это требование, которое соблюдают и Direct3D и OpenGL.
Проблема возникает из-за необходимости отображения из непрерывного (система координат экрана) в дискретное (пиксели на мониторе). Традиционный алгоритм растеризации (при отрисовке без сглаживания) решает это следующим образом: каждому пикселю сопоставляется некая точка (sample point), которая и отвечает за вхождение пикселя в полигон. Так же, именно в этой точке считаются значения всех необходимых атрибутов. Другими словами, все пространство, занимаемое пикселем в системе координат экрана, «представляется» одной точкой. Как правило, это центр: (0.5, 0.5):
Теоретически, можно брать любую точку внутри пикселя, вместо центра. Другие значения приведут к тому, что изображение может быть «сдвинуто» на пиксель в одну из сторон. Так же, в ситуации со смежным полигонами, для пикселей, в которых не расположены вершины треугольников, использование точки (0.5, 0.5) обладает хорошим свойством: эта точка входит в тот полигон, который охватывает более 50% площади прямоугольника, представляющего пиксель.
Таким образом, если центр пикселя входит в полигон, то считается, что пиксель принадлежит полигону. Но теперь возникает следующая проблема: что, если два полигона имеют общую грань, которая проходит через центр пикселя? Мы уже поняли, что пиксель должен принадлежать только одному из двух треугольников, но какому именно? На картинке ниже такой пиксель помечен красным цветом:
Эту проблему решает так называемое «соглашение о заполнении пикселей» (filling convention).
Соглашение о заполнении
Итак, предположим мы столкнулись с ситуацией, описаной выше — два полигона делят между собой грань, которая проходят ровно через центр пикселя. Наша задача состоит в том, чтобы выяснить, какому из полигонов принадлежит этот пиксель.
Де-факто стандартом является так называемое top-left rule: ему следует DirectX и большинство реализаций OpenGL. Суть этого правила такова: если грань полигона проходит через центр пикселя, то этот пиксель принадлежит полигону в двух случаях — если это левая грань или верхняя грань (отсюда и название).
Теперь рассмотрим случай смежных полигонов. Если грань — смежная, и является левой в одном полигоне, то эта же грань является правой для всех полигонов, которые делят эту грань с этим полигоном. Аналогичное правило работает для верхних и нижних граней:
Мы можем использовать это свойство для того, чтобы определять, какому из смежных полигонов принадлежит пиксель. Если мы договоримся, что пиксель, чей центр лежит на общей грани, принадлежит только полигонам, у которых эта грань — левая, то он автоматически не будет принадлежать смежным полигонам, поскольку для них эта грань — правая. И то же самое для верхней грани.
Несмотря на то, что правило верхней и левой грани встречается чаще всего, мы можем использовать любое подходящее сочетание. Например, правило нижней и левой грани, верхней и правой и т.д. Direct3D обязывает использовать top-left rule, OpenGL же не так строг и позволяет использовать любое правило, решающее проблему принадлежности пикселя. Я в дальнейшем буду предполагать использование top-left rule.
Точность
Рассмотрим следующие два полигона:
Второй полигон может быть получен из первого в результате вращения на некоторый угол. В итоге, некоторые пиксели дополнительно включаются в итоговое изображение (такие пиксели помечены зеленым), а некоторые, наоборот, исчезают из него (помечены красным). Соответственно, нам необходимо учитывать дробные части координат вершин. Если мы будем их отбрасывать, то получим проблемы при рисовании нестатической сцены. Если, например, заставить полигон очень медленно вращаться, то он будет это делать дерганно — поскольку грани будут резко «прыгать» из одного положения в другое, вместо того, чтобы корректно обрабатывать промежуточные результаты. Разницу легко понять, сравнив два этих видео:
Конечно, в случае со статической сценой таких проблем не возникнет.
Интерполяция атрибутов
Прежде чем перейти непосредственно к алгоритмам растеризации, остановимся на интерполяции атрибутов.
Атрибут — это некая информация, связанная с объектом, которая необходима для его корректной отрисовки по заданному алгоритму. Таким атрибутом может быть все, что угодно. Одними из самых частых вариантов являются: цвет, текстурные координаты, координаты нормали. Значения атрибута задаются в вершинах сетки объекта. При растеризации полигонов, эти атрибуты интерполируются вдоль поверхности треугольников и используются для вычисления цвета каждого из пикселей.
Самым простым примером (и своеобразным аналогом «hello world») является отрисовка треугольника, в каждой вершине которого задан один атрибут — цвет:
В этом случае, если мы будем присваивать каждому пикселю полигона цвет, являющийся результатом линейной интерполяции цветов трех вершин, мы получим следующее изображение:
Способ, которым производится интерполяция, зависит от данных, которыми мы оперируем в процессе отрисовки, а они, в свою очередь, зависят от алгоритма, который используется при растеризации. Например, при использовании «стандартного» алгоритма мы можем использовать простую линейную интерполяцию значений между двумя пикселями, а при использовании traversal-алгоритмов — барицентрические координаты. Поэтому мы отложим это до описания самих алгоритмов.
Тем не менее, есть еще важная тема, на которой необходимо остановиться заранее: интерполяция атрибутов с коррекцией перспективы.
Самым простым способом интерполяции является линейная интерполяция в пространстве экрана: после того, как полигон был спроецирован на плоскость проекции, мы линейным образом интерполируем атрибуты вдоль поверхности треугольника. Важно понимать, что эта интерполяция не является корректной, поскольку она не учитывает произведенную проекцию.
Рассмотрим проецирование линии на плоскость проекции d = 1. На начальной и конечной вершинах установлены некие атрибуты, которые линейно изменяются в пространстве камеры (и в мировом). После того, как произведена проекция, эти атрибуты не растут линейно в пространстве экрана. Если, например, взять среднюю точку в пространстве камеры (v = v0 * 0.5 + v1 * 0.5), то после проекции эта точка не будет лежать в середине спроецированной линии:
Легче всего это заметить при текстурировании объектов (я буду использовать простое текстурирование без фильтрации в примерах ниже). Я еще не описывал процесс текстурирования подробно (и это тема отдельной статьи), поэтому пока что ограничусь кратким описанием.
При текстурировании в каждой вершине полигона задается значение атрибута текстурных координат (его часто называют uv по названию соответствующих осей). Это нормализованные координаты (от 0 до 1), которые определяют, какой участок текстуры будет использован.
Теперь представим, что мы хотим нарисовать текстурированный прямоугольник и задали четыре значения атрибута uv таким образом, чтобы текстура использовалась целиком:
Кажется, все неплохо:
Правда, эта модель расположена параллельна плоскости проекции, а значит и искажений за счет перспективы быть не должно. Попробуем сдвинуть верхние две вершины на единицу вдоль оси z, и проблема станет видна сразу:
Таким образом, необходимо учитывать перспективу при интерполяции атрибутов. Ключевым фактом к этому является то, что, хотя z не может быть корректно интерполировано в пространстве экрана, 1/z — может. Снова рассмотрим проецирование линии:
Мы так же уже знаем, что по подобным треугольникам:
Интерполируя x в пространстве экрана, получаем:
Интерполируя x в пространстве камеры, получаем:
Эти три равенства является ключевыми и на их основе выводятся все последующие формулы. Я не буду приводить полный вывод, поскольку это легко сделать и самостоятельно, и опишу его только вкратце, акцентируя внимание на результатах.
Подставив эти два равенства в уравнение, полученное из соотношений сторон треугольника, и упростив все выражения, мы в итоге получим, что величина, обратная z-координате, может быть линейно интерполирована в пространстве экрана:
Важно, что в данном выражении интерполяция происходит между величинами, обратными z-координатам в пространстве камеры.
Далее, предположим, что в вершинах A и B заданы значения некого атрибута, обозначим их T1 и T2, который так же может быть линейно интерполирован в пространстве камеры:
Используя промежуточные результаты из вывода выше, мы можем записать, что величина Tc / Zc может быть так же корректно интерполирована в пространстве экрана:
Подведя итоги, мы получили, что 1 / Zc и Tc / Zc могут быть линейно интерполированы в пространстве экрана. Теперь мы легко можем получить значение Tc:
Собственно, стоимость перспективно-корректной интерполяции и заключается, в основном, в этом делении. Если в ней нет большой необходимости, то лучше минимизировать количество атрибутов, для которых она используется и обойтись простым линейным интерполированием в пространстве экрана, если это возможно. Ниже изображен корректный результат текстурирования:
Для реализации коррекции перспективы нам нужны значения, обратные глубине (z-координате) вершин в пространстве камеры. Вспомним, что происходит при умножении на матрицу проекции:
Вершины из пространства камеры переходят в пространство отсечения. В частности, z-координата подвергается определенным изменениям (которые в дальнейшем понадобятся для буфера глубины) и уже не совпадает с z-координатой вершины в пространстве камеры, так что использовать ее мы не можем. А что совпадает — так это w-координата, поскольку мы явно кладем в нее z из пространства камеры (достаточно посмотреть на 4-й столбец матрицы). На самом деле, нам нужно даже не сама z, а 1 / z. И мы получаем ее фактически «бесплатно», поскольку при переходе в NDC мы делим все вершины на z (которая лежит в w-координате):
А, значит, можем просто заменить ее на обратное значение:
Алгоритмы растеризации
Ниже будет представлено описание трех подходов к растеризации полигонов. Полные примеры кода будут отсутствовать, поскольку очень многое в нем зависит от реализации, и это будет скорее путать, чем помогать. В конце статьи будет ссылка на проект, и, если необходимо, можно посмотреть код реализации в нем.
«Стандартный» алгоритм
Я назвал этот алгоритм «стандартным», поскольку это наиболее часто описываемый алгоритм растеризации для программных рендереров. Он проще для понимания, чем traversal-алгоритмы и растеризация в однородных координатах, и, соответственно, проще в реализации.
Итак, начнем с треугольника, который мы хотим растеризовать. Предположим, для начала, что это треугольник с горизонтальной нижней гранью.
Суть этого алгоритма заключается в последовательном движении вдоль боковых граней и закрашивании пикселей между ними. Для этого сначала вычисляются значения смещения вдоль оси X за каждое смещение на единицу вдоль оси Y.
Затем, начинается движение вдоль сторон. Важно, что движение начинается с ближайшего центра, а не с Y-координаты вершины v0, поскольку пиксели представлены именно этими точками. Если Y-координата v0 уже лежит на центре, то мы все равно переходим к следующему центру по этой оси, поскольку v0 лежит как на левой так и на правой грани, а значит этот пиксель не должен включаться в изображение:
Когда мы переходим к следующей строке, мы так же начинаем движение только со следующего центра вдоль оси X. Если же грань проходит через центр пикселя, то на левой грани мы включаем пиксель в изображение, а на правой нет.
Аналогичным образом алгоритм работает для треугольников с горизонтальной верхней стороной. Те треугольники, который не имеют ни одной горизонтальной стороны, просто делятся на два треугольника — один с горизонтальной верхней и один с горизонтальной нижней. Для этого ищется пересечение горизонтальной линии, проходящей через одну из вершин треугольника (средней по Y-координате), с другой гранью:
После этого каждый из этих треугольников растеризуется по алгоритму выше. Необходимо так же корректно вычислить значения z и w координат в новой вершине — например, интерполировать их. Аналогично, наличие этой вершины необходимо учитывать при интерполяции атрибутов.
Интерполяция атрибутов без коррекции перспективы происходит следующим образом — при движении вдоль боковых граней мы вычисляем интерполированные значения атрибутов в начальной и конечной точки линии, которую собираемся растеризовывать. Затем, эти значение линейно интерполируются вдоль этой линии. Если коррекция перспективы нужна для атрибута, то вместо этого мы интерполируем T/z вдоль граней полигона (вместо того, чтобы интерполировать просто T — значение атрибута), а так же 1/z. Затем, эти значения в начальной и конечной точках линии интерполируются вдоль нее и используются, чтобы получить итоговое значение атрибута с учетом перспективы, по формуле, данной выше. Нужно помнить, что 1/z, на которую я ссылаюсь, на самом деле лежит в w-координате вектора после всех произведенных трансформаций.
Traversal алгоритмы
Это целая группа алгоритмов, использующих один и тот же подход, основанный на уравнениях граней полигона.
Уравнение грани — это уравнение линии, на которой лежит эта грань. Другими словами, это уравнение прямой, проходящей через две вершины полигона. Соответственно, каждый треугольник характеризуется тремя линейными уравнениями:
Начнем с того, что опишем уравнение прямой, проходящей через две точки (в качестве них выступают пара вершин треугольника):
Мы можем переписать его в следующем виде:
Из последнего выражения видно, что вектор n перпендикулярен вектору v0 — v1 (координаты поменяны местами, и X-координата взята со знаком минус). Таким образом, n — это нормаль к линии, образованной двумя вершинами. Это все то же уравнение прямой, а, значит, подставив туда точку (x, y) и получив ноль, мы знаем, что эта точка лежит на прямой. Что насчет остальных значений? Тут нам и пригодится форма записи с нормалью. Мы знаем, что скалярное произведение двух векторов вычисляет длину проекции первого вектора на второй, умноженную на длину второго вектора. В качестве первого вектора выступает нормаль, а в качестве второго — вектор из первой вершины к точке (x, y):
Мы так же можем задать уравнение прямой таким образом, чтобы нормаль указывала в обратном направлении — достаточно просто домножить его на минус единицу. В дальнейшем я буду предполагать, что уравнение составлено таким образом, что нормаль указывает внутрь треугольника.
Используя эти уравнения, мы можем определить треугольник как пересечение трех положительных полуплоскостей.
Ниже представлен пример функции, определяющей, находится ли пиксель в положительной полуплоскости относительно одной из граней (используя top-left rule). Ей достаточно принимать три аргумента на вход: значение уравнения грани в точке, и координаты нормали:
Простая и полезная оптимизация при вычислении значений уравнений: если мы знаем значение в пикселе с координатами (x, y), то для вычисления значения в точке (x + 1, y) достаточно добавить значение коэффициента a. Аналогично, для вычисления значения в (x, y + 1) достаточно добавить коэффициент b:
Следующий шаг — интерполяция атрибутов и коррекция перспективы. Для этого используются барицентрические координаты. Эти координаты, в которых точка треугольника описывается как линейная комбинация вершин (формально, подразумевая, что точка является центром масс треугольника, при соответствующем весе вершин). Мы будем использовать нормализованный вариант — т.е. суммарный вес трех вершин равен единице:
У этой системы координат так же есть очень полезное свойство, которое позволяет их вычислять: барицентрические координаты равны отношению площадей треугольников, образованных на рисунке выше, к общей площади треугольника (по этой причине они так же иногда называются areal coordinates):
Третья координата может вычисляться не через площади треугольников, поскольку сумма трех координат равна единице — фактически, мы имеем только две степени свободы.
Теперь все готово для линейной интерполяции атрибутов: значение атрибута в заданной точке треугольника равно линейной комбинации барицентрических координат и значений атрибута в соответствующих вершинах:
Для коррекции перспективы мы используем другую формулу — сначала, вычисляем интерполированное значение T/z, затем интерполированное значение 1/z, и затем делим их друг на друга, чтобы получить итоговое значение T с учетом перспективы:
Разница между различными traversal-алгоритмами заключается в том, как выбираются пиксели для проверки. Мы рассмотрим несколько вариантов.
AABB-алгоритм
Как ясно из названия, этот алгоритм просто строит axis-aligned bounding box полигона, и проходит по всем пикселям внутри него. Пример:
Backtracking-алгоритм
Проверить, что пиксель находится левее полигона можно следующим образом — хотя бы для одной грани, у которой нормаль указывает вправо (т.е. a > 0), значение уравнения этой грани отрицательно.
Zigzag-алгоритм
Этот алгоритм можно рассматривать как улучшенный вариант backtracking-алгоритма. Вместо того чтобы «вхолостую» проходить по пикселям в линии, пока не найдется пиксель, с которого мы можем начать двигаться в правую сторону, мы запоминаем информацию о пикселе, с которого мы начали движение на линии, а затем проходим по пикселям слева и справа от него.
Алгоритм растеризации в однородных координатах
Этот алгоритм изначально был описан в публикации Triangle scan conversion using 2D homogeneous coordinates, Marc Olano & Trey Greer. Его основными преимуществами являются отсутствие необходимости в отсечении и делении на w-координату в процессе трансформации вершин (за исключением пары оговорок — они будут описаны позже).
Первым делом, предположим, что, к началу растеризации, x и y координаты вершин содержат в себе значения, которые отображаются в координаты на экране простым делением на соответствующую w-координату. Это может немного изменить код трансформации вершин, при условии, что поддерживается несколько алгоритмов растеризации, поскольку он не включает в себя деление на w-координату. Координаты в однородном двухмерном пространстве передаются напрямую в функцию, которая производит растеризацию.
Рассмотрим подробнее вопрос линейной интерполяции атрибутов вдоль полигона. Поскольку значение атрибута (назовем его p) растет линейно, он должен удовлетворять следующему уравнению (в трехмерном пространстве):
Поскольку точка (x, y, z) проецируется на плоскость с использованием однородных координат (x, y, w), где w = z, мы так же можем записать это уравнение в однородных координатах:
Представим, что мы знаем коэффициенты a, b и с (мы рассмотрим их нахождение чуть позже). При растеризации мы имеем дело с координатами пикселей в пространстве экрана, которые связаны с координатам в однородном пространстве по следующей формуле (это было наше первоначальное предположение):
Мы можем выразить значение p/w используя только координаты в пространстве экрана, путем деления на w:
Для получение корректного значения p при помощи экранных координат, нам достаточно поделить это значение на 1/w (или, что то же самое, умножить на w):
1/w, в свою очередь, может быть посчитано по аналогичному алгоритму — достаточно представить, что мы имеем некий параметр, который одинаков во всех вершинах: p = [1 1 1].
Теперь рассмотрим, каким образом мы можем найти коэффициенты a, b и с. Поскольку для каждого атрибута заданы его значения в вершинах полигона, мы на самом деле имеем систему уравнений вида:
Мы можем переписать эту систему в матричной форме:
Важно заметить, что нам необходимо посчитать всего лишь одну обратную матрицу на полигон — затем эти коэффициенты могут использоваться для нахождения корректного значения атрибута в любой точке экрана. Так же, поскольку нам необходимо вычислить определитель матрицы для ее инвертирования, мы получаем некоторую вспомогательную информацию, поскольку определитель так же вычисляет объем тетраэдра с вершинами в начале координат и точках полигона, умноженного на два (это следует из определения смешанного произведения векторов). Если определитель равен нулю, это значит, что полигон не может быть отрисован, поскольку он либо вырожденный, либо повернут ребром по отношению к камере. Так же, объем тетраэдра может быть со знаком плюс и со знаком минус — и это может использоваться при отсечении полигонов, которые повернуты «спиной» к камере (так называемое backface culling). Если мы считаем корректным порядок вершин против часовой стрелки, то полигоны, у которых значением определителя положительно, должны быть пропущены (при условии использования левосторонней системы координат).
Таким образом, вопрос интерполяции атрибутов уже решен — мы можем вычислить корректное значение (с учетом перспективы) любого атрибута в заданной точке экрана. Осталось только решить, каким точкам экрана принадлежит полигону.
Вспомним, каким образом проверялась принадлежность пикселю к полигону в traversal-алгоритмах. Мы вычисляли уравнения граней, и затем проверяли их значения в нужной точке экрана. Если они все были положительные (или нулевые, но принадлежали к левой или верхней граням), то мы закрашивали пиксель. Поскольку мы уже умеем интерполировать атрибуты вдоль поверхности треугольника, мы можем использовать точно такой же подход, считая, что интерполируем некий псевдо-атрибут, который равен нулю вдоль грани и некоему положительному значению (самое удобное — 1) в противоположной вершине (фактически, это плоскости, проходящие через эти грани):
Соответственно, значения этих псевдо-атрибутов для каждой из граней:
Используя их мы можем вычислить соответствующие коэффициенты a, b и с для каждой из граней и получить их уравнения:
Теперь мы можем аналогичным образом интерполировать их значения вдоль поверхности треугольника и вычислять их значения в нужной нам точке. В случае, если оно положительно, либо же оно нулевое, но мы находимся на левой и верхней грани, пиксель находится внутри полигона и должен быть закрашен. Мы так же можем применить небольшую оптимизацию — нам совсем не нужны точные значения уравнений граней, достаточно его знака. Поэтому можно избежать деления на 1/w, мы можем просто проверить знаки p/w и 1/w — они должны совпадать.
Поскольку мы оперируем все теми же уравнения граней, многое, сказанное в разделе о traversal-алгоритмах, может быть применено и к этому алгоритму тоже. Например, top-left rule может быть реализован аналогичным образом, а значения уравнений граней могут рассчитываться инкрементально, что является полезной оптимизацией.
При представлении этого алгоритма, я написал, что данный алгоритм не требует реализации отсечения, поскольку оперирует в однородных координатах. Это почти целиком верно, за исключением одного случая. Могут быть ситуации при работе с w-координатами точек, которые близки к началу координат (или совпадают с ним). В этом случае могут произойти переполнения при интерполяции атрибутов. Так что хорошей идеей будет добавление еще одной «грани», которая расположена параллельно плоскости xy и находится на расстоянии z near от начала координат, чтобы избежать подобных ошибок.
При описании traversal-алгоритмов я упомянул несколько вариантов выбора множества пикселей, которые следует проверять на принадлежность треугольнику (axis aligned bounding box, backtracking, zigzag алгоритмы). Их можно применить и здесь. Это и есть ситуация, в которой все-таки необходимо будет деление вершин на w-координату для вычисления граничных значений (например, координат bounding box’а), следует только предусмотреть ситуации, когда w