Построение инвариантных множеств рациональных преобразований. - презентация

1 Построение инвариантных множеств рациональных преобразований

2 Множество Жюлиа функции f: C C J(f) = {z C: f n (z), при n }

3 Наполненное множество Жюлиа K(f) = {z C: f n (z), при n }

4 Множество Жюлиа функции f c (z) = z 2 + c Свойство: Множество Жюлиа (J = J(f c )) – отталкивающее по отношению к f с И, наоборот, множество J – притягивающее по отношению к обратной функции f c –1 (z) =(z – c)

5 Множество Жюлиа функции f c (z) = z 2 + c Два типа (в зависимости от параметра с) связные несвязные

6 Множество Мандельброта Служит индикатором для двух типов множеств Жюлиа. Каждая точка в множестве Мандельброта представляет значение c, для которого множество Жюлиа J(f c ) связно. Каждая точка из дополнения к множеству Мандельброта представляет значение c, для которого J(f c ) несвязно

7 Множество Мандельброта M = {c C: {f c n (0)}n=0, 1, 2,… ограничена} (теорема Фату) M = {c C: f c n (0), при n }

8 z n+1 = f c (z n ) Зафиксируем c. Все такие точки z 0, что последовательность {z n } ограничена, образуют наполненное множество Жюлиа K(f c ) Зафиксируем z 0 = 0. Все такие точки c, что последовательность {z n } ограничена, образуют множество Мандельброта M

9 Алгоритм проверки ограниченности последовательности {f c n (z 0 )} Выбираются достаточно большие m и R Для j = 1, …, m проверяется неравенство |f c j (z 0 )| > R z C j N z = z 0 for j = 1 to m do z = z 2 + c // z = f c j (z 0 ) if |z| > R then return неограниченная_последовательность return ограниченная_последовательность

10 Метод обратных итераций Алгоритм построения множества Жюлиа J(f c ) Выбирается произвольная начальная точка. После нескольких итераций обратной функции f c –1 (z) =(z – c) точка становится очень близкой к множеству J Каждая последующая итерация точки выводится на экран

11 Кватернионы (гиперкомплексные числа) q = r + ai + bj + ck, где i, j, k – мнимые единицы со следующими свойствами: i 2 = j 2 = k 2 = –1, ij = k, jk = i, ki = j, ji = –k, kj = –i, ik = –j; r, a, b, c – вещественные

12 Гиперкомплексные множества Жюлиа и Мандельброта f: H H (например, f(h) = f с (h) = h 2 + с) K(f) = { h H: |f n (h)| ограничен, если n } M = {q H: 0 K(f с ), где f с (h) = h 2 + с}

13

14

15 Метод трассировки лучей Луч задается начальной точкой q 0 H вне множества направлением dir H, |dir| = 1 Точка h на луче, находящаяся на расстоянии dist от начала луча, определяется по следующей формуле: h = q0 + dirdist

16 Первый способ нахождения расстояния от начала луча до точки пересечения Дополнительно задаются: максимальное расстояние maxD, дальше которого пересечение не ищется количество разбиений n Определяется шаг по расстоянию D = maxD / n

17 Недостатки данного способа нахождения пересечения С возрастанием точности (количества разбиений n) пропорционально возрастает время поиска пересечения Даже если луч пересекает K(f c ) (или M), и расстояние от начала луча до точки пересечения меньше maxD, пересечение может быть не найдено Может быть найдено не первое пересечение

18 Второй способ нахождения расстояния от начала луча до точки пересечения Алгоритм: Выбирается точка q = q 0 Вычисляется dMin = dmin(q) и dMax = dmax(q) q = q + dirdMin Если |dMax-dMin| < ε, то точка пересечения q найдена. Выход. Если |q 0 – q| > maxD, то пересечения нет. Выход. Переход к 2. Расстояние от начала луча до точки пересечения dist = |q0 – q|. Существуют функции dmin и dmax, которые для каждой точки q выдают минимальную и максимальную оценку расстояния от q до множества. Задана погрешность ε

19 Переход от 4D к 2D, вычисление матрицы расстояний Задаются следующие параметры: center, xDir, yDir, zDir H, minDist, maxDist, dx, dy R

20 Вычисление матрицы расстояний Для элемента (n, m) матрицы вычислим q 0 = center + dx(n / xRes – 0.5) xDir + dy(m / yRes – 0.5) yDir + minDistzDir Для луча с началом q 0 и направлением zDir найдем расстояние dist nm от q 0 до точки пересечения с множеством (примем maxD = maxDist – minDist) dm[n, m] = dist nm + minDist

21 Вычисление нормалей Получение изображения Для каждого элемента (n, m) матрицы dm, кроме граничных, координаты нормали (x, y, z): x = (dm[n + 1, m] – dm[n – 1, m]) / x, y = (dm[n, m + 1] – dm[n, m – 1]) / y, z = 2, где x = dx / xRes, y = dy / yRes. После этого вектор (x, y, z) нужно нормировать Получили 3-х мерные нормали (normal nm ) в подпространстве, натянутом на векторы xDir, yDir, zDir Яркость в точке (n, m): brightness = lightDirnormal nm, где lightDir – направление на источник света

22

23

24

25

26

27