Введение в компьютерные методы метрико- топологических построений. Г.Г.Рябов (МГУ) 2007г. - презентация

1 Введение в компьютерные методы метрико- топологических построений. Г.Г.Рябов (МГУ) 2007г

2 Современная вычислительная среда. Глобальная модель циркуляции «атмосфера- океан»(МITcgm) узлов(кубов). Глобальная модель циркуляции «атмосфера- океан»(МITcgm) узлов(кубов). Обтекание «Аэробуса»-10 7 тетраэдров. Обтекание «Аэробуса»-10 7 тетраэдров. Биотомограф-1000х1000х1000(10 9 ) вокселов. Биотомограф-1000х1000х1000(10 9 ) вокселов. Фармацевтика- триангуляция молекулярной поверхности Фармацевтика- триангуляция молекулярной поверхности Перколяционные задачи- решетка Перколяционные задачи- решетка Архитектура и строительство -минимальные поверхности. Архитектура и строительство -минимальные поверхности. Научно-техническая визуализация треугольников. Научно-техническая визуализация треугольников.

3 Геометрико - топологические особенности. Меры по сохранению устойчивости решения(число и геометрия тетраэдров). Меры по сохранению устойчивости решения(число и геометрия тетраэдров). Проведение оперативных преобразований среды.(кластеризация и разбиение для распараллеливания вычислений). Проведение оперативных преобразований среды.(кластеризация и разбиение для распараллеливания вычислений). Сохранение при преобразованиях топологических инвариантов и заданных геометрических отношений(тел). Сохранение при преобразованиях топологических инвариантов и заданных геометрических отношений(тел).

4 Digital geometry and topology Discrete differential geometry США ( MIT, Caltech, Stanford) США ( MIT, Caltech, Stanford) Франция(INRIA) Франция(INRIA) Германия (Un.Gumbold) Германия (Un.Gumbold) Швеция (Un.Upsala) Швеция (Un.Upsala) Венгрия (Un.Seged) Венгрия (Un.Seged) Нов.Зеландия (Un.Oakland) Нов.Зеландия (Un.Oakland) Япония (Un.Chiba) Япония (Un.Chiba)

5

6 Комбинаторная топология. Конечный элемент- симплекс. Конечный элемент- симплекс. Комплекс – множество правильно расположенных симплексов. Комплекс – множество правильно расположенных симплексов. Звездный полиэдр- окрестность. Звездный полиэдр- окрестность. Преобразование комплексов -сумма допустимых преобразований звездных полиэдров. Преобразование комплексов -сумма допустимых преобразований звездных полиэдров.

7 Целые точки и простые ребра. Симплексы с вершинами в целых точках и простыми ребрами (не имеющими внутренних целых точек). Симплексы с вершинами в целых точках и простыми ребрами (не имеющими внутренних целых точек). Модельные множества (Z n, Up), n-размерность пространства, p-норма простых ребер(p=max I x i I ;i=1-n). Модельные множества (Z n, Up), n-размерность пространства, p-норма простых ребер(p=max I x i I ;i=1-n). Основные построения для n=3,4,5,6 ; p=1; Основные построения для n=3,4,5,6 ; p=1;

8 Основная последовательность базисных построений. Построение однородных звездчатых полиэдров (стереоэдров) на простых симплексах. Построение однородных звездчатых полиэдров (стереоэдров) на простых симплексах. Покрытие такими полиэдрами всего пространства(нормальное,правильное разбиение). Покрытие такими полиэдрами всего пространства(нормальное,правильное разбиение). Определение симплициальных комплексов. Определение симплициальных комплексов. Аналоги гомотопных преобразований на комплексах-преобразования на граничных зв.полиэдрах (гомотопные волны). Аналоги гомотопных преобразований на комплексах-преобразования на граничных зв.полиэдрах (гомотопные волны).

9 (Z 2, U 1 ) и все 6 типов 2d зв.полиэдров

10 Перестройки разбиения - выделение параллелограммов и замена диагоналей.

11 Двоичный код-инвариант при перестройках 1-го типа (диагональ-диагональ)

12 Классификация типов зв. полиэдров. 1.Транслируемые. 1.Транслируемые. 2.Конгруэнтные. 2.Конгруэнтные. 3.Парнотранслируемые. 3.Парнотранслируемые.

13 Перечисление всех неконгруэнтных триангуляций куба. Любая триангуляция на вершинах куба порождает диагональное разбиение граней куба. Любая триангуляция на вершинах куба порождает диагональное разбиение граней куба. Каждому разбиению соответствует вектор степеней вершин (инцидентных диагоналей). Каждому разбиению соответствует вектор степеней вершин (инцидентных диагоналей). Разные векторы- неконгруэнтные триангуляции. Разные векторы- неконгруэнтные триангуляции. v1-1,v2-1,v3-2,v4-2,v5-3,v6-1, v7-0,v8-2; v1-1,v2-1,v3-2,v4-2,v5-3,v6-1, v7-0,v8-2; (1,3,3,1) (1,3,3,1)

14 Диофантовы уравнения. i-число диагоналей сходящихся к вершине. i-число диагоналей сходящихся к вершине. x i -число вершин с i сходящимися диагоналями. x i -число вершин с i сходящимися диагоналями. Σ x i =8; i=0-3; Σ x i =8; i=0-3; Σ i x i =12; i=0-3; Σ i x i =12; i=0-3; Решения: (2,2,2,2);(0,6,0,2); (1,3,3,1); (2,0,6,0);(4,0,4,0);(0,4,4,0); Решения: (2,2,2,2);(0,6,0,2); (1,3,3,1); (2,0,6,0);(4,0,4,0);(0,4,4,0);

15 Все типы неконгруэнтных триангуляций куба. (0,6,0,2) (2,0,6,0) (1,3,3,1) (2,2,2,2) (4,0,0,4) (0,6,0,2) (2,0,6,0) (1,3,3,1) (2,2,2,2) (4,0,0,4)

16 Решение (0,4,4,0) не соответствует никакой триангуляции. Ни при какой диагонали внутри куба невозможно правильное разбиение на пирамиды. Ни при какой диагонали внутри куба невозможно правильное разбиение на пирамиды.

17 Все 3d звездчатые полиэдры (4 типа симплексов) на (Z3,V1).

18 Разбиение кубов проекциями- транслируемая полиэдризация R 3. Разбиение единичного куба на 6 тетраэдров- симплексов. Разбиение единичного куба на 6 тетраэдров- симплексов.

19 Ребра и грани вокруг (0,0,0) Трансляция построений во все кубы R3. Трансляция построений во все кубы R3. Звездный полиэдр для (0,0,0) Звездный полиэдр для (0,0,0)

20 Cтруктура полиэдра. 24 симпплекса внутри транслируемого звездного полиэдра. 24 симпплекса внутри транслируемого звездного полиэдра. Объем полиэдра V=24x1/6=4. Объем полиэдра V=24x1/6=4.

21 Транслируемый 3d звездчатый полиэдр MSP. Кубододекаэдр- 14,36,24. Кубододекаэдр- 14,36,24. Вершин-15 (1+14) Вершин-15 (1+14) Ребер- 50(14+36) Ребер- 50(14+36) Граней-48(24+24) Граней-48(24+24) 3d cимплексов-24 3d cимплексов-24 Объем=4 Объем=4 Строго выпуклый (по Малеру) Строго выпуклый (по Малеру)

22 Дуальный полиэдр.

23 Построение транслируемых nd-полиэдров как отображение R n на подпространства.

24 Транслируемый 4d зв. полиэдр. Два полярных 4d куба с одной общей вершиной и доп. ребрами. Два полярных 4d куба с одной общей вершиной и доп. ребрами.

25 Структура n-куба. f(I n )=(f 0,f 1,f 2,…f n-1,f n ) – вектор граней. f(I n )=(f 0,f 1,f 2,…f n-1,f n ) – вектор граней. f 0 -число вершин; f 0 -число вершин; f 1 -число ребер; f 1 -число ребер; f 2 -число квадратов; f 2 -число квадратов; f 3 -число кубов;… f 3 -число кубов;… f n -I n ; f n -I n ; f k =C(n,k)2 n-k ; f k =C(n,k)2 n-k ; f(I 4 )=(16,32,24,8,1); f(I 4 )=(16,32,24,8,1);

26 Характеристика Эйлера-Пуанкаре Формула Эйлера:В-Р+Г=2 Формула Эйлера:В-Р+Г=2 Топологический инвариант Топологический инвариант χ=f 0 -f 1 +f 2 -f 3 +…+(-1) n-1 f n-1 ; χ=f 0 -f 1 +f 2 -f 3 +…+(-1) n-1 f n-1 ;

27 Треугольник и пирамида Паскаля. Треугольник C(x,y)=C(x-1,y)+C(x,y-1);C(0,0)=1; Треугольник C(x,y)=C(x-1,y)+C(x,y-1);C(0,0)=1; Пирамида V(x,y,z)=V(x-1,y,z)+V(x,y-1,z)+V(x,y,z-1); V(0,0,0)=1; Пирамида V(x,y,z)=V(x-1,y,z)+V(x,y-1,z)+V(x,y,z-1); V(0,0,0)=1;

28 Триномиальные коэффициенты. (a+b+c) n (a+b+c) n V(n,k,l)a l b k c n-k-l V(n,k,l)a l b k c n-k-l l=x;k=y;n=x+y+z; l=x;k=y;n=x+y+z; V(n,k,l)= n!/l!k!(n-k-l)! V(n,k,l)= n!/l!k!(n-k-l)! Σ V(n,k,l)=C(n,k)2 n-k ; l=1-(n-k); Σ V(n,k,l)=C(n,k)2 n-k ; l=1-(n-k); ΣV(n,k,l)=f k ; ΣV(n,k,l)=f k ; (16,32,24,8) (16,32,24,8)

29 Кодирование k-граней. Каждой k-грани соответствует кратчайший путь по решетке в вершину слоя n c y=k; Каждой k-грани соответствует кратчайший путь по решетке в вершину слоя n c y=k; Каждый путь кодируется троичным кодом. {0,1,2} Каждый путь кодируется троичным кодом. {0,1,2}

30 Кодировка I в 0001 в 0002 р 0010 в 0011 в 0012 р 0000 в 0001 в 0002 р 0010 в 0011 в 0012 р 0020 р 0021 р 0022 к 0100 в 0101 в 0102 р 0020 р 0021 р 0022 к 0100 в 0101 в 0102 р 0200 р 0201 р 0202 к 0210 р 0211 р 0212 к 0200 р 0201 р 0202 к 0210 р 0211 р 0212 к 0220 к … 2220 г 2221 г 2222 I к … 2220 г 2221 г 2222 I 4 Вершины- традиционная кодировка. Вершины- традиционная кодировка. Ребра- коды с одной «двойкой» Ребра- коды с одной «двойкой» К-грани- с к «двойками» К-грани- с к «двойками»

31 Геометрическая интерпретация Код 2120 Код 2120 Ребра 0020 и > грань 2020 Ребра 0020 и > грань 2020 Грань 2020 транслируется из (0000) в (0100) Грань 2020 транслируется из (0000) в (0100)

32 Генерация примитивной триангуляции (путевые симплексы) Симметрическая группа подстановок S n. Симметрическая группа подстановок S n. s i S n s i S n … n … n a i1 a i2 a i3 … a in a i1 a i2 a i3 … a in e ai1, e ai1 +e ai2, e ai1 +e ai2 +e ai3,… - последовательные вершины симплекса e ai1, e ai1 +e ai2, e ai1 +e ai2 +e ai3,… - последовательные вершины симплекса Рис. -> Рис. ->

33 Примитивная триангуляция I cимплекса могут быть закодированы 5-ью двоичными разрядами. 24 cимплекса могут быть закодированы 5-ью двоичными разрядами.

34 3d звезда-полиэдр и ее симплексы. Вклад кубов (по числу симплексов) из 8 октантов, содержащих (000). Вклад кубов (по числу симплексов) из 8 октантов, содержащих (000).

35 Симплициальная структура транслируемого nd звезды-полиэдра W(k)-число симплексов с вершиной r=k W(k)-число симплексов с вершиной r=k S(k)-число n- кубов с вершиной r=k в (00…0) S(k)-число n- кубов с вершиной r=k в (00…0) W(k)=k!(n-k)!; W(k)=k!(n-k)!; S(k)=C(n,k); S(k)=C(n,k); S=Σ W(k)S(k)= (n+1)!; S=Σ W(k)S(k)= (n+1)!; V(P)=n+1; V(P)=n+1;

36 Кодирование симплексов. 1234,1243,1324,1342,1423,1432, 1234,1243,1324,1342,1423,1432, ,2143,2314,2341,2413,2431, 2134,2143,2314,2341,2413,2431, ,3142,3214,3241,3412,3421, 3124,3142,3214,3241,3412,3421, ,4132,4213,4231,4312, ,4132,4213,4231,4312, a 0 n!+a 1 (n-1)!+…+a n-2 2!+a n-1 1!=; a k 2, 1+1=2-ая из ост.->3; и ост.1 21=(3,1,1) -> 4231:3+1=4, 1+1=2-ая из ост. ->2, 1+1=2-ая из ост.->3; и ост.1

37 Транслируемые звездчатые nd-полиэдры. 2d 3d 4d 5d 6d 7d 2d 3d 4d 5d 6d 7d В В S S V V

38 Гомотопные расширения и сжатия комплексов-сумма преобразований MSP на границе комплексов. Топологический контроль-проверка связности в MSP до и после преобразования. Топологический контроль-проверка связности в MSP до и после преобразования. Для общего 3d случая объем вычислений Q~ N 3 x V x E x N (для N =10 3 Q= память M= 100Гb ) Для общего 3d случая объем вычислений Q~ N 3 x V x E x N (для N =10 3 Q= память M= 100Гb ) Для топол. процессора Q= M=1Гb Для топол. процессора Q= M=1Гb

39 Допустимые преобразования без склеек и разрывов. Расширение «желтого» без склеек и разрывов «желтого» и «красного» зависит только от ситуации в «выколотом» зв.полиэдре. Расширение «желтого» без склеек и разрывов «желтого» и «красного» зависит только от ситуации в «выколотом» зв.полиэдре.

40 Анализ связности множеств М1 и М2 на границе полиэдра. М1 на границе несвязно. М1 на границе несвязно. М2 на границе связно. М2 на границе связно. Если переход (000) в М1, то М1 и М2 связны- изменения в связностях недопустимы! Если переход (000) в М1, то М1 и М2 связны- изменения в связностях недопустимы!

41 Три 2d комплекса

42 Расширение черного.

43

44 Сжатие черного.

45 Приближение к евклидовой метрике на Zn. Метрика на ребрах звездчатых полиэдров (многогранная метрика) далека от евклидовой. Метрика на ребрах звездчатых полиэдров (многогранная метрика) далека от евклидовой. Расширить множество простых ребер (увеличить норму) в зависимости от заданной погрешности приближения. Расширить множество простых ребер (увеличить норму) в зависимости от заданной погрешности приближения.

46 Линейные преобразования на решетках. Унимодулярные матрицы- модуль определителя =1. Унимодулярные матрицы- модуль определителя =1. Линейные унимодулярные преобразования сохраняют площадь (объем) фигур(тел). Линейные унимодулярные преобразования сохраняют площадь (объем) фигур(тел).

47 Составление веера. Стыковку секторов веера обеспечивают «соседние» унимодулярные матрицы. Стыковку секторов веера обеспечивают «соседние» унимодулярные матрицы.

48 Несократимые дроби и простые ребра (веер Фарея). В каждом секторе целые точки образуют решетки с базисами {(0,1),(1,1)}; {(1,1),(1,0)}. В каждом секторе целые точки образуют решетки с базисами {(0,1),(1,1)}; {(1,1),(1,0)}. С увеличением порядка Ф(к) длина по ребрам решеток приближается к евклидовой. С увеличением порядка Ф(к) длина по ребрам решеток приближается к евклидовой. Δ=L-Le/Le=~ φ 2 /4+o(φ 4 ); Δ=L-Le/Le=~ φ 2 /4+o(φ 4 );

49 Увеличение порядка Ф(к).

50

51 Отображения Z 2 (0,π/2) на Z 2 (i,i+1)

52 Веер Фарея 3-го порядка.

53 Неравномерность уменьшения углов в секторах веера. Для веера Ф(3): Для веера Ф(3): Сектор ((0/1)(1/3))~1/3. Сектор ((0/1)(1/3))~1/3. Cектор ((1/3)(1/2))~1/6. Cектор ((1/3)(1/2))~1/6. Коррекция процедуры генерации несократимых дробей-наибольшие углы разбивать чаще. Коррекция процедуры генерации несократимых дробей-наибольшие углы разбивать чаще.

54 Приближение к евклидовой метрике. Для сектора веера с базисом b i,b j и углом φ: Для сектора веера с базисом b i,b j и углом φ: L=λ 1 ρ(b i )+λ 2 ρ(b j );на решетке, L=λ 1 ρ(b i )+λ 2 ρ(b j );на решетке, L e -евклидова длина между этими точками. L e -евклидова длина между этими точками. Максимальная отн. погрешность в секторе: Максимальная отн. погрешность в секторе: Δm(φ)=L-L e /L e =φ 2 /4+O(φ 4 /16); Δm(φ)=L-L e /L e =φ 2 /4+O(φ 4 /16);

55 Для построения веера в Rn. Множество целочисленных квадратных матриц:{Ai}. Множество целочисленных квадратных матриц:{Ai}. Ai =1 сохраняет объемы. Ai =1 сохраняет объемы. Бесконечная группа с Е-ед.диагон.м. Бесконечная группа с Е-ед.диагон.м. Аналог несократимых дробей- простые целые n-мерные вектора (компоненты вектора, как целые числа не имеют общего делителя >1). Аналог несократимых дробей- простые целые n-мерные вектора (компоненты вектора, как целые числа не имеют общего делителя >1).

56 Построение 3d веера для заданной Δ- итерационная процедура на1/48 сферы. Вырезанному сектору соответствует матрица Ао из простых векторов. Вырезанному сектору соответствует матрица Ао из простых векторов. IAoI=1; IAoI=1; Замена строки в матрице суммой строки с другой не меняет основных свойств матрицы. Замена строки в матрице суммой строки с другой не меняет основных свойств матрицы.

57 Веерная триангуляция. Определение грани(ребра) с макс. углом и разбиение ребра сложением векторов (строк матрицы). Определение грани(ребра) с макс. углом и разбиение ребра сложением векторов (строк матрицы). Продолжение процедуры, пока макс. угол

58 Nd-случай. Для nd случая триангулируется (а затем и хранится в памяти) 1/2 n n! – часть nd сферы. Для nd случая триангулируется (а затем и хранится в памяти) 1/2 n n! – часть nd сферы. Вся nd сфера может покрываться зеркальными отображениями. Вся nd сфера может покрываться зеркальными отображениями.

59 Проекция 3d веера на сферу (для Δ=L-Le/Le=0,001) После зеркальных отображений 1/48 части на всю сферу. После зеркальных отображений 1/48 части на всю сферу. Веер содержит 7610 ребер. Веер содержит 7610 ребер.

60 Сравнение по числу ребер 3d веера Фарея и решеточного расслоения. K … 19 K … 19 Δ(%) 4,85 2,41 1,44 1,17 0,76 … 0,1 Δ(%) 4,85 2,41 1,44 1,17 0,76 … 0,1 N(k) … (~k 3 ) N(k) … (~k 3 ) N* … 7610 (~k 2 ) N* … 7610 (~k 2 )

61 Основные операции прототипа топологического процессора. Задание решетки и метода полиэдризации. Задание решетки и метода полиэдризации. Задание границ и преград. Задание границ и преград. Задание комплексов. Индексные массивы(1:128) Задание комплексов. Индексные массивы(1:128) Определение связности комплексов и характеристики Эйлера- Пуанкаре. Определение связности комплексов и характеристики Эйлера- Пуанкаре. Задание преобразований и их режимов(целевых функций). Задание преобразований и их режимов(целевых функций). Проведение преобразований. Анализ MSP-один такт! Проведение преобразований. Анализ MSP-один такт! Выделение триангулированной границы. Выделение триангулированной границы. Генерация решеточного веера по заданной погрешности. Генерация решеточного веера по заданной погрешности. Прогон метрической волны от множества-источника и построение эквидистантного графа. Прогон метрической волны от множества-источника и построение эквидистантного графа. Операции над эквидистантными графами. Операции над эквидистантными графами. Все операции эмулированы и верифицированы на решетках до 200х200х200. Все операции эмулированы и верифицированы на решетках до 200х200х200. Видеопоказ на Видеопоказ на

62 Построение «сферы» как 2d многообразия. Заданы центр «сферы» и преграды(2пластины). Заданы центр «сферы» и преграды(2пластины). Построить «сферу» минимального радиуса. Построить «сферу» минимального радиуса. Условие: преграды внутри «сферы», Δ = 0,01; Условие: преграды внутри «сферы», Δ = 0,01; Cхема решения- генерация веера для Δ=0,01;метрическая волна и эквидистантный граф;сжатие комплекса до преград; выделение трианг. границы. Cхема решения- генерация веера для Δ=0,01;метрическая волна и эквидистантный граф;сжатие комплекса до преград; выделение трианг. границы. ( симплексов) ( симплексов) Т(2Ггц,512Mb)=2мин. Т(2Ггц,512Mb)=2мин.

63 Ближайшие задачи. Перенос комплекса на кластер НИВЦ МГУ с целями: Перенос комплекса на кластер НИВЦ МГУ с целями: 1.Решение задач на решетках:3d ,4d-500 4,5d-200 5,6d Решение задач на решетках:3d ,4d-500 4,5d-200 5,6d Использование распараллеливания, потенциально близкого к клеточным автоматам. 2.Использование распараллеливания, потенциально близкого к клеточным автоматам. 3.Полиэкранная визуализация сечений многомерных комплексов. 3.Полиэкранная визуализация сечений многомерных комплексов.

64 Основные ссылки. Л.С.Понтрягин. Основы комбинаторной топологии. Л.С.Понтрягин. Основы комбинаторной топологии. П.С.Александров. Комбинаторная топология. П.С.Александров. Комбинаторная топология. Б.Н.Делоне. Теория стереоэдров. Б.Н.Делоне. Теория стереоэдров. К.Чандрасекхаран. Введение в аналитическую теорию чисел. К.Чандрасекхаран. Введение в аналитическую теорию чисел. Д.Касселс. Введение в геометрию чисел. Д.Касселс. Введение в геометрию чисел. И.М.Гельфанд. Лекции по линейной алгебре. И.М.Гельфанд. Лекции по линейной алгебре. В.А.Ковалевский. Конечная топология. В.А.Ковалевский. Конечная топология. Ж.Бертран, М.Купри. Гомотопные преобразования. Ж.Бертран, М.Купри. Гомотопные преобразования. И.Кенмочи, А.Имийя. Глобальная полиэдризация. И.Кенмочи, А.Имийя. Глобальная полиэдризация. Г.Г.Рябов. Метрические и топологические волны на решетках. Г.Г.Рябов. Метрические и топологические волны на решетках. О.Д.Авраамова. Язык VRML. О.Д.Авраамова. Язык VRML.

65 Поклон корифеям! П.С.Александров Л.С.Понтрягин Б.Н Делоне П.С.Александров Л.С.Понтрягин Б.Н Делоне