Кривая Безье

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

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

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

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

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

ОпределениеПравить

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

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

$z_j(t)=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}{x}_{j,k}{b}_{k,n}(t)$$z_{j}(t)=\sum _{k=0}^{n}x_{j,k}b_{k,n}(t)\quad$  для $0⩽<!--\; ⩽\; -->t⩽<!--\; ⩽\; -->1,$$\quad 0\leqslant t\leqslant 1,\quad$  где $j=1,\dots <!--\; \dots \; -->,m,$$\quad j=1,\ldots ,m,\quad$  а $b_{k,n}(t)=(\genfrac{}{}{0ex}{}{n}{k})t^k(1-<!--\; -\; -->t{)}^{n-<!--\; -\; -->k}$$\quad b_{k,n}(t)={n \choose k}t^{k}(1-t)^{n-k}\quad$  для $k=0,\dots <!--\; \dots \; -->,n$$\quad k=0,\ldots ,n$ ,

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

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

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

ЗамечанияПравить

1. Кривая Безье, соответствующая как $({\mathbf{P}}_0)$$(\mathbf {P} _{0})$  так и $({\mathbf{P}}_0,{\mathbf{P}}_0,\dots <!--\; \dots \; -->,{\mathbf{P}}_0)$$(\mathbf {P} _{0},\mathbf {P} _{0},\ldots ,\mathbf {P} _{0})$ , есть точка ${\mathbf{P}}_0$$\mathbf {P} _{0}$ .
2. Кривая Безье, соответствующая паре $({\mathbf{P}}_0,{\mathbf{P}}_1)$$(\mathbf {P} _{0},\mathbf {P} _{1})$ , то есть, при $n=1$$n=1$ , есть (линейно) параметризованный отрезок, соединяющий точку ${\mathbf{P}}_0$$\mathbf {P} _{0}$  (при $t=0$$t=0$ ) с точкой ${\mathbf{P}}_1$$\mathbf {P} _{1}$  (при $t=1$$t=1$ ).
3. При любом порядке $n⩾<!--\; ⩾\; -->0$$n\geqslant 0$  кривая Безье содержит как точку ${\mathbf{P}}_0$$\mathbf {P} _{0}$  (это — образ параметра $t=0$$t = 0$ ), так и точку ${\mathbf{P}}_n$$\mathbf {P} _{n}$  (это — образ параметра $t=1$$t = 1$ ).
4. Кривая Безье (в общем случае, то есть, если не выродилась в точку ${\mathbf{P}}_0$$\mathbf {P} _{0}$ ) ориентируема, поскольку является образом ориентированного отрезка $[0;1]$$[0;1]$ . Последовательностям контрольных точек $({\mathbf{P}}_0,{\mathbf{P}}_1,\dots <!--\; \dots \; -->,{\mathbf{P}}_{n-<!--\; -\; -->1},{\mathbf{P}}_n)$$(\mathbf {P} _{0},\mathbf {P} _{1},\ldots ,\mathbf {P} _{n-1},\mathbf {P} _{n})$  и $({\mathbf{P}}_n,{\mathbf{P}}_{n-<!--\; -\; -->1},\dots <!--\; \dots \; -->,{\mathbf{P}}_1,{\mathbf{P}}_0)$$(\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} _{1},\mathbf {P} _{2})$  и $({\mathbf{P}}_0,{\mathbf{P}}_2,{\mathbf{P}}_1)$$(\mathbf {P} _{0},\mathbf {P} _{2},\mathbf {P} _{1})$ , при ${\mathbf{P}}_1\ne <!--\; \ne \; -->{\mathbf{P}}_2$$\mathbf {P} _{1}\neq \mathbf {P} _{2}$  не совпадают.
6. Если изменить $(x_{j,0},\dots <!--\; \dots \; -->,x_{j,n})$$(x_{j,0},\ldots ,x_{j,n})$ , то изменяется только $z_j(t)$$z_{j}(t)$ .

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

Линейные кривыеПравить

 

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

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

$\mathbf{B}(t)=(1-<!--\; -\; -->t){\mathbf{P}}_0+t{\mathbf{P}}_{1}t\in <!--\; \in \; -->[0,1]$${\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,t\in <!--\; \in \; -->[0,1]$${\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 <!--\; \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},{\mathbf{P}}_0-<!--\; -\; -->2{\mathbf{P}}_1+{\mathbf{P}}_2\ne <!--\; \ne \; -->0$$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)},{\mathbf{P}}_0-<!--\; -\; -->2{\mathbf{P}}_1+{\mathbf{P}}_2=0,{\mathbf{P}}_0\ne <!--\; \ne \; -->{\mathbf{P}}_1$$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}},{\mathbf{P}}_0={\mathbf{P}}_1\ne <!--\; \ne \; -->{\mathbf{P}}_2$$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,t\in <!--\; \in \; -->[0,1]$${\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}$  называется базисной матрицей Безье:

${\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{B{R}_0}{R_1{R}_0}$${\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}),\,(x_{1};y_{1}),\,(x_{2};y_{2})$  преобразовывается в кубическую кривую Безье с координатами $(x_0;y_0),\left(x_0+\frac{2\cdot <!--\; \cdot \; -->(x_1-<!--\; -\; -->x_0)}{3};y_0+\frac{2\cdot <!--\; \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)$$(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$$|B_{next}-B_{prev}|=1$ 

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

$\left|\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{n!}{k!\times <!--\; \times \; -->(n-<!--\; -\; -->k)!}\times <!--\; \times \; -->t_{next}^k\times <!--\; \times \; -->(1-<!--\; -\; -->t_{next}{)}^{n-<!--\; -\; -->k}\times <!--\; \times \; -->P_k-<!--\; -\; -->\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{n!}{k!\times <!--\; \times \; -->(n-<!--\; -\; -->k)!}\times <!--\; \times \; -->t_{prev}^k\times <!--\; \times \; -->(1-<!--\; -\; -->t_{prev}{)}^{n-<!--\; -\; -->k}\times <!--\; \times \; -->P_k\right|=1$$\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$ 

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

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

$B(t)=(1-<!--\; -\; -->t)\times <!--\; \times \; -->P_0+t\times <!--\; \times \; -->P_1,0\le <!--\; \le \; -->t\le <!--\; \le \; -->1$$B(t)=(1-t)\times P_{0}+t\times P_{1},0\leq t\leq 1$ 

$B(t)=\{\begin{array}{l}x=(1-<!--\; -\; -->t)\times <!--\; \times \; -->P_{0_x}+t\times <!--\; \times \; -->P_{1_x}\\ y=(1-<!--\; -\; -->t)\times <!--\; \times \; -->P_{0_y}+t\times <!--\; \times \; -->P_{1_y}\end{array}$$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|P_0-<!--\; -\; -->t_{next}\times <!--\; \times \; -->P_0+t_{next}\times <!--\; \times \; -->P_1-<!--\; -\; -->P_0+t_{prev}\times <!--\; \times \; -->P_0-<!--\; -\; -->t_{prev}\times <!--\; \times \; -->P_1\right|=1$${\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|t_{next}\times <!--\; \times \; -->(P_0-<!--\; -\; -->P_1)-<!--\; -\; -->t_{prev}\times <!--\; \times \; -->(P_0-<!--\; -\; -->P_1)\right|=1$${\left\vert t_{next}\times (P_{0}-P_{1})-t_{prev}\times (P_{0}-P_{1})\right\vert }=1$ 

Найдём $\mathrm{\Delta <!--\; \Delta \; -->}t$$\Delta {t}$ :

$\mathrm{\Delta <!--\; \Delta \; -->}t=\left|t_{next}-<!--\; -\; -->t_{prev}\right|=\left|\frac{1}{P_0-<!--\; -\; -->P_1}\right|$$\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