Кривая Безье

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

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

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

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

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

Определение[править | править код]

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

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

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

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

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

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

Замечания[править | править код]

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

Виды кривых Безье[править | править код]

Линейные кривые[править | править код]

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

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

Квадратичные кривые[править | править код]

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

${\displaystyle \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-файлах.

${\displaystyle 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}$

${\displaystyle 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}}$

${\displaystyle 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) описывается следующим уравнением:

${\displaystyle \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₃.

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

${\displaystyle \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}}}$,

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

${\displaystyle \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)^[1], 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₁ и описывает квадратичную кривую Безье.

Кривые высших степеней[править | править код]

Для построения кривых высших порядков соответственно требуется больше промежуточных точек. Для кубической кривой это промежуточные точки Q₀, Q₁ и Q₂, описывающие линейные кривые, а также точки R₀ и R₁, которые описывают квадратичные кривые: более простое уравнение ${\displaystyle {\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}}}}$.

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

Свойства кривой Безье[править | править код]

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

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

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

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

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

Квадратичная кривая Безье с координатами ${\displaystyle (x_{0};y_{0}),\,(x_{1};y_{1}),\,(x_{2};y_{2})}$ преобразовывается в кубическую кривую Безье с координатами ${\displaystyle (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})}$.

Уровень дискретизации Кривых Безье^[2][править | править код]

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

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

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

${\displaystyle \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}$

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

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

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

${\displaystyle 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}}}$

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

${\displaystyle {\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}$

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

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

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

${\displaystyle \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