Хабрахабр

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

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

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

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

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

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

Какая от этого польза? 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, то получится квадратное уравнение. Что же получится по другим линиям?

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

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

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

m=0, b=0

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

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

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

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

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

m=1, b=0

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

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

$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, когда x равно нулю. Вы можете удивиться, что уравнение заканчивается $+C$ вместо $+A$, но если посмотреть на график, то это имеет смысл.

x=2u, y=3u

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

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

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

$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.

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

5+0. $x=sin(2\pi u)*0. 5$

5+0. $y=cos(2 \pi u)*0. 5$

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

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

5+0. $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) + A$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

@Atrix256

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть