'

Введение в компьютерные методы метрико-топологических построений.

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

(Z2, U1) и все 6 типов 2d зв.полиэдров


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

Диофантовы уравнения. i-число диагоналей сходящихся к вершине. xi-число вершин с i сходящимися диагоналями. ? xi =8; i=0-3; ? i xi=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);


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

Структура n-куба. f(In)=(f0,f1,f2,…fn-1,fn) – вектор граней. f0-число вершин; f1-число ребер; f2-число квадратов; f3-число кубов;… fn-In; fk=C(n,k)2n-k; f(I4)=(16,32,24,8,1);


Слайд 25

Характеристика Эйлера-Пуанкаре Формула Эйлера:В-Р+Г=2 Топологический инвариант ?=f0-f1+f2-f3+…+(-1)n-1fn-1;


Слайд 26

Треугольник и пирамида Паскаля. Треугольник 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;


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

Генерация примитивной триангуляции (путевые симплексы) Симметрическая группа подстановок Sn. si € Sn 1 2 3 … n ai1 ai2 ai3… ain eai1, eai1+eai2, eai1+eai2+eai3,… -последовательные вершины симплекса Рис. -> 1 2 4 3


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

Кодирование симплексов . 1234,1243,1324,1342,1423,1432, 0 1 2 3 4 5 2134,2143,2314,2341,2413,2431, 5 7 8 9 10 11 3124,3142,3214,3241,3412,3421, 12 13 14 15 16 17 4123,4132,4213,4231,4312,4321 18 19 20 21 22 23 a0 n!+a1(n-1)!+…+an-2 2!+an-1 1!=№; ak<k+1; 21=(3,1,1) -> 4231:3+1=4, 1+1=2-ая из ост. ->2, 1+1=2-ая из ост.->3; и ост.1


Слайд 36

Транслируемые звездчатые nd-полиэдры. 2d 3d 4d 5d 6d 7d В 6 14 30 62 126 254 S 6 24 120 720 5040 40320 V 3 4 5 6 7 8


Слайд 37

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


Слайд 38

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


Слайд 39

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


Слайд 40

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


Слайд 41

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


Слайд 42

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


Слайд 43

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


Слайд 44

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


Слайд 45

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


Слайд 46

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


Слайд 47

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


Слайд 48

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


Слайд 49

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


Слайд 50

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


Слайд 51

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


Слайд 52

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


Слайд 53

Приближение к евклидовой метрике. Для сектора веера с базисом bi,bj и углом ?: L=?1?(bi)+?2?(bj);на решетке, Le-евклидова длина между этими точками. Максимальная отн. погрешность в секторе: ?m(?)=L-Le/Le=?2/4+O(?4/16);


Слайд 54

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


Слайд 55

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


Слайд 56

Веерная триангуляция. Определение грани(ребра) с макс. углом и разбиение ребра сложением векторов (строк матрицы). Продолжение процедуры, пока макс. угол <?0(?). Затем зеркальные отображения на всю сферу. 000


Слайд 57

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


Слайд 58

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


Слайд 59

Сравнение по числу ребер 3d веера Фарея и решеточного расслоения . K 2 3 4 5 6 … 19 ?(%) 4,85 2,41 1,44 1,17 0,76 … 0,1 N(k) 98 290 578 1154 1730 … 50114 (~k3) N* 74 194 266 530 722 … 7610 (~k2)


Слайд 60

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


Слайд 61

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


Слайд 62

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


Слайд 63

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


Слайд 64

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


×

HTML:





Ссылка: