![](https://jeremykun.files.wordpress.com/2013/05/s-pablo-picasso-large640.jpg)
Пабло Пикассо в своей студии на фоне картины «Кухня», фотография Херберта Листа.
Художник и простота
Одни из самых любимых мной работ Пабло Пикассо — это его линейные рисунки. Он изобразил на некоторых из них животных: сову, верблюда, бабочку и т.д. Эта работа под названием «Собака» висит на моей стене:
![](https://jeremykun.files.wordpress.com/2013/05/dachshund-picasso-sketch.jpg)
(Можете перейти к интерактивному демо, в которой мы воссоздали «Собаку» с помощью представленных в статье математических расчётов)
Эти рисунки чрезвычайно просты, но каким-то образом им удаётся глубоко тронуть зрителя. Они создают впечатление простоты композиции и реализации. Одно движение руки и подпись создают настоящий шедевр! Рисунок одновременно кажется и небрежной импровизацией, и точно подобранной увертюрой в симфонии изящества. На самом деле мы знаем, что процесс работы Пикассо был глубоким. Например, в 1945-1946 годах Пикассо создал серию из одиннадцати рисунков (литографий, если точнее), демонстрирующих его постепенный прогресс в визуализации быка. Первые были более-менее похожи на реалистичные, но в дальнейшем мы видим, как бык превращается в саму свою сущность, а последний рисунок состоит всего из десятка линий. В процессе развития серии рисунков мы видим быка, напоминающего некоторые из других работ Пикассо (номер 9 напоминает мне скульптуру в чикагском Daley Center Plaza). Здесь можно подробнее прочитать о серии литографий.
![](https://jeremykun.files.wordpress.com/2013/04/the-bull.jpg)
«Бык» Пикассо. Фотография сделана Джереми Куном в Институте искусств в Чикаго. Нажмите на изображение, чтобы увеличить его.
Я не буду притворяться опытным художником (я не смог бы нарисовать быка, даже если бы от этого зависела моя жизнь), зато я могу распознать математические аспекты его картин и написать чертовски хорошую программу. Есть один очевидный способ рассмотрения линейных рисунков в стиле Пикассо как математических объектов, и это конечно же кривые Безье. Давайте начнём с изучения теории кривых Безье, а потом напишем программу для их отрисовки. Используемая в ней математика не требует никаких дополнительных знаний, кроме основ алгебры и полиномов, и я постараюсь как можно меньше вдаваться в сложные подробности. Мы изучим очень простой алгоритм рисования кривых Безье, реализуем его на Javascript, а затем воссоздадим один из линейных рисунков Пикассо с помощью нескольких кривых Безье.
Кривые Безье и параметризация
Когда кто-нибудь просит вспомнить «кривые», большинство людей (возможно, отравленных преподаванием основ математики) или начинает трястись от страха, или рисует часть графика многочлена. Хотя это вполне правильные и уважаемые кривые, но они представляют лишь небольшую часть мира кривых. Особенно нас интересуют кривые, которые не являются частью графиков функций.
![](http://upload.wikimedia.org/wikipedia/commons/0/0c/Krzywiki.jpg)
Три лекала.
Например, лекало — это физический шаблон, используемый для (ручного) рисования плавных кривых. Просто соединяя рёбрами любую часть этих кривых, мы обычно не можем получить график функции. Очевидно, что нам нужна более общая идея о том, что же такое кривые. Проблема в том, что в разных областях математики под «кривой» подразумеваются различные понятия. Кривые, которые мы будем изучать, называемые «кривыми Безье» — это особый случай полиномиальных плоских кривых с одним параметром. Это звучит слишком сложно, но на самом деле это означает, что всю кривую можно задать двумя многочленами: одним для значений
На примере всё должно стать понятнее. Давайте подберём два простых многочлена от
![](https://jeremykun.files.wordpress.com/2013/05/example-curve.jpg)
Но очевидно, что мы можем записать любую функцию с одной переменной
Вкратце повторим: полиномиальная плоская кривая с одним параметром задаётся как пара многочленов
Здесь коэффициенты — это точки на плоскости (те же, что и векторы), и мы выделяем функцию
Мы также ограничим наше внимание рассмотрением однопараметрических плоских кривых, описываемых полиномом, для которых переменная
С этими кривыми мы можем делать очень интересные вещи. Например для любых двух точек в плоскости
Для более общего случая давайте добавим третью точку
Выполнив все эти умножения, мы получим формулу
С течением времени точка
![](https://jeremykun.files.wordpress.com/2013/05/screen-shot-2013-05-07-at-9-38-42-pm.png)
Этот скриншот взят из потрясающего демо консультанта по визуализации данных Джейсона Дейвиса. Он идеально демонстрирует математическую идею. В демо можно перетаскивать все три точки, чтобы посмотреть, как это влияет на конечную кривую. Стоит поиграть с ней хотя бы пять минут.
Вся идея кривых Безье заключается в обобщении этого принципа: имея список точек
Определение: для заданного множества точек на плоскости
Мы назовём
Хотя концепция перемещения с единичной скоростью между двумя кривыми Безье более низкого порядка является настоящей сутью дела (и позволяет нам подойти с к решению с вычислительной точки зрения), можно просто всё это перемножить (с помощью формулы биномиальных коэффициентов) и получить формулу в явном виде. Она будет следующей:
Например, кубическая кривая Безье с контрольными точками
Кривые Безье более высокого порядка может быть достаточно сложно отобразить геометрически. Например, ниже показана кривая Безье пятой степени (с шестью контрольными точками).
![](https://jeremykun.files.wordpress.com/2013/05/beziercurve.gif)
Кривая Безье пятой степени, иллюстрация из Википедии.
Отрисованные дополнительные отрезки прямых демонстрируют рекурсивную природу кривой. Самые простые — зелёные точки, перемещающиеся между контрольными точками. Синие точки перемещаются по отрезкам прямых между зелёными точками, розовые перемещаются по отрезкам между синими, оранжевые — между розовыми, и, наконец, красная точка перемещается по отрезку прямой между оранжевыми точками.
Без рекурсивной структуры задачи (просто из наблюдения за кривой) было бы сложно понять, как можно всё это вычислить. Но как мы увидим, алгоритм отрисовки кривой Безье очень естественен.
Кривые Безье как данные и алгоритм де Кастельжо
Давайте выведем и реализуем алгоритм отрисовки кривой Безье на экране, воспользовавшись исключительно возможностью рисования прямых линий. Для простоты мы ограничимся рассмотрением только кривых Безье третьей степени (кубических). И в самом деле, любая кривая Безье по рекурсивному определению может быть записана как сочетание кубических кривых, и на практике кубические кривые обеспечивают баланс между эффективностью вычислений и выразительностью. Весь код в этом посте написан на Javascript и выложен на странице этого блога на Github.
Итак, кубическая кривая Безье представляется в программе списком из четырёх точек. Например,
var curve = [[1,2], [5,5], [4,0], [9,3]];
В большинстве графических библиотек (в том числе в стандартной HTML5 canvas) существует графический примитив, способный выводить кривые Безье на основании списка из четырёх точек. Но предположим, что у нас нет такой функции. Предположим, что мы можем рисовать только прямые линии. Как же мы можем нарисовать аппроксимацию кривой Безье? Если такой алгоритм существует (а он есть, и мы убедимся в этом), то мы можем создать настолько точную аппроксимацию, что она будет визуально неотличима от истинной кривой Безье.
Важнейшее свойство кривых Безье, которое позволит нам создать такой алгоритм, заключается в следующем:
Любую кубическую кривую Безье
Давайте посмотрим, как же это сделать. Пусть
Более того, наше рекурсивное определение даёт нам способ вычислить точку на основании кривых меньшей степени. Но когда вычисления выполняются при 1/2, их формулы достаточно просто записать. Изображение выглядит так:
![](https://jeremykun.files.wordpress.com/2013/05/subdivision.png)
Зелёные точки — это кривые первой степени, розовые точки — кривые второй степени, а синяя точка — это кубическая кривая. Мы заметим, что поскольку каждая из кривых вычисляется при
На самом деле, разделение на две нужные нам кривые точно задаётся этими точками. То есть половина кривой задаётся
Как мы можем быть уверены, что это точно те же кривые Безье? Ну, это просто полиномы. Мы можем проверить их на равенство с помощью запутанных алгебраических вычислений. Но стоит заметить, что поскольку
Алгебраические вычисления очень запутаны, но вполне посильны. В доказательство привожу скринкаст того, как я выполняю вычисления, доказывающие идентичность двух кривых.
Теперь, когда мы всё проверили, у нас есть хороший алгоритм для разделения кубической кривой Безье (или любой кривой Безье) на две части. На Javascript он будет выглядеть так:
function subdivide(curve) {
var firstMidpoints = midpoints(curve);
var secondMidpoints = midpoints(firstMidpoints);
var thirdMidpoints = midpoints(secondMidpoints);
return [[curve[0], firstMidpoints[0], secondMidpoints[0], thirdMidpoints[0]],
[thirdMidpoints[0], secondMidpoints[1], firstMidpoints[2], curve[3]]];
}
Здесь
curve
— это список из четырёх точек, как описано в начале этого раздела, а выходными данными является список двух кривых с правильными контрольными точками. Используемая функция midpoints
достаточно проста, и для полноты мы тоже добавим её сюда:function midpoints(pointList) {
var midpoint = function(p, q) {
return [(p[0] + q[0]) / 2.0, (p[1] + q[1]) / 2.0];
};
var midpointList = new Array(pointList.length - 1);
for (var i = 0; i < midpointList.length; i++) {
midpointList[i] = midpoint(pointList[i], pointList[i+1]);
}
return midpointList;
}
Она просто получает на входе список точек и вычисляет их последовательные средние точки. То есть список из
Как я объяснил ранее, мы можем продолжать подразделять нашу кривую снова и снова, пока каждая из небольших частей не станет практически прямой. То есть наша функция для отрисовки кривой Безье будет следующей:
function drawCurve(curve, context) {
if (isFlat(curve)) {
drawSegments(curve, context);
} else {
var pieces = subdivide(curve);
drawCurve(pieces[0], context);
drawCurve(pieces[1], context);
}
}
Если выразить словами, то поскольку наша кривая не «плоская», мы хотим рекурсивно подразделять и отрисовывать каждую часть. Если она плоская, то мы можем просто отрисовать три отрезка прямых кривой и логично считать, что это будет хорошей аппроксимацией. Используемая здесь переменная контекста представляет собой холст (canvas), на которой должна выполняться отрисовка; её нужно передавать фунции
drawSegments
, которая просто отрисовывает на холсте прямую линию.Разумеется, это ставит перед нами очевидный вопрос: как мы можем определить, что кривая Безье плоская? Для этого есть множество способов. Можно вычислять углы отклонения (от прямой) в каждой внутренней контрольной точке и складывать их. Или можно вычислить объём образуемого четырёхугольника. Однако вычисление углов и объёмов обычно не так удобно: на расчёты углов тратится много времени, объёмы имеют проблемы со стабильностью, а стабильные алгоритмы не очень просты. Нам нужно измерение, для которого достаточно простой арифметики и, возможно, проверки нескольких логических условий.
Оказывается, что такое измерение существует. Его изначально приписывают Роджеру Уилкоксу, но оно достаточно просто выводится вручную.
В сущности, мы хотим измерить «плоскостность» кубической кривой Безье вычислением расстояния от настоящей кривой во время
Формально, имея заданную
Здесь не происходит ничего волшебного. Мы просто задаём кривую Безье с контрольными точками
Теперь мы зададим функцию
Добавив немного алгебры, мы можем упростить это выражение. Во-первых, значение
Теперь давайте запишем разность как один полином. Во-первых, мы можем избавиться от троек в
и поэтому
Вынеся за скобки
Поскольку максимумом произведения является произведение максимумов, мы можем ограничить вышеприведённую величину произведением двум максимумов. Причина этого в том, что мы сможем просто вычислить два максимума по отдельности. Вычислить максимум несложно и без разделения, но при таком способе нам потребуется меньше этапов вычислений в готовом алгоритме, а визуальный результат будет таким же хорошим.
Применив элементарные вычисления с единственной переменной, получим, что максимальное значение
И заметьте: для любых вещественных чисел
И поэтому наше условие плоскостности заключается в том, чтобы это ограничение было меньше некоторого допуска. Мы можем безопасно разложить 1/16 на множители в это ограничение допуска, и этого будет достаточно для того, чтобы записать функцию.
function isFlat(curve) {
var tol = 10; // всё, что меньше 50, выглядит довольно хорошо
var ax = 3.0*curve[1][0] - 2.0*curve[0][0] - curve[3][0]; ax *= ax;
var ay = 3.0*curve[1][1] - 2.0*curve[0][1] - curve[3][1]; ay *= ay;
var bx = 3.0*curve[2][0] - curve[0][0] - 2.0*curve[3][0]; bx *= bx;
var by = 3.0*curve[2][1] - curve[0][1] - 2.0*curve[3][1]; by *= by;
return (Math.max(ax, bx) + Math.max(ay, by) <= tol);
}
Вот и она. Мы написали простую HTML-страницу, чтобы получить доступ к элементу canvas и несколько вспомогательных функций для отрисовки отрезков прямой, когда кривая достаточно плоская, и представили конечный результат в этом интерактивном демо (контрольные точки можно двигать).
Изображение, которое вы видиет на этой странице (ниже) — это моя визуализация «Собаки» Пикассо, нарисованная как последовательность кривых Безье. Думаю, что сходство вполне убедительное.
«Собака» Пикассо, собранная из последовательности девяти кривых Безье.
Хотя сам рисунок изобрели не мы (и потому не можем поставить под ним свою подпись), мы смогли представить его как последовательность кривых Безье. Можно только назвать их художественной работой. Здесь мы свели представление к одному файлу: первая строка — это размер холста, а каждая последующая строка представляет кубическую кривую Безье. Комментарии добавлены для лучшей читаемости.
![](https://jeremykun.files.wordpress.com/2013/05/bezier-dog-for-web.png)
«Собака», Джереми Кун, 2013 год.
Стандартизация кажется мне важной, поэтому мы определим новый тип файла ".bezier", который будет иметь показанный выше формат:
int int
(int) curve
(int) curve
...
Здесь первые два целых числа определяют размер холста, первое (необязательное) целое число в каждой строке задаёт ширину линии, а
curve
имеет вид[int,int] [int,int] ... [int,int]
Если int в начале строки отсутствует, то линии задаётся ширина в три пикселя.
В целом, файл .bezier может задавать кривую с произвольным количеством контрольных точек, однако представленный выше код не отрисовывает их в общем виде. В качестве упражнения попробуйте написать программу, которая получает на входе файл .bezier, а на выходе создаёт изображение рисунка. Для этого потребуется расширить представленный выше алгоритм, чтобы он мог рисовать произвольные кривые Безье, циклически производя вычисления средних точек и отслеживая те из них, которые оказываются конечным подразделением. Или же можно написать программу, получающую на входе файл .bezier только с кубическими кривыми Безье, а на выходе выдающую файл SVG рисунка (SVG поддерживает только кубические кривые Безье). То есть файл .bezier является упрощением (меньше возможностей) и расширением (кривые Безье произвольной степени) файла SVG.
Мы не так сильно углублялись в теорию кривых Безье, как могли бы. Если вы хотите изучить тему глубже (и с использованием матанализа), то см. этот длинный вводный курс. В нём содержится практически всё, что нужно знать о кривых Безье, а также представлены написанные на Processing интерактивные демо.
Искусство низкой сложности
У того, что мы сделали с «Собакой» Пикассо, есть некое философское значение. Ранее в этом блоге мы исследовали идею искусства низкой сложности, и здесь она полностью применима. Основная мысль заключается в том, что «красивое» искусство имеет описание малой длины; если более формально, то «сложность» объекта (представленного в тексте) — это длина самой короткой программы, дающей на выходе этот объект при отсутствии входных данных. Подробнее об этом можно прочитать в нашем введении в колмогоровскую сложность. Тот факт, что мы можем описать линейные рисунки Пикассо малым числом кривых Безье (и относительно короткой программой, дающей на выходе кривые Безье), должен быть глубоким заявлением о красоте самого искусства. Очевидно, что такой взгляд очень субъективен, но у него есть свои сторонники.
Сегодня существует интерес к генерируемому компьютером искусству. Например, в этих недавних соревнованиях по программированию (статья на нидерландском) участникам дали задание сгенерировать рисунок, напоминающий работу Пита Мондриана. Идея заключалась в том, что чем элегантнее алгоритм, тем выше будет его оценка. Для генерации работ Мондриана победитель использовал хэши MD5, и есть ещё множество других впечатляющих примеров (по ссылке выше представлена галерея готовых работ).
В предыдущем посте об искусстве низкой сложности мы исследовали возможность представления всех изображений в системе координат, в которой используются окружности с закрашенным внутренним пространством. Но очевидно, что в такой системе координат нельзя представить «Собаку» с очень низкой сложностью. Похоже, что кривые Безье — это гораздо более естественные системы координат. Небольшие усовершенствования, включающие в себя длину линий и небольшие искажения, не влияют на конечную сложность. Кубическую кривую Безье можно описать любым множество из четырёх точек, а для более «запутанных» описаний (с повышенной сложностью) требуется большее количество точек. Кривые Безье можно произвольно масштабировать, и это не изменит значительно сложность кривой (несмотря на то, что масштабирование на многие порядки величины добавит увеличение сложности с логарифмическим множителем, оно довольно мало). Кривые с большой шириной линий немного сложнее, чем с малой шириной, а для представления множества мелких острых изгибов требуется больше кривых, чем для длинных и плавных дуг.
Недостатком является сложность представления в виде кривой Безье окружности. На самом деле, точно это сделать невозможно. Несмотря на простоту этого объекта (он даже задаётся как единственный многочлен, хотя и с двумя переменными), лучшее, что можно с ним сделать — аппроксимировать его. То же относится и к эллипсам. На самом деле есть способы обхода этой проблемы (концепция рациональных кривых Безье, которые являются частными многочленов), но они добавляют в алгоритм отрисовки неотъемлемую сложность, а аппроксимации с использованием обычных кривых Безье выглядят достаточно хорошо.
Итак, мы определим сложность рисунка как количество битов в виде файла .bezier (комментарии при вычислениях не учитываются).
Настоящей наградой, которую мы ещё исследуем, будет нахождение способа автоматической генерации искусства. То есть реализации одной из двух возможностей:
- Задав что-то вроде случайного начального числа (seed), написать программу, создающую псевдослучайный линейный рисунок.
- Задав рисунок, создать изображение .bezier, точно воспроизводящее рисунок как линейный рисунок.
Мы попробуем исследовать эти возможности в последующем посте. Для этого могут потребоваться какие-нибудь алгоритмы локального поиска, генетические алгоритмы или другие способы.