uzluga.ru
добавить свой файл
1


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

  • Г.Г.Рябов (МГУ)

  • 2007г


Современная вычислительная среда.

  • Глобальная модель циркуляции «атмосфера-океан»(МITcgm)-107-109 узлов(кубов).

  • Обтекание «Аэробуса»-107 тетраэдров.

  • Биотомограф-1000х1000х1000(109) вокселов.

  • Фармацевтика- триангуляция молекулярной поверхности-107.

  • Перколяционные задачи- решетка 109.

  • Архитектура и строительство -минимальные поверхности.

  • Научно-техническая визуализация -107-108 треугольников.



Геометрико - топологические особенности.

  • Меры по сохранению устойчивости решения(число и геометрия тетраэдров).

  • Проведение оперативных преобразований среды.(кластеризация и разбиение для распараллеливания вычислений).

  • Сохранение при преобразованиях топологических инвариантов и заданных геометрических отношений(тел).



Digital geometry and topology Discrete differential geometry

  • США ( MIT, Caltech, Stanford)

  • Франция(INRIA)

  • Германия (Un.Gumbold)

  • Швеция (Un.Upsala)

  • Венгрия (Un.Seged)

  • Нов.Зеландия (Un.Oakland)

  • Япония (Un.Chiba)





Комбинаторная топология.

  • Конечный элемент-симплекс.

  • Комплекс –множество правильно расположенных симплексов.

  • Звездный полиэдр-окрестность.

  • Преобразование комплексов -сумма допустимых преобразований звездных полиэдров.



Целые точки и простые ребра.

  • Симплексы с вершинами в целых точках и простыми ребрами (не имеющими внутренних целых точек).

  • Модельные множества (Zn, Up), n-размерность пространства, p-норма простых ребер(p=max IxiI;i=1-n).

  • Основные построения для n=3,4,5,6 ; p=1;



Основная последовательность базисных построений.

  • Построение однородных звездчатых полиэдров (стереоэдров) на простых симплексах.

  • Покрытие такими полиэдрами всего пространства(нормальное,правильное разбиение).

  • Определение симплициальных комплексов.

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



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



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



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



Классификация типов зв. полиэдров.

  • 1.Транслируемые.

  • 2.Конгруэнтные.

  • 3.Парнотранслируемые.



Перечисление всех неконгруэнтных триангуляций куба.

  • Любая триангуляция на вершинах куба порождает диагональное разбиение граней куба.

  • Каждому разбиению соответствует вектор степеней вершин (инцидентных диагоналей).

  • Разные векторы-неконгруэнтные триангуляции.

  • v1-1,v2-1,v3-2,v4-2,v5-3,v6-1, v7-0,v8-2;

  • (1,3,3,1)



Диофантовы уравнения.

  • 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);



Все типы неконгруэнтных триангуляций куба.

  • (0,6,0,2) (2,0,6,0) (1,3,3,1) (2,2,2,2) (4,0,0,4)



Решение (0,4,4,0) не соответствует никакой триангуляции.

  • Ни при какой диагонали внутри куба невозможно правильное разбиение на пирамиды.



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



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

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



Ребра и грани вокруг (0,0,0)

  • Трансляция построений во все кубы R3.

  • Звездный полиэдр для (0,0,0)



Cтруктура полиэдра.

  • 24 симпплекса внутри транслируемого звездного полиэдра.

  • Объем полиэдра V=24x1/6=4.



Транслируемый 3d звездчатый полиэдр MSP.

  • Кубододекаэдр-14,36,24.

  • Вершин-15 (1+14)

  • Ребер- 50(14+36)

  • Граней-48(24+24)

  • 3d cимплексов-24

  • Объем=4

  • Строго выпуклый (по Малеру)



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



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



Транслируемый 4d зв. полиэдр.

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



Структура 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);



Характеристика Эйлера-Пуанкаре

  • Формула Эйлера:В-Р+Г=2

  • Топологический инвариант

  • χ=f0-f1+f2-f3+…+(-1)n-1fn-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;



Триномиальные коэффициенты.

  • (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)



Кодирование k-граней.

  • Каждой k-грани соответствует кратчайший путь по решетке в вершину слоя n c y=k;

  • Каждый путь кодируется троичным кодом. {0,1,2}



Кодировка I4

  • 0000 в 0001 в 0002 р 0010 в 0011 в 0012 р

  • 0020 р 0021 р 0022 к 0100 в 0101 в 0102 р

  • 0200 р 0201 р 0202 к 0210 р 0211 р 0212 к

  • 0220 к … 2220 г 2221 г 2222 I4

  • Вершины- традиционная кодировка.

  • Ребра- коды с одной «двойкой»

  • К-грани- с к «двойками»



Геометрическая интерпретация

  • Код 2120

  • Ребра 0020 и 2000 -> грань 2020

  • Грань 2020 транслируется из (0000) в (0100)



Генерация примитивной триангуляции (путевые симплексы)

  • Симметрическая группа подстановок Sn.

  • si € Sn

  • 1 2 3 … n

  • ai1 ai2 ai3… ain

  • eai1, eai1+eai2, eai1+eai2+eai3,… -последовательные вершины симплекса

  • Рис. -> 1 2 4 3



Примитивная триангуляция I4.

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



3d звезда-полиэдр и ее симплексы.

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



Симплициальная структура транслируемого 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;



Кодирование симплексов .

  • 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

  • 21=(3,1,1) -> 4231:3+1=4, 1+1=2-ая из ост. ->2, 1+1=2-ая из ост.->3; и ост.1



Транслируемые звездчатые 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



Гомотопные расширения и сжатия комплексов-сумма преобразований MSP на границе комплексов.

  • Топологический контроль-проверка связности в MSP до и после преобразования.

  • Для общего 3d случая объем вычислений Q~ N3xVxExN (для N =103 Q= 1014 память M= 100Гb )

  • Для топол. процессора Q=1011 M=1Гb



Допустимые преобразования без склеек и разрывов.

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



Анализ связности множеств М1 и М2 на границе полиэдра.

  • М1 на границе несвязно.

  • М2 на границе связно.

  • Если переход (000) в М1, то М1 и М2 связны- изменения в связностях недопустимы!



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



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



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



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



Приближение к евклидовой метрике на Zn.

  • Метрика на ребрах звездчатых полиэдров (многогранная метрика) далека от евклидовой.

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



Линейные преобразования на решетках.

  • Унимодулярные матрицы- модуль определителя =1.

  • Линейные унимодулярные преобразования сохраняют площадь (объем) фигур(тел).



Составление веера.

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



Несократимые дроби и простые ребра (веер Фарея).

  • В каждом секторе целые точки образуют решетки с базисами {(0,1),(1,1)}; {(1,1),(1,0)}.

  • С увеличением порядка Ф(к) длина по ребрам решеток приближается к евклидовой.

  • Δ=L-Le/Le=~ φ2/4+o(φ4);



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



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



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



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



Неравномерность уменьшения углов в секторах веера.

  • Для веера Ф(3):

  • Сектор ((0/1)(1/3))~1/3.

  • Cектор ((1/3)(1/2))~1/6.

  • Коррекция процедуры генерации несократимых дробей-наибольшие углы разбивать чаще.



Приближение к евклидовой метрике.

  • Для сектора веера с базисом bi,bj и углом φ:

  • L=λ1ρ(bi)+λ2ρ(bj);на решетке,

  • Le-евклидова длина между этими точками.

  • Максимальная отн. погрешность в секторе:

  • Δm(φ)=L-Le/Le=φ2/4+O(φ4/16);



Для построения веера в Rn.

  • Множество целочисленных квадратных матриц:{Ai}.

  • Ai =1 сохраняет объемы.

  • Бесконечная группа с Е-ед.диагон.м.

  • Аналог несократимых дробей- простые целые n-мерные вектора (компоненты вектора, как целые числа не имеют общего делителя >1).



Построение 3d веера для заданной Δ-итерационная процедура на1/48 сферы.

  • Вырезанному сектору соответствует матрица Ао из простых векторов.

  • IAoI=1;

  • Замена строки в матрице суммой строки с другой не меняет основных свойств матрицы.



Веерная триангуляция.

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

  • Продолжение процедуры, пока макс. угол <φ0(Δ).

  • Затем зеркальные отображения на всю сферу.



Nd-случай.

  • Для nd случая триангулируется (а затем и хранится в памяти) 1/2n n! – часть nd сферы.

  • Вся nd сфера может покрываться зеркальными отображениями.



Проекция 3d веера на сферу (для Δ=L-Le/Le=0,001)

  • После зеркальных отображений 1/48 части на всю сферу.

  • Веер содержит 7610 ребер.



Сравнение по числу ребер 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)



Основные операции прототипа топологического процессора.

  • Задание решетки и метода полиэдризации.

  • Задание границ и преград.

  • Задание комплексов. Индексные массивы(1:128)

  • Определение связности комплексов и характеристики Эйлера-Пуанкаре.

  • Задание преобразований и их режимов(целевых функций).

  • Проведение преобразований. Анализ MSP-один такт!

  • Выделение триангулированной границы.

  • Генерация решеточного веера по заданной погрешности.

  • Прогон метрической волны от множества-источника и построение эквидистантного графа.

  • Операции над эквидистантными графами.

  • Все операции эмулированы и верифицированы на решетках до 200х200х200.

  • Видеопоказ на http://www.vizcom.srcc.msu.ru



Построение «сферы» как 2d многообразия.

  • Заданы центр «сферы» и преграды(2пластины).

  • Построить «сферу» минимального радиуса.

  • Условие: преграды внутри «сферы», Δ = 0,01;

  • Cхема решения-генерация веера для Δ=0,01;метрическая волна и эквидистантный граф;сжатие комплекса до преград; выделение трианг. границы.

  • (750 000 симплексов)

  • Т(2Ггц,512Mb)=2мин.



Ближайшие задачи.

  • Перенос комплекса на кластер НИВЦ МГУ с целями:

  • 1.Решение задач на решетках:3d-20003,4d-5004,5d-2005,6d-506.

  • 2.Использование распараллеливания, потенциально близкого к клеточным автоматам.

  • 3.Полиэкранная визуализация сечений многомерных комплексов.



Основные ссылки.

  • Л.С.Понтрягин. Основы комбинаторной топологии.

  • П.С.Александров. Комбинаторная топология.

  • Б.Н.Делоне. Теория стереоэдров.

  • К.Чандрасекхаран. Введение в аналитическую теорию чисел.

  • Д.Касселс. Введение в геометрию чисел.

  • И.М.Гельфанд. Лекции по линейной алгебре.

  • В.А.Ковалевский. Конечная топология.

  • Ж.Бертран, М.Купри. Гомотопные преобразования.

  • И.Кенмочи, А.Имийя. Глобальная полиэдризация.

  • Г.Г.Рябов. Метрические и топологические волны на решетках.

  • О.Д.Авраамова. Язык VRML.



Поклон корифеям!

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