В данном разделе рассматриваются основные виды параметрических кривых и алгоритмы их растеризации. Параметрические кривые, а также поверхности, применяются для описания более сложных, чем плоские, форм. Они находят широкое применение в графическом и промышленном дизайне.
В этом разделе будут рассматриваться вопросы построения кривых по контрольным точкам. Нас будут интересовать две задачи:
Интерполяция - построение кривой, проходящей через контрольные точки и обладающей некими дополнительными свойствами (часто n -й степени гладкости имеет непрерывную производную n -ого порядка; такой класс кривых обозначается как Cn .
Аппроксимация - приближение кривой (не обязательно проходит точно через данные точки, но удовлетворяет некоторому заданному свойству относительно этих точек).
В настоящее время большее применение находят аппроксимирующие кривые, поэтому в данном разделе им уделяется большее внимание.
Сплайн - кусочный многочлен степени K с непрерывной производной степени K - 1 в точках соединения сегментов.
Далее нас будут интересовать самые распространенные
Понятие сплайна пришло из машиностроения, где сплайном называли гибкую линейку, закрепив которую в нужных местах, добивались плавной формы кривой, и затем чертили ее по этой линейке (см. рис. 4.1). Форма такой линейки, если ее рассматривать как функцию y(x), будет удовлетворять уравнению Эйлера-Бернулли:
где M(x) - момент изгиба вдоль линейки, E - модуль Юнга, зависящий от свойств материала рейки, I - момент инерции, определяемый формой кривой. Если мы фиксируем некоторые точки xi подпорками, то момент изгиба на каждом отрезке $$[x_i, x_{i+1}], i \in \overline{0,N - 1}$$ меняется по линейному закону: M(x) = Ax + B. Подставляя M в исходное уравнение получаем
Дважды интегрируя, получаем уравнение кривой на данном отрезке:
y(x) = ax3 + bx2 + cx + d.
(рис 4.1) СплайнТаким образом, форма физического сплайна описывается кусочным кубическим многочленом. Теперь рассмотрим задачу построения системы таких кубических многочленов для всего отрезка [x0, xN].
N отрезков имеем 4N коэффициентов: y(x) = aix3+bix2+cix + di для $$x \in [x_i, x_{i+1}], i \in \overline{0,N - 1}$$ ;2N уравнений;C1 в точках $$x_i, i \in \overline{1,N - 1}$$ дает N - 1 уравнений;C2 в точках $$x_i, i \in \overline{1,N - 1}$$ дает N - 1 уравнений.Итого, имеем 4N - 2 уравнения; для того чтобы система была определенной, необходимы еще 2 уравнения. Их можно вывести, например, из заданных значений производных на границах или из условия периодичности. При корректно заданных условиях линейная относительно $$\{a_i, b_i, c_i, d_i\}, i \in \overline{0,N - 1}$$ система имеет единственное решение. Подробнее см. в [8].
В настоящее время для
Наглядный метод построения этих кривых был предложен де Кастелье (de Casteljau) в 1959 году [26]. Метод де Кастелье основан на разбиении отрезков, соединяющих исходные точки в отношении t (значение параметра), а затем в рекурсивном повторении этого процесса для полученных отрезков:
Нижний индекс - номер точки, верхний индекс - уровень разбиения. Уравнение кривой n -ого порядка задается $$P(t) := P_0^n(t)$$.
Для примера построим кривую c 3 опорными точками (иногда они также называются контрольными ) (см. рис. 4.2).
(рис 4.2) Обозначим опорные точки как $$P_i, i \in \overline{0, 2}$$, начало кривой положим в точке $$P_0 (t = 0)$$, а конец - в точке $$P_2 (t = 1)$$ ; для каждого $$t \in [0, 1]$$ найдем точку $$P_0^2(t)$$:
$$P_0^1(t) = (1 - t)P_0 + tP_1, \\ P_1^1(t) = (1 - t)P_1 + tP_2, \\ P_0^2(t) = (1 - t)P_0^1(t) + tP_1^1(t) = \\ = {(1 - t)}^2P_0(t) + 2t(1 - t)P_1(t) + t^2P_2(t),$$таким образом, получим кривую второго порядка.
Теперь построим аналогичным методом кривую Безье с четырьмя опорными точками:
$$P_0^1 (t) = (1 - t)P_0 + tP_1, \\ P_1^1(t) = (1 - t)P_1 + tP_2, \\ P_2^1(t) = (1 - t)P_2 + tP_3,$$
(рис 4.3) Кривая Безье с четырьмя опорными точками$$P_0^2(t) = (1 - t)P_0^1(t) + tP_1^1(t) = \\
= {(1 - t)}^2P_0 + 2t(1 - t)P_1 + t^2P_2, \\
P_1^2(t) = (1 - t)P_1^1(t) + tP_2^1(t) = \\
= {(1 - t)}^2P_1 + 2t(1 - t)P_2 + t^2P_3, \\
P_0^3(t) = (1 - t)P_0^2(t) + tP_1^2(t) = \\
= {(1 - t)}^2P_0^1(t) + 2t(1 - t)P_1^1 (t) + t^2P_2^1(t) = \\
={(1 - t)}^3P_0 + 3t{(1 - t)}^2P_1 + 3t^2(1 - t)P_2 + t^3P_3.$$
Запишем общее аналитическое представление для кривой Безье с N + 1 опорной точкой:
$$B_i ^N(t)$$ называются базисными многочленами Бернштейна N - й степени (а также весовыми функциями Безье-Бернштейна). На рис. 4.4 и 4.5 изображены многочлены Бернштейна 3-й и 4-й степеней.
(рис 4.5) Базисные функции Бернштейна 3-й степени(рис 4.4) Базисные функции Бернштейна 4-й степени
Следствие. Если все опорные точки лежат на одной прямой, то кривая Безье вырождается в отрезок, соединяющий эти точки.
P0 и PN.1 меньше числа опорных точек.P0 и PN Замечание. Хотя все выкладки проводились в $$\mathbb{R}^2$$, аналогичные построения и свойства справедливы и в $$\mathbb{R}^n$$.
$$\{x = x(t), y = y(t)\}, t \in [0, 1]$$ (определяются по выражению (4.2)). Подберем шаг $$\Delta t$$ так, чтобы $$\Delta x = x(t + \Delta t) - x(t)$$ и $$\Delta y = y(t + \Delta t) - y(t) (t \in [0, 1])$$ были меньше размера стороны пикселя d (если мы работаем в пиксельных координатах, то это 1 ), т. е. мы не пропустим ни одного пикселя при таких приращениях. Т.к. $$\frac{dx}{dt}$$ и $$\frac{dy}{dt}$$ - многочлены, то, соответственно, легко найти максимумы их модулей Mx и My на отрезке [0, 1]. Положим M = max(Mx,My), тогда, взяв $$\Delta t = \frac{d}{M}$$, получим что смещения по x и по y при каждом шаге не превосходят длины стороны пикселя.
// x(t), y(t) заданы в пиксельных координатах => d = 1
// M - максимум модулей dx/dt и dy/dt на всем отрезке [0,1]
// round(x) - округляет x до ближайшего целого
dt = 1 / M;
t = 0;
while(t < 1)
{
x = x(t); // см. выражение 4.2
y = y(t); // см. выражение 4.2
plot( round(x) , round(y) );
t += dt;
}
Недостаток данного алгоритма состоит в том, что при малых смещениях по x и y много итераций проходит зря, т.к. происходит повторная закраска одних и тех же пикселей.
Предложен де Кастелье. Рассмотрим пример этого алгоритма для кривой 4-го порядка с опорными точками P0P1P2P3 (см. рис. 4.6). Если рассмотреть участок между P0 и $$P_0^4 (t_1), t_1 = \frac{1}{2}$$, то он может быть задан как кривая Безье с опорными точками $$P_0P_0^1(t_1)P_0^2(t_1)P_0^3(t_1)P_0^4(t_1), t_1 = \frac{1}{2}$$ (почему это так, подробнее см., например, в [28]).
Аналогичные рассуждения справедливы и для участка между $$P_0^4(t_1), t_1 = \frac{1}{2}$$ и P4. Будем применять этот алгоритм рекурсивно для левой и правой частей, пока кривая не выродится в прямую с точностью до пикселя, а это так или иначе (все точки попадут в один пиксель) произойдет.
P.
P1, . . . ,Pn.
// работаем в пиксельных координатах
// (размер пикселя равен 1x1)
// P0 - начальная точка кривой
// Pn - конечная точка кривой
DrawCurve(P0,P1, . . . ,Pn)
{
// Проверка на завершение
if( макс. длина ребра BBox(P0,P1, . . . , Pn) < 1 )
return;
if( P0,P1, . . . , Pn лежат на отрезке P0Pn
с точностью до пикселя )
{
Нарисовать отрезок P0Pn;
// (см. лекцию о растеризации отрезков)
return;
}
Найти P01,P02, . . . , P0{n-1} для t = 0,5;
// используя (4.1)
Найти P0n для t = 0,5; // используя (4.1)
Найти P1{n-1},P2{n-2}, . . . , P{n-1}1 для t = 0,5;
// используя (4.1)
plot(P0n);
// Нарисовать половинки (см. рис. 4.6)
DrawCurve( P0,P01, . . . , P0n);
DrawCurve( P0n,P1{n-1}, . . . , Pn);
}
(рис 4.6) Построение кривой Безье методом разбиения.Для построения кривых по большому множеству опорных точек пришлось бы использовать кривые Безье большого порядка, что привело бы к громоздким вычислениям; к тому же часто желательным является локальное влияние на форму кривой (для кривых Безье это не так). Поэтому чаще используют
Такие сплайны обладают свойством локальности влияния контрольных точек на форму кривой. Как и в случае интерполирующих сплайнов, будем искать сплайны определенной степени гладкости.
Для упрощения будем считать, что параметризация равномерная, т.е. длины отрезков, которые пробегает параметр на каждом из участков, равны. Для того чтобы рассмотреть условия на C1 и C2, необходимо найти производные кривых Безье:
где
$$\Delta^k(P_i) = \sum\limits_{j=0}^{k}(-1)^j \cdot C_j ^k \cdot P_{i+j}, \\ C_j ^k =\frac{k!}{j!(k - j)!}.$$Рассмотрим подробно случай кубических кривых Безье, которые являются самыми распространенными.
C1. Пусть заданы значения производных на концах ( d0 и d1 ), обозначим совпадающую последнюю контрольную точку предыдущей кривой и первую контрольную точку текущей как Pn:$$$ \frac{d}{dt}P^3(0) = 3(P_{n+1} - P_n) = d_0 \quad \Rightarrow \quad P_{n+1} = P_n + \frac{1}{3}d_0 \\ \frac{d}{dt}P^3(1) = 3(P_{n+3} - P_{n+2}) = d_1 \quad \Rightarrow \quad P_{n+2} = P_{n+3} - \frac{1}{3}d_1. $$$
Таким образом, для того чтобы в точках стыковки производные были равны (d0 = d1), необходимо, чтобы
(рис 4.7) Стыковка с требованием C1
C2:$$$\frac{d}{dt}P^3(0) = 3(P_{n+1}- Pn) = 3d_1, \\ \frac{d}{dt}P^3(1) = 3(P_n - P_{n-1}) = 3d_2, \\ \frac{d^2}{dt^2}P^3(0) = 6(P_{n+2} - 2P_{n+1} + P_n), \\ = 6((P_{n+2} - P_{n+1}) + (P_n - P_{n+1})) = 6\Delta_1, \\ \frac{d^2}{dt^2}P^3(1) = 6(P_n - 2P_{n-1} + P_{n-2}), \\ = 6((P_n - P_{n-1}) + (P_{n-2} - P_{n-1})) = 6\Delta_2. $$$
Из требования C1 в точках стыковки мы уже получили $$d =d_1 = d_2 \Leftrightarrow P_{n-1}P_n = P_nP_{n+1}$$. Далее, из требования C2 следует равенство $$\Delta = \Delta_1 = \Delta_2$$. Так как $$\Delta$$ получаются сложением соответствующих векторов по правилу параллелограмма, то $$P_{n-2}P_{n+2} \quad \| \quad P_{n-1}P_{n+1}$$ и, если обозначить точку
пересечения Pn-2Pn-1 и Pn+2Pn+1 как Dn, то получим, что Pn-1Pn+1 - средняя линия треугольника Pn-2DnPn+2. Распространяя эти рассуждения на все точки стыковки, получаем, что для задания формы такого сплайна достаточно задать точки Dk, где $$k = 3i, i \in \overline{1,N/3}$$, где N + 1 - число опорных точек, и краевые точки - P0 и PN (см. рис. 4.9 ).
Замечание. Для замкнутой кривой задание краевых точек не нужно.
(рис 4.8) Стыковка с требованием C2.
(рис 4.9) Связь между точками Dk для соседних сегментов.
Однако даже такие достаточно развитые средства аппроксимации кривыми Безье не позволяют построить окружность$$\left\{ \begin{array}{c}
x = \cos t \\
y = \sin t \\
\end{array} \right. ,$$
так как sin и cos для достаточно хорошего приближения требуют многочленов высокой степени. Поэтому вводится более широкий класс кривых, способ построения которых связан с представлением о проективном пространстве:
Пусть у нас есть пространственная кривая Безье P0P1 . . . PN в системе координат OXY w. Спроецируем все точки исходной кривой на плоскость w = 1, т.е.:
где
$$P_i = \left[ \begin{array}{c} w_i \cdot \tilde{P}_i \\ w_i \end{array} \right] = \left( \begin{array}{c} w_ix_i \\ w_iy_i \\ w_i \end{array} \right) \mbox{ (см. рис. 4.10.)}$$Полученная кривая, лежащая в плоскости w = 1, и называется рациональной двумерной кривой Безье. Аналогичным образом можно получать рациональные кривые Безье и в пространстве большего числа измерений.
$$\tilde{P}_i = \left( \begin{array}{c}
x_i \\
y_i
\end{array} \right)$$
будем называть опорными точками рациональной кривой Безье, а wi - весовыми функциями.
Рассмотрим пример представления окружности, составленной из 3-х рациональных кубических кривых Безье. Возьмем для примера один из сегментов (см. рис. 4.11). Положим $$w_0 = 1, w_1 = \frac{1}{2} , w_2 = 1$$, а
$$$\tilde{P}_0 = \left( \begin{array}{c} \frac{R}{2} \\ \frac{\sqrt{3}R}{2} \end{array} \right), \tilde{P}_1 = \left( \begin{array}{c} \frac{2R}{\sqrt{3}} \\ 0 \end{array} \right), \tilde{P}_2 = \left( \begin{array}{c} \frac{R}{2} \\ -\frac{\sqrt{3}R}{2} \end{array} \right), $$$где R - радиус окружности.
Итоговое изображение представлено на рис. 4.12.
(рис 4.10) Рациональная кривая Безье.Растеризовать такие кривые можно теми же двумя способами, что и для обыкновенных кривых Безье. При этом в алгоритме рекурсивного разбиения разбивается исходная кривая в проективном пространстве.
B-сплайны являются обобщением кривых Безье. Они также представимы в линейной комбинации контрольных точек. Пусть заданы порядок кривой n, потенциальное количество участков m, вектор узлов
и контрольные точки $$\{P_i\} , i = \overline{0,m + n - 1}$$. Если ti = ti+1 = . . . = ti+l и соответственно Pi = Pi+1 = . . . = Pi+l, то говорят об узле ti кратности l. Как правило, для кривой порядка n в начале и в конце ставятся узлы кратности n, так как при этом концы кривой будут совпадать с крайними контрольными точками.
(рис 4.12) Сегмент окружности, представленный рациональной кривой Безье.(рис 4.11) Изображение окружности.Формулы Кокса - де Бура (Cox - de Boor) рекурсивно определяют B-сплайн:
$$Pn(t) = \sum\limits_{i=0}^{m+n-1}b_{i,n}(t) \cdot P_i, \mbox{ где}$$ $$b_{j,0}(t) = { \left\{ \begin{array}{cc} 1, \text{если } t_{j-1} \le t < t_j, \\ 0, \text{в другом случае} \\ \end{array} \right. }; \\ b_{j,k}(t) = \frac{t-t_{j-1}}{t_{j+n-1}-t_{j-1}}b_{j,k-1}(t) + \frac{t_{j+n}- t}{t_{j+n}-t_j}b_{j+1,k-1}(t).$$Если узлы кратные, то в (4.3) возникают неопределенности вида $$\frac{0}{0}$$, которые по определению должны разрешаться как 0. Многочисленные полезные свойства этих кривых находятся за рамками данной книги. Подробную информацию можно найти в [28], [8].
Кратко остановимся только на вопросе растеризации данных кривых. Можно выделить три основных подхода.
Алгоритм де Бура
Для $$t \in [t_I , t_{I+1}), I \in \overline{n - 1,m+ n - 1}$$
$$P^n(t) := P_{I+1}^n(t), \mbox{ где} \\ P_I^0(t) = P_I ; \\ P_j^k(t) = \left(1 - \frac{t-t_{j-1}}{t_{j+n-k}-t_{j-1}}\right) \cdot P_{j-1}^{k-1}(t) + \frac{t-t_{j-1}}{t_{j+n-k}-t_{j-1}} \cdot P_j^{k-1}(t).$$Если узлы кратные, то в (4.4) также могут возникнуть неопределенности вида $$\frac{0}{0}$$, которые по определению должны разрешаться как 0.
[ti, ti+1] можно при помощи вставки узлов ti до тех пор пока их кратность не достигнет n. Новые контрольные точки B-сплайна, которые также будут контрольными точками для кривых Безье на каждом отрезке [ti, ti+1], будут получены в результате стандартной процедуры добавления узлов в B-сплайн (см. например, [28]).Самыми распространенными в геометрическом моделировании в настоящее время являются Неоднородные рациональные B-сплайны (англ. NURBS). Неоднородность означает, что промежутки между соседними узлами ti могут быть различными. Рациональные они в том же смысле, что и рациональные кривые Безье (см. раздел 4.2), т.е. проекция B-сплайна из проективного пространства. Это наиболее широкий из рассмотренных классов кривых.
Специфика данного курса не предполагает детального изучения математических свойств рассмотренных выше кривых; особенно это касается лишь кратко рассмотренных B-сплайнов. Всех интересующихся описанием этих вопросов, а также тех, кто хотел бы узнать более подробно о вышеизложенном материале, отсылаем к книгам [8], [28].
Также за рамками данной лекции остались кривые разбиения. О них можно узнать подробнее из [47].
В данном разделе рассматриваются основные виды параметрических кривых и алгоритмы их растеризации. Параметрические кривые, а также поверхности, применяются для описания более сложных, чем плоские, форм. Они находят широкое применение в графическом и промышленном дизайне.
В этом разделе будут рассматриваться вопросы построения кривых по контрольным точкам. Нас будут интересовать две задачи:
Интерполяция - построение кривой, проходящей через контрольные точки и обладающей некими дополнительными свойствами (часто n -й степени гладкости имеет непрерывную производную n -ого порядка; такой класс кривых обозначается как Cn .
Аппроксимация - приближение кривой (не обязательно проходит точно через данные точки, но удовлетворяет некоторому заданному свойству относительно этих точек).
В настоящее время большее применение находят аппроксимирующие кривые, поэтому в данном разделе им уделяется большее внимание.
Сплайн - кусочный многочлен степени K с непрерывной производной степени K - 1 в точках соединения сегментов.
Далее нас будут интересовать самые распространенные
Понятие сплайна пришло из машиностроения, где сплайном называли гибкую линейку, закрепив которую в нужных местах, добивались плавной формы кривой, и затем чертили ее по этой линейке (см. рис. 4.1). Форма такой линейки, если ее рассматривать как функцию y(x), будет удовлетворять уравнению Эйлера-Бернулли:
где M(x) - момент изгиба вдоль линейки, E - модуль Юнга, зависящий от свойств материала рейки, I - момент инерции, определяемый формой кривой. Если мы фиксируем некоторые точки xi подпорками, то момент изгиба на каждом отрезке $$[x_i, x_{i+1}], i \in \overline{0,N - 1}$$ меняется по линейному закону: M(x) = Ax + B. Подставляя M в исходное уравнение получаем
Дважды интегрируя, получаем уравнение кривой на данном отрезке:
y(x) = ax3 + bx2 + cx + d.
(рис 4.1) СплайнТаким образом, форма физического сплайна описывается кусочным кубическим многочленом. Теперь рассмотрим задачу построения системы таких кубических многочленов для всего отрезка [x0, xN].
N отрезков имеем 4N коэффициентов: y(x) = aix3+bix2+cix + di для $$x \in [x_i, x_{i+1}], i \in \overline{0,N - 1}$$ ;2N уравнений;C1 в точках $$x_i, i \in \overline{1,N - 1}$$ дает N - 1 уравнений;C2 в точках $$x_i, i \in \overline{1,N - 1}$$ дает N - 1 уравнений.Итого, имеем 4N - 2 уравнения; для того чтобы система была определенной, необходимы еще 2 уравнения. Их можно вывести, например, из заданных значений производных на границах или из условия периодичности. При корректно заданных условиях линейная относительно $$\{a_i, b_i, c_i, d_i\}, i \in \overline{0,N - 1}$$ система имеет единственное решение. Подробнее см. в [8].
В настоящее время для
Наглядный метод построения этих кривых был предложен де Кастелье (de Casteljau) в 1959 году [26]. Метод де Кастелье основан на разбиении отрезков, соединяющих исходные точки в отношении t (значение параметра), а затем в рекурсивном повторении этого процесса для полученных отрезков:
Нижний индекс - номер точки, верхний индекс - уровень разбиения. Уравнение кривой n -ого порядка задается $$P(t) := P_0^n(t)$$.
Для примера построим кривую c 3 опорными точками (иногда они также называются контрольными ) (см. рис. 4.2).
(рис 4.2) Обозначим опорные точки как $$P_i, i \in \overline{0, 2}$$, начало кривой положим в точке $$P_0 (t = 0)$$, а конец - в точке $$P_2 (t = 1)$$ ; для каждого $$t \in [0, 1]$$ найдем точку $$P_0^2(t)$$:
$$P_0^1(t) = (1 - t)P_0 + tP_1, \\ P_1^1(t) = (1 - t)P_1 + tP_2, \\ P_0^2(t) = (1 - t)P_0^1(t) + tP_1^1(t) = \\ = {(1 - t)}^2P_0(t) + 2t(1 - t)P_1(t) + t^2P_2(t),$$таким образом, получим кривую второго порядка.
Теперь построим аналогичным методом кривую Безье с четырьмя опорными точками:
$$P_0^1 (t) = (1 - t)P_0 + tP_1, \\ P_1^1(t) = (1 - t)P_1 + tP_2, \\ P_2^1(t) = (1 - t)P_2 + tP_3,$$(рис 4.3) Кривая Безье с четырьмя опорными точками$$P_0^2(t) = (1 - t)P_0^1(t) + tP_1^1(t) = \\
= {(1 - t)}^2P_0 + 2t(1 - t)P_1 + t^2P_2, \\
P_1^2(t) = (1 - t)P_1^1(t) + tP_2^1(t) = \\
= {(1 - t)}^2P_1 + 2t(1 - t)P_2 + t^2P_3, \\
P_0^3(t) = (1 - t)P_0^2(t) + tP_1^2(t) = \\
= {(1 - t)}^2P_0^1(t) + 2t(1 - t)P_1^1 (t) + t^2P_2^1(t) = \\
={(1 - t)}^3P_0 + 3t{(1 - t)}^2P_1 + 3t^2(1 - t)P_2 + t^3P_3.$$
Запишем общее аналитическое представление для кривой Безье с N + 1 опорной точкой:
$$B_i ^N(t)$$ называются базисными многочленами Бернштейна N - й степени (а также весовыми функциями Безье-Бернштейна). На рис. 4.4 и 4.5 изображены многочлены Бернштейна 3-й и 4-й степеней.
(рис 4.5) Базисные функции Бернштейна 3-й степени(рис 4.4) Базисные функции Бернштейна 4-й степениСледствие. Если все опорные точки лежат на одной прямой, то кривая Безье вырождается в отрезок, соединяющий эти точки.
P0 и PN.1 меньше числа опорных точек.P0 и PN Замечание. Хотя все выкладки проводились в $$\mathbb{R}^2$$, аналогичные построения и свойства справедливы и в $$\mathbb{R}^n$$.
$$\{x = x(t), y = y(t)\}, t \in [0, 1]$$ (определяются по выражению (4.2)). Подберем шаг $$\Delta t$$ так, чтобы $$\Delta x = x(t + \Delta t) - x(t)$$ и $$\Delta y = y(t + \Delta t) - y(t) (t \in [0, 1])$$ были меньше размера стороны пикселя d (если мы работаем в пиксельных координатах, то это 1 ), т. е. мы не пропустим ни одного пикселя при таких приращениях. Т.к. $$\frac{dx}{dt}$$ и $$\frac{dy}{dt}$$ - многочлены, то, соответственно, легко найти максимумы их модулей Mx и My на отрезке [0, 1]. Положим M = max(Mx,My), тогда, взяв $$\Delta t = \frac{d}{M}$$, получим что смещения по x и по y при каждом шаге не превосходят длины стороны пикселя.
// x(t), y(t) заданы в пиксельных координатах => d = 1
// M - максимум модулей dx/dt и dy/dt на всем отрезке [0,1]
// round(x) - округляет x до ближайшего целого
dt = 1 / M;
t = 0;
while(t < 1)
{
x = x(t); // см. выражение 4.2
y = y(t); // см. выражение 4.2
plot( round(x) , round(y) );
t += dt;
}
Недостаток данного алгоритма состоит в том, что при малых смещениях по x и y много итераций проходит зря, т.к. происходит повторная закраска одних и тех же пикселей.
Предложен де Кастелье. Рассмотрим пример этого алгоритма для кривой 4-го порядка с опорными точками P0P1P2P3 (см. рис. 4.6). Если рассмотреть участок между P0 и $$P_0^4 (t_1), t_1 = \frac{1}{2}$$, то он может быть задан как кривая Безье с опорными точками $$P_0P_0^1(t_1)P_0^2(t_1)P_0^3(t_1)P_0^4(t_1), t_1 = \frac{1}{2}$$ (почему это так, подробнее см., например, в [28]).
Аналогичные рассуждения справедливы и для участка между $$P_0^4(t_1), t_1 = \frac{1}{2}$$ и P4. Будем применять этот алгоритм рекурсивно для левой и правой частей, пока кривая не выродится в прямую с точностью до пикселя, а это так или иначе (все точки попадут в один пиксель) произойдет.
P.
P1, . . . ,Pn.
// работаем в пиксельных координатах
// (размер пикселя равен 1x1)
// P0 - начальная точка кривой
// Pn - конечная точка кривой
DrawCurve(P0,P1, . . . ,Pn)
{
// Проверка на завершение
if( макс. длина ребра BBox(P0,P1, . . . , Pn) < 1 )
return;
if( P0,P1, . . . , Pn лежат на отрезке P0Pn
с точностью до пикселя )
{
Нарисовать отрезок P0Pn;
// (см. лекцию о растеризации отрезков)
return;
}
Найти P01,P02, . . . , P0{n-1} для t = 0,5;
// используя (4.1)
Найти P0n для t = 0,5; // используя (4.1)
Найти P1{n-1},P2{n-2}, . . . , P{n-1}1 для t = 0,5;
// используя (4.1)
plot(P0n);
// Нарисовать половинки (см. рис. 4.6)
DrawCurve( P0,P01, . . . , P0n);
DrawCurve( P0n,P1{n-1}, . . . , Pn);
}
(рис 4.6) Построение кривой Безье методом разбиения.Для построения кривых по большому множеству опорных точек пришлось бы использовать кривые Безье большого порядка, что привело бы к громоздким вычислениям; к тому же часто желательным является локальное влияние на форму кривой (для кривых Безье это не так). Поэтому чаще используют
Такие сплайны обладают свойством локальности влияния контрольных точек на форму кривой. Как и в случае интерполирующих сплайнов, будем искать сплайны определенной степени гладкости.
Для упрощения будем считать, что параметризация равномерная, т.е. длины отрезков, которые пробегает параметр на каждом из участков, равны. Для того чтобы рассмотреть условия на C1 и C2, необходимо найти производные кривых Безье:
где
$$\Delta^k(P_i) = \sum\limits_{j=0}^{k}(-1)^j \cdot C_j ^k \cdot P_{i+j}, \\ C_j ^k =\frac{k!}{j!(k - j)!}.$$Рассмотрим подробно случай кубических кривых Безье, которые являются самыми распространенными.
C1. Пусть заданы значения производных на концах ( d0 и d1 ), обозначим совпадающую последнюю контрольную точку предыдущей кривой и первую контрольную точку текущей как Pn:$$$ \frac{d}{dt}P^3(0) = 3(P_{n+1} - P_n) = d_0 \quad \Rightarrow \quad P_{n+1} = P_n + \frac{1}{3}d_0 \\ \frac{d}{dt}P^3(1) = 3(P_{n+3} - P_{n+2}) = d_1 \quad \Rightarrow \quad P_{n+2} = P_{n+3} - \frac{1}{3}d_1. $$$
Таким образом, для того чтобы в точках стыковки производные были равны (d0 = d1), необходимо, чтобы
(рис 4.7) Стыковка с требованием C1
C2:$$$\frac{d}{dt}P^3(0) = 3(P_{n+1}- Pn) = 3d_1, \\ \frac{d}{dt}P^3(1) = 3(P_n - P_{n-1}) = 3d_2, \\ \frac{d^2}{dt^2}P^3(0) = 6(P_{n+2} - 2P_{n+1} + P_n), \\ = 6((P_{n+2} - P_{n+1}) + (P_n - P_{n+1})) = 6\Delta_1, \\ \frac{d^2}{dt^2}P^3(1) = 6(P_n - 2P_{n-1} + P_{n-2}), \\ = 6((P_n - P_{n-1}) + (P_{n-2} - P_{n-1})) = 6\Delta_2. $$$
Из требования C1 в точках стыковки мы уже получили $$d =d_1 = d_2 \Leftrightarrow P_{n-1}P_n = P_nP_{n+1}$$. Далее, из требования C2 следует равенство $$\Delta = \Delta_1 = \Delta_2$$. Так как $$\Delta$$ получаются сложением соответствующих векторов по правилу параллелограмма, то $$P_{n-2}P_{n+2} \quad \| \quad P_{n-1}P_{n+1}$$ и, если обозначить точку
пересечения Pn-2Pn-1 и Pn+2Pn+1 как Dn, то получим, что Pn-1Pn+1 - средняя линия треугольника Pn-2DnPn+2. Распространяя эти рассуждения на все точки стыковки, получаем, что для задания формы такого сплайна достаточно задать точки Dk, где $$k = 3i, i \in \overline{1,N/3}$$, где N + 1 - число опорных точек, и краевые точки - P0 и PN (см. рис. 4.9 ).
Замечание. Для замкнутой кривой задание краевых точек не нужно.
(рис 4.8) Стыковка с требованием C2.
(рис 4.9) Связь между точками Dk для соседних сегментов.
Однако даже такие достаточно развитые средства аппроксимации кривыми Безье не позволяют построить окружность$$\left\{ \begin{array}{c}
x = \cos t \\
y = \sin t \\
\end{array} \right. ,$$
так как sin и cos для достаточно хорошего приближения требуют многочленов высокой степени. Поэтому вводится более широкий класс кривых, способ построения которых связан с представлением о проективном пространстве:
Пусть у нас есть пространственная кривая Безье P0P1 . . . PN в системе координат OXY w. Спроецируем все точки исходной кривой на плоскость w = 1, т.е.:
где
$$P_i = \left[ \begin{array}{c} w_i \cdot \tilde{P}_i \\ w_i \end{array} \right] = \left( \begin{array}{c} w_ix_i \\ w_iy_i \\ w_i \end{array} \right) \mbox{ (см. рис. 4.10.)}$$Полученная кривая, лежащая в плоскости w = 1, и называется рациональной двумерной кривой Безье. Аналогичным образом можно получать рациональные кривые Безье и в пространстве большего числа измерений.
$$\tilde{P}_i = \left( \begin{array}{c}
x_i \\
y_i
\end{array} \right)$$
будем называть опорными точками рациональной кривой Безье, а wi - весовыми функциями.
Рассмотрим пример представления окружности, составленной из 3-х рациональных кубических кривых Безье. Возьмем для примера один из сегментов (см. рис. 4.11). Положим $$w_0 = 1, w_1 = \frac{1}{2} , w_2 = 1$$, а
$$$\tilde{P}_0 = \left( \begin{array}{c} \frac{R}{2} \\ \frac{\sqrt{3}R}{2} \end{array} \right), \tilde{P}_1 = \left( \begin{array}{c} \frac{2R}{\sqrt{3}} \\ 0 \end{array} \right), \tilde{P}_2 = \left( \begin{array}{c} \frac{R}{2} \\ -\frac{\sqrt{3}R}{2} \end{array} \right), $$$где R - радиус окружности.
Итоговое изображение представлено на рис. 4.12.
(рис 4.10) Рациональная кривая Безье.Растеризовать такие кривые можно теми же двумя способами, что и для обыкновенных кривых Безье. При этом в алгоритме рекурсивного разбиения разбивается исходная кривая в проективном пространстве.
B-сплайны являются обобщением кривых Безье. Они также представимы в линейной комбинации контрольных точек. Пусть заданы порядок кривой n, потенциальное количество участков m, вектор узлов
и контрольные точки $$\{P_i\} , i = \overline{0,m + n - 1}$$. Если ti = ti+1 = . . . = ti+l и соответственно Pi = Pi+1 = . . . = Pi+l, то говорят об узле ti кратности l. Как правило, для кривой порядка n в начале и в конце ставятся узлы кратности n, так как при этом концы кривой будут совпадать с крайними контрольными точками.
(рис 4.12) Сегмент окружности, представленный рациональной кривой Безье.(рис 4.11) Изображение окружности.Формулы Кокса - де Бура (Cox - de Boor) рекурсивно определяют B-сплайн:
$$Pn(t) = \sum\limits_{i=0}^{m+n-1}b_{i,n}(t) \cdot P_i, \mbox{ где}$$ $$b_{j,0}(t) = { \left\{ \begin{array}{cc} 1, \text{если } t_{j-1} \le t < t_j, \\ 0, \text{в другом случае} \\ \end{array} \right. }; \\ b_{j,k}(t) = \frac{t-t_{j-1}}{t_{j+n-1}-t_{j-1}}b_{j,k-1}(t) + \frac{t_{j+n}- t}{t_{j+n}-t_j}b_{j+1,k-1}(t).$$Если узлы кратные, то в (4.3) возникают неопределенности вида $$\frac{0}{0}$$, которые по определению должны разрешаться как 0. Многочисленные полезные свойства этих кривых находятся за рамками данной книги. Подробную информацию можно найти в [28], [8].
Кратко остановимся только на вопросе растеризации данных кривых. Можно выделить три основных подхода.
Алгоритм де Бура
Для $$t \in [t_I , t_{I+1}), I \in \overline{n - 1,m+ n - 1}$$
$$P^n(t) := P_{I+1}^n(t), \mbox{ где} \\ P_I^0(t) = P_I ; \\ P_j^k(t) = \left(1 - \frac{t-t_{j-1}}{t_{j+n-k}-t_{j-1}}\right) \cdot P_{j-1}^{k-1}(t) + \frac{t-t_{j-1}}{t_{j+n-k}-t_{j-1}} \cdot P_j^{k-1}(t).$$Если узлы кратные, то в (4.4) также могут возникнуть неопределенности вида $$\frac{0}{0}$$, которые по определению должны разрешаться как 0.
[ti, ti+1] можно при помощи вставки узлов ti до тех пор пока их кратность не достигнет n. Новые контрольные точки B-сплайна, которые также будут контрольными точками для кривых Безье на каждом отрезке [ti, ti+1], будут получены в результате стандартной процедуры добавления узлов в B-сплайн (см. например, [28]).Самыми распространенными в геометрическом моделировании в настоящее время являются Неоднородные рациональные B-сплайны (англ. NURBS). Неоднородность означает, что промежутки между соседними узлами ti могут быть различными. Рациональные они в том же смысле, что и рациональные кривые Безье (см. раздел 4.2), т.е. проекция B-сплайна из проективного пространства. Это наиболее широкий из рассмотренных классов кривых.
Специфика данного курса не предполагает детального изучения математических свойств рассмотренных выше кривых; особенно это касается лишь кратко рассмотренных B-сплайнов. Всех интересующихся описанием этих вопросов, а также тех, кто хотел бы узнать более подробно о вышеизложенном материале, отсылаем к книгам [8], [28].
Также за рамками данной лекции остались кривые разбиения. О них можно узнать подробнее из [47].
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.