Similar presentations:
Интерактивная компьютерная графика
1. (Сплайны)
Часть 8-2(Сплайны)
2. Определения (нестрогое определение)
Сплайн – непрерывная функция, проходящая какможно ближе к контрольным точкам
Контрольные точки
2(42)
8.2.1 Сплайны [1/4]
Не сплайны!
3. Определения (математические определения)
Сплайн – функция,область определения которой разбита на подобласти,
на каждой из которых сплайн совпадает
с некоторым алгебраическим многочленом (полиномом)
Степень сплайна – максимальная степень использованных полиномов
Гладкость сплайна – максимальный порядок непрерывной
производной
Дефект сплайна – разность между степенью сплайна
и его гладкостью
Пример сплайна: ломаная (кусочно-линейная функция)
Производная сплайна: кусочно-постоянная функция
Степень сплайна:
1
Гладкость сплайна:
0
Дефект сплайна:
1
3(42)
8.2.1 Сплайны [2/4]
4. Виды сплайнов
По близости к контрольным точкам (КТ):• Интерполяционные (обязаны проходить через КТ)
• Сглаживающие (не обязаны проходить через КТ)
По учету КТ при расчете коэффициентов сплайна:
• Локальные (коэффициенты рассчитываются через соседние КТ)
• Глобальные (коэффициенты рассчитываются через все КТ)
По типу производной:
• Рациональные (с разрывной производной)
• Нерациональные (с непрерывной 1ой, 2ой,... производной)
По типу используемых базисных функций:
• Полиномиальные (лагранжевые, эрмитовые,…)
• Неполиномиальные (логарифмические, тригонометрические,…)
По мерности пространства:
• Одномерные (кривые)
• Двумерные (поверхности)
4(42)
8.2.1 Сплайны [3/4]
5. Виды сплайнов
Контрольные точки:( f – неизвестная функция)
f xi fi , i 1, n
hi xi 1 xi ,
i 1, n 1
Общий вид сплайна: P x
m
q ( x )
i 1
i
i
P xi fi
Условие для интерполяционного сплайна:
n
Условие для сглаживающего сплайна:
(методом Наименьших квадратов)
P x f
i 1
i
i
Задача сглаживания – построение достаточно гладкой функции,
значения которой в КТ максимально близки к
5(42)
8.2.1 Сплайны [4/4]
2
min
fi
6. Одномерные квадратичные базисные функции (лагражевы шаблонные)
1 2 12 4 1
x xi
hi
3 2
6(42)
1
2
0, x xi 1
3 x , x xi 1 , xi
i x
1 x , x xi , xi 1
0, x xi 1
8.2.2 Одномерные базисы [1/4]
7. Одномерные кубические базисные функции (лагражевы шаблонные)
91
2
27
2
1
2
27
3
1
2
9
4
2
1
7(42)
x xi
hi
1
3
2
3
8.2.2 Одномерные базисы [2/4]
0, x xi 1
3 x , x xi 1 , xi
i x
1 x , x xi , xi 1
0, x xi 1
8. Одномерные кубические базисные функции (эрмитовы шаблонные)
1 1 3 2 2 32 2 2 3
3 3 2 2 3
4 2 3
8(42)
x xi
hi
0, x xi 1
3 , x xi 1 , xi
i
1 , x xi , xi 1
0, x x
i 1
8.2.2 Одномерные базисы [3/4]
0, x xi 1
h 4 , x xi 1 , xi
i 1
h 2 , x xi , xi 1
0, x x
i 1
9. Интерполяционный полином Лагранжа
Степени n:x xj
L x fi
i 1
j i xi x j
Степени 1:
L x Pi1 x ,
n
n
n 1
1
i 1
Степени 2:
n 1
L x Pi x ,
2
2
i 1
Степени 3:
n 1
L x Pi x ,
3
3
i 1
9(42)
a x bi , x xi , xi 1
Pi1 x i
0, иначе
2
ai x bi x ci , x xi , xi 1
Pi x
0, иначе
2
3
2
ai x bi x ci x di , x xi , xi 1
Pi x
0, иначе
3
8.2.2 Одномерные базисы [4/4]
10. Проблема согласования полиномов (негладкий сплайн, независимые параболы)
Параболы по трем точкам (всего 7 точек)Ошибка: производные в КТ не равны (нет гладкости)!
10(42)
8.2.3 Сплайн на основе полиномов Лагранжа [1/4]
11. Линейный сплайн с полиномами Лагранжа (формулы)
P xn 1
Pi1 x , где Pi1 x ai x bi , x xi , xi 1
i 1
Pi x
xi
hi
xi 1
Система для определения
коэффициентов сплайна
ai
1
fi 1 fi
hi
bi fi ai xi
Pi xi fi
Pi xi 1 fi 1
11(42)
8.2.3 Сплайн на основе полиномов Лагранжа [2/4]
12. Квадратичный сплайн с полиномами Лагранжа (формулы)
P xn 1
Pi 2 x , где Pi 2 x ai x 2 bi x ci , x xi , xi 1
i 1
a1
Pi x
xi
hi
1
1 '
f
f
f1
2
1
h12
h1
b1 f1' 2a1 x1
xi 1
c1 f1 f1' x1 a1 x12
f1'
f f
f
x1 2 1
x
h1
Система для определения
коэффициентов сплайна
Pi 2 xi fi
2
Pi xi 1 fi 1
2
Pi 21
Pi
x xi x xi
12(42)
ai
1
1
f
f
i
i 1
i
hi2
hi
bi i 2ai xi
i 2ai 1 xi bi 1
ci fi i xi ai xi2
8.2.3 Сплайн на основе полиномов Лагранжа [3/4]
13. Кубический сплайн с полиномами Лагранжа (формулы)
P xn 1
Pi 3 x , где Pi 3 x ai x3 bi x 2 ci x di , x xi , xi 1
i 1
a1
Pi x
xi
hi
xi 1
Система для определения
коэффициентов сплайна
Pi 3 xi f i
3
Pi xi 1 f i 1
3
3
Pi x Pi 1 x
i
x i
x
2 3
2 3
P
Pi 1
i
x
x
2 i
x 2 i
x
13(42)
1
1 ' 1 ''
f
f
f
f1
2
1
3
2 1
h1
h1
2h1
1 ''
f1 3a1 x1
2
c1 f1' 2b1 x1 3a1 x12
b1
f1'
f f
f
x1 2 1
x
h1
2 f
f 2 x1 0
x
''
1
d1 f1 c1 x1 b1 x12 a1 x13
ai
1
1
1
f
f
i
i 1
i
i
hi3
hi2
hi
bi i 3ai xi
ci i 2bi xi 3ai xi2
i 3ai 1 xi2 2bi 1 xi ci 1
i 3ai 1 xi bi 1
di fi ci xi bi xi2 ai xi3
8.2.3 Сплайн на основе полиномов Лагранжа [4/4]
14. Кубический сплайн с полиномами Эрмита (интерполяционный сплайн)
nn
i 1
i 1
P x fi 2i -1 ( x) fi ' 2i ( x)
f i ' – значения производных квадратичного полинома Лагранжа для xi 1 , xi , xi 1
dL2i x f i 1
x xi x xi 1 f x xi 1 x xi 1 f x xi x xi 1
xi 1 xi xi 1 xi 1 i xi xi 1 xi xi 1 i 1 xi 1 xi xi 1 xi 1
fi ' x
14(42)
f
xi dL2i xi
x
f
x1 dL22 x1
x
f
f n' x xn dL2n 1 xn
x
f1' x
8.2.4 Сплайн на основе полиномов Эрмита [1/3]
15. Кубический сплайн с полиномами Эрмита (сглаживающий сплайн)
x1 , xnk
i
i 1
область подразбивается на конечные элементы
с эрмитовыми базисными функциями
n
P x f
Условие для сглаживающего сплайна:
i 1
i
i
2
min
Функционал минимизации для расчета коэффициентов:
A j x j
n
T
j 1
2
T
T
2k
F q = j qi i x j f j q Aq 2q b c
j=1
i 1
n
b j x j f j
n
j 1
n
c j f j2
j 1
Функционал в случае неединственности:
F p = j P( x j ) f j
k
j=1
15(42)
2
2
n
d 2 P( x)
dP( x)
( x)
dx
dx ( x)
2
dx
dx
x1
x1
xn
2
x
8.2.4 Сплайн на основе полиномов Эрмита [2/3]
x
j
16. Кубический сплайн с полиномами Эрмита (сглаживающий сплайн)
Эквивалентное матричное уравнение:Aq b
Матрица A и вектор b собираются
i
i
из стандартных локальных матриц Aˆ и векторов bˆ
конечного элемента i :
d ˆ d ˆ m
aˆlm j ˆ l x j ˆ m x j x l
dx
dx dx
j 1
xi
xi 1
n
xi 1
xi
d 2 ˆ l d 2 ˆ m
x 2
dx
2
dx dx
bˆl j ˆ l x j f j
n
j 1
Расчет значения сплайна в любой точке:
2k
P x qi i x
i 1
16(42)
8.2.4 Сплайн на основе полиномов Эрмита [3/3]
l , m 1, 4
17. Кривая Безье (Bezier Curve)
Кривая Безье – это параметрическая кривая вида:n 1
B t Pi bi ,n 1 t , t 0,1
i 0
Pi xi , fi – вектор i-й контрольной точки
bi , j – базисные функции кривой Безье (полиномы Бернштейна):
bi , j t C ij t i 1 t
C ij
j i
j!
– число сочетаний из j по i
i ! j i !
Расчет значения сплайна в точке (x,y) x t B t
x
для конкретного значения параметра t:
y t By t
17(42)
8.2.5 Кривая Безье [1/6]
18. Кривая Безье (2 Контрольных Точки)
Кривая представляет собою отрезок P0 , P1Q B ti – точка на отрезке P0 , P1
18(42)
8.2.5 Кривая Безье [2/6]
19. Кривая Безье (3 Контрольных Точки)
P1Q1
Q0
B
t
P0
19(42)
1
Q0 P0 P1 P0
4
1
Q1 P1 P2 P1
4
1
4
P2
8.2.5 Кривая Безье [3/6]
точка кривой Безье:
1
1
P = B= Q0 + Q1 -Q0
4
4
P t 1 t P0 2t 1 t P1 t 2 P2
2
20. Кривая Безье (4 Контрольных Точки)
Q1P1
P2
R1
B
Q0
R0
P0
t
1
4
1
1
P1 P0 Q1 P1 P2 P1
4
4
1
Q2
Q 2 P2 P3 P2
4
1
R 0 Q0 Q1 Q0
4
P3
1
R
Q
Q2 Q1
1
1
1
1
4
P = B= R 0 + R1 -R 0
Q0 P0
4
4
P t 1 t P0 3t 1 t P1 3t 2 1 t P2 t 3P3
3
20(42)
8.2.5 Кривая Безье [4/6]
2
21. Кривая Безье (6 Контрольных Точки)
21(42)8.2.5 Кривая Безье [5/6]
22. Кривая Безье (некоторые свойства)
соединяет начальную и конечную КТ,но нельзя получить окружность
изменение координат хотя бы одной из точек
ведет к изменению формы всей кривой (глобальность)
всегда располагается внутри фигуры (выпуклой оболочки),
образованной линиями, соединяющими контрольные точки
симметрична, то есть обмен местами между начальной и конечной КТ
(изменение направления траектории) не влияет на форму кривой
степень кривой всегда на одну ступень ниже числа КТ
(например, при трех контрольных точках форма кривой – парабола)
22(42)
8.2.5 Кривая Безье [6/6]
23. B-сплайн (определение)
B-сплайн – это сплайн-функция,имеющая наименьший носитель для заданных:
• степени
• гладкости
• разбиения области определения
B-сплайн – это «базисный сплайн»
Теорема: любой сплайн с заданной степенью, гладкостью и областью
может быть представлен как линейная комбинация B-сплайнов
той же степени и гладкости на той же области определения
23(42)
8.2.6 B-сплайн [1/4]
24. B-сплайн (определение)
B-сплайн – это параметрическая кривая, задаваемая выражением:n 1
P t Pi Bi , p t ,
i 0
t T tmin , tmax специальный вектор узлов (не КТ !)
p 2, n 1 – степень сплайна степень полинома 1
Базисные функции рассчитываются
по рекуррентным формулам Кокса-де Бура:
1, t ti , ti 1
Bi ,0 t
0, иначе
Bi ,k t
24(42)
t ti Bi ,k 1 t ti k t Bi 1,k 1 t
ti k 1 ti
ti k ti 1
8.2.6 B-сплайн [2/4]
25. B-сплайн (задание вектора узлов)
Открытый B-сплайн:T 0, 1, 2,..., n p 1
T T1 T 2 T 3
Закрытый B-сплайн:
T11 p 0, 0,..., 0
T1 2 n p 1, 2,..., n p
T1 3 p n p 1,..., n p 1
T 1, 2, 3,..., n 2 p 1
Замкнутый B-сплайн:
f f1 , f 2 ,..., f n f1 , f 2 ,..., f p 1
n 1
p 1
i 0
i 0
P t Pi Bi , p 1 t Pi Bi n , p 1 t
25(42)
8.2.6 B-сплайн [3/4]
26. B-сплайн (некоторые свойства)
Некоторые свойства:• если p n 1 , то Закрытый B-сплайн вырождается в Кривую Безье
• масштабирование и параллельный перенос КТ не влияет на Bi , p t
• содержится в выпуклой оболочке его КТ
• в общем случае является локальным
• степень гладкости равна p 1
• кривая проходит вблизи средней точки каждой стороны
выпуклой оболочки, за исключением первой и последней
26(42)
8.2.6 B-сплайн [4/4]
27. NURBS-сплайн (Non-Uniform Rational B-Spline)
NURBS – неоднородный рациональный B-сплайнРациональный В-сплайн – это проекция (обобщение)
нерационального (полиномиального) В-сплайна,
определенного в четырехмерном (4D)
однородном координатном пространстве,
на трехмерное (3D) физическое пространство
x y z
x
,
y
,
z
,
, , x ', y ', z '
Если узлы равноудалены друг от друга,
то B-сплайн является однородным,
в противном случае - неоднородный
27(42)
8.2.7 NURBS-сплайн [1/2]
28. NURBS-сплайн (Non-Uniform Rational B-Spline)
n -1B t
'
P
i i Bi, p t
i =0
n -1
B t
i
i =0
i, p
n -1
Pi' R i , p t
i =0
Pi' – вершины полигона в 3D
R i , p t – базисные функции,
i – веса контрольных точек
28(42)
8.2.7 NURBS-сплайн [2/2]
n -1
R t 1
i, p
i =0
29. Лагранжев квадратичный интерполяционный (различные наборы КТ)
7 точек2 значения
в одной точке
29(42)
+1 точка внутри
(сортировка)
+1 точка в конце
8.2.8 Сравнение сплайнов [1/6]
+1 точка внутри
(без сортировки)
+1 точка внутри (пики)
30. Эрмитов кубический интерполяционный сплайн (различные наборы КТ)
7 точек2 значения
в одной точке
30(42)
+1 точка внутри
(сортировка)
+1 точка в конце
8.2.8 Сравнение сплайнов [2/6]
+1 точка внутри
(без сортировки)
+1 точка внутри (пики)
31. Эрмитов кубический сглаживающий сплайн (различные наборы КТ)
0, 00
2 КЭ
0, 0
31(42)
8.2.8 Сравнение сплайнов [3/6]
0
32. Сравнение интерполяционных сплайнов (эрмитового и лагранжевых)
Эрмитовкубический
Линейный
Лагранжев
квадратичный
32(42)
Лагранжев
кубический
8.2.8 Сравнение сплайнов [4/6]
Лагранжев
степени n
33. Сравнение сглаживающих сплайнов (эрмитов и закрытые B-сплайны)
ЛинейныйB-сплайн
степени 6+1 (Безье)
33(42)
Эрмитов
кубический
B-сплайн
степени 3+1
8.2.8 Сравнение сплайнов [5/6]
B-сплайн
степени 1+1
34. Сравнение видов B-сплайнов
Открытыйстепени 2+1
Закрытый
степени 2+1
Замкнутый
степени 6+1
Замкнутый
степени 2+1
34(42)
8.2.8 Сравнение сплайнов [6/6]
35. Сплайн-поверхности
nm
S u, v pi , j bi u b j u
i 0 j 0
35(42)
8.2.9 Сплайн-поверхности [1/6]
36. Сплайн-поверхности (Безье и B-сплайн)
Pi , j (n m) контрольных точек (вершин сетки)Поверхность Безье
порядка (n-1,m-1)
n 1 m 1
P u, v Pi , j Bi ,n 1 u B j ,m 1 v
i =0 j 0
Поверхность B-сплайна
порядка (p,q):
n 1 m 1
P u, v Pi , j Bi , p u B j ,q v
i =0 j 0
n 1 m 1
Поверхность NURBS
порядка (p,q):
P u, v
w
i =0 j 0
n 1 m 1
w
i =0 j 0
36(42)
P Bi , p u B j ,q v
i, j i, j
8.2.9 Сплайн-поверхности [2/6]
i, j
Bi , p u B j ,q v
37. Сплайн-поверхности (Безье)
37(42)8.2.9 Сплайн-поверхности [3/6]
38. Сплайн-поверхности (Безье)
38(42)8.2.9 Сплайн-поверхности [4/6]
39. Сплайн-поверхности (сплайн Безье, чайник Юта)
39(42)8.2.9 Сплайн-поверхности [5/6]
40. Сплайн-поверхности (бикубический интерполяционный)
40(42)8.2.9 Сплайн-поверхности [6/6]
41. Поддержка в OpenGL (библиотека GLU)
gluNewNurbsRenderer ()// создание объекта типа NURBS
gluDeleteNurbsRenderer (*) // создание объекта типа NURBS
gluNurbsProperty (*) // задание свойств
gluNurbsCallback() // проверка на ошибки и возврат значений
gluBeginSurface (*) // начало рисование поверхности
gluNurbsSurface (*) // передача контрольных точек, нормалей,….
gluEndSurface (*) // завершение рисования поверхности
gluBeginCurve (*) // начало рисование кривой
gluNurbsCurve (*) // передача контрольных точек, нормалей,….
gluEndCurve (*) // завершение рисования кривой
41(42)
8.2.10 Поддержка в OpenGL [1/2]
42. Поддержка в OpenGL (пример построения Безье с равномерным шагом)
parts = 20 * n;gl.Map1(OpenGL.GL_MAP1_VERTEX_3, 0f, 1f, 3, n, ver3);
gl.Enable(OpenGL.GL_MAP1_VERTEX_3);
gl.MapGrid1(parts, 0f, 1f);
gl.EvalMesh1(OpenGL.GL_LINE, 0, parts);
gl.Disable(OpenGL.GL_MAP1_VERTEX_3);
42(42)
8.2.10 Поддержка в OpenGL [2/2]