[Перевод] Прогулка между пикселями02.05.2018 19:33

Этот пост относится к моей статье о вычислении точек на кривых Безье с помощью линейной интерполяции текстур. Расширенный метод распространяется на поверхности Безье и (многомерные) многочлены.

Первоначальное наблюдение состояло в том, что если произвести выборку по диагонали текстуры 2×2, то в качестве выходных данных получатся точки на квадратичной кривой Безье, а опорные точки кривой являются значениями пикселей, как на изображении ниже. Когда я говорю, что вы получаете квадратичную кривую Безье, то выражаюсь буквально и точно. Происходящее можно представить так: интерполяция текстуры буквально выполняет алгоритм де Кастельжо. (Примечание: если в примере ниже значения «B» не равны, то вторая опорная точка будет средним из этих двух значений: расширение злоупотребляет этим, чтобы аппроксимировать больше кривых в меньшее количество пикселей).

В моих планах давно было посмотреть, что происходит при выборке пикселей по другим направлениям, кроме диагонали 45°. В частности, интересует следующее:

Что если попробовать другую линию?
Что если произвести выборку вдоль квадратичной кривой, например, ?
Что если попробовать окружность или синусоиду?
Как изменятся паттерны выборки в высших измерениях, вроде трилинейной или квадрилинейной интерполяции?

Когда я случайно наткнулся на ответ на первый вопрос, пришло время взглянуть и на другие!

P.S. Какая от этого польза? Самое лучшее, что приходит в голову — сжатие данных на GPU. Если аппроксимировать кусочно-рациональными многочленами, то идеи этого метода пригодятся для сжатия данных (пиксели в текстуре), которые быстро и легко декодируются GPU. Идеи из этой статьи позволяют использовать при аппроксимации и хранении данных другие виды кривых, кроме кусочно-рациональных многочленов. Кроме того, кривые и поверхности более высокого порядка занимают меньший объём текстур.

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

Билинейную интерполяцию можно описать как интерполяцию двух значений по оси x и интерполяцию результатов по оси y (или в обратном порядке). Математически это выглядит так:

$z = (A (1-x) + Bx) (1-y) + (C (1-x)+Dx)y$

Где x и y — значения от 0 до 1, описывающие расположение точки между пикселями, а A, B, C и D — значения четырёх ближайших пикселей, которые образуют прямоугольник вокруг точки, которую мы вычисляем. A = (0,0), B = (1,0), C = (0,1) и D = (1,1).

После некоторых преобразований это уравнение представляется в виде степенного ряда, который лучше подходит для наших экспериментов:

$z = (A-B-C+D)xy + (B-A)x + (C-A)y + A$

Для более подробной информации о билинейной интерполяции изучите эти материалы: 1, 2, 3, 4.

С формулой на руках можно начинать!

Итак, мы знаем, что если выборка идёт по диагонали от A до D, то получится квадратное уравнение. Что же получится по другим линиям?

Прежде чем я узнал ответ, то предполагал, что если линия под углом 45° даёт квадратное уравнение (степень 2), а горизонтальные и вертикальные линии — линейное (степень 1), то выборка вдоль других линий должна быть многочленом со степенью между 1 и 2. Ответ оказался не таким, но меня заинтересовало, можно ли интерпретировать «настоящий ответ» в виде многочлена со степенью между 1 и 2?

В любом случае, мне подсказала Википедия:

«Интерполянт линеен вдоль линий, параллельных x или y, то есть если x или y являются константами. Вдоль любой другой прямой линии интерполянт квадратичен»

Это значит, что по горизонтальной или вертикальной линии будет линейное уравнение. Любая другая линия даёт квадратичное.

Давайте проверим.

Помним, что уравнение для линейной функции $y=mx+b$ , так что буквально заменим $y$ на $mx+b$ и посмотрим, что получится.

Итак, начнём со степенного ряда многочлена билинейной интерполяции:

$z = (A-B-C+D)xy + (B-A)x + (C-A)y + A$

После замены получается:

$z = (A-B-C+D)x(mx+b) + (B-A)x + (C-A)(mx+b) + A$

После некоторого расширения и упрощения получаем следующее:

$z = (Am-Bm-Cm+Dm)x^2+(Ab-Bb-Cb+Db+Cm-Am+B-A)x+Cb-Ab+A$

Эта формула сообщает значение билинейной интерполяции A, B, C и D (то есть билинейной поверхности, ограниченной этими точками), и мы осуществляем выборку вдоль линии x, y, определённой $y=mx+b$ .

Это очень обобщённая функция, о которой трудно много рассуждать, но ясно одно: это квадратичная функция! Какие бы постоянные значения вы ни выбрали для A, B, C, D, m и b, вы получите квадратичный многочлен (или более низкую степень, но никогда не выше).

Этот шейдер показывает кривые, сгенерированные случайными субпиксельными сегментами линии на случайной текстуре RGB (белый шум).

(Обратите внимание, что неровные края кривой связаны с тем, что интерполяция происходит в формате с фиксированной запятой X.8, так что точность довольно ограничена. См. вышеупомянутую научную работу для дополнительной информации и способов решения этой проблемы).

Пойдём дальше, укажем некоторые значения для $m$ и $b$ и посмотрим, что происходит для разных типов линий.

m=0, b=0

Что будет, если m и b равны 0. Другими словами, что произойдёт при выборке вдоль линии $y=0$ .

Подстановка этих значений даёт:

$z = (B-A)x + A$

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

Это согласуется с тем, что нам сказала Википедия: когда одна из координат неизменна (горизонтальная или вертикальная линия), то результат линейный.

m=1, b=0

Попробуем m = 1 и b = 0. Это линия $y=x$ . График показывает, откуда берётся выборка на билинейной поверхности:

Подстановка этих значений даёт такое уравнение:

$z = (A-B-C+D)x^2+(C+B-2A)x+A$

Мы получили квадратное уравнение, что не должно слишком удивлять. Это также формула для квадратичной кривой Безье с опорными точками $A$ , $(B+C)/2$ , $D$ .

m=2, b=1

Попробуем линию $y=2x+1.$ Вот график, где мы производим выборку на билинейной поверхности:

Подстановка значений даёт нам уравнение:

$z = (2A-2B-2C+2D)x^2+(C+D-2A)x+C$

Опять получилась квадратичная функция.

Вы можете удивиться, что уравнение заканчивается $+C$ вместо $+A$ , но если посмотреть на график, то это имеет смысл. Линия буквально начинается в точке C, когда x равно нулю.

x=2u, y=3u

В приведённых выше примерах мы изменяем только переменную y как функцию от x. Что если также изменить переменную x?

Один из вариантов — ввести третью переменную $u$ , которая принимает значения от 0 до 1. Тогда можно выразить x и y через эту переменную.

Посмотрим, что происходит, если использовать эти два уравнения:

$y=2u$

$x=3u$

Выборка проходит вдоль такой линии на билинейной поверхности.

Подстановка функций u для x и y даёт:

$z = (6A-6B-6C+6D)u^2+(2B+3C-5A)u+A$

Это всё равно квадратное уравнение!
Итак, теперь мы знаем, что при движении по прямой линии на билинейной поверхности получается квадратичная функция, за исключением случая, когда линия является горизонтальной или вертикальной. Примечание: если билинейная поверхность является плоскостью, то все линии на этой поверхности будут линейными функциями, так что это ещё один способ получить линейный результат. Он также может выродиться в точку. Вы никогда не получите кубический результат (или выше) при движении по прямой линии.

Что произойдёт, если вместо выборки по прямым линиям выбрать другие формы, такие как квадратичные кривые?

y=x*x

Начнём с функции $y=x^2$ . Вот полученная кривая:

Возвращаясь к форме билинейной интерполяции в виде степенного ряда, давайте подставим $x^2$ вместо $y$ и посмотрим, что получится.

Начальное уравнение:

$z = (A-B-C+D)xy + (B-A)x + (C-A)y + A$

становится таким:

$z = (A-B-C+D)x(x^2) + (B-A)x + (C-A)(x^2) + A$

Оно превращается:

$z = (A-B-C+D)x^3 + (C-A)x^2 + (B-A)x + A$

Это кубическое уравнение!

Вот шейдер, который выводит эту траекторию для случайных пикселей:

Определённая изящность этого примера в том, что у кубического уравнения четыре коэффициента, которые основаны на четырёх опорных точках, так что «всё идёт в дело», если можно так выразиться.

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

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

x=u*u, y=u*u

Посмотрим, что происходит, если двигаться по x и y квадратично.

Как и в линейном случае, у нас есть наша третья переменная u, которая изменяется от 0 до 1, и у нас есть x и y, основанные на этой переменной. Будем использовать такие уравнения:

$x=u^2$

$y=u^2$

Траектория выборки выглядит следующим образом:

Когда подставим значения, то получается уравнение четвёртой степени:

$z = (A-B-C+D)u^4 + (B+C-2A)u^2 + A$

Вы можете удивиться, глядя на линейную траекторию. Просто дело в том, что x всегда равно y, пусть они даже изменяются по графику нелинейно: шейдер.

Давайте немного порезвимся, взяв такие уравнения:

$x=3u^2$

$y=u^4$

Что соответствует такой траектории выборки:

Если подставить значения, то уравнение билинейной интерполяции…

$z = (A-B-C+D)xy + (B-A)x + (C-A)y + A$

… превращается в уравнение шестой степени:

$z = (3A-3B-3C+3D)u^6 + (C-A)u^4 + (3B-3A)u^2 + A$

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

Попробуем функцию $y=sin (2\pi x)$ , которая идёт по такой траектории на билинейной поверхности:

Уравнение билинейной интерполяции становится тригонометрическим многочленом:

$z = (A-B-C+D)x*sin(2\pi x) + (B-A)x + (C-A)*sin(2\pi x) + A$

Здесь есть разрывы из-за выхода за пределы изначальной пиксельной области, поэтому в данном случае лучше выглядит этот шейдер, сгенерированный для $y=sin(2\pi x)*0.5+0.5$ . Он масштабирует и сдвигает значения y, чтобы они находились между 0 и 1.

Наконец, выборка по окружности.

$x=sin(2\pi u)*0.5+0.5$

$y=cos(2 \pi u)*0.5+0.5$

Вот её траектория:

Подставляем в билинейное уравнение:

$z = (A-B-C+D)*(sin(2 \pi u)*0.5+0.5)*(cos(2 \pi u)*0.5+0.5) + (B-A)*(sin(2 \pi u)*0.5+0.5) + (C-A)*(cos(2 \pi u)*0.5+0.5) + A$

Соответствующие шейдеры.

Замечательная особенность выборки по кругу — её непрерывность. Обратите внимание, как левая сторона кривой незаметно переходит в правую. Это кажется довольно полезным свойством.

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

Это сложнее простого метода «выборки по диагонали», и требуются инструкции шейдера. В частности, в шейдере нужно закодировать любое изменение x или y перед передачей в интерполятор линейных текстур. Значит, метод требует больше ресурсов ALU. Но зато он экономит текстурную память.

Последний вопрос из перечисленных в начале статьи: как изменятся паттерны выборки в высших измерениях, вроде трилинейной или квадрилинейной интерполяции?

Ну, здесь механизм примерно такой же, как в билинейной интерполяции, только больше измерений.

В двумерной билинейной интерполяции мы видели, что после превращения x и y в функции (либо друг от друга, либо от третьей переменной u) у полученного многочлена была степень, равная сумме степеней x и y.

В трёх измерениях с трилинейной интерполяцией итоговый многочлен будет иметь степень, равную сумме степеней x, y и z.

В четырёх измерениях с квадрилинейной интерполяцией добавьте ещё степень z.

Рассмотрим случай, когда нам нужна не кривая, а поверхность или (гипер) объём.

Как мы видели в расширении, которое работает с поверхностями и объёмами, если у нас многочлен степени N, то его можно разбить на многомерный многочлен (он же поверхность или гиперобъём), если сумма степеней каждой оси складывается в N.

Это примерно то, о чём мы только что говорили, только наоборот.

Есть кое-что, что мне кажется интересным изучить в будущем — посмотреть, какие ограничения возникают, если зайти «слишком далеко».

Например, текстура 2×2 может дать квадратичную функцию, если провести выборку вдоль любой прямой в координатах uv. Если сначала выразить координату u через кубическую функцию, а координату v — через другую кубическую функцию, то я думаю, что можно сделать бикубическую поверхность.

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

Хотелось бы посмотреть, какие там ограничения и есть ли шанс получить реальную пользу от чего-то подобного.

Во всяком случае, спасибо за чтение! Любые идеи, исправления, случаи использования — бросайте мне!

@Atrix256