Pull to refresh

Comments 27

Не увлекаюсь явой, но статья, как ни странно, показалась интересной. Видимо, тяготит меня к «своим велосипедам». Даже подожду вторую часть.
Джавой она называется, джавой.
Спасибо за статью. Хороший велосипед, горный годный.
Дрожь берёт, как представишь, сколько суровой математики скрыто за тем, чтобы «зделать симпотичную аватарку».
Я бы вспомнил аналитическую геометрию (длина AF — проекция AE на AB), а еще лучше матричные преобразования (найти такую матрицу M, чтобы M*A = [0;0; 1], M*B=[0; 255; 1], тогда цвет пикселя будет color(координата_x(M*координаты_пикселя)), где f функция x->цвет). Так, сходу, никогда градиентов не рисовал.
Ага. Автору стоит подучить векторную алгебру, через неё такие вещи гораздо проще делаются.
Поддерживаю. В данном случае AF можно найти как скалярное произведение векторов AE и AB, что значительно быстрее. Длину вектора AB можно посчитать заранее, причём лучше инвертированную, то есть 1 / |AB|. В итоге расчёт для каждой точки будет состоять из двух вычитаний (для нахождения вектора AE), двух умножений и сложения (скалярное произведение) и умножения (для вычисления отношения AF / AB).

Более того, можно заметить, что линии, поперечные AB, имеют одинаковую лестничную структуру. Можно вычислить эту структуру и делать прогоны параллельными линиями.

Короче, оптимизировать можно долго. :-)
А нормализация АE куда делась?
Верно, забыл. Нормализируем на длину вектора AB, поэтому посчитанный коэффициент можно возвести в квадрат. Исходя из этого, формула для него становится ещё проще: k = 1 / ( |AB| )^2 = 1 / (dx^2 + dy^2).
О, благодаря этой статье я вспомнил свои увлечения градиентами в школе, даже с такой программой на областном конкурсе Малой академии наук второе место взял.
Могу вам сходу подсказать приличную оптимизацию
Описание оптимизации
Вычерчивать такой градиент (а соответственно и вычислять цвета точек) нужно не по точкам, а целыми линиями, перпендикулярными отрезку, соединяющему управляющие точки градиента. Ведь для каждой такой линии точек одинаковый. Таким образом вы в десятки-сотни раз (смотря какая форма закрашиваемой области) уменьшите количество корней, косинусов и умножений.
А т.к. все линии параллельны, и полностью заполняют собой пространство, рисовать можно без антиэлейзинга, и даже дельту линии нужно будет вычислить всего один раз.
А в качестве начальных точек каждой линии брать точки на отрезке, соединяющем управляющие точки. Тогда и вычислением проекции стороны треугольника на основание заниматься не придется.
По моим прикидкам ускорение должно быть раз в 50.

Кстати, косинусная интерполяция — это просто замечательно. В свое время я так и не понял, почему мои градиенты «немного не такие» :)
На курсе высшей математики при изучении градиентов у многих фотошоперов был разрыв шаблона, потому как градиенты были в виде уравнений и стрелочек и без графики!
наш использует линейную интерполяцию, а в фотошопе в ходу определенно какая-то другая.

В ФШ этим делом можно управлять через параметр Smoothness, по умолчанию равный 100%. Если установить его в 0% — получим просто линейный градиент. Разумеется, возможны и промежуточные значения.
Это сделано для гладкости стыковки двух и более градиентов. При линейной интерполяции такие стыки становятся резко видны.
Подробности с картинками, например, здесь: bourt.com/blog/?p=700

Лично я предпочитаю это сглаживание включать только при необходимости. Если градиент одиночный — отключаю. Так получается естественнее и предсказуемее при экспорте, например, в CSS.
Спасибо, не знал. В принципе, если в ФШ при значении 0 получается результат как у меня с INTERPOLATION_LINEAR, а при значении 100 — как с INTERPOLATION_COS_LINEAR, можно легко реализовать передачу в метод параметра smoothness. Более того, можно ограничить его не сотней процентов, а двумя сотнями (INTERPOLATION_COS эквивалентен smoothness 200%, как я понимаю)
Скорее всего там используется не интерполяция косинусом (она не гибка, и неудобна в использовании) а полином третьей степени. См. мой комментарий ниже, и параметры P1 и P2 вычиляются в зависимости от smoothnes скорее всего так:
P1 = smoothnes * 0.5
P2 = 1 — smoothnes * 0.5

p.s. В фотошоп не заглядывал, нужно проверить
ошибся, P1 и P2 надо считать так:
p1 := (1 — smooth) * (1 / 3);
p2 := (1 — p1);
а вот и семпл с исходником, клик мышом и тянем. Вверху трекбар — smoothnes как в фш: screenup.org/tmp/Grad.7z (осторожно, Delphi, но бинарник присутствует)
Простите мое невежество (далек от веб-графики). А что, из ФШ можно экспортировать градиенты в CSS, или под экспортом имеется ввиду нечто иное?
Спасибо за ответ!
Я «экспортирую» вручную: просто беру пипеткой 2 крайних цвета и вставляю из в онлайн генератор www.colorzilla.com/gradient-editor/. Насчет автоматизации — не знаю, но вполне возможно, что таковые плагины есть.

Если параметр Smoothness=0, результат в CSS получается а) идентичным б) более плавным. При Smoothness=100 градиент, перенесенный в CSS по 2-ум крайним точкам, будет визуально более «плоский», чем казался в ФШ.

Учитывая наличие java.awt.GradientPaint, java.awt.LinearGradientPaint и java.awt.RadialGradientPaint, практическая значимость не очень ясна. Вот разве что была бы версия для SWT, так как там возможности рисования градиентов скромные.
Можно я вам подскажу.
Вспомним что такое скалярное произведение векторов.
Это модуль одного вектора, на модуль другого и на косинус угла между ними: c = |a|*|b|*cos(ab). Так же справедлива формула: c = ax * bx + ay * by
Так вот, если косинус отрицательный, то угол больше 0.5*Пи, длины векторов у нас всегда положительны, а значит, что если все скалярное произведение отрицательно, то угол между векторами больше 0.5*Пи
По этому рисунку получается, что точка точка лежит в красной зоне, если (AE*AB) отрицательное.
Точка лежит в зеленой части, если (BE*BA) отрицательное.
image
И не надо никаких теорем пифагора, квадратных корней и прочего.
В сухом остатке, у вас есть координаты A (Ax. Ay), координаты B (Bx, By) и координаты E (Ex, Ey)
Проверки:
if (((Ex — Ax)*(Bx — Ax) + (Ey — Ay)*(By — Ay))<0) //точка в красной зоне
if (((Ex — Bx)*(Ax — Bx) + (Ey — By)*(Ay — By))<0) //точка в зеленой зоне

Теперь посмотрим, как поможет нам скалярное произведение для промежуточного этапа.
Вспоминаем, что косинус на тригонометрическом круге — ничто иное, как проекция на ось X. Т.к. у нас косинус между векторами, то можно считать, что ось X направлена так же, как наш вектор AB.
Смотрим еще раз на формулы скалярного произведения:
c = ax * bx + ay * by
c = |a|*|b|*cos(ab)
косинус отсюда будет:
cos(ab) = (ax * bx + ay * by) / (|a|*|b|)
если мы умножим длину вектора AE на этот косинус, то мы получим длину вектора AF
Но сам по себе вектор AF нам не удобен, для градиента. Удобно было бы получить нормализованное значение. Это значение, лежащее в диапазоне от 0 до 1, так, что если F лежит в точке A, то наше нормализованное значение будет 0, а если А лежит в точке B — то нормализованное значение будет равно 1, и значение изменяется линейно. Для этого нам нужно разделить длинну AF на длинну AB.
Итак финальный результат, зная координаты трех точек (как уже было описано ранее)
t = ((Ex — Ax)*(Bx — Ax) + (Ey — Ay)*(By — Ay)) / (|AB|*|AE|) * |AE| / |AB|
длина AE сокращается с длиной в знаменателе, длина AB превращается в квадрат длины вектора AB: ((Bx — Ax) * (Bx — Ax) + (By — Ay) * (By — Ay))
Причем квадрат длины AB можно подсчитать 1 раз.
Итак t = ((Ex — Ax)*(Bx — Ax) + (Ey — Ay)*(By — Ay)) / ((Bx — Ax) * (Bx — Ax) + (By — Ay) * (By — Ay))

Таким образом на точку нам понадобится считать максимум:
два скалярных произведения
((Ex — Ax)*(Bx — Ax) + (Ey — Ay)*(By — Ay))
((Ex — Bx)*(Ax — Bx) + (Ey — By)*(Ay — By)
и одно деление на квадрат длины AB

Что намного быстрее тех корней что у вас ;)
Интерполяция.
Я не смотрел, как фотошоп рисует график, но судя по вашим картинкам нужна функция f(t)=t'

Для конкретного случая нам подойдет полином третьей степени, и я бы воспользовался кривой безье.
image
P0 у нас всегда 0. P3 у нас всегда 1. Ну а P1 и P2 либо на глазок, скажем P1 (0.3, 0.2) и P2 (0.7, 0.8) либо анализировать градиент фотошопа, чтобы сделать точную реплику
Думаю, вам будет очень интересно это видео, там как раз рассматриваются интерполяции градиентов: www.youtube.com/watch?v=BkTiqe-8QZA
Реализовав данные идеи, можно будет легко посоревноваться в качестве отрисовки градиентов со стандартной java-библиоекой.
Хорошая статья! Куча инфы в комментариях!
Еще нужно реализовать дизеринг, иначе градиент будет полосками (banding), особенно на некоторых дисплеях.
Спасибо за статью! Она как раз кстати — утром делал графику в джаве для диплома и тоже реализовал градиент, но другого типа. Интересное совпадение вышло.
Сейчас, благодаря Вашей статье, кое что подправил, ибо отрисовка изображения у меня было организована через… А впрочем, это уже совсем другая история.
Много оптимизаций для алгоритма можно почерпнуть из компьютерной графики. В случае, приведенном у вас на пояснительных изображениях — каждая строка средней части градиента — это, по сути, градиент в одну линию. Промежуточные точки которого рассчитываются довольно быстро по крайним значениям, либо по начальному значению + смещение цвета на пиксель. При этом для последовательного расчета промежуточных точек будет использоваться только сложение. Естественно, всё это справедливо без наложения корректирующей кривой.
Недавно у меня вывелась формула, которая очень хорошо (разница не превышает 1%) приближает косинус-интерполяцию: 3 * t^2 — 2 * t^3

Погуглил — оказывается, я переизобрел так называемый smoothstep, который давным-давно известен и реализован во всех графических библиотеках: en.wikipedia.org/wiki/Smoothstep

Sign up to leave a comment.

Articles