Постигая кривые Безье | CAT.IN.WEB

Кривые Безье — это способ определения кривой по опорным точкам.

Для наглядности можно рассматривать их как график передвижения точки от начала до конца маршрута в зависимости от времени движения.

Время изменяется от 0 до 1 (до 100%). То есть мы изначально знаем время, за которое нужно переместиться из начальной точки (P₀) в конечную (P_n) (конкретная величина не имеет значения). На основании этого времени можно вычислить точную траекторию — по формулам.

Берем все время за 100% (или за единицу). В момент 0 (0%) точка находится в точке P₀, в момент 1 (100%) – в точке P_n. Положение точки в любой момент между этими моментами можно вычислить по формуле.

Порядок кривой всегда на 1 меньше количества контрольных точек. Рассмотрим построение пошагово, начиная с самой простой кривой.

Кривая Безье первого порядка

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

B(t) = (1-t)*P₀ + t*P₁

А график — вот так:

Разберем на простейшем примере. Пусть:

• первая контрольная точка — P₀ имеет координаты (0; 0),
• вторая (и последняя) – P₁ – (5; 0).

Сразу же проверим формулу.

При t = 0 (в начальный момент времени) должна получиться точка P₀, а при t = 1 должна получиться точка P₁.

• B(0) = (1-0)*P₀ + 0*P₁ = P₀ — (0; 0)
• B(1) = (1-1)*P₀ + 1*P₁ = P₁ — (5; 0)

А теперь найдем несколько точек между началом и концом. Тут используется сложение и умножение векторов, но в данном случае все интуитивно понятно:

• B(0.1) = (1-0.1)*P0 + 0.1*P1 = 0.9*P0 + 0.1*P1 = 0.9*(0;0) + 0. 1*(5;0) = (0.5; 0)
• B(0.2) = (1-0.2)*P0 + 0.2*P1 = 0.8*P0 + 0.2*P1 = 0.8*(0;0) + 0.2*(5;0) = (1; 0)
• B(0.3) = (1-0.3)*P0 + 0.3*P1 = 0.7*P0 + 0.3*P1 = 0.7*(0;0) + 0.3*(5;0) = (1.5; 0)
• B(0.4) = (1-0.4)*P0 + 0.4*P1 = 0.6*P0 + 0.4*P1 = 0.6*(0;0) + 0.4*(5;0) = (2; 0)
• B(0.5) = (1-0.5)*P0 + 0.5*P1 = 0.5*P0 + 0.5*P1 = 0.5*(0;0) + 0.5*(5;0) = (2.5; 0)
• B(0.6) = (1-0.6)*P0 + 0.6*P1 = 0.4*P0 + 0.6*P1 = 0.4*(0;0) + 0.6*(5;0) = (3; 0)
• B(0.7) = (1-0.7)*P0 + 0.7*P1 = 0.3*P0 + 0.7*P1 = 0.3*(0;0) + 0.7*(5;0) = (3.5; 0)
• B(0.8) = (1-0.8)*P0 + 0.8*P1 = 0.2*P0 + 0.8*P1 = 0. 2*(0;0) + 0.8*(5;0) = (4; 0)
• B(0.9) = (1-0.9)*P0 + 0.9*P1 = 0.1*P0 + 0.9*P1 = 0.1*(0;0) + 0.9*(5;0) = (4.5; 0)

Все полученные точки лежат на одной прямой – это и есть кривая Безье первого порядка.

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

Кривые Безье второго порядка и больше

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

Непосредственно через них кривая не проходит, так зачем же они нужны?

На самом деле эти точки определяют направление движения (направление изгиба кривой) и крутизну этого изгиба.

Квадратичная кривая

Кривая Безье второго порядка, или квадратичная, задается тремя контрольными точками:

• P₀ – начало;
• P₂ – конец;
• P₁ – вспомогательная точка, определяющая изгиб кривой.

Маленький спойлер: кривая Безье второго порядка имеет форму параболы (не обязательно симметричной).

Формула у нее вот такая:

B(t) = (1 - t)2*P0 + 2t*(1 - t)*P1 + t2*P2

Проверим, что в начале и конце движения мы окажемся в точках P₀ и P₂ соответственно:

• B(0) = (1 — 0)² *P₀ + 2*0*(1 — 0) * P₁ + 0²*P₂ = P₀
• B(1) = (1 — 1)² *P₀ + 2*1*(1 — 1) * P₁ + 1²*P₂ = P₂

На примере:

• P₀ (-1; 0)
• P₂ (1; 0)
• опорная точка P₁ (0; 2):

Найдем, где будет точка через половину времени 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)

То есть на половине временного интервала мы окажемся в точке (0; 1).

Если найти еще несколько точек, вырисуется ровная парабола. Так, в общем, и было задумано для простоты вычислений и визуальной ясности.

Рекурсивность кривых Безье

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

Вернемся к предыдущему примеру:

• P₀ (-1; 0)
• P₂ (1; 0)
• опорная точка P₁ (0; 2):

Предположим, что мы не знаем, как построить кривую второго порядка между P₀ и P₂. Но мы можем построить простейшую кривую первого порядка между P₀ и P₁, а также между P₁ и P₂, пользуясь формулой:

B(t) = (1-t)*P0 + t*P1

Для каждого момента времени мы можем найти положение точки на каждой из этих кривых.

Например, в момент времени 0.25 соответствующие точки Q₀ и Q₁ будут в таких позициях:

Между этими точками тоже можно построить кривую первого порядка.

Магия заключается в том, что точка на этой кривой в момент времени t = 0.25 соответствует точке на искомой кривой второго порядка в этот же момент времени.

Распишем чуть подробнее.

Мы хотим найти точку на кривой второго порядка P₀-P₁1-P₂ в момент времени t.

• Этому моменту на кривой P₀-P₁ соответствует точка Q₀;
• А на кривой P₁-P₂ – точка Q₁.

Искомая точка – это точка на кривой Q₀-Q₁, соответствующая моменту времени t.

Этот рекурсивный алгоритм построения кривой Безье носит имя Поля де Кастельжо.

Кубическая кривая

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

Две вспомогательные точки снова определяют направление и крутизну изгибов кривой.

Формула кубической кривой еще сложнее:

B(t) = (1 - t)3*P0 + 3t*(1-t)2*P1 + 3t2*(1 - t)*P2 + t3*P3

Вы можете попробовать эту кривую рассчитать самостоятельно.

Обратите внимание, ее тоже можно получить рекурсивно!

Найти точку кривой третьего порядка в момент времени t можно по следующему алгоритму:

1. Строим кривые первого порядка P₀-P₁, P₁-P₂, P₂-P₃
2. Находим на них соответствующие t точки Q₀, Q₁, Q₂
3. Строим кривые первого порядка Q₀-Q₁ и Q₁-Q₂
4. Находим на них соответствующие t точки R₀ и R₁
5. Строим кривую первого порядка R₀-R₁
6. Находим на ней точку, соответствующую t.

Зачем все это нужно?

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

Кривые Безье используются в описаниях шрифтов TrueType, в SVG, GIMP и других графических форматах, в 3D-графике. Они используются даже в CSS для описания плавности анимации.

В общем, штука очень полезная.

вектор — Построение кривых Безье SVG

В SVG есть встроенная функция построения кривых Безье 2-ой и 3-ей степени, т.е. только по трем и четырем точкам. Нужно строить по произвольному кол-ву точек.

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

Поэтому хотелось бы объединить несколько кривых второй степени в одну большую.

Как это сделать? Желательно с готовым кодом.

P.S. Пишу векторную рисовалку в академических целях

• svg
• вектор

0

Приведу коды примеров сначала одиночной кривой Безье второго порядка, затем с присоединенной второй кривой и третий пример двух кривых с гарантированным гладким соединением.

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg version="1. 1"
     baseProfile="full"
     xmlns="http://www.w3.org/2000/svg"
     xmlns:xlink="http://www.w3.org/1999/xlink"
     xmlns:ev="http://www.w3.org/2001/xml-events"
	 viewBox="0 0 400 400" >
	  
	  <path d="M50,200 Q175,75 300,200" 
        />
	</svg>

2. Для соединения двух кривых к конечной точке первой кривой присоединяется начальная точка второй кривой. В этом случае координаты начальной точки второй кривой не указываются.

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg version="1.1"
     baseProfile="full"
     xmlns="http://www.w3.org/2000/svg"
     xmlns:xlink="http://www.w3.org/1999/xlink"
     xmlns:ev="http://www.w3.org/2001/xml-events"
	 viewBox="0 0 800 800" >
	  
	 <path d="M50,200 Q175,75 300,200 Q425,75 550,200" 
          />
	</svg>

3. Для гарантированного получения гладкого, без изломов соединения двух кривых применяется команда – (T) или (t) (для относительных координат).

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<svg version="1.1"
     baseProfile="full"
     xmlns="http://www.w3.org/2000/svg"
     xmlns:xlink="http://www.w3.org/1999/xlink"
     xmlns:ev="http://www.w3.org/2001/xml-events"
	 viewBox="0 0 800 800" >
	  
	 <path d="M50,200 Q175,75 300,200 T 550,200" 
      />
	</svg>

Далее можно присоединять сколько угодно кривых Безье.
Примеры кода взяты здесь

Ну, насколько я помню, чтобы кусочки между собой гладко состыковывались, должно выполнятся два правила:

1. Точка, в которой заканчивается один кусочек, должен совпадать с точкой, где начинается второй кусочек (ну, это очевидно).

2. Эта точка должна лежать на прямой между предыдущей и последующей опорными точками.

То есть, получается как-то так:

(Извиняюсь за качество, рисовал на скорую руку).

Готового кода нет, но, думаю, тут его не очень сложно будет написать.

2

Зарегистрируйтесь или войдите

Регистрация через Google

Регистрация через Facebook

Регистрация через почту

Отправить без регистрации

Почта

Необходима, но никому не показывается

Отправить без регистрации

Почта

Необходима, но никому не показывается

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Графика

— Ближайшая точка на кубической кривой Безье?

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

Посмотрите интерактивный пример здесь.

Нажмите, чтобы увеличить. 93*px_0 + …

Преобразуйте его в стандартный вид с четырьмя коэффициентами.

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

Расстояние от точки p до кривой B(t) можно рассчитать по теореме Пифагора.

Здесь a и b два измерения наших точек х и х . Это означает, что квадрат расстояния D(t) равен:

Сейчас я не вычисляю квадратный корень, потому что достаточно сравнить относительные квадраты расстояний. Все последующие уравнения относятся к расстоянию в квадрате .

Эта функция D(t) описывает расстояние между графиком и точками. Нас интересуют минимумы в диапазоне t в [0, 1] . Чтобы их найти, мы должны вывести функцию дважды. Первая производная функции расстояния представляет собой полином 5-го порядка:

Вторая производная:

График десмоса позволяет нам исследовать различные функции.

D(t) имеет свои локальные минимумы, где d'(t) = 0 и d»(t) >= 0 . Это означает, что мы должны найти t для d'(t) = 0′ .

^{черный : кривая Безье, зеленый : d(t), фиолетовый : d'(t), красный :d»(t)}

9 найти корни д'(т) . Я использую библиотеку numpy, которая принимает коэффициенты полинома.

 dcoeffs = np.stack([da, db, dc, dd, de, df])
корни = np.roots (dcoeffs)
 

Удалите мнимые корни (оставьте только действительные корни) и удалите все корни, которые < 0 или > 1 . С кубическим Безье, вероятно, останется около 0-3 корней.

Затем проверьте расстояния каждого |B(t) - pt| за каждые т в корнях . Также проверьте расстояния для B(0) и B(1) , поскольку начало и конец кривой Безье могут быть ближайшими точками (хотя они не являются локальными минимумами функции расстояния).

Вернуть ближайшую точку.

Прикрепляю класс для Безье в питоне. Проверьте ссылку github для примера использования. 92 из
# pt и кривая
# ближайшая(pt) возвращает точку на кривой
# который ближе всего к pt
# maxes(pt) строит кривую, используя matplotlib
класс Безье (объект):
exp3 = np.array([[3, 3], [2, 2], [1, 1], [0, 0]], dtype=np.float32)
exp3_1 = np.array([[[3, 3], [2, 2], [1, 1], [0, 0]]], dtype=np. 1 + d
#
# Коэффициенты имеют ту же размерность, что и контроль
# точки.
def create_coefficients (я):
очки = личные очки
a = - очки [0] + 3 * очки [1] - 3 * очки [2] + очки [3]
b = 3*баллы[0] - 6*баллы[1] + 3*баллы[2]
с = -3*баллы[0] + 3*баллы[1]
д = очки [0]
self.coeffs = np.stack([a, b, c, d]).reshape(-1, 4, 2)
# Возвращаем точку на кривой по параметру t.
защита в (я, т):
если тип (t) != np.ndarray:
т = np.массив (т)
pts = self.coeffs * np.power (t, self.exp3_1)
вернуть np.sum (pts, ось = 1)
# Возвращает ближайшее РАССТОЯНИЕ (в квадрате) между точкой pt
# и кривая.
Защитное расстояние2 (я, pt):
точки, расстояния, индекс = self.measure_distance(pt)
обратные расстояния[индекс]
# Возвращаем ближайшую POINT между точкой pt
# и кривая.
Ближайший по определению (я, pt):
точки, расстояния, индекс = self.measure_distance(pt)
точки возврата[индекс]
# Измерить расстояние^2 и ближайшую точку на кривой
# точка pt и кривая. 2
# 2 Получите корни D'(t). Это крайности
# D(t) и содержат ближайшие точки на неотсеченном
# изгиб. Сохраняйте только минимумы, проверяя,
# D''(roots) > 0 и отбросить мнимые корни.
# 3 Вычислите расстояния от точки до минимумов как
# а также начало и конец кривой и возврат
# индекс кратчайшего расстояния.
#
# Этот график десмоса является полезной визуализацией.
# https://www.desmos.com/calculator/ktglugn1ya
def мера_расстояния (я, pt):
коэфф = self.coeffs
# Это коэффициенты производных d/dx и d/(d/dx).
da = 6*np.sum(коэфф[0][0]*коэфф[0][0])
db = 10*np.sum(коэфф[0][0]*коэфф[0][1])
dc = 4*(np.sum(коэфф[0][1]*коэфф[0][1]) + 2*np.sum(коэфф[0][0]*коэфф[0][2]))
dd = 6*(np.sum(коэфф[0][0]*(коэфф[0][3]-pt)) + np.sum(коэфф[0][1]*коэфф[0][2]) )
de = 2*(np.sum(coeffs[0][2]*coeffs[0][2])) + 4*np.sum(coeffs[0][1]*(coeffs[0][3]- пт))
df = 2*np.sum(коэфф[0][2]*(коэфф[0][3]-pt))
дда = 5*да
ддб = 4*дб
ддц = 3*ддц
ддд = 2*дд
дде = де
dcoeffs = np. stack([da, db, dc, dd, de, df])
ddcoeffs = np.stack([dda, ddb, ddc, ddd, dde]).reshape(-1, 1)

# Вычисление реальных экстремумов путем получения корней первого
# производная функции расстояния.
экстремум = np_real_roots (dcoeffs)
# Удаляем корни, выходящие за границы обрезанного диапазона [0, 1].
# [будущая ссылка] https://stackoverflow.com/questions/47100903/удаление-каждого-третьего-элемента-тензора-в-тензорном потоке
dd_clip = (np.sum(ddcoeffs * np.power(extrema, self.exp4)) >= 0) & (extrema > 0) & (extrema < 1) минимумы = экстремумы[dd_clip] # Добавьте начальную и конечную позиции как возможные позиции. потенциалы = np.concatenate((минимумы, self.boundaries)) # Вычислить точки при возможных параметрах t и # получить индекс ближайшего точки = self.at (потенциалы. изменить форму (-1, 1, 1)) расстояния = np.sum (np.square (точки - pt), ось = 1) индекс = np.argmin (расстояния) точки возврата, расстояния, индекс # Наведите кривую на фигуру из библиотеки matplotlib.
# maxes ... оси фигуры matplotlib
заговор по определению (я, максимумы):
импортировать matplotlib.path как mpath
импортировать matplotlib.patches как mpatches
Путь = mpath.Путь
pp1 = mppatches.PathPatch(
Путь(собственные.точки, [Путь.MOVETO, Путь.КРИВАЯ4, Путь.КРИВАЯ4, Путь.КРИВАЯ4]),
fc="none")#, transform=ax.transData)
pp1.set_alpha(1)
pp1.set_color('#00cc00')
pp1.set_fill(ложь)
pp2 = mppatches.PathPatch(
Путь(собственные.точки, [Путь.MOVETO, Путь.LINETO, Путь.LINETO, Путь.LINETO]),
fc="none")#, transform=ax.transData)
pp2.set_alpha(0.2)
pp2.set_color('#666666')
pp2.set_fill(ложь)
maxes.scatter(*zip(*self.points), s=4, c=((0, 0,8, 1, 1), (0, 1, 0,5, 0,8), (0, 1, 0,5, 0,8),
(0, 0,8, 1, 1)))
maxes.add_patch(pp2)
maxes.add_patch (pp1)
# Обертка вокруг np.roots, но возвращает только реальный
# корни и игнорирование мнимых результатов.
def np_real_roots (коэффициенты, EPSILON = 1e-6):
r = np.roots (коэффициенты)
вернуть r.real[abs(r.imag) < EPSILON]

Кривая Безье. Поймите математику Безье… | by Omar Aflak

Понимание математики кривых Безье

Кривые Безье часто используются в компьютерной графике, часто для создания плавных кривых, и тем не менее они являются очень простым инструментом. Если вы когда-либо использовали Photoshop, вы, возможно, наткнулись на этот инструмент под названием «Якорь», где вы можете ставить опорные точки и рисовать с их помощью некоторые кривые… Да, это кривые Безье. Или, если вы использовали векторную графику, SVG, они тоже используют кривые Безье. Посмотрим, как это работает.

Учитывает N+1 баллы (P0,…, PN) называется Контрольные точки , . Безегеное, определяемое эти очки, определяется как:

EQ. 1

Где B(t) — полином Бернштейна, а:

экв. 2

Вы заметите, что этот многочлен Бернштейна очень похож на член k(th) в биномиальной формуле Ньютона:

экв. 3

На самом деле многочлен Бернштейна есть не что иное, как 9n = 1. Вот почему, если вы суммируете все Bi до n , вы получите 1 . В любом случае.

Квадратичная кривая Безье — это то, как мы называем кривую Безье с 3 контрольными точками, поскольку степень P(t) будет равна 2. Давайте рассчитаем кривую Безье с учетом 3 контрольных точек и исследуем некоторые свойства, которые мы можем найти! Помните, экв. 1 соответствует n+1 точек, поэтому в нашем случае n=2.

экв. 4

Имейте в виду, что P(t) возвращает не число, а точку на кривой. Теперь нам осталось выбрать три контрольные точки и оценить кривую в диапазоне [0, 1] . Мы можем сделать это в Python довольно легко.

Вы можете заметить, что кривая начинается и заканчивается в первой и последней контрольных точках. Этот результат будет верным для любого количества точек. Поскольку t находится в диапазоне от 0 до 1 , мы можем доказать это, оценив P(t) при t=0 и t=1 . Используя экв. 1 :

экв. 4 экв. 5

Поскольку кривая идет от P0 до P2 , в этом случае P1 полностью определяет форму кривой . Перемещаясь P1 вокруг вы можете кое-что заметить:

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

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

экв. 6

Итак, вся информация о квадратичной кривой Безье сжата в одну матрицу, М . Теперь мы можем захотеть найти коэффициенты этой матрицы, не выполняя все эти шаги и легко программируемым способом. Поскольку коэффициенты матрицы — это просто коэффициенты полинома перед каждым Pi , то, что мы ищем, — это расширенная форма полинома Бернштейна экв. 2 .

Еще одно: если мы разложим Bi(t) на , мы получим многочлен перед Pi , что соответствует i(му) столбцу в матрице. Однако это не очень удобно, и было бы проще программировать, если бы вместо этого мы могли получать строки. Тем не менее, вы можете заметить, что i (я) строка матрицы точно такая же, как перевернутый (n-i) (th) столбец , и коэффициенты перевернутого (n-i) (th) столбца есть не что иное, как коэффициенты B(n-i)(t) , взятые в убывающей степени t .