(Сплайны)
Определения (нестрогое определение)
Определения (математические определения)
Виды сплайнов
Виды сплайнов
Одномерные квадратичные базисные функции (лагражевы шаблонные)
Одномерные кубические базисные функции (лагражевы шаблонные)
Одномерные кубические базисные функции (эрмитовы шаблонные)
Интерполяционный полином Лагранжа
Проблема согласования полиномов (негладкий сплайн, независимые параболы)
Линейный сплайн с полиномами Лагранжа (формулы)
Квадратичный сплайн с полиномами Лагранжа (формулы)
Кубический сплайн с полиномами Лагранжа (формулы)
Кубический сплайн с полиномами Эрмита (интерполяционный сплайн)
Кубический сплайн с полиномами Эрмита (сглаживающий сплайн)
Кубический сплайн с полиномами Эрмита (сглаживающий сплайн)
Кривая Безье (Bezier Curve)
Кривая Безье (2 Контрольных Точки)
Кривая Безье (3 Контрольных Точки)
Кривая Безье (4 Контрольных Точки)
Кривая Безье (6 Контрольных Точки)
Кривая Безье (некоторые свойства)
B-сплайн (определение)
B-сплайн (определение)
B-сплайн (задание вектора узлов)
B-сплайн (некоторые свойства)
NURBS-сплайн (Non-Uniform Rational B-Spline)
NURBS-сплайн (Non-Uniform Rational B-Spline)
Лагранжев квадратичный интерполяционный (различные наборы КТ)
Эрмитов кубический интерполяционный сплайн (различные наборы КТ)
Эрмитов кубический сглаживающий сплайн (различные наборы КТ)
Сравнение интерполяционных сплайнов (эрмитового и лагранжевых)
Сравнение сглаживающих сплайнов (эрмитов и закрытые B-сплайны)
Сравнение видов B-сплайнов
Сплайн-поверхности
Сплайн-поверхности (Безье и B-сплайн)
Сплайн-поверхности (Безье)
Сплайн-поверхности (Безье)
Сплайн-поверхности (сплайн Безье, чайник Юта)
Сплайн-поверхности (бикубический интерполяционный)
Поддержка в OpenGL (библиотека GLU)
Поддержка в OpenGL (пример построения Безье с равномерным шагом)
2.12M
Categories: mathematicsmathematics programmingprogramming

Интерактивная компьютерная графика

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 1
2 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. Одномерные кубические базисные функции (лагражевы шаблонные)

9
1
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 3
2 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 x
n 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 x
n 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 x
n 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. Кубический сплайн с полиномами Эрмита (интерполяционный сплайн)

n
n
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 , xn
k
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 , P1
Q B ti – точка на отрезке P0 , P1
18(42)
8.2.5 Кривая Безье [2/6]

19. Кривая Безье (3 Контрольных Точки)

P1
Q1
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 Контрольных Точки)

Q1
P1
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 -1
B 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, 0
0
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. Сплайн-поверхности

n
m
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]
English     Русский Rules