Кривая Безье (Tjnfgx >y[,y)

Кривы́е Безье́ — типы кривых, предложенные в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Кастельжо из компании «Ситроен», где применялись для проектирования кузовов автомобилей.

Несмотря на то, что открытие де Кастельжо было сделано несколько ранее Безье (1959), его исследования не публиковались и скрывались компанией как производственная тайна до конца 1960-х.

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

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

Впоследствии это открытие стало одним из важнейших инструментов систем автоматизированного проектирования и программ компьютерной графики.

Определение

Пусть в пространстве $\mathbb {R} ^{m}$ размерности $m\geqslant 1$ над $\mathbb {R}$ задана последовательность контрольных точек $(\mathbf {P} _{0},\ldots ,\mathbf {P} _{n})$, где $n\geqslant 0$, а $\mathbf {P} _{k}=(x_{1,k},\ldots ,x_{m,k})$ для $k=0,\ldots ,n$.

Тогда множество $\left\{\mathbf {B} (t)|0\leqslant t\leqslant 1\right\}$ точек $\mathbf {B} (t)=(z_{1}(t),\ldots ,z_{m}(t))$ с координатами $(z_{j}(t))_{j=1,\ldots ,m}$, параметрически задаваемыми выражениями

$z_{j}(t)=\sum _{k=0}^{n}x_{j,k}b_{k,n}(t)\quad$ для $\quad 0\leqslant t\leqslant 1,\quad$ где $\quad j=1,\ldots ,m,\quad$ а $\quad b_{k,n}(t)={n \choose k}t^{k}(1-t)^{n-k}\quad$ для $\quad k=0,\ldots ,n$,

называется кривой Безье.

Многочлен $b_{k,n}(t)$ степени $n$ по параметру $t$ называется базисной функцией (соответствующей контрольной точке $\mathbf {P} _{k}$) кривой Безье или полиномом Бернштейна.

Здесь ${n \choose k}={\frac {n!}{k!(n-k)!}}$ — число сочетаний из $n$ по $k$.

Замечания

1. Кривая Безье, соответствующая как $(\mathbf {P} _{0})$ так и $(\mathbf {P} _{0},\mathbf {P} _{0},\ldots ,\mathbf {P} _{0})$, есть точка $\mathbf {P} _{0}$.
2. Кривая Безье, соответствующая паре $(\mathbf {P} _{0},\mathbf {P} _{1})$, то есть при $n=1$, есть (линейно) параметризованный отрезок, соединяющий точку $\mathbf {P} _{0}$ (при $t=0$) с точкой $\mathbf {P} _{1}$ (при $t=1$).
3. При любом порядке $n\geqslant 0$ кривая Безье содержит как точку $\mathbf {P} _{0}$ (это — образ параметра $t=0$), так и точку $\mathbf {P} _{n}$ (это — образ параметра $t=1$).
4. Кривая Безье (в общем случае, то есть если не выродилась в точку $\mathbf {P} _{0}$) ориентируема, поскольку является образом ориентированного отрезка $[0;1]$. Последовательностям контрольных точек $(\mathbf {P} _{0},\mathbf {P} _{1},\ldots ,\mathbf {P} _{n-1},\mathbf {P} _{n})$ и $(\mathbf {P} _{n},\mathbf {P} _{n-1},\ldots ,\mathbf {P} _{1},\mathbf {P} _{0})$ соответствуют кривые Безье, которые совпадают как множества точек, но имеют (в общем случае) противоположные ориентации.
5. Кривые Безье, соответствующие последовательностям контрольных точек $(\mathbf {P} _{0},\mathbf {P} _{1},\mathbf {P} _{2})$ и $(\mathbf {P} _{0},\mathbf {P} _{2},\mathbf {P} _{1})$, при $\mathbf {P} _{1}\neq \mathbf {P} _{2}$ не совпадают.
6. Если изменить $(x_{j,0},\ldots ,x_{j,n})$, то изменяется только $z_{j}(t)$.

Виды кривых Безье

Линейные кривые

Линейная кривая Безье

При n = 1 кривая представляет собой отрезок прямой линии, опорные точки P₀ и P₁ определяют его начало и конец. Кривая задаётся уравнением:

$\mathbf {B} (t)=(1-t)\mathbf {P} _{0}+t\mathbf {P} _{1}\quad t\in [0,1]$.

Квадратичные кривые

Квадратичная кривая Безье

Квадратичная кривая Безье (n = 2) задаётся тремя опорными точками: P₀, P₁ и P₂.

$\mathbf {B} (t)=(1-t)^{2}\mathbf {P} _{0}+2t(1-t)\mathbf {P} _{1}+t^{2}\mathbf {P} _{2},\quad t\in [0,1]$.

Квадратичные кривые Безье в составе сплайнов используются для описания формы символов в шрифтах TrueType и в SWF-файлах.

$t={\frac {\mathbf {P} _{0}-\mathbf {P} _{1}\pm {\sqrt {(\mathbf {P} _{0}-2\mathbf {P} _{1}+\mathbf {P} _{2})\mathbf {B} +\mathbf {P} _{1}^{2}-\mathbf {P} _{0}\mathbf {P} _{2}}}}{\mathbf {P} _{0}-2\mathbf {P} _{1}+\mathbf {P} _{2}}},\quad \mathbf {P} _{0}-2\mathbf {P} _{1}+\mathbf {P} _{2}\neq 0$

$t={\frac {\mathbf {B} -\mathbf {P} _{0}}{2(\mathbf {P} _{1}-\mathbf {P} _{0})}},\quad \mathbf {P} _{0}-2\mathbf {P} _{1}+\mathbf {P} _{2}=0,\quad \mathbf {P} _{0}\neq \mathbf {P} _{1}$

$t={\sqrt {\frac {\mathbf {B} -\mathbf {P} _{0}}{\mathbf {P} _{2}-\mathbf {P} _{1}}}},\quad \mathbf {P} _{0}=\mathbf {P} _{1}\neq \mathbf {P} _{2}$

Кубические кривые

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

В параметрической форме кубическая кривая Безье (n = 3) описывается следующим уравнением:

$\mathbf {B} (t)=(1-t)^{3}\mathbf {P} _{0}+3t(1-t)^{2}\mathbf {P} _{1}+3t^{2}(1-t)\mathbf {P} _{2}+t^{3}\mathbf {P} _{3},\quad t\in [0,1]$.

Четыре опорные точки P₀, P₁, P₂ и P₃, заданные в 2- или 3-мерном пространстве, определяют форму кривой.

Линия берёт начало из точки P₀, направляясь к P₁ и заканчивается в точке P₃, подходя к ней со стороны P₂. То есть, кривая не проходит через точки P₁ и P₂, они используются для указания её направления. Длина отрезка между P₀ и P₁ определяет, как скоро кривая повернёт к P₃.

В матричной форме кубическая кривая Безье записывается следующим образом:

$\mathbf {B} (t)={\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}\mathbf {M} _{B}{\begin{bmatrix}\mathbf {P} _{0}\\\mathbf {P} _{1}\\\mathbf {P} _{2}\\\mathbf {P} _{3}\end{bmatrix}}$,

где $\mathbf {M} _{B}$ называется базисной матрицей Безье:

$\mathbf {M} _{B}={\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&3&0&0\\1&0&0&0\end{bmatrix}}$

В современных графических системах и форматах, таких как PostScript (а также основанных на нём форматах Adobe Illustrator и Portable Document Format (PDF)), Scalable Vector Graphics (SVG), Metafont, CorelDraw и GIMP для представления криволинейных форм используются сплайны Безье, составленные из кубических кривых.

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

Линейные кривые

Параметр t в функции, описывающей линейный случай кривой Безье, определяет, где именно на расстоянии от P₀ до P₁ находится B(t). Например, при t = 0,25 значение функции B(t) соответствует четверти расстояния между точками P₀ и P₁. Параметр t изменяется от 0 до 1, а B(t) описывает отрезок прямой между точками P₀ и P₁.

Квадратичные кривые

Для построения квадратичных кривых Безье требуется выделение двух промежуточных точек Q₀ и Q₁ из условия, чтобы параметр t изменялся от 0 до 1:

• Точка Q₀ изменяется от P₀ до P₁ и описывает линейную кривую Безье.
• Точка Q₁ изменяется от P₁ до P₂ и также описывает линейную кривую Безье.
• Точка B изменяется от Q₀ до Q₁ и описывает квадратичную кривую Безье.

Построение квадратичной кривой Безье

Анимация t: [0;1]

Кривые высших степеней

Для построения кривых высших порядков соответственно требуется больше промежуточных точек. Для кубической кривой это промежуточные точки Q₀, Q₁ и Q₂, описывающие линейные кривые, а также точки R₀ и R₁, которые описывают квадратичные кривые: более простое уравнение ${\frac {P_{0}Q_{0}}{P_{0}P_{1}}}={\frac {Q_{1}P_{1}}{P_{1}P_{2}}}={\frac {BR_{0}}{R_{1}R_{0}}}$.

Построение кубической кривой Безье

Анимация t: [0;1]

Для кривых четвёртой степени это будут точки Q₀, Q₁, Q₂ и Q₃, описывающие линейные кривые, R₀, R₁ и R₂, которые описывают квадратичные кривые, а также точки S₀ и S₁, описывающие кубические кривые Безье:

Построение кривой Безье 4-й степени

Анимация t: [0;1]

Свойства кривой Безье

• непрерывность заполнения сегмента между начальной и конечной точками;
• кривая всегда располагается внутри фигуры, образованной линиями, соединяющими контрольные точки;
• при наличии только двух контрольных точек сегмент представляет собой прямую линию;
• прямая линия образуется при коллинеарном (на одной прямой) размещении управляющих точек;
• кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;
• масштабирование и изменение пропорций кривой Безье не нарушает её стабильности, поскольку с математической точки зрения она «аффинно инвариантна»;
• изменение координат хотя бы одной из точек ведет к изменению формы всей кривой Безье;
• любой частичный отрезок кривой Безье также является кривой Безье;
• степень (порядок) кривой всегда на одну ступень меньше числа контрольных точек. Например, при трёх контрольных точках форма кривой — парабола, так как парабола — кривая 2-го порядка;
• окружность не может быть описана параметрическим уравнением кривой Безье;
• невозможно создать параллельные кривые Безье, за исключением тривиальных случаев (прямые линии и совпадающие кривые), хотя существуют алгоритмы, строящие приближённую параллельную кривую Безье с приемлемой для практики точностью.

Применение в компьютерной графике

Основная статья: Компьютерная графика

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

Наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. Для построения сложных по форме линий отдельные кривые Безье могут быть последовательно соединены друг с другом в сплайн Безье. Для того, чтобы обеспечить гладкость линии в месте соединения двух кривых, три смежные опорные точки обеих кривых должны лежать на одной прямой. В программах векторной графики, например Adobe Illustrator или Inkscape, подобные фрагменты известны под названием «путей» (path), а в 3DS Max и подобных программах 3D-моделирования кривые Безье имеют название «сплайны».

Преобразование квадратичных кривых Безье в кубические

Квадратичная кривая Безье с координатами $(x_{0};y_{0}),\,(x_{1};y_{1}),\,(x_{2};y_{2})$ преобразовывается в кубическую кривую Безье с координатами $(x_{0};y_{0}),\,\left(x_{0}+{\frac {2\cdot (x_{1}-x_{0})}{3}};y_{0}+{\frac {2\cdot (y_{1}-y_{0})}{3}}\right),\,\left(x_{1}+{\frac {x_{2}-x_{1}}{3}};y_{1}+{\frac {y_{2}-y_{1}}{3}}\right),\,(x_{2};y_{2})$.

Уровень дискретизации Кривых Безье

Уровень дискретизации определяется следующим образом:

$|B_{next}-B_{prev}|=1$

, то есть каждая следующая точка должна отличаться от предыдущей на 1 (допустим пиксель). Причём, если задать $B$ следующим образом:

$\left\vert \sum _{k=0}^{n}{{\frac {n!}{k!\times (n-k)!}}\times t_{next}^{k}\times (1-t_{next})^{n-k}\times P_{k}}-\sum _{k=0}^{n}{{\frac {n!}{k!\times (n-k)!}}\times t_{prev}^{k}\times (1-t_{prev})^{n-k}\times P_{k}}\right\vert =1$

Через него можно вычислить $\Delta {t}$.

Решим это уравнение для кривых Безье первого порядка (линейных):

$B(t)=(1-t)\times P_{0}+t\times P_{1},0\leq t\leq 1$

$B(t)={\begin{cases}x=(1-t)\times P_{0_{x}}+t\times P_{1_{x}}\\y=(1-t)\times P_{0_{y}}+t\times P_{1_{y}}\end{cases}}$

Запишем разницу точек для одной оси:

${\left\vert P_{0}-t_{next}\times P_{0}+t_{next}\times P_{1}-P_{0}+t_{prev}\times P_{0}-t_{prev}\times P_{1}\right\vert }=1$

Вынесем общие множители за скобки:

${\left\vert t_{next}\times (P_{0}-P_{1})-t_{prev}\times (P_{0}-P_{1})\right\vert }=1$

Найдём $\Delta {t}$:

$\Delta {t}={\left\vert t_{next}-t_{prev}\right\vert }=\left\vert {\frac {1}{P_{0}-P_{1}}}\right\vert$

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

См. также

• Поверхность Безье
• NURBS
• B-сплайн
• Кривые

Литература

• Роджерс Д., Адамс Дж. Математические основы машинной графики. — М.: Мир, 2001.

Ссылки

• Wolfram Math World Bézier Curve (англ.)
• American Mathematical Society From Bézier to Bernstein (англ.)
• Кривые Безье в компьютерных играх [1] (рус.)
• Часы на кривых Безье (рус.)
• A Primer on Bézier Curves