Что такое кривые безье
Интерполяция: рисуем плавные графики с помощью кривых Безье
Доброго времени суток, харбачитатель.
В этой статье мне хотелось бы рассказать об одном придуманном когда-то алгоритме (или скорее всего — переизобретённом велосипеде) построения плавного графика по заданным точкам, используя кривые Безье. Статья была написана под влиянием вот этой статьи и очень полезного комментария товарища lany, за что им отдельное спасибо.
Постановка задачи
Есть массив Y-ков точек, расположенных равномерно по оси X. Нужно получить плавный график, который проходит через все заданные точки. Пример на рисунке ниже:
Всех, кому интересно, прошу под кат.
Существует ряд стандартных решений для проведения плавной кривой через точки (по этому поводу много интересного написано в уже упомянутой статье) таких, как например, интерполяции сплайнами. Когда на третьем курсе был придуман этот алгоритм, слово «интерполяция» вселяло в меня ужас, а гугление по запросу «сглаживание графиков» не давало посильных пониманию результатов. Но как-то я дошел до кривых Безье и уж очень они мне понравились. Рисует быстро, алгоритм интуитивно понятный… Что еще надо для счастья. Ну и как-то понеслось.
Основная идея
Таким образом получается, что задача сводится к поиску прямой (B1C1) и, собственно, опорных точек B1 и C1, по которым мы потом будем строить кривые Безье.
Поиск прямой
Как известно, прямая на плоскости выражается формулой y=kx+b, где k — тангенс угла наклона прямой к оси Х, а b — «высота» пересечения прямой и оси Y.
Поиск коэффициента k
Под квадратными скобками подразумевается длинна отрезка (не хотел использовать вертикальные прямые — надеюсь, что читатель меня простит)
Получаем, что:
И так, k мы нашли. Забегая наперед скажу, что b нам при расчетах не пригодится. Приступим к поиску опорных точек.
Ищем опорные точки
Из тригонометрии мы помним, что:
Если мы принимаем [AC1] равным половине шага по X между основным точками графика (точками B и A, A и C, т.д.), то:
К приятному!
Кривые Безье
Кривые Безье используются в компьютерной графике для рисования плавных изгибов, в CSS-анимации и много где ещё.
Это очень простая вещь, которую стоит изучить один раз, а затем чувствовать себя комфортно в мире векторной графики и продвинутых анимаций.
Опорные точки
Кривая Безье задаётся опорными точками.
Их может быть две, три, четыре или больше. Например:
Если вы посмотрите внимательно на эти кривые, то «на глазок» заметите:
Точки не всегда на кривой. Это совершенно нормально, как именно строится кривая мы рассмотрим чуть позже.
Степень кривой равна числу точек минус один. Для двух точек – это линейная кривая (т.е. прямая), для трёх точек – квадратическая кривая (парабола), для четырёх – кубическая.
Кривая всегда находится внутри выпуклой оболочки, образованной опорными точками:
Благодаря последнему свойству в компьютерной графике можно оптимизировать проверку пересечения двух кривых. Если их выпуклые оболочки не пересекаются, то и кривые тоже не пересекутся. Таким образом, проверка пересечения выпуклых оболочек в первую очередь может дать быстрый ответ на вопрос о наличии пересечения. Проверить пересечение или выпуклые оболочки гораздо проще, потому что это прямоугольники, треугольники и т.д. (см. рисунок выше), гораздо более простые фигуры, чем кривая.
Основная ценность кривых Безье для рисования в том, что, двигая точки, кривую можно менять, причём кривая при этом меняется интуитивно понятным образом.
Попробуйте двигать точки мышью в примере ниже:
Как можно заметить, кривая натянута по касательным 1 → 2 и 3 → 4.
После небольшой практики становится понятно, как расположить точки, чтобы получить нужную форму. А, соединяя несколько кривых, можно получить практически что угодно.
Вот некоторые примеры:
Алгоритм «де Кастельжо»
Есть математическая формула для кривых Безье, но давайте рассмотрим её чуть позже, потому что Алгоритм де Кастельжо идентичен математическому определению кривой и наглядно показывает, как она строится.
Рассмотрим его на примере трёх точек (точки 1,2 и 3 можно двигать). Нажатие на кнопку «play» запустит демонстрацию.
Построение кривой Безье с 3 точками по «алгоритму де Кастельжо»:
Для каждого из этих значений t :
Например, при t=0 – точки будут в начале, при t=0.25 – на расстоянии в 25% от начала отрезка, при t=0.5 – 50% (на середине), при t=1 – в конце отрезков.
Был описан процесс для построения по трём точкам. Но то же самое происходит и с четырьмя точками.
Демо для четырёх точек (точки можно двигать):
Алгоритм для 4 точек:
Точки по порядку соединяются отрезками: 1 → 2, 2 → 3, 3 → 4. Получается три коричневых отрезка.
Для t на отрезке от 0 до 1 :
Эти точки вместе описывают кривую.
Алгоритм является рекурсивным и может быть обобщён на любое количество контрольных точек.
Дано N контрольных точек:
Эти точки образуют кривую.
Запускайте и приостанавливайте примеры, чтобы ясно увидеть отрезки и то, как строится кривая.
Кривая, которая выглядит как y=1/t :
Зигзагообразные контрольные точки тоже работают нормально:
Создание петли возможно:
Негладкая кривая Безье (да, это тоже возможно):
Если в описании алгоритма есть что-то непонятное, посмотрите «живые» примеры выше, они наглядно показывают, как строится кривая.
Поскольку алгоритм является рекурсивным, мы можем построить кривые Безье любого порядка, используя 5, 6 или более контрольных точек. Но на практике много точек не так полезны. Обычно мы берём 2-3 точки, а для сложных линий склеиваем несколько кривых. Это проще для разработки и расчёта.
Для задания кривой Безье используются контрольные точки. Как видим, они не находятся на кривой, кроме первой и последней.
Иногда перед нами стоит другая задача: нарисовать кривую через несколько точек, чтобы все они были на одной гладкой кривой. Эта задача называется интерполяцией, и она за рамками нашего изложения.
Для таких кривых существуют математические формулы, например, полином Лагранжа. В компьютерной графике сплайн-интерполяция часто используется для построения плавных кривых, соединяющих множество точек.
Математика
Кривая Безье может быть описана с помощью математической формулы.
Как мы видели, на самом деле нет необходимости её знать, большинство людей просто рисуют кривую, перемещая точки с помощью мыши. Но если вы увлекаетесь математикой – вот она.
Формула для 2-х точечной кривой:
Для 3 контрольных точек:
Для 4 контрольных точек:
Вместо x1, y1, x2, y2, x3, y3 мы должны поместить координаты 3 контрольных точек, а затем при перемещении t от 0 до 1 для каждого значения t мы получим (x,y) кривой.
Итого
Кривые Безье задаются опорными точками.
Мы рассмотрели два определения кривых:
Их удобство в том, что:
Кривые Безье. Немного о пересечениях и как можно проще
Вы сталкивались когда-нибудь с построением (непрерывного) пути обхода кривой на плоскости, заданной отрезками и кривыми Безье?
Вроде бы не сильно сложная задача: состыковать отрезки кривых в один путь и обойти его «не отрывая пера». Замкнутая кривая обходится в одном направлении, ответвления — в прямом и обратном, начало и конец в одном узле.
Всё было хорошо, пока из-под рук дизайнеров не стали вылезать монструозные пути, где отдельные кривые могли пересекаться или не точно состыковываться. Объяснение было предельно простым — визуально они все лежат как надо, а для станка, который этот путь будет обходить, такие отклонения незаметны.
Вооружившись знанием о величине максимально допустимого отклонения, я приступил к исследованию, результатами которого хочу поделиться.
Первое что я сделал — это разобрался как на сегодняшний день (октябрь 2020) обстоят дела с поиском точек пересечения кривых. То ли я не там искал, то ли не то спрашивал, но найти простого решения не получилось. Хотя, идея с результантом пары полиномов довольно занимательна. Много разных алгоритмов связанных с кривыми Безье собрано здесь.
Что не понравилось в известных способах и что точно не хочется делать, так это численно искать корни полиномов, или даже решать квадратичные уравнения. Очень не хочется исследовать кривые на экстремумы. Да и вообще, хотелось бы избежать деления, возведения в степень и всего того, что может привести к неопределённому поведению.
Если пытаться продолжить кривую, то не факт что она вообще пересечётся с другой кривой, хотя они находятся достаточно близко
Итак, с чем придётся работать.
Для Point определены операторы сложения, вычитания, умножения на скаляр, скалярного умножения.
Задана величина R допустимого отклонения точек.
Кривые заданы массивами опорных (контрольных) точек std::vector
Почти совпадающие кривые следует отмечать и, по возможности, удалять, например, если это забытый дубликат (копипаста — это зло).
Первое, что точно понадобиться, это простой способ вычисления значения параметрической кривой. (Простой в смысле реализации и читабельности):
Оставлять функцию в таком виде для постоянного использования не стоит — лучше спрятать её подальше, а пользоваться такой:
Здесь, curve — контейнер для опорных точек: для отрезка их две, для кривой Безье три или четыре или более.
Второе — точки надо как-то сравнивать, с учётом R :
Для поиска точек пересечения пары кривых я воспользовался идеей деления каждой кривой на две до тех пор пока есть пересечение области значений этих кривых. А чтобы не заморачиваться с экстремумами и интервалами монотонности, использовал тот факт, что кривая Безье ограничена выпуклым многоугольником, вершинами которого являются опорные точки кривой. Или даже ещё проще — достаточно ограничивающего эти точки прямоугольника:
Алгоритм поиска рекурсивный и достаточно простой
Эту функцию тоже лучше спрятать куда подальше, а для получения всех опорных точек воспользоваться этой:
Кривые Безье
Материал на этой странице устарел, поэтому скрыт из оглавления сайта.
Более новая информация по этой теме находится на странице https://learn.javascript.ru/bezier-curve.
Кривые Безье используются в компьютерной графике для рисования плавных изгибов, в CSS-анимации и много где ещё.
Несмотря на «умное» название – это очень простая штука.
В принципе, можно создавать анимацию и без знания кривых Безье, но стоит один раз изучить эту тему хотя бы для того, чтобы в дальнейшем с комфортом пользоваться этим замечательным инструментом. Тем более что в мире векторной графики и продвинутых анимаций без них никак.
Виды кривых Безье
Кривая Безье задаётся опорными точками.
Их может быть две, три, четыре или больше. Например:
Если вы посмотрите внимательно на эти кривые, то «на глазок» заметите:
Точки не всегда на кривой. Это совершенно нормально, как именно строится кривая мы рассмотрим чуть позже.
Степень кривой равна числу точек минус один. Для двух точек – это линейная кривая (т.е. прямая), для трёх точек – квадратическая кривая (парабола), для четырёх – кубическая.
Кривая всегда находится внутри выпуклой оболочки, образованной опорными точками:
Благодаря последнему свойству в компьютерной графике можно оптимизировать проверку пересечений двух кривых. Если их выпуклые оболочки не пересекаются, то и кривые тоже не пересекутся.
Основная ценность кривых Безье для рисования – в том, что, двигая точки, кривую можно менять, причём кривая при этом меняется интуитивно понятным образом.
Попробуйте двигать точки мышью в примере ниже:
Как можно заметить, кривая натянута по касательным 1 → 2 и 3 → 4.
После небольшой практики становится понятно, как расположить точки, чтобы получить нужную форму. А, соединяя несколько кривых, можно получить практически что угодно.
Вот некоторые примеры:
Математика
У кривых Безье есть математическая формула.
Как мы увидим далее, для пользования кривыми Безье знать её нет особенной необходимости, но для полноты картины – вот она.
Координаты кривой описываются в зависимости от параметра t⋲[0,1]
Эти уравнения векторные, то есть для каждой из координат:
Впрочем, это чересчур наукообразно, не очень понятно, почему кривые именно такие, и как зависят от опорных точек. С этим нам поможет разобраться другой, более наглядный алгоритм.
Рисование «де Кастельжо»
Метод де Кастельжо идентичен математическому определению кривой и наглядно показывает, как она строится.
Посмотрим его на примере трёх точек (точки можно двигать). Нажатие на кнопку «play» запустит демонстрацию.
Алгоритм построения кривой по «методу де Кастельжо»:
Для каждого из этих значений t :
На каждом из коричневых отрезков берётся точка, находящаяся от начала на расстоянии от 0 до t пропорционально длине. Так как коричневых отрезков – два, то и точек две штуки.
Например, при t=0 – точки будут в начале, при t=0.25 – на расстоянии в 25% от начала отрезка, при t=0.5 – 50%(на середине), при t=1 – в конце отрезков.
Это был процесс для построения по трём точкам. Но то же самое происходит и с четырьмя точками.
Демо для четырёх точек (точки можно двигать):
Нажмите на кнопку «play» в примере выше, чтобы увидеть это в действии.
Постигая кривые Безье
Кривые Безье — это способ определения кривой по опорным точкам.
Для наглядности можно рассматривать их как график передвижения точки от начала до конца маршрута в зависимости от времени движения.
Время изменяется от 0 до 1 (до 100%). То есть мы изначально знаем время, за которое нужно переместиться из начальной точки (P0) в конечную (Pn) (конкретная величина не имеет значения). На основании этого времени можно вычислить точную траекторию — по формулам.
Берем все время за 100% (или за единицу). В момент 0 (0%) точка находится в точке P0, в момент 1 (100%) – в точке Pn. Положение точки в любой момент между этими моментами можно вычислить по формуле.
Порядок кривой всегда на 1 меньше количества контрольных точек. Рассмотрим построение пошагово, начиная с самой простой кривой.
Кривая Безье первого порядка
Простейшая кривая Безье — это обычная линия. Порядок первый – значит, контрольных точек две. Ее академическое уравнение выглядит так:
Разберем на простейшем примере. Пусть:
Сразу же проверим формулу.
При t = 0 (в начальный момент времени) должна получиться точка P0, а при t = 1 должна получиться точка P1.
А теперь найдем несколько точек между началом и концом. Тут используется сложение и умножение векторов, но в данном случае все интуитивно понятно:
Все полученные точки лежат на одной прямой – это и есть кривая Безье первого порядка.
Время идет, точка движется от старта к финишу. И в любой момент времени мы точно знаем, где она находится.
Кривые Безье второго порядка и больше
В определении кривых Безье выше первого порядка кроме начала и конца появляются дополнительные опорные точки, смысл которых сложно понять с первого захода.
Непосредственно через них кривая не проходит, так зачем же они нужны?
На самом деле эти точки определяют направление движения (направление изгиба кривой) и крутизну этого изгиба.
Квадратичная кривая
Кривая Безье второго порядка, или квадратичная, задается тремя контрольными точками:
Маленький спойлер: кривая Безье второго порядка имеет форму параболы (не обязательно симметричной).
Формула у нее вот такая:
Проверим, что в начале и конце движения мы окажемся в точках P0 и P2 соответственно:
Найдем, где будет точка через половину времени t (0.5):
B(0.5) = 0.25*P0 + 0.5*P1 + 0.25*P2 = (-0.25; 0) + (0; 1) + (0.25; 0) = (0; 1)
Если найти еще несколько точек, вырисуется ровная парабола. Так, в общем, и было задумано для простоты вычислений и визуальной ясности.
Рекурсивность кривых Безье
Волшебство кривых Безье заключается в том, что они рекурсивны. То есть умея строить кривую первого порядка, мы можем построить и квадратичную кривую, даже не зная ее формулы.
Вернемся к предыдущему примеру:
Предположим, что мы не знаем, как построить кривую второго порядка между P0 и P2. Но мы можем построить простейшую кривую первого порядка между P0 и P1, а также между P1 и P2, пользуясь формулой:
Для каждого момента времени мы можем найти положение точки на каждой из этих кривых.
Например, в момент времени 0.25 соответствующие точки Q0 и Q1 будут в таких позициях:
Между этими точками тоже можно построить кривую первого порядка.
Магия заключается в том, что точка на этой кривой в момент времени t = 0.25 соответствует точке на искомой кривой второго порядка в этот же момент времени.
Распишем чуть подробнее.
Этот рекурсивный алгоритм построения кривой Безье носит имя Поля де Кастельжо.
Кубическая кривая
Кривая Безье третьего порядка, или кубическая кривая, определяется уже четырьмя опорными точками – началом, концом и двумя вспомогательными, через которые она не будет непосредственно проходить.
Две вспомогательные точки снова определяют направление и крутизну изгибов кривой.
Формула кубической кривой еще сложнее:
Вы можете попробовать эту кривую рассчитать самостоятельно.
Обратите внимание, ее тоже можно получить рекурсивно!
Найти точку кривой третьего порядка в момент времени t можно по следующему алгоритму:
Зачем все это нужно?
Круто, теперь мы умеем строить кривые Безье любого порядка, но зачем нам это нужно? Каково практическое применение этих построений?
Кривые Безье используются в описаниях шрифтов TrueType, в SVG, GIMP и других графических форматах, в 3D-графике. Они используются даже в CSS для описания плавности анимации.